# On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 65 references that are in the map.
- First posted on arXiv 5 Dec 2022.

## Builds on (most cited first, 30 of 36)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Vision GNN: An Image is Worth Graph of Nodes](https://mlsanity.com/paper/2206.00272/) (2022)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [Towards Deeper Graph Neural Networks with Differentiable Group Normalization](https://mlsanity.com/paper/2006.06972/) (2020)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)

## Built on by (most cited first, 30 of 64)

- [On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning](https://mlsanity.com/paper/2502.10818/) (2025)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement](https://mlsanity.com/paper/2503.09008/) (2025)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting](https://mlsanity.com/paper/2305.09703/) (2023)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring](https://mlsanity.com/paper/2502.04891/) (2025)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited](https://mlsanity.com/paper/2407.09381/) (2024)
- [PANDA: Expanded Width-Aware Message Passing Beyond Rewiring](https://mlsanity.com/paper/2406.03671/) (2024)
- [Beyond Over-smoothing: Uncovering the Trainability Challenges in Deep Graph Neural Networks](https://mlsanity.com/paper/2408.03669/) (2024)
- [UniIF: Unified Molecule Inverse Folding](https://mlsanity.com/paper/2405.18968/) (2024)
- [A Systematic Literature Review of Spatio-Temporal Graph Neural Network Models for Time Series Forecasting and Classification](https://mlsanity.com/paper/2410.22377/) (2024)
- [Continuous Product Graph Neural Networks](https://mlsanity.com/paper/2405.18877/) (2024)
- [WiGNet: Windowed Vision Graph Neural Network](https://mlsanity.com/paper/2410.00807/) (2024)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2411.17429/) (2024)
- [Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvature](https://mlsanity.com/paper/2503.01079/) (2025)
- [Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks](https://mlsanity.com/paper/2401.14580/) (2024)
- [On the Two Sides of Redundancy in Graph Neural Networks](https://mlsanity.com/paper/2310.04190/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks](https://mlsanity.com/paper/2411.02279/) (2024)
- [Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks](https://mlsanity.com/paper/2508.19071/) (2025)
- [mHC-GNN: Manifold-Constrained Hyper-Connections for Graph Neural Networks](https://mlsanity.com/paper/2601.02451/) (2026)
- [Subhomogeneous Deep Equilibrium Models](https://mlsanity.com/paper/2403.00720/) (2024)
- [xAI-Drop: Don't Use What You Cannot Explain](https://mlsanity.com/paper/2407.20067/) (2024)
- [When Graph Neural Networks Meet Dynamic Mode Decomposition](https://mlsanity.com/paper/2410.05593/) (2024)
- [ADMP-GNN: Adaptive Depth Message Passing GNN](https://mlsanity.com/paper/2509.01170/) (2025)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [TSC: A Simple Two-Sided Constraint against Over-Smoothing](https://mlsanity.com/paper/2408.03152/) (2024)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have succeeded in various computer science applications, yet deep GNNs underperform their shallow counterparts despite deep learning's success in other domains. Over-smoothing and over-squashing are key challenges when stacking graph convolutional layers, hindering deep representation learning and information propagation from distant nodes. Our work reveals that over-smoothing and over-squashing are intrinsically related to the spectral gap of the graph Laplacian, resulting in an inevitable trade-off between these two issues, as they cannot be alleviated simultaneously. To achieve a suitable compromise, we propose adding and removing edges as a viable approach. We introduce the Stochastic Jost and Liu Curvature Rewiring (SJLR) algorithm, which is computationally efficient and preserves fundamental properties compared to previous curvature-based methods. Unlike existing approaches, SJLR performs edge addition and removal during GNN training while maintaining the graph unchanged during testing. Comprehensive comparisons demonstrate SJLR's competitive performance in addressing over-smoothing and over-squashing.