# Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics

arXiv: https://arxiv.org/abs/2510.20556 · HTML: https://mlsanity.com/paper/2510.20556/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 42 references that are in the map.
- First posted on arXiv 23 Oct 2025.

## Builds on (most cited first, 16 of 16)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Community Detection on Networks with Ricci Flow](https://mlsanity.com/paper/1907.03993/) (2019)
- [Locality-Aware Graph-Rewiring in GNNs](https://mlsanity.com/paper/2310.01668/) (2023)
- [Graph Neural Networks Use Graphs When They Shouldn't](https://mlsanity.com/paper/2309.04332/) (2023)
- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [Rewiring Networks for Graph Neural Network Training Using Discrete Geometry](https://mlsanity.com/paper/2207.08026/) (2022)

## Built on by (most cited first, 1 of 1)

- [Omega-N: Interpretable Structural Node Descriptors and Their Applicability Domain](https://mlsanity.com/paper/2609.01633/) (2026)

## Abstract (arXiv)

Graph rewiring has emerged as a key technique to alleviate over-squashing in Graph Neural Networks (GNNs) and Graph Transformers by modifying the graph topology to improve information flow. While effective, rewiring inherently alters the graph's structure, raising the risk of distorting important topology-dependent signals. Yet, despite the growing use of rewiring, little is known about which structural properties must be preserved to ensure both performance gains and structural fidelity. In this work, we provide the first systematic analysis of how rewiring affects a range of graph structural metrics, and how these changes relate to downstream task performance. We study seven diverse rewiring strategies and correlate changes in local and global graph properties with node classification accuracy. Our results reveal a consistent pattern: successful rewiring methods tend to preserve local structure while allowing for flexibility in global connectivity. These findings offer new insights into the design of effective rewiring strategies, bridging the gap between graph theory and practical GNN optimization.