# RAwR: Role-Aware Rewiring via Approximate Equitable Partition

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 35 references that are in the map.
- First posted on arXiv 10 May 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [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)
- [On the Connection Between MPNN and Graph Transformer](https://mlsanity.com/paper/2301.11956/) (2023)
- [Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks](https://mlsanity.com/paper/2502.14546/) (2025)
- [On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs](https://mlsanity.com/paper/2107.01495/) (2021)
- [Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement](https://mlsanity.com/paper/2503.09008/) (2025)
- [Understanding Virtual Nodes: Oversquashing and Node Heterogeneity](https://mlsanity.com/paper/2405.13526/) (2024)
- [GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring](https://mlsanity.com/paper/2502.04891/) (2025)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation](https://mlsanity.com/paper/2512.17762/) (2025)
- [2-hop Neighbor Class Similarity (2NCS): A graph structural metric indicative of graph neural network performance](https://mlsanity.com/paper/2212.13202/) (2022)
- [Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks](https://mlsanity.com/paper/2508.19071/) (2025)
- [Efficient Network Embedding by Approximate Equitable Partitions](https://mlsanity.com/paper/2409.10160/) (2024)
- [Active Discovery of Network Roles for Predicting the Classes of Network Nodes](https://mlsanity.com/paper/1312.7258/) (2013)
- [An Optimization-based Approach To Node Role Discovery in Networks: Approximating Equitable Partitions](https://mlsanity.com/paper/2305.19087/) (2023)
- [Convergence of gradient based training for linear Graph Neural Networks](https://mlsanity.com/paper/2501.14440/) (2025)

## Abstract (arXiv)

While Graph Neural Networks (GNNs) have demonstrated significant efficacy in node classification tasks, where predictions rely on local neighborhood information, the performance of GNNs often drops when prediction tasks depend on long-range interactions. These limitations are attributed to phenomena such as oversquashing, where structural bottlenecks restrict signal propagation across the network topology. To address this challenge, we introduce RAwR, a computationally efficient rewiring framework that augments the input graph with a quotient graph derived from equitable partitions. This approach facilitates accelerated communication between nodes that share identical structural roles, as identified by the Weisfeiler-Leman graph coloring, and thereby reduces the total effective resistance of the system. Furthermore, by employing an approximate definition of the equitable partition, RAwR enables a controllable reduction of the quotient graph, which, in its most condensed state, recovers the conventional Master Node rewiring technique. Empirical evaluations across a diverse suite of benchmarks -- including homophilic, heterophilic, and synthetic long-range datasets -- demonstrate that RAwR achieves state-of-the-art results. Our contribution is further supported by an analytical investigation using a teacher-student model of linear GNNs, which elucidates the theoretical foundations of role-based rewiring. This analysis leads to the formulation of Spectral Role Lift (SRL), a metric designed to identify the optimal approximate equitable partition for maximizing predictive performance.