RAwR: Role-Aware Rewiring via Approximate Equitable Partition

• URL: http://arxiv.org/abs/2605.09457v1
• Date: Sun, 10 May 2026 10:15:40 GMT
• Title: RAwR: Role-Aware Rewiring via Approximate Equitable Partition
• Abstract summary: We introduce RAwR, a computationally efficient rewiring framework.<n> RAwR augments the input graph with a quotient graph derived from equitable partitions.<n> Empirical evaluations across a diverse suite of benchmarks demonstrate RAwR achieves state-of-the-art results.
• Score: 1.5445058818973285
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Deep Gaussian Processes on Directed Acyclic Graphs [11.74273181198187]
  Many real-world processes can be represented as compositions of functions along a directed acyclic graph (DAG)<n>These functions are partially observed across the DAG, with noisy and heterogeneously sampled measurements.<n>We theoretically study their prior-collapse behaviour, and the effect of graph topology and intermediate observations on information preservation.<n>We offer a structured variational approximation that retains graph dependencies, preserves compositional uncertainty, and captures the explaining-away behaviour of colliders.
  arXiv  Detail & Related papers  (2026-07-10T17:41:11Z)
• Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs [81.39865232674413]
  Graph Neural Networks (GNNs) have emerged as a powerful tool for wireless resource allocation.<n>This work establishes theoretical results for transferability of GNNs over graphs derived from sparse Random Geometric Graphs (RGGs)
  arXiv  Detail & Related papers  (2026-06-02T15:42:14Z)
• SCL-GNN: Towards Generalizable Graph Neural Networks via Spurious Correlation Learning [12.004932896426347]
  Graph Neural Networks (GNNs) have demonstrated remarkable success across diverse tasks.<n>GNNs tend to exploit imperceptible statistical correlations in training data, even when such correlations are unreliable for prediction.<n>We propose a novel framework designed to enhance generalization on both Independent and Identically Distributed (IID) and Out-of-Distribution (OOD) graphs.
  arXiv  Detail & Related papers  (2026-03-09T11:42:06Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• Understanding the Effect of GCN Convolutions in Regression Tasks [8.299692647308323]
  Graph Convolutional Networks (GCNs) have become a pivotal method in machine learning for modeling functions over graphs.<n>We consider networks for which the graph structure implies that neighboring nodes exhibit similar signals.<n>We examine how two common convolutions - the original GCN and GraphSAGE convolutions - affect the learning error.
  arXiv  Detail & Related papers  (2024-10-26T04:19:52Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphs [94.44374472696272]
  We investigate NTKs and alignment in the context of graph neural networks (GNNs) Our results establish the theoretical guarantees on the optimality of the alignment for a two-layer GNN. These guarantees are characterized by the graph shift operator being a function of the cross-covariance between the input and the output data.
  arXiv  Detail & Related papers  (2023-10-16T19:54:21Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  We propose a novel graph contrastive learning method, termed Mixed Graph Contrastive Network (MGCN)<n>In our method, we improve the discriminative capability of the latent embeddings by an unperturbed augmentation strategy and a correlation reduction mechanism.<n>By combining the two settings, we extract rich supervision information from both the abundant nodes and the rare yet valuable labeled nodes for discriminative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  Graph Neural Networks (GNNs) are proposed without considering the distribution shifts between training and testing graphs. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. We propose a general causal representation framework, called StableGNN, to eliminate the impact of spurious correlations.
  arXiv  Detail & Related papers  (2021-11-20T18:57:18Z)

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.