Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics
This work addresses the problem of balancing performance gains with structural fidelity in graph rewiring for GNNs, offering insights for researchers and practitioners, though it is incremental as it builds on existing rewiring techniques.
The paper systematically analyzes how graph rewiring affects structural metrics and relates these changes to node classification performance, finding that successful methods preserve local structure while allowing flexibility in global connectivity.
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.