图神经网络的新篇章：通用、强大、可扩展的图变换器

人工智能咨询培训老师叶梓转载标明出处

图变换器（Graph Transformers, GTs）因其在处理节点间全局依赖关系方面的能力而受到广泛关注。然而，现有的GTs模型在处理大规模图时面临着计算复杂度高、泛化能力有限等问题。为了解决这些问题，蒙特利尔大学、麦吉尔大学、新加坡南洋理工大学等研究人员共同提出了一种新的GTs架构——通用、强大、可扩展（GPS）。这种图变换器不仅能够处理具有数百个节点的小规模图，还能扩展到具有数千个节点的大规模图，同时保持线性复杂度O(N + E)。

方法

图1展示了通用、强大、可扩展（GPS）图变换器的模块化架构。该架构是围绕三个核心组件设计的：定位/结构编码（PE/SE）、局部消息传递机制、以及全局注意力机制。这些组件共同工作，提供了一个既能处理小型图也能扩展到大型图的高效图神经网络。

模块化定位/结构编码

局部PE（Local PE）：这类编码使得图中的每个节点能够了解自己在局部邻域中的位置和角色。例如，通过随机游走矩阵的非对角元素的列求和来获得。
全局PE（Global PE）：这类编码让节点了解其在整个图中的全局位置。通常使用图的拉普拉斯矩阵或距离矩阵的特征向量来实现。
相对PE（Relative PE）：这类编码帮助两个节点理解它们之间的距离或方向关系。例如，基于最短路径或热核的节点对距离。

局部消息传递机制 这一机制通过消息传递神经网络（MPNN）实现，它能够处理节点的局部邻域信息。在GPS架构中，MPNN层能够利用节点特征和边缘特征来更新节点的状态。

全局注意力机制 全局注意力层允许图中的每个节点都能够注意到其他所有节点，从而捕获全局依赖关系。这一层通常使用变换器（Transformer）架构实现，它能够处理节点特征并生成节点的全局表示。

GPS层将局部消息传递机制和全局注意力机制结合起来，形成了一个混合层。这一层首先通过MPNN层处理局部信息，然后通过全局注意力层处理全局信息。最终，通过一个多层感知器（MLP）将局部和全局的信息融合，生成综合的节点表示。

GPS架构通过将计算复杂度控制在线性级别（O(N + E)），其中N是节点数，E是边数，从而实现了可扩展性。这意味着即使在大规模图上，GPS架构也能够高效地运行。

现有的大多数GNNs，包括消息传递神经网络（MPNNs），在处理图结构时，往往忽略了PE/SE所包含的信息。研究者们通过1-Weisfeiler-Leman测试（1-WL）展示了MPNNs在没有PE/SE的情况下，无法区分某些非同构图。而通过引入适当的PE/SE，可以显著提高MPNNs的表达能力。

GPS层是MPNN和变换器的混合体，它通过结合局部邻域聚合和全局自注意力机制，减少了初始表示的瓶颈，使得模型能够迭代地进行局部和全局的交互。GPS层通过一系列精确的更新方程来实现，其中包括MPNN层和全局注意力层的输出聚合。

只要给定足够的参数，GPS模型能够为图同构问题提供近似解，比任何Weisfeiler-Leman同构测试都更强大。

想要掌握如何将大模型的力量发挥到极致吗？叶老师带您深入了解 Llama Factory —— 一款革命性的大模型微调工具。实战专家1小时讲解让您轻松上手，学习如何使用 Llama Factory 微调模型。

评论留言“参加”或扫描微信备注“参加”，即可参加线上直播分享，叶老师亲自指导，互动沟通，全面掌握Llama Factory。关注享粉丝福利，限时免费录播讲解。

LLaMA Factory 支持多种预训练模型和微调算法。它提供灵活的运算精度和优化算法选择，以及丰富的实验监控工具。开源特性和社区支持使其易于使用，适合各类用户快速提升模型性能。

实验

实验分为消融研究和基准测试两部分。在消融研究部分，对模型的三个主要组成部分进行了详尽的评估，以确定它们对预测性能的贡献，并为特定数据集的超参数优化提供指导。

全局注意力模块：

实验考虑了O(N^2)时间复杂度的Transformer注意力机制，以及Performer和BigBird的线性时间注意力机制。
结果显示，在多数数据集上使用Transformer都是有益的，除了ZINC数据集，在该数据集上并没有观察到显著变化。这支持了长距离依赖通常很重要的假设。
Performer在预测性能上虽落后于Transformer，但与基线相比仍有提升，并且能够扩展到非常大的图。
在当前设置中，BigBird并未提供显著的增益，且比Performer更慢。

消息传递模块：

评估了各种消息传递架构，发现它们对模型的成功至关重要。没有MPNN层会导致所有数据集的性能显著下降。
尽管普通的PNA通常优于GINE和GatedGCN，但添加PE和SE，尤其是对于GatedGCN，会显著提升性能。

定位/结构编码：

评估了各种PE/SE方案，发现它们通常对下游任务有益。
对于分子数据，随机游走结构编码（RWSE）更有益；而在图像超像素中，拉普拉斯特征向量编码（LapPE）更有益。
使用SignNet与DeepSets编码处理LapPE在任务中表现出一致的成功。

在基准测试部分，将GPS与多种流行的信息传递神经网络（如GCN、GIN、GatedGCN、PNA等）、图变换器（如SAN、Graphormer等）以及其他具有最新结果的图神经网络进行了比较。

表2展示了对全局注意力模块、消息传递模块（MPNN层）和定位/结构编码（PE/SE）的消融研究结果：

全局注意力模块：在多数数据集上，使用Transformer全局注意力都带来了性能的提升，但在ZINC数据集上未见明显变化。这表明对于某些特定类型的图数据，全局注意力可能不是关键因素。
MPNN层：移除MPNN层导致性能显著下降，证实了其在捕获局部图结构信息中的重要性。
PE/SE：不同的编码策略在不同的数据集上表现各异，显示了PE/SE在增强模型对图结构理解中的关键作用。