专题解读|Graph Transformer 最新研究进展

图结构数据可以有效表示和建模显示世界中的任意交互关系，如社交网络、蛋白质网络和交通网络等，甚至以自然语言为代表的序列数据和以视觉为代表的网格数据也均可以通过“图”来进行建模表示。自 GCN[1] 出现以来，基于消息传递机制的图学习范式迅速成为了图机器学习领域的主流研究热点，然而过平滑[2]和过压缩[3]问题的存在使得基于消息传递的图神经网络无法叠加多层，使其感知范围只能局限于 2-3 跳邻居之内，大大限制了这类方法解决长范围依赖问题的能力。另一方面，Transformer 模型在自然语言处理以及计算机视觉领域取得的巨大成功也让众多研究者开始将目光转向 Graph Transformer 的研究中来。Graph Transformer 通过其全局注意力机制，自适应选择节点进行注意力计算，从而可以自然地避免过平滑、过压缩问题。同时，其全连接机制使得其可以打破固有的结构偏置，从而学习发现对下游任务更加重要的图结构。早期经典工作如 Gophormer[4]、Graphormer[5]、GraphGPS[6]等分别在节点级别和图级别任务上取得了一定了成果。接下来，我将对近期一些有代表性的 Graph Transformer 方法进行介绍和解读。

1. EXPHORMER

EXPHORMER[7] 是谷歌为了解决 Transformer 模型由于其 的时间空间复杂度导致难以扩展到大图上而提出的一种面向图数据的稀疏注意力机制。该方法发表在了 ICML 2023 上。具体来说，为了解决由于高复杂度导致的扩展问题，EXPHORMER 提出通过三种稀疏的注意力机制组合来实现近似的 Graph Transformer。

• 局部注意力机制：通过在原始图结构，即图 (a) 上计算注意力分数，来实现局部注意力机制。
• 扩张图注意力机制：首先对原始图结构进行扩张形成扩张图 。如上图中的 (b)，就是通过算法生成的每个节点的度均为 3 的扩张图。得到扩张图之后，可以基于扩张图的结构进行注意力计算。
• 全局注意力机制：传统的  Graph Transformer 方法为了获得全局信息需要进行全连接的注意力计算，从而导致巨大的资源开销。EXPHORMER 通过引入虚拟节点和虚拟连接，如图 (c)，并计算每个节点与虚拟节点之间的注意力，有效解决了这一问题。

通过这种方式，EXPHORMER 实现了以较低的资源开销捕获全局信息，同时保证了对原始图结构的有效学习。作者通过理论证明了提出方法的有效性并进行了大量的实验验证。

2. SGFormer

SGFormer[8] 是上海交通大学的研究团队提出的一种用于大图表示学习 Graph Transformer，该研究成果成功发表在了 NeurIPS 2023 上。首先，作者定义了一种简化的全局注意力机制：

这种注意力机制抛弃了传统注意力计算中的 SoftMax 函数，从而使得可以先进行 的计算，而不用先计算 的 的注意力矩阵，大大减小了内存开销。同时，作者还理论证明了单层单头的全局注意力机制就足够解决节点分类任务。除此之外，作者还引入一个 GNN 来捕获图的局部信息。

通过该架构，作者实现了局部信息和全局信息的融合，并可以高效泛化到大规模网络数据集上。实验结果表明该方法相比基线模型可以有效提升模型节点分类准确率。

值得注意的是，这是首个成功将 Graph Transformer 应用到超大规模网络数据集 ogbn-papers100M 的模型。

3. POLYNORMER

POLYNORMER[9] 是康奈尔大学的团队提出的一种多项式表达能力的 Graph Transformer，该工作成功发表在 ICLR 2024 上。该方法将多项式网络的思想引入到 Graph Transformer 中，从而大大增强了模型的性能。

如图，是一个多项式网络的例子，通过一个点积运算，使得输出的表示不仅包含 这样的一阶项，还包含了 这样的二阶项。通过继续叠加多层这样的点积运算，可以实现更高阶的多项式。将该想法引入到 Graph Transformer 中，得到了如下的模型架构：

