Spectral Analysis of Time-Varying Graphs

This direction is split into other directions: static topology assumption (time-varying graph inference). Its last version stays readable and citable here.

Version 1 of 1127 papers150 conceptsfrozen 2026-10-04

In classical signal processing, we analyze sounds or images by breaking them down into frequencies. Graph Signal Processing (GSP) extends this to data on irregular networks—like traffic flow on a city grid or neural activity in a brain. As established by David I Shuman, Antonio Ortega, and colleagues in The Emerging Field of Signal Processing on Graphs, the "harmonics" of a network are defined by the eigenvectors of its Laplacian matrix.

However, real-world networks are rarely frozen in time. Social ties dissolve, financial markets shift, and sensor networks lose nodes. When the underlying "grid" moves, traditional spectral tools break. This research direction focuses on extending GSP to time-varying graphs, where both the signal and the topology itself are dynamic.

The Challenge of a Moving Domain

The core difficulty in dynamic GSP is that the "coordinate system" (the spectral domain) is tied to the graph's structure. If the edges change, the Graph Fourier Transform (GFT) changes. Alejandro D. de la Concha Duarte and Argyris Kalogeratos point out in Offline detection of change-points in the mean for stationary graph signals that most spectral methods assume a fixed topology. When connectivity patterns flicker, a sudden shift in the signal might be caused by a change in the data or a change in the network itself.

To solve this, researchers like Mladen Kolar and Eric P. Xing proposed that we must assume the network evolves "smoothly." In On Time Varying Undirected Graphs, they demonstrate that even in high-dimensional settings, we can recover the evolving structure of a graph if we treat the precision matrix as a continuous, time-varying operator.

Joint Time-Vertex Representations

Rather than treating time and space (the graph) as separate entities, a powerful intuition is to merge them into a single high-dimensional structure. Andreas Loukas and Benjamin Ricaud pioneered this in A Time-Vertex Signal Processing Framework.

By defining a Joint time-vertex Fourier Transform (JFT), they allow filters to operate across both dimensions simultaneously. This works because it captures the "rhythm" of the graph. For example, in a traffic network, a "low frequency" might represent a slow, city-wide change in congestion, while a "high frequency" represents a localized accident. This framework enables denoising and inpainting by leveraging the fact that signals are often smooth across both the graph edges and the time axis.

Adaptive and Recursive Filtering

Calculating the full spectrum (eigen-decomposition) of a graph is computationally expensive. Doing it at every time step for a dynamic graph is impossible for large systems. To bypass this, researchers use polynomial approximations.

  • Chebyshev Polynomials: Nian Liu and Xavier Bresson developed WaveGC, which uses Chebyshev order decomposition to create learnable wavelets. These filters are "localized," meaning they only need to look at a node's immediate neighbors, making them naturally more robust to changes in distant parts of the graph.
  • Feedback Loops: In DFNets, Asiri Wijesinghe and Qing Wang introduced filters that behave like rational functions. These use recursive updates to track signals, allowing the model to adapt as the graph evolves without re-calculating the entire spectral basis.

Finding Spectral Invariants

A recent breakthrough in this field is the search for "invariants"—patterns in the frequency domain that remain stable even when the graph's edges shift. Xin Wang and Ziwei Zhang introduced SILD (Spectral Invariant Learning for Dynamic Graphs) in Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts.

The intuition here is that while the specific nodes and edges might change (the "variant" part), the underlying generative process of the system often stays the same (the "invariant" part). By shifting the analysis to the spectral domain, SILD identifies these stable patterns, allowing models to generalize to new network structures they haven't seen during training.

Beyond Simple Graphs

The frontier of this research is moving toward even more complex structures. Claudio Battiloro and Paolo Di Lorenzo are extending these ideas to simplicial complexes—structures that model not just pairs of nodes, but groups (like triangles). In Topological Adaptive Least Mean Squares Algorithms over Simplicial Complexes, they show how to process time-varying flow signals (like river currents or brain signals) that exist on these higher-order topologies.

By treating the evolution of the network as a fundamental part of the signal, this research direction transforms graph analysis from a static snapshot into a dynamic, multi-resolution study of how information flows through a changing world.

Papers in this version

Showing 60 of 127 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_spectral_analysis_of_time_varying_graphs_08c7ad83,
  title = {Spectral Analysis of Time-Varying Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spectral-analysis-of-time-varying-graphs/rdr_08c7ad833338455f89d7886065697fb6},
  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_spectral_analysis_of_time_varying_graphs_08c7ad83_v1,
  title = {Spectral Analysis of Time-Varying Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spectral-analysis-of-time-varying-graphs/rdr_08c7ad833338455f89d7886065697fb6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}