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

arXiv: https://arxiv.org/abs/2505.15547 · HTML: https://mlsanity.com/paper/2505.15547/

## 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 (most cited first, 30 of 83)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [Graph-Coupled Oscillator Networks](https://mlsanity.com/paper/2202.02296/) (2022)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Artificial Intelligence for Science in Quantum, Atomistic, and Continuum Systems](https://mlsanity.com/paper/2307.08423/) (2023)
- [Towards Deeper Graph Neural Networks with Differentiable Group Normalization](https://mlsanity.com/paper/2006.06972/) (2020)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)

## Built on by (most cited first, 19 of 19)

- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [On Measuring Long-Range Interactions in Graph Neural Networks](https://mlsanity.com/paper/2506.05971/) (2025)
- [Short-Range Oversquashing](https://mlsanity.com/paper/2511.20406/) (2025)
- [Early-Exit Graph Neural Networks](https://mlsanity.com/paper/2505.18088/) (2025)
- [Hierarchical Message-Passing Policies for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2507.23604/) (2025)
- [Position: Don't be Afraid of Over-Smoothing And Over-Squashing](https://mlsanity.com/paper/2601.07419/) (2026)
- [gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity](https://mlsanity.com/paper/2510.08450/) (2025)
- [From Message-Passing to Linearized Graph Sequence Models](https://mlsanity.com/paper/2605.12358/) (2026)
- [Probing Graph Neural Network Activation Patterns Through Graph Topology](https://mlsanity.com/paper/2602.21092/) (2026)
- [Local Message-Passing for Discrete Graph Generation](https://mlsanity.com/paper/2603.08825/) (2026)
- [Can Graph Foundation Models Generalize Over Architecture?](https://mlsanity.com/paper/2603.22984/) (2026)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2605.00951/) (2026)
- [S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning](https://mlsanity.com/paper/2605.23467/) (2026)
- [Applications of temporal graph learning for predicting the dynamics of biological systems](https://mlsanity.com/paper/2605.28659/) (2026)
- [Ramanujan Graph Rewiring with Non Negative Resistance Curvature](https://mlsanity.com/paper/2606.21333/) (2026)
- [Schreier-Coset Graph Rewiring](https://mlsanity.com/paper/2607.27479/) (2026)
- [Graph Machine Learning: An Opportunity for Power Systems](https://mlsanity.com/paper/2608.16494/) (2026)
- [Reachability is not enough: Diagnosing long-range behavior in GNNs](https://mlsanity.com/paper/2609.33674/) (2026)
- [Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing](https://mlsanity.com/paper/2610.03556/) (2026)

## 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.