Graph+Transformer前沿进展研究！

图作为具有高度表达能力的数据结构，广泛用于表示各个领域的复杂数据，例如社交媒体、知识图谱、生物学、化学和交通网络[1]。它们从数据中捕捉结构和语义信息，促进了推荐系统[2]、问答系统[3]、异常检测[4]、情感分析[5]、文本生成[6]和信息检索[7]等任务的发展。为了有效处理图结构数据，研究人员开发了各种图学习模型，例如图神经网络（GNN），这些模型可以学习节点、边和图的有意义表示[8]。特别是，遵循消息传递框架的GNN通过迭代地聚合邻居信息并更新节点表示，在各种基于图的任务中表现出色[9]。从信息提取到推荐系统等应用都受益于GNN对知识图谱的建模[10]。

最近，作为新兴且强大的图学习方法，图Transformer在学术界和工业界都引起了极大的关注[11],[12]。图Transformer的研究受到了Transformer在自然语言处理（NLP）[13]和计算机视觉（CV）[14]中成功应用的启发，并结合了GNN的价值。图Transformer结合了图归纳偏差（例如，对图属性的先验知识或假设）来有效处理图数据[15]。此外，它们可以适应动态和异构图，利用节点和边的特征和属性[16]。图Transformer的各种改编和扩展在解决图学习的各种挑战（如大规模图处理）方面表现出优越性[17]。此外，图Transformer已成功应用于各个领域和应用，展示了其有效性和多功能性。

现有的综述未能充分涵盖图Transformer的最新进展和全面应用。此外，大多数综述未能提供系统的图Transformer模型分类。例如，Chen等人[18]主要关注GNN和图Transformer在CV中的应用，但未能总结图Transformer模型的分类法并忽略了其他领域（如NLP）。同样，Muller等人[12]概述了图Transformer及其理论属性，但未提供现有方法的全面综述或评估其在各种任务上的表现。最后，Min等人[19]集中于图Transformer的架构设计方面，系统评估了不同组件在不同图基准测试中的表现，但未包括图Transformer的重要应用或讨论该领域的开放问题。

为了填补这些空白，本综述旨在从设计和应用视角全面系统地回顾图Transformer研究的最新进展和挑战。与现有综述相比，我们的主要贡献如下：

1. 我们全面回顾了图Transformer的设计视角，包括图归纳偏差和图注意力机制。我们将这些技术分类并讨论其优缺点。

2. 我们提出了一种基于深度、可扩展性和预训练策略的图Transformer新分类法，并提供了选择不同任务和场景中有效图Transformer架构的指南。

3. 我们回顾了图Transformer在各种图学习任务中的应用视角，以及在其他领域（如NLP和CV任务）中的应用场景。

4. 我们确定了图Transformer研究中的关键开放问题和未来方向，如模型的可扩展性、泛化性、可解释性、高效的时间图学习和数据相关问题。

本文的概述如图1所示。后续综述的结构如下：第二节介绍与图和Transformer相关的符号和预备知识。第三节深入探讨包含图归纳偏差和图注意力机制的图Transformer的设计视角。第四节提出图Transformer的分类法，基于其深度、可扩展性和预训练策略进行分类。此外，还提供了选择适当图Transformer模型以应对不同任务和领域的指南。第五节探讨图Transformer在各种节点级、边级和图级任务中的应用视角，以及其他应用场景。第六节确定了图Transformer研究的开放问题和未来方向。最后，第七节总结本文并强调其主要贡献。

图Transformer分类法 

近年来，图Transformer引起了极大的兴趣。本节深入探讨当前文献中的四个主要类别：浅层图Transformer、深层图Transformer、可扩展图Transformer和预训练图Transformer。通过分析每个类别中的代表性模型，我们旨在为设计高效的图Transformer提供有价值的指导。

A. 浅层图Transformer 

