Network Topology Inference from Spectral Templates

By Santiago Segarra, Antonio Garcia Marques, Gonzalo Mateos, Alejandro Ribeiro. IEEE Transactions on Signal and Information Processing over Networks, 2016

309 citations recorded by the source corpus.

We address the problem of identifying the structure of an undirected graph from the observation of signals defined on its nodes. Fundamentally, the unknown graph encodes direct relationships between signal elements, which we aim to recover from observable indirect relationships generated by a diffusion process on the graph. The fresh look advocated here leverages concepts from convex optimization and stationarity of graph signals, in order to identify the graph shift operator (a matrix representation of the graph) given only its eigenvectors. These spectral templates can be obtained, e.g., from the sample covariance of independent graph signals diffused on the sought network. The novel idea is to find a graph shift that, while being consistent with the provided spectral information, endows the network with certain desired properties such as sparsity. To that end, we develop efficient inference algorithms stemming from provably tight convex relaxations of natural nonconvex criteria, particularizing the results for two shifts: the adjacency matrix and the normalized Laplacian. Algorithms and theoretical recovery conditions are developed not only when the templates are perfectly known, but also when the eigenvectors are noisy or when only a subset of them are given. Numerical tests showcase the effectiveness of the proposed algorithms in recovering synthetic and real-world networks.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d05d863537c7ac403c22b29b0b550900393f942e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Cognitive Neuroscience

In Statistical and Nonlinear Physics

Citations in the corpus

Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, methodology): “For a comprehensive performance evaluation that includes comparisons with the statistical methods of Section III as well as with graph learning algorithms that rely on smoothness priors (Section V), the interested reader is referred to [53].”
Graph Learning Based on Total Variation Minimization (2018, background): “In [20, 21] the graph topology is estimated from diffused signals, and in [22] the graph is learned under the assumption that the signals are band-limited on the graph.”
Learning Graphs From Data: A Signal Representation Perspective (2018, methodology): “c In particular, F may be defined as an arbitrary (polynomial) function of a matrix related to the graph [45], [46], or a wellknown diffusion kernel, such as the heat diffusion kernel [47] (see Figure 7 for two examples).”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “has also been addressed with help of spectral graph templates [148].”
Graph Learning: A Survey (2021, background): “[60] agreed that there exists a diffusion process in the shift, and the signals can be observed.”