GraphMinNet：基于低复杂度极简架构学习图中的依赖关系

《Neural Networks》：GraphMinNet: Learning Dependencies in Graphs with Light Complexity Minimal Architecture

　　摘要图神经网络在多种应用中取得了显著成果。尽管如此，传统图神经网络由于依赖局部消息传递机制，往往难以有效捕捉长距离依赖关系。本文提出了GraphMinNet，这是一种专为图结构数据设计的新型图神经网络框架，其灵感来源于序列学习中使用的最小门控循环单元。该框架能够在保持排列等变性和稳定性的同时，以线性计算复杂度实现对长距离依赖关系的建模，并且其表达能力经过数学证明优于1-WL测试标准。通过整合节点特征与图的结构和位置信息，该框架的表达能力也得到了证实。我们通过严格的理论分析证明了该框架的各项特性，包括捕捉长距离依赖关系的能力、表达能力、利普希茨稳定性、排列等变性以及线性复杂度。在包括分子图、图像图和合成网络在内的十个不同数据集上的大量实验表明，GraphMinNet在保持高计算效率的同时实现了最先进的性能。我们的结果显示，该框架在大多数数据集上表现优异，在其他数据集上也具有竞争力，从而验证了其在捕捉局部和全局图结构方面的有效性。我们的代码可在相应仓库中获取。

引言图结构在从社交网络、知识表示到工程学等多个领域都有广泛应用。图神经网络为从图数据中提取信息并进行推理提供了重要技术手段。虽然已经开发出了众多图神经网络模型，但仍有许多重要挑战需要克服。图神经网络面临的一个核心挑战就是捕捉长距离依赖关系——即建模图中相距较远的节点之间的关系。传统的图神经网络通常采用节点间的消息传递方式，每一层仅允许信息传播一步。要到达较远的节点，信息必须经过多层传递，这就导致了所谓的过度压缩现象：随着信息在多层中传播，来自多个源节点的消息会被压缩成固定大小的节点表示，从而导致过度压缩并丢失重要细节。这种过度压缩问题在深度图神经网络或高度连接的图中尤为严重，会形成信息瓶颈，阻碍对长距离关系的有效建模。

捕捉长距离依赖关系至关重要，因为许多现实世界中的图本质上都包含重要的长距离关系，需要理解全局图结构。除了过度压缩问题之外，试图通过深度消息传递来捕捉这些依赖关系还会带来其他挑战，如过度平滑（导致节点特征过于相似）、梯度消失以及信息稀释。因此，尽管图神经网络的性能往往取决于对局部和远处图结构的捕捉，但现有方法仍难以解决这一根本矛盾。为了解决这些挑战，人们提出了多种方法，包括针对更长路径的注意力机制、全局图特征、跳跃连接、图扩散以及多尺度架构等。虽然这些方法显示出潜力，但基于注意力和多尺度的方法在处理大型图时往往存在计算可扩展性问题，而像跳跃连接和全局特征这样的简单方法则可能在复杂的图结构上容易过拟合。

为了解决这些限制，我们提出了一种新的方法，能够在线性计算复杂度下实现有效的长距离依赖关系建模。我们的关键思路来源于循环神经网络，尤其是最近出现的一种名为minGRU的变体，它已被证明能够在保持线性复杂度的同时，出色地捕捉序列数据中的长距离依赖关系。然而，将minGRU应用于图数据面临着诸多挑战，因为序列数据和图结构之间存在本质差异。与具有自然顺序的序列数据不同，图节点缺乏内在顺序。此外，图还通过边包含显式的结构信息，而这在普通序列数据中是不存在的。为了解决这些差异，我们开发了GraphMinNet。该框架没有保留minGRU的有序序列递归结构，因为这与图的排列等变性不相容，而是采用了其高效的并行形式。具体而言，它保留了minGRU的线性可扩展上下文聚合和基于内容的门控机制，同时用由拉普拉斯位置编码调制的无序跨节点聚合替代了依赖顺序的累积交互。这种设计在保持minGRU计算效率的同时，融入了图特有的结构信息。从这个角度来看，GraphMinNet包含一个可学习的融合门，能够平衡全局跨节点证据与每个节点的自身位置先验，从而使模型在同质区域强调全局一致的上下文，在异质或噪声较大的邻域则侧重于局部位置信息。

