mlsanityData to 14 Oct 2026

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

arXiv 2312.16560 ↗First posted 27 Dec 2023cs.LGcited by 24

Not on the map. Why?

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.

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

71 of 108 references.

References · 71

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2018How Powerful are Graph Neural Networks?cited by 4,393
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  8. 2016Variational Inference: A Review for Statisticianscited by 1,472
  9. 2017Deep Setscited by 1,421
  10. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  11. 2019Strategies for Pre-training Graph Neural Networkscited by 971
  12. 2020Learning to Simulate Complex Physics with Graph Networkscited by 880
38 more
  1. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  2. 2020Simple and Deep Graph Convolutional Networkscited by 860
  3. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  4. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  5. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  6. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  7. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  8. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  9. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  10. 2019Diffusion Improves Graph Learningcited by 414
  11. 2017Residual Gated Graph ConvNetscited by 346
  12. 2020SIGN: Scalable Inception Graph Neural Networkscited by 284
  13. 2022Long Range Graph Benchmarkcited by 263
  14. 2021GRAND: Graph Neural Diffusioncited by 258
  15. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
  16. 2019Learning Discrete Structures for Graph Neural Networkscited by 231
  17. 2020Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddingscited by 214
  18. 2020Data Augmentation for Graph Neural Networkscited by 203
  19. 2022Structure-Aware Transformer for Graph Representation Learningcited by 194
  20. 2023Exphormer: Sparse Transformers for Graphscited by 170
  21. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  22. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  23. 2022Graph-Coupled Oscillator Networkscited by 124
  24. 2019A Gentle Introduction to Deep Learning for Graphscited by 108
  25. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  26. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  27. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  28. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 85
  29. 2023Attending to Graph Transformerscited by 83
  30. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  31. 2020Bayesian Graph Neural Networks with Adaptive Connection Samplingcited by 81
  32. 2019GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulationcited by 75
  33. 2022Expander Graph Propagationcited by 75
  34. 2019Auto-GNN: Neural Architecture Search of Graph Neural Networkscited by 74
  35. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 60
  36. 2019Graph-Revised Convolutional Networkcited by 59
  37. 2021Dissecting the Diffusion Process in Linear Graph Convolutional Networkscited by 58
  38. 2023Locality-Aware Graph-Rewiring in GNNscited by 56

50 most cited of 71 All 71 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 11; 2026: 8.

24 papers.

Sort:

By area:

  1. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 86
  2. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 19
  3. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  4. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  5. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  6. 2025Can You Hear Me Now? A Benchmark for Long-Range Graph Propagationcited by 10
  7. 2025Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvaturecited by 8
  8. 2025PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networkscited by 6
  9. 2024GATE: How to Keep Out Intrusive Neighborscited by 5
  10. 2025ADMP-GNN: Adaptive Depth Message Passing GNNcited by 3
  11. 2025Fast, Modular, and Differentiable Framework for Machine Learning-Enhanced Molecular Simulationscited by 2
  12. 2025Early-Exit Graph Neural Networkscited by 2
12 more
  1. 2025Variational Kolmogorov-Arnold Networkcited by 1
  2. 2025gLSTM: Mitigating Over-Squashing by Increasing Storage Capacitycited by 1
  3. 2025Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulationscited by 1
  4. 2024Information propagation dynamics in Deep Graph Networkscited by 0
  5. 2026Graph Hierarchical Recurrence for Long-Range Generalizationcited by 0
  6. 2026Learn When and Where to Connect: Adaptive Virtual Nodes for Dynamic Message Passing on Graphscited by 0
  7. 2026Continuous-Time Quantum Walks based Graph Neural Networkcited by 0
  8. 2026Reachability is not enough: Diagnosing long-range behavior in GNNscited by 0
  9. 2026Learning Propagation Geometry from Message-Passing Feedbackcited by 0
  10. 2026Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Networkcited by 0
  11. 2026Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspectivecited by 0
  12. 2026Oscillatory Neural Dynamics over Sheavescited by 0