除了引入多项式网络外，Polynormer 还提出将常用的局部注意力与全局注意力直接组合的方式变为先计算局部注意力再计算全局注意力的方式，避免了直接组合局部和非局部信息可能带来的风险。实验结果表明该方法在同配图、异配图以及大图数据集上都取得了优越的性能表现。

4. Gradformer

Gradformer[10] 是武汉大学的团队提出的一种引入指数衰减掩码的 Graph Transformer，使其在实现全局感知捕获全局信息的同时更加关注局部结构信息，该工作发表于 IJCAI 2024。具体来说，该方法首先需要计算最短路径距离，然后学习得到一个随最短路径距离增长而指数衰减的掩码矩阵，再根据该掩码矩阵修改注意力矩阵。

实验结果表明该方法相比传统的全局注意力能够更好的结合图结构信息，并在下游任务上实现性能提升。

5. CoBFormer

CoBFormer[11] 是我们团队发表在 ICML 2024 上一篇对 Graph Transformer 进行分析的文章。我们发现了 Graph Transformer 中存在过全局化问题，即过多的注意力分数被分配给了距离较远的节点，而往往更加有用的相距较近的节点相对来说被忽视。

我们理论证明了过全局化问题会导致模型在节点分类任务上难以取得足够好的性能。基于此发现，我们提出一种两级全局注意力机制，并配合以协同训练方式学习图的局部结构信息。

我们首先对原图采用图划分算法划分出一系列子图（簇），然后在子图内部进行注意力计算，再对每个子图内的节点表征进行平均池化得到子图表征，从而计算子图之间的注意力。同时，我们用一个 GCN 来捕获图的局部信息，再采用协同训练方式，让 GCN 与注意力模块相互监督学习。我们理论证明了该方法可以有效近似全局注意力机制并实现更好的分类性能。大量实验也证明了我们方法的有效性。

总结

本文通过对最近一年内有关 Graph Transformer 的部分顶会论文进行了简要的解读，可以看出目前该领域内的主要研究问题主要集中于如下两个方面：

• 高效性：如何克服 Transformer 架构的高复杂性，从而有效应用到大规模网络上。
• 局部性：由于 Graph Transformer 的过全局化问题的存在，如何缓解该问题，促进其对局部信息的感知。

除此之外，还有很多方法致力于提出更具有表达能力的位置/结构编码[12, 13]，从而向 Graph Transformer 中注入更有效的结构信息，使其在 WL 图同构测试中取得更好地结果，从而有效区分图级别任务中同分异构体等难题。该方向也是现如今一大研究热点，值得更多的探讨。

参考文献

[1] Kipf, T. N., & Welling, M. Semi-supervised classification with graph convolutional networks. ICLR 2017.

[2] Li, Q., Han, Z., & Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. AAAI 2018.

[3] Alon, U., & Yahav, E. On the bottleneck of graph neural networks and its practical implications. ICLR 2021.

[4] Zhao, J., Li, C., Wen, Q., Wang, Y., Liu, Y., Sun, H., Xie, X., & Ye, Y. Gophormer: Ego-graph transformer for node classification. arXiv 2021.

[5] Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., & Liu, T.-Y. Do transformers really perform badly for graph representation? NeurIPS 2021.

[6] Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. Recipe for a general, powerful, scalable graph transformer. NeurIPS 2022.

[7] Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., & Sinop, A. K. Exphormer: Sparse transformers for graphs. ICML 2023.

[8] Wu, Q., Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., & Yan, J. Simplifying and empowering transformers for large-graph representations. NeurIPS 2024.

[9] Deng, C., Yue, Z., & Zhang, Z. Polynormer: Polynomial-expressive graph transformer in linear time. ICLR 2024.

[10] Liu, C., Yao, Z., Zhan, Y., Ma, X., Pan, S., & Hu, W. Gradformer: Graph transformer with exponential decay. IJCAI 2024.

[11] Xing, Y., Wang, X., Li, Y., Huang, H., & Shi, C. Less is more: On the over-globalizing problem in graph transformers. ICML 2024.

[12] Black, M., Wan, Z., Mishne, G., Nayyeri, A., & Wang, Y. Comparing graph transformers via positional encodings. ICML 2024.

[13] Cantürk, S., Liu, R., Lapointe-Gagné, O., Létourneau, V., Wolf, G., Beaini, D., & Rampásek, L. Graph positional and structural encoder. ICML 2024.