Spectral Graph Convolution

Graph Laplacian, ChebNet, Kipf & Welling GCN, renormalization trick, transductive limitation

A citation network has 2708 papers across 7 fields — machine learning, databases, and five others. Each paper has 1433 binary features encoding word presence. A plain MLP on those features achieves 56% accuracy at field classification. The problem: a paper's field is determined not just by its own words but by what it cites and who cites it. Machine learning papers cite other machine learning papers. The graph structure carries signal the MLP ignores.

Standard convolution is defined for regular grids — the same kernel slides over every pixel position. Graphs have no grid, no canonical node ordering, and variable neighborhood sizes. You cannot slide a fixed-size kernel over a graph. Spectral methods provided the first principled definition of graph convolution by grounding it in signal processing: the graph Laplacian L = D - A acts as the frequency operator, and filtering in spectral space multiplies signal components in eigenspace.

The problem is that eigendecomposition of the Laplacian costs O(N³) — infeasible for any real graph. ChebNet avoids explicit eigendecomposition by approximating spectral filters with Chebyshev polynomials of degree K, reducing convolution to sparse matrix multiplications that scale with edge count. Kipf & Welling (2017) simplified further to K=1 with a self-loop trick, giving one sparse matrix multiply per layer: H^{(l+1)} = σ(D̃^{-1/2} Ã D̃^{-1/2} H^{(l)} W^{(l)}). This GCN achieves 81% accuracy on the citation network versus 56% for the feature-only MLP — the graph structure accounts for 25 percentage points of accuracy.

But spectral GCNs carry a fundamental limitation that no hyperparameter can fix: the learned filter weights are defined in the eigenspace of a specific graph's Laplacian. A new graph has a different Laplacian with different eigenvectors. The model cannot generalize. This is why every production GNN system uses spatial methods.

NOT this. "GCN is just convolution applied to graphs." Image convolution is defined for regular grids with fixed-size neighborhoods — the same kernel applies at every position because the grid is uniform. Graph convolution operates on irregular, variable-size neighborhoods with no canonical ordering. The spectral formulation connected graph operations to signal processing theory, but it gave way to spatial formulations because spectral filters cannot transfer to new graphs. Spatial message-passing GNNs — which aggregate over explicit neighborhoods — generalize inductively. Spectral GCNs do not.

Key points

• Graph Laplacian: L = D - A where D is the diagonal degree matrix. Normalized: L̃ = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}. Eigendecomposition: L = UΛU^T, columns of U are eigenvectors, Λ diagonal with eigenvalues λᵢ ∈ [0, 2]. The eigenvectors form the graph Fourier basis — analogous to Fourier basis functions for regular grids, but dependent on the specific graph topology.
• Spectral filtering requires eigendecomposition first: x̂ = U^T x (graph Fourier transform), apply filter ĝ(Λ) pointwise to eigenvalues, inverse transform x = Ux̂. The full pipeline costs O(N³) for decomposition plus O(N²) to store U. At N=10,000 nodes: already expensive. At N=1M: completely infeasible. The solution is polynomial approximation — if ĝ(λ) = Σ_k θ_k λ^k, then U ĝ(Λ) U^T = Σ_k θ_k L^k, reducing convolution to sparse matrix multiplications that never require U.
• ChebNet (Defferrard et al., 2016): approximate spectral filters with Chebyshev polynomials T_k(λ̃) where λ̃ = 2λ/λ_max - 1 ∈ [-1,1]. K-th order ChebNet considers K-hop neighborhoods — wider than K=1 but still local. Chebyshev polynomials are chosen for numerical stability (min-max optimal approximation) and efficient recurrence T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x), avoiding explicit computation of eigenvectors entirely.
• Kipf & Welling GCN (2017): simplify ChebNet to K=1 (first-order), approximate λ_max ≈ 2. This collapses the two-parameter filter to a single parameter per feature. Adding self-loops (Ã = A + I) before normalization gives the propagation rule: H^{(l+1)} = σ(D̃^{-1/2} Ã D̃^{-1/2} H^{(l)} W^{(l)}). A single sparse matrix multiply per layer — tractable on large graphs. The simplification was what made GCNs widely adopted.
• Renormalization trick: adding self-loops (A → A + I = Ã) before degree normalization prevents numerical instability for degree-zero nodes and ensures each node's own features contribute to its update. Without self-loops, an isolated node receives a zero vector regardless of its features. The trick also shifts the spectral range to approximately [0,1], improving gradient flow through deep networks.
• Spectral methods cannot transfer to new graphs. The learned filter weights are defined in terms of polynomial coefficients applied to L — and L is specific to the training graph. A new graph has a different L with different eigenvectors. Even though ChebNet doesn't explicitly compute eigenvectors, its polynomial coefficients were optimized for the specific spectral profile of the training graph. Inference on a new graph produces meaningless results. PinSage at Pinterest uses spatial methods for exactly this reason.
• Over-smoothing from a spectral perspective: each GCN layer applies D̃^{-1/2} Ã D̃^{-1/2}, a low-pass filter with eigenvalues in [0,1]. With L layers, eigenvalues are raised to the L-th power — high-frequency components (small eigenvalues) vanish exponentially, leaving only the dominant eigenvector, which corresponds to the stationary distribution of the graph's random walk. After many layers, all node embeddings converge to a constant times the degree sequence, losing all discriminative power.
• Even the first-order approximation requires the full adjacency matrix for the matrix-vector product ÃH at each layer. Mini-batching requires carefully handling multi-hop neighborhoods to avoid the neighbor explosion problem — not naturally addressed by spectral formulations. This is another reason spatial methods dominate production: neighbor sampling (GraphSAGE) and subgraph sampling (GraphSAINT) require explicit neighborhood control that spectral methods don't support.

Recap

• Graph structure carries signal: citation net → MLP 56% vs GCN 81%, +25pp from structure alone.
• Spectral convolution = filter in Laplacian eigenspace: $L = D - A$, eigenvectors are the graph Fourier basis.
• Eigendecomposition is O(N³) — infeasible. ChebNet approximates filters with degree-K Chebyshev polynomials → sparse matmuls, no eigenvectors.
• Kipf & Welling GCN = K=1 ChebNet: $H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$ — one sparse matmul/layer.
• Renormalization trick: self-loops ($\tilde{A}=A+I$) before normalization fix degree-zero nodes and improve gradient flow.
• Spectral filters can't transfer: weights tied to the training graph's Laplacian → transductive only.
• Over-smoothing: low-pass filter to the L-th power collapses embeddings to the dominant eigenvector.

Check your understanding