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

• URL: http://arxiv.org/abs/2608.10619v1
• Date: Tue, 11 Aug 2026 08:05:32 GMT
• Title: Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment
• Abstract summary: Graph rewiring provides a structural response to over-squashing.<n>With a limited rewiring budget, the key question is which pairwise communications most need structural support.<n>This paper proposes PairAlign, a pair-centric graph rewiring framework.
• Score: 24.215683640150413
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Adjacency-Based Spectral Proxy Control of Mobile Communication Agents [0.23872611575805827]
  We consider a heterogeneous mobile-agent network composed of uncontrolled task agents and controllable communication agents.<n>Controlling connectivity relies on the eigenvector corresponding to the second-smallest eigenvalue of a graph's Laplacian matrix.<n>We propose A-Fiedler, which replaces the Fiedler embedding with the dominant eigenvector of the adjacency matrix.
  arXiv  Detail & Related papers  (2026-08-12T20:35:02Z)
• Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing [0.03636228980200798]
  We introduce Effective Resistance Rewiring (ERR), a simple topology correction strategy that uses effective resistance as a global signal to detect structural bottlenecks.<n>ERR iteratively adds edges between node pairs with the largest resistance while removing edges with minimal resistance, strengthening weak communication pathways.<n>By tracking cosine similarity between node embeddings across layers, we examine how the relationship between initial node features and learned representations evolves during message passing.
  arXiv  Detail & Related papers  (2026-03-12T13:55:48Z)
• LineGraph2Road: Structural Graph Reasoning on Line Graphs for Road Network Extraction [0.0]
  LineGraph2Road is a framework that improves connectedness prediction by formulating it as binary classification over edges in a constructed global but sparse Euclidean graph.<n>We evaluate it on three benchmarks: City-scale, SpaceNet, and Global-scale, and show that it achieves state-of-the-art results on two key metrics, TOPO-F1 and APLS.
  arXiv  Detail & Related papers  (2026-02-26T18:02:44Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration [50.67878993903822]
  We propose a communication-efficient Adapt-Then-Combine (ATC) framework, FlexATC, unifying numerous ATC-based distributed algorithms.<n>We show for the first time that local updates provably lead to communication acceleration for ATC-based distributed algorithms.
  arXiv  Detail & Related papers  (2026-02-18T02:47:05Z)
• A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing [11.765197673198983]
  We study finite-sum nonlinear programs whose decision variables interact locally according to a graph or hypergraph.<n>We propose MP-Jacobi, a graph-compliant decentralized framework that couples min-sum message passing with Jacobi block updates.
  arXiv  Detail & Related papers  (2025-12-31T07:05:37Z)
• Transfer Learning on Edge Connecting Probability Estimation under Graphon Model [7.805468525082696]
  We propose a transfer learning framework that integrates neighborhood smoothing and Gromov-Wasserstein optimal transport to align and transfer structural patterns between graphs.<n>GTRANS includes an adaptive debiasing mechanism that identifies and corrects for target-specific deviations via residual smoothing.<n>These improvements translate directly to enhanced performance in downstream applications, such as the graph classification task and the link prediction task.
  arXiv  Detail & Related papers  (2025-10-07T02:37:12Z)
• Towards Pre-trained Graph Condensation via Optimal Transport [52.6504753271008]
  Graph condensation aims to distill the original graph into a small-scale graph, mitigating redundancy and accelerating GNN training.<n> conventional GC approaches heavily rely on rigid GNNs and task-specific supervision.<n>Pre-trained Graph Condensation (PreGC) via optimal transport is proposed to transcend the limitations of task- and architecture-dependent GC methods.
  arXiv  Detail & Related papers  (2025-09-18T08:13:24Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Self-Supervised Relation Alignment for Scene Graph Generation [44.3983804479146]
  We introduce a self-supervised relational alignment regularization to improve scene graph generation performance. The proposed alignment is general and can be combined with any existing scene graph generation framework. We illustrate the effectiveness of this self-supervised relational alignment in conjunction with two scene graph generation architectures.
  arXiv  Detail & Related papers  (2023-02-02T20:34:13Z)
• Graph Reasoning Transformer for Image Parsing [67.76633142645284]
  We propose a novel Graph Reasoning Transformer (GReaT) for image parsing to enable image patches to interact following a relation reasoning pattern. Compared to the conventional transformer, GReaT has higher interaction efficiency and a more purposeful interaction pattern. Results show that GReaT achieves consistent performance gains with slight computational overheads on the state-of-the-art transformer baselines.
  arXiv  Detail & Related papers  (2022-09-20T08:21:37Z)

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.