Depth in GNNs: Why Deeper Is Not Always Better
Published:
Intuition First
Think of a GNN layer as a โneighbourhood blender.โ Each node pours its features into a blender with its neighbours and takes the average result. One blend: useful โ the node learns from its surroundings. Two blends: still useful but blurrier. Ten blends: every node has blended with every other nodeโs blend of every other node โ the result is a uniform grey smoothie.
Transformers donโt have this problem because each layer performs attention (selective mixing), not averaging (uniform mixing). A 96-layer Transformer sharpens distinctions; a 96-layer GCN erases them.
Depth in GNNs Is Different
In Transformers, adding layers increases representational depth โ each layer refines the global representation with no structural penalty. Transformers scale to 96+ layers with consistent improvement.
In GNNs, each layer has a dual effect:
- Positive: expands the receptive field by one hop (more context)
- Negative: smooths features by averaging neighbours (more oversmoothing)
These effects fight each other. The optimal depth depends on which dominates.
What Depth Buys: Receptive Field
With \(K\) GNN layers, node \(v\) aggregates information from its \(K\)-hop neighbourhood \(\mathcal{N}_K(v)\). For node classification, the useful depth \(K^{*}\) is the number of hops that actually contains task-relevant information.
For homophilic datasets (Cora, CiteSeer) most task-relevant context sits at 1โ2 hops. Beyond that the neighbourhood is dominated by same-label nodes that add little new information while accelerating oversmoothing.
For long-range tasks โ predicting a molecular property that depends on the whole molecule โ you need \(K\) at least as large as the relevant interaction distance, which can approach the graph diameter. That requirement collides head-on with oversmoothing.
The Empirical Depth Cliff
On standard homophilic node-classification benchmarks, accuracy as a function of depth follows a characteristic shape:
Layers: 1 2 3 4 8 16 32
GCN: โ โ โ โ โ โ โ
GAT: โ โ โ โ โ โ โ
Performance peaks at 2โ3 layers, then falls away; at very large depth the model degrades toward predicting a constant, because oversmoothing has collapsed the node distinctions. (The shape is what matters here โ exact numbers depend heavily on dataset, split, normalisation and regularisation, so treat any specific table you see as setup-specific rather than a law.)
The Depth Dilemma
This creates an uncomfortable trade-off:
- Task requires long-range context โ need many layers
- Many layers โ oversmoothing โ performance collapse
- Few layers โ undershooting the diameter โ missing distant context
For graphs with large diameter (long molecules, social networks, knowledge graphs), standard GNNs are caught in this dilemma with no good resolution.
Architectural Solutions for Deep GNNs
GCNII (Chen et al., 2020)
GCNII adds two modifications that make very deep GCNs trainable:
- Initial residual: a skip connection back to the initial representation \(H^{(0)}\) at every layer
- Identity mapping: each weight matrix is blended with the identity
where \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) is the usual propagation matrix, \(\alpha_k \in (0,1)\) controls how much of the initial feature signal is re-injected, and \(\beta_k \in (0,1)\) controls how close the layerโs weight matrix stays to the identity (Chen et al. set \(\beta_k = \log(1 + \lambda/k) \approx \lambda/k\), so deeper layers stay closer to the identity).
The mechanism is worth stating in the language of the oversmoothing post. Plain propagation iterates \(\hat{A}^{K}\), whose limit is the rank-one projector \(u_1u_1^{\top}\). The \(\alpha_k H^{(0)}\) term makes the iteration an affine one whose fixed point retains a component of \(H^{(0)}\) โ so the limit is no longer rank one, and the collapse is arrested. The \(\beta_k\) term separately keeps the Jacobian of each layer near the identity, which is what prevents gradient vanishing. Neither alone would suffice.
GCNII reaches competitive accuracy at 64 layers on Cora, a depth at which plain GCN has long since collapsed.
JK-Net (Jumping Knowledge, Xu et al., 2018)
JK-Net uses all intermediate representations, not just the last layer:
where \(\mathrm{AGG}\) is concatenation, max-pooling, or an LSTM over the layer index. Each nodeโs final embedding draws on every receptive-field size at once, so a node whose useful context is 2 hops away is not forced to read it off a heavily smoothed layer-\(K\) representation. Oversmoothing in the deep layers is offset by the sharper early-layer ones.
APPNP
As discussed in the APPNP post: separate transformation from propagation. Propagation becomes the personalised-PageRank iteration
The teleport probability \(\alpha \in (0,1)\) keeps each node anchored to its own transformed features \(H\) no matter how many propagation steps are taken. Note that the limit exists and is not rank one: the inverse is well defined because \((1-\alpha)\hat{A}\) has spectral radius \(1-\alpha < 1\). That is precisely why APPNP can propagate for 10 or 20 steps without oversmoothing, while plain \(\hat{A}^{K}\) cannot.
DropEdge
Randomly drop a fraction of edges during each training step. This reduces the averaging effect per layer, slowing oversmoothing. Analogous to Dropout for edges.
Worked Example: Receptive Field Growth
If a graph were an infinite tree with branching factor \(d = 10\), the \(k\)-hop neighbourhood would grow as \(\lvert \mathcal{N}_k(v)\rvert \approx d^{k}\):
| Layers \(k\) | Upper bound \(d^{k}\) | Notes |
|---|---|---|
| 1 | \(\sim 10\) nodes | Direct neighbours |
| 2 | \(\sim 10^{2}\) nodes | 2-hop |
| 3 | \(\sim 10^{3}\) nodes | Often exceeds the whole graph |
| 4 | \(\sim 10^{4}\) nodes | Saturates all but the largest graphs |
Read these as upper bounds, not counts: on a real graph, cycles and overlapping neighbourhoods mean the same node is reached by many paths, so growth saturates well before \(d^{k}\) and stops entirely once the receptive field covers the connected component.
Cora has 2,708 nodes and an average degree of roughly 4, so a 4-layer GCNโs receptive field already covers a large fraction of the graph from a typical node. That is exactly the regime in which oversmoothing bites: every node has โheard fromโ essentially every other node, weighted only by degree.
The implication: on most citation and social graphs, 2 layers already reach most of the useful context. Going deeper adds smoothing, not signal.
The Depth vs Width Trade-off
An alternative to depth: make each layer wider (more hidden dimensions). In practice, going from d=64 to d=256 with 2-3 layers often outperforms using d=64 with 8-16 layers โ wider layers better capture local structure without oversmoothing.
The GNN community is moving toward:
- Shallow local GNNs (2-4 layers) for node-level tasks
- Aggregation-then-transform designs (APPNP, SGC) for medium range
- Graph Transformers or GPS (Transformer + local MPNN) for long-range tasks
Summary
| Depth | Effect | Recommendation |
|---|---|---|
| 1-2 layers | Minimal smoothing, limited context | Good baseline |
| 3-4 layers | Optimal for most homophilic benchmarks | Default choice |
| 8-16 layers | Oversmoothing dominates; needs residuals | Use GCNII, JK-Net |
| 32+ layers | Near-impossible without special design | GCNII or abandon local MPNN |
GNN depth scaling does not follow the same scaling laws as Transformer depth. Understanding this โ and which architectural tricks restore the benefit of depth โ is central to modern GNN design.
References
- Chen, M., Wei, Z., Huang, Z., Ding, B., & Li, Y. (2020). Simple and Deep Graph Convolutional Networks. ICML 2020 (GCNII).
- Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., & Jegelka, S. (2018). Representation Learning on Graphs with Jumping Knowledge Networks. ICML 2018 (JK-Net).
- Rong, Y., Huang, W., Xu, T., & Huang, J. (2020). DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. ICLR 2020.