GrassNet：状态空间模型与图神经网络的结合

《Pattern Recognition》：GrassNet: State Space Model Meets Graph Neural Network

针对传统谱图神经网络滤波器设计的局限性，本文提出GrassNet，通过结构状态空间模型（SSMs）建模图信号不同频率的关联，实现全局谱分布建模。该模型为每个频率设计唯一整流，解决相同频率不同信号基的调制问题，在九个基准数据集上验证其优于多项式和小波基的滤波器设计。

　　

赵功培|王涛|金毅|郎从彦|李一东|凌海斌

教育部北京交通大学大数据与人工智能交通应用重点实验室

摘要

在图学习中，设计光谱卷积网络是一个重要的挑战。在传统的光谱图神经网络（GNN）中，通常使用基于多项式的方法通过拉普拉斯矩阵来设计滤波器。然而，在实际应用中，这些多项式方法存在固有的局限性，主要源于多项式滤波器的低阶截断以及对图谱的整体建模不足。这导致现有的光谱方法在处理真实世界图数据时性能较差，尤其是当图谱高度集中或包含许多数值相同的值时，因为它们倾向于对具有相同频率的信号应用完全相同的调制。为了解决这些问题，本文提出了GrassNet（Graph State Space Network），这是一种新型图神经网络，它具有理论支持，能够简单而有效地设计和学习任意的图谱滤波器。具体来说，我们的GrassNet引入了结构化状态空间模型（SSM）来模拟不同频率下图信号的相关性，并为图谱中的每个频率推导出独特的整流方式。据我们所知，我们的工作是首次将SSM用于GNN光谱滤波器的设计，并且在理论上比多项式滤波器具有更强的表达能力。在九个公开基准测试上的广泛实验表明，GrassNet在真实世界图建模任务中表现优异。代码可在以下链接获取：https://github.com/Graph-ZKY/grassnet

引言

作为专门为处理和学习图数据而设计的神经网络类别，图神经网络（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节讨论了潜在的未来发展方向并总结了本文。

章节片段

光谱图神经网络

光谱GNN通过在光谱域过滤图信号来工作。ChebNet[6]使用切比雪夫多项式来近似光谱滤波器。APPNP[22]利用个性化PageRank来推导传播矩阵，作为固定滤波器。GPR-GNN[7]通过学习单项式基的组合系数引入了一个可学习的过滤模型。FAGCN[23]设计了一种自适应的门控机制，以便在消息传递过程中适应性地整合不同的信号。

符号说明

为了确保我们陈述的清晰性和一致性，我们提供了本文中使用的符号的简要概述。分析中使用的标量用斜体小写字母表示（例如，m, n），而方法中使用的向量用粗体小写字母表示（例如，x, y）。本文中的所有向量都被假定为列向量。粗体大写字母（例如，W, Z）用于表示矩阵。此外，我们的符号中的下标和上标

序列光谱图过滤范式

图1展示了现有光谱图滤波器在调制方面的局限性。这主要是因为现有的图滤波器独立地建模拉普拉斯矩阵的每个特征值，假设图谱中的所有频率都遵循独立同分布（i.i.d.）的假设，而没有充分考虑它们之间的潜在相关性，例如，对应于数值相同的信号基之间的相互正交性

复杂性分析

我们的方法包括三个主要步骤：光谱分解、滤波器学习和图卷积。我们将分解作为预处理步骤，除非硬件限制显著，否则对大型数据集的影响最小。对于大型图，可以使用近似迭代算法（如Lanczos算法[43]）进一步将复杂性降低到$O(n·m)$，其中m表示稀疏矩阵中非零元素的数量。滤波器学习的时间复杂性在很大程度上取决于

数据集统计

我们在九个不同领域的基准数据集上评估了我们的方法：引用网络（Cora, CiteSeer, PubMed）[45]、[46]、亚马逊共同购买图（Photo）[47]、维基百科图（Chameleon, Squirrel）[48]、演员共现图（Actor）[49]以及WebKB的网页图（Texas, Cornell）[49]。采用的数据集具有代表性，描述了多种现实生活场景。其中一些数据集高度同质，而另一些则异质。数据集的详细统计信息是

结论

在本文中，我们探讨了状态空间模型作为图神经网络中光谱滤波器的潜力，从而提出了新型的光谱图神经网络GrassNet。它利用精心设计的SSM图滤波器有效地模拟图谱序列，理论上比传统的基于多项式和小波的滤波器具有更强的表达能力。这种增强的能力使GrassNet能够适应性地处理复杂的谱模式

CRediT作者贡献声明

赵功培：撰写——审阅与编辑、撰写——原始草稿、可视化、监督、软件、方法论、形式分析、数据整理、概念化。王涛：撰写——审阅与编辑、验证、监督、方法论、形式分析。金毅：撰写——审阅与编辑、监督、方法论。郎从彦：撰写——审阅与编辑、监督、方法论。李一东：验证、监督。凌海斌：撰写——审阅与编辑、监督、方法论。

利益冲突声明

我们声明与可能不当影响我们工作的其他人或组织没有财务和个人关系。在任何产品、服务或公司中，无论出于何种性质或原因，我们都没有专业或其他个人利益，这些利益可能会影响本文中提出的观点或手稿的审查。

致谢

本工作得到了国家自然科学基金（编号62376020）的支持。