Graph Rewiring

Follow this topic Ask about this topic

Graph rewiring studies how adding, removing, or reweighting edges can help graph neural networks pass information across distant nodes and avoid over-squashing or over-smoothing. Methods use signals such as curvature, effective resistance, spectral properties, structural roles, optimal transport, or learned edge scores to identify or create useful connections. They are tested on node and graph classification, heterophilic graphs, and spatio-temporal forecasting, often across multiple GNN architectures. A central tension is that stronger connectivity can ease communication but also accelerate over-smoothing or disrupt useful local structure, while finding an optimal rewiring may be computationally hard.

Latest papers

14 papers0 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classification
Sep 26, 2026Harshit Kumar, Sujan Chakraborty, Priyanka Saha +2Graph Rewiring Graph Structure Learning
School of Data Science, Indian Institute of Science Education and Research Thiruvananthapuram, Thiruvananthapuram 695551, India
Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment
Aug 11, 2026Yan Wang, Chuan-Xian RenGraph Rewiring Over-Squashing
School of Mathematics, Sun Yat-sen University, Guangzhou 510275, China
Schreier-Coset Graph Rewiring
Jul 29, 2026Aryan Mishra, Randy Martinez, Lizhen LinGraph Neural Networks Graph Rewiring
Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature
Jul 24, 2026Rachid Caich, Yassine AbbahaddouOversmoothing Graph Rewiring
LIX, École Polytechnique IP Paris Palaiseau, France
Ramanujan Graph Rewiring with Non Negative Resistance Curvature
Jun 19, 2026Hugo Attali, Rachid El JouhriGraph Structure Learning Graph Rewiring
Université Sorbonne Paris Nord, CNRS, LIPN, France
Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning
Jun 3, 2026Meher Chaitanya, My Le, Luana RuizGraph Structure Learning Graph Rewiring
Johns Hopkins University Baltimore, MD 21210
RADE: Random Add-Drop Edge as a Regularizer
May 30, 2026Danial Saber, Amirali Salehi-AbariNeural Network Generalization Graph Neural Networks
Ontario Tech University, Oshawa, Ontario, Canada.
Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint
May 22, 2026Hoyun Choi, Junghyo Jo, Deok-Sun LeeGraph Rewiring Graph Generation
School of Computational Sciences, Korea Institute for Advanced Study, 85, Hoegi-ro, 02455, Seoul, Korea. · Department of Physics Education, Seoul National University, 1, Gwanak-ro, 08826, Seoul, Korea. · Center for Theoretical Physics and Artificial Intelligence Institute, Seoul National University, 1, Gwanak-ro, 08826, Seoul, Korea. +1
Improving Spatio-Temporal Residual Error Propagation by Mitigating Over-Squashing
May 18, 2026Seyed Mohamad Moghadas, Esther Rodrigo Bonet, Bruno Cornelis +1Graph Rewiring Over-Squashing
ETRO Department, Vrije Universiteit Brussel, B-1050 Brussels, Belgium · imec Kapeldreef 75, B-3001 Leuven, Belgium
RAwR: Role-Aware Rewiring via Approximate Equitable Partition
May 10, 2026Riccardo Porcedda, Giuseppe Squillace, Bastian Epping +4Graph Structure Learning Graph Neural Networks
Department of Excellence L’EMbeDS, Sant’Anna School of Advanced Studies, Pisa, Italy · Department of Computer Science, University of Pisa, Italy · IMT School for Advanced Studies, Lucca, Italy +4
Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey
May 1, 2026Hugo Attali, Nathalie Pernelle, Davide Buscaldi +1Graph Neural Networks Graph Rewiring
Universit´e Sorbonne Paris Nord, CNRS, LIPN · Universit´e Paris-Saclay, CentraleSup´elec, Inria
On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks
Mar 27, 2026Mostafa Haghir ChehreghaniOver-Squashing in GNNs Over-Smoothing in GNNs
Department of Computer Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing
Mar 12, 2026Bertran Miquel-Oliver, Manel Gil-Sorribes, Victor Guallar +1Oversmoothing Graph Neural Networks
Barcelona Supercomputing Center (BSC), Barcelona, Spain · Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Barcelona, Spain · Nostrum Biodiscovery, Barcelona, 08029, Spain +1
Understanding over-squashing and bottlenecks on graphs via curvature
Nov 29, 2021Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain +2Graph Rewiring Over-Squashing
University of Oxford · Imperial College London · Twitter

Sep 26, 2026J/K move · Enter open · S save

Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classification

Harshit Kumar, Sujan Chakraborty, Priyanka Saha, Pritam Kar+1

School of Data Science, Indian Institute of Science Education and Research Thiruvananthapuram, Thiruvananthapuram 695551, India

Graph Rewiring Graph Structure Learning Graph Heterophily Node Classification Graph Embedding

Open paper AskPDF arXiv

Graph neural networks lose much of their advantage on heterophilic graphs, where connected nodes often carry different labels. Graph rewiring is a popular remedy, but rewiring methods are usually evaluated with a single classifier, which makes it hard to tell whether the gains come from the new topology or from that particular pairing. We propose an affinity-guided rewiring method that estimates the graph and the node representation together. It alternates, in the spirit of expectation maximisation, between training a lightweight graph neural network on the current graph and re-weighting candidate edges under a modularity objective with a pseudo-label homophily term. Candidate edges come from a compact pool scored by a contrastively learned node similarity and a neighbourhood-distribution affinity. The method returns two classifier-independent outputs: a rewired graph and a node embedding learned on it. Across six heterophilic benchmarks and five downstream classifiers, it improves accuracy over the original graph with normalised features in 23 of 30 classifier-dataset combinations, with a mean gain of 5.8 points, and reduces the accuracy spread between classifiers about fourfold. A controlled ablation shows that the two outputs are each useful and play complementary roles: the embedding contributes most of the accuracy gain, while the rewired graph makes different classifiers agree. A fully unsupervised variant, which uses no labels during rewiring, retains most of the improvement. The rewired graphs are also more homophilic and improve label propagation and community detection.