Spectral Graph Convolutions
What you'll learn: How to perform convolutions on graph-structured data by working in the frequency domain using graph spectral theory.
The Core Idea
Traditional CNNs convolve filters across image grids, but graphs have no regular grid structure. Spectral graph convolutions solve this by transforming graph signals into the "frequency domain" using the graph Laplacian's eigenvectors, applying filters there, and transforming back.
Think of it like audio processing: instead of manipulating sound waves directly in time, you work in the frequency domain (via Fourier transform), apply filters, then convert back. Here, the graph Fourier transform uses eigenvectors of the graph Laplacian as the basis.
How It Works
Given node features x and the graph Laplacian L:
- Decompose L: Compute eigenvalues Λ and eigenvectors U where L = UΛU^T
- Transform to spectral domain: Project features using U^T x
- Apply spectral filter: Multiply by a learnable diagonal filter matrix g(Λ)
- Transform back: Apply U to return to graph domain
The convolution becomes: y = U g(Λ) U^T x
The learnable parameters are in g(Λ), which defines how each frequency component is weighted—smooth filters emphasize low frequencies (global patterns), while sharp filters capture high frequencies (local variations).
Limitations
This approach is elegant but computationally expensive: eigen-decomposition costs O(n³) for n nodes, and the filters aren't spatially localized. This motivated later spatial approaches (like message passing) that aggregate neighborhoods directly without spectral decomposition.
Key Takeaway: Spectral graph convolutions generalize CNNs to graphs by filtering node features in the graph's frequency domain, defined by the eigenbasis of the Laplacian—though computationally costly, they laid theoretical groundwork for modern GNNs.