Less is More: on the Over-Globalizing Problem in Graph Transformers
作者：Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, Chuan Shi
单位：北京邮电大学，北京航空航天大学
摘要：Graph Transformer，由于其强大的全局注意力机制，受到研究者的大量关注并已经成为处理图结构数据的一类重要方法。人们普遍认为，全局注意力机制以全连接图的形式考虑了更广泛的感受野，使得许多人相信 Graph Transformer 可以从所有节点中有效地提取信息。在本文中，我们对这一信念提出了挑战：Graph Transformer 的全局化特性是否总是有益呢？我们首先通过实验证据和理论分析，揭示了 Graph Transformer 中的过全局化问题 (Over-Globalizing Problem)，即当前 Graph Transformer 的注意力机制过度关注那些远端节点，而实际上包含了大部分有用信息的近端节点则被相对忽视了。为了缓解这一问题，我们提出了一种新的采用协同训练的两级全局 Graph Transformer 方法 (CoBFormer)。该方法首先将全图划分成不同的簇，然后分别在簇内以及簇间采用注意力机制来捕获解耦的近端节点信息以及全局信息。同时，我们提出以协同训练的方式来促使我们的两级全局注意力模块 (BGA) 与一个图卷积网络模块 (GCN) 相互学习并提升彼此的性能表现。我们通过理论保证了该协同训练方式可以有效提升模型性能的泛化能力。我们在多个数据集上与 SOTA 模型进行充分比较，实验表明了我们的方法的有效性。
1. 背景与动机
图结构数据是现实世界中普遍存在的一种数据形式，可以有效建模实体之间的交互关系，例如社交网络、交通网络、蛋白质交互网络等。图神经网络 (GNNs) 作为一类成熟的代表性的图机器学习方法，利用消息传递机制可以有效地从图数据中挖掘有效信息并学习高质量的表征。然而由于过平滑 (over-smoothing) 以及过压缩 (over-squashing) 等问题的存在，GNN 通常难以叠加多层，从而其感受野通常被限制在局部邻居之内。另一方面，Transformers 由于其强大的全局注意力机制，使得其具有优越的表达能力，并在自然语言处理，计算机视觉等领域已经取得了巨大的成功。将 Transformer 引入图结构数据可以很好地解决图神经网络所面临的这些问题因为它天然构建了一个全连通图并且可以通过全局注意力机制自适应地学习交互关系。
近年来，已经有了很多将 Transformer 引入到图结构数据中并很好地解决了图上的节点分类、图分类等任务。尽管全局注意力机制已经被视为 Graph Transformers 的一个基本单元，其全局感受野的特性以及强大的全局注意力机制也使得很多人相信 Graph Transformers 可以从所有节点中有效地提取有用信息，但是我们在本文中对这一信念提出了挑战：Graph Transformers 的全局化特性是否总是有益呢？ 我们认为理解 Graph Transformers 的注意力机制，尤其是全局化特性可以为我们设计更加先进的 Graph Transformers 提供有价值的指导。在本文中，我们通过经验性证据以及理论推导揭示了 Graph Transformers 中的过全局化问题。具体来说，我们经验性地发现 Graph Transformers 的全局注意力机制倾向于关注高阶邻居节点，然而局部低阶邻居节点通常会包含更多有用信息，二者之间存在不一致性。尽管高阶邻居节点也可能包含有效信息，但当前的全局注意力机制过度关注于这些节点。我们通过理论阐述了过度扩张的感受野有可能减弱全局注意力机制的有效性，进一步表明了过全局化问题的存在。
既然我们已经指出了 Graph Transformers 中存在的过全局化问题，一个新的问题也自然产生：如何改进现有的 Graph Transformers 的全局注意力机制使得其在保持高阶感受野的同时缓解过全局化问题？ 现有的工作通常显示或隐示地引入一个局部模块（例如GNN）来缓解这一问题，但是 GNN 的局部平滑性以及 Graph Transformers 的过全局化特性，这两种截然不同的性质会引起一个基本的问题：哪一种性质会主导节点的表示？同时，我们发现现有的普遍做法是将局部信息以及全局信息通过线性组合来进行融合，这种方式可能会带来错误的预测结果，尽管单个局部信息或者全局信息会带来正确的预测。
在本文中，我们提出了一种新的采用协同训练的两级全局 Graph Transformer 方法 (CoBFormer)。该方法首先将全图划分成不同的簇，然后提出一个两级全局注意力模块 (BGA)，分别在簇内以及簇间采用注意力机制来捕获解耦的近端节点信息以及全局信息。同时，为了补充 BGA 模块忽视的图结构信息，我们采用一个图卷机网络 (GCN) 来作为局部模块。我们创新性地提出采用一种协同训练的方式来整合 BGA 模块以及 GCN 模块学习的信息并促进它们各自的性能。本文的贡献总结如下：
我们阐述了一个关键的现象：Graph Transformers 通常存在过全局化问题。我们的经验性观察以及理论分析均表明这种问题会影响 Graph Transformers 的性能。我们的发现为改进 Graph Transformers 提供了一个有价值的指导方向。 我们提出了 CoBFormer，一个采用协同训练的两级全局 Graph Transformer 模型。该方法可以有效缓解过全局化问题。理论分析表明我们提出的协同训练方法可以有效提升模型性能的泛化能力。 大量实验表明我们的方法可以打败 SOTA 的 Graph Transformers 方法，并且可以有效解决过全局化问题。
2. 过全局化问题
经验性观察： 为了检验图数据中有效信息的分布情况以及 Graph Transformers 学得的注意力分布情况，我们首先定义两个变量 以及 Attn- 如下：
表示节点 第 跳邻居中与其类别相同的节点的比例，反映了第 跳邻居节点中有效信息的占比。Attn- 表示 Graph Transformers 分配给第 跳邻居的注意力分数之和的均值，反映了其对第 跳邻居节点的整体关注强度。我们在五个真实数据集上可视化了平均 随跳数增长的变化以及 Vanilla Transformer、NodeFormer 在这五个数据集上 Attn- 的变化情况。为了实现这一可视化，我们对多个注意力头的注意力分数进行平均并可视化其第一层的结果。我们发现后续层的可视化也会展现出类似的趋势。
Figure 1 (a) 表明：(1) 在同配图上， 随着跳数增加逐渐递减；(2) 在异配图上， 在 时快速递减随即几乎保持不变。这表明同配图数据集上，距离较近的节点信息对于下游任务更加有用；而在异配图上，全局感受野会为其提供更多信息。Figure 1 (b) 和 (c) 则表明，无论是 Vanilla Transformer 还是专为图数据设计的 NodeFormer，都会为远距离节点分配大部分的注意力分数。这二者之间存在一个明显的不一致，表明了 Graph Transformers 的全局注意力机制会导致过全局化问题。
理论分析： 理想情况下，Graph Transformers 会为表征相近的节点分配更多的注意力分数，因此隐示地学得了一个可以确保相邻节点表征平滑的图结构。这种平滑性可以由 来度量，其中 是节点表征矩阵， 是注意力矩阵。该值越小，表明图结构越好的平滑性，即 Graph Transformers 可以有效识别有用的节点并聚合信息。为了研究影响 的因素，我们首先定义 的可达集合中与其类别相同的节点的比例。具体来说，若该可达集合定义为 跳邻居集合，则 可以写为：
现在，我们通过定理3.1 建立起 与注意力分数 以及 的联系：
定理3.1表明 的上界由不同类别的节点对之间的注意力分数之和确定，并且与 成反比。注意，对于一个给定的训练好的 Graph Transformer, 以及 是定值。然后，我们在定理3.2 中进一步研究了 的变化情况：
定理3.2表明，在同配图（即边同配率 较大的图）中，随着跳数 的增加， 会逐渐收敛减小并收敛到 。而在异配图（即边同配率 较小的图）中，随着跳数 的增加， 会在 附近震荡并最终收敛到 。结合定理3.1，我们发现在同配图中，随着感受野的扩张，逐渐减小的 会导致变小的 ，以及一个变大的 ，这意味着同配图中过度扩张的感受野对于全局注意力来说是有害的。相反的，在异配图中，全局注意力机制会带来更多局部邻居所不包含的有用信息。基于定理3.2，我们可视化了只有两类节点且节点标签分布均匀的情况下 的变化情况：
实验分析： 受到定理3.1 的启发，我们定义注意力信噪比 (Attn-SNR) 作为衡量 Graph Transformers 识别有效节点的量化指标：
对于一个给定的 Graph Transformer，过全局化问题可能会导致注意力机制将更多的注意力分数分配给了不同类别的节点，从而产生较小的 Attn-SNR。我们在 Cora 和 CiteSeer 数据集上采用 Attn-SNR 和准确率评测了传统 Transformer (VT) 以及 NodeFormer (NF) 的性能。我们进一步通过将标签相同的节点对之间的注意力分数提升一倍来人为增强 Attn-SNR (VT-D)，并汇报其性能。
我们可以观察到：(1) 传统 Transformer 表现出最低的 Attn-SNR 从而导致了最低的分类准确率。NodeFormer 展现出更高的 Attn-SNR 以及优越的分类准确率。(2) 通过人为增强传统 Transformer 的 Attn-SNR，并相比 VT 有巨大的性能提升。这是因为我们通过人为引导 Transformer 学得更高的 Attn-SNR，使得模型更加关注局部信息，可以一定程度上缓解过全局化问题并增强模型的分类能力。
3. 方法：CoBFormer
基于上述对过全局化问题的认定和分析 ，可以为我们改进 Graph Transformer 提供有价值的观点和指导。我们提出了一种新的采用协同训练的两级全局 Graph Transformer 方法 (CoBFormer)。该方法首先将全图划分成不同的簇，然后提出两级全局注意力模块 (BGA) 分别在簇内以及簇间采用注意力机制来捕获解耦的近端节点信息以及全局信息。除此之外，我们采用一个 GCN 作为局部模块来辅助学习图结构信息，并提出以协同训练的方式来促使我们的 BGA 模块 与 GCN模块相互学习并提升彼此的性能表现。
3.1 两级全局注意力模块
传统的 Graph Transformers 采用全局注意力机制捕获任意两个节点之间的信息交互，从而导致了过全局化问题的产生。因此，为了缓解过全局化问题，我们需要保证模型对局部信息的捕获能力。为了实现这一目标，我们首先使用 METIS 算法将一张完整的图划分为 个不重叠的簇。我们将簇集合标记为 ，其中 代表原图 的一个子图，并且满足 。
由于局部信息通常存在于每一个簇内，我们采用一个簇内注意力机制 (intra-cluster Transformer) 来保证对局部信息的学习能力。簇 内的节点特征被表示为 ，我们首先采用一个 MLP 将原始节点特征投影到隐空间中，即 。然后通过簇内注意力机制来学习其更新后的隐藏表征 ：
其中 和 是第 k 层 intra-cluster Transformer 内线性投影层的可训练权重，FFN 表示一个前馈神经网络。在每个注意力块以及前馈神经网络中我们都采用了一个残差连接和一个层归一化。
紧接着，我们对 应用平均池化来获得每个簇的表征 。 的第 行，标记为 ，由 计算得到。然后，我们采用簇间注意力机制 (inter-cluster Transforemer) 来捕获全局信息：
其中 和 是第 k 层 inter-cluster Transformer 内线性投影层的可训练权重。尽管 inter-cluster Transforemer 是在簇间学习注意力机制，但如 proposition 4.1 所述，它可以近似 等式1 中的全局注意力机制并有效学习全局信息。
通过 proposition 4.1 我们可以看到，全局注意力的注意力分数 可以 近似表示为 ，后者可以由我们的 inter-cluster Transformer 计算得到。
现在，我们将节点表征与其对应的簇表征拼接起来，并通过由 参数化的融合线性层来计算输出的节点表征：
这里 表示拼接运算， 是一个 维的全 向量， 是簇 的隐藏表征。通过解耦簇内以及簇间的信息，我们的 BGA 模块可以可以缓解过全局化问题并保留捕获全局信息的能力。与此同时，我们的方法将时间空间复杂度降低到了 ，最优情况下可达到 ，这种高效性使得我们的模型可以被应用到大的网络数据集中。值得注意的是，我们的方法可以进一步通过线性注意力机制提升其效率。
3.2 协同训练
除了通过 BGA 模块学习簇内以及簇间的信息，我们还引入了一个 GCN 作为局部模块来补充 BGA 模块丢失的图结构信息。与很多现有方法直接将局部模块以及全局注意力模块捕获的信息进行线性组合用于节点分类不同，我们为 GCN 模块和 BGA 模块提出一个协同训练方法来促使它们互相学习。我们首先将有标签的节点集合定义为 以及无标签的节点集合定义为 ，并用 和 表示他们相应的标签集合。在之前的工作中，模型通常通过预测有标签节点的标签分布以及采用交叉熵损失函数来进行训练。然而，这种做法不能保证对无标签节点的预测性能。
此处，我们首先采用两个线性层，分别将 BGA 模块以及 GCN 模块的输出投影到标签空间中：
然后我们采用 SoftMax 函数来计算预测标签以及软标签：
其中 是一个温度系数用于控制软标签的平滑程度。最终的目标函数可以形式化定义为：
其中 表示节点 的真实标签， 和 分别是 GCN 模块和 BGA 模块的预测标签。 和 表示二者预测的软标签。 是交叉熵损失函数，分类任务的标准选择。 可以鼓励 GCN 模块和 BGA 模块互相监督学习。参数 用于平衡二者之间的贡献。
定理4.2 证明了协同训练方式可以提升 GCN 模块和 BGA 模块在无标签数据上的泛化能力，从而可以实现更好的分类性能。以训练 GCN 模块为例， 是 和 之间的交叉熵，我们的目标是最大化这个交叉熵从而使模型在有标签节点和无标签节点上都能达到最佳的性能表现。然而，由于无标签节点的标签分布未知，这个交叉熵并不能被直接优化。定理4.2 表明该交叉熵可以被分解为三项，其中第一项是 和 的交叉熵，这一项可以通过 进行优化并保证其在有标签节点上实现好的分类性能。第二项是 和 的交叉熵，这一项可以通过 进行优化并表明我们可以通过协同训练的方式进一步提升模型在无标签节点上的分类性能。第三项是 和 之间的 KL 散度，值得注意的是，当我们优化 GCN 模块的时候，这是一个常量，并且这个值会随着 BGA 模块的优化逐渐减小。综上，GCN 模块和 BGA 模块的分类性能可以通过上述的目标函数得到提升。
4. 实验
为了验证我们的方法的有效性，我们在七个数据集 (包括同配图数据集 Cora、CiteSeer、Pubmed、Ogbn-Arxiv、Ogbn-Products 以及异配图数据集 Actor、Deezer，其中 Ogbn-Arxiv 和 Ogbn-Products 是较大规模的网络数据集) 上与五个基线模型比较节点分类性能。
实验结果表明：
传统的 Graph Transformer 方法在异配图上展现出优越的性能，然而在同配图上的优势则相对有限。这表明同配图中局部信息扮演着更加重要的角色然而全局信息可以显著增强模型在异配图中的表现。这与我们对过全局化问题的分析结果一致。 在同配图数据集上，我们提出的 CoBFormer 中的 GCN 模块和 BGA 模块均大幅优于五个基线模型，表明了我们的方法在同配图数据集上的有效性； 在异配图数据集上，我们的 BGA 模块与最强大的基线模型 SGFormer 相比，可以实现可比甚至更强的性能，表明我们的方法可以有效捕获全局信息；
5. 消融实验及分析
消融实验 我们在 Cora，PubMed 以及 Deezer 上展开了消融实验来评测我们的方法中两个基本模块 ( BGA 模块以及协同训练方式) 的有效性。
通过消融实验，我们有以下关键发现：
无论是否使用协同训练方式，在所有数据集上，BGA 模块的分类准确率均一致优于传统的 Transformer (VT)，表明了我们提出的 BGA 模块的有效性； 使用协同训练方式会显著提升我们的 GCN 模块和 BGA 模块的性能，说明其可以通过鼓励这两个模块相互学习从而增强模型的泛化能力； 我们提出的 BGA 模块显著减小了 GPU 的内存占用，一定程度上解决了无法扩展到大规模网络数据上的问题。特别的，我们的方法在 PubMed 上减少了 94% 的内存占用以及在 Deezer 数据集上减少了 80% 的内存占用；
过全局化问题 为了阐述我们提出的 CoBFormer 方法缓解过全局化问题的能力，我们可视化了 CoBFormer 的 Attn- 指标如下。
与 Figure 1 中 (b) 和 (c) 相比，我们的相比 Vanilla Transformer 和 NodeFormer 会分配更多的注意力分数在局部区域中，表明 BGA 模块通过解耦簇内信息和簇间信息，可以有效缓解过全局化问题。我们进一步计算了 Attn-SNR 和测试准确率来表现 CoBFormer 区分有用节点并提取有效信息的能力。
显然，通过采用 BGA 模块，CoB-T 的 Attn-SNR 显著提升且在 Cora，CiteSeer，PubMed 数据集上带来巨大的性能提升，表现了 CoBFormer 的有效性并可以缓解过全局化问题。在 Actor 和 Deezer 数据集上，CoB-T 实现了与 Vanilla Transformer 可比的性能，表明 CoBFormer 可以有效捕获全局信息。
参数实验 我们分析了关键参数：协同学习强度系数 、温度系数 以及簇数目 P。我们将 设定为 {1.0, 0.9, 0.8, 0.7} 进行测试，并在 Figure 6 中报告最佳性能表现。结果表明，除 ，即不使用协同训练方式的情况外，我们的模型在其他值上均取得了显著的性能提升。此外，模型在不同 值上表现出一致的性能，强调了我们协同训练方法的有效性和鲁棒性。
接下来，我们固定最佳的 ，并对不同 值 {0.9, 0.7, 0.5, 0.3} 下的最优性能进行了测试。在 Figure 7 中可以看出，选择适当的 对性能有显著影响，这突出了选择合适 以获得最佳结果的重要性。
最后，我们固定最佳的 和 值，并选择不同的簇数目来报告分类准确率，结果如 Figure 8 所示。结果表明，在 Deezer 数据集上，不同聚类数目的性能变化不大，而在其他数据集上，最佳聚类选择对于达到最优性能至关重要。尽管如此，即使没有理想的聚类选择，模型通常也能超过其他模型，展示了其在聚类数目变化下的鲁棒性。
6. 总结
在本文中，我们通过理论见解和实证结果发现了 Graph Transformer 中的过全局化问题。然后，我们提出了一种双层全局图变换器CoBFormer，并采用协同训练，旨在缓解过度全局化问题并提高泛化能力。大量实验验证了CoBFormer的有效性。
论文链接：https://arxiv.org/abs/2405.01102 点击阅读原文可跳转
代码链接：https://github.com/null-xyj/CoBFormer
