# Network Topology Inference from Spectral Templates

arXiv: https://arxiv.org/abs/1608.03008 · HTML: https://mlsanity.com/paper/1608.03008/

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2016.

## Built on by (most cited first, 30 of 58)

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior](https://mlsanity.com/paper/2406.09513/) (2024)
- [Estimating the State of Epidemics Spreading with Graph Neural Networks](https://mlsanity.com/paper/2105.05060/) (2021)
- [Online Graph Learning under Smoothness Priors](https://mlsanity.com/paper/2103.03762/) (2021)
- [Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals](https://mlsanity.com/paper/2404.02621/) (2024)
- [Non-negative Weighted DAG Structure Learning](https://mlsanity.com/paper/2409.07880/) (2024)
- [Solving Linear Inverse Problems using Higher-Order Annealed Langevin Diffusion](https://mlsanity.com/paper/2305.05014/) (2023)
- [Joint inference of multiple graphs with hidden variables from stationary graph signals](https://mlsanity.com/paper/2110.03666/) (2021)
- [Learning Graph Structure from Convolutional Mixtures](https://mlsanity.com/paper/2205.09575/) (2022)
- [Learning Product Graphs from Spectral Templates](https://mlsanity.com/paper/2211.02893/) (2022)
- [A Primer on Temporal Graph Learning](https://mlsanity.com/paper/2401.03988/) (2024)
- [An Unbiased Symmetric Matrix Estimator for Topology Inference under Partial Observability](https://mlsanity.com/paper/2203.15500/) (2022)
- [Network Topology Inference with Sparsity and Laplacian Constraints](https://mlsanity.com/paper/2309.00960/) (2023)
- [Prior-Informed Flow Matching for Graph Reconstruction](https://mlsanity.com/paper/2601.22107/) (2026)
- [Robust Graph Learning Under Wasserstein Uncertainty](https://mlsanity.com/paper/2105.04210/) (2021)
- [Joint graph learning from Gaussian observations in the presence of hidden nodes](https://mlsanity.com/paper/2212.01816/) (2022)
- [Graph Laplacian Learning with Exponential Family Noise](https://mlsanity.com/paper/2306.08201/) (2023)
- [Learning graphs and simplicial complexes from data](https://mlsanity.com/paper/2312.10545/) (2023)
- [Multiview Graph Learning with Consensus Graph](https://mlsanity.com/paper/2401.13769/) (2024)
- [Learning Cartesian Product Graphs with Laplacian Constraints](https://mlsanity.com/paper/2402.08105/) (2024)
- [Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields](https://mlsanity.com/paper/2109.08666/) (2021)
- [Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach](https://mlsanity.com/paper/2208.04405/) (2022)
- [Online Learning Of Expanding Graphs](https://mlsanity.com/paper/2409.08660/) (2024)
- [Network Topology Inference from Smooth Signals Under Partial Observability](https://mlsanity.com/paper/2410.05707/) (2024)
- [Graphon-aided Joint Estimation of Multiple Graphs](https://mlsanity.com/paper/2202.05686/) (2022)
- [Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model](https://mlsanity.com/paper/2203.07831/) (2022)

## Abstract (arXiv)

We address the problem of identifying a graph structure 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 permeates benefits 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 social, brain, and amino-acid networks.