浅层图Transformer代表了一类利用自注意力机制从图结构数据中获取节点表示的GNN。这些模型受到了Transformer在顺序数据中通过自注意力有效捕捉长程依赖关系的启发，将这一概念扩展到图数据中，通过基于节点特征和图拓扑计算自注意力权重[94]。浅层图Transformer的主要目标是在尽量减少计算复杂度和内存使用的同时，达到卓越的性能。

浅层图Transformer可以看作是图注意力网络（GAT）的广义版本[42]。GAT使用多头注意力机制来计算节点嵌入。然而，GAT存在一些局限性，如无法建模边特征以及注意力头之间缺乏多样性[95]。文献中提出了几种GAT扩展以解决这些问题。例如，Yun等人[36]提出的GTN引入了边缘自注意力机制，将边信息纳入节点嵌入。Ahmad等人[63]提出的图注意力Transformer编码器（GATE）应用了掩码自注意力机制，为不同节点学习不同的注意模式。GATE还使用了位置前馈网络和dropout来增强模型容量和泛化能力。浅层图Transformer方法的总结见表II。

浅层图Transformer高效且适应性强，能够处理各种图学习任务和不同类型的图，但其深度和递归的缺乏可能限制其捕捉复杂依赖关系的能力。其性能还可能受到掩码矩阵选择和注意力头数量的影响，这表明需要进一步研究其优化设计和正则化。

B. 深层图Transformer 

深层图Transformer由多个堆叠在一起的自注意力层组成，层之间可以有可选的跳跃连接、残差连接或密集连接[102]。它们旨在通过增加模型深度和复杂性来达到更高的性能[103]。深层图Transformer通过层次化地将自注意力层应用于节点特征和图拓扑，扩展了浅层图Transformer。

然而，深层图Transformer也面临需要解决的几个挑战。一个挑战是训练更深模型的难度，可以通过使用DeeperGCN中引入的PairNorm等技术来缓解[104]。另一个挑战是过度平滑问题，可以通过使用门控残差连接和广义卷积算子（如DeeperGCN中提出的）来解决。此外，全局注意力能力的消失和注意力头之间缺乏多样性也是需要解决的问题，可以通过像DeepGraph[94]这样的方法来解决。DeepGraph引入了子结构token和局部注意力，以改进全局注意力的焦点和多样性。

深层图Transformer虽然复杂，但能够在各种图学习任务中取得顶级成绩，并适应不同类型的图和领域。然而，其高计算成本、优化难度和对超参数的敏感性需要进一步研究以优化设计和训练。深层图Transformer方法的总结见表III。

C. 可扩展图Transformer 

可扩展图Transformer是一类在将自注意力应用于大规模图时应对可扩展性和效率挑战的图Transformer[39],[53],[114],[115]。这些Transformer专门设计用来在保持或提高性能的同时减少计算成本和内存使用。为实现这一目标，采用了各种技术来降低自注意力的复杂性，例如稀疏注意力、局部注意力和低秩近似[12],[115]。可扩展图Transformer可以看作是深层图Transformer的增强版，解决了如过度平滑和全局注意力能力有限等挑战。

提出了几种可扩展图Transformer模型，以提高图Transformer的可扩展性和效率。例如，Rampašek等人[39]引入的GPS使用低秩矩阵近似来降低计算复杂性，并在各种基准测试中取得了最先进的结果。GPS将局部真实边聚合与全连接Transformer分离，并结合不同的位置信息和结构编码来捕捉图拓扑。它还提供了一个模块化框架，支持多种编码类型和局部与全局注意力机制。Cong等人[116]开发的DyFormer是一种动态图Transformer，利用子结构token和局部注意力来增强全局注意力的焦点和多样性。DyFormer采用时间联合图结构和基于子图的节点采样策略，实现高效和可扩展的训练。

可扩展图Transformer是一类创新且高效的图Transformer，能够在处理大规模图时表现出色，同时尽量减少计算成本和内存使用。然而，可扩展图Transformer也面临一些局限性，包括可扩展性和表达能力之间的权衡、选择最佳超参数和编码的挑战以及缺乏关于其收敛性和稳定性的理论分析。因此，需要进一步研究以探索各种应用中可扩展图Transformer的最佳设计和评估。可扩展图Transformer方法的综合概述见表IV。

