mlsanityData to 14 Oct 2026

Schreier-Coset Graph Rewiring

arXiv 2607.27479 ↗First posted 29 Jul 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

The information flow in the graph neural networks (GNNs) is fundamentally constrained by over-squashing, where structural bottlenecks impede long range information propagation. Graph-rewiring methods, which modify graph topology, have been extensively used to alleviate this. However, existing approaches often introduce prohibitive structural and computational bottlenecks, fail to preserve the critical properties of original graphs, and increase the edge counts massively. We introduce a novel method Schreier-Coset Graph Rewiring , a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group. Our method provides theoretical guarantees, a graph that exhibits spectral gap and a bounded effective resistance, creating a low-resistance bypass for long-range communication. Empirical evaluations demonstrate that SCGR reduces effective resistance by 5-40% across various learning tasks, effectively mitigating connectivity bottlenecks while maintaining competitive accuracy.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 31 of its 48 references that are in the map. First posted on arXiv 29 Jul 2026.

Builds on

31 of 48 references.

References · 31

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  6. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  8. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  10. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  12. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
19 more
  1. 2019Diffusion Improves Graph Learningcited by 414
  2. 2018Graph networks as learnable physics engines for inference and controlcited by 244
  3. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  4. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 98
  5. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  6. 2022Expander Graph Propagationcited by 75
  7. 2019A Review of Stochastic Block Models and Extensions for Graph Clusteringcited by 46
  8. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 41
  9. 2023Cooperative Graph Neural Networkscited by 36
  10. 2023Graph Positional Encoding via Random Feature Propagationcited by 31
  11. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  12. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 24
  13. 2024Cayley Graph Propagationcited by 21
  14. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 19
  15. 2022ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalizationcited by 15
  16. 2019MONET: Debiasing Graph Embeddings via the Metadata-Orthogonal Training Unitcited by 11
  17. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  18. 2023Message Passing Meets Graph Neural Networks: A New Paradigm for Massive MIMO Systemscited by 8
  19. 2023Effective Resistances in Non-Expander Graphscited by 3

Built on by

Not cited yet.