Over-Smoothing in Deep GNNs

In an image classifier, stacking more convolutional layers usually helps — deeper networks like ResNet-152 outperform shallow ones because each layer builds a more abstract feature. A graph neural network with the same intuition — "more layers, more capacity" — breaks in the opposite direction: stack more than a handful of graph convolution layers, and accuracy falls off a cliff. Every node's features start looking identical to every other node's, and the model can no longer tell them apart at all.

The analogy: stirring milk into coffee

Each graph convolution layer mixes a node's value with its neighbors' values, the way stirring a spoon of milk into coffee mixes it with the surrounding liquid. One stir, and you can still see swirls — some regions are milkier than others. Stir a hundred times, and the cup becomes a uniform, undifferentiated tan: every drop of liquid has effectively mixed with every other drop, and the original swirl pattern is gone forever. Stacking $k$ graph convolution layers is exactly $k$ rounds of stirring: each layer's neighbor-averaging step mixes a node's representation with everything within $k$ hops, and once $k$ is large enough to span the whole (well-connected) graph, every node converges toward the same "average" value.

Why the math forces this

Most GNN layers update a node by aggregating and averaging its neighbors, which is a form of applying $D^{-1}A$ (or a symmetrically normalized version) to the node feature matrix at every layer, where $A$ is the adjacency matrix and $D$ is the degree matrix. Repeated application of this normalized adjacency operator is a random walk on the graph — and every random walk on a connected, non-bipartite graph converges to a single stationary distribution regardless of where it started. Applying it $k$ times, layer after layer, pushes every node's representation toward that same stationary point:

$$h^{(k)} = \left(D^{-1}A\right)^k h^{(0)}$$

In words: after $k$ rounds of neighbor-averaging, a node's representation is a weighted blend of the entire $k$-hop neighborhood's original features, and as $k$ grows, that blend converges toward one graph-wide average — the differences between nodes that made classification possible get averaged away.

Worked example 1: a 5-node cycle graph

Take a 5-node ring where each node connects to its two neighbors, with initial values $x^{(0)} = [10, 0, 0, 0, 0]$. One layer of mean-aggregation (each node becomes the average of itself and its two neighbors, weight $\tfrac13$ each): node 1 becomes $\tfrac13(10+0+0) = 3.33$ (neighbors are nodes 2 and 5), node 2 becomes $\tfrac13(0+10+0)=3.33$, node 5 similarly $3.33$, nodes 3 and 4 (two hops from node 1) get $0$. After a second layer, the spike has spread further and flattened: values move toward roughly $[2.7, 2.4, 1.6, 1.6, 2.4]$-ish. Keep applying this and the values on all 5 nodes converge toward $2.0$ — the graph-wide average of the original $[10,0,0,0,0]$. After enough layers, node 1 (which started with all the signal) and node 3 (which started with none) are indistinguishable.

Worked example 2: measuring it with cosine similarity

Suppose after 2 layers, two nodes' feature vectors are $h_a = [0.9, 0.1]$ and $h_b = [0.7, 0.3]$ — cosine similarity $\cos\theta = \tfrac{h_a \cdot h_b}{\|h_a\|\|h_b\|} = \tfrac{0.66}{0.905 \times 0.762} \approx 0.957$, already quite similar. After 8 layers, suppose they have become $h_a = [0.501, 0.499]$ and $h_b = [0.499, 0.501]$ — cosine similarity $\approx 0.999992$, essentially identical. A downstream classifier fed these two vectors can no longer separate node $a$ from node $b$, even if their true labels differ — this collapsing similarity, tracked layer by layer, is exactly how researchers detect and quantify over-smoothing.

Watch how the descent path behaves under different step settings above — over-smoothing is a related but distinct failure: it is not the optimizer overshooting, it is the architecture itself, at a fixed depth, forcing every node toward one shared point regardless of how well it is trained.

What this means in practice

This is why most practical GNNs stay shallow — 2 to 4 layers — even though a node's "receptive field" (how many hops of neighbors it can see) is correspondingly small; a 3-layer GNN can only ever use information from within 3 hops, no matter how large the graph is. Fixes include residual/skip connections that let a node's own original features bypass the averaging (borrowed from ResNet), normalization layers, attention-based aggregation (as in GATs, which learn to weight some neighbors near zero instead of averaging uniformly), and explicitly separating "how many hops to gather information from" (which can be large) from "how many learnable layers to stack" (which stays small), as GraphSAGE-style and PageRank-inspired architectures do.

Practice

1. Explain why a random walk on a graph converging to a stationary distribution implies that a deep mean-aggregation GNN over-smooths.
2. For the 5-node cycle example, what value does every node converge to as the number of layers grows, and why does that specific number appear?
3. Two fixes for over-smoothing were mentioned — residual connections and attention-based aggregation. Explain in one sentence each why they slow the collapse.