mlsanityData to 14 Oct 2026

DRew: Dynamically Rewired Message Passing with Delay

arXiv 2305.08018 ↗First posted 13 May 2023cs.LG cs.AI stat.MLcited by 82

Not on the map. Why?

Abstract (arXiv)

Message passing neural networks (MPNNs) have been shown to suffer from the phenomenon of over-squashing that causes poor performance for tasks relying on long-range interactions. This can be largely attributed to message passing only occurring locally, over a node's immediate neighbours. Rewiring approaches attempting to make graphs 'more connected', and supposedly better suited to long-range tasks, often lose the inductive bias provided by distance on the graph since they make distant nodes communicate instantly at every layer. In this paper we propose a framework, applicable to any MPNN architecture, that performs a layer-dependent rewiring to ensure gradual densification of the graph. We also propose a delay mechanism that permits skip connections between nodes depending on the layer and their mutual distance. We validate our approach on several long-range tasks and show that it outperforms graph Transformers and multi-hop MPNNs.

Key facts. Cited by 82 papers in the map (data through 14 Oct 2026). Builds on 48 of its 63 references that are in the map. First posted on arXiv 13 May 2023.

Builds on

48 of 63 references.

References · 48

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  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. 2018Neural Ordinary Differential Equationscited by 3,779
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  8. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  9. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,694
  10. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  11. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  12. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
36 more
  1. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  2. 2020Benchmarking Graph Neural Networkscited by 680
  3. 2020A Generalization of Transformer Networks to Graphscited by 661
  4. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  5. 2019Graph Transformer Networkscited by 523
  6. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  7. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  8. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  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. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  13. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 329
  14. 2022Long Range Graph Benchmarkcited by 263
  15. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 261
  16. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 249
  17. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  18. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
  19. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  20. 2021Nested Graph Neural Networkscited by 137
  21. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  22. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  23. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  24. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  25. 2019GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulationcited by 75
  26. 2022Expander Graph Propagationcited by 75
  27. 2019k-hop Graph Neural Networkscited by 57
  28. 2018N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classificationcited by 54
  29. 2022Gradient Gating for Deep Multi-Rate Learning on Graphscited by 49
  30. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  31. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 36
  32. 2021Neural Delay Differential Equationscited by 26
  33. 2021Persistent Message Passingcited by 13
  34. 2020Delay Differential Neural Networkscited by 5
  35. 2022Neural Piecewise-Constant Delay Differential Equationscited by 4
  36. 2022Asynchronous Neural Networks for Learning in Graphscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 14; 2024: 32; 2025: 21; 2026: 15.

82 papers.

Sort:

By area:

  1. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 86
  2. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 85
  3. 2023How does over-squashing affect the power of GNNs?cited by 53
  4. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 43
  5. 2023Cooperative Graph Neural Networkscited by 36
  6. 2023Graph Positional and Structural Encodercited by 33
  7. 2024On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systemscited by 28
  8. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  9. 2025Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellencecited by 26
  10. 2023Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreachingcited by 24
  11. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 24
  12. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
38 more
  1. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  2. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 19
  3. 2024Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FRONDcited by 17
  4. 2023Enhancing Graph Transformers with Hierarchical Distance Structural Encodingcited by 16
  5. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  6. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  7. 2024Bundle Neural Networks for message diffusion on graphscited by 14
  8. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  9. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  10. 2023Recurrent Distance Filtering for Graph Representation Learningcited by 11
  11. 2024The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisitedcited by 11
  12. 2024Towards Dynamic Message Passing on Graphscited by 11
  13. 2025On Measuring Long-Range Interactions in Graph Neural Networkscited by 11
  14. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  15. 2025Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modelingcited by 10
  16. 2025Can You Hear Me Now? A Benchmark for Long-Range Graph Propagationcited by 10
  17. 2024On The Temporal Domain of Differential Equation Inspired Graph Neural Networkscited by 9
  18. 2024Unitary convolutions for learning on graphs and groupscited by 8
  19. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  20. 2023Non-backtracking Graph Neural Networkscited by 7
  21. 2024Distributed-Order Fractional Graph Operating Networkcited by 7
  22. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 7
  23. 2025Improving the Effective Receptive Field of Message-Passing Neural Networkscited by 6
  24. 2023Multiscale Neural Operators for Solving Time-Independent PDEscited by 5
  25. 2024Graph Unitary Message Passingcited by 5
  26. 2024CKGConv: General Graph Convolution with Continuous Kernelscited by 5
  27. 2024Next Level Message-Passing with Hierarchical Support Graphscited by 5
  28. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  29. 2026mHC-GNN: Manifold-Constrained Hyper-Connections for Graph Neural Networkscited by 4
  30. 2024Graph External Attention Enhanced Transformercited by 3
  31. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  32. 2024Improving Graph Neural Networks by Learning Continuous Edge Directionscited by 3
  33. 2023Can strong structural encoding reduce the importance of Message Passing?cited by 2
  34. 2024Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attentioncited by 2
  35. 2024Scalable Graph Compressed Convolutionscited by 2
  36. 2024Relational Graph Convolutional Networks Do Not Learn Sound Rulescited by 2
  37. 2025Early-Exit Graph Neural Networkscited by 2
  38. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2

50 most cited of 82 All 82 (JSON)