Introduction
Deep Graph Neural Networks (GNNs) often suffer from a performance degradation known as over-smoothing, where node representations become increasingly similar as network depth increases. While residual connections have revolutionized deep learning in computer vision, their application in GNNs has seen limited success in preventing this phenomenon. This paper investigates why standard residuals fail and proposes a novel DRIVE (colD staRt adaptIVe rEsidual) connection to enable truly deep GNNs.
The Over-smoothing Problem and Residual Failure
As GNNs grow deeper, node features tend to converge to a stationary distribution, losing the distinctiveness required for downstream tasks. In standard deep learning, residual connections allow for identity mappings that facilitate gradient flow. However, in GNNs, simple residuals only marginally delay smoothing.
The authors identify two primary reasons for this failure:
- The Binomial Trap: Through path decomposition, a GNN with skip connections can be viewed as an ensemble of paths. In deep networks, the distribution of path lengths follows a binomial distribution where "medium-length" paths—those long enough to be smoothed—dominate the output, drowning out the "short" paths that preserve local features.
- Gradient Smoothing: It is not just the forward pass that smooths; the gradients themselves become smoothed during backpropagation. This prevents weight matrices from effectively learning the identity mapping needed to skip layers.
Methodology: The DRIVE Connection and UDGNN
To address these issues, the authors introduce the DRIVE connection. Unlike standard residuals, DRIVE incorporates a trainable coefficient $\alpha$, initialized at zero.
Cold Start Adaptive Residual (DRIVE)
By initializing $\alpha = 0$, the model begins training as a "cold start" identity mapping—effectively a shallow MLP. This creates an information "superhighway" from input to output. As training progresses, the model adaptively learns the optimal amount of neighbor information to aggregate. If the graph structure is noisy or harmful (as in heterophily or noisy datasets), the model can maintain a low $\alpha$ to preserve node-specific features.
Path Decomposition Perspective
The theoretical foundation of DRIVE lies in rethinking the network as a collection of paths. By decomposing the residual and initial paths, the authors show how different architectures favor different path length distributions.
The UDGNN Framework
The DRIVE connection is integrated into the Universal Deep GNN (UDGNN) framework. This framework combines DRIVE with a FeedForward Module (FFN) similar to those in Transformers. UDGNN is convolution-agnostic, meaning it can be wrapped around standard layers like GCN, GAT, or GraphSAGE to make them deep-capable.
Experimental Evaluation
The UDGNN framework was tested across 11 datasets covering homophily, heterophily, and noisy scenarios.
Scaling to Extreme Depth
While traditional GNNs typically peak at 2-4 layers, UDGNN maintains high performance even at 64 layers. In the "Cora-Random" benchmark—a version of the Cora dataset with randomized edges—UDGNN successfully ignored the noise by keeping $\alpha$ near zero, whereas standard GNNs failed completely as depth increased.
Performance on Heterophily
UDGNN achieved state-of-the-art results on heterophily datasets (where neighbors often have different labels). On datasets like Squirrel and Chameleon, UDGNN significantly outperformed existing methods, demonstrating its "universal" applicability to different graph types.
Conclusion
By rethinking residual connections through path decomposition and introducing the DRIVE mechanism, this work provides a robust solution to the over-smoothing problem. The DRIVE connection's zero-initialization strategy ensures a stable starting point, allowing deep GNNs to adaptively learn complex graph structures without losing individual node information.
Limitations
The current path decomposition analysis assumes linearity by omitting ReLU activations for simplicity. Future work may involve extending this analysis to non-linear regimes and providing formal convergence proofs for the DRIVE initialization strategy.
Summary updated