Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing

• URL: http://arxiv.org/abs/2603.11944v1
• Date: Thu, 12 Mar 2026 13:55:48 GMT
• Title: Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing
• Abstract summary: 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.
• Score: 0.03636228980200798
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks struggle to capture long-range dependencies due to over-squashing, where information from exponentially growing neighborhoods must pass through a small number of structural bottlenecks. While recent rewiring methods attempt to alleviate this limitation, many rely on local criteria such as curvature, which can overlook global connectivity constraints that restrict information flow. We introduce Effective Resistance Rewiring (ERR), a simple topology correction strategy that uses effective resistance as a global signal to detect structural bottlenecks. ERR iteratively adds edges between node pairs with the largest resistance while removing edges with minimal resistance, strengthening weak communication pathways while controlling graph densification under a fixed edge budget. The procedure is parameter-free beyond the rewiring budget and relies on a single global measure aggregating all paths between node pairs. Beyond predictive performance with GCN models, we analyze how rewiring affects message propagation. 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, comparing graphs with and without rewiring. This analysis helps determine whether improvements arise from better long-range communication rather than changes in embedding geometry. Experiments on homophilic and heterophilic graphs, including directed settings with DirGCN, reveal a trade-off between over-squashing and oversmoothing, where oversmoothing corresponds to the loss of representation diversity across layers. Resistance-guided rewiring improves connectivity and signal propagation but can accelerate representation mixing in deep models. Combining ERR with normalization techniques such as PairNorm stabilizes this trade-off and improves performance.

Related papers

• Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment [24.215683640150413]
  Graph rewiring provides a structural response to over-squashing.<n>With a limited rewiring budget, the key question is which pairwise communications most need structural support.<n>This paper proposes PairAlign, a pair-centric graph rewiring framework.
  arXiv  Detail & Related papers  (2026-08-11T08:05:32Z)
• Schreier-Coset Graph Rewiring [1.6566053195631467]
  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.
  arXiv  Detail & Related papers  (2026-07-29T21:42:02Z)
• On the Geometric Coherence of Global Aggregation in Federated GNN [0.0]
  Federated Learning (FL) enables distributed training across multiple clients without centralized data sharing.<n> Graph Neural Networks (GNNs) model relational data through message passing.<n>In federated GNN settings, client graphs often exhibit heterogeneous structural and propagation characteristics.<n>Our work identifies a geometric failure mode of global aggregation in Cross- Domain Federated GNNs.<n>We propose GGRS, a server-side framework that regulates client updates prior to aggregation based on geometric admissibility criteria.
  arXiv  Detail & Related papers  (2026-02-17T11:34:04Z)
• Generalizing GNNs with Tokenized Mixture of Experts [75.8310720413187]
  We show that improving stability requires reducing reliance on shift-sensitive features, leaving an irreducible worst-case generalization floor.<n>We propose STEM-GNN, a pretrain-then-finetune framework with a mixture-of-experts encoder for diverse computation paths.<n>Across nine node, link, and graph benchmarks, STEM-GNN achieves a stronger three-way balance, improving robustness to degree/homophily shifts and to feature/edge corruptions while remaining competitive on clean graphs.
  arXiv  Detail & Related papers  (2026-02-09T22:48:30Z)
• Riemannian Flow Matching for Disentangled Graph Domain Adaptation [51.98961391065951]
  Graph Domain Adaptation (GDA) typically uses adversarial learning to align graph embeddings in Euclidean space.<n>DisRFM is a geometry-aware GDA framework that unifies embedding and flow-based transport.
  arXiv  Detail & Related papers  (2026-01-31T11:05:35Z)
• 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)
• Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks [21.49824162847618]
  Graph Neural Networks (GNNs) suffer from Oversquashing, which occurs when tasks require long-range interactions.<n>We propose an efficient model-agnostic framework that asynchronously updates node features, unlike traditional synchronous message passing GNNs.<n>Our framework is applied to six standard graph datasets and two long-range datasets to perform graph classification.
  arXiv  Detail & Related papers  (2025-09-08T15:03:05Z)
• Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio [0.6117371161379209]
  Message passing neural networks (MPNNs) are powerful models for node classification but suffer from performance limitations under heterophily and structural bottlenecks in the graph.<n>We provide a unifying statistical framework exposing the relationship between heterophily and bottlenecks through the signal-to-noise ratio (SNR) of MPNN representations.<n>We prove that optimal graph structures for maximising higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters.<n>This yields BRIDGE, a graph ensemble-based rewiring algorithm that achieves near-perfect classification accuracy across all homophily
  arXiv  Detail & Related papers  (2025-08-25T09:25:14Z)
• 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)
• A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs [54.62268052283014]
  We present a unified theoretical perspective based on the framework of signed graphs.<n>We show that many existing strategies implicitly introduce negative edges that alter message-passing to resist oversmoothing.<n>We propose Structural Balanced Propagation (SBP), a plug-and-play method that assigns signed edges based on either labels or feature similarity.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Point Cloud Denoising With Fine-Granularity Dynamic Graph Convolutional Networks [58.050130177241186]
  Noise perturbations often corrupt 3-D point clouds, hindering downstream tasks such as surface reconstruction, rendering, and further processing. This paper introduces finegranularity dynamic graph convolutional networks called GDGCN, a novel approach to denoising in 3-D point clouds.
  arXiv  Detail & Related papers  (2024-11-21T14:19:32Z)
• NetDiff: Deep Graph Denoising Diffusion for Ad Hoc Network Topology Generation [1.6768151308423371]
  We introduce NetDiff, a graph denoising diffusion probabilistic architecture that generates wireless ad hoc network link topologies. Our results show that the generated links are realistic, present structural properties similar to the dataset graphs', and require only minor corrections and verification steps to be operational.
  arXiv  Detail & Related papers  (2024-10-09T15:39:49Z)
• Adversarial Graph Disentanglement [47.27978741175575]
  A real-world graph has a complex topological structure, which is often formed by the interaction of different latent factors. We propose an underlinetextbfAdversarial underlinetextbfDisentangled underlinetextbfGraph underlinetextbfConvolutional underlinetextbfNetwork (ADGCN) for disentangled graph representation learning.
  arXiv  Detail & Related papers  (2021-03-12T14:11:36Z)

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.