# Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 71 of its 108 references that are in the map.
- First posted on arXiv 27 Dec 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [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)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [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)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [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)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)

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

- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [PANDA: Expanded Width-Aware Message Passing Beyond Rewiring](https://mlsanity.com/paper/2406.03671/) (2024)
- [Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation](https://mlsanity.com/paper/2512.17762/) (2025)
- [Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvature](https://mlsanity.com/paper/2503.01079/) (2025)
- [PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networks](https://mlsanity.com/paper/2504.04052/) (2025)
- [GATE: How to Keep Out Intrusive Neighbors](https://mlsanity.com/paper/2406.00418/) (2024)
- [ADMP-GNN: Adaptive Depth Message Passing GNN](https://mlsanity.com/paper/2509.01170/) (2025)
- [Fast, Modular, and Differentiable Framework for Machine Learning-Enhanced Molecular Simulations](https://mlsanity.com/paper/2503.20541/) (2025)
- [Early-Exit Graph Neural Networks](https://mlsanity.com/paper/2505.18088/) (2025)
- [Variational Kolmogorov-Arnold Network](https://mlsanity.com/paper/2507.02466/) (2025)
- [gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity](https://mlsanity.com/paper/2510.08450/) (2025)
- [Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulations](https://mlsanity.com/paper/2511.12709/) (2025)
- [Information propagation dynamics in Deep Graph Networks](https://mlsanity.com/paper/2410.10464/) (2024)
- [Graph Hierarchical Recurrence for Long-Range Generalization](https://mlsanity.com/paper/2605.18387/) (2026)
- [Learn When and Where to Connect: Adaptive Virtual Nodes for Dynamic Message Passing on Graphs](https://mlsanity.com/paper/2606.03068/) (2026)
- [Continuous-Time Quantum Walks based Graph Neural Network](https://mlsanity.com/paper/2608.20738/) (2026)
- [Reachability is not enough: Diagnosing long-range behavior in GNNs](https://mlsanity.com/paper/2609.33674/) (2026)
- [Learning Propagation Geometry from Message-Passing Feedback](https://mlsanity.com/paper/2609.34711/) (2026)
- [Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network](https://mlsanity.com/paper/2609.34904/) (2026)
- [Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective](https://mlsanity.com/paper/2610.04157/) (2026)
- [Oscillatory Neural Dynamics over Sheaves](https://mlsanity.com/paper/2610.10018/) (2026)

## Abstract (arXiv)

Long-range interactions are essential for the correct description of complex systems in many scientific fields. The price to pay for including them in the calculations, however, is a dramatic increase in the overall computational costs. Recently, deep graph networks have been employed as efficient, data-driven models for predicting properties of complex systems represented as graphs. These models rely on a message passing strategy that should, in principle, capture long-range information without explicitly modeling the corresponding interactions. In practice, most deep graph networks cannot really model long-range dependencies due to the intrinsic limitations of (synchronous) message passing, namely oversmoothing, oversquashing, and underreaching. This work proposes a general framework that learns to mitigate these limitations: within a variational inference framework, we endow message passing architectures with the ability to adapt their depth and filter messages along the way. With theoretical and empirical arguments, we show that this strategy better captures long-range interactions, by competing with the state of the art on five node and graph prediction datasets.