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

# Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment
Source: [https://arxiv.org/html/2608.10619](https://arxiv.org/html/2608.10619)
Yan Wang and Chuan\-Xian RenThis work is supported by National Natural Science Foundation of China 62376291\. \(Corresponding author: Chuan\-Xian Ren\.\)The authors are with the School of Mathematics, Sun Yat\-sen University, Guangzhou 510275, China \(e\-mail: rchuanx@mail\.sysu\.edu\.cn\)\.

###### 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\.

## IIntroduction

MPNNS have become a standard framework for learning on graph\-structured data because they represent nodes, edges, and whole graphs through iterative local propagation over graph connectivity\[[17](https://arxiv.org/html/2608.10619#bib.bib26),[20](https://arxiv.org/html/2608.10619#bib.bib27)\]\. The effectiveness of an MPNN depends on whether the input topology can support the transfer of task\-relevant information\. When useful evidence is distributed across distant regions of a graph, it must pass through successive local neighborhoods and be compressed into fixed\-width hidden states\. The graph can then become a communication bottleneck, with many remote signals forced through a small number of structural interfaces and consequently attenuated or lost\. This over\-squashing phenomenon has made graph rewiring a natural structural response, since the difficulty is governed not only by model depth but also by how the graph distributes communication support across node interactions\[[3](https://arxiv.org/html/2608.10619#bib.bib28),[30](https://arxiv.org/html/2608.10619#bib.bib32),[10](https://arxiv.org/html/2608.10619#bib.bib25)\]\.

![Refer to caption](https://arxiv.org/html/2608.10619v1/x1.png)Figure 1:Different rewiring targets in graph rewiring\. Under the same graph structure, graph\-level rewiring targets global connectivity, edge\-level rewiring focuses on local bottleneck repair, and PairAlign assigns rewiring support to communication\-limited node pairs\.Existing rewiring methods intervene on this problem from several directions\. Curvature\-based and edge\-centered methods use local geometric or topological cues to locate bottlenecks and modify structurally unfavorable regions\[[30](https://arxiv.org/html/2608.10619#bib.bib32),[24](https://arxiv.org/html/2608.10619#bib.bib30)\]\. Related local or path\-aware variants enlarge the propagation structure through positional or shortest\-path\-based modifications\[[16](https://arxiv.org/html/2608.10619#bib.bib29),[1](https://arxiv.org/html/2608.10619#bib.bib2)\]\. A second group evaluates rewiring through graph\-level communication surrogates such as spectral expansion, effective resistance, graph expansion, or differentiable global objectives\[[19](https://arxiv.org/html/2608.10619#bib.bib33),[10](https://arxiv.org/html/2608.10619#bib.bib25),[6](https://arxiv.org/html/2608.10619#bib.bib10),[5](https://arxiv.org/html/2608.10619#bib.bib11)\]\. Fig\.[1](https://arxiv.org/html/2608.10619#S1.F1)summarizes these two rewiring targets: graph\-level methods improve aggregate connectivity, while edge\-level methods repair local bottleneck structures\. More recent formulations further incorporate structural priors such as locality, community structure, feature similarity, or homophily guidance into the rewiring process\[[7](https://arxiv.org/html/2608.10619#bib.bib34),[28](https://arxiv.org/html/2608.10619#bib.bib36),[22](https://arxiv.org/html/2608.10619#bib.bib37),[9](https://arxiv.org/html/2608.10619#bib.bib6),[12](https://arxiv.org/html/2608.10619#bib.bib8)\]\. These directions have broadened the design space of graph rewiring, yet they also leave a practical allocation problem under limited budgets: structural support must be assigned to the node\-pair communications that need it most\. This problem is not fully resolved by graph\-level connectivity measures or edge\-level bottleneck scores, because the scarce budget must ultimately serve interactions between node pairs\. Without an explicit pair\-level notion of communication shortage, rewiring can improve aggregate connectivity while leaving the most constrained pairwise communications only indirectly supported\. This can weaken the effect of rewiring on the pairwise interactions most affected by over\-squashing\.

To address this gap, we proposePairAlign, a graph rewiring framework that makes*pairwise communication shortage*the basic object of structural repair\. PairAlign follows the pair\-level view in Fig\.[1](https://arxiv.org/html/2608.10619#S1.F1)and builds on the Jacobian view by prioritizing node pairs whose structural communication demand is high while their finite\-hop propagation support remains limited\. To make this view operational, PairAlign defines shortage as the ratio between original\-graph structural demand and current\-graph finite\-hop propagation support\. This score highlights interactions whose communication demand is poorly supported by the current topology\. Our theory shows that this shortage score provides a computable proxy for the corresponding Jacobian\-based shortage with a pair\-level interpretation of over\-squashing\.

To turn pair\-level diagnosis into edge additions, PairAlign scores candidate edges by their support effect on high\-shortage pairs\. A useful candidate edge need not directly connect the target pair; its value depends on the support improvement it provides to shortage pairs\. Our theory shows that the gain from edge insertion is not always positive: a new edge can create useful walks, while normalization reduces the transition mass assigned to existing neighbors\. Thus, PairAlign recomputes shortage during rewiring and selects edges by their current shortage reduction\. To coordinate the limited budget, PairAlign introduces an OT\-guided rewiring mechanism to allocate candidate\-edge mass across shortage targets\. This keeps the budget from concentrating on a few locally cheap pairs and coordinates allocation according to the shortage distribution over graph\-wide targets\. Accordingly, the main contributions of this work are summarized as follows\.

- •The paper introduces a*pair\-centric*formulation of graph rewiring based on communication shortage\. The shortage score ranks node pairs by the lack of current\-graph support relative to the original\-graph structural demand\. The theory shows the formulation makes Jacobian\-based shortage tractable through graph structure and yields an interpretable pair\-level diagnostic for over\-squashing\.
- •PairAlign is proposed as an OT\-guided graph rewiring framework for shortage\-aware edge addition\. Candidate edges are scored by current shortage reduction, and the OT\-guided allocation coordinates the limited edge budget across shortage targets\. This yields a globally coordinated rewiring strategy and avoids concentrating additions on only a few targets\.
- •We validate PairAlign on standard graph benchmarks across message\-passing backbones\. The results and mechanism studies show that PairAlign can effectively repair the communication shortage and improve performance\. This supports pair\-level repair as an effective route for alleviating over\-squashing\.

The remainder of the paper is organized as follows\. Section II reviews graph rewiring methods for over\-squashing\. Section III develops PairAlign from the shortage formulation to OT\-guided edge allocation\. Section IV evaluates the method and analyzes its rewiring mechanism\. Section V concludes the paper and discusses future directions\.

## IIRelated Work

Graph rewiring has become a central structural strategy for mitigating over\-squashing in MPNNs\. Over\-squashing arises when the input topology concentrates multiple information flows through restricted structural interfaces, causing useful signals to be compressed into fixed\-width node representations\[[3](https://arxiv.org/html/2608.10619#bib.bib28),[30](https://arxiv.org/html/2608.10619#bib.bib32)\]\. This phenomenon links the effectiveness of message passing to graph topology, including curvature, expansion, information contraction, and effective resistance properties\[[6](https://arxiv.org/html/2608.10619#bib.bib10),[10](https://arxiv.org/html/2608.10619#bib.bib25),[7](https://arxiv.org/html/2608.10619#bib.bib34)\]\. Expander\-based propagation further shows that bottleneck\-resistant computational structures can improve message passing without relying only on the original input topology\[[15](https://arxiv.org/html/2608.10619#bib.bib4)\]\. Recent surveys further organize over\-squashing mitigation into rewiring, spectral, curvature\-based, and propagation\-oriented families, confirming graph rewiring as a sustained research direction in MPNN design\[[2](https://arxiv.org/html/2608.10619#bib.bib15)\]\. Related spatial and path\-aware interventions expand the computational neighborhood through positional encodings, shortest\-path message passing, or discrete geometric rewiring, providing additional ways to improve propagation beyond immediate graph adjacency\[[16](https://arxiv.org/html/2608.10619#bib.bib29),[1](https://arxiv.org/html/2608.10619#bib.bib2),[11](https://arxiv.org/html/2608.10619#bib.bib9)\]\. In this setting, the main question is how a modified computational graph should distribute propagation support under a finite structural budget\.

A major line of rewiring methods diagnoses over\-squashing through local geometry and edge\-level bottlenecks\. SDRF uses graph curvature to locate structurally critical regions for rewiring, making curvature one of the earliest operational proxies for topology\-induced over\-squashing\[[30](https://arxiv.org/html/2608.10619#bib.bib32)\]\. BORF extends this perspective through Ollivier\-Ricci curvature and connects negative curvature with over\-squashing and positive curvature with over\-smoothing, yielding a unified local\-geometric rewriting principle\[[24](https://arxiv.org/html/2608.10619#bib.bib30)\]\. Recent studies have refined this view by examining the empirical behavior of curvature\-guided rewiring and by proposing more expressive curvature variants for detecting over\-squashed edges\[[31](https://arxiv.org/html/2608.10619#bib.bib19),[13](https://arxiv.org/html/2608.10619#bib.bib16)\]\. This family establishes a strong local diagnostic foundation for graph rewiring, and it motivates a complementary question concerning which node\-pair communications should receive structural support after local bottlenecks have been detected\.

Another line of work formulates rewiring through graph\-level communication surrogates\. FoSR improves spectral expansion by adding sparse edges that increase the spectral gap, thereby strengthening global connectivity for message passing\[[19](https://arxiv.org/html/2608.10619#bib.bib33)\]\. Effective resistance\-based methods use resistance as a communication proxy and guide edge modification through graph\-wide improvements in connectivity\[[10](https://arxiv.org/html/2608.10619#bib.bib25),[29](https://arxiv.org/html/2608.10619#bib.bib17)\]\. DiffWire introduces a differentiable rewiring objective based on the Lovász bound\[[5](https://arxiv.org/html/2608.10619#bib.bib11)\], and LASER studies the trade\-off among connectivity, locality, and sparsity through locality\-aware sequential rewiring\[[7](https://arxiv.org/html/2608.10619#bib.bib34)\]\. More recently, spectrum\-preserving sparsification has strengthened this family by improving connectivity while retaining sparsity and Laplacian spectral structure\[[21](https://arxiv.org/html/2608.10619#bib.bib35)\]\. Cayley graph propagation extends the expander\-based perspective by propagating over complete Cayley graph structures to obtain bottleneck\-free computational templates\[[34](https://arxiv.org/html/2608.10619#bib.bib7)\]\. These methods provide mature graph\-level principles for structural improvement, and they set the stage for rewiring objectives that explicitly organize the budget around a distribution of underserved node\-pair interactions\.

Recent rewiring studies have also incorporated task\-relevant signals beyond purely topological criteria\. ComFy uses community structure and feature similarity to guide rewiring toward stronger label\-community alignment\[[28](https://arxiv.org/html/2608.10619#bib.bib36)\]\. JDR jointly rewires the graph and denoises node features by aligning the leading spectral spaces of graph and feature matrices\[[22](https://arxiv.org/html/2608.10619#bib.bib37)\]\. In heterophilic graphs, DHGR modifies neighborhoods by adding homophilic edges and pruning heterophilic ones, and label\-guided rewiring further uses label information to improve the compatibility between graph structure and downstream classification\[[9](https://arxiv.org/html/2608.10619#bib.bib6),[12](https://arxiv.org/html/2608.10619#bib.bib8)\]\. These studies show that rewiring objectives benefit from structural signals that better match the role of the graph in downstream prediction\.

PairAlign keeps the criterion topology\-driven and uses topology to define a pair\-level shortage signal that brings node\-pair communication needs into the rewiring objective\. It frames rewiring as pair\-centric structural repair, where the target is a communication\-deficient node pair whose demand exceeds the support available under the current topology\. Its OT\-guided allocation assigns candidate additions to high\-shortage pairs under the finite budget, turning graph rewiring into a budgeted allocation problem for the pairwise communications most constrained by over\-squashing\.

## IIIMethods

### III\-APreliminaries

LetG=\(V,E,𝐇\)G=\(V,E,\\mathbf\{H\}\)be a graph with node setVV, edge setEE, and node feature matrix𝐇∈ℝn×d\\mathbf\{H\}\\in\\mathbb\{R\}^\{n\\times d\}, wheren=\|V\|n=\|V\|\. Set𝐇\(0\)=𝐇\\mathbf\{H\}^\{\(0\)\}=\\mathbf\{H\}, and lethu\(0\)h\_\{u\}^\{\(0\)\}denote itsuu\-th row\. The adjacency matrix ofGGis denoted by𝐀∈\{0,1\}n×n\\mathbf\{A\}\\in\\\{0,1\\\}^\{n\\times n\}\. For anyu,v∈Vu,v\\in V, letdG​\(u,v\)d\_\{G\}\(u,v\)denote the shortest\-path distance on the original graph\. We consider an add\-only rewiring setting\. LetE¯\\bar\{E\}denote the set of candidate non\-edges ofGG\. A rewiring solution is represented by a matrix𝐁∈ℝ≥0n×n\\mathbf\{B\}\\in\\mathbb\{R\}\_\{\\geq 0\}^\{n\\times n\}\. Its feasible set is

ℬ:=\{𝐁:𝐁=𝐁⊤,diag⁡\(𝐁\)=𝟎,supp⁡\(𝐁\)⊆E¯\}\.\\mathcal\{B\}:=\\bigl\\\{\\mathbf\{B\}:\\mathbf\{B\}=\\mathbf\{B\}^\{\\top\},\\ \\operatorname\{diag\}\(\\mathbf\{B\}\)=\\mathbf\{0\},\\ \\operatorname\{supp\}\(\\mathbf\{B\}\)\\subseteq\\bar\{E\}\\bigr\\\}\.\(1\)
For budgeted allocation, let𝒯\\mathcal\{T\}be the finite target\-pair set, letℰ⊆E¯\\mathcal\{E\}\\subseteq\\bar\{E\}be the finite candidate\-edge pool, and let𝐩∈Δ​\(𝒯\)\\mathbf\{p\}\\in\\Delta\(\\mathcal\{T\}\)be the shortage\-target distribution used by the allocation\. The added\-budget distribution induced by the edge\-addition variables is denoted by𝐪​\(𝐁\)∈Δ​\(ℰ\)\\mathbf\{q\}\(\\mathbf\{B\}\)\\in\\Delta\(\\mathcal\{E\}\)and is used as the source marginal over candidate added edges\.

The rewired graph is encoded by𝐖=𝐀\+𝐁\.\\mathbf\{W\}=\\mathbf\{A\}\+\\mathbf\{B\}\.Let𝐃\\mathbf\{D\}be the degree matrix of𝐖\\mathbf\{W\}\. The row\-normalized propagation matrix𝐏\\mathbf\{P\}on the rewired graph is defined as𝐏=𝐃−1​𝐖\.\\mathbf\{P\}=\\mathbf\{D\}^\{\-1\}\\mathbf\{W\}\.Let𝒫=\{\(u,v\)∈V×V:u≠v\}\\mathcal\{P\}=\\\{\(u,v\)\\in V\\times V:\\,u\\neq v\\\}denote the set of ordered node pairs\. Unless explicitly specified, all pairwise quantities in the sequel are indexed over𝒫\\mathcal\{P\}, and all distance\-based constraints are defined on the original graphGG\. At layerrr, a row\-normalized MPNN updates nodejjby

hj\(r\)=ϕr​\(hj\(r−1\),∑iPi​j​ψr​\(hi\(r−1\)\)\),h\_\{j\}^\{\(r\)\}=\\phi\_\{r\}\\left\(h\_\{j\}^\{\(r\-1\)\},\\sum\_\{i\}P\_\{ij\}\\psi\_\{r\}\(h\_\{i\}^\{\(r\-1\)\}\)\\right\),\(2\)whereψr\\psi\_\{r\}is the message map andϕr\\phi\_\{r\}is the update map\.

### III\-BPairwise Communication Shortage as a Demand–Support View of Over\-Squashing

Motivation\.Existing graph rewiring studies usually evaluate structural modifications through edge\-level bottlenecks, local geometric indicators, or graph\-level connectivity surrogates\. These criteria provide useful diagnoses of unfavorable graph structures\. Under a limited rewiring budget, the central decision is which node\-pair interactions should receive structural support\. From the perspective of over\-squashing, the constrained object is the communication between distant node pairs whose information exchange must pass through limited multi\-hop propagation pathways\. This observation motivates a pair\-centric view that allocates structural budget to node pairs whose communication demand is poorly supported by the current graph\. We introduce pairwise communication shortage as a demand\-support diagnostic for over\-squashing risk and use it to prioritize the node\-pair interactions that should be supported by rewiring\.

Formulation\.To make the pair\-centric view operational, PairAlign scores over\-squashing risk by comparing structural demand with propagation support for each node pair\. The demand term is fixed on the original graph and reflects how much structural communication the pair requires\. The support term is measured on the current computational graph and records how much finite\-hop propagation is available to that pair\. A large shortage marks a pair whose communication demand receives limited support from the current topology\. We use this score as a rewiring diagnostic for over\-squashing risk and first define the two quantities that enter it: pairwise communication demand and propagation support\.

###### Definition 1\(Pairwise Communication Demand\)\.

Let𝒫\\mathcal\{P\}denote the set of ordered node pairs\. The pairwise communication demand is the functionω:𝒫→ℝ≥0\\omega:\\mathcal\{P\}\\to\\mathbb\{R\}\_\{\\geq 0\}defined by

ω​\(u,v\)=dG​\(u,v\)p,\(u,v\)∈𝒫,\\omega\(u,v\)=d\_\{G\}\(u,v\)^\{p\},\\qquad\(u,v\)\\in\\mathcal\{P\},\(3\)wheredG​\(u,v\)d\_\{G\}\(u,v\)is the shortest\-path distance betweenuuandvvonGG, andp\>0p\>0controls the growth rate of communication demand with respect to distance\.

This definition captures the structural side of pairwise communication demand\. By assigning greater demand weights to distant node pairs, it brings to the foreground those interactions that rely more heavily on long\-range information exchange; under multi\-hop propagation, such interactions typically traverse longer transmission chains and are more vulnerable to compression caused by bottlenecks and information attenuation\[[3](https://arxiv.org/html/2608.10619#bib.bib28),[30](https://arxiv.org/html/2608.10619#bib.bib32)\]\. In this sense, the shortest\-path distance provides a natural topology\-based prior for long\-range pairwise communication demand\.

We now define the support side of the demand\-support diagnostic\. For a finite\-depth message passing model, communication fromuutovvcan only use propagation walks whose length is within the effective depth of the model\. PairAlign measures support by the finite\-hop propagation mass induced by the current computational graph\.

###### Definition 2\(Pairwise Propagation Support\)\.

Let𝐖\\mathbf\{W\}be a graph with propagation matrix𝐏\\mathbf\{P\}, let𝒫\\mathcal\{P\}denote the set of ordered node pairs, and letα1,…,αK∈ℝ≥0\\alpha\_\{1\},\\ldots,\\alpha\_\{K\}\\in\\mathbb\{R\}\_\{\\geq 0\}be nonnegative hop weights satisfying∑ℓ=1Kαℓ=1\\sum\_\{\\ell=1\}^\{K\}\\alpha\_\{\\ell\}=1\. The finite\-hop pairwise propagation support on𝐖\\mathbf\{W\}is the functions​\(⋅;𝐖\):𝒫→ℝ≥0s\(\\,\\cdot\\,;\\mathbf\{W\}\):\\mathcal\{P\}\\to\\mathbb\{R\}\_\{\\geq 0\}defined by

s​\(u,v;𝐖\)=∑ℓ=1Kαℓ​\[𝐏ℓ\]u​v,\(u,v\)∈𝒫\.s\(u,v;\\mathbf\{W\}\)=\\sum\_\{\\ell=1\}^\{K\}\\alpha\_\{\\ell\}\\,\[\\mathbf\{P\}^\{\\ell\}\]\_\{uv\},\\qquad\(u,v\)\\in\\mathcal\{P\}\.\(4\)

In the main method, PairAlign uses the uniform hop averageαℓ=1/K\\alpha\_\{\\ell\}=1/K\. Under this convention,s​\(u,v;𝐖\)s\(u,v;\\mathbf\{W\}\)measures the average propagation mass that can travel fromuutovvwithinKKmessage\-passing steps\. The following lemma gives the corresponding Jacobian bound\.

###### Lemma 1\(Support bounds normalized Jacobian influence\)\.

Consider theKK\-layer MPNN defined as Eq\. \([2](https://arxiv.org/html/2608.10619#S3.E2)\), and lethv\(ℓ\)h\_\{v\}^\{\(\\ell\)\}be the representation of nodevvat layerℓ=0,…,K\\ell=0,\\ldots,K\. Assume thatψr\\psi\_\{r\}is Lipschitz andϕr\\phi\_\{r\}is Lipschitz in its propagated\-message argument at each layerr=1,…,Kr=1,\\ldots,K, and letLrL\_\{r\}denote the corresponding layer Lipschitz constant\. For every ordered pair\(u,v\)∈𝒫\(u,v\)\\in\\mathcal\{P\}, the supports​\(u,v;𝐖\)s\(u,v;\\mathbf\{W\}\)upper bounds the normalized finite\-depth Jacobian influenceℐ​\(u,v\)\\mathcal\{I\}\(u,v\)as

ℐ​\(u,v\)=1K​∑ℓ=1K‖∂hv\(ℓ\)/∂hu\(0\)‖∏r=1ℓLr≤s​\(u,v;𝐖\)\.\\mathcal\{I\}\(u,v\)=\\frac\{1\}\{K\}\\sum\_\{\\ell=1\}^\{K\}\\frac\{\\left\\\|\\partial h\_\{v\}^\{\(\\ell\)\}/\\partial h\_\{u\}^\{\(0\)\}\\right\\\|\}\{\\prod\_\{r=1\}^\{\\ell\}L\_\{r\}\}\\leq s\(u,v;\\mathbf\{W\}\)\.

At the mechanism level, over\-squashing appears as weak influence between distant nodes after finite\-depth message passing\. This influence reflects the graph structure together with the MPNN model functions\. When the model functions are Lipschitz, Lemma[1](https://arxiv.org/html/2608.10619#Thmlemma1)isolates the structural side and shows that the finite\-hop propagation masss​\(u,v;𝐖\)s\(u,v;\\mathbf\{W\}\)is a structural upper bound on the normalized Jacobian influence\.

For a pair with large structural demandω​\(u,v\)\\omega\(u,v\), a small value ofs​\(u,v;𝐖\)s\(u,v;\\mathbf\{W\}\)means that the current graph leaves little finite\-depth influence available for this pairwise message passing, which indicates a higher risk of over\-squashing\. The shortage score serves as a diagnostic to record this mismatch between structural demand and support on the graph topology\. Overall, PairAlign ranks the resulting communication\-deficient pairs by the ratio below\.

###### Definition 3\(Pairwise Communication Shortage\)\.

For each ordered node pair\(u,v\)∈𝒫\(u,v\)\\in\\mathcal\{P\}, letω​\(u,v\)\\omega\(u,v\)denote its pairwise communication demand in Eq\. \([3](https://arxiv.org/html/2608.10619#S3.E3)\) and lets​\(u,v;𝐖\)s\(u,v;\\mathbf\{W\}\)denote its finite\-hop pairwise propagation support in Eq\. \([4](https://arxiv.org/html/2608.10619#S3.E4)\)\. The pairwise communication shortage on𝐖\\mathbf\{W\}is defined as the function𝒮​\(⋅;𝐖\):𝒫→ℝ≥0\\mathcal\{S\}\(\\,\\cdot\\,;\\mathbf\{W\}\):\\mathcal\{P\}\\to\\mathbb\{R\}\_\{\\geq 0\}given by

𝒮​\(u,v;𝐖\)=ω​\(u,v\)s​\(u,v;𝐖\)\+ε,\(u,v\)∈𝒫,\\mathcal\{S\}\(u,v;\\mathbf\{W\}\)=\\frac\{\\omega\(u,v\)\}\{s\(u,v;\\mathbf\{W\}\)\+\\varepsilon\},\\qquad\(u,v\)\\in\\mathcal\{P\},\(5\)whereε\>0\\varepsilon\>0is a small positive constant\.

For fixed\(u,v\)\(u,v\), we abbreviates​\(𝐖\)=s​\(u,v;𝐖\)s\(\\mathbf\{W\}\)=s\(u,v;\\mathbf\{W\}\)and𝒮​\(𝐖\)=𝒮​\(u,v;𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)=\\mathcal\{S\}\(u,v;\\mathbf\{W\}\)\. Under a fixed demand specification and propagation protocol,𝒮​\(𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)ranks node pairs by how much structural demand remains unsupported by finite\-hop propagation; larger values indicate pairs that should receive higher priority in shortage\-aware rewiring\. The Jacobian view of over\-squashing relates the problem to weak finite\-depth influence between nodes\. In graph rewiring, weak influence alone is not enough to rank repair priorities, since some weakly influenced pairs may require only limited structural communication\. A pair with large structural demand and weak normalized Jacobian influence reflects a more severe communication shortage\. We measure this shortage by the ratio between structural demand and normalized Jacobian influence, defined below as the Jacobian\-based shortage\. Proposition[1](https://arxiv.org/html/2608.10619#Thmproposition1)shows that the computable shortage used by PairAlign serves as a reasonable proxy for this Jacobian\-based ratio\.

###### Proposition 1\(Proxy of Jacobian\-based shortage\)\.

For a node pair\(u,v\)\(u,v\), suppose that the assumptions of Lemma[1](https://arxiv.org/html/2608.10619#Thmlemma1)hold\. Define the Jacobian\-based communication shortage by

𝒮Jac​\(𝐖\)=ω​\(u,v\)ℐ​\(u,v\)\+ε,\\mathcal\{S\}^\{\\rm Jac\}\(\\mathbf\{W\}\)=\\frac\{\\omega\(u,v\)\}\{\\mathcal\{I\}\(u,v\)\+\\varepsilon\},whereℐ​\(u,v\)\\mathcal\{I\}\(u,v\)is the normalized Jacobian influence in Lemma[1](https://arxiv.org/html/2608.10619#Thmlemma1)\. Then the following statements hold\.

*\(i\) Bottleneck lower bound\.*𝒮​\(𝐖\)≤𝒮Jac​\(𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)\\leq\\mathcal\{S\}^\{\\rm Jac\}\(\\mathbf\{W\}\)\.

*\(ii\) Constant\-factor equivalence in the non\-degenerate regime\.*Assume that the normalized Jacobian influence fromuutovvretains accfraction ofs​\(𝐖\)s\(\\mathbf\{W\}\), i\.e\.,ℐ​\(u,v\)≥c​s​\(𝐖\)\\mathcal\{I\}\(u,v\)\\geq c\\,s\(\\mathbf\{W\}\)withc∈\(0,1\]c\\in\(0,1\]\.𝒮​\(𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)and𝒮Jac​\(𝐖\)\\mathcal\{S\}^\{\\rm Jac\}\(\\mathbf\{W\}\)satisfy the following constant\-factor equivalence:

𝒮​\(𝐖\)≤𝒮Jac​\(𝐖\)≤c−1​𝒮​\(𝐖\)\.\\mathcal\{S\}\(\\mathbf\{W\}\)\\leq\\mathcal\{S\}^\{\\rm Jac\}\(\\mathbf\{W\}\)\\leq c^\{\-1\}\\mathcal\{S\}\(\\mathbf\{W\}\)\.

The non\-degenerate regime gives a sufficient setting for analyzing graph rewiring as a structural way to alleviate over\-squashing\. It assumes that the finite\-hop support supplied by the graph is not erased by the model functions, so topology changes can still improve the communication bottlenecks\. With this condition,𝒮​\(𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)and𝒮Jac​\(𝐖\)\\mathcal\{S\}^\{\\rm Jac\}\(\\mathbf\{W\}\)are equivalent up to a constant factor\. A large𝒮​\(𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)points to a node pair whose communication demand is high while the current graph provides limited finite\-hop support\. Thus, reducing the computable score𝒮​\(𝐖\)\\mathcal\{S\}\(\\mathbf\{W\}\)also reduces the corresponding Jacobian\-based shortage\. This makes the rewiring objective focus on the pairs most vulnerable to over\-squashing\.

Once the shortage score selects demand–support deficient pairs, we now consider how an edge insertion changes the support of those targets\. PairAlign acts on the graph through candidate edges and each edge is evaluated by its support change for a shortage target under the row\-normalized propagation matrix\. This effect is not monotone\. Adding a new neighbor creates walks through the new edge, while row normalization reallocates probability mass away from the original neighbors of the same row\. To make this local effect explicit, we consider the row updatee=a→be=a\\to binduced by the undirected candidate edge\{a,b\}\\\{a,b\\\}\. Forβ≥0\\beta\\geq 0, let𝐏β\\mathbf\{P\}\_\{\\beta\}denote the row\-normalized propagation matrix obtained after adding edge weightβ\\betato this row update, with𝐏0=𝐏\\mathbf\{P\}\_\{0\}=\\mathbf\{P\}\. The first\-order support changege​\(u,v\)g\_\{e\}\(u,v\)at the uninserted graph is

ge​\(u,v\)=dd​β​1K​∑ℓ=1K\[𝐏βℓ\]u​v\|β=0\+\.g\_\{e\}\(u,v\)=\\left\.\\frac\{d\}\{d\\beta\}\\frac\{1\}\{K\}\\sum\_\{\\ell=1\}^\{K\}\\left\[\\mathbf\{P\}\_\{\\beta\}^\{\\ell\}\\right\]\_\{uv\}\\right\|\_\{\\beta=0^\{\+\}\}\.
###### Proposition 2\(First\-order support change from edge insertion\)\.

Assume thatb∉N​\(a\)b\\notin N\(a\)before insertion and letdad\_\{a\}be the original row degree ofaa\. Fore=a→be=a\\to b, the first\-order finite\-hop support change of\(u,v\)\(u,v\)is

ge​\(u,v\)=Be​\(u,v\)−De​\(u,v\),g\_\{e\}\(u,v\)=B\_\{e\}\(u,v\)\-D\_\{e\}\(u,v\),where the added\-path contribution is

Be​\(u,v\)=1K​∑ℓ=1K∑i=1ℓ\[𝐏i\]u​a​\[𝐏ℓ−i\]b​vda,\\displaystyle B\_\{e\}\(u,v\)=\\frac\{1\}\{K\}\\sum\_\{\\ell=1\}^\{K\}\\sum\_\{i=1\}^\{\\ell\}\[\\mathbf\{P\}^\{i\}\]\_\{ua\}\\frac\{\[\\mathbf\{P\}^\{\\ell\-i\}\]\_\{bv\}\}\{d\_\{a\}\},and the normalization loss over the original neighbors ofaais

De​\(u,v\)=1K​∑ℓ=1K∑i=1ℓ\[𝐏i\]u​a​∑z∈N​\(a\)𝐏a​z​\[𝐏ℓ−i\]z​vda\.\\displaystyle D\_\{e\}\(u,v\)=\\frac\{1\}\{K\}\\sum\_\{\\ell=1\}^\{K\}\\sum\_\{i=1\}^\{\\ell\}\[\\mathbf\{P\}^\{i\}\]\_\{ua\}\\frac\{\\sum\_\{z\\in N\(a\)\}\\mathbf\{P\}\_\{az\}\[\\mathbf\{P\}^\{\\ell\-i\}\]\_\{zv\}\}\{d\_\{a\}\}\.HereBe​\(u,v\)B\_\{e\}\(u,v\)sums walks that reachaa, use the new stepa→ba\\to b, and continue tovv, whileDe​\(u,v\)D\_\{e\}\(u,v\)sums the mass removed from walks that would have continued through the original neighbors ofaa\. For the undirected insertion\{a,b\}\\\{a,b\\\}, the first\-order support change is the symmetrized quantityg\{a,b\}​\(u,v\)=ga→b​\(u,v\)\+gb→a​\(u,v\)g\_\{\\\{a,b\\\}\}\(u,v\)=g\_\{a\\to b\}\(u,v\)\+g\_\{b\\to a\}\(u,v\)\.

Proposition[2](https://arxiv.org/html/2608.10619#Thmproposition2)shows that an inserted edge does not simply add propagation support to a target pair\. The support increases only when the added\-path contribution exceeds the loss, namelyBe​\(u,v\)\>De​\(u,v\)B\_\{e\}\(u,v\)\>D\_\{e\}\(u,v\)\. An edge is useful only when it lowers shortage on the rewiring graph, not merely when it increases connectivity\. This view is consistent with evidence that more connectivity is not always preferable\[[18](https://arxiv.org/html/2608.10619#bib.bib3)\]\. PairAlign keeps optimizing shortage during rewiring to ensure the effectiveness of edge insertions\.

### III\-CPairAlign with OT\-Guided Communication Alignment for Shortage Reduction

Under a finite edge addition budget, graph rewiring needs a global allocation rule for assigning candidate edges to high\-shortage pairs\. This allocation must address two coupled issues\. High\-shortage pairs are not independent targets\. Several targets may rely on overlapping communication regions, and one candidate edge may affect multiple targets at once\. If edges are selected independently, as in Greedy\-Local, the budget can concentrate on targets that are easier to improve locally, leaving other shortage regions undercovered\. The allocation also needs to account for how well a candidate edge can serve the target pairs it is meant to support\. A candidate edge should be favored only when it can provide useful propagation support for the corresponding shortage pairs\.

To establish a pair\-level rewiring mechanism that captures both budget coverage and structural compatibility, PairAlign formulates the communication alignment between the candidate edge budget and the shortage targets as an Optimal Transport problem, as shown in Fig\.[2](https://arxiv.org/html/2608.10619#S3.F2)\. Drawing on the coupling view of Optimal Transport\[[33](https://arxiv.org/html/2608.10619#bib.bib13),[14](https://arxiv.org/html/2608.10619#bib.bib14)\], OT\-guided alignment treats the candidate edge budget as structural resources to be assigned and pairs with high shortage as targets that require support\. The transport cost measures how suitable a candidate edge is for supporting a given shortage target\. The optimal coupling gives the allocation solution by matching the finite candidate\-edge budget to the shortage targets with minimum total transport cost\. As a result, structural resources are preferentially assigned to node pairs that both need support and can be effectively served by the selected candidates\.

![Refer to caption](https://arxiv.org/html/2608.10619v1/x2.png)Figure 2:PairAlign rewiring mechanism\. PairAlign rewires a graph by aligning limited edge additions with pairwise communication shortages\. \(a\) The method constructs a shortage\-target distribution over communication\-deficient node pairs, and defines a candidate\-edge budget to represent the limited structural resources available for repair\. \(b\) OT\-guided alignment solves for a coupling between candidate edges and shortage targets under a transport cost that balances structural compatibility and target coverage\. \(c\) The optimization loop updates candidate\-edge scores, re\-evaluates shortage on the current rewired graph, and feeds this signal back into edge selection\. After discrete projection, the selected setEaddE\_\{\\mathrm\{add\}\}forms𝐖=𝐀\+𝐁\\mathbf\{W\}=\\mathbf\{A\}\+\\mathbf\{B\}\. By assigning limited rewiring capacity to communication\-deficient node pairs, PairAlign strengthens message passing and alleviates over\-squashing\.Formulation of OT\-guided Alignment\.Under this view, PairAlign aligns the added\-budget distribution𝐪​\(𝐁\)\\mathbf\{q\}\(\\mathbf\{B\}\)with the shortage distribution𝐩\\mathbf\{p\}on the original graph under a transport cost𝐂\\mathbf\{C\}that encodes their structural compatibility\. The corresponding OT problem is defined as Eq\. \([6](https://arxiv.org/html/2608.10619#S3.E6)\) and the optimal coupling𝚪⋆\\mathbf\{\\Gamma\}^\{\\star\}characterizes the cost\-compatible allocation,

𝚪⋆=arg⁡min𝚪∈Π​\(𝐪​\(𝐁\),𝐩\)⁡⟨𝚪,𝐂⟩−ε​H​\(𝚪\),\\mathbf\{\\Gamma\}^\{\\star\}=\\arg\\min\_\{\\mathbf\{\\Gamma\}\\in\\Pi\(\\mathbf\{q\}\(\\mathbf\{B\}\),\\mathbf\{p\}\)\}\\;\\langle\\mathbf\{\\Gamma\},\\mathbf\{C\}\\rangle\-\\varepsilon H\(\\mathbf\{\\Gamma\}\),\(6\)whereΠ​\(𝐪​\(𝐁\),𝐩\)=\{𝚪i​j≥0,∀i,j∣𝚪​𝟏=𝐪​\(𝐁\),𝚪⊤​𝟏=𝐩\}\\Pi\(\\mathbf\{q\}\(\\mathbf\{B\}\),\\mathbf\{p\}\)=\\\{\\mathbf\{\\Gamma\}\_\{ij\}\\geq 0,\\forall i,j\\mid\\mathbf\{\\Gamma\}\\mathbf\{1\}=\\mathbf\{q\}\(\\mathbf\{B\}\),\\;\\mathbf\{\\Gamma\}^\{\\top\}\\mathbf\{1\}=\\mathbf\{p\}\\\}, andH​\(𝚪\)=−∑i,jΓi​j​\(log⁡Γi​j−1\)H\(\\mathbf\{\\Gamma\}\)=\-\\sum\_\{i,j\}\\Gamma\_\{ij\}\(\\log\\Gamma\_\{ij\}\-1\)is the entropy regularizer\. The construction of PairAlign involves three key components, namely the added\-budget distribution𝐪​\(𝐁\)\\mathbf\{q\}\(\\mathbf\{B\}\), the shortage distribution𝐩\\mathbf\{p\}, and the transport geometry𝐂\\mathbf\{C\}\.

Here,𝐪​\(𝐁\)\\mathbf\{q\}\(\\mathbf\{B\}\)denotes the distribution over candidate added edges induced by the current edge\-addition variables𝐁\\mathbf\{B\}\. It represents how the finite added structural budget is placed over candidate non\-edges before alignment and is used as the source marginal in the OT problem\.

To make the shortage target more concentrated, PairAlign starts from the pairwise shortage of the original graph and derives a target distribution𝐩\\mathbf\{p\}by centering it against the graph\-wide baseline\. This centering gives more weight to severe communication shortages\. Specifically, the base shortage\{𝒮u​v\}\(u,v\)∈𝒫\\\{\\mathcal\{S\}\_\{uv\}\\\}\_\{\(u,v\)\\in\\mathcal\{P\}\}on the original graph is obtained from Eq\. \([5](https://arxiv.org/html/2608.10619#S3.E5)\) with𝐖=𝐀\\mathbf\{W\}=\\mathbf\{A\}\. This pattern contains both graph\-wide background shortage and genuinely prominent shortage mass\. Directly using the raw shortage pattern would spread the budget over many mildly deficient pairs and make the severe regions less visible\. We use a simple construction adapted to the graph in which the original shortage is centered relative to a graph\-level baseline and only the positive excessp~u​v=max⁡\(𝒮u​v−\|𝒫\|−1​∑\(a,b\)∈𝒫𝒮a​b,0\)\\tilde\{p\}\_\{uv\}=\\max\(\\mathcal\{S\}\_\{uv\}\-\|\\mathcal\{P\}\|^\{\-1\}\\sum\_\{\(a,b\)\\in\\mathcal\{P\}\}\\mathcal\{S\}\_\{ab\},\\,0\)is retained\. The corresponding shortage target distribution is then

defined by

𝐩=\(pu​v\)\(u,v\)∈𝒫,wherepu​v=p~u​v∑\(a,b\)∈𝒫p~a​b\.\\mathbf\{p\}=\(p\_\{uv\}\)\_\{\(u,v\)\\in\\mathcal\{P\}\},\\quad\\operatorname\{where\}\\quad p\_\{uv\}=\\frac\{\\tilde\{p\}\_\{uv\}\}\{\\sum\_\{\(a,b\)\\in\\mathcal\{P\}\}\\tilde\{p\}\_\{ab\}\}\.\(7\)
In PairAlign, the transport cost matrix𝐂\\mathbf\{C\}captures the structural match between candidate added edges and target shortage pairs\. For any candidate added edgee=\(a,b\)e=\(a,b\)and target pair\(u,v\)\(u,v\), the costCe,\(u,v\)C\_\{e,\(u,v\)\}has two parts\. Endpoint alignment measures whether the edge can connect the source side of the target pair to its target side, while bridge suitability measures whether the span of the candidate edge is commensurate with the scale of the shortage pair\. Based on this design, the transport cost is defined by

C\(a,b\),\(u,v\)=\\displaystyle C\_\{\(a,b\),\(u,v\)\}=\{\}min⁡\{d​\(a,u\)\+d​\(b,v\),d​\(a,v\)\+d​\(b,u\)\}⏟endpoint alignment\\displaystyle\\underbrace\{\\begin\{aligned\} \\min\\bigl\\\{\\,d\(a,u\)\+d\(b,v\),d\(a,v\)\+d\(b,u\)\\,\\bigr\\\}\\end\{aligned\}\}\_\{\{\\text\{endpoint alignment\}\}\}−λ​ψ​\(d​\(a,b\)d​\(u,v\)\+ε\)⏟bridge suitability,\\displaystyle\\quad\-\\underbrace\{\\lambda\\psi\\\!\\left\(\\frac\{d\(a,b\)\}\{d\(u,v\)\+\\varepsilon\}\\right\)\}\_\{\{\\text\{bridge suitability\}\}\},\(8\)whereλ\>0\\lambda\>0controls the strength of the bridge reward andψ​\(⋅\)\\psi\(\\cdot\)is a monotone increasing function\. The endpoint\-alignment term measures how well a feasible candidate edge is positioned with respect to the two sides of a target pair\. For a single target pair\(u,v\)\(u,v\), the direct shortcut\(u,v\)\(u,v\), if feasible, is naturally one of the most strongly aligned candidates\. PairAlign does not exclude this case\. At the graph level, the goal is not to add one direct shortcut for each pair with high shortage, but to select a finite set of added edges that can support many shortage targets under a limited budget\. The transport cost is used to evaluate the structural fit between each feasible candidate edge and each shortage target\. The bridge\-suitability term complements the endpoint score by considering the scale of the candidate edge\. Among candidates with similar endpoint alignment, an edge whose span covers a larger normalized portion of the original pairwise distance receives a lower cost\. In this way, the matrix𝐂\\mathbf\{C\}provides a support\-aware geometry for OT allocation\. It favors candidate edges that are well positioned for a shortage pair and have a span suitable for supporting that pair under the finite edge budget\. If each unit of candidate\-edge budget is assigned independently to its cheapest target, the induced target marginal follows the cost\-induced preference instead of the shortage distribution𝐩\\mathbf\{p\}\. Part of the high\-shortage target set can then remain uncovered\. Proposition[3](https://arxiv.org/html/2608.10619#Thmproposition3)formalizes the coverage advantage of shortage alignment\. OT alignment addresses it by solving a minimum\-cost global allocation with prescribed added edge and shortage target marginals\. By keeping the allocation aligned with pairs with high shortage, the selected edges provide more effective structural repair under the same budget\.

###### Proposition 3\(Coverage advantage over greedy target assignment\)\.

Letℰ=\{e1,…,eM\}\\mathcal\{E\}=\\\{e\_\{1\},\\ldots,e\_\{M\}\\\}be the candidate\-edge set and𝒯=\{t1,…,tm\}\\mathcal\{T\}=\\\{t\_\{1\},\\ldots,t\_\{m\}\\\}be the set of shortage target pairs; writet∈𝒯t\\in\\mathcal\{T\}for one target pair\. Let𝐩∈Δ​\(𝒯\)\\mathbf\{p\}\\in\\Delta\(\\mathcal\{T\}\)be the shortage\-target distribution,𝐪​\(𝐁\)∈Δ​\(ℰ\)\\mathbf\{q\}\(\\mathbf\{B\}\)\\in\\Delta\(\\mathcal\{E\}\)be the added\-budget distribution\. LetE1,…,EnE\_\{1\},\\ldots,E\_\{n\}be drawn independently from𝐪​\(𝐁\)\\mathbf\{q\}\(\\mathbf\{B\}\)\.

For eache∈ℰe\\in\\mathcal\{E\}, define the greedy target mapgC:ℰ→𝒯g\_\{C\}:\\mathcal\{E\}\\to\\mathcal\{T\}and its induced target distribution by

gC​\(e\)=arg⁡mint∈𝒯⁡Ce,t,πC𝐁​\(t\)=∑e∈ℰqe​\(𝐁\)​𝟏​\{gC​\(e\)=t\}\.g\_\{C\}\(e\)=\\arg\\min\_\{t\\in\\mathcal\{T\}\}C\_\{e,t\},\\qquad\\pi\_\{C\}^\{\\mathbf\{B\}\}\(t\)=\\sum\_\{e\\in\\mathcal\{E\}\}q\_\{e\}\(\\mathbf\{B\}\)\\mathbf\{1\}\\\{g\_\{C\}\(e\)=t\\\}\.Let𝚪g∈ℝ\+n×m\\mathbf\{\\Gamma\}^\{g\}\\in\\mathbb\{R\}\_\{\+\}^\{n\\times m\}be the empirical greedy coupling over the realized edge budgets, where𝚪i,tg=n−1​𝟏​\{gC​\(Ei\)=t\}\\mathbf\{\\Gamma\}^\{g\}\_\{i,t\}=n^\{\-1\}\\mathbf\{1\}\\\{g\_\{C\}\(E\_\{i\}\)=t\\\}\. Letr𝚪gr\_\{\\mathbf\{\\Gamma\}^\{g\}\}be its target marginal\. Define shortage\-target coverage by

Cov𝐩​\(Γ\)=∑t∈𝒯min⁡\{rΓ​\(t\),pt\}\.\\mathrm\{Cov\}\_\{\\mathbf\{p\}\}\(\\Gamma\)=\\sum\_\{t\\in\\mathcal\{T\}\}\\min\\\{r\_\{\\Gamma\}\(t\),p\_\{t\}\\\}\.Let𝚪OT\\mathbf\{\\Gamma\}^\{\\rm OT\}be any OT coupling over the same realized budget units with target marginal𝐩\\mathbf\{p\}, namelyΓOT∈Πn​\(𝐩\)\\Gamma^\{\\rm OT\}\\in\\Pi\_\{n\}\(\\mathbf\{p\}\), where

Πn​\(𝐩\)=\{𝚪≥0:𝚪​𝟏=n−1​𝟏,𝚪⊤​𝟏=𝐩\}\.\\Pi\_\{n\}\(\\mathbf\{p\}\)=\\\{\\mathbf\{\\Gamma\}\\geq 0:\\mathbf\{\\Gamma\}\\mathbf\{1\}=n^\{\-1\}\\mathbf\{1\},\\ \\mathbf\{\\Gamma\}^\{\\top\}\\mathbf\{1\}=\\mathbf\{p\}\\\}\.ThenCov𝐩​\(ΓOT\)=1\\mathrm\{Cov\}\_\{\\mathbf\{p\}\}\(\\Gamma^\{\\rm OT\}\)=1\. Moreover, for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

Cov𝐩​\(𝚪OT\)−Cov𝐩​\(𝚪g\)≥TV​\(πC𝐁,𝐩\)−\|𝒯\|2​log⁡\(2​\|𝒯\|/δ\)2​n\.\\mathrm\{Cov\}\_\{\\mathbf\{p\}\}\(\\mathbf\{\\Gamma\}^\{\\rm OT\}\)\-\\mathrm\{Cov\}\_\{\\mathbf\{p\}\}\(\\mathbf\{\\Gamma\}^\{g\}\)\\geq\\mathrm\{TV\}\(\\pi\_\{C\}^\{\\mathbf\{B\}\},\\mathbf\{p\}\)\-\\frac\{\|\\mathcal\{T\}\|\}\{2\}\\sqrt\{\\frac\{\\log\(2\|\\mathcal\{T\}\|/\\delta\)\}\{2n\}\}\.

Proposition[3](https://arxiv.org/html/2608.10619#Thmproposition3)explains the necessity of OT\-guided allocation\. Under the randomized finite\-sample view, Greedy\-Local maps each sampled candidate edge to its lowest cost target, so the induced target distributionπC𝐁\\pi\_\{C\}^\{\\mathbf\{B\}\}may drift away from the𝐩\\mathbf\{p\}and leave some shortage mass uncovered\. Proposition[3](https://arxiv.org/html/2608.10619#Thmproposition3)shows that, with high probability, the coverage gain of OT over Greedy\-Local is controlled byTV​\(πC𝐁,𝐩\)\\mathrm\{TV\}\(\\pi\_\{C\}^\{\\mathbf\{B\}\},\\mathbf\{p\}\)up to a finite\-sample error term\. OT introduces coordination across edge budgets by matching the shortage marginal, preventing the finite budget from collapsing onto a few targets\. This coordinated allocation helps PairAlign turn limited edge additions into targeted shortage reduction and alleviate over\-squashing more effectively\.

Total Rewiring Objective of PairAlign\.The goal of rewiring in PairAlign is to reduce pairwise communication shortage under a limited structural budget\. OT\-guided allocation controls how structural additions are deployed\. The overall objective combines two terms\. The first term measures the focused pairwise shortage on the rewired graph\. Following Proposition[2](https://arxiv.org/html/2608.10619#Thmproposition2), this term checks whether the selected insertions increase finite\-hop support after row normalization, and encourages rewiring to reduce the residual demand–support mismatch of high\-shortage pairs,

Lshortage​\(𝐖\)=∑\(u,v\)∈𝒫pu​v​𝒮u​v​\(𝐖\)\.L\_\{\\mathrm\{shortage\}\}\(\\mathbf\{W\}\)=\\sum\_\{\(u,v\)\\in\\mathcal\{P\}\}p\_\{uv\}\\,\\mathcal\{S\}\_\{uv\}\(\\mathbf\{W\}\)\.\(9\)
The second term is the OT\-guided rewiring term introduced above\. The optimal coupling𝚪⋆\\mathbf\{\\Gamma\}^\{\\star\}represents how candidate added edges should be matched to shortage pairs\. Minimizing the OT\-guided alignment term yields an allocation with global structural compatibility, defined by

LOT​\(𝐁\)=minΓ∈Γ​\(𝐪add​\(𝐁\),𝐩\)⁡⟨Γ,𝐂⟩−ε​H​\(Γ\)\.L\_\{\\mathrm\{OT\}\}\(\\mathbf\{B\}\)=\\min\_\{\\Gamma\\in\\Gamma\(\\mathbf\{q\}\_\{\\mathrm\{add\}\}\(\\mathbf\{B\}\),\\mathbf\{p\}\)\}\\;\\langle\\Gamma,\\mathbf\{C\}\\rangle\-\\varepsilon H\(\\Gamma\)\.\(10\)
In all, the total objective of PairAlign is defined by combining shortage reduction with OT\-guided alignment,

min𝐁Lshortage​\(𝐀\+𝐁\)\+λOT​LOT​\(𝐁\)\.\\min\_\{\\mathbf\{B\}\}\\quad L\_\{\\mathrm\{shortage\}\}\(\\mathbf\{A\}\+\\mathbf\{B\}\)\+\\lambda\_\{\\mathrm\{OT\}\}L\_\{\\mathrm\{OT\}\}\(\\mathbf\{B\}\)\.\(11\)

### III\-DOptimization and Computational Complexity

Algorithm 1The PairAlign Rewiring0:Original graph

G=\(V,E,𝐇\)G=\(V,E,\\mathbf\{H\}\), candidate non\-edge set

E¯\\bar\{E\}, add budget

kk, propagation depth

KK, temperature

τ\\tau, optimization steps

ToptT\_\{\\mathrm\{opt\}\}
0:Discrete added\-edge set

EaddE\_\{\\mathrm\{add\}\}
1:Phase I: Construct pairwise shortage\-aware targets\.

2:Compute pairwise demand

ωu​v\\omega\_\{uv\}for

\(u,v\)∈𝒫\(u,v\)\\in\\mathcal\{P\};

3:Compute original pairwise shortage

𝒮u​v\\mathcal\{S\}\_\{uv\}on

𝐀\\mathbf\{A\}and construct target weights

pu​vp\_\{uv\};

4:Initialize candidate logits

\{θe\}e∈E¯\\\{\\theta\_\{e\}\\\}\_\{e\\in\\bar\{E\}\};

5:Phase II: Optimize budgeted near\-discrete selection\.

6:for

t=1t=1to

ToptT\_\{\\mathrm\{opt\}\}do

7:Compute soft edge scores

ze=softmax\(𝜽/τ\)ez\_\{e\}=\\operatorname\{softmax\}\(\\bm\{\\theta\}/\\tau\)\_\{e\};

8:Select the top\-

kkcandidates by a hard mask in the forward pass

9:Form

𝐖\(t\)=𝐀\+𝐁\(t\)\\mathbf\{W\}^\{\(t\)\}=\\mathbf\{A\}\+\\mathbf\{B\}^\{\(t\)\};

10:Evaluate pairwise supports

s​\(𝐖\(t\)\)s\(\\mathbf\{W\}^\{\(t\)\}\);

11:Compute focused shortage

Lshortage​\(𝐖\(t\)\)L\_\{\\mathrm\{shortage\}\}\(\\mathbf\{W\}^\{\(t\)\}\);

12:Construct

𝐪add​\(𝐁\(t\)\)\\mathbf\{q\}\_\{\\mathrm\{add\}\}\(\\mathbf\{B\}^\{\(t\)\}\)and evaluate

LOT​\(𝐁\(t\)\)L\_\{\\mathrm\{OT\}\}\(\\mathbf\{B\}^\{\(t\)\}\);

13:Update

𝜽\\bm\{\\theta\}by minimizing Eq\. \([11](https://arxiv.org/html/2608.10619#S3.E11)\) using a straight\-through style gradient approximation;

14:endfor

15:Phase III: Project to the final discrete rewiring

16:Rank candidate non\-edges by the optimized scores;

17:Form a projection pool from the top\-ranked candidates;

18:Select

EaddE\_\{\\mathrm\{add\}\}from the pool by re\-evaluating Eq\. \([11](https://arxiv.org/html/2608.10619#S3.E11)\) under the add budget;

19:return

EaddE\_\{\\mathrm\{add\}\}

Optimization\.The PairAlign rewiring induced in Eq\. \([11](https://arxiv.org/html/2608.10619#S3.E11)\) amounts to choosing a finite subset of added edges from the candidate non\-edge setE¯\\bar\{E\}, which makes the optimization combinatorial\. The candidate non\-edge setE¯\\bar\{E\}specifies the feasible locations for edge addition, while𝐁\\mathbf\{B\}is the decision matrix supported onE¯\\bar\{E\}, with each nonzero entryBu​vB\_\{uv\}representing the strength or selection of the added edge\(u,v\)\(u,v\)\. Direct optimization over such discrete edge subsets is intractable in general\. To address this, we introduce a continuous parameterization that yields a differentiable approximation while remaining consistent with the final discrete rewiring\. In all, the PairAlign procedure in Alg\.[1](https://arxiv.org/html/2608.10619#alg1)consists of three stages: shortage\-aware pairwise target construction, budgeted near\-discrete rewiring, and final projection to the discrete added\-edge set\.

Specifically, Optimization is carried out over continuous logits on candidate non\-edges\. Let𝜽=\{θe\}e∈E¯\\bm\{\\theta\}=\\\{\\theta\_\{e\}\\\}\_\{e\\in\\bar\{E\}\}denote the collection of all logits\. The logits are initialized uniformly, e\.g\.,θe=0\\theta\_\{e\}=0for all candidate edges\. Letze=softmax\(𝜽/τ\)ez\_\{e\}=\\operatorname\{softmax\}\(\\bm\{\\theta\}/\\tau\)\_\{e\}be the corresponding soft selection probability under temperatureτ\>0\\tau\>0\. During optimization, under an add\-only rewiring budget ofkkedges, a top\-kkhard mask is applied in the forward pass so that only the highest\-scoring candidate edges contribute to the current rewiring matrix, with reduced forward computation\. In the backward pass, gradients are propagated through the corresponding soft variables by a straight\-through style approximation\[[8](https://arxiv.org/html/2608.10619#bib.bib41)\]\. This yields a near\-discrete training procedure that remains compatible with gradient\-based optimization while staying close to the target discrete add\-only rewiring problem\. This objective implements the feedback loop in Fig\.[2](https://arxiv.org/html/2608.10619#S3.F2)\. Updates to𝐁\\mathbf\{B\}change the rewired graph𝐖=𝐀\+𝐁\\mathbf\{W\}=\\mathbf\{A\}\+\\mathbf\{B\}, the shortage term re\-evaluates finite\-hop support on the current graph, and the OT term keeps the edge budget aligned with the shortage targets\.

After optimization, the learned candidate scores are converted into a discrete rewiring set through a projection step\. Candidate non\-edges are first ranked by their optimized scores, and a projection pool is formed from the top\-ranked entries\. The final rewiring set is then selected from this pool under the prescribed add budget by re\-evaluating the main objective Eq\. \([11](https://arxiv.org/html/2608.10619#S3.E11)\) after optimization\. In this way, the final output is a discrete added\-edge set, while the training and projection stages remain aligned under a common objective\.

Computational Complexity\.The computational cost of PairAlign mainly comes from truncated propagation evaluation, OT\-based alignment, and candidate ranking\. LetMMbe the number of focused target pairs\. The one\-time construction of the shortage target distribution is a preprocessing cost before the optimization loop\. The full sorting of candidate non\-edges costs𝒪​\(\|E¯\|​log⁡\|E¯\|\)\\mathcal\{O\}\(\|\\bar\{E\}\|\\log\|\\bar\{E\}\|\)per step\. Dense Sinkhorn alignment over candidate edges and target pairs costs𝒪​\(TOT​\|E¯\|​M\)\\mathcal\{O\}\(T\_\{\\mathrm\{OT\}\}\|\\bar\{E\}\|M\)per step\[[14](https://arxiv.org/html/2608.10619#bib.bib14),[4](https://arxiv.org/html/2608.10619#bib.bib18)\]\. The overall optimization complexity is𝒪​\(Topt​\(\|E¯\|​log⁡\|E¯\|\+TOT​\|E¯\|​M\)\)\.\\mathcal\{O\}\\\!\\left\(T\_\{\\mathrm\{opt\}\}\\bigl\(\|\\bar\{E\}\|\\log\|\\bar\{E\}\|\+T\_\{\\mathrm\{OT\}\}\|\\bar\{E\}\|M\\bigr\)\\right\)\.If the implementation restricts Sinkhorn alignment to the candidates retained by the hard top\-kkmask, the factor\|E¯\|\|\\bar\{E\}\|in the OT term is replaced by at mostkk\. After optimization, the final candidate scores are ranked once more, adding another𝒪​\(\|E¯\|​log⁡\|E¯\|\)\\mathcal\{O\}\(\|\\bar\{E\}\|\\log\|\\bar\{E\}\|\)cost\. The final projection is performed on a small projection pool, so the exact reevaluation of feasiblekk\-subsets remains a low\-cost post\-processing step\. PairAlign is used as an offline rewiring preprocessor, so this cost is incurred once before downstream message\-passing model training\. A broader comparison with representative rewiring methods is provided in the supplementary appendix\.

TABLE I:Node classification accuracy \(%\) on six datasets under different rewiring methods and backbones\.The average ranking \(AR\) reflects the mean position of each method across all datasets\.

## IVExperiments

### IV\-AExperimental Setup

The experimental study compares PairAlign \(PAR\) with representative preprocessing\-based graph rewiring baselines covering the main design families in the literature\. Specifically, we include curvature\-driven methods, namely SDRF\[[30](https://arxiv.org/html/2608.10619#bib.bib32)\]and BORF\[[24](https://arxiv.org/html/2608.10619#bib.bib30)\]; spectral or global\-connectivity methods, including FoSR\[[19](https://arxiv.org/html/2608.10619#bib.bib33)\], the effective resistance\-based rewiring method GTR\[[10](https://arxiv.org/html/2608.10619#bib.bib25)\], and GOKU\[[21](https://arxiv.org/html/2608.10619#bib.bib35)\]; and the locality\-aware sparse rewiring method LASER\[[7](https://arxiv.org/html/2608.10619#bib.bib34)\]\. For the heterophilic benchmarks, we further compare with two recent variants that extend rewiring beyond purely structural criteria, namely JDR\[[22](https://arxiv.org/html/2608.10619#bib.bib37)\], which couples graph rewiring with feature denoising, and ComFy\[[28](https://arxiv.org/html/2608.10619#bib.bib36)\], which guides rewiring using community structure and feature similarity\. For each backbone, we also report the corresponding model on the original graph as the no\-rewiring baseline\. Across all tables, boldface denotes the best result and underline denotes the second\-best result\.

The benchmarks are organized into three groups\. The first group contains widely used real\-world node classification datasets: the citation networks Cora and CiteSeer\[[36](https://arxiv.org/html/2608.10619#bib.bib38)\], the web graphs Texas, Cornell, and Wisconsin\[[25](https://arxiv.org/html/2608.10619#bib.bib39)\], and the Wikipedia\-network dataset Chameleon\[[27](https://arxiv.org/html/2608.10619#bib.bib40)\]\. The second group contains the standard TUDataset graph classification benchmarks ENZYMES, IMDB\-BINARY, MUTAG, PROTEINS, REDDIT\-BINARY, and COLLAB\[[23](https://arxiv.org/html/2608.10619#bib.bib42)\]\. The third group contains five heterophilic node classification benchmarks from Platonov et al\.\[[26](https://arxiv.org/html/2608.10619#bib.bib22)\]: Roman\-Empire, Amazon\-Ratings, Minesweeper, Tolokers, and Questions\. Following the standard evaluation protocols of these benchmarks, performance is reported in classification accuracy for the first group and for Roman\-Empire and Amazon\-Ratings, and in ROC AUC for Minesweeper, Tolokers, and Questions\. Detailed dataset statistics, split protocols, and implementation settings are provided in the appendix\.

For the standard node classification and graph classification benchmarks, we consider two widely used message\-passing backbones, namely GCN\[[20](https://arxiv.org/html/2608.10619#bib.bib27)\]and GIN\[[35](https://arxiv.org/html/2608.10619#bib.bib43)\]\. For the heterophilic node classification benchmarks, we use GCN\[[20](https://arxiv.org/html/2608.10619#bib.bib27)\]and GAT\[[32](https://arxiv.org/html/2608.10619#bib.bib23)\]\. Within each benchmark family, all rewiring methods are evaluated under the same backbone, data split, and training protocol unless otherwise stated, so that performance differences can be attributed to the rewiring strategy rather than to backbone\-specific tuning\. Rewiring is treated as a structural preprocessing step, after which the downstream message\-passing model is trained on the rewired graph using an otherwise identical optimization pipeline across competing methods\. This protocol is designed to isolate the contribution of rewiring to both graph structure and downstream prediction\.

### IV\-BEvaluation Protocol

We evaluate rewiring from two complementary perspectives, downstream prediction performance and structural rewiring quality\. For downstream prediction performance, the primary metric follows the native evaluation protocol of each benchmark family\. Classification accuracy is reported on node classification and graph classification datasets\. We state the exact evaluation implementation in Appendix and report results under that protocol for reproducibility\.

Beyond downstream accuracy, we evaluate how rewiring changes the communication structure of the graph\. We report two pair\-centric diagnostics,Δ\\DeltaShortage and Coverage@10, to inspect whether the added edges repair pairs with high shortage\. Effective resistance proxies provide external references for pairwise and global communication bottlenecks\.

Based on the pair\-shortage𝒮u​v\\mathcal\{S\}\_\{uv\}in Eq\. \([5](https://arxiv.org/html/2608.10619#S3.E5)\) and the normalized shortage weightpu​vp\_\{uv\}in Eq\. \([7](https://arxiv.org/html/2608.10619#S3.E7)\) on the computational graph𝐖\\mathbf\{W\}, we measure the relative reduction of shortage on the rewired graph𝐖′\\mathbf\{W\}^\{\\prime\}by

Δ​Shortage=∑\(u,v\)∈𝒯pu​v​\[𝒮u​v​\(𝐖\)−𝒮u​v​\(𝐖′\)\]∑\(u,v\)∈𝒯pu​v​𝒮u​v​\(𝐖\)\+ε\.\\Delta\\mathrm\{Shortage\}=\\frac\{\\sum\_\{\(u,v\)\\in\\mathcal\{T\}\}p\_\{uv\}\\left\[\\mathcal\{S\}\_\{uv\}\(\\mathbf\{W\}\)\-\\mathcal\{S\}\_\{uv\}\(\\mathbf\{W\}^\{\\prime\}\)\\right\]\}\{\\sum\_\{\(u,v\)\\in\\mathcal\{T\}\}p\_\{uv\}\\mathcal\{S\}\_\{uv\}\(\\mathbf\{W\}\)\+\\varepsilon\}\.A larger value indicates stronger repair of the originally underserved pairs\. Coverage@10 measures how broadly this repair reaches the most severe shortage region\. Let𝒯10⊂𝒯\\mathcal\{T\}\_\{10\}\\subset\\mathcal\{T\}be the top 10% pairs ranked by𝒮u​v​\(𝐖\)\\mathcal\{S\}\_\{uv\}\(\\mathbf\{W\}\)\. We compute

Coverage​@​10=1\|𝒯10\|​∑\(u,v\)∈𝒯10𝕀​\[su​v​\(𝐖′\)−su​v​\(𝐖\)\>η\],\\mathrm\{Coverage@10\}=\\frac\{1\}\{\|\\mathcal\{T\}\_\{10\}\|\}\\sum\_\{\(u,v\)\\in\\mathcal\{T\}\_\{10\}\}\\mathbb\{I\}\\left\[s\_\{uv\}\(\\mathbf\{W\}^\{\\prime\}\)\-s\_\{uv\}\(\\mathbf\{W\}\)\>\\eta\\right\],whereη\\etais a small numerical tolerance\. The valueΔ\\DeltaShortage measures the amount of targeted repair, and Coverage@10 measures the fraction of top shortage pairs that receive nontrivial support\.

We further report effective resistance proxies to relate our diagnostics to established bottleneck measures\[[10](https://arxiv.org/html/2608.10619#bib.bib25)\]\. For a pair\(u,v\)\(u,v\), the pairwise effective resistance is

PERG​\(u,v\)=\(𝐞u−𝐞v\)⊤​LG†​\(𝐞u−𝐞v\),\\mathrm\{PER\}\_\{G\}\(u,v\)=\(\\mathbf\{e\}\_\{u\}\-\\mathbf\{e\}\_\{v\}\)^\{\\top\}L\_\{G\}^\{\\dagger\}\(\\mathbf\{e\}\_\{u\}\-\\mathbf\{e\}\_\{v\}\),whereLG†L\_\{G\}^\{\\dagger\}is the Moore–Penrose pseudoinverse of the graph Laplacian, and𝐞u,𝐞v∈ℝ\|V\|\\mathbf\{e\}\_\{u\},\\mathbf\{e\}\_\{v\}\\in\\mathbb\{R\}^\{\|V\|\}are the standard basis vectors associated with nodesuuandvv, respectively\. At the graph level, we use total effective resistance,

TER​\(G\)=∑u<vPERG​\(u,v\)=\|V\|​∑i=2\|V\|1λi​\(LG\)\.\\mathrm\{TER\}\(G\)=\\sum\_\{u<v\}\\mathrm\{PER\}\_\{G\}\(u,v\)=\|V\|\\sum\_\{i=2\}^\{\|V\|\}\\frac\{1\}\{\\lambda\_\{i\}\(L\_\{G\}\)\}\.Here,λi​\(LG\)\\lambda\_\{i\}\(L\_\{G\}\)is theii\-th eigenvalue ofLGL\_\{G\}\. Lower PER or TER indicates smaller effective resistance and stronger communication connectivity\. We report the relative reductions of PER on top shortage pairs and TER on the whole graph as external bottleneck proxies\. Rewiring is applied as a preprocessing step, and downstream results are averaged over repeated seeds\.

### IV\-CExperiment analysis

TABLE II:Graph classification accuracy \(%\) on six datasets under different rewiring methods and backbones\. The average ranking \(AR\) reflects the mean position of each method across all datasets\.Node Classification\. PAR gives the strongest node classification results under both backbones, with the best average rank under GCN and GIN, reaching 1\.50 and 1\.00\. The gains are steady on citation graphs and become larger on topology\-limited datasets\. Under GIN, Texas rises from 53\.5 to 68\.8 and Cornell from 36\.5 to 51\.0; under GCN, PAR also improves the no\-rewiring baseline on both Cora and CiteSeer\. The consistent gains across GCN and GIN suggest that the benefit comes from the repaired topology used for message passing\. PAR improves the pairwise support available before backbone training, which is especially useful when useful information must move beyond immediate neighborhoods\.

Graph Classification\. PAR also performs strongly on the TUD graph classification benchmarks, with the best average rank under both GCN and GIN\. Under GCN, it attains the top result on five of the six datasets, with clear gains on ENZYMES and MUTAG\. Under GIN, it remains strongest on ENZYMES, IMDB, MUTAG, and COLLAB\. The gains are larger when graph labels depend on information distributed across separated or weakly connected substructures\. They are narrower on PROTEINS and in some REDDIT settings, where local motifs or sufficient original structure may already carry much of the label signal\. This pattern supports the intended role of PairAlign\. Pairwise support can improve whole\-graph representations when labels require information to move across separated parts of the graph\.

TABLE III:Results on heterophilic node classification datasets\. Roman\-Empire and Amazon\-Ratings are reported in Accuracy \(%\), while Minesweeper, Tolokers, and Questions are reported in ROC AUC \(%\)\. The average ranking \(AR\) reflects the mean position of each method across all datasets\.Heterophilous Node Classification\. The heterophilous benchmarks are a stricter test of rewiring quality because useful evidence is often nonlocal, but arbitrary shortcuts can damage class\-relevant structure\. PAR obtains the best average rank under both GCN and GAT, improving over the closest competitor ComFy in each case\. With GCN, it gives the strongest results on Roman\-Empire and Amazon\-Ratings and remains close to the top on Minesweeper and Tolokers\. With GAT, it leads on Tolokers and Questions and stays within a small margin of the best result on the remaining datasets\. This stability is more informative than isolated wins\. It shows that PAR can add useful nonlocal support without turning rewiring into broad long\-range mixing, which is important for heterophilous graphs where distant evidence and structural specificity must both be preserved\.

The benchmark groups offer three important observations about PairAlign\.

- •On node classification, PAR improves both GCN and GIN across the tested datasets and keeps the best average rank under both backbones\. This consistent gain across backbones supports a graph\-side explanation\. PairAlign repairs pairwise support for message passing\.
- •On graph classification, the larger gains appear on datasets where labels depend on information spread across separated or weakly connected substructures\. This extends the effect of pairwise repair beyond node prediction, showing that better pairwise support can improve whole\-graph representations\.
- •On heterophilous graphs, PAR is more stable across datasets than baselines that peak only in a few cases\. This stability matters because heterophily needs nonlocal evidence but can be harmed by indiscriminate mixing\. PAR adds nonlocal support through shortage targets, keeping long\-range rewiring selective\.

### IV\-DPair\-Shortage Validity\.

We first relate the proposed pair\-shortage score to an external pair\-level bottleneck proxy before analyzing the effect of rewiring\. For each graph in MUTAG, we compute the pair\-shortage score on the original graph and compare it with pairwise effective resistance \(PER\)\. We then group node pairs into five shortage quantiles and report the normalized mean PER in each bin\. As shown in Fig\.[3](https://arxiv.org/html/2608.10619#S4.F3)\(a\), higher shortage quantiles consistently correspond to larger PER\. The normalized mean PER increases from 0\.4527 in the lowest shortage bin to 1\.8161 in the highest bin, and the graph\-level Spearman correlation between shortage and PER reaches 0\.9304 on average\. This monotone pattern indicates that pairs with high shortage are also pairwise bottlenecks under an effective\-resistance view\. Hence, the proposed pair\-shortage can provide a sensible pair\-level diagnostic that is aligned with an established communication bottleneck proxy\.

![Refer to caption](https://arxiv.org/html/2608.10619v1/x3.png)\(a\)Pair\-shortage validity
![Refer to caption](https://arxiv.org/html/2608.10619v1/x4.png)\(b\)Structural reduction

Figure 3:Pair\-level shortage analysis and structural reduction comparison\.We next evaluate structural reduction on the same target pairs fixed before rewiring\. On MUTAG, PAR is compared with FOSR under the same edge budget\. Since FOSR directly optimizes a spectral graph\-connectivity surrogate, it provides a relevant baseline for resistance\-based evaluation\.

As shown in Fig\.[3](https://arxiv.org/html/2608.10619#S4.F3)\(b\), PAR yields larger reductions in both the shortage score and the pairwise effective resistance of the top 10% pairs with high shortage\.Δ​PER​@​T​10\\Delta\\mathrm\{PER\}@T10increases from0\.48260\.4826with FOSR to0\.62780\.6278with PAR, andΔ\\DeltaShortage increases from0\.37950\.3795to0\.50300\.5030\. This indicates that the pair\-centric objective of PAR improves aggregate graph connectivity and guides the limited rewiring budget toward communication\-deficient node pairs\. PAR makes the structural modification more aligned with the pairwise interactions relevant to downstream prediction\.

### IV\-EMain Ablations\.

The ablation study in Table[IV](https://arxiv.org/html/2608.10619#S4.T4)isolates the components that turn shortage diagnosis into targeted repair\. We compare the full model with Greedy\-Local and variants that remove focused target selection, remove OT allocation, or drop one term in the transport cost\. Task performance is reported together withΔ\\DeltaShortage and Coverage@10\.

TABLE IV:Mechanism\-oriented ablations on three representative benchmarks\. Higher values mean better task performance, shortage reduction, and Coverage@10\.The full model gives the clearest evidence for this mechanism\. PAR obtains the best task performance on Texas, Roman\-Empire, and MUTAG, while also producing the largestΔ\\DeltaShortage and Coverage@10\. For example, on Texas, PAR reachesΔ\\DeltaShortage of0\.23500\.2350and Coverage@10 of0\.21130\.2113, both higher than all ablated variants\. On MUTAG, PAR achieves the best task score of0\.82630\.8263, with the strongest structural diagnostics as well\. The consistent improvement in both prediction and structural repair supports the alignment between PAR’s downstream gains and its targeted repair of pairs with high shortage\.

The focused target set is the first ingredient behind this behavior\. PAR does not start from candidate edges alone; it first selects pairs with high shortage on the original graph as the pairs to be repaired by rewiring\. Removing the focus mechanism still preserves part of the shortage signal, so the variant does not collapse\. Yetw/o Focusis consistently below PAR in task performance,Δ\\DeltaShortage, and Coverage@10 across the three datasets\. On Roman\-Empire, Coverage@10 decreases from0\.70480\.7048to0\.58570\.5857, and on MUTAG it drops from0\.64470\.6447to0\.54790\.5479\. This gap means that the focused target set gives rewiring a sharper pairwise target\. Greedy\-Local further shows why local edge ranking is not enough\. It selects edges by local improvement but does not coordinate the budget across shortage targets, so its Coverage@10 is only0\.03510\.0351on Texas and0\.04670\.0467on MUTAG, far below PAR\. The focus mechanism does more than filter candidates by specifying the pairwise interactions that should receive the limited rewiring budget\.

The transport term becomes important once the target set has been fixed\. Thew/o OTvariant keeps the focus mechanism, continuous optimization, and projection pipeline, but sets the transport weight to zero\. It yields nontrivialΔ\\DeltaShortage, reaching0\.57090\.5709on Roman\-Empire and0\.48260\.4826on MUTAG\. This confirms that the shortage term can expose communication\-deficient regions\. Thew/o OTvariant remains below PAR in task performance and targeted coverage\. On Texas, Coverage@10 decreases from0\.21130\.2113to0\.14710\.1471, and on Roman\-Empire it decreases from0\.70480\.7048to0\.61430\.6143\. These gaps clarify the role of OT: shortage reveals where support is lacking, and OT coordinates the limited edge budget across targets with high shortage to produce an organized allocation\.

The remaining variants separate the roles of the two geometric terms in the transport cost\. Inw/o Bridge, endpoint matching is retained, so the model can still cover a moderate fraction of pairs with high shortage\. For instance, on Roman\-Empire, its Coverage@10 is0\.64650\.6465, close tow/o OTat0\.61430\.6143and clearly abovew/o Endpointat0\.49520\.4952\. ItsΔ\\DeltaShortage remains lower than PAR, decreasing from0\.23500\.2350to0\.15860\.1586on Texas and from0\.48550\.4855to0\.44150\.4415on MUTAG\. Endpoint proximity alone does not guarantee effective repair; the bridge reward helps select edges that actually increase pairwise support\. In contrast,w/o Endpointkeeps the bridge reward but suffers a larger drop in Coverage@10, especially on Texas, where it decreases from0\.21130\.2113to0\.10360\.1036\. Bridge\-like edges still need to be aligned with the intended target pairs\. The two cost terms play distinct roles\. Endpoint matching determines the pairwise targets an added edge should support, and the bridge reward favors edges that can produce effective communication repair\.

By reformulating over\-squashing around communication\-deficient node pairs, PAR recasts graph rewiring as a budgeted structural repair problem, yielding stronger targeted repair and better downstream performance across the datasets\.

### IV\-FAnalysis of OT\-guided Budget Allocation

Necessity of OT\.To observe how the OT\-guided rewiring rule changes the allocation of a limited edge addition budget, we visualize the assignment from the final added edges to the top shortage target pairs\. As shown in Fig\.[4](https://arxiv.org/html/2608.10619#S4.F4), each row corresponds to the added edge and each column corresponds to a target pair with high shortage\. Darker entries indicate that a larger fraction of the allocation associated with an added edge is assigned to the corresponding target pair\.

The heatmap shows that our PAR distributes its added edges across a broader set of targets with high shortage while retaining clear assignments\. Full PAR achieves higherΔ\\DeltaShortage and Coverage@10\. Greedy\-Local exhibits a more concentrated allocation pattern, with several added edges assigned mainly to a small subset of target columns\. These results indicate that OT\-guided allocation spreads the budget over a wider target set and produces stronger pair\-centric structural repair\.

![Refer to caption](https://arxiv.org/html/2608.10619v1/x5.png)Figure 4:Visualization of how added edges are allocated to target pairs with high shortage\. Each row is normalized to show how one added edge distributes its allocation over the selected target pairs\. Darker colors indicate a larger allocated fraction for the corresponding target pair\.Stability of OT\.We further analyze how the weightλOT\\lambda\_\{\\mathrm\{OT\}\}of the OT\-guided rewiring affects the rewiring objective\. The MUTAG\-GCN setting is kept fixed and onlyλOT\\lambda\_\{\\mathrm\{OT\}\}is varied\. As shown in Fig\.[5\(a\)](https://arxiv.org/html/2608.10619#S4.F5.sf1), OT\-guided alignment improves Task and structure proxies in the main operating range compared withλOT=0\\lambda\_\{\\mathrm\{OT\}\}=0\. This indicates that the OT\-guided rule provides a proper global coordination signal for structural repair and helps added edges cover targets with high shortage more effectively\. WhenλOT\\lambda\_\{\\mathrm\{OT\}\}is further increased,Δ\\DeltaShortage remains high and even continues to increase, but Task performance starts to decrease\. This suggests that an overly strong transport preference mainly emphasizes the structural repair objective and does not necessarily translate into better prediction\. The trend supports the role of OT as a budget\-coordination mechanism\. With a suitable weight, it organizes the limited edge addition budget across shortage targets and helps convert structural repair into downstream task gains\.

![Refer to caption](https://arxiv.org/html/2608.10619v1/x6.png)\(a\)OT weight
![Refer to caption](https://arxiv.org/html/2608.10619v1/x7.png)\(b\)Rewiring budget
![Refer to caption](https://arxiv.org/html/2608.10619v1/x8.png)\(c\)Propagation depth

Figure 5:Visualization of OT\-weight stability and sensitivity analysis\.
### IV\-GSensitivity Analysis\.

Rewiring budget\.The budget sensitivity on MUTAG is shown in Fig\.[5\(b\)](https://arxiv.org/html/2608.10619#S4.F5.sf2)\. We setk0=3k\_\{0\}=3as the integer PAR budget anchor compatible with the main GIN setting\. The task curve shows a high\-variance plateau; the highest mean appears at0\.25​k00\.25k\_\{0\}, and its error band largely overlaps with the results from0\.5​k00\.5k\_\{0\}tok0k\_\{0\}\. In this compact budget range, PAR already achieves competitive task performance, andΔ\\DeltaShortage increases from0\.06200\.0620to0\.18600\.1860\. When the budget is enlarged beyondk0k\_\{0\},Δ\\DeltaShortage continues to rise and reaches0\.25060\.2506at2\.0​k02\.0k\_\{0\}\. The task mean moves to a lower range\.

This trend indicates that PAR obtains its main predictive benefit within a limited rewiring budget, with additional edges mainly contributing further targeted shortage repair\.

Propagation depth\.We further evaluate the sensitivity to the propagation depthKKin the pair\-support term\. To avoid the bias that largerKKaccumulates more hop contributions under uniform weighting, this experiment uses the same MUTAG\-GIN setting with a fixed decayed\-support configuration\. As shown in Fig\.[5\(c\)](https://arxiv.org/html/2608.10619#S4.F5.sf3),K=1K=1gives the weakest structural repair, withΔ\\DeltaShortage of only0\.02180\.0218\. This indicates that a purely local propagation range is insufficient to capture pairwise communication shortage\. IncreasingKKto22raises the task score to0\.81720\.8172and improvesΔ\\DeltaShortage to0\.23890\.2389, showing that a moderate propagation range provides a more effective support estimate\. WhenKKincreases to33and44,Δ\\DeltaShortage continues to grow and reaches0\.36520\.3652and0\.63980\.6398\. The task means stay in a similar range under larger variance\.

The result suggests thatKKcontrols the scale at which PairAlign evaluates pairwise communication shortage\. Task\-relevant rewiring benefits are strongest when this scale matches the effective range of downstream message passing\.

## VConclusion

This work proposes PairAlign \(PAR\), an OT\-guided graph rewiring framework that treats over\-squashing as a pair\-level communication shortage\. PAR centers rewiring on node pairs whose structural demand is high but whose propagation support remains limited\. The shortage score turns this pair\-level bottleneck into an interpretable quantity as the ratio of current\-graph support relative to original\-graph demand, with theoretical consistency to the Jacobian\-based shortage\. PairAlign turns this diagnosis into an OT\-guided allocation strategy for rewiring\. Candidate additions are scored by current shortage reduction, with theoretical support for positive shortage relief on the rewired graph\. OT\-guided allocation then coordinates the limited budget across the shortage profile, prevents repair from concentrating on only a few targets, and obtains a coverage advantage over Greedy\-Local under the coverage theory\. Across standard graph benchmarks and different backbones, PAR shows consistent effectiveness, and its agreement with PER/TER supports pairwise shortage as a valid over\-squashing bottleneck diagnostic\.

How to explore task\-aware demand modeling and explicit locality constraints for improving scalability on large graphs is our future work\.

## References

- \[1\]\(2022\)Shortest path networks for graph property prediction\.InLearning on graphs conference,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1)\.
- \[2\]S\. Akansha\(2025\)Over\-squashing in graph neural networks: a comprehensive survey\.Neurocomputing642\.Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p1.1)\.
- \[3\]U\. Alon\(2021\)On the bottleneck of graph neural networks and its practical implications\.InInternational Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p1.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1),[§III\-B](https://arxiv.org/html/2608.10619#S3.SS2.p3.1)\.
- \[4\]J\. Altschuler, J\. Weed, and P\. Rigollet\(2017\)Near\-linear time approximation algorithms for optimal transport via sinkhorn iteration\.InAdvances in Neural Information Processing Systems,Cited by:[§III\-D](https://arxiv.org/html/2608.10619#S3.SS4.p4.9)\.
- \[5\]A\. Arnaiz\-Rodríguez, A\. Begga, F\. Escolano, and N\. M\. Oliver\(2022\)DiffWire: inductive graph rewiring via the lovász bound\.InProceedings of the First Learning on Graphs Conference,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p3.1)\.
- \[6\]P\. K\. Banerjee, K\. Karhadkar, Y\. G\. Wang, U\. Alon, and G\. Montúfar\(2022\)Oversquashing in gnns through the lens of information contraction and graph expansion\.In58th Annual Allerton Conference on Communication, Control, and Computing \(Allerton\),pp\. 1–8\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1)\.
- \[7\]F\. Barbero, A\. Velingker, A\. Saberi, M\. M\. Bronstein, and F\. Di Giovanni\(2024\)Locality\-aware graph rewiring in gnns\.InInternational Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1),[§II](https://arxiv.org/html/2608.10619#S2.p3.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.36.36.8),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.84.84.8),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.35.35.8),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.82.82.8)\.
- \[8\]Y\. Bengio, N\. Léonard, and A\. Courville\(2013\)Estimating or propagating gradients through stochastic neurons for conditional computation\.arXiv preprint arXiv:1308\.3432\.Cited by:[§III\-D](https://arxiv.org/html/2608.10619#S3.SS4.p2.8)\.
- \[9\]W\. Bi, L\. Du, Q\. Fu, Y\. Wang, S\. Han, and D\. Zhang\(2024\)Make heterophilic graphs better fit gnn: a graph rewiring approach\.IEEE Transactions on Knowledge and Data Engineering36\(12\),pp\. 8744–8757\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p4.1)\.
- \[10\]M\. Black, Z\. Wan, A\. Nayyeri, and Y\. Wang\(2023\)Understanding oversquashing in gnns through the lens of effective resistance\.InInternational Conference on Machine Learning,pp\. 2528–2547\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p1.1),[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1),[§II](https://arxiv.org/html/2608.10619#S2.p3.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.30.30.7),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.78.78.7),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[§IV\-B](https://arxiv.org/html/2608.10619#S4.SS2.p4.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.29.29.7),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.76.76.7),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.23.23.6),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.61.61.6)\.
- \[11\]J\. Bober, A\. Monod, E\. Saucan, and K\. N\. Webster\(2023\)Rewiring networks for graph neural network training using discrete geometry\.InInternational Conference On Complex Networks And Their Applications,pp\. 225–236\.Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p1.1)\.
- \[12\]K\. Bose, S\. Banerjee, and S\. Das\(2025\)Can graph neural networks tackle heterophily? yes, with a label\-guided graph rewiring approach\!\.IEEE Transactions on Neural Networks and Learning Systems\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p4.1)\.
- \[13\]J\. Chen, B\. Deng, Z\. Zheng, and C\. Chen\(2026\)RETHINKING the gold standard: why discrete curvature fails to fully capture over\-squashing in gnns?\.InInternational Conference on Learning Representations,Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p2.1)\.
- \[14\]M\. Cuturi\(2013\)Sinkhorn distances: lightspeed computation of optimal transport\.InAdvances in Neural Information Processing Systems,Cited by:[§III\-C](https://arxiv.org/html/2608.10619#S3.SS3.p2.1),[§III\-D](https://arxiv.org/html/2608.10619#S3.SS4.p4.9)\.
- \[15\]A\. Deac, M\. Lackenby, and P\. Veličković\(2022\)Expander graph propagation\.InLearning on Graphs Conference,pp\. 38–1\.Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p1.1)\.
- \[16\]R\. B\. Gabrielsson, M\. Yurochkin, and J\. Solomon\(2023\)Rewiring with positional encodings for graph neural networks\.Transactions on Machine Learning Research\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1)\.
- \[17\]J\. Gilmer, S\. S\. Schoenholz, P\. F\. Riley, O\. Vinyals, and G\. E\. Dahl\(2017\)Neural message passing for quantum chemistry\.InInternational conference on machine learning,pp\. 1263–1272\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p1.1)\.
- \[18\]A\. Jamadandi, C\. Rubio\-Madrigal, and R\. Burkholz\(2024\)Spectral graph pruning against over\-squashing and over\-smoothing\.InAdvances in Neural Information Processing Systems,Vol\.37\.Cited by:[§III\-B](https://arxiv.org/html/2608.10619#S3.SS2.p11.1)\.
- \[19\]K\. Karhadkar, P\. Banerjee, and G\. Montufar\(2023\)FoSR: first\-order spectral rewiring for addressing oversquashing in gnns\.InInternational Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p3.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.18.18.7),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.66.66.7),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.18.18.7),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.65.65.7),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.15.15.6),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.53.53.6)\.
- \[20\]T\. N\. Kipf and M\. Welling\(2016\)Semi\-supervised classification with graph convolutional networks\.arXiv preprint arXiv:1609\.02907\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p1.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.6.6.8),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p3.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.6.6.8),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.5.5.7)\.
- \[21\]L\. Liang, F\. Bu, Z\. Song, Z\. Xu, S\. Pan, and K\. Shin\(2025\)Mitigating over\-squashing in graph neural networks by spectrum\-preserving sparsification\.InInternational Conference on Machine Learning,Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p3.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.42.42.8),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.90.90.8),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.41.41.8),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.88.88.8)\.
- \[22\]J\. Linkerhägner, C\. Shi, and I\. Dokmanić\(2025\)Joint graph rewiring and feature denoising via spectral resonance\.InInternational Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p4.1),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.28.28.6),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.66.66.6)\.
- \[23\]C\. Morris, N\. M\. Kriege, F\. Bause, K\. Kersting, P\. Mutzel, and M\. Neumann\(2020\)Tudataset: a collection of benchmark datasets for learning with graphs\.arXiv preprint arXiv:2007\.08663\.Cited by:[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p2.1)\.
- \[24\]K\. Nguyen, N\. M\. Hieu, V\. D\. Nguyen, N\. Ho, S\. Osher, and T\. M\. Nguyen\(2023\)Revisiting over\-smoothing and over\-squashing using ollivier\-ricci curvature\.InInternational Conference on Machine Learning,pp\. 25956–25979\.Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p2.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.24.24.7),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.72.72.7),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.23.23.6),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.70.70.6),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.18.18.4),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.56.56.4)\.
- \[25\]H\. Pei, B\. Wei, K\. C\. C\. Chang, Y\. Lei, and B\. Yang\(2020\)GEOM\-gcn: geometric graph convolutional networks\.InInternational Conference on Learning Representations,Cited by:[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p2.1)\.
- \[26\]O\. Platonov, D\. Kuznedelev, M\. Diskin, A\. Babenko, and L\. Prokhorenkova\(2023\)A critical look at the evaluation of gnns under heterophily: are we really making progress?\.InAdvances in Neural Information Processing Systems,Cited by:[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p2.1)\.
- \[27\]B\. Rozemberczki, C\. Allen, and R\. Sarkar\(2021\)Multi\-scale attributed node embedding\.Journal of Complex Networks9\(2\),pp\. 1–22\.Cited by:[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p2.1)\.
- \[28\]C\. Rubio\-Madrigal, A\. Jamadandi, and R\. Burkholz\(2025\)GNNs getting comfy: community and feature similarity guided rewiring\.InInternational Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p4.1),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.33.33.6),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.71.71.6)\.
- \[29\]X\. Shen, P\. Lio, L\. Yang, R\. Yuan, Y\. Zhang, and C\. Peng\(2024\)Graph rewiring and preprocessing for graph neural networks based on effective resistance\.IEEE Transactions on Knowledge and Data Engineering36\(11\),pp\. 6330–6343\.Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p3.1)\.
- \[30\]J\. Topping, F\. Di Giovanni, B\. P\. Chamberlain, X\. Dong, and M\. M\. Bronstein\(2022\)Understanding over\-squashing and bottlenecks on graphs via curvature\.InInternational Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2608.10619#S1.p1.1),[§I](https://arxiv.org/html/2608.10619#S1.p2.1),[§II](https://arxiv.org/html/2608.10619#S2.p1.1),[§II](https://arxiv.org/html/2608.10619#S2.p2.1),[§III\-B](https://arxiv.org/html/2608.10619#S3.SS2.p3.1),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.12.12.7),[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.60.60.7),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p1.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.12.12.7),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.59.59.7),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.10.10.6),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.48.48.6)\.
- \[31\]F\. Tori, V\. Holst, and V\. Ginis\(2025\)The effectiveness of curvature\-based rewiring and the role of hyperparameters in gnns revisited\.InInternational Conference on Learning Representations,Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p2.1)\.
- \[32\]P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. Bengio\(2018\)Graph attention networks\.InInternational Conference on Learning Representations,Cited by:[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p3.1),[TABLE III](https://arxiv.org/html/2608.10619#S4.T3.43.43.7)\.
- \[33\]C\. Villaniet al\.\(2009\)Optimal transport: old and new\.Vol\.338,Springer\.Cited by:[§III\-C](https://arxiv.org/html/2608.10619#S3.SS3.p2.1)\.
- \[34\]J\. Wilson, M\. Bechler\-Speicher, and P\. Veličković\(2025\)Cayley graph propagation\.InProceedings of the Third Learning on Graphs Conference,Cited by:[§II](https://arxiv.org/html/2608.10619#S2.p3.1)\.
- \[35\]K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka\(2018\)How powerful are graph neural networks?\.arXiv preprint arXiv:1810\.00826\.Cited by:[TABLE I](https://arxiv.org/html/2608.10619#S3.T1.54.54.8),[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p3.1),[TABLE II](https://arxiv.org/html/2608.10619#S4.T2.53.53.8)\.
- \[36\]Z\. Yang, W\. Cohen, and R\. Salakhudinov\(2016\)Revisiting semi\-supervised learning with graph embeddings\.InInternational conference on machine learning,pp\. 40–48\.Cited by:[§IV\-A](https://arxiv.org/html/2608.10619#S4.SS1.p2.1)\.