mlsanityData to 7 Oct 2026

PANDA: Expanded Width-Aware Message Passing Beyond Rewiring

arXiv 2406.03671 ↗First posted 6 Jun 2024cs.LG cs.AIcited by 10

Not on the map. Why?

Abstract (arXiv)

Recent research in the field of graph neural network (GNN) has identified a critical issue known as "over-squashing," resulting from the bottleneck phenomenon in graph structures, which impedes the propagation of long-range information. Prior works have proposed a variety of graph rewiring concepts that aim at optimizing the spatial or spectral properties of graphs to promote the signal propagation. However, such approaches inevitably deteriorate the original graph topology, which may lead to a distortion of information flow. To address this, we introduce an expanded width-aware (PANDA) message passing, a new message passing paradigm where nodes with high centrality, a potential source of over-squashing, are selectively expanded in width to encapsulate the growing influx of signals from distant nodes. Experimental results show that our method outperforms existing rewiring methods, suggesting that selectively expanding the hidden state of nodes can be a compelling alternative to graph rewiring for addressing the over-squashing.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 41 of its 56 references that are in the map. First posted on arXiv 6 Jun 2024.

Builds on

41 of 56 references.

References · 41

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  5. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  6. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  7. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  8. 2020Simple and Deep Graph Convolutional Networkscited by 857
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  11. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  12. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
29 more
  1. 2019Diffusion Improves Graph Learningcited by 414
  2. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  3. 2022Long Range Graph Benchmarkcited by 258
  4. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  5. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  6. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  7. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  8. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 88
  9. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 84
  10. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  11. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  12. 2019GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulationcited by 75
  13. 2022Expander Graph Propagationcited by 75
  14. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 63
  15. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  16. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  17. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  18. 2023Cooperative Graph Neural Networkscited by 35
  19. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  20. 2023Reversible and irreversible bracket-based dynamics for deep graph neural networkscited by 25
  21. 2023Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreachingcited by 23
  22. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  23. 2021LT-OCF: Learnable-Time ODE-based Collaborative Filteringcited by 21
  24. 2021Climate Modeling with Neural Diffusion Equationscited by 20
  25. 2023Graph Neural Rough Differential Equations for Traffic Forecastingcited by 14
  26. 2023How Curvature Enhance the Adaptation Power of Framelet GCNscited by 13
  27. 2023Node Embedding from Neural Hamiltonian Orbits in Graph Neural Networkscited by 12
  28. 2023Non-backtracking Graph Neural Networkscited by 7
  29. 2024Graph Unitary Message Passingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 4.

10 papers.

  1. 2024Cayley Graph Propagationcited by 21
  2. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 6
  3. 2025PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networkscited by 5
  4. 2025Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNscited by 3
  5. 2025Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networkscited by 1
  6. 2025Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networkscited by 0
  7. 2026S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learningcited by 0
  8. 2026Ramanujan Graph Rewiring with Non Negative Resistance Curvaturecited by 0
  9. 2026Schreier-Coset Graph Rewiringcited by 0
  10. 2026LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNNcited by 0