NWGformer：一种具有注意力分数非线性重新加权的线性图变换器

《Knowledge-Based Systems》：NWGformer: A Linear Graph Transformer with Non-linear Re-weighting of Attention Scores

本文提出一种新型非线性重加权算子（NWO），通过利用节点间语义和拓扑特征的相对差异对注意力分数进行非线性重加权，解决线性图Transformer模型因缺乏Softmax的聚焦能力导致的信息扩散问题。结合特征重加权与拓扑重加权机制，构建NWGformer-F和NWGformer-T两个高效模型，在15个异构图数据集上验证其显著优于现有GNN和线性GT方法，同时保持线性复杂度。

　　近年来，图神经网络（GNNs）和图变换器（GTs）在处理图结构数据方面取得了显著进展。图结构数据通常包含节点的属性和节点之间的连接关系，这种非线性结构使得传统方法难以高效建模。因此，研究者们不断探索新的方法，以在保持模型表达能力的同时提高其可扩展性。其中，注意力机制在图变换器中扮演了重要角色，但传统的Softmax注意力机制在计算复杂度上存在明显问题，而线性注意力机制则在保留注意力分布的聚焦性方面表现不足。为了解决这一问题，本文提出了一种新的非线性重新加权操作符（NWO），它能够通过利用节点间有效信息的成对差异，对注意力分数进行非线性重新加权，并引入隐式正则化，从而提升模型对关键节点关系的捕捉能力。

图变换器在自然语言处理和计算机视觉领域已经取得了成功，但在图结构数据上的应用仍处于探索阶段。传统的图神经网络主要依赖于局部信息聚合，即每个节点通过其直接邻居的特征进行更新。然而，这种局部方法在处理全局属性时存在局限，如信息过平滑（oversmoothing）和信息过压缩（over-squashing）等问题。此外，图结构的不规则性和不完整性也使得局部方法难以充分建模全局关系。为了解决这些问题，研究者们尝试将图神经网络与线性变换器结合，以实现更高效的全局关系建模。这类线性GT通常采用随机特征映射、非局部扩散操作符或线性核近似等方法，将语义相关函数分解为更小的部分，并利用矩阵乘法的结合性将全局注意力的计算复杂度从O(N2)降低到O(N)。然而，这种方法在注意力分数的分布上失去了Softmax机制的关键特性，从而影响了模型的聚焦能力。

本文的研究灵感来源于上述方法的不足，旨在设计一种能够兼顾计算效率与表达能力的线性GT架构。具体来说，我们提出了一种新的非线性重新加权操作符（NWO），该操作符不同于现有方法中使用非线性激活函数对查询和键进行模拟，而是通过节点间有效信息的成对差异生成权重，并直接对全局注意力分数进行非线性重新加权。NWO不仅提供了有效的隐式正则化，还确保了注意力分数的非负性，并实现了类似于Softmax操作符的非线性重新加权机制。为了实现线性计算复杂度下的全局注意力计算，我们进一步采用核技术对操作符进行分解，并利用矩阵乘法的结合性实现高效的全局注意力建模。

考虑到图数据的内在特性，我们设计了两种重新加权方案：一种是基于节点特征的重新加权（feature re-weighting），另一种是基于拓扑结构的重新加权（topology re-weighting）。在特征重新加权中，我们将节点特征映射到潜在空间，并利用NWO建模该空间中的成对特征差异，从而对注意力分数进行自适应加权。这一机制同时优化了点积相似度和特征差异的分布，确保只有当两个信号都表明强关联时才会分配高注意力分数，同时抑制无用的分数，从而实现更精确的节点关系建模。在拓扑重新加权中，我们使用单源最短路径距离作为节点的拓扑特征，并将成对的拓扑特征输入NWO中，以提取邻域关系并重新加权注意力分数，引导模型关注节点之间的关键拓扑关系。

在实验部分，我们对15个图数据集进行了系统评估，包括同质图（homophilic）和异质图（heterophilic）设置，以及大规模图数据。实验结果表明，我们的两种NWGformer变体（NWGformer-F和NWGformer-T）不仅在关注能力上表现出色，还在大多数数据集上超越了现有的GNN和线性GT模型。值得注意的是，在最大100万节点的可扩展性评估中，NWGformer变体的运行时间和内存使用量随着图规模的增长几乎呈线性增长。同时，在多个数据集上，我们的模型在使用更少的网络层数和更少的训练轮次的情况下，取得了比竞争方法更高的分类准确率。这些结果表明，NWGformer提供了一种高效且可扩展的解决方案，适用于大规模节点嵌入学习。

