2016/05/09 by Bastien Pasdeloup, Pasdeloup, Bastien, Vincent Gripon +7
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Opinion Dynamics and Social Influence
paper · pdf · doi:10.48550/arxiv.1605.02569
openalex publication_date 2016/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many tools from the field of graph signal processing exploit knowledge of the\nunderlying graph's structure (e.g., as encoded in the Laplacian matrix) to\nprocess signals on the graph. Therefore, in the case when no graph is\navailable, graph signal processing tools cannot be used anymore. Researchers\nhave proposed approaches to infer a graph topology from observations of signals\non its nodes. Since the problem is ill-posed, these approaches make\nassumptions, such as smoothness of the signals on the graph, or sparsity\npriors. In this paper, we propose a characterization of the space of valid\ngraphs, in the sense that they can explain stationary signals. To simplify the\nexposition in this paper, we focus here on the case where signals were i.i.d.\nat some point back in time and were observed after diffusion on a graph. We\nshow that the set of graphs verifying this assumption has a strong connection\nwith the eigenvectors of the covariance matrix, and forms a convex set. Along\nwith a theoretical study in which these eigenvectors are assumed to be known,\nwe consider the practical case when the observations are noisy, and\nexperimentally observe how fast the set of valid graphs converges to the set\nobtained when the exact eigenvectors are known, as the number of observations\ngrows. To illustrate how this characterization can be used for graph recovery,\nwe present two methods for selecting a particular point in this set under\nchosen criteria, namely graph simplicity and sparsity. Additionally, we\nintroduce a measure to evaluate how much a graph is adapted to signals under a\nstationarity assumption. Finally, we evaluate how state-of-the-art methods\nrelate to this framework through experiments on a dataset of temperatures.\n