Vocabulary.
Relabel the nodes and you get a completely different matrix describing an identical object.
\[A \;\longmapsto\; P A P^{\top}, \qquad X \;\longmapsto\; P X\]
where \(P\) is a permutation matrix. There are \(n!\) such relabelings.
Two words we will use constantly:
Key idea: thirty years of GNN research is one sustained attempt to answer “how do we build a network whose architecture respects the symmetry of the domain?”: and later, “what if the domain also has geometric symmetries like rotations and translations in molecules?”
| Term | Meaning |
|---|---|
| Adjacency matrix \(A\) | \(n \times n\) table of which nodes connect |
| Laplacian \(L=D-A\) | discrete second derivative; measures roughness |
| Aggregation | permutation-invariant combination of neighbor messages |
| Invariant / equivariant | output unchanged / output transforms with the input |
| Transductive / inductive | answers only for seen items / a general reusable function |
| Multiset | a set that records how many times each element appears |
| Receptive field | region of input an output depends on; \(L\) hops after \(L\) layers |
| Oversmoothing | representations converge to identical values with depth |
| Oversquashing | exponentially many nodes squeezed into one fixed-size vector |
| WL test | color-refinement heuristic; the expressivity ceiling for message passing |
| Body order | how many atoms one interaction term involves at once |
| Readout / pooling | collapsing node representations into one graph-level vector |
The Laplacian measures how much a function at a point differs from the average nearby: a discrete second derivative.
\[L = D - A, \qquad D = \mathrm{diag}(d_1, \ldots, d_n)\]
Applied to a signal \(x\) on the nodes:
\[(Lx)_i = d_i x_i - \sum_{j \in \mathcal{N}(i)} x_j = \sum_{j \in \mathcal{N}(i)} (x_i - x_j)\]
Normalized version (keeps eigenvalues in a small range, which matters for stacking layers):
\[L_{\text{sym}} = I - D^{-1/2} A D^{-1/2}\]
Spectral graph neural networks transform a graph into a spectrum of “frequencies”, measuring how features vary across nodes, so the model can amplify key structural patterns and then project the filtered result back onto the nodes.
Bruna et al. (2014) applied the convolution theorem to graphs: spatial convolution equals pointwise frequency multiplication. By diagonalizing the Graph Laplacian (\(L=U \Lambda U^{\top}\)), spectral convolution is defined as:
\[ x *_G g = U\, g_\theta(\Lambda)\, U^{\top} x \]
Spectral graph convolution mathematically mirrors lattice vibrations in solid-state physics.
ChebNet’s fix (2016): you never need the eigenvectors. Approximate \(g_\theta\) by a polynomial:
\[g_\theta(L) \approx \sum_{k=0}^{K} \theta_k T_k(\tilde{L})\]
ChebNet limitations:
Simplify ChebNet by setting \(K = 1\) and simplify. Assume \(\lambda_{\max} \approx 2\), tie the two parameters, and add self-loops:
\[H^{(l+1)} = \sigma\!\left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)} \right), \qquad \tilde{A} = A + I\]
Why GCN won and ChebNet didn’t.
Imagine a simple line graph with three nodes, where the feature is a single number. At each layer, a node updates its value by averaging its own value with its direct neighbors.
Initial State: A(100) — B(50) — C(0)
A(75) — B(50) — C(25)A(62.5) — B(50) — C(37.5)A(50) — B(50) — C(50)The Result: The model can no longer distinguish between node A, B, or C because their representations have completely smoothed out into the global average.
In graph signal processing, “frequency” doesn’t refer to time, but to how rapidly node features change across edges.
spectral methods (like ChebNet) still suffer from oversmoothing—but due to practical training dynamics rather than strict mathematical limitations.
The Theoretical Difference
Why They Still Oversmooth in Practice
\[\underbrace{|\mathcal{B}_r(v)| \sim \mathcal{O}(c^{\,r})}_{\text{information to carry}} \quad\Longrightarrow\quad \underbrace{h_v \in \mathbb{R}^{d}}_{\text{fixed pipe}}\]
\[\left\| \frac{\partial h_v^{(L)}}{\partial x_u} \right\| \longrightarrow 0 \quad \text{exponentially in } \mathrm{dist}(u,v)\]
| Oversmoothing | Oversquashing | |
|---|---|---|
| Symptom | Representations too similar | Representations can’t hold enough |
| Cause | Repeated averaging equalizes | Too much info, too small a pipe |
| Failure type | Loss of contrast | Loss of capacity |
| Fix | Residuals, normalization, stay shallow | Rewiring, global attention |
r
/ \
a b
/ \ / \
c d e f
/ \ / \ / \ / \
1 2 3 4 5 6 7 8
| Layer | Node | Leaves summarized | Budget per leaf |
|---|---|---|---|
| 1 | \(c,d,e,f\) | 2 | 64 numbers |
| 2 | \(a,b\) | 4 | 32 numbers |
| 3 | \(r\) | 8 | 16 numbers |
| Depth \(L\) | Nodes in field | Budget per node |
|---|---|---|
| 3 | 15 | 8.5 numbers |
| 6 | 127 | 1.0 number |
| 8 | 511 | 0.25 numbers |
| 10 | 2047 | 0.06 numbers |
( 50 nodes, dense ) ---bridge--- ( 50 nodes, dense )
Fixes:
Depth buys reach. It does not buy bandwidth. /
Every GNN from 2009 to today is a choice of three functions.
\[ \begin{aligned} \textbf{1. Message:} \quad & m_{ij}^{(l)} = M_l\!\left(h_i^{(l)},\, h_j^{(l)},\, e_{ij}\right) \\[4pt] \textbf{2. Aggregate:} \quad & a_i^{(l)} = \bigoplus_{j \in \mathcal{N}(i)} m_{ij}^{(l)} \\[4pt] \textbf{3. Update:} \quad & h_i^{(l+1)} = U_l\!\left(h_i^{(l)},\, a_i^{(l)}\right) \end{aligned} \]
Permutation equivariance is now automatic: the same \(M_l\) is applied to every edge, and \(\bigoplus\) ignores order. The symmetry is baked into the architecture, not learned from data (e.g. via data augmentation):
Reading any new GNN paper: ask what is the message, what is the aggregation, what is the update.
GraphSAGE (2017): make it scale, make it inductive.
\[h_i^{(l+1)} = \sigma\!\left( W^{(l)} \cdot \left[\, h_i^{(l)} \;\Vert\; \mathrm{AGG}\big(\{h_j^{(l)} : j \in \mathcal{N}_{\text{samp}}(i)\}\big) \right] \right)\]
GAT (2018): learn the neighbor weights.
\[\alpha_{ij} = \frac{\exp\!\big(\mathrm{LeakyReLU}(a^\top [Wh_i \Vert Wh_j])\big)}{\sum_{k \in \mathcal{N}(i)} \exp\!\big(\mathrm{LeakyReLU}(a^\top [Wh_i \Vert Wh_k])\big)}, \qquad h_i' = \sigma\!\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij} W h_j\right)\]
GIN (2019): make it maximally expressive.
\[h_i^{(l+1)} = \mathrm{MLP}^{(l)}\!\left( (1 + \epsilon^{(l)}) \cdot h_i^{(l)} + \sum_{j \in \mathcal{N}(i)} h_j^{(l)} \right)\]
Xu, Hu, Leskovec & Jegelka, 2019 — “How Powerful Are Graph Neural Networks?”
Key terms: - \(h_v^{(k)}\): node representation after \(k\) layers (\(h_v^{(0)} = x_v\)) - \(\mathcal{N}(v)\): neighbors of \(v\) - \(\epsilon^{(k)}\): learnable or fixed, lets layer distinguish self vs neighbors - \(\mathrm{MLP}^{(k)}\): small feedforward net
Graph-level readout: - For whole-graph prediction: \[ h_G = \Big\Vert_{k=0}^{K} \sum_{v \in V} h_v^{(k)} \] - (Sum over all nodes for each layer, concatenate across layers)
Message-passing mapping: - Message: identity - Aggregation: sum - Update: MLP
Failures: - Same mean/max for \(\{\text{blue},\text{blue},\text{blue}\}\) vs \(\{\text{blue}\}\); only sum distinguishes. - \(\{\text{red},\text{blue},\text{blue}\}\) vs \(\{\text{red},\text{red},\text{blue}\}\): only sum and mean separate.
Why MLP after sum? - Sums can collide (\(1+3=2+2\)); MLP “un-collides” multisets — ensures injectivity with enough capacity.
Design rule: - Counting/multiplicity needed? → Use sum - Averaging needed? (e.g. influence in social, smooth fields) → Use mean
Correspondence: - WL colors \(\leftrightarrow\) node features in GNN - Hashing \(\leftrightarrow\) update - Multiset agg \(\leftrightarrow\) sum aggregation
Key results: - Upper bound: Any MP-GNN ≤ 1-WL in power; more layers/parameters won’t break this limit - Achievability: Aggregation and readout injective (sum + MLP): GNN matches 1-WL (GIN maximally expressive within MP-GNNs) - Blind spots: 1-WL (and thus GIN) can’t count triangles, nor distinguish 6-cycle from two triangles
Still relevant:
Limitations:
Summary: GIN set the theoretical limit for MP-GNNs, proved sum+MLP is optimal up to WL power, and moved the field from guesswork to principled architecture design.
The observation: a transformer is a GNN. Self-attention over \(n\) tokens is message passing on a complete graph with attention-derived edge weights. Sequences only work because positional encodings restore the order that the complete graph discarded.
So the recipe follows immediately: let every node attend to every other node, and inject structure through encodings rather than through connectivity.
Attention is \(O(n^2)\) in nodes. * Fifty atoms: trivial. * A few thousand protein residues: manageable with linear-attention approximations. * A hundred million nodes: out of the question.
Graph transformers own molecular property prediction; sampled message passing still owns web-scale node classification. That split is a feature not a bug.
History in brief: The field started with rigorous but impractical spectral graph convolution, then developed tractable approximations that powered a decade of progress. Now, the field returns to the original theory: using Laplacian eigenvectors, spectral insights, and representation theory: to address current challenges.
The rigorous version was never wrong. It was just early.