mlsanityData to 7 Oct 2026

Understanding Oversquashing in GNNs through the Lens of Effective Resistance

arXiv 2302.06835 ↗First posted 14 Feb 2023cs.LGcited by 94

Not on the map. Why?

Abstract (arXiv)

Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the effective resistance between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use total effective resistance as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.

Key facts. Cited by 94 papers in the map (data through 7 Oct 2026). Builds on 19 of its 38 references that are in the map. First posted on arXiv 14 Feb 2023.

Builds on

19 of 38 references.

References · 19

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  5. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  6. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  7. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  8. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  9. 2019Diffusion Improves Graph Learningcited by 414
  10. 2022Long Range Graph Benchmarkcited by 258
  11. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
  12. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
7 more
  1. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  2. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  3. 2022Expander Graph Propagationcited by 75
  4. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  5. 2020Persistent Laplacians: properties, algorithms and implicationscited by 28
  6. 2017Graph Clustering using Effective Resistancecited by 12
  7. 2020Ultrasparse Ultrasparsifiers and Faster Laplacian System Solverscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 14; 2024: 27; 2025: 34; 2026: 19.

94 papers.

Sort:

  1. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  2. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  3. 2023How does over-squashing affect the power of GNNs?cited by 53
  4. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  5. 2025Hallucination Detection in LLMs Using Spectral Features of Attention Mapscited by 42
  6. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  7. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  8. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 23
  9. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  10. 2024Cayley Graph Propagationcited by 21
  11. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  12. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
38 more
  1. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  2. 2024Bundle Neural Networks for message diffusion on graphscited by 13
  3. 2024Revisiting Random Walks for Learning on Graphscited by 13
  4. 2025Unified Spatial-Temporal Edge-Enhanced Graph Networks for Pedestrian Trajectory Predictioncited by 13
  5. 2025GNNs Getting ComFy: Community and Feature Similarity Guided Rewiringcited by 13
  6. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  7. 2024The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisitedcited by 11
  8. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 11
  9. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  10. 2025On Measuring Long-Range Interactions in Graph Neural Networkscited by 9
  11. 2024Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 8
  12. 2023FedGKD: Unleashing the Power of Collaboration in Federated Graph Neural Networkscited by 7
  13. 2023Non-backtracking Graph Neural Networkscited by 7
  14. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 7
  15. 2024Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networkscited by 6
  16. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 6
  17. 2024Graph Unitary Message Passingcited by 5
  18. 2025PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networkscited by 5
  19. 2023Structural Group Unfairness: Measurement and Mitigation by means of the Effective Resistancecited by 4
  20. 2023On the Two Sides of Redundancy in Graph Neural Networkscited by 4
  21. 2025Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networkscited by 4
  22. 2025Integrating Temporal and Structural Context in Graph Transformers for Relational Deep Learningcited by 4
  23. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  24. 2024GNN-SKAN: Harnessing the Power of SwallowKAN to Advance Molecular Representation Learning with GNNscited by 3
  25. 2025Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNscited by 3
  26. 2023An Empirical Evaluation of Rewiring Approaches in Graph Neural Networkscited by 2
  27. 2023Can strong structural encoding reduce the importance of Message Passing?cited by 2
  28. 2024Differentiable Cluster Graph Neural Networkcited by 2
  29. 2024Scalable Graph Compressed Convolutionscited by 2
  30. 2024When Graph Neural Networks Meet Dynamic Mode Decompositioncited by 2
  31. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  32. 2025Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passingcited by 2
  33. 2025Refined Causal Graph Structure Learning via Curvature for Brain Disease Classificationcited by 2
  34. 2025Short-Range Oversquashingcited by 2
  35. 2023Over-Squashing in Riemannian Graph Neural Networkscited by 1
  36. 2024Conditional Shift-Robust Conformal Prediction for Graph Neural Networkcited by 1
  37. 2024Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attentioncited by 1
  38. 2024Accelerating Flood Warnings by 10 Hours: The Power of River Network Topology in AI-enhanced Flood Forecastingcited by 1

50 most cited of 94 All 94 (JSON)