此外，本文还对多种线性变换器进行了系统比较，实验结果表明，广泛应用于现有GT中的线性变换器在关注关键节点对方面存在困难，导致注意力分布分散。进一步分析发现，保持注意力分数分布的非负性和尖锐性对于模型的聚焦能力至关重要，而我们提出的NWO机制有效地弥补了这一不足。我们的方法在保持模型表达能力的同时，通过引入隐式正则化和非线性重新加权，使得模型能够在大规模图数据上实现高效的全局关系建模。

在实现方面，我们设计了两种不同的注意力模块：一种是基于NWO的局部注意力模块，另一种是基于NWO的全局注意力模块。通过将这两种模块有机地结合在一起，我们提出了一个新的框架NWGformer，用于学习节点表示。在该框架中，我们根据全局注意力中使用的NWO，开发了两种变体：NWGformer-F和NWGformer-T，分别基于特征和拓扑的重新加权。这些变体不需要昂贵的位置编码（position encoding）或辅助损失函数，同时能够高效捕捉任意节点对之间的长距离依赖关系。

为了验证我们的方法的有效性，我们在多个数据集上进行了广泛的实验，包括同质图和异质图设置。实验结果表明，我们的方法在大多数数据集上都优于现有的GNN和GT模型。特别是在大规模图数据的测试中，我们的模型在保持高分类准确率的同时，表现出更好的可扩展性。这表明，我们的方法在处理大规模图数据时，能够在不牺牲性能的前提下，显著减少计算资源的消耗。

本文的主要贡献包括：首先，我们首次在一种线性GT中引入了非线性注意力分数的重新加权机制，通过基于节点间成对差异的NWO，增强了模型对复杂依赖关系的建模能力；其次，我们设计了两种重新加权方案，分别基于特征和拓扑的特性，以进一步提升模型的表达能力；再次，我们提出了一个结合局部和全局注意力模块的框架，使得模型能够在不依赖复杂位置编码的情况下，实现高效的全局关系建模；最后，我们对多种线性变换器进行了系统比较，并发现保持注意力分布的非负性和尖锐性对于模型的聚焦能力至关重要，而我们的NWO机制能够有效解决这一问题。

在数据方面，我们使用了多个公开的数据集，包括Planetoid、Planetoid扩展版以及OGB（Open Graph Benchmark）等数据集。这些数据集涵盖了同质图和异质图的场景，并且适用于大规模图结构的分析。所有数据集都可以在GitHub上找到，并且我们提供的代码也在GitHub上公开，方便其他研究者进行复现和进一步研究。

在模型设计方面，我们不仅关注计算效率，还注重模型的表达能力。传统的Softmax注意力机制虽然能够提供良好的聚焦性，但其计算复杂度较高，难以应用于大规模图数据。而线性注意力机制虽然计算复杂度较低，但在保持注意力分布的聚焦性方面存在明显不足。为此，我们提出了一种新的非线性重新加权操作符（NWO），该操作符能够基于节点间有效信息的成对差异，对注意力分数进行非线性重新加权，并引入隐式正则化，从而在保持注意力分布的聚焦性的同时，提高计算效率。

在实验结果中，我们发现，尽管线性GT模型在计算效率和表达能力之间取得了一定的平衡，但它们仍然继承了线性变换器的一些固有缺陷，如全局依赖关系过于平滑和对无关特征的过度聚合，这些缺陷最终限制了模型的表达能力。而我们提出的NWO机制能够有效解决这些问题，使得模型在大规模图数据上仍能保持较高的性能。

此外，我们还对不同类型的图数据进行了实验分析，包括同质图和异质图。在同质图中，节点之间的连接关系通常具有相似的特征，因此局部方法可能已经足够。而在异质图中，节点之间的连接关系更加复杂，局部方法难以充分建模全局关系。因此，我们提出的方法在异质图上的表现尤为突出，能够更好地捕捉节点之间的关键关系。

在实际应用中，图变换器已被广泛用于分子属性预测、动态模拟和图生成等任务。然而，如何在节点表示学习中实现满意的性能仍然是一个未解决的挑战。我们的方法通过引入非线性重新加权机制，能够在保持模型表达能力的同时，提高计算效率，从而在大规模图数据上实现高效的节点表示学习。

总的来说，本文提出了一种新的非线性重新加权操作符（NWO），并将其应用于图变换器中，以解决传统方法在计算效率和表达能力之间的矛盾。我们的方法不仅在计算复杂度上实现了线性增长，还在保持注意力分布的聚焦性方面表现优异，从而提升了模型的整体性能。实验结果表明，我们的方法在多个数据集上都优于现有的GNN和GT模型，特别是在大规模图数据上的表现更为突出。这些结果为图结构数据的处理提供了一种新的思路，并为未来的研究奠定了基础。