S$^3$GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning
For graph learning practitioners, S$^3$GNN provides a practical and efficient solution to the oversquashing problem without restrictive theoretical assumptions.
S$^3$GNN mitigates oversquashing in graph neural networks by efficiently combining global spectral mixing and local message passing, achieving up to an order-of-magnitude error reduction with up to 50% fewer parameters on long-range benchmarks, KGQA, and mesh-based fluid dynamics.
Message-passing neural networks (MPNNs) often suffer from an information bottleneck when capturing long-range dependencies, leading to the oversquashing (OSQ) phenomenon. Alongside spatial connectivity enrichment (e.g., rewiring), recent studies have shown that spectral filtering can yield strong long-range learning outcomes, as spectral operators enable global information mixing that alleviates OSQ. These approaches achieve this either by stabilizing the Jacobian energies in deep propagation or by guaranteeing OSQ mitigation under strong theoretical assumptions. We revisit these conclusions and show that the associated Jacobian sensitivity lower bound is generally difficult to achieve in practice. We then propose S$^3$GNN, which mitigates OSQ without such restrictive assumptions by lightweightly reintroducing omitted components with substantially lower computational complexity, while standard stability constraints on feature transformations remain effective under our new dynamics. Extensive experiments across diverse domains (e.g., long-range benchmarks, KGQA, and mesh-based fluid dynamics) demonstrate that S$^3$GNN achieves up to an order-of-magnitude error reduction with up to 50\% fewer parameters. Our code can be found in https://github.com/EEthanShi/S3-GNN.git.