# Identifying the Topology of Undirected Networks from Diffused Non-stationary Graph Signals

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jan 2018.

## Built on by (most cited first, 12 of 12)

- [Graph Laplacian Learning with Exponential Family Noise](https://mlsanity.com/paper/2306.08201/) (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)
- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)
- [Kernel-based Joint Multiple Graph Learning and Clustering of Graph Signals](https://mlsanity.com/paper/2310.19005/) (2023)
- [Learning Networks from Wide-Sense Stationary Stochastic Processes](https://mlsanity.com/paper/2412.03768/) (2024)
- [Cramer-Rao Bounds for Laplacian Matrix Estimation](https://mlsanity.com/paper/2504.04576/) (2025)
- [Learning Kronecker-Structured Graphs from Smooth Signals](https://mlsanity.com/paper/2505.09822/) (2025)
- [Signed Graph Learning: Algorithms and Theory](https://mlsanity.com/paper/2507.09717/) (2025)
- [A Generative Model for Controllable Feature Heterophily in Graphs](https://mlsanity.com/paper/2509.23230/) (2025)
- [Co-Hub Node Based Multiview Graph Learning with Theoretical Guarantees](https://mlsanity.com/paper/2512.12435/) (2025)
- [Directed Graph Topology Inference via Graph Filter Identification](https://mlsanity.com/paper/2606.27455/) (2026)

## Abstract (arXiv)

We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics that depend on the structure of the unknown network. Using the so-called graph-shift operator (GSO), which is a matrix representation of the graph, we first identify the eigenvectors of the shift matrix from realizations of the diffused signals, and then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. Different from the stationary setting where the eigenvectors can be obtained directly from the covariance matrix of the observations, here we need to estimate first the unknown diffusion (graph) filter -- a polynomial in the GSO that preserves the sought eigenbasis. To carry out this initial system identification step, we exploit different sources of information on the arbitrarily-correlated input signal driving the diffusion on the graph. We first explore the simpler case where the observations, the input information, and the unknown graph filter are linearly related. We then address the case where the relation is given by a system of matrix quadratic equations, which arises in pragmatic scenarios where only the second-order statistics of the inputs are available. While such quadratic filter identification problem boils down to a non-convex fourth-order polynomial minimization, we discuss identifiability conditions, propose algorithms to approximate the solution and analyze their performance. Numerical tests illustrate the effectiveness of the proposed topology inference algorithms in recovering brain, social, financial and urban transportation networks using synthetic and real-world signals.