Spectral Graph Convolutions

On an image, convolution is defined by sliding a filter across a grid where every pixel has the same neighbourhood shape. A graph has no grid, no consistent neighbourhood size and no notion of "shift by one". What it does have is a Laplacian matrix, and the Laplacian's eigenvectors play the role that sines and cosines play for signals on a line. Convolution can be defined there, in the frequency domain, and the most widely used GNN layer turns out to be a heavily simplified version of that definition.

The spatial reading of the same layer is covered in graph neural networks and message passing. The spectral view explains why it behaves as a smoother, which is the root of over-smoothing.

The graph Fourier transform

For an undirected graph with adjacency matrix \(A\) and diagonal degree matrix \(D\), the normalised Laplacian is

where \(U\) holds orthonormal eigenvectors and \(\Lambda\) the eigenvalues, which lie in \([0, 2]\). A signal \(x \in \mathbb{R}^N\) assigns one number to each node. Its graph Fourier transform is \(\hat{x} = U^\top x\). Eigenvectors with small eigenvalues vary slowly across edges (low frequency); those with large eigenvalues flip sign between neighbours (high frequency).

A spectral filter is a function \(g_\theta\) applied to the eigenvalues:

Transform, rescale each frequency, transform back. Bruna and colleagues made \(g_\theta(\Lambda)\) a free diagonal of learnable values (Bruna et al., 2014, Spectral Networks and Locally Connected Networks on Graphs, ICLR, arXiv:1312.6203). It works and is impractical: the eigendecomposition costs \(O(N^3)\), each filter has \(N\) parameters, multiplying by \(U\) costs \(O(N^2)\), the filter is not spatially localised, and because \(U\) belongs to one specific graph, the learned filter means nothing on another.

ChebNet: polynomials make it local

The fix is to restrict \(g_\theta\) to a polynomial of the eigenvalues. A degree-\(K\) polynomial in \(L\) touches only nodes within \(K\) hops, because \(L^k\) has nonzeros only between nodes at most \(k\) edges apart. Defferrard, Bresson and Vandergheynst used Chebyshev polynomials for numerical stability (Defferrard et al., 2016, Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering, NeurIPS, arXiv:1606.09375):

with \(T_0(y) = 1\), \(T_1(y) = y\) and \(T_k(y) = 2y\,T_{k-1}(y) - T_{k-2}(y)\). Rescaling maps eigenvalues into \([-1, 1]\), where Chebyshev polynomials are well behaved. The recurrence means \(T_k(\tilde{L})x\) is computed by repeated sparse matrix-vector products, so the cost is \(O(K|E|)\) and no eigendecomposition is ever performed. Each filter now has \(K\) parameters instead of \(N\).

GCN as a first-order approximation

Kipf and Welling took \(K = 2\), a first-order polynomial, and approximated \(\lambda_{\max} \approx 2\) (Kipf & Welling, 2017, Semi-Supervised Classification with Graph Convolutional Networks, ICLR, arXiv:1609.02907). Then \(\tilde{L} = L - I = -D^{-1/2}AD^{-1/2}\), and

Tying the parameters with \(\theta = \theta_0 = -\theta_1\) gives \(\theta\,(I + D^{-1/2}AD^{-1/2})\,x\). The operator \(I + D^{-1/2}AD^{-1/2}\) has eigenvalues in \([0, 2]\), so stacking layers can amplify some components geometrically. The renormalisation trick adds self-loops first, \(\tilde{A} = A + I\) with degrees \(\tilde{D}\), producing the familiar layer

A two-node graph makes the difference concrete. With \(A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) and \(D = I\), the operator \(I + A\) has eigenvalues 2 (for the constant vector) and 0 (for the alternating vector). Ten stacked layers scale the constant component by \(2^{10} = 1024\). After renormalisation, \(\tilde{A}\) is all ones and \(\tilde{D} = 2I\), so the operator is a matrix of 0.5s with eigenvalues 1 and 0. The constant signal passes unchanged and the alternating signal is removed. This is a low-pass filter, and nothing else.

Where the literature disagrees

In Kipf and Welling's experiments the crude first-order model beat higher-order ChebNet, which seemed to say that expressive spectral filters were unnecessary. Wu and colleagues pushed further, removing nonlinearities entirely: SGC is a fixed low-pass filter followed by a linear classifier and matches GCN on many tasks (Wu et al., 2019, Simplifying Graph Convolutional Networks, ICML, arXiv:1902.07153).

He, Wei and Wen contested the interpretation. They argue ChebNet underperformed because its learned coefficients were not constrained to approximate valid filter functions, which led to overfitting, and that constraining them through Chebyshev interpolation, as ChebNetII does, recovers strong results (He et al., 2022, Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited, NeurIPS, arXiv:2202.03580). The question of whether flexible filters matter is therefore not closed, and the answer depends heavily on whether the task needs frequencies other than low ones.

When it breaks

Heterophily needs high frequencies. On graphs where neighbours tend to have different labels, the informative signal is the high-frequency part that GCN's filter deletes. A fixed low-pass layer is structurally wrong there, and learnable or high-pass filters are required.

Spectral bases do not transfer. A filter defined by free coefficients on one graph's eigenvectors has no meaning on another graph. Polynomial filters escape this because they are functions of \(L\), not of \(U\), which is a major reason the polynomial versions won.

Directed graphs break the construction. The derivation assumes a symmetric Laplacian with real eigenvalues and orthogonal eigenvectors. Directed adjacency gives neither, and the usual workaround of symmetrising the graph discards direction.

The \(\lambda_{\max} \approx 2\) approximation is loose. On many graphs the largest eigenvalue is well below 2, so the rescaled spectrum does not fill \([-1, 1]\), which is harmless for GCN but distorts higher-order Chebyshev filters unless \(\lambda_{\max}\) is estimated.