# How does over-squashing affect the power of GNNs?

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 71 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Builds on (most cited first, 30 of 49)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [E(3)-Equivariant Graph Neural Networks for Data-Efficient and Accurate Interatomic Potentials](https://mlsanity.com/paper/2101.03164/) (2021)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Message Passing Neural PDE Solvers](https://mlsanity.com/paper/2202.03376/) (2022)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [GemNet: Universal Directional Graph Neural Networks for Molecules](https://mlsanity.com/paper/2106.08903/) (2021)
- [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)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [ETA Prediction with Graph Neural Networks in Google Maps](https://mlsanity.com/paper/2108.11482/) (2021)

## Built on by (most cited first, 30 of 53)

- [Transformers need glasses! Information over-squashing in language tasks](https://mlsanity.com/paper/2406.04267/) (2024)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [A Hitchhiker's Guide to Geometric GNNs for 3D Atomic Systems](https://mlsanity.com/paper/2312.07511/) (2023)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Understanding Virtual Nodes: Oversquashing and Node Heterogeneity](https://mlsanity.com/paper/2405.13526/) (2024)
- [Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond](https://mlsanity.com/paper/2309.02769/) (2023)
- [Towards Neural Scaling Laws on Graphs](https://mlsanity.com/paper/2402.02054/) (2024)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Even Sparser Graph Transformers](https://mlsanity.com/paper/2411.16278/) (2024)
- [Towards Dynamic Message Passing on Graphs](https://mlsanity.com/paper/2410.23686/) (2024)
- [On Measuring Long-Range Interactions in Graph Neural Networks](https://mlsanity.com/paper/2506.05971/) (2025)
- [TxPert: Leveraging Biochemical Relationships for Out-of-Distribution Transcriptomic Perturbation Prediction](https://mlsanity.com/paper/2505.14919/) (2025)
- [Graph Reinforcement Learning for Power Grids: A Comprehensive Survey](https://mlsanity.com/paper/2407.04522/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Deep Equilibrium Algorithmic Reasoning](https://mlsanity.com/paper/2410.15059/) (2024)
- [Over-squashing in Spatiotemporal Graph Neural Networks](https://mlsanity.com/paper/2506.15507/) (2025)
- [What makes a good feedforward computational graph?](https://mlsanity.com/paper/2502.06751/) (2025)
- [Higher-Order Expander Graph Propagation](https://mlsanity.com/paper/2311.07966/) (2023)
- [A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition](https://mlsanity.com/paper/2405.13806/) (2024)
- [Temporal Graph Rewiring with Expander Graphs](https://mlsanity.com/paper/2406.02362/) (2024)
- [Commute-Time-Optimised Graphs for GNNs](https://mlsanity.com/paper/2407.08762/) (2024)
- [Simplifying the Theory on Over-Smoothing](https://mlsanity.com/paper/2407.11876/) (2024)
- [Stuart-Landau Oscillatory Graph Neural Network](https://mlsanity.com/paper/2511.08094/) (2025)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)
- [Photonics-Enhanced Graph Convolutional Networks](https://mlsanity.com/paper/2512.15549/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. The most popular class of GNNs operate by exchanging information between adjacent nodes, and are known as Message Passing Neural Networks (MPNNs). Given their widespread use, understanding the expressive power of MPNNs is a key question. However, existing results typically consider settings with uninformative node features. In this paper, we provide a rigorous analysis to determine which function classes of node features can be learned by an MPNN of a given capacity. We do so by measuring the level of pairwise interactions between nodes that MPNNs allow for. This measure provides a novel quantitative characterization of the so-called over-squashing effect, which is observed to occur when a large volume of messages is aggregated into fixed-size vectors. Using our measure, we prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough, depending on properties of the input graph structure, such as commute times. For many relevant scenarios, our analysis results in impossibility statements in practice, showing that over-squashing hinders the expressive power of MPNNs. We validate our theoretical findings through extensive controlled experiments and ablation studies.