图变换器的再思考：谱注意力网络

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

图神经网络（GNNs）的传统策略是通过稀疏的消息传递过程直接编码图结构。然而，这种方法存在固有的局限性，例如过度平滑和过度压缩问题，这些限制了模型的性能和表达能力。为了克服这些限制，麦吉尔大学、米拉蒙特利尔研究所、渥太华大学等研究者们提出了一种基于谱图理论的新型可学习位置编码方法，即谱注意力网络（SAN），该模型巧妙地利用图的谱特性，通过学习位置编码（Learned Positional Encoding，简称LPE）来表征图中的节点，从而解决了传统图神经网络在表达能力上的一些限制。

表1 比较了不同的图变换器模型（GAT, GT sparse, GT full, SAN）的属性，展示了每个模型是否保留了局部结构、是否使用边特征、是否连接非邻近节点等特性。

模型架构

图1展示了谱注意力网络（SAN）模型，该模型通过节点学习位置编码（LPE）将变换器（Transformers）泛化到图结构数据上。这个模型结合了变换器架构的强大能力和图数据结构的特性，以处理图表示学习中的问题。

输入图：模型的输入是一个图，包括节点特征和邻接矩阵。
预处理步骤：
- 计算拉普拉斯矩阵的特征向量：首先计算图的拉普拉斯矩阵的特征向量和特征值。这些特征向量和特征值用于后续的位置编码。
- 生成节点位置编码（LPE）：使用特征向量和特征值为每个节点生成初始的位置编码。
主变换器步骤：
- 全连接图：为了使模型能够捕捉长距离依赖，通过添加所有不直接连接的节点对之间的边，将输入图转换为全连接图。
- 特征融合：将节点特征和从LPE得到的位置编码进行融合。
- 应用变换器：使用变换器架构处理融合后的特征，通过自注意力机制学习节点间的复杂关系。
输出：
- 预测层：根据任务需求（如节点分类、图分类等），将变换器的输出送入预测层，生成最终的预测结果。

SAN模型的架构设计主要围绕如何有效地利用图的谱信息。该模型通过将图的拉普拉斯特征映射到固定大小的LPE，使得网络能够利用每个图的整个拉普拉斯谱。这一过程分为两个步骤：

节点的LPE Transformer：首先，模型对每个节点应用Transformer，处理与该节点相关的拉普拉斯特征，生成每个图的LPE矩阵。
图Transformer：然后，将LPE与节点嵌入拼接，传递给图Transformer进行处理。如果任务涉及图分类或回归，最终的节点嵌入会被传递到一个最终的池化层。

在节点的LPE Transformer部分，模型首先为每个节点创建一个大小为2×m的嵌入矩阵，通过将m个最低的拉普拉斯特征值及其对应的特征向量进行拼接。这里的m是一个超参数，表示计算的最大特征向量数量。如果m大于图中的节点数N，模型会添加掩码填充。

在图 4 中，展示了LPE架构。模型通过考虑m个特征值和特征向量，意识到了图的拉普拉斯谱。每个节点可以被视为一批中的一个元素，从而并行化计算。这里的$\phi_{i,j}$是与第i个最低特征值$\lambda_i$配对的特征向量的第j个元素。

边的LPE Transformer是另一种拉普拉斯编码的形式，它解决了节点特征中特征向量符号任意性的问题。与将绝对位置编码为节点特征不同，这种方法考虑将相对位置编码为边特征。通过计算两个节点之间的差的绝对值和乘积，可以获得与符号不变的操作符，这表明单个节点上的$\phi_{i,j1}$的符号并不重要，而节点j1和j2之间的相对符号才是重要的。

主要的图Transformer基于先前的工作，通过考虑图结构和通过边特征嵌入改进注意力估计，将原始的Transformer应用于图。模型采用了多头注意力机制，通过所有节点进行计算。

尽管SAN模型在理论上具有强大的表达能力，但它也存在一些局限性。首先，节点级别的LPE缺乏符号不变性，随机翻转特征向量的符号可能会产生不同的LPE输出。LPE的计算复杂度为O(m^2N)，当考虑所有特征函数时，复杂度为O(N^3)。这限制了模型在GPU上的内存使用。

由于完全连接性，SAN模型不受其卷积/消息传递对应物在表达能力上的相同限制。模型使用完整的特征函数集，并且给定足够的参数，可以区分任何一对非同构图，并且在这方面比任何WL测试都更强大。然而，这并没有解决多项式时间内的图同构问题；它只是近似一个解决方案，所需的参数数量是未知的，可能不是多项式的。

由于全连接网络，模型不存在过度压缩问题，因为远距离节点之间存在直接路径。SAN模型使用拉普拉斯谱更有效地学习节点之间的物理交互，这与需要深层网络来捕获长距离交互的卷积方法形成对比。

SAN模型通过创新的谱注意力机制，为图神经网络的发展提供了新的方向，尤其是在处理具有复杂拓扑结构的图数据时。

想要掌握如何将大模型的力量发挥到极致吗？叶老师带您深入了解 Llama Factory —— 一款革命性的大模型微调工具（限时免费）。

1小时实战课程，您将学习到如何轻松上手并有效利用 Llama Factory 来微调您的模型，以发挥其最大潜力。

CSDN教学平台录播地址：https://edu.csdn.net/course/detail/39987

实验

谱注意力网络（SAN）在多个标准图数据集上进行了测试，包括ZINC、PATTERN、CLUSTER、MolHIV和MolPCBA。这些数据集被用于验证SAN模型在处理图数据时的有效性和性能。

首先进行了消融研究以评估全注意力和节点学习位置编码（LPE）的效果。通过调整平衡稀疏和全注意力的γ参数，研究了模型在不同数据集上的性能变化。图 5 展示了γ参数对使用节点LPE的模型性能的影响。结果表明，对于分子数据集ZINC和MolHIV，全注意力的好处有限，而对于更大的SBM数据集（PATTERN和CLUSTER），更高的γ值有助于提升性能。

在图 6 中，展示了在稀疏和全图架构中节点LPE影响的消融研究。研究发现，对于分子任务（ZINC和MolHIV），节点级别的LPE显著提升了模型性能，这可以归因于其在检测子结构方面的能力。而对于PATTERN和CLUSTER数据集，由于任务本身较为简单，LPE的提升作用相对较小。

与当前最先进（SOTA）模型的比较中，SAN模型在所有合成数据集上的表现均优于其他模型，这突出了SAN模型的强大表达能力。在MolHIV数据集上，尽管测试集上的性能略低于SOTA，但在验证集上的性能却优于PNA和DGN模型。这一现象可能与该数据集的一个众所周知的问题有关：验证集和测试集的指标相关性较低。