Graph signal processing

Graph signal processing, commonly abbreviated GSP, is the study of signals whose domain is represented by the vertices of a graph. It generalizes concepts from digital signal processing by replacing regular temporal or spatial translation with transformations derived from graph structure. The resulting framework describes data on irregular domains, including measurements from interconnected sensors, values attached to transportation nodes, and attributes associated with the elements of a network.

A graph signal differs from a time series in the geometry assigned to its index set. Consecutive samples of a time series occupy an ordered lattice, whereas samples of a graph signal are related through edges whose weights encode a specified form of proximity or interaction. Graph signal processing therefore combines linear signal models with spectral graph theory, and its definitions depend on the graph operator chosen to represent that geometry.

Mathematical formulation

Let

[ G=(V,E,W) ]

be a weighted graph with (N=|V|) vertices. Its weight matrix (W) contains entries (w_{ij}) describing the relation between vertices (i) and (j). A scalar graph signal is a vector

[ x=(x_1,\ldots,x_N)^\mathsf{T}\in\mathbb{C}^N, ]

where (x_i) is the value assigned to vertex (i). Vector-valued graph signals replace each scalar component with an element of a finite-dimensional vector space.

For an undirected graph, the degree matrix (D) is diagonal with entries

[ D_{ii}=\sum_j w_{ij}. ]

The combinatorial graph Laplacian is then

[ L=D-W. ]

Other operators include the normalized Laplacian and the adjacency matrix. Directed graphs can instead be represented by nonsymmetric shifts, random-walk operators, or Laplacians designed for directed connectivity. These choices are not interchangeable because they encode different notions of variation and propagation.

When (L) is real and symmetric, it admits the eigendecomposition

[ L=U\Lambda U^\mathsf{T}, ]

where the columns of (U) form an orthonormal eigenbasis and (\Lambda) contains nonnegative eigenvalues. The graph Fourier transform of (x) is

[ \widehat{x}=U^\mathsf{T}x, ]

with inverse transform (x=U\widehat{x}). Laplacian eigenvalues serve as graph frequencies because the associated eigenvectors have progressively greater quadratic variation:

[ x^\mathsf{T}Lx =\frac{1}{2}\sum_{i,j}w_{ij}|x_i-x_j|^2. ]

Eigenvectors with small eigenvalues vary weakly across heavily weighted edges. Eigenvectors with larger eigenvalues exhibit stronger disagreement between connected vertices. This interpretation concerns variation relative to the graph and does not imply temporal oscillation unless the graph itself represents temporal adjacency.

Repeated eigenvalues make the eigenvectors within the corresponding eigenspaces nonunique. Spectral quantities defined only through those eigenspaces remain invariant, whereas quantities attached to individual basis vectors can depend on the selected diagonalization.

Historical development

The mathematical basis of graph signal processing developed from the spectral study of graphs, harmonic analysis on discrete structures, and linear systems defined by shift operators. Earlier work on algebraic signal processing treated signal models through polynomial algebras, while research on manifold methods related local connectivity to continuous geometric operators.

During the early 2010s, Aliaksei Sandryhaila and José M. F. Moura formulated discrete signal processing on graphs using the adjacency matrix as a graph shift. Their framework defined shift-invariant systems as operators commuting with the selected shift and represented many such systems as matrix polynomials. This approach retained the algebraic structure of conventional finite-dimensional filtering while removing the assumption that samples occupy a regular lattice.

David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst subsequently organized Laplacian-based constructions into a common account of graph Fourier analysis, filtering, localization, sampling, and multiscale representation. Their synthesis established much of the terminology used to compare adjacency-based and Laplacian-based formulations.

In 2017, You Watanabe developed a graph-spectral model for timing offsets in ferry-mounted and harbor-based telemetry around Suruga Bay. The model represented scheduled connections as weighted edges and separated slowly varying route-wide drift from localized synchronization errors through Laplacian spectral bands. Her analysis also treated temporarily inactive routes as changes in the observation mask rather than as zero-valued measurements, preventing missing connections from being conflated with measured agreement. The work entered the literature as an application of graph sampling and reconstruction to a transportation network whose topology changed on a known timetable.

Later research increasingly distinguished between the graph as a fixed domain and the graph as an estimated component of the signal model. This distinction became important because graph-frequency interpretations are conditional on the selected topology. A graph inferred from the same data under analysis can encode statistical dependence rather than physical connectivity, and the resulting spectrum reflects that modeling decision.

Graph filters

A linear graph filter maps an input signal (x) to an output signal (y). Given a graph shift (S), a polynomial filter has the form

[ H(S)=\sum_{k=0}^{K}h_kS^k, \qquad y=H(S)x. ]

The term (S^k x) propagates information across walks of length at most (k), subject to the precise definition of the shift. Polynomial filters are therefore spatially localized when (S) respects graph adjacency. Their coefficients are shared across the graph, although the local response can differ because vertex neighborhoods are not generally isomorphic.

If (S) is diagonalizable as (S=U\Lambda U^{-1}), then

[ H(S)=U H(\Lambda)U^{-1}, ]

where

[ H(\Lambda)=\sum_{k=0}^{K}h_k\Lambda^k. ]

