Source Localization on Graphs via l1 Recovery and Spectral Graph Theory
This addresses source localization in diffusion processes on graphs, which is incremental as it builds on existing sparse recovery and spectral graph theory methods.
The paper tackles source localization on graphs by combining sparse recovery and diffusion kernel learning using l1 regularization, recovering sources from a single snapshot of diffusion. Results show successful learning on synthetic data and validation with cholera mortality and atmospheric tracer data, with accuracy depending on graph construction.
We cast the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion kernel learning. An l1 regularization term enforces the sparsity constraint while we recover the sources of diffusion from a single snapshot of the diffusion process. The diffusion kernel is estimated by assuming the process to be as generic as the standard heat diffusion. We show with synthetic data that we can concomitantly learn the diffusion kernel and the sources, given an estimated initialization. We validate our model with cholera mortality and atmospheric tracer diffusion data, showing also that the accuracy of the solution depends on the construction of the graph from the data points.