In the world of deep learning, depth is usually synonymous with power. Convolutional Neural Networks and Transformers rely on dozens or hundreds of layers to build complex hierarchical representations. Yet, for years, Graph Neural Networks (GNNs) have been stuck in a "shallow trap," typically performing best with only two or three layers. Adding more layers usually leads to a sharp decline in performance, preventing these models from capturing the long-range dependencies and global structures inherent in large-scale graphs.
Recent research has moved beyond simply identifying this "depth wall" to diagnosing its mathematical roots and engineering the bypasses necessary to build truly deep GNNs.
The Three Walls of Deep GNNs
To understand why GNNs fail at depth, we must look at three distinct phenomena that degrade the signal as it passes through the network.
- Over-smoothing: This is the most cited culprit. As Chaoqi Yang and colleagues note in Revisiting "Over-smoothing" in Deep GCNs, repeated graph convolutions act like a low-pass filter. Eventually, every node’s representation converges to the same value, making them indistinguishable.
- Over-squashing: When a model tries to squeeze information from an exponentially growing neighborhood into a fixed-size vector, information from distant nodes is "squashed" and lost. Alessio Gravina explores this in Information propagation dynamics in Deep Graph Networks, framing the problem as a bottleneck in the flow of information across the graph's diameter.
- Trainability Collapse: Even if the representations remain distinct, the network might become impossible to train. Wei Huang and Miao Zhang prove in Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective that deep GNNs suffer from an exponential collapse in the ability of gradient descent to find viable solutions.
Engineering Stability through Normalization
The first wave of solutions focused on stabilizing the forward and backward passes. Just as BatchNorm enabled deep CNNs, new normalization schemes are doing the same for graphs.
George Dasoulas and Kevin Scaman introduced LipschitzNorm in Lipschitz normalization for self-attention layers with application to graph neural networks. By bounding the Lipschitz constant of the layers, they prevent gradients from exploding, allowing GNNs to scale to 30+ layers. Similarly, the DeeperGCN framework introduced message normalization and pre-activation residual connections to successfully train models with over 100 layers.
Another approach, Adaptive Initial Residual (AIR), proposed by Wentao Zhang in Model Degradation Hinders Deep Graph Neural Networks, suggests that the problem isn't just smoothing, but "model degradation"—the same identity-mapping issue that ResNets solved for vision. By anchoring deep layers to the initial node features, the model retains local identity even as it integrates global structure.
GNNs as Continuous Dynamical Systems
A more radical shift treats GNNs not as a stack of discrete layers, but as a continuous process. In GRAND: Graph Neural Diffusion, Ben Chamberlain and colleagues reinterpret GNN layers as time-steps in a Parital Differential Equation (PDE). This allows them to use stable numerical solvers to propagate information, effectively bypassing the stability issues of discrete stacking.
Building on this, Alessio Gravina and Davide Bacciu introduced Anti-Symmetric DGN. By enforcing anti-symmetry in the weight matrices, they ensure that the "energy" of the node features is conserved, preventing the signal from vanishing or exploding regardless of depth.
Breaking the Smoothing Limit with Chaos and Noise
If over-smoothing is the tendency of features to become too similar, one solution is to inject controlled diversity. Bastian Epping demonstrated in Graph Neural Networks Do Not Always Oversmooth that by simply increasing the variance of initial weights, GNNs can enter a "chaotic" phase. In this regime, node features remain distinct even after thousands of layers.
Similarly, Jonathan Godwin and Alvaro Sanchez-Gonzalez proposed Noisy Nodes in Very Deep Graph Neural Networks Via Noise Regularisation. By corrupting input features and adding a denoising task, they force the deep network to maintain a high-fidelity representation of individual nodes, enabling 100-layer architectures for complex tasks like molecular property prediction.
Why Depth Matters
The push for depth isn't just an academic exercise. Many real-world problems require a large receptive field. For instance, in ProGraML, Chris Cummins shows that for compiler optimizations, a GNN must "see" across long control-flow paths to understand program behavior. Without depth, the model is blind to the long-range dependencies that define the program's logic.
By solving the stability and smoothing problems, researchers are finally allowing GNNs to move from local pattern matchers to global reasoners, capable of processing the vast, multi-hop complexities of the modern relational world.