PairAlign is proposed, a pair-centric graph rewiring framework that makes this question explicit through demand-support shortage and introduces an Optimal Transport-guided rewiring mechanism to coordinate the finite edge budget for pair-level structural compatibility and shortage-target coverage.
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.
This work introduces a novel method Schreier-Coset Graph Rewiring, a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group, creating a low-resistance bypass for long-range communication.
Aryan Mishra, Randy Martinez, Lizhen Lin· arXiv.org· 0 citations
A differentiable Sandpile Stabilization Layer (SSL) and congestion-aware objectives designed to redistribute excess load and manage stabilization costs are proposed and Experiments on long-range benchmarks show that targeting sandpile-identified bottlenecks mitigates representation collapse and improves over standard baselines.
Yang Shi, Li-Xian Chen, Jingchao Wang et al.· Proceedings of the 32nd ACM...· 0 citations
Graph Similarity Computation (GSC) is a core task in graph analysis. However, current mainstream GNN-based similarity models still suffer from two fundamental bottlenecks. First, constrained by the inherent mechanism of recursive local aggregation, namely the 1-Weisfeiler–Lehman (1-wl) test, these models primarily measure similarity by aligning local structures, while struggling to capture long-range dependencies and overall topological configurations. Second, the simplified treatment of edge features prevents them from fully exploiting fine-grained semantic interactions between nodes. To address these challenges, this paper pro-poses Structure-Aware Collaborative Network (SAC-Net), an end-to-end framework that leverages structural information to unify global contexts with local affinities. Specifically, we design a Dynamic Structural Perception (DSP) backbone to establish a joint evolution paradigm for node, position, and edge features. By treating positional encodings as dynamic states, the model effectively captures long-range dependencies and overall topological configurations to maintain a robust global structural skeleton. Subsequently, this study introduce an Edge-Aware Fusion mechanism that leverages edge features as a bridge to adaptively integrate global and local structural information, thereby effectively addressing the alignment and integration of multi-granularity semantics. Extensive experiments on four real-world datasets demonstrate that SAC-Net effectively integrates global and local information, leading to more accurate graph similarity measurement.
Unknown authors· Tsinghua Science and Technol...· 0 citations
Graph neural networks typically propagate information through repeated message-passing layers, coupling the distance over which information travels with the number of nonlinear transformations applied. This coupling can make deep architectures difficult to optimize and can lead to over-smoothing, over-squashing, and the loss of long-range information. Linearized Graph Sequence Models (LGSMs) address this issue by separating information depth from processing depth and treating the successive propagation states of each node as a sequence. However, existing LGSMs construct these sequences using fixed graph operators, limiting their ability to adapt propagation to the input graph, node features, and downstream task. We introduce HOPPER, an end-to-end learnable extension of LGSM that learns how hop sequences should be extracted before they are processed by a modern state-space model. Our framework supports feature-conditioned, structure-aware, graph- and hop-adaptive propagation mechanisms while preserving permutation equivariance. Standard adjacency-based and non-backtracking LGSM sequences arise as special cases of our proposed extractor family. We show that HOPPER is state-of-the-art or competitive across the ECHO-Synth benchmark, and that varying the maximum neighborhood size of message backtracking cancellation (i.e. structural memory window) can optimize accuracy on the LRIM physics-based long-range dependency benchmark. These results demonstrate that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning.
Dynamic Graph Neural Networks (DGNNs) suffer from a significant scalability bottleneck due to high computational demands resulting from their innate design to aggregate information both over graph topology and over time. While graph coarsening has successfully mitigated these costs for static graph neural networks, its potential remains largely untapped in the dynamic setting. Bridging this gap is particularly challenging because different DGNN architectures in literature aggregate information across structural topologies and temporal dimensions in different manners. %Hence, we require a coarsening method that can adapt to the complexity of a system evolving over time in different manners. In this work, we first group popular DGNNs into two general categories based on their topological and temporal message passing patterns. We then derive appropriate coarsening criteria for both classes of DGNNs with a goal to maximize the connectivity in the coarsened graph. Specifically, we aim to maximize the spectral gap of a generalized combinatorial Laplacian matrix in each case. In order to determine the quality of the candidate node-pairs to merge in an efficient manner, we derive an estimated change in eigenvalues from first principles using the Matrix Perturbation Theory. This leads to a naturally efficient algorithm Spectral-gap Aware Coarsening of Dynamic networks (SACoD). Experimental results demonstrate that our coarsening technique significantly accelerates dynamic GNN training and inference without compromising predictive performance, offering a practical path toward scalable dynamic graph learning.
Hieu Vu, Rares-Mihail Neagu, Bijaya Adhikari· Proceedings of the 32nd ACM...· 0 citations
DeltaGNN is introduced, to the best of the authors' knowledge, among the first scalable (featuring linear computational and memory complexity overhead) and generalizable (capable of effectively handling graphs with diverse homophily, density, and topology) architectures for long-range and short-range interaction detection.
Kevin Mancini, Islem Rekik· IEEE Transactions on Pattern...· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
