VPF: Topology-preserving Virtual Path Fusion to tackle over-squashing

Despite the widespread success of graph neural networks (GNNs) in various graph learning tasks, their performance is often hampered by the over-squashing issue, which impedes the propagation of messages from distant nodes and limits the expressive power of the model. Existing solutions to mitigate over-squashing primarily rely on altering graph topology to improve message flow. However, such modification of structure can disrupt the graph's intrinsic topology and corresponding inductive bias, while the introduction of extra edges may increase the risk of over-smoothing. To address these limitations, we propose the Virtual Path Fusion (VPF) framework, an enhanced GNN that tackles over-squashing by facilitating message flow through virtual paths, offering a topology-preserving solution that sidesteps the inherent risks of structural distortion and over-smoothing. Specifically, our method leverages effective resistance, a universal measure that captures both sensitivity and spectral properties, to guide the construction of virtual paths that target structurally susceptible bottlenecks. These paths are encoded via sequence models to capture long-range dependencies, thereby adaptively strengthening interactions between distant nodes. VPF is designed as a model-agnostic and plug-and-play module, making it compatible with a variety of message-passing GNN architectures, while also contributing to the mitigation of over-smoothing. Extensive experiments demonstrate that VPF consistently and significantly outperforms baseline methods across multiple benchmarks, validating virtual path augmentation as an effective and versatile strategy for tackling over-squashing. The code is available at: https://github.com/BHuiwen/VPF.