Inferring Graph Topology from Observed Signals

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2294 papers325 conceptsfrozen 2026-10-04

In many modern datasets, we observe the "traffic" but cannot see the "roads." We might have the time-series activity of thousands of neurons, the fluctuating prices of stocks, or the spread of a virus across cities, but the underlying network of connections—the graph topology—remains hidden.

Traditional Graph Signal Processing (GSP), as outlined in the seminal tutorial by David I Shuman, Antonio Ortega, and colleagues in Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Data Domains, assumes the graph is given. However, a growing body of research focuses on the inverse problem: how to reverse-engineer the graph structure directly from the signals observed at its nodes.

The Smoothness Prior

The most intuitive way to link data to structure is through the concept of smoothness. If two nodes are connected by a strong edge, we expect their signal values to be similar. Mathematically, this is captured by the Graph Laplacian $L$. A signal $x$ is "smooth" on a graph if the quadratic form $x^T L x$ is small.

Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst formalized this in Learning Laplacian Matrix in Smooth Graph Signal Representations. They framed graph learning as an optimization problem: find the Laplacian $L$ that minimizes the smoothness penalty across all observed signals, subject to constraints that ensure $L$ represents a valid, physically meaningful graph. By assuming signals are low-frequency components of the graph, we can "solve" for the edges that best explain the data's lack of volatility.

Diffusion and Spectral Templates

Signals are rarely just static and smooth; they often evolve or diffuse across a network. Imagine a drop of ink spreading through a container of water; the final distribution of the ink is dictated by the shape of the container.

In Graph reconstruction from the observation of diffused signals, Bastien Pasdeloup, Michael Rabbat, and their team demonstrated that if we assume signals are generated by a diffusion process (like heat flow), the eigenvectors of the signal's covariance matrix will match the eigenvectors of the graph's adjacency matrix. This allows researchers to reconstruct the graph's "skeleton" (its spectral properties) even if they only see the end result of the diffusion.

Statistical Regularity and Stationarity

A more general approach treats graph signals as stochastic processes. In classical signal processing, a signal is "stationary" if its statistical properties don't change over time. Andreas Loukas and others extended this to graphs in Stationary signal processing on graphs, defining Graph Wide-Sense Stationarity (GWSS).

If a signal is stationary on a graph, its covariance matrix must commute with the Graph Laplacian. This provides a powerful structural constraint: the graph that "fits" the data is the one whose structure is consistent with the observed correlations. This perspective allows for topology discovery by finding a graph that makes the observed signals appear statistically regular.

Dynamics and Causal Inference

When data is temporal, we can look for the "fingerprints" of interaction in how one node's past affects another node's future. Donatello Materassi and Giacomo Innocenti showed in Topological identification in networks of dynamical systems that for linear dynamical systems, the exact tree structure of a network can be recovered using the coherence function, a frequency-domain measure of relationship.

For "spiky" event data, such as neural firings or social media posts, Scott Linderman and Ryan P Adams proposed using Hawkes processes in Discovering Latent Network Structure in Point Process Data. By modeling how an event at one node increases the probability of an event at another, they can infer the hidden "influence" graph that governs the system's behavior.

Sparsity and Simplicial Complexes

A recurring challenge in topology inference is that a fully connected graph can explain almost any data, but it provides no insight. To find the true underlying structure, researchers like Sundeep Prabhakar Chepuri and Geert Leus emphasize sparsity in Learning sparse graphs under smoothness prior. By penalizing the number of edges, the algorithms are forced to find the simplest network that explains the signal.

Recent work is even moving beyond simple pairwise edges. Andrei Buciulea, Antonio G. Marques, and colleagues in Learning graphs and simplicial complexes from data have begun inferring simplicial complexes—higher-order structures that capture group interactions (like three-way relationships) that simple graphs miss. This represents the frontier of the field: moving from learning "who is connected to whom" to "how groups of entities collectively influence each other."

Papers in this version

Showing 60 of 294 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 439 papers
  2. Version 1 · 2026-10-04 · 294 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_latent_topology_inference_2bac077b,
  title = {latent topology inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/latent-topology-inference/rdr_2bac077b946740a5a239c2c78988426d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_inferring_graph_topology_from_observed_s_2bac077b_v1,
  title = {Inferring Graph Topology from Observed Signals},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inferring-graph-topology-from-observed-signals/rdr_2bac077b946740a5a239c2c78988426d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}