mlsanityData to 7 Oct 2026

On the Bottleneck of Graph Neural Networks and its Practical Implications

arXiv 2006.05205 ↗First posted 9 Jun 2020cs.LG stat.MLcited by 624

Not on the map. Why?

Abstract (arXiv)

Since the proposal of the graph neural network (GNN) by Gori et al. (2005) and Scarselli et al. (2008), one of the major problems in training GNNs was their struggle to propagate information between distant nodes in the graph. We propose a new explanation for this problem: GNNs are susceptible to a bottleneck when aggregating messages across a long path. This bottleneck causes the over-squashing of exponentially growing information into fixed-size vectors. As a result, GNNs fail to propagate messages originating from distant nodes and perform poorly when the prediction task depends on long-range interaction. In this paper, we highlight the inherent problem of over-squashing in GNNs: we demonstrate that the bottleneck hinders popular GNNs from fitting long-range signals in the training data; we further show that GNNs that absorb incoming edges equally, such as GCN and GIN, are more susceptible to over-squashing than GAT and GGNN; finally, we show that prior work, which extensively tuned GNN models of long-range problems, suffers from over-squashing, and that breaking the bottleneck improves their state-of-the-art results without any tuning or additional weights. Our code is available at https://github.com/tech-srl/bottleneck/ .

Key facts. Cited by 624 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 43; 2022: 96; 2023: 129; 2024: 130; 2025: 123; 2026: 103.

624 papers.

Sort:

By area:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  2. 2021How Attentive are Graph Attention Networks?cited by 818
  3. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  4. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  5. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  6. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  7. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  8. 2021GRAND: Graph Neural Diffusioncited by 258
  9. 2022Long Range Graph Benchmarkcited by 258
  10. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  11. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  12. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 207
38 more
  1. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  2. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  3. 2022Graph neural networks for materials science and chemistrycited by 181
  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. 2023Do We Really Need Complicated Model Architectures For Temporal Networks?cited by 141
  8. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  9. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  10. 2024Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spacescited by 132
  11. 2023GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learnercited by 131
  12. 2022Graph-Coupled Oscillator Networkscited by 123
  13. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  14. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  15. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  16. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  17. 2023Graph Foundation Models: Concepts, Opportunities and Challengescited by 101
  18. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  19. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  20. 2022Decoupling the Depth and Scope of Graph Neural Networkscited by 94
  21. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  22. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  23. 2021Parameter Prediction for Unseen Deep Architecturescited by 89
  24. 2023On the Expressive Power of Geometric Graph Neural Networkscited by 89
  25. 2024Transformers need glasses! Information over-squashing in language taskscited by 87
  26. 2023Everything is Connected: Graph Neural Networkscited by 85
  27. 2021Beltrami Flow and Neural Diffusion on Graphscited by 84
  28. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 84
  29. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 83
  30. 2023Attending to Graph Transformerscited by 81
  31. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  32. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  33. 2022Expander Graph Propagationcited by 75
  34. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  35. 2022MolGenSurvey: A Systematic Survey in Machine Learning Models for Molecule Designcited by 66
  36. 2022A Survey on Graph Representation Learning Methodscited by 66
  37. 2024Polynormer: Polynomial-Expressive Graph Transformer in Linear Timecited by 64
  38. 2021Gophormer: Ego-Graph Transformer for Node Classificationcited by 63

50 most cited of 624 All 624 (JSON)