How Can State Space Models Enhance Machine Learning on Graphs?

Message Passing Neural Networks are known to struggle with limited expressivity and capturing long-range dependencies. While Graph Transformers alleviate these issues with global attention modules, their quadratic complexity limits efficiency. Recently, State Space Models have emerged as a compelling alternative to attention for sequence modeling to 1) capture long-range dependencies, 2) enable computational efficiency, and 3) generalize well across varying sequence lengths. However, extending SSMs to graphs presents unique challenges due to the lack of canonical node ordering. This work studies how to leverage the insights of SSM design to improve learning on graph-structured data and proposes Graph State Space Convolution (GSSC). Using global permutation-equivariant set aggregation and factorizable graph kernels based on relative node distances, GSSC retains the three advantages of SSMs. Across 11 real-world, widely used graph benchmark datasets, GSSC achieves the best results on 5 datasets with significant improvements over the state-of-the-art baselines and competitive performance on the other 6. Our findings highlight the potential of building powerful and scalable models upon GSSC for graph machine learning.