Over-Squashing

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 9

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
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
Graph Neural Networks Applications Across Domains: All Insights You Need
Jun 25, 2026Abderaouf BahiGraph Neural Networks Over-Squashing
Computer Science and Applied Mathematics Laboratory (LIMA), Faculty of Science and Technology, Chadli Bendjedid University, P.O. Box 73, El Tarf 36000, Algeria
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
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
Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
May 8, 2026Md Sazzad Hossen, Avimanyu SahooGraph Neural Networks Over-Squashing
University of Alabama in Huntsville, Huntsville, AL, USA.
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 9