专题解读 | Graph Transformer代表性工作介绍

本文介绍了一种名为Graphormer的基于Transformer架构的模型，专门用于图数据的表示学习。作者提出了结构信息编码方法，包括中心性编码和空间编码，以有效地捕捉图中的节点重要性和节点之间的结构关系。通过数学证明，论文表明Graphormer的表达能力强大，能够包含许多流行的GNN变体。实验结果表明，Graphormer在多个图级别预测任务上表现卓越，包括OGB-LSC，相对于传统GNN方法，性能显著提升。该研究为在图数据领域利用Transformer架构提供了新的可能性。

方法简介

为了有效地将图的结构信息融入到Transformer模型中，作者提出了几种结构编码方法。其中主要的编码包括：

• 中心性编码：捕捉节点的重要性。
• 空间编码：捕捉节点之间的结构关系。

中心性编码：

Graphormer使用使用度中心性，作为神经网络的附加信号。中心性编码根据每个节点的入度和出度分配两个实值嵌入向量。由于中心性编码应用于每个节点，我们可以简单地将其添加到节点特征作为输入。

其中是由入度和出度所指定的可学习向量。通过在输入中使用中心性编码，softmax 注意力可以捕捉到查询和键中的节点重要性信号。因此，模型可以在注意力机制中捕捉到语义相关性和节点重要性。

空间编码：

为了在模型中编码图的结构信息，本文提出了一种新的空间编码方法。具体来说，对于任何图，我们考虑一个函数该函数度量图中 和 之间的空间关系。函数 可以由图中节点之间的连接性定义。在本文中，将 定义为 和 之间最短路径的距离（SPD），如果这两个节点是连接的。如果不是连接的，我们将 的输出设置为一个特殊值，即 。我们为每个（可行的）输出值分配一个可学习的标量，它将用作自注意力模块中的偏置项。将 表示为查询-键乘积矩阵 的元素，我们有：

其中是一个由指定的可学习标量，在所有层间共享。

Structure-Aware Transformer for Graph Representation Learning

本文介绍了结构感知Transformer（SAT），这是一种新型的图Transformer，它明确地考虑图结构来捕获节点之间的结构交互。与传统的Transformer相比，SAT通过将结构信息纳入自注意力机制来解决在图表示学习中捕获节点间结构相似性的问题，实验结果显示，SAT在多个图预测基准测试上都表现出色，并且比其他方法更具可解释性。

方法简介

本文提出了一个将图结构编码到注意力机制中的模型。首先，通过Structure extractor抽取节点的子图结构，进行子图结构的注意力计算。其次，遵循Transformer的结构进行计算。

k-subtree GNN提取器

k-subtree GNN提取器通过应用现有的图神经网络（GNN）模型于输入图上，专门提取以特定节点u为中心的局部结构信息。这种提取器能够表示以u为根的k-subtree结构，即以节点u为中心，半径为k的子图。尽管它的计算速度快并且灵活，但其表达能力可能受到消息传递GNN的限制。

k-subgraph GNN提取器

k-subgraph GNN提取器不仅仅关注单一节点的表示，而是直接计算以特定节点u为中心的整个k-hop子图的表示。它首先计算k-hop子图中所有节点的表示，然后使用池化函数来聚合这些表示，从而得到节点u的综合表示。这种方法能够捕获更广泛的结构信息，但可能在计算上更为复杂，尤其是对于大型数据集。

GraphGPS: General Powerful Scalable Graph Transformers

本文提出了一种构建具有线性复杂度的通用、强大和可扩展的图形Transformer的方法。作者将不同类型的位置和结构编码分类为局部、全局或相对。他们将局部实边聚合与完全连接的Transformer解耦，以实现线性复杂度。所提议的架构支持多种类型的编码，并在16个基准测试上取得了有竞争力的结果。作者还提供了一个名为GRAPH GPS的模块化框架来实现这种架构。

方法简介

本文为了实现线性复杂度，采取了以下关键策略：

GPS层：MPNN+Transformer混合：

GPS层是一个混合的MPNN+Transformer层。在每一层，特征通过聚合MPNN层的输出与全局注意力层的输出来更新。边特征仅传递给MPNN层。这种结构允许在局部邻域上执行任何函数的MPNN，而GlobalAttn可以是任何完全连接的层。

线性Transformer的应用：

通过限制PE/SE（位置编码/结构编码）到实节点和边，并从全局注意力层中排除边特征，可以避免实现完整的二次注意力矩阵。因此，可以使用具有O(N)复杂度的线性Transformer，而MPNN的复杂度为O(E)。对于稀疏图（如分子图、规则图和知识图），边实际上与节点成比例，即E∼O(N)，这意味着整个复杂度可以被认为是线性的，与节点数O(N)成比例。