Graph Fourier Transform: The Spectral View of Graphs
Published:
From Classical to Graph Fourier
In classical signal processing, the Fourier transform decomposes a signal f(t) into complex exponentials:
The complex exponentials e^{iωt} are the eigenfunctions of the derivative operator (d/dt): they satisfy de^{iωt}/dt = iω e^{iωt}.
On a graph, the natural differential operator is the graph Laplacian L = D − A (see the Graph Laplacian post). Its eigenvectors play the role of complex exponentials.
The Graph Laplacian Eigenvectors
The symmetric normalised Laplacian L_sym = D^{-1/2} L D^{-1/2} has eigendecomposition:
Where:
- U = [u₁, u₂, …, uₙ] — matrix of orthonormal eigenvectors
- Λ = diag(λ₁ ≤ λ₂ ≤ … ≤ λₙ) — diagonal matrix of eigenvalues (real, non-negative)
- λ₁ = 0 always (the constant vector u₁ = 1/√N is the eigenvector for λ=0)
Eigenvalues range from 0 to 2 for the normalised Laplacian.
Graph Signals and Frequencies
A graph signal is a function f: V → ℝ, assigning a scalar value to each node. Stack these into a vector f ∈ ℝᴺ: f[v] = signal value at node v.
The smoothness of a signal is measured by the Laplacian quadratic form:
A smooth signal (nearby nodes have similar values) gives small fᵀ L f. A rough signal (wildly varying between neighbours) gives large fᵀ L f.
Eigenvectors as frequency components:
- u₁ (λ₁ = 0): perfectly constant over the graph — the DC component, lowest frequency
- u₂, u₃, … (increasing λ): progressively rougher signals — higher frequencies
- uₙ (λₙ = largest): alternates sign between connected nodes — highest frequency, like a checkerboard
The Graph Fourier Transform
The Graph Fourier Transform (GFT) of signal f is its projection onto the eigenvectors:
f̂[k] = uₖᵀ f is the “amplitude” of the k-th frequency component in the signal.
This is a change of basis: from node space (what value is at each node) to frequency space (how much of each eigenvector pattern is present in the signal).
Graph Convolution via the GFT
In classical signal processing, convolution in time equals pointwise multiplication in frequency:
Analogously, spectral graph convolution is defined as:
where ⊙ is elementwise multiplication. A spectral filter h_θ(Λ) is a diagonal matrix of learnable weights in the frequency domain:
Learning h_θ learns which frequencies to amplify and which to suppress — exactly like an equaliser on a music player.
The Problem: Computation Cost
Computing the full eigendecomposition of L costs O(N³) — prohibitive for large graphs. Storing U costs O(N²).
Solutions:
ChebNet approximates h_θ(Λ) with Chebyshev polynomials — O( E ) cost, no eigendecomposition - GCN further simplifies by using the first-order Chebyshev approximation — a single message-passing step
- Graph Transformers abandon the spectral view and use attention directly in node space
Low-Pass Filtering and GCN
Standard GCN acts as a low-pass filter — it amplifies smooth (low-frequency) signals and suppresses rough (high-frequency) ones. Averaging neighbour features is a local smoothing operation.
This is why GCN works well for homophilic graphs (smooth label signals) and poorly for heterophilic graphs (rough, high-frequency label signals). A heterophilic graph needs a high-pass filter — accentuating differences between neighbours rather than averaging them away.
Summary
| Concept | Classical (time) | Graph (node space) |
|---|---|---|
| Signal | f(t) ∈ ℝ | f ∈ ℝᴺ (one value per node) |
| Frequency basis | Complex exponentials e^{iωt} | Laplacian eigenvectors U |
| Forward transform | F̂(ω) = ∫ f e^{-iωt} dt | f̂ = Uᵀf |
| Inverse | f = ∫ F̂ e^{iωt} dω | f = Uf̂ |
| Convolution | Pointwise product in freq. domain | U (f̂ ⊙ ĝ) |
| Low-pass filter | Removes high ω | Smooths across edges |
| High-pass filter | Removes low ω | Accentuates edge differences |
The Graph Fourier Transform is the mathematical foundation of spectral GNNs. Even if you use spatial GNNs (which avoid eigendecomposition), understanding this spectral view helps diagnose why GNNs succeed or fail on specific graph types.
References
- Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The Emerging Field of Signal Processing on Graphs. IEEE Signal Processing Magazine.
- Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS 2016.
- Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2014). Spectral Networks and Locally Connected Networks on Graphs. ICLR 2014.