Graph Signal Processing

Signals living on nodes get a Fourier transform from the graph itself: the Laplacian eigenvectors are the frequencies, and filtering is reweighting them.

A 3, 0, minus 3 signal on a three-node path projects entirely onto the middle Laplacian eigenvector with coefficient 4.24

Why Does This Exist?

Sensor readings on a road network, labels on a citation graph, features on a molecule: values attached to nodes, where neighbours should usually (but not always) agree. Classical Fourier analysis gives frequencies, filtering, and sampling for line and grid signals. Graph signal processing rebuilds that toolkit when the domain is a graph: the Laplacian eigenvectors become the Fourier basis, eigenvalues become frequencies, and a graph convolution becomes pointwise reweighting in that basis. Message-passing networks are low-pass filters in exactly this sense, which is why they smooth and why they fail on disassortative graphs. The matrix underneath is the Laplacian, and the classical analogue is the Fourier-convolution pair.

The one idea you need first

For symmetric $L = U \Lambda U^\top$ , the graph Fourier transform of $x$ is $\hat{x} = U^\top x$ : coefficients on eigenvector-modes ordered by variation $\lambda$ . Filtering multiplies each coefficient by a gain $g(\lambda)$ and transforms back: $y = U g(\Lambda) U^\top x$ .

Think of It Like This

Choir risers, from hum to hiss

A choir stands on risers: the lowest mode is everyone singing one note (zero variation across neighbours), the middle mode is left side versus right side, the top mode is every singer alternating with their neighbour (maximum variation). Any song the choir sings decomposes into how much hum, how much sectional contrast, and how much hiss it contains.

A low-pass filter turns down the hiss (denoise by neighbour agreement). A high-pass filter removes the hum (keep only local contrast). The catch: the risers are the graph, so a different seating gives different modes. There is no universal equalizer setting across graphs.

Where the analogy stops: real filters are polynomials in $L$ or the adjacency, applied without ever computing eigenvectors, because full decompositions do not scale.

How It Actually Works

Order Laplacian eigenpairs $0 = \lambda_1 \le \cdots \le \lambda_n$ with modes $u_1, \ldots, u_n$ . Mode $u_k$ varies across edges in proportion to $\lambda_k$ : $u_1$ is constant, the top mode alternates as fast as the graph allows.

Filtering. Choose gains $g(\lambda)$ : low-pass keeps small $\lambda$ (smooth, denoise), high-pass keeps large $\lambda$ (anomalies, boundaries). A one-hop neighbour average is $I - \alpha L$ : gain $1 - \alpha\lambda$ , a gentle low-pass. Stacking $k$ such layers without nonlinearity is a polynomial filter of degree $k$ , reaching $k$ hops.

Sampling and smoothness. Smooth signals (energy concentrated at small $\lambda$ ) are recoverable from few labels, which is the assumption behind label propagation. The smoothness price is $x^\top Lx = \sum_\lambda \lambda \hat{x}_\lambda^2$ .

Worked example

Path $1 - 2 - 3$ with Laplacian eigenvalues $0, 1, 3$ and modes $u_0 = (1,1,1)/\sqrt{3}$ , $u_1 = (1,0,-1)/\sqrt{2}$ , $u_2 = (1,-2,1)/\sqrt{6}$ .

Signal $x = (3, 0, -3)$ . Coefficients:

$\hat{x}_0 = (3 + 0 - 3)/\sqrt{3} = 0$ : no constant part, since the entries sum to zero.
$\hat{x}_1 = (3(1) + 0(0) + (-3)(-1))/\sqrt{2} = 6/\sqrt{2} \approx 4.24$ : everything lives here.
$\hat{x}_2 = (3(1) + 0(-2) + (-3)(1))/\sqrt{6} = 0$ : no alternating part.

Energy check: $\|x\|^2 = 18$ and $4.24^2 \approx 18$ . A low-pass keeping $\lambda \le 1$ preserves the whole signal; a filter killing $\lambda = 1$ deletes it entirely. Smoothness: $x^\top Lx = 1 \times 18 = 18$ , all at mid-frequency.

Watch Out For

Assuming low-frequency means signal and high means noise

On homophilic graphs (friends agree, citations share topics) smoothing helps. On heterophilic ones (fraudsters link honest users, proteins bind unlike partners) the label lives at high frequency, and a low-pass filter deletes the answer while reporting high confidence.

Symptom: GNN accuracy below an MLP on the same features, worst on graphs where neighbours differ. Fix: use high-pass or band-pass filters, signed propagation, or models that separate ego from neighbour embeddings instead of averaging them.

Carrying a filter across graphs

Fourier modes belong to one graph: eigenvectors of $L_1$ are not eigenvectors of $L_2$ . A filter learned as per-mode gains does not transfer, and even polynomial coefficients assume similar spectra.

Symptom: a spectral model trained on one network collapses on another with different density. Fix: learn polynomial or spatial filters (shared local rules) rather than per-mode gains, and check spectral similarity before transferring anything spectral.

The Quick Version

Graph Fourier modes are Laplacian eigenvectors ordered by eigenvalue-as-frequency.
Filtering reweights mode coefficients: low-pass smooths, high-pass keeps contrast.
The $(3, 0, -3)$ path signal is pure $\lambda = 1$ mode with coefficient 4.24.
Neighbour averaging is a gentle low-pass; stacking builds polynomial filters.
Smoothness $x^\top Lx$ concentrates recoverable signals at low frequencies.
Heterophily breaks the smooth assumption, and modes do not transfer across graphs.