Breaking the Bottleneck on Graphs with Structured State Spaces

The majority of GNNs are based on message-passing mechanisms. However, Message Passing Neural Networks (MPNNs) have inherent limitations in capturing long-range interactions. The exponentially growing node information is compressed into fixed-size representations through multiple rounds of message passing, leading to the over-squashing problem. This issue severely hinders the flow of information across the graph and creates a bottleneck in graph learning. The natural idea of introducing global attention to point-to-point communication, as adopted in Graph Transformers (GTs), lacks inductive biases on graph structures and relies on complex positional encodings to enhance their performance in practical tasks. In this paper, we observe that the sensitivity between nodes in MPNNs decreases exponentially with the shortest path distance. In contrast, GTs have constant sensitivity, which leads to a loss of inductive bias. To address these issues, we introduce structured state spaces to capture the hierarchy of rooted trees, achieving linear sensitivity with theoretical guarantees. We further propose a novel state-space model-based graph convolution, resulting in a new paradigm that retains both the strong inductive biases from MPNNs and the long-range modeling capabilities from GTs. Extensive experimental results on long-range and general graph benchmarks demonstrate the superiority of our approach.