mlsanityData to 14 Oct 2026

Oversquashing in GNNs through the lens of information contraction and graph expansion

arXiv 2208.03471 ↗First posted 6 Aug 2022cs.LG cs.IT math.ITcited by 53

Not on the map. Why?

Abstract (arXiv)

The quality of signal propagation in message-passing graph neural networks (GNNs) strongly influences their expressivity as has been observed in recent works. In particular, for prediction tasks relying on long-range interactions, recursive aggregation of node features can lead to an undesired phenomenon called "oversquashing". We present a framework for analyzing oversquashing based on information contraction. Our analysis is guided by a model of reliable computation due to von Neumann that lends a new insight into oversquashing as signal quenching in noisy computation graphs. Building on this, we propose a graph rewiring algorithm aimed at alleviating oversquashing. Our algorithm employs a random local edge flip primitive motivated by an expander graph construction. We compare the spectral expansion properties of our algorithm with that of an existing curvature-based non-local rewiring strategy. Synthetic experiments show that while our algorithm in general has a slower rate of expansion, it is overall computationally cheaper, preserves the node degrees exactly and never disconnects the graph.

Key facts. Cited by 53 papers in the map (data through 14 Oct 2026). Builds on 18 of its 62 references that are in the map. First posted on arXiv 6 Aug 2022.

Builds on

18 of 62 references.

References · 18

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  7. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  8. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  9. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  11. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  12. 2019Diffusion Improves Graph Learningcited by 414
6 more
  1. 2022Long Range Graph Benchmarkcited by 263
  2. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  3. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 131
  4. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  5. 2015Expanders via Local Edge Flipscited by 3
  6. 2017The flip Markov chain for connected regular graphscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 15; 2024: 14; 2025: 13; 2026: 7.

53 papers.

Sort:

By area:

  1. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  2. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  3. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 98
  4. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  5. 2022Expander Graph Propagationcited by 75
  6. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  7. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 41
  8. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  9. 2023Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreachingcited by 24
  10. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 24
  11. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  12. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
38 more
  1. 2023Neurosymbolic AI for Reasoning over Knowledge Graphs: A Surveycited by 21
  2. 2024Cayley Graph Propagationcited by 21
  3. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 19
  4. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  5. 2025GNNs Getting ComFy: Community and Feature Similarity Guided Rewiringcited by 13
  6. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  7. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  8. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  9. 2024Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 8
  10. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 7
  11. 2023The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structurecited by 6
  12. 2024Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networkscited by 6
  13. 2024Deep Equilibrium Algorithmic Reasoningcited by 6
  14. 2025PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networkscited by 6
  15. 2024Graph Unitary Message Passingcited by 5
  16. 2023Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistancecited by 4
  17. 2023Higher-Order Expander Graph Propagationcited by 4
  18. 2025Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networkscited by 4
  19. 2023Framelet Message Passingcited by 3
  20. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  21. 2024When Graph Neural Networks Meet Dynamic Mode Decompositioncited by 3
  22. 2025Short-Range Oversquashingcited by 3
  23. 2023An Empirical Evaluation of Rewiring Approaches in Graph Neural Networkscited by 2
  24. 2024Differentiable Cluster Graph Neural Networkcited by 2
  25. 2025Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passingcited by 2
  26. 2023Over-Squashing in Riemannian Graph Neural Networkscited by 1
  27. 2024Conditional Shift-Robust Conformal Prediction for Graph Neural Networkcited by 1
  28. 2025Effects of Dropout on Performance in Long-range Graph Learning Taskscited by 1
  29. 2025Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networkscited by 1
  30. 2024Introduction to Graph Neural Networks for Machine Learning Engineerscited by 0
  31. 2025Schreier-Coset Graph Propagationcited by 0
  32. 2025GraphTorque: Torque-Driven Rewiring Graph Neural Networkcited by 0
  33. 2025Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networkscited by 0
  34. 2025Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)cited by 0
  35. 2026Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 0
  36. 2026Bilevel Graph Structure Learning, Revisited: Inner-Channel Origins of the Reported Gaincited by 0
  37. 2026Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observablescited by 0
  38. 2026S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learningcited by 0

50 most cited of 53 All 53 (JSON)