Adaptive Signal Processing on Graph Structures

19 concepts17 papers1 proposal

In classical signal processing, data lives on highly structured grids: time series are sequences of points on a line, and images are pixels on a 2D lattice. However, many modern datasets—ranging from functional brain activity to sensor network readings—reside on irregular structures. As Frossard et al. describe, Graph Signal Processing (GSP) extends traditional tools to these irregular domains by treating data as signals indexed by the nodes of a graph.

The core challenge is defining what it means to "filter" or "adapt" a signal when there is no natural notion of time or spatial ordering. The solution lies in the Graph Shift Operator (GSO).

The Building Blocks of Graph Filtering

In a standard digital filter, the fundamental operation is a delay (or shift). To translate this to graphs, researchers use a matrix representation—typically the adjacency or Laplacian matrix—to define how a signal at one node propagates to its neighbors. Isufi et al. explain that this GSO acts as the atomic unit for convolution on graphs.

By applying the GSO repeatedly, we can define Graph Finite Impulse Response (GFIR) filters. These are modeled as polynomials of the GSO. Because the GSO only connects immediate neighbors, a polynomial of degree $K$ ensures that the filter only uses information from a node's $K$-hop neighborhood. This localization is critical for computational efficiency and is a foundational principle for Graph Neural Networks, which Ruiz et al. show are essentially compositions of these graph filters with nonlinearities.

For more complex spectral responses, Liu et al. propose Autoregressive Moving Average (ARMA) graph filters. Unlike polynomial FIR filters, ARMA filters use rational functions of the GSO, offering greater flexibility and accuracy with fewer parameters. Zhang et al. further refine this by introducing energy-preserving shift operators that more closely mirror the properties of the classical Fourier transform.

Learning and Tracking Time-Varying Signals

Real-world network data is rarely static. Adaptive graph signal processing aims to estimate or track signals that change over time, often when only a subset of nodes can be observed.

Di Lorenzo et al. pioneered this by merging GSP with classical adaptive filtering theory. Their approach alternates between two steps:

  1. Vertex-domain update: Adjusting the estimate based on new observations at specific nodes.
  2. Frequency-domain projection: Enforcing smoothness by constraining the signal to a specific spectral bandwidth.

This framework allows for real-time tracking of signals on irregular topologies. To handle more difficult environments, such as those with impulsive noise, Kuruoglu and Yan introduced the Graph-Sign algorithm, which provides a computationally efficient and robust alternative to standard least-squares methods.

Blind Identification and Network Diffusion

Often, we observe the output of a network process without knowing the original source or the exact mechanism of spread (the filter). This is known as blind identification.

Segarra et al. framed this as a "blind deconvolution" problem on graphs. By modeling the network process as a polynomial of the GSO, the authors demonstrated that one can jointly recover both the unknown filter and a sparse input signal using convex optimization. This was later expanded by Iglesias et al. to handle multiple filters, providing a unified way to analyze how information or influence diffuses through complex networks.

Filtering on Dynamic and Stochastic Graphs

The most recent frontier involves signals on graphs that are themselves changing. Loukas et al. extended GSP to the stochastic realm, analyzing how filters behave when the underlying graph topology varies randomly over time. They proved that FIR and ARMA filters remain "well-behaved" in expectation, allowing for effective denoising even in highly unstable environments.

Furthermore, the theoretical reach of these tools is expanding. Ji and Tay developed a Hilbert space theory for GSP, moving beyond finite graphs to handle infinite-dimensional signals, such as those found in continuous-time sensor networks. This generalization ensures that the intuition of "shifting" and "filtering" remains robust regardless of whether the underlying graph is a simple social network or a complex, evolving physical system.

Key Foundational Work

Parametric estimation for Gaussian fields indexed by graphs (2013) — contributed 2 concept elements to this direction.
Blind Identification of Graph Filters (2016) — contributed 1 concept elements to this direction.
Distributed adaptive learning of signals defined over graphs (2016) — 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_graph_based_adaptive_filtering_fc6047d9,
  title = {graph-based adaptive filtering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-adaptive-filtering/rdr_fc6047d9f7b44646ba29f92262441239},
  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_graph_based_adaptive_filtering_fc6047d9_v1,
  title = {graph-based adaptive filtering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-adaptive-filtering/rdr_fc6047d9f7b44646ba29f92262441239/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake