Why a Graph Neural Network Gets Worse With More Layers

Two layers works, three is about the same, six is worse than two, and twelve produces a model that assigns nearly the same output to every node. This is not underfitting and it is not a learning-rate problem. It is oversmoothing, and it follows from what the layer computes.

The failure has a name

Qimai Li, Zhichao Han and Xiao-Ming Wu identified the mechanism in Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning (AAAI 2018). Their observation is that a graph convolution is a special form of Laplacian smoothing — each layer replaces a node’s features with a weighted average of its neighbourhood, including itself. One round of that is useful, because it is exactly the homophily assumption the model rests on: connected nodes tend to be similar, so averaging reduces noise. Applied repeatedly, smoothing does what smoothing does. It removes the differences it is smoothing, and the differences between nodes are the entire output.

Oversmoothing is the name for that endpoint: as depth increases, node representations converge toward one another, and past some depth they carry information about the graph’s global structure and almost none about which node you asked about.

Eight layers, by hand

Take a path of four nodes, A–B–C–D, one scalar feature per node, starting at (1, 0, 0, 0). One layer is the mean over the closed neighbourhood — the node and its neighbours — which is a GCN layer with the weight matrix set to the identity so that only the propagation is visible. A has two members in its closed neighbourhood (A, B), B has three (A, B, C), C has three (B, C, D), D has two (C, D).

layer      A        B        C        D      spread (max - min)
  0    1.0000   0.0000   0.0000   0.0000       1.0000
  1    0.5000   0.3333   0.0000   0.0000       0.5000
  2    0.4167   0.2778   0.1111   0.0000       0.4167
  3    0.3472   0.2685   0.1296   0.0556       0.2917
  4    0.3079   0.2485   0.1512   0.0926       0.2153
  5    0.2782   0.2359   0.1641   0.1219       0.1563
  6    0.2570   0.2260   0.1740   0.1430       0.1140
  7    0.2415   0.2190   0.1810   0.1585       0.0830
  8    0.2303   0.2138   0.1862   0.1697       0.0605
  ...
  inf  0.2000   0.2000   0.2000   0.2000       0.0000

Layer 1 through 3 are the useful part: information from A has reached C and D, and the four values still differ enough to separate the nodes. By layer 8 the spread is 6% of what it was, and a classifier reading these four numbers is choosing between 0.2303 and 0.1697. Add float16 arithmetic and a normalisation layer and that difference is inside the noise.

The limit is checkable, which is what makes this more than a picture. The propagation matrix here is row-stochastic, so its stationary distribution is proportional to the closed-neighbourhood sizes, (2, 3, 3, 2) normalised to (0.2, 0.3, 0.3, 0.2). The quantity 0.2A + 0.3B + 0.3C + 0.2D is conserved by every layer — it is 0.2 at layer 0 and 0.2 at layer 8 — and since every node converges to that same weighted average, the limit is 0.2 everywhere. The final state depends on the graph’s degrees and not at all on which node started with the 1.

Why it converges, and how fast

Read the spread column as a sequence and the ratios settle quickly: 0.2917/0.4167 = 0.700, then 0.738, 0.726, 0.729, 0.728, 0.729. The spread contracts by a constant factor of roughly 0.73 per layer. That factor is the second-largest eigenvalue of the propagation matrix; the largest is 1 and belongs to the constant vector that everything is collapsing onto. The gap between them is the graph’s spectral gap.

Constant factor per layer means geometric decay, and that is the part worth internalising. It is not that quality degrades gently past some depth — it is that the signal is multiplied by 0.73 each time. At twenty layers the spread is 0.73¹⁹ of the layer-1 spread, about a quarter of one percent. There is no safe range in which “just add a few more layers” is a small change.

Kenta Oono and Taiji Suzuki proved the general statement in Graph Neural Networks Exponentially Lose Expressive Power for Node Classification (ICLR 2020): under conditions on the weight matrices, the distance from the node representations to an invariant subspace — the subspace where nodes are indistinguishable except by degree and connected component — shrinks exponentially in depth. The rate depends on the spectral gap and on the largest singular value of the layer weights, which is also why aggressive weight normalisation can make oversmoothing worse rather than better.

A denser graph has a larger spectral gap and therefore oversmooths in fewer layers, which is the practical inversion of the usual intuition: the well-connected graph that seems like it should support a deep model is the one that tolerates depth least.

What actually mitigates it

Nothing here is a cure. Each one changes the operator so that the convergence is slowed or anchored.

• Residual connections to the input, not just to the previous layer. Ming Chen and colleagues’ Simple and Deep Graph Convolutional Networks (ICML 2020) combines an initial residual — every layer mixes in a fraction of the layer-0 representation — with identity mapping on the weights, and reports models trained to 64 layers. The initial residual is the load-bearing half: re-injecting the input at every layer means the fixed point still depends on the node.
• Decouple propagation from transformation. Johannes Gasteiger and colleagues’ Predict then Propagate (ICLR 2019) replaces stacked layers with a personalised-PageRank propagation that carries a teleport probability α back to the starting node. The teleport term is an anchor with weight α that never decays, so the limit is not the constant vector — you can propagate far without collapsing, and there is only one small MLP to train.
• Jumping knowledge. Keqiang Xu and colleagues’ Representation Learning on Graphs with Jumping Knowledge Networks (ICML 2018) keeps every layer’s output and combines them at the end by concatenation, max or an LSTM, letting each node draw on the depth that suits it. A node in a sparse region uses the deep representation; a node in a hub uses a shallow one.
• Normalise the pairwise distances. Lingxiao Zhao and Leman Akoglu’s PairNorm (ICLR 2020) rescales representations after each layer so that the total pairwise squared distance stays constant. The relative geometry still drifts, but the collapse to a single point is prevented by construction.
• Drop edges during training. Yu Rong and colleagues’ DropEdge (ICLR 2020) removes a random subset of edges each epoch, which sparsifies the propagation matrix, reduces the mixing rate, and acts as a regulariser. It slows convergence to the fixed point; it does not move the fixed point.

What does not help: feature dropout, wider layers, more training, batch normalisation on its own, or a better optimiser. None of them touch the operator. Nor does attention rescue you — a graph attention layer learns the averaging weights instead of fixing them, so it can slow smoothing but it is still averaging.

The unfashionable answer is often the right one: use two or three layers. Most node classification benchmarks are strongly homophilous and two hops carries nearly all the usable signal. If you genuinely need information from six hops away, a propagation scheme with an anchor term is a better tool than six stacked layers, and it is cheaper — depth is also what makes neighbour sampling expensive.

The other failure it gets confused with

Over-squashing is a different problem with a similar-sounding symptom. Uri Alon and Eran Yahav described it in On the Bottleneck of Graph Neural Networks and its Practical Implications (ICLR 2021): an L-layer model’s receptive field grows exponentially with L, and all of it has to be compressed into one fixed-size vector. Signal from a distant node arrives attenuated because it is sharing a narrow channel with exponentially many other nodes.

The distinction is worth keeping straight because the fixes are opposite in spirit. Oversmoothing is too much mixing, and it is addressed by anchoring or slowing propagation. Over-squashing is too little capacity on long-range paths, and it is addressed by widening the channel — larger hidden dimensions, or rewiring the graph to add shortcut edges through the bottleneck. A model that is simultaneously oversmoothed and over-squashed is a model asked to carry long-range information through stacked local averaging, which is the configuration to avoid rather than to tune.