mlsanityData to 7 Oct 2026

On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems

arXiv 2405.01009 ↗First posted 2 May 2024cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

A common problem in Message-Passing Neural Networks is oversquashing -- the limited ability to facilitate effective information flow between distant nodes. Oversquashing is attributed to the exponential decay in information transmission as node distances increase. This paper introduces a novel perspective to address oversquashing, leveraging dynamical systems properties of global and local non-dissipativity, that enable the maintenance of a constant information flow rate. We present SWAN, a uniquely parameterized GNN model with antisymmetry both in space and weight domains, as a means to obtain non-dissipativity. Our theoretical analysis asserts that by implementing these properties, SWAN offers an enhanced ability to transmit information over extended distances. Empirical evaluations on synthetic and real-world benchmarks that emphasize long-range interactions validate the theoretical understanding of SWAN, and its ability to mitigate oversquashing.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 41 of its 57 references that are in the map. First posted on arXiv 2 May 2024.

Builds on

41 of 57 references.

References · 41

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2018Neural Ordinary Differential Equationscited by 3,733
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  8. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  9. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  10. 2019Strategies for Pre-training Graph Neural Networkscited by 964
  11. 2020Simple and Deep Graph Convolutional Networkscited by 857
  12. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
29 more
  1. 2020A Generalization of Transformer Networks to Graphscited by 653
  2. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  3. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  4. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  5. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  6. 2019Diffusion Improves Graph Learningcited by 414
  7. 2017Residual Gated Graph ConvNetscited by 341
  8. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  9. 2021GRAND: Graph Neural Diffusioncited by 258
  10. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
  11. 2018Deep Neural Networks Motivated by Partial Differential Equationscited by 187
  12. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  13. 2019Graph Neural Ordinary Differential Equationscited by 153
  14. 2019Continuous Graph Neural Networkscited by 114
  15. 2021PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equationscited by 106
  16. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  17. 2021Beltrami Flow and Neural Diffusion on Graphscited by 84
  18. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  19. 2023On the Connection Between MPNN and Graph Transformercited by 60
  20. 2021Dissecting the Diffusion Process in Linear Graph Convolutional Networkscited by 58
  21. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 58
  22. 2022GREAD: Graph Neural Reaction-Diffusion Networkscited by 54
  23. 2021From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformerscited by 38
  24. 2023From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyondcited by 26
  25. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  26. 2024Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FRONDcited by 16
  27. 2022Capturing Graphs with Hypo-Elliptic Diffusionscited by 12
  28. 2024Temporal Graph ODEs for Irregularly-Sampled Time Seriescited by 11
  29. 2023QDC: Quantum Diffusion Convolution Kernels on Graphscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 16; 2026: 8.

26 papers.

Sort:

  1. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  2. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  3. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  4. 2025Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modelingcited by 9
  5. 2025Can You Hear Me Now? A Benchmark for Long-Range Graph Propagationcited by 8
  6. 2025Over-squashing in Spatiotemporal Graph Neural Networkscited by 6
  7. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 6
  8. 2025Improving Long-Range Interactions in Graph Neural Simulators via Hamiltonian Dynamicscited by 6
  9. 2026FairGE: Fairness-Aware Graph Encoding in Incomplete Social Networkscited by 4
  10. 2024Interpreting Temporal Graph Neural Networks with Koopman Theorycited by 2
  11. 2025Early-Exit Graph Neural Networkscited by 2
  12. 2026Stochastic Parroting in Temporal Attention -- Regulating the Diagonal Sinkcited by 2
14 more
  1. 2025Wavy Transformercited by 1
  2. 2025gLSTM: Mitigating Over-Squashing by Increasing Storage Capacitycited by 1
  3. 2026From Message-Passing to Linearized Graph Sequence Modelscited by 1
  4. 2024Information propagation dynamics in Deep Graph Networkscited by 0
  5. 2025TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flowscited by 0
  6. 2025Non-Dissipative Graph Propagation for Non-Local Community Detectioncited by 0
  7. 2025Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networkscited by 0
  8. 2025Model Metamers Reveal Invariances in Graph Neural Networkscited by 0
  9. 2025How Wide and How Deep? Mitigating Over-Squashing of GNNs via Channel Capacity Constrained Estimationcited by 0
  10. 2026Geometry-Induced Diffusion on Graphs: A Learnable Weighted Laplacian for Spectral GNNscited by 0
  11. 2026Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observablescited by 0
  12. 2026Graph Hierarchical Recurrence for Long-Range Generalizationcited by 0
  13. 2026Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformerscited by 0
  14. 2026TwinS-GCN: Spectral conjugate for Spectral Graph Convolutional Networkscited by 0