mlsanityData to 7 Oct 2026

Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges

arXiv 2311.07073 ↗First posted 13 Nov 2023cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

Graph-based message-passing neural networks (MPNNs) have achieved remarkable success in both node and graph-level learning tasks. However, several identified problems, including over-smoothing (OSM), limited expressive power, and over-squashing (OSQ), still limit the performance of MPNNs. In particular, OSQ serves as the latest identified problem, where MPNNs gradually lose their learning accuracy when long-range dependencies between graph nodes are required. In this work, we provide an exposition on the OSQ problem by summarizing different formulations of OSQ from current literature, as well as the three different categories of approaches for addressing the OSQ problem. In addition, we also discuss the alignment between OSQ and expressive power and the trade-off between OSQ and OSM. Furthermore, we summarize the empirical methods leveraged from existing works to verify the efficiency of OSQ mitigation approaches, with illustrations of their computational complexities. Lastly, we list some open questions that are of interest for further exploration of the OSQ problem along with potential directions from the best of our knowledge.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 72 of its 134 references that are in the map. First posted on arXiv 13 Nov 2023.

Builds on

72 of 134 references.

References · 72

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  9. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  10. 2019Simplifying Graph Convolutional Networkscited by 1,470
  11. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  12. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
38 more
  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2020Benchmarking Graph Neural Networkscited by 672
  3. 2020A Generalization of Transformer Networks to Graphscited by 653
  4. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  5. 2018Hypergraph Neural Networkscited by 482
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  7. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  8. 2019Diffusion Improves Graph Learningcited by 414
  9. 2019Hyperbolic Graph Convolutional Neural Networkscited by 400
  10. 2020Explainability in Graph Neural Networks: A Taxonomic Surveycited by 383
  11. 2021GRAND: Graph Neural Diffusioncited by 258
  12. 2022Long Range Graph Benchmarkcited by 258
  13. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  14. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
  15. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  16. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 207
  17. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  18. 2021Self-Supervised Learning of Graph Neural Networks: A Unified Reviewcited by 184
  19. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
  20. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  21. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  22. 2020Directional Graph Networkscited by 132
  23. 2021UniGNN: a Unified Framework for Graph and Hypergraph Neural Networkscited by 127
  24. 2022Graph-Coupled Oscillator Networkscited by 123
  25. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  26. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  27. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  28. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  29. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  30. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  31. 2023DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusioncited by 85
  32. 2021Beltrami Flow and Neural Diffusion on Graphscited by 84
  33. 2023Attending to Graph Transformerscited by 81
  34. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  35. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  36. 2022Expander Graph Propagationcited by 75
  37. 2022Benchmarking Graphormer on Large-Scale Molecular Modeling Datasetscited by 63
  38. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 63

50 most cited of 72 All 72 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 8; 2025: 12; 2026: 2.

22 papers.

Sort:

  1. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  2. 2024On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systemscited by 26
  3. 2024Cayley Graph Propagationcited by 21
  4. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  5. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  6. 2024Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networkscited by 6
  7. 2025Improving Long-Range Interactions in Graph Neural Simulators via Hamiltonian Dynamicscited by 6
  8. 2025PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networkscited by 5
  9. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  10. 2025Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guaranteescited by 3
  11. 2025Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNscited by 3
  12. 2024When Graph Neural Networks Meet Dynamic Mode Decompositioncited by 2
10 more
  1. 2025Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passingcited by 2
  2. 2024Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuningcited by 1
  3. 2025Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphscited by 1
  4. 2025Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulationscited by 1
  5. 2026Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learningcited by 1
  6. 2024Information propagation dynamics in Deep Graph Networkscited by 0
  7. 2025Graph Pseudotime Analysis and Neural Stochastic Differential Equations for Analyzing Retinal Degeneration Dynamics and Beyondcited by 0
  8. 2025Schreier-Coset Graph Propagationcited by 0
  9. 2025TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flowscited by 0
  10. 2026S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learningcited by 0