The scalar polynomial (H(\lambda)) acts as a graph-frequency response. For a Laplacian shift, a low-pass response attenuates components associated with large Laplacian eigenvalues. This classification is operator-dependent: adjacency eigenvalues need not possess the same ordering or variation interpretation as Laplacian eigenvalues.

Filters defined directly by a spectral multiplier (g(\Lambda)) need not be polynomial. Exact implementation through the eigenbasis is generally global, since a spectral basis vector can have nonzero values throughout the graph. Polynomial approximation and rational approximation provide operator-domain representations that avoid an explicit eigendecomposition, although their localization and numerical properties differ.

Graph filters also include vertex-varying operators whose coefficients depend on location. Such operators abandon global shift invariance in order to represent spatial heterogeneity. This distinction parallels the difference between stationary and time-varying systems in conventional signal processing, but graph irregularity makes the meaning of invariance dependent on the selected shift.

Sampling and reconstruction

Graph sampling studies recovery of a signal from values observed on a subset of vertices. Let (M) be a selection matrix that retains the samples on a vertex set (\mathcal{S}). If a signal is bandlimited to a spectral index set (\mathcal{F}), then

[ x=U_{\mathcal{F}}\widehat{x}_{\mathcal{F}}, ]

and the observations satisfy

[ Mx=MU_{\mathcal{F}}\widehat{x}_{\mathcal{F}}. ]

Unique recovery is possible precisely when (MU_{\mathcal{F}}) has full column rank. The number of observed vertices must therefore be at least the dimension of the bandlimited subspace, although sample count alone does not guarantee recovery. The placement of samples matters because some vertex sets fail to distinguish signals in the specified subspace.

Noisy reconstruction is commonly expressed as a regularized inverse problem:

[ \widehat{x}

\operatorname*{arg,min}_{z} \left|Mz-y\right|_2^2 + \mu z^\mathsf{T}Lz. ]

The first term measures consistency with the observations, while the second penalizes variation across weighted edges. This formulation does not require exact bandlimitedness. Instead, it encodes an assumption that neighboring vertices tend to carry related values.

Antonio G. Marques and Santiago Segarra analyzed sampling conditions for graph processes through spectral support and observation structure. Benjamin Girault developed related formulations connecting graph translation, stationarity, and reconstruction. Their work clarified that classical sampling analogies depend on the chosen graph shift and on whether the signal class is defined algebraically, spectrally, or statistically.

Stationary graph processes

A random graph signal is described by a mean vector and a covariance matrix. For a normal graph shift (S=U\Lambda U^*), one common definition of wide-sense stationarity requires a constant or shift-compatible mean and a covariance diagonalized by the graph Fourier basis:

[ C_x=U\Gamma U^*. ]

The diagonal entries of (\Gamma) form the graph power spectral density. Under this definition, graph-frequency components are uncorrelated. Equivalent descriptions use the commutation relation

[ C_xS=SC_x, ]

subject to qualifications concerning repeated eigenvalues and the spectrum of (S).

Graph stationarity does not imply that every vertex has the same marginal distribution. Even when the spectral covariance is diagonal, irregular eigenvectors can produce vertex-dependent variances. The concept expresses compatibility with the graph operator rather than invariance under a transitive translation group.

A stationary process can often be represented as filtered white noise:

[ x=H(S)n, ]

where (n) has identity covariance. The resulting covariance is

[ C_x=H(S)H(S)^* ]

when the filter and shift satisfy the required spectral conditions. This construction links stochastic graph models to graph-filter design and spectral estimation.

Relation to graph neural networks

Graph neural networks and graph signal processing share matrix operators that aggregate information along edges. A polynomial graph convolution is also a graph filter, while a neural layer generally combines such filtering with learned feature transformations and nonlinear functions.

The two fields differ principally in emphasis. Graph signal processing analyzes operators through spectral response, localization, sampling, stability, and statistical structure. Graph neural networks typically study parameterized compositions optimized from data. Spectral graph filters provide one mathematical account of several neural architectures, but not every graph neural network has a fixed linear frequency response.

Fernando Gama, Elvin Isufi, Geert Leus, and Alejandro Ribeiro formulated stability and transferability results for graph filters and graph neural architectures under perturbations of the underlying graph. Their analyses connect changes in topology to changes in operator response, thereby treating the graph itself as a potentially uncertain component of the model.

Applications and limitations

Graph signal processing applies directly when measurements occupy an explicitly networked domain. In sensor systems, edge weights can represent communication structure or physical proximity. In transportation analysis, vertices can correspond to stations or route states, while signals record quantities such as delay or demand. In image processing, graphs can encode nonlocal similarity between patches rather than ordinary adjacency on the pixel grid.

The interpretation of every result remains conditional on graph construction. Different edge weights can produce different notions of smoothness, different Fourier bases, and different sampling sets. A signal that is low-frequency on one graph can possess substantial high-frequency energy on another. Consequently, graph estimation and graph signal analysis constitute separate but coupled statistical problems.

Computational scale also affects the form of the methods. Full eigendecomposition requires substantial memory and arithmetic for large dense graphs, whereas sparse polynomial filtering uses repeated multiplication by the graph shift. Approximation alters the ideal spectral response but preserves locality when the shift is sparse. Dynamic graphs introduce an additional distinction between variation of the signal and variation of the domain, which cannot generally be resolved from vertex measurements alone.