Search papers, labs, and topics across Lattice.
This paper introduces PairAlign, a novel pair-centric graph rewiring framework designed to address the issue of over-squashing in message-passing neural networks (MPNNs) by optimizing communication alignment. By combining structural demand and finite-hop propagation support, PairAlign identifies critical pairwise communications that require enhanced structural support, leveraging a theoretical framework that interprets over-squashing through a pair-level lens. Experimental results demonstrate that PairAlign significantly improves performance across various message-passing backbones, validating its effectiveness in alleviating communication bottlenecks in graph-based learning tasks.
PairAlign reveals that optimizing pairwise communication can dramatically enhance the performance of message-passing neural networks by effectively addressing over-squashing.
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.
