mlsanityData to 14 Oct 2026

Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning

arXiv 2505.15547 ↗First posted 21 May 2025cs.LG cs.AIcited by 19

Not on the map. Why?

Abstract (arXiv)

After a renaissance phase in which researchers revisited the message-passing paradigm through the lens of deep learning, the graph machine learning community shifted its attention towards a deeper and practical understanding of message-passing's benefits and limitations. In this paper, we notice how the fast pace of progress around the topics of oversmoothing and oversquashing, the homophily-heterophily dichotomy, and long-range tasks, came with the consolidation of commonly accepted beliefs and assumptions -- under the form of universal statements -- that are not always true nor easy to distinguish from each other. We argue that this has led to ambiguities around the investigated problems, preventing researchers from focusing on and addressing precise research questions while causing a good amount of misunderstandings. Our contribution is to make such common beliefs explicit and encourage critical thinking around these topics, refuting universal statements via simple yet formally sufficient counterexamples. The end goal is to clarify conceptual differences, helping researchers address more clearly defined and targeted problems.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 83 of its 123 references that are in the map. First posted on arXiv 21 May 2025.

Builds on

83 of 123 references.

References · 83

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  5. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  6. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  7. 2020Simple and Deep Graph Convolutional Networkscited by 860
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  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. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 545
  12. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
38 more
  1. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  2. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  3. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  4. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  5. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  6. 2020Towards Deeper Graph Neural Networkscited by 296
  7. 2022Long Range Graph Benchmarkcited by 263
  8. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 249
  9. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
  10. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
  11. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  12. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  13. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  14. 2022Graph-Coupled Oscillator Networkscited by 124
  15. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  16. 2023Artificial Intelligence for Science in Quantum, Atomistic, and Continuum Systemscited by 121
  17. 2020Towards Deeper Graph Neural Networks with Differentiable Group Normalizationcited by 114
  18. 2019A Gentle Introduction to Deep Learning for Graphscited by 108
  19. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  20. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  21. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 98
  22. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  23. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  24. 2021Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?cited by 82
  25. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  26. 2020Bayesian Graph Neural Networks with Adaptive Connection Samplingcited by 81
  27. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  28. 2022Expander Graph Propagationcited by 75
  29. 2020Tackling Over-Smoothing for General Graph Convolutional Networkscited by 66
  30. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 64
  31. 2023On the Connection Between MPNN and Graph Transformercited by 61
  32. 2023Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunitiescited by 61
  33. 2022Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyondcited by 60
  34. 2022Understanding convolution on graphs via energiescited by 59
  35. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  36. 2022Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminatingcited by 57
  37. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  38. 2020Revisiting Over-smoothing in Deep GCNscited by 55

50 most cited of 83 All 83 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 6; 2026: 13.

19 papers.

Sort:

  1. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  2. 2025On Measuring Long-Range Interactions in Graph Neural Networkscited by 11
  3. 2025Short-Range Oversquashingcited by 3
  4. 2025Early-Exit Graph Neural Networkscited by 2
  5. 2025Hierarchical Message-Passing Policies for Multi-Agent Reinforcement Learningcited by 2
  6. 2026Position: Don't be Afraid of Over-Smoothing And Over-Squashingcited by 2
  7. 2025gLSTM: Mitigating Over-Squashing by Increasing Storage Capacitycited by 1
  8. 2026From Message-Passing to Linearized Graph Sequence Modelscited by 1
  9. 2026Probing Graph Neural Network Activation Patterns Through Graph Topologycited by 0
  10. 2026Local Message-Passing for Discrete Graph Generationcited by 0
  11. 2026Can Graph Foundation Models Generalize Over Architecture?cited by 0
  12. 2026Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 0
7 more
  1. 2026S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learningcited by 0
  2. 2026Applications of temporal graph learning for predicting the dynamics of biological systemscited by 0
  3. 2026Ramanujan Graph Rewiring with Non Negative Resistance Curvaturecited by 0
  4. 2026Schreier-Coset Graph Rewiringcited by 0
  5. 2026Graph Machine Learning: An Opportunity for Power Systemscited by 0
  6. 2026Reachability is not enough: Diagnosing long-range behavior in GNNscited by 0
  7. 2026Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashingcited by 0