Graphormer 的理解、复现及应用——理解

Transformer 在NLP和CV领域取得颇多成就，近期突然杀入图神经网络竞赛，并在OGB Large-Scale Challenge竞赛中取得第一名的成绩。Graphormer作为实现算法实现的主要架构，已经在Do Transformers Really Perform Bad for Graph Representation?（https://arxiv.org/abs/2106.0523

代码的搬运工-

14671人浏览 · 2021-07-12 22:20:53

代码的搬运工- · 2021-07-12 22:20:53 发布

Transformer 在NLP和CV领域取得颇多成就，近期突然杀入图神经网络竞赛，并在OGB Large-Scale Challenge竞赛中取得第一名的成绩。

Graphormer 作为实现算法实现的主要架构，已经在Do Transformers Really Perform Bad for Graph Representation?（https://arxiv.org/abs/2106.05234）进行了详细的介绍。本博文主要是在讲解翻译一下该文章的基础上加入一些博主自己的理解，并对Graphormer的代码进行性进一步理解和复现。

1、论文翻译及理解

1.1 介绍

介绍部分主要讲了Transformer在处理图形数据上存在的问题。最后，作者对Transformer在图结构数据上是否有效发出疑问——因此，Transformer体系结构是否适合于对图进行建模，以及如何使其在图表示学习中发挥作用，仍然是一个悬而未决的问题。

在本文中，我们通过开发Graphormer给出了肯定的答案，Graphormer直接构建在标准Transformer上，并在广泛的图形级别预测任务上实现了最先进的性能，包括最近的Open Graph Benchmark LSC(OGB-LSC)[20]，以及几个流行的排行榜(例如，OGB[21]，Benchmark-GNN[14])。Transformer最初是为序列建模而设计的。关键是要正确地将图的结构信息融入到模型中。注意，对于每个节点i，自我关注只计算i与其他节点之间的语义相似度，而没有考虑反映在节点上的图的结构信息和节点对之间的关系。Graphormer结合了几种有效的结构化编码方法来利用这些信息，如下所述:

这里提出了Centrality Encoding，Graphormer 中的三个关键encoding之一，主要用于捕获节点的重要性。具体地说，作者利用度中心性进行Centrality Encoding，根据每个节点的度为每个节点分配一个可学习向量，并将其添加到输入层中的节点特征中。实证研究表明，简单的Centrality Encoding对Transformer的图形数据建模是有效的。

这里主要是提出了一种空间编码（Spatial Encoding），主要用于解决图结构数据的空间位置，在后面的公式中会详细介绍。

1.2、预备知识

这里简要介绍了图神经网络和Transformer的知识

这一部分的内容相对容易理解，图神经网络的本质主要是聚合和连接操作即文中的（AGGREGA TE 和 COMBINE），通过聚合邻居节点的特征和连接上一层的embedding表示得到本层的embedding表示，其中第0层的embedding表示是节点的特征。关于Transformer，主要分为两个部分，一个是自注意模块（self-attention module）和位置前馈网络（ position-wise feed-forward network）。这里定义了3个参数矩阵，如式3和式4所示。关于Transformer我也不是很了解，前两个星期看了一下相关文章，但是还未理解透彻。

1.3 Graphormer

这里是本文的关键实现部分，作者巧妙地设计了三种Graphormer编码，分别是Centrality Encoding，Spatial Encoding和Edge Encoding in the Attention。

首先，我们看一下Centrality Encoding

这里是在第0层的embedding表示 $h_i^{(0)}$ 等于原始节点的特征 $x_i$ 加上度矩阵z，这里我的理解是主要考虑了节点和其他节点的连接情况，作者这里将其定义为节点的中心性。

其次，我们来看空间编码，这里我认为是本篇文章最有意思的地方。

这里作者说了现有的神经网络仅仅考虑了节点的局部连接，并没有考虑节点的全局位置，以及节点与图中不是其邻居节点的关系，因此作者指出，应该增加相关方面的考虑。于是，作者将节点 $v_i$ 与节点 $v_j$ 的最小连接路径计算出来，得到 $\phi (v_i,v_j)$ ，如果两个节点没有连接，则另其为-1等，这样整个图的结构将嵌入到一个 $V\cdot V$ 的矩阵，这样就可以表示图中节点的空间关系，相对于邻接矩阵，得到的矩阵可以反映全局的连接关系。