mlsanityData to 14 Oct 2026

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

arXiv 2608.10619 ↗First posted 11 Aug 2026cs.LGcited by 0

Not on the map. Why?

Abstract (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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 30 of its 35 references that are in the map. First posted on arXiv 11 Aug 2026.

Builds on

30 of 35 references.

References · 30

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  6. 2013Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computationcited by 2,079
  7. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  11. 2019Multi-scale Attributed Node Embeddingcited by 548
  12. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
18 more
  1. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  2. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 223
  3. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  4. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 98
  5. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  6. 2022Expander Graph Propagationcited by 75
  7. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  8. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 53
  9. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  10. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 36
  11. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 24
  12. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  13. 2024Cayley Graph Propagationcited by 21
  14. 2022Rewiring Networks for Graph Neural Network Training Using Discrete Geometrycited by 14
  15. 2025GNNs Getting ComFy: Community and Feature Similarity Guided Rewiringcited by 13
  16. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  17. 2024The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisitedcited by 11
  18. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 8

Built on by

Not cited yet.