Inference and Filtering over Dynamic Graph Topologies

23 concepts27 papers

In classical Graph Signal Processing (GSP), we typically treat the underlying network as a frozen, immutable structure. Imagine a highway system where the roads are permanently fixed, and the only thing changing is the density of the traffic moving over them. Under this static topology assumption, graph filters use a fixed algebraic representation of the network—such as the adjacency or Laplacian matrix—to smooth, denoise, or predict signals across nodes.

But real-world networks are rarely static. In financial markets, asset correlations shift in an instant during a crash. In biological systems, the electrical pathways of a heart fluctuate during arrhythmia. In social networks, new users and friendships appear continuously. When the "highway system" itself is constantly shifting, traditional GSP models break down. As Wei Yang et al. point out in Structured Spectral Reasoning for Frequency-Adaptive Multimodal Recommendation, forcing non-stationary, time-varying behaviors into a rigid, static graph basis pollutes information propagation and misleads predictive models.

To solve this, a major research direction has emerged that relaxes the static topology constraint. By merging GSP with adaptive filtering, online optimization, and time-vertex representations, researchers have developed frameworks capable of tracking and filtering signals over dynamic, evolving graphs.

Tracking the Moving Map via Adaptive Filtering

If a network's topology changes over time, we cannot rely on offline, batch-oriented graph learning algorithms. Waiting to collect a massive, stationary time-series dataset to infer a single graph is impractical when the network structure changes from one second to the next. Instead, we need methods that update their understanding of the graph topology on the fly as new data streams in.

The breakthrough intuition here is to adapt classical adaptive filtering theory (like Least Mean Squares) to the graph domain. Paolo Di Lorenzo et al. pioneered this approach in Least Mean Squares Estimation of Graph Signals and Distributed Adaptive Learning of Graph Signals. They demonstrated that an autonomous system can simultaneously track changes in both the signal values and the underlying edge connections using a continuous prediction-correction loop.

  Streaming Data ---> [ Predict Topology ] ---> [ Compare with Signal ]
                             ^                           |
                             |                           v
                      [ Update Weights ] <--- [ Calculate Error ]

In this framework, the algorithm uses the current estimate of the graph to predict the next signal state. When the actual signal arrives, the discrepancy (prediction error) is used to adjust both the estimated signal and the graph weights.

To make this tracking mathematically tractable in real-time, the authors often model the relationships using Time-Varying Structural Equation Models (SEMs). For instance, Alberto Natali et al. showed in Online Graph Learning From Time-Varying Structural Equation Models that by combining recursive covariance updates with a prediction-correction optimization strategy, a system can track changing topologies up to three orders of magnitude faster than traditional batch methods. This makes it possible to map highly volatile, non-stationary physical phenomena, such as the chaotic electrical waves in biological tissues during cardiac fibrillation, as demonstrated by Alexander Jenkins et al. in Online Graph Topology Learning via Time-Vertex Adaptive Filters: From Theory to Cardiac Fibrillation.

Spatiotemporal Unification: The Time-Vertex Perspective

A second core mechanism for handling dynamic networks is to stop viewing time and graph space as separate dimensions. Instead, we can mathematically unify them into a single time-vertex graph.

In this view, every observation of a node at a specific timestamp is treated as a unique vertex in a larger, macro-graph. Edges exist not only between different nodes at the same time step (spatial connections) but also between the same node across consecutive time steps (temporal connections).

Daniel Romero et al. formalize this in Kernel-Based Reconstruction of Space-Time Functions on Dynamic Graphs and Inference of Spatio-Temporal Functions Over Graphs via Multikernel Kriged Kalman Filtering. By treating the temporal dimension as an extension of the graph's spatial structure, they introduce deterministic Kernel Kalman Filters (KKF). This allows the underlying graph edges to shift at every single observation interval while maintaining a coherent global estimation framework, which is highly effective when data is sparse or heavily corrupted by noise.

This time-vertex perspective also elegantly handles networks that are not just shifting their weights, but actively growing. In applications like social networks or disease tracking, new nodes and edges join the system sequentially. Bishwadeep Das et al. addressed this in Online Filtering over Expanding Graphs and Online Graph Filtering Over Expanding Graphs, proving that online gradient descent can adaptively update graph filters to accommodate expanding dimensions without requiring expensive offline re-training.

Why It Works: Balancing Spatial and Temporal Smoothness

Inferring a graph topology from data is inherently an underdetermined problem—there are far more possible edge configurations than there are data points. Why, then, do these time-varying frameworks work so reliably?

The secret lies in leveraging two simultaneous mathematical priors: spatial smoothness and temporal smoothness.

  1. Spatial Smoothness: As reviewed by Xiaowen Dong et al. in Learning Graphs from Data: A Signal Representation Perspective, graph learning assumes that the observed signals are smoothed by the network topology. This means that if two nodes are strongly connected, their signal values should be highly correlated or similar.
  2. Temporal Smoothness (Bounded Volatility): While the network is dynamic, it does not completely randomize its structure from one millisecond to the next. The topology at time $t$ is highly dependent on the topology at time $t-1$.

By optimizing a joint objective function that penalizes both spatial roughness (signals mismatching the graph structure) and temporal jumps (the graph changing too drastically between steps), these algorithms drastically narrow down the search space.

Even when the network structure experiences random, intermittent link failures, the system remains stable. Andreas Loukas et al. proved in Filtering Random Graph Processes Over Random Time-Varying Graphs that time-varying Finite Impulse Response (FIR) and Autoregressive Moving Average (ARMA) filters are "well-behaved" in expectation. Because the underlying stochastic processes are bounded by these dual smoothness constraints, the filters can successfully denoise signals and track structural reconfigurations without succumbing to signal volatility.

Key Foundational Work

Least Mean Squares Estimation of Graph Signals (2016) — contributed 1 concept elements to this direction.
LMS estimation of signals defined over graphs (2016) — contributed 1 concept elements to this direction.
Topological identification in networks of dynamical systems (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_static_topology_assumption_time_varying__4778573e,
  title = {static topology assumption (time-varying graph inference)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/static-topology-assumption-time-varying-graph-inference/rdr_4778573eaf9a468ba40c366c2debb1e5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_static_topology_assumption_time_varying__4778573e_v1,
  title = {static topology assumption (time-varying graph inference)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/static-topology-assumption-time-varying-graph-inference/rdr_4778573eaf9a468ba40c366c2debb1e5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake