What Can We Learn from State Space Models for Machine Learning on Graphs?

最近，图上的机器学习在许多领域得到广泛应用。然而，常用的消息传递神经网络（MPNN）表现出有限的表达能力，难以捕捉长程依赖关系。图转换器由于其全局注意力机制，成为一种强有力的替代方案，但是对于大型图来说，它们带来了巨大的计算开销。近年来，状态空间模型（SSM）已经成为一种有吸引力的方法，用来替代变压器中的全注意力机制，用于建模序列数据。它结合了RNN和CNN的优点，提供了a）高效的计算，b）捕捉长程依赖关系的能力，以及c）对各种长度序列的良好泛化能力。然而，将SSM扩展到图结构数据中，由于图中没有规范化的节点排序，存在独特的挑战。在这项工作中，我们提出了图状态空间卷积（GSSC）作为SSM扩展到图结构数据的基本方法。通过利用全局置换等变集合聚合和依赖于相对节点距离作为卷积核的可分解图核，GSSC保留了SSM的所有三个优点。我们证明了GSSC在计数图子结构方面比MPNN具有更强的表达能力，并在10个真实世界广泛使用的基准数据集上展示了其有效性，在其中7个数据集上取得了最佳结果，在其他3个数据集上取得了次佳结果，与最先进的基线相比，显著提高了性能。我们的发现突显了GSSC作为图机器学习的强大和可扩展模型的潜力。我们的代码可在https://github.com/Graph-COM/GSSC上获得。

本论文旨在解决在图机器学习中常见的长距离依赖问题以及计算效率问题。同时，还尝试将State Space Models（SSMs）扩展到图结构数据上。

论文提出了一种名为Graph State Space Convolution（GSSC）的方法，通过全局置换等变集合聚合和基于相对节点距离的可分离图卷积核，实现了SSMs在图结构数据上的扩展。

实验结果表明，GSSC在10个真实世界的基准数据集上取得了最佳结果，其中7个数据集的结果显著优于现有的最佳结果。论文提供了开源代码。

在最近的研究中，也有一些关于图机器学习的相关研究，例如《Message Passing Transformers》和《Graph Attention Networks》等。