Graph Rewiring

Follow this topic Ask about this topic

Momentum

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

Jul 13Week of Sep 28

Latest papers 11

All topics

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 AbbahaddouGraph Neural Networks 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
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

Aug 11, 2026, cs.LGJ/K move · Enter open · S save

Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment

Yan Wang, Chuan-Xian Ren

School of Mathematics, Sun Yat-sen University, Guangzhou 510275, China

Graph Rewiring Over-Squashing Message Passing Neural Networks

Open paper AskPDF arXiv

Message-passing neural networks (MPNNs) often struggle when task-relevant information is distributed across distant regions of a graph, since local propagation must compress remote signals through limited structural interfaces. Graph rewiring provides a structural response to over-squashing. Most existing methods rely on edge-level bottleneck scores or graph-level connectivity surrogates. With a limited rewiring budget, the key question is which pairwise communications most need structural support. This paper proposes PairAlign, a pair-centric graph rewiring framework that makes this question explicit through demand-support shortage. Specifically, PairAlign combines original-graph structural demand with current-graph finite-hop propagation support; their ratio highlights interactions whose communication demand is poorly supported by topology, and our theory shows that this score provides a computable proxy for the corresponding Jacobian-based shortage with a pair-level interpretation of over-squashing. Our theory reveals a two-sided effect of edge insertion: a new edge can create useful walks and simultaneously dilute existing normalized transition mass. Guided by this observation, PairAlign optimizes shortage to favor edge additions that alleviate over-squashing. Beyond selecting useful additions, PairAlign further introduces an Optimal Transport-guided rewiring mechanism to coordinate the finite edge budget for pair-level structural compatibility and shortage-target coverage. It formulates communication alignment between the candidate edge budget and the shortage targets, and the theory shows that this allocation covers shortage targets more broadly and effectively than a greedy-local assignment. Experiments on standard graph benchmarks show PairAlign's improvement across message-passing backbones, validating pair-level repair as an effective route for alleviating over-squashing.

Momentum

Related topics

Latest papers 11