Machine learning on graphs has recently found extensive applications across
domains. However, the commonly used Message Passing Neural Networks (MPNNs)
suffer from limited expressive power and struggle to capture long-range
dependencies. Graph transformers offer a strong alternative due to their global
attention mechanism, but they come with great computational overheads,
especially for large graphs. In recent years, State Space Models (SSMs) have
emerged as a compelling approach to replace full attention in transformers to
model sequential data. It blends the strengths of RNNs and CNNs, offering a)
efficient computation, b) the ability to capture long-range dependencies, and
c) good generalization across sequences of various lengths. However, extending
SSMs to graph-structured data presents unique challenges due to the lack of
canonical node ordering in graphs. In this work, we propose Graph State Space
Convolution (GSSC) as a principled extension of SSMs to graph-structured data.
By leveraging global permutation-equivariant set aggregation and factorizable
graph kernels that rely on relative node distances as the convolution kernels,
GSSC preserves all three advantages of SSMs. We demonstrate the provably
stronger expressiveness of GSSC than MPNNs in counting graph substructures and
show its effectiveness across 10 real-world, widely used benchmark datasets,
where GSSC achieves best results on 7 out of 10 datasets with all significant
improvements compared to the state-of-the-art baselines and second-best results
on the other 3 datasets. Our findings highlight the potential of GSSC as a
powerful and scalable model for graph machine learning. Our code is available
at this https URL

提出了一种名为 Graph State Space Convolution (GSSC) 的方法，该方法是 State Space Models (SSMs) 在图结构数据上的扩展，通过利用全局置换等变集合聚合和以节点之间的相对距离作为卷积核的可分解图卷积核，保留了 SSMs 的三个优点。实验证明 GSSC 在计算图子结构和十个常用基准数据集的表现上比 Message Passing Neural Networks (MPNNs) 更加表达能力强，且在 7 个数据集上取得了最佳结果，在其他 3 个数据集上也有显著提升。该研究结果突出了 GSSC 作为一种强大且可扩展的图机器学习模型的潜力。