mlsanityData to 14 Oct 2026

Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey

arXiv 2411.17429 ↗First posted 26 Nov 2024cs.LG cs.AIcited by 8

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks are powerful models for learning from graph-structured data, yet their effectiveness is often limited by two critical challenges: over-squashing, where information from distant nodes is excessively compressed, and over-smoothing, where repeated propagation makes node representations indistinguishable. Both phenomena stem from the interaction between message passing and the input topology, ultimately degrading information flow and limiting the performance of GNNs. In this survey, we examine graph rewiring techniques, a class of methods designed to modify the graph topology to enhance information propagation in GNNs. We provide a comprehensive review of state-of-the-art rewiring approaches, delving into their theoretical underpinnings, practical implementations, and performance trade-offs.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 33 of its 60 references that are in the map. First posted on arXiv 26 Nov 2024.

Builds on

33 of 60 references.

References · 33

  1. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  2. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  3. 2017Deep Setscited by 1,421
  4. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  5. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  7. 2019Diffusion Improves Graph Learningcited by 414
  8. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  9. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  10. 2022Long Range Graph Benchmarkcited by 263
  11. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 249
  12. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
21 more
  1. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  2. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  3. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  4. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 98
  5. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  6. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  7. 2022Expander Graph Propagationcited by 75
  8. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 64
  9. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  10. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 53
  11. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 41
  12. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 40
  13. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  14. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 24
  15. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  16. 2024Cayley Graph Propagationcited by 21
  17. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  18. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  19. 2024A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directionscited by 13
  20. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  21. 2024The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisitedcited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 3.

8 papers.

  1. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 19
  2. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  3. 2025Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networkscited by 4
  4. 2025It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graphcited by 0
  5. 2025A Remedy for Over-Squashing in Graph Learning via Forman-Ricci Curvature based Graph-to-Hypergraph Structural Liftingcited by 0
  6. 2026Exploring the impact of adaptive rewiring in Graph Neural Networkscited by 0
  7. 2026Ramanujan Graph Rewiring with Non Negative Resistance Curvaturecited by 0
  8. 2026Omega-N: Interpretable Structural Node Descriptors and Their Applicability Domaincited by 0