作为专门为处理和学习图数据而设计的神经网络类别，图神经网络（GNN）[1]、[2]在解决图分析问题方面取得了显著的成功。它们在各种应用中表现出色，包括推荐系统[3]、药物发现[4]和问答[5]。基于空间的GNN和基于光谱的GNN是图神经网络的两个主要类别。与基于消息传递和注意力机制的空间GNN不同，光谱GNN建立在图谱理论和图谱过滤机制之上。由于它们坚实的理论基础和出色的实际性能，近年来吸引了大量研究关注。
光谱GNN通过图傅里叶变换将图信号映射到光谱域，在光谱域设计图滤波器，并用图谱滤波器近似图卷积。光谱滤波器的设计对GNN模型的整体性能至关重要，其主要思想是调制图信号的频率，使某些频率分量被放大而其他分量被减弱。最近的研究表明，大多数流行的光谱GNN作为多项式或小波图谱滤波器来操作[6]、[7]、[8]、[9]、[10]。例如，GCN[11]使用简化的一阶切比雪夫多项式，这已被证明是一个低通滤波器[12]。ChebNet[6]用高阶切比雪夫多项式来近似滤波操作。BernNet[13]采用伯恩斯坦多项式[14]来近似光谱滤波器。最近提出的WaveNet[15]利用哈尔小波基[16]来近似图卷积，其中滤波器被表示为不同尺度的小波基之和。
尽管上述GNN在各种图学习任务中取得了显著成果，但在光谱GNN中仍有一些值得研究的问题。首先，大多数现有方法基于预定义的多项式或小波基来设计光谱滤波器，这需要大量的先验知识。这给GNN模型带来了强烈的归纳偏见，并引入了许多需要费力调整的超参数。例如，基于低阶多项式基的ChebNet在需要复杂且不平滑滤波器（例如带阻滤波器和梳状滤波器）的异质图中常常失败，而基于高阶多项式基的ChebNet在需要简单和平滑滤波器的同质图中则容易过拟合。对光谱滤波器的严格预定义归纳偏见可能会损害模型的通用性和泛化能力，并增加超参数调整的难度。其次，现有的光谱GNN在设计滤波器时经常忽略图谱的全局分布，这在一定程度上可能限制了滤波器的调制能力。如图1所示，我们考虑了一个具有六个节点的玩具图数据集。通过对它的归一化拉普拉斯矩阵进行光谱分解，将得到两组数值相等的特征值（即0和1.5）。集合中的每个元素具有相同的频率，但对应于不同且相互正交的图信号基。现有的光谱GNN对数值相等的频率应用相同的调制，这是有限的。例如，在图1中，两个值为零的频率不应受到理想滤波器的相同调制，因为数据集中的两个连接组件表现出明显不同的同质性。左上角的图信号应该被保留或增强，而中间位置的图信号应该被减弱。同样的分析也可以应用于值为1.5的另一组频率。不幸的是，基于高阶多项式或小波的现有光谱滤波器无法区分具有相同频率值的光谱图信号基。它们通常对数值相等的频率应用相同的调制，这使得它们在处理图1所示的复杂情况时无效。最近的一项研究[17]表明，一个能够生成任意图信号的理想光谱GNN要求图拉普拉斯矩阵没有重复的特征值。然而，现实世界的数据往往偏离这种理想条件。
为了解决这些挑战，本文提出了GrassNet（Graph State Space Network），这是一种用于半监督节点分类任务的新型光谱图神经网络。它不对光谱滤波器施加强烈的归纳偏见，并能有效地处理频率在数值上相似或相等的情况。具体来说，我们的GrassNet模拟了图数据的有序谱序列的整个序列，使其光谱滤波器能够完全捕捉谱内元素之间的相关性。这种方法即使对于数值相同的频率也能实现不同的增强/减弱过程。鉴于结构化状态空间序列模型（SSM）的最新进展及其在自然语言处理[18]、[19]和计算机视觉[20]、[21]任务中的广泛应用，我们基于SSM的基本原理设计了光谱滤波器。与现有光谱GNN中滤波器在连续空间中定义不同，我们的方法将光谱过滤问题转化为离散谱序列的建模问题。据我们所知，这是首次将SSM应用于光谱GNN模型的设计。
总之，本工作的主要贡献有四个方面：
•图谱滤波器的新视角：我们提出了关于基于多项式和小波的方法的新讨论，指出了它们的潜在局限性，并提出了使用序列模型进行光谱过滤的建议。
•SSM在非序列图数据中的适应：我们设计了一种有效的方法来扩展SSM以处理非序列图数据。具体来说，我们基于SSM的基本原理设计了光谱滤波器来模拟图谱序列。
•创新的图神经网络设计：我们提出了GrassNet，这是一种新型的光谱图神经网络，开创了与SSM集成的先河。
•卓越的性能和效率：我们从理论上证明了GrassNet的优势，并在九个基准测试中验证了其有效性。实验结果证明了GrassNet优于最先进的光谱GNN。
本文的结构如下：第2节简要回顾了成熟的光谱图神经网络、状态空间模型以及为图学习适应状态空间模型的代表性方法。第3节介绍了必要的预备知识，包括问题表述和图上的光谱定义。第4节详细介绍了我们提出的方法GrassNet，包括一种新的序列光谱图过滤范式、基于状态空间模型的精心设计的光谱图滤波器实现，以及整个流程和提出的图状态空间网络架构的全面概述。第5节讨论了我们方法的计算复杂性，并强调了它与流行的光谱GNN和基于SSM的GNN的关键区别。第6节展示了在真实世界数据集上的广泛实验结果和性能分析。最后，第7节讨论了潜在的未来发展方向并总结了本文。
