mlsanityData to 7 Oct 2026

Understanding over-squashing and bottlenecks on graphs via curvature

arXiv 2111.14522 ↗First posted 29 Nov 2021stat.ML cs.LGcited by 471

Not on the map. Why?

Abstract (arXiv)

Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of k-hop neighbors grows rapidly with k. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.

Key facts. Cited by 471 papers in the map (data through 7 Oct 2026). Builds on 28 of its 63 references that are in the map. First posted on arXiv 29 Nov 2021.

Builds on

28 of 63 references.

References · 28

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Dynamic Graph CNN for Learning on Point Cloudscited by 2,220
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  8. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  9. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  10. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  11. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  12. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
16 more
  1. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  2. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  3. 2019Multi-scale Attributed Node Embeddingcited by 543
  4. 2019Diffusion Improves Graph Learningcited by 414
  5. 2019Hyperbolic Graph Convolutional Neural Networkscited by 400
  6. 2019Provably Powerful Graph Networkscited by 385
  7. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  8. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  9. 2019Hyperbolic Graph Neural Networkscited by 244
  10. 2018Bayesian graph convolutional neural networks for semi-supervised classificationcited by 88
  11. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  12. 2018MotifNet: a motif-based Graph Convolutional Network for directed graphscited by 63
  13. 2019Community Detection on Networks with Ricci Flowcited by 62
  14. 2020Network Geometrycited by 31
  15. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  16. 2018Network Alignment by Discrete Ollivier-Ricci Flowcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 67; 2023: 102; 2024: 114; 2025: 110; 2026: 78.

471 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  3. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 190
  4. 2023Exphormer: Sparse Transformers for Graphscited by 166
  5. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  6. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  7. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  8. 2024Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spacescited by 132
  9. 2022Graph-Coupled Oscillator Networkscited by 123
  10. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  11. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  12. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
38 more
  1. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  2. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  3. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  4. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
  5. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 88
  6. 2024Transformers need glasses! Information over-squashing in language taskscited by 87
  7. 2024Position: Graph Foundation Models are Already Herecited by 84
  8. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  9. 2023Attending to Graph Transformerscited by 81
  10. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  11. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  12. 2022Expander Graph Propagationcited by 75
  13. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  14. 2022A Survey on Graph Representation Learning Methodscited by 66
  15. 2024Position: Topological Deep Learning is the New Frontier for Relational Learningcited by 65
  16. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 63
  17. 2022Graph Data Augmentation for Graph Machine Learning: A Surveycited by 61
  18. 2023On the Connection Between MPNN and Graph Transformercited by 60
  19. 2023Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunitiescited by 60
  20. 2022Understanding convolution on graphs via energiescited by 58
  21. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 58
  22. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  23. 2023How does over-squashing affect the power of GNNs?cited by 53
  24. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  25. 2022Gradient Gating for Deep Multi-Rate Learning on Graphscited by 49
  26. 2022Message passing all the way upcited by 47
  27. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  28. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  29. 2025Hallucination Detection in LLMs Using Spectral Features of Attention Mapscited by 42
  30. 2022Hyperbolic Graph Neural Networks: A Review of Methods and Applicationscited by 40
  31. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  32. 2024A Comprehensive Survey on Data Augmentationcited by 38
  33. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  34. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 35
  35. 2023Cooperative Graph Neural Networkscited by 35
  36. 2024VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connectionscited by 34
  37. 2022Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashingcited by 31
  38. 2023Graph Positional and Structural Encodercited by 31

50 most cited of 471 All 471 (JSON)