Universal Deep GNNs: Rethinking Residual Connection in GNNs from a Path Decomposition Perspective for Preventing the Over-smoothing

Jie Chen, Weiqi Liu, Zhizhong Huang, Junbin Gao, Junping Zhang, Jian PuarXiv 2022 · DOI · arXiv

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:

  1. 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.
  2. 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.
Comparison of skip connection architectures and their performance under over-smoothing conditions.

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.

Path decomposition of residual and initial connections.

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

Abstract

The performance of GNNs degrades as they become deeper due to the over-smoothing. Among all the attempts to prevent over-smoothing, residual connection is one of the promising methods due to its simplicity. However, recent studies have shown that GNNs with residual connections only slightly slow down the degeneration. The reason why residual connections fail in GNNs is still unknown. In this paper, we investigate the forward and backward behavior of GNNs with residual connections from a novel path decomposition perspective. We find that the recursive aggregation of the median length paths from the binomial distribution of residual connection paths dominates output representation, resulting in over-smoothing as GNNs go deeper. Entangled propagation and weight matrices cause gradient smoothing and prevent GNNs with residual connections from optimizing to the identity mapping. Based on these findings, we present a Universal Deep GNNs (UDGNN) framework with cold-start adaptive residual connections (DRIVE) and feedforward modules. Extensive experiments demonstrate the effectiveness of our method, which achieves state-of-the-art results over non-smooth heterophily datasets by simply stacking standard GNNs.
BibTeX
@misc{chen2022universal,
  author = {Jie Chen and Weiqi Liu and Zhizhong Huang and Junbin Gao and Junping Zhang and Jian Pu},
  title = {{Universal Deep GNNs: Rethinking Residual Connection in GNNs from a Path Decomposition Perspective for Preventing the Over-smoothing}},
  year = {2022},
  eprint = {2205.15127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.15127},
}
Figure