Joint Inference of Graph Topology and Signal Representations

This direction is split into other directions: joint topology and signal estimation. Its last version stays readable and citable here.

Version 1 of 161 papers92 conceptsfrozen 2026-10-04

In classical signal processing, we often know the domain our data lives on—a sequence of audio samples in time or a grid of pixels in space. But in modern datasets, the "domain" is often an irregular network: the functional connectivity of the brain, the physical links of a power grid, or the social ties in a community.

Graph Signal Processing (GSP) was developed to handle this, but it faces a fundamental "chicken-and-egg" problem. To denoise or interpolate a signal, you need to know the underlying graph structure. However, to infer that graph structure from observations, you usually need clean, complete signal data. As Amirhossein Javaheri and colleagues note in Joint Signal Recovery and Graph Learning from Incomplete Time-Series, these two tasks are traditionally solved in isolation, leading to error propagation when either the data or the network map is imperfect.

The research direction of Joint Topology and Signal Inference breaks this cycle by treating the graph and the signal as coupled variables in a single optimization framework.

The Smoothness Bridge

The core intuition behind this joint approach is the smoothness prior. If a signal is "smooth" on a graph, it means that nodes connected by an edge are likely to have similar values.

Xiaowen Dong and Pascal Frossard pioneered this by showing that we can learn a Laplacian matrix—the mathematical representation of a graph—by assuming the observed data is a noisy version of a smooth signal. In Learning Laplacian Matrix in Smooth Graph Signal Representations, they demonstrate that by balancing data fidelity (how well the signal matches observations) with signal smoothness and graph sparsity, we can recover hidden relationships in everything from weather patterns to political voting blocks.

This smoothness acts as a bridge: the signal provides the evidence for the edges, and the edges provide the constraints to clean the signal.

Breaking the Cycle with Alternating Minimization

How do you solve for two unknown things at once? The most common mechanism across this literature is alternating minimization.

The algorithm follows a simple, iterative rhythm:

  1. Fix the Graph, Update the Signal: Given the current estimate of the network, denoise or interpolate the signal (often using Tikhonov regularization).
  2. Fix the Signal, Update the Graph: Given the "cleaned" signal, refine the edge weights to maximize smoothness and sparsity.

Sijia Liu shows in Learning sparse graphs under smoothness prior that this process ensures the learned graph remains consistent with the recovered signal. This "bootstrapping" effect is powerful; as Rui Liu and Ngai-Man Cheung demonstrate in Joint Estimation of Low-Rank Components and Connectivity Graph in High-Dimensional Graph Signals, the system can recover high-fidelity connectivity patterns even when starting from a highly distorted initial graph.

Robustness to Real-World Messiness

In the real world, graphs are rarely "ground truth." Sensors fail, and connections are often misidentified. Samuel Rey and Antonio G. Marques have focused on making GSP robust to these perturbations.

In Robust Graph Filter Identification and Graph Denoising from Signal Observations, they argue that treating the graph as a fixed input is a liability. By treating the graph structure as an optimization variable, the signal observations themselves act as a mechanism for graph denoising. If the signal doesn't "flow" correctly across a purported edge, the joint optimization can weaken or remove that edge, effectively correcting the network map as it processes the data.

Expanding the Domain: Points, Molecules, and Complexes

This joint inference framework is not limited to simple social or sensor networks. It has been adapted to solve complex geometric and structural problems:

By moving away from the assumption of a "fixed graph," this research direction allows us to process data in a way that is fundamentally aware of—and capable of correcting—the structure of the world it inhabits.

Papers in this version

Showing 60 of 61 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_joint_inference_of_graph_topology_and_si_bd4b8b94,
  title = {Joint Inference of Graph Topology and Signal Representations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/joint-inference-of-graph-topology-and-signal-representations/rdr_bd4b8b942c9446089b29e2e1263a25aa},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_joint_inference_of_graph_topology_and_si_bd4b8b94_v1,
  title = {Joint Inference of Graph Topology and Signal Representations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/joint-inference-of-graph-topology-and-signal-representations/rdr_bd4b8b942c9446089b29e2e1263a25aa/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}