Spectral vs Spatial Graph Convolutions

A convolution on an image works because pixels sit on a fixed grid: "the 3x3 neighborhood around this pixel" means the same thing everywhere. A graph has no grid — a node might have 3 neighbors or 300, with no natural "up, down, left, right." So what does it mean to "convolve" on a graph? Two different answers were developed, leading to two very different kinds of graph neural network.

The analogy: filtering a song versus averaging with your neighbors

Think of two ways to smooth out noise. One: transform the whole signal into frequencies (bass, mid, treble), turn down the frequencies that look like noise, and transform back — filtering in the frequency domain. The other: at every point, just average the value with its immediate neighbors — a moving average, no transform needed. Both smooth the signal; the first needs a global transform of the entire signal, the second only looks at local neighborhoods.

Spectral graph convolutions are the first kind: transform the graph signal (the node features) into the graph's "frequency" basis, multiply by a filter, and transform back. Spatial graph convolutions are the second kind: at each node, just aggregate values from its immediate neighbors, directly in node-space, no transform required.

The graph Laplacian gives you the frequencies

A graph's "frequencies" come from the graph Laplacian $L = D - A$, where $D$ is the diagonal degree matrix (how many neighbors each node has) and $A$ is the adjacency matrix (who connects to whom). $L$ has an eigendecomposition $L = U \Lambda U^T$: the eigenvectors $U$ are the graph's analogue of sine and cosine waves, and the eigenvalues $\Lambda$ are their "frequencies" — low eigenvalues mean smoothly varying patterns across the graph, high eigenvalues mean rapidly oscillating ones between neighbors.

A spectral convolution filters a signal $x$ (a value at every node) by:

$$x_{\text{filtered}} = U \, g_\theta(\Lambda) \, U^T x$$

In words: project the node values onto the graph's frequency basis ($U^T x$), scale each frequency by a learnable filter $g_\theta$, then project back ($U$). The catch: computing $U$ costs roughly $O(N^3)$ — for a graph of a few hundred thousand nodes that is infeasible, and the filter is tied to this exact graph's eigenvectors, so it cannot generalize to a different graph.

Worked example 1: a tiny 4-node graph, both ways

Take a 4-node path graph $1 - 2 - 3 - 4$ with node values $x = [10, 20, 30, 40]$. Degrees are $[1, 2, 2, 1]$, so:

$$L = \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix}$$

A full spectral filter would eigendecompose this $4\times4$ matrix — doable by hand here, but already tedious, and this is the smallest possible nontrivial graph. Now the spatial route: a simple mean-aggregation convolution updates each node as the average of itself and its neighbors. For node 2 (neighbors 1 and 3): $x_2' = \tfrac{1}{3}(20 + 10 + 30) = 20$. For node 3 (neighbors 2 and 4): $x_3' = \tfrac{1}{3}(30 + 20 + 40) = 30$. For node 1 (neighbor 2 only): $x_1' = \tfrac{1}{2}(10+20) = 15$. For node 4: $x_4' = \tfrac{1}{2}(40+30) = 35$. No eigendecomposition, no global matrix — just local averages, computed independently at every node.

Worked example 2: why spatial scales and spectral doesn't

Suppose the graph instead has 1 million nodes (roughly the size of a large ownership or trading-relationship network). The spectral route needs $U$, an eigendecomposition of a $1{,}000{,}000 \times 1{,}000{,}000$ matrix — computationally out of reach, and it would have to be recomputed after adding even one new node. The spatial route needs only each node's handful of neighbors: node 500,000 with 8 neighbors does the same 8-neighbor average regardless of graph size, and the same learned weights transfer unchanged to a completely different graph. This is why every practical GNN in production — GCN, GraphSAGE, GAT — uses a spatial formulation, not a true global spectral one.

Drag the matrix entries above and watch the eigenvectors rotate: that is the same idea a full spectral graph convolution needs, except instead of a $2\times 2$ matrix it needs the full $N \times N$ graph Laplacian — the reason this approach breaks down at scale.

What this means in practice

The original GCN paper is often called "spectral," but the version everyone trains is a first-order local approximation — derived from spectral theory, computed spatially, using only 1-hop neighbor sums. Nearly every modern GNN skips the spectral derivation entirely. Spectral methods still matter for graph signal-processing theory and for graphs fixed across training and inference, but anything needing to generalize across graphs or scale past a few thousand nodes uses spatial.

Practice

1. For the 4-node path graph above, compute one more spatial aggregation step starting from the updated values $[15, 20, 30, 35]$.
2. Explain why the graph Laplacian's eigenvectors are described as the graph's analogue of sine and cosine waves.
3. A trading desk wants a GNN that can be retrained daily as new tickers enter and leave a correlation graph. Which approach, spectral or spatial, fits that requirement, and why?