# Beyond Over-smoothing: Uncovering the Trainability Challenges in Deep Graph Neural Networks

arXiv: https://arxiv.org/abs/2408.03669 · HTML: https://mlsanity.com/paper/2408.03669/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 42 references that are in the map.
- First posted on arXiv 7 Aug 2024.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [A Survey of the Recent Architectures of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1901.06032/) (2019)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Semantic Graph Convolutional Networks for 3D Human Pose Regression](https://mlsanity.com/paper/1904.03345/) (2019)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Towards Deeper Graph Neural Networks with Differentiable Group Normalization](https://mlsanity.com/paper/2006.06972/) (2020)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [Language Modeling with Deep Transformers](https://mlsanity.com/paper/1905.04226/) (2019)
- [On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks](https://mlsanity.com/paper/2212.02374/) (2022)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Improving Graph Attention Networks with Large Margin-based Constraints](https://mlsanity.com/paper/1910.11945/) (2019)
- [DropMessage: Unifying Random Dropping for Graph Neural Networks](https://mlsanity.com/paper/2204.10037/) (2022)
- [Model Degradation Hinders Deep Graph Neural Networks](https://mlsanity.com/paper/2206.04361/) (2022)
- [Efficient Algorithms for Personalized PageRank Computation: A Survey](https://mlsanity.com/paper/2403.05198/) (2024)
- [Improving Graph Neural Networks with Learnable Propagation Operators](https://mlsanity.com/paper/2210.17224/) (2022)
- [Old can be Gold: Better Gradient Flow can Make Vanilla-GCNs Great Again](https://mlsanity.com/paper/2210.08122/) (2022)

## Built on by (most cited first, 10 of 10)

- [TIDFormer: Exploiting Temporal and Interactive Dynamics Makes A Great Dynamic Graph Transformer](https://mlsanity.com/paper/2506.00431/) (2025)
- [Geometric Machine Learning on EEG Signals](https://mlsanity.com/paper/2502.05334/) (2025)
- [Efficient Mixed Precision Quantization in Graph Neural Networks](https://mlsanity.com/paper/2505.09361/) (2025)
- [ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion](https://mlsanity.com/paper/2504.15920/) (2025)
- [GDGB: A Benchmark for Generative Dynamic Text-Attributed Graph Learning](https://mlsanity.com/paper/2507.03267/) (2025)
- [Directed Acyclic Graph Convolutional Networks](https://mlsanity.com/paper/2506.12218/) (2025)
- [TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows](https://mlsanity.com/paper/2508.05070/) (2025)
- [Rethinking Link Prediction for Directed Graphs](https://mlsanity.com/paper/2502.05724/) (2025)
- [Cascade-KDE: Robust Time-Series Restoration under Out-of-Distribution Impulse Corruptions](https://mlsanity.com/paper/2605.24055/) (2026)
- [Explainable Deep Learning of Resting-State Functional Connectomes Reveals Network Biomarkers of Adolescent Intelligence](https://mlsanity.com/paper/2609.33422/) (2026)

## Abstract (arXiv)

The drastic performance degradation of Graph Neural Networks (GNNs) as the depth of the graph propagation layers exceeds 8-10 is widely attributed to a phenomenon of Over-smoothing. Although recent research suggests that Over-smoothing may not be the dominant reason for such a performance degradation, they have not provided rigorous analysis from a theoretical view, which warrants further investigation. In this paper, we systematically analyze the real dominant problem in deep GNNs and identify the issues that these GNNs towards addressing Over-smoothing essentially work on via empirical experiments and theoretical gradient analysis. We theoretically prove that the difficult training problem of deep MLPs is actually the main challenge, and various existing methods that supposedly tackle Over-smoothing actually improve the trainability of MLPs, which is the main reason for their performance gains. Our further investigation into trainability issues reveals that properly constrained smaller upper bounds of gradient flow notably enhance the trainability of GNNs. Experimental results on diverse datasets demonstrate consistency between our theoretical findings and empirical evidence. Our analysis provides new insights in constructing deep graph models.