RAwR: Role-Aware Rewiring via Approximate Equitable Partition

arXiv (Cornell University)

Abstract

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.

Authors 7

1. Riccardo Porcedda

   University of Pisa · Scuola Superiore Sant'Anna

   Affiliation as printed

   Department of Computer Science , University of Pisa , Italy

   Department of Excellence L'EMbeDS , Sant'Anna School of Advanced Studies , Pisa , Italy

2. Giuseppe Squillace

   IMT School for Advanced Studies Lucca · Scuola Superiore Sant'Anna

   Affiliation as printed

   Department of Excellence L'EMbeDS , Sant'Anna School of Advanced Studies , Pisa , Italy

   IMT School for Advanced Studies , Lucca , Italy

3. Bastian Epping Aachen Computational Network Science

   RWTH Aachen University

   Affiliation as printed

   Computational Network Science , RWTH Aachen University , Aachen , Germany

4. Andrea Vandin

   Scuola Superiore Sant'Anna · Technical University of Denmark

   Affiliation as printed

   DTU Technical University of Denmark , Lyngby , Denmark

   Department of Excellence L'EMbeDS , Sant'Anna School of Advanced Studies , Pisa , Italy

5. Michael Schaub Aachen Computational Network Science

   RWTH Aachen University

   Affiliation as printed

   Computational Network Science , RWTH Aachen University , Aachen , Germany

6. Mirco Tribastone

   IMT School for Advanced Studies Lucca

   Affiliation as printed

   IMT School for Advanced Studies , Lucca , Italy

7. Francesca Chiaromonte