Schreier-Coset Graph Rewiring

• URL: http://arxiv.org/abs/2607.27479v1
• Date: Wed, 29 Jul 2026 21:42:02 GMT
• Title: Schreier-Coset Graph Rewiring
• Abstract summary: We introduce a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group.<n>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.
• Score: 1.6566053195631467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks [1.652121135969053]
  Topology-Aware Gaussian Repair (TAGR) is a simple graph repair framework for robust message passing in graph neural networks.<n>We show that TAGR improves the robustness of graph neural networks under both noisy-edge and missing-edge settings.
  arXiv  Detail & Related papers  (2026-06-02T10:39:24Z)
• Improved large-scale graph learning through ridge spectral sparsification [65.84577791298442]
  We consider the problem of learning over the Laplacian L in a distributed streaming setting.<n>In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L.<n>We present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances.
  arXiv  Detail & Related papers  (2026-04-22T00:49:31Z)
• Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing [0.03636228980200798]
  We introduce Effective Resistance Rewiring (ERR), a simple topology correction strategy that uses effective resistance as a global signal to detect structural bottlenecks.<n>ERR iteratively adds edges between node pairs with the largest resistance while removing edges with minimal resistance, strengthening weak communication pathways.<n>By tracking cosine similarity between node embeddings across layers, we examine how the relationship between initial node features and learned representations evolves during message passing.
  arXiv  Detail & Related papers  (2026-03-12T13:55:48Z)
• Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics [52.077620040518646]
  We provide the first systematic analysis of how rewiring affects a range of graph structural metrics.<n>We study seven diverse rewiring strategies and correlate changes in local and global graph properties with node classification accuracy.<n>Our results reveal a consistent pattern: successful rewiring methods tend to preserve local structure while allowing for flexibility in global connectivity.
  arXiv  Detail & Related papers  (2025-10-23T13:38:41Z)
• GraphTorque: Torque-Driven Rewiring Graph Neural Network [24.311681447733346]
  We propose a torque-driven hierarchical rewiring strategy to improve representation learning in heterophilous and homophilous graphs.<n>We use the metric to reconfigure hierarchically receptive field of each layer by judiciously pruning high-torque edges and adding low-torque links.<n>Our approach surpasses state-of-the-art rewiring methods on both heterophilous and homophilous graphs.
  arXiv  Detail & Related papers  (2025-07-29T01:14:27Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• A Graph Data Augmentation Strategy with Entropy Preserving [11.886325179121226]
  We introduce a novel graph entropy definition as a quantitative index to evaluate feature information among a graph. Under considerations of preserving graph entropy, we propose an effective strategy to generate training data using a perturbed mechanism. Our proposed approach significantly enhances the robustness and generalization ability of GCNs during the training process.
  arXiv  Detail & Related papers  (2021-07-13T12:58:32Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.