总之，本文的贡献如下：•我们将RNN的一种变体——最小GRU的概念推广到图结构数据，开发了一种高效的算法，可将节点特征与位置编码相结合；•由此产生的GraphMinNet模型具有多项优势，包括强大的长距离依赖关系捕捉能力、在图区分能力方面介于1-WL和3-WL之间的表达能力，以及线性计算复杂度，而且所有这些特性都拥有可证明的性能保障；•通过在不同数据集上的大量实验，我们证明了相比现有的最先进基准方法，我们的算法在预测精度和效率方面都具有更优的表现。

相关工作我们将用于预测或分类任务的现有图神经网络根据其主要网络架构分为几类。值得注意的是，较新的模型往往结合了多个类别的元素。基于GCN或消息传递的模型。这类方法通过消息传递或图卷积利用空间域或谱域运算。主要方法包括图卷积网络（GCN）、门控GCN等。GRU已经经过改进，变成了minGRU，从而克服了梯度消失/爆炸的问题，能够更好地捕捉全局依赖关系。对于一个由标记组成的输入序列，minGRU的定义如下：ht=(1?zt)⊙ht?1+zt⊙h?t，其中zt=σ(Lineardh(xt))，h?t=Lineardh(xt)，这里xt∈Rd是输入特征向量，ht∈Rd是其在时间t对应的状态空间表示。其中σ(·)是取值在(0, 1)之间的逐元素非线性激活函数，Lineardh(xt)则将xt投影到d维空间。

实验在本节中，我们将展示实验结果。表1总结了我们的方法在多个数据集上与几种强大基准方法的对比性能。我们在10个不同的数据集上评估了我们的方法，详细说明见E.1部分（表E.8）。我们的评估涵盖了几个主要的数据集类别：1）长距离图基准测试（Dwivedi等人，2022年），该测试要求对长距离交互进行有效推理，包含三项任务。

消融研究我们进行了消融研究，分析了GraphMinNet的关键组成部分，包括可选的自项贡献、dropout的有效性以及局部方法的影响。为了使这些评估既有信息量又具备实际计算可行性，我们选择了三个具有不同图学习特性的代表性数据集：ogbg-molhiv，这是一个具有二元图级标签的分子属性预测基准测试；Peptides-func，这是一个多标签图分类基准测试，旨在评估……

结论本文介绍了GraphMinNet，这是一种新型图神经网络，它能够在保持线性计算复杂度的同时有效捕捉长距离依赖关系。我们的方法成功地将最小GRU的概念推广到图结构数据，同时保持了排列等变性并确保了稳定性，而且从理论上保证了图中任意距离处的梯度都不会消失。我们的主要贡献包括高效地将节点特征与位置信息相结合……

CRediT作者贡献声明Md Atik Ahamed：写作——审阅与编辑，写作——初稿撰写，可视化，验证，软件，资源，方法论，研究，形式分析，数据整理，概念构思。Andrew Cheng：写作——审阅与编辑，写作——初稿撰写，验证，方法论，形式分析，概念构思。Qiang Ye：写作——审阅与编辑，写作——初稿撰写，可视化，验证，监督，项目管理，方法论，研究，资金支持。

利益冲突声明作者声明他们没有已知的可能影响本文所述工作的财务利益或个人关系。

致谢本研究部分得到了美国国家科学基金会IIS 2327113和ITE 2433190项目的支持，美国国立卫生研究院R21AG070909和P30AG072946项目的支持，以及国家人工智能研究资源（NAIRR）试点项目NSF OAC 240219、Jetstream2、Bridges2和Neocortex资源的支持。我们还要感谢肯塔基大学计算科学与信息技术服务研究计算中心对Lipscomb计算集群及相关研究的支持与使用。

Md Atik Ahamed|Andrew Cheng|Qiang Ye|Qiang Cheng