S$^3$GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learning

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 examine the practical attainability of these guarantees 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.

Many real-world problems can be described as networks: molecules are networks of atoms, knowledge bases are networks of facts, and physical simulations can be represented as networks of interacting regions. Graph neural networks are widely used to learn from such data, but they often struggle when useful information must travel across many distant parts of the network. As messages are repeatedly passed from one node to another, important long-range information can become compressed or lost. This paper proposes S3GNN, a new graph neural network designed to make long-range communication easier and more efficient. The key idea is to combine local message passing between neighboring nodes with a lightweight global mixing step, allowing distant parts of the same connected network to exchange information more directly. The method is also designed to remain stable as more layers are used, so information does not quickly vanish or become unstable during propagation. Beyond standard graph learning benchmarks, this type of model has potential value for industry-facing applications where long-range interactions matter, such as molecular property prediction, knowledge graph question answering, large-scale network analysis, and mesh-based physical simulation. Experiments show that S3GNN performs strongly across diverse tasks, including long-range graph benchmarks, large-scale node classification, knowledge graph reasoning, brain signal interpolation, and fluid dynamics prediction. It achieves better accuracy while often using fewer parameters and lower computational cost than competing methods.