mlsanityData to 7 Oct 2026

Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning

arXiv 2606.05046 ↗First posted 3 Jun 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We introduce Graph Cascades, a mesoscopic rewiring strategy for Graph Neural Networks (GNNs) and Graph Transformers (GTs) that captures intermediate-scale graph structure beyond purely local edges or fully global attention. Using contagion-based diffusion processes, Graph Cascades constructs, in O(|V|+|E|) time, an auxiliary graph where node pairs supported by repeated multi-hop reinforcement are promoted to direct neighbors. We theoretically characterize when reinforcement-based rewiring helps: sufficient conditions under which reinforcement-based edge selection is more label-aligned than direct adjacency, an SBM witness in which two-hop reinforcement is perfectly homophilic, and a formalization of mesoscopic connectivity via graph effective resistance. Empirically, across node-classification benchmarks, Graph Cascades improves multiple GNN and sparse-GT backbones, with the most reliable gains observed on heterophilic and moderate- to high-degree homophilic graphs. The theoretical conditions also identify regimes where mesoscopic rewiring is unlikely to be beneficial -- low-degree regular graphs and graphs with structural bottlenecks -- and these predictions match the observed failures. We additionally observe tight correlations between performance and structural properties in the rewired graphs.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 48 of its 62 references that are in the map. First posted on arXiv 3 Jun 2026.

Builds on

48 of 62 references.

References · 48

  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. 2020Rethinking Attention with Performerscited by 1,584
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  7. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  8. 2020Benchmarking Graph Neural Networkscited by 672
  9. 2020A Generalization of Transformer Networks to Graphscited by 653
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  11. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  12. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
36 more
  1. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  2. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  3. 2021Graph Neural Network-Based Anomaly Detection in Multivariate Time Seriescited by 300
  4. 2022Long Range Graph Benchmarkcited by 258
  5. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 207
  6. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  7. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  8. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  9. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  10. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  11. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  12. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  13. 2023Exphormer: Sparse Transformers for Graphscited by 166
  14. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  15. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  16. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 131
  17. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  18. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  19. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  20. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  21. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  22. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  23. 2021Gophormer: Ego-Graph Transformer for Node Classificationcited by 63
  24. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  25. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  26. 2024VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connectionscited by 34
  27. 2022GRAND+: Scalable Graph Random Neural Networkscited by 25
  28. 2023Homophily-oriented Heterogeneous Graph Rewiringcited by 18
  29. 2023No prejudice! Fair Federated Graph Neural Networks for Personalized Recommendationcited by 18
  30. 2024Benchmarking Positional Encodings for GNNs and Graph Transformerscited by 13
  31. 2025GNNs Getting ComFy: Community and Feature Similarity Guided Rewiringcited by 13
  32. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 11
  33. 2024PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformercited by 10
  34. 2024Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphscited by 8
  35. 2025Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networkscited by 4
  36. 2024Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classificationcited by 3

Built on by

Not cited yet.