How do you slide a filter over a graph? The answer split the field of graph deep learning in two. Understanding the difference between the spectral and spatial domains is the key to understanding how GNNs actually work under the hood.
1The Spectral Domain: Filtering Frequencies
Spectral GNNs treat the graph as a signal processing system. They use the Graph Laplacian (L = D - A) to define a Graph Fourier Transform. By looking at the eigenvectors of the Laplacian, the model decomposes the graph's signals into 'Frequencies' — smooth signals that change slowly across connected nodes, versus high-frequency noise that varies sharply.
While mathematically elegant, pure spectral methods have severe engineering flaws. First, performing eigen-decomposition on the Laplacian takes O(N³) time, which is impossible for graphs with millions of nodes. Second, the learned filters are defined by the specific eigenvectors of that exact graph. This makes spectral models inherently Transductive: they are tied to a specific topology. If you train on Graph A, you cannot run inference on Graph B, because Graph B has entirely different eigenvectors. This limits pure spectral methods to static, fixed-graph problems.
// Pure Spectral Convolution (O(N^3))
function spectralConv(A, X, theta) {
const D = degreeMatrix(A);
const L = subtract(D, A); // Laplacian
// Expensive Eigen-decomposition
// L = U * Lambda * U^T
const { U, Lambda } = eigendecompose(L);
// Fourier Transform: U^T * X
// Filter: diag(theta)
// Inverse FT: U * result
return U @ diag(theta) @ U.T @ X;
}2The Spatial Message Domain
Spatial GNNs bypass the heavy math and operate directly on the graph's local topology. They define convolution simply as an Aggregation of neighbor information (message passing). Models like GraphSAGE and GAT are purely spatial.
Because the convolution rule ('average my neighbors', 'attend to my neighbors') does not depend on the global eigenvectors, spatial models are Inductive. They can be applied to completely new, unseen graphs instantly. Furthermore, they only require sparse matrix multiplication (O(E) time, where E is the number of edges), making them highly scalable.
So how do they relate? ChebNet and GCN form the bridge. They mathematically prove that you can approximate a spectral filter using Chebyshev polynomials, eliminating the need for eigen-decomposition. The first-order approximation of a spectral filter turns out to be exactly equivalent to averaging a node's immediate neighbors. Thus, GCN is a spatial model with a spectral soul.
// Spatial Convolution (O(E) edges)
function spatialConv(edgeList, X, W) {
const messages = new Map();
// Local aggregation (Message Passing)
// NO global Laplacian needed
for (const [u, v] of edgeList) {
messages[v] = (messages[v]||0) + X[u];
}
// Transform
return relu(messages @ W);
}