Annihilation Filter Approach For Estimating Graph Dynamics From Diffusion Processes

We propose an approach for estimating graph diffusion processes using annihilation filters from a finite set of observations of the diffusion process made at regular intervals. Our approach is based on the key observation that a graph diffusion process can be entirely estimated by estimating the eigenvalues and the contributions from the corresponding eigenvectors of the graph-Laplacian, that we achieve through the use of annihilation filters applied in a node-wise manner. We show that the diffusion process can be exactly estimated when the number of samples exceeds 2N + 1, where N is the number of nodes in the graph. We further show how our approach can be used to explicitly learn the underlying graph using an eigenvector proxy. We demonstrate the potential of our approach using experiments with synthesized small-world graphs and real-world network time series data.