D. 预训练图Transformer 

预训练图Transformer利用大规模无标签图来获取可转移的节点嵌入[135]。这些嵌入可以通过微调用于下游任务，以解决图学习任务中的数据稀缺和领域适应挑战[136],[137]。这些Transformer类似于预训练的大型语言模型（LLM），使用自监督学习目标在图数据集上进行训练，例如掩码节点预测[138]、边重建[139]和图对比学习[140]。这些目标旨在独立于外部标签或监督捕捉图数据的固有属性[141]。通过结合特定任务层或损失函数并在标签数据上进行优化，预训练模型可以在特定下游任务上进行微调。这样，预训练模型能够将从大规模图数据集中获得的知识转移到后续任务，从而获得比从头训练更好的性能[142]。

预训练图Transformer面临一些挑战，如选择合适的预训练任务、领域知识的结合、异构信息的整合和预训练质量的评估[143]。为解决这些问题，提出了KPGT[144]和KGTransformer[145]。KPGT利用额外的领域知识进行预训练，而KGTransformer作为统一的知识表示和融合（KRF）模块应用于各种任务中。尽管预训练图Transformer功能强大且灵活，但它们也面临图数据异质性和稀疏性、领域适应、模型泛化和性能解释等问题。预训练图Transformer方法的总结见表V。

E. 高效图Transformer的设计指南 

开发高效的图Transformer需要仔细注意细节和周全的考虑。本指南提供了为各种场景和任务设计图Transformer的一般原则和提示。

• 根据图数据和任务的性质和复杂性选择合适的图Transformer类型。对于简单和小规模的图数据，浅层图Transformer几层可能就足够了。对于复杂和大规模的图数据，深层图Transformer具有更多层次可以学习更具表现力的表示。对于动态或流式图数据，可扩展图Transformer更高效。预训练图Transformer更适合稀疏或噪声图数据。

• 为图数据设计合适的结构和位置编码。这些编码捕捉图的结构，并在将输入节点或边特征输入Transformer层之前添加。编码的选择取决于图数据的特征，如方向性、权重和同质性。精心设计这些编码可以确保它们的信息性。

• 优化自注意力机制以适应图数据。自注意力机制在图中的所有节点或边对之间计算注意力分数，捕捉长程依赖关系和交互。然而，这引入了计算复杂性、内存消耗、过拟合、过度平滑和压缩等挑战。可以采用采样、稀疏化、分区、哈希、掩码、正则化和归一化等技术来解决这些挑战，并提高自注意力机制的质量和效率。

• 利用预训练技术增强图Transformer的性能。预训练技术利用其他领域或任务的预训练模型或数据，将知识或参数转移到特定的图学习任务。可以使用微调、蒸馏和适应等方法来调整预训练模型或数据。利用预训练技术特别有益于拥有大量预训练数据或资源时。

结论 

图Transformer是一类新颖且强大的神经网络模型，能够有效地编码和处理图结构数据。本综述从设计视角、分类法、应用和开放问题等方面提供了图Transformer的全面概述。我们首先讨论了图Transformer如何结合图归纳偏差，包括节点位置编码、边结构编码、消息传递偏差和注意力偏差，以编码图的结构信息。然后，我们介绍了图注意力机制的设计，包括全局和局部注意力机制。接着，我们提出了图Transformer的分类法。本综述还包括有效图Transformer的设计指南，提供了选择适当组件和超参数的最佳实践和建议。此外，我们基于各种图相关任务（如节点级、边级和图级任务）以及其他领域的任务，回顾了图Transformer的应用场景。最后，我们确定了图Transformer的当前挑战和未来方向。本综述旨在为对图Transformer及其应用感兴趣的研究人员和实践者提供有价值的参考。

链接：https://arxiv.org/pdf/2407.09777