1 摘要

作者提出了一种适用于任何图的GraphTransformer。原始的transformer在基于单词的全连接图上用于NLP，它有如下缺点：

1. 这种结构不能很好利用图的连通归纳偏置（graph connectivity inductive bias）
2. 当图的拓扑结构很重要且尚未编码到节点特征时，表现很差

作者提出的GraphTransformer，有4个优势：

1. 注意力机制是图中每个节点的邻域连通性的函数
2. positional encoding用拉普拉斯特征向量表示
3. Batch Normalization代替Layer Normalization，优点：训练更快，泛化性能更好
4. 该架构扩展到边特征表示，这对于某些任务可能至关重要，例如化学（键类型）或链接预测（知识图谱中的实体关系）

2 贡献

1. 提出了一种将 transformer 网络推广到任意结构的同构图，即 Graph Transformer，以及具有边缘特征的 GraphTransformer 的扩展版本，允许使用显式域信息作为边缘特征。
2. 方法包括一种使用拉普拉斯特征向量为图数据集融合节点位置特征的优雅方法。与文献的比较表明，拉普拉斯特征向量比任何现有的方法都更适合编码任意同构图的节点位置信息
3. 实验表明，所提出的模型超过了baseline的各向同性和各向异性 GNN

Graph Transformer

On Graph Sparsity（图稀疏）

在NLP的transformer中，用全连接图去处理一个句的原因：

1. 很难在句子中的单词之间找到有意义的稀疏交互或联系。例如：句子中的单词对另一个单词的依赖性可能因上下文、用户视角而异
2. NLP的transformer的nodes数量比较少（几十个，几百个），便于计算。

对于实际的图形数据集，图形可能有任意的连接结构，nodes的数量高达数百万或数十亿，使得不可能为此类数据集提供完全连接的图形，因此需要Graph Transformer来让nodes处理邻居信息。

On Positional Encodings（位置编码）

在 NLP 中，基于 transformer 的模型为每个单词提供位置编码。确保每个单词的唯一表示并确保最终保留距离信息

对于图形，唯一节点位置的设计具有挑战性，因此大多数在图数据集上训练的 GNN 学习的是不随节点位置变化的结构化节点信息，这就是为什么GAT是局部attention，而不是全局attention。

现在的目标是学习结构和位置的特征，Dwivedi et al. (2020)利用现有的图结构预先计算拉普拉斯特征向量，并将它们作为节点的位置信息。

• 拉普拉斯 PE 能更好地帮助编码距离感知信息（即，附近的节点具有相似的位置特征，而较远的节点具有不同的位置特征）

因此使用拉普拉斯特征向量作为 Graph Transformer 中的 PE。特征向量通过图拉普拉斯矩阵的分解来定义：
$$\Delta =\mathrm{I}-D^{-1/2}A{D}^{-1/2}=U^T\Lambda U,(1)$$

• $A$是$n\times n$邻接矩阵，$D$是度矩阵
• $\Lambda$和$U$分别对应特征值和特征向量
• 使用节点的 k个最小的非平凡特征向量作为其位置编码，对于节点$i$，用${\lambda }_i$表示

3 Graph Transformer Architecture（架构）

模型框架

input（输入）

首先准备要输入Graph Transformer Layer的input node 和 edge embeddings。

在图$\mathcal{G}$中，对于任意一个节点$i$的节点特征${\alpha }_i\in {\mathbb{R}}^{d_n\times 1}$以及节点$i$和节点$j$之间的边特征${\beta }_{ij}\in {\mathbb{R}}^{d_e\times 1}$，${\alpha }_i$和${\beta }_{ij}$通过一个线性映射，从而嵌入到$d$维的隐藏特征（hidden features）$h_i^0$和$e_{ij}^0$中，公式如下：
$${\hat{h}}_i^0=A^0{\alpha }_i+a^0;e_{ij}^0=B^0{\beta }_{ij}+b^0,(2)$$

• 其中$A^0\in {\mathbb{R}}^{d\times d_n},B^0\in {\mathbb{R}}^{d\times d_e}$，以$A^0$为例，其每一列是每个节点的节点特征（总共$d_n$个结点），维度为$d$，而${\alpha }_i$一个其他元素都为0，对应节点位置的元素为1的向量

• $a^0,b^0\in {\mathbb{R}}^d$是线性映射层的参数

然后通过线性映射嵌入维度为$k$的预计算节点位置编码并将其添加到节点特征${\hat{h}}_i^0$中。
$${\lambda }_i^0=C^0{\lambda }_i+c^0;h_i^0={\hat{h}}_i^0+{\lambda }_i^0,(3)$$

• 其中$C^0\in {\mathbb{R}}^{d\times k}，c^0\in {\mathbb{R}}^d$，其作用是将位置编码转化为维度为$d$的向量

Graph Transformer Layer

现在定义第$l$层的节点更新方程：
$${\hat{h}}_i^{\ell +1}=O_h^{\ell }{\left|\right|}_{k=1}^H\left(\sum _{j\in {\mathcal{N}}_i}{w}_{ij}^{k,\ell }{V}^{k,\ell }{h}_j^{\ell }\right),(4)$$
$$\mathrm{where},w_{ij}^{k,\ell }={\mathrm{softmax}}_j\left(\frac{Q^{k,\ell }{h}_i^{\ell }\cdot K^{k,\ell }{h}_j^{\ell }}{\sqrt{d_k}}\right),(5)$$

• $Q^{k,\ell },K^{k,\ell },V^{k,\ell }\in {\mathbb{R}}^{d_k\times d},O_h^{\ell }\in {\mathbb{R}}^{d\times d}$
• $k=1$到$H$代表注意头的数量
• $\left|\right|$表示串联（concatenation）

这里详细讲一下式子（5），$Q^{k,\ell }{h}_i^{\ell }$相当于$h_i^{\ell }$的查询向量，$K^{k,\ell }{h}_j^{\ell }$是$h_j^{\ell }$的键向量（相当于查询的答案）

• 比如，查询向量在问：“我前面有形容词吗”，键向量回答：“有的”。假设二者向量点积值越大，则说明了它们越匹配，则说明越相关
• 除以$\sqrt{d_k}$是为了数据的稳定性

接着将结果${\hat{h}}_i^{\ell +1}$按照框架图所示依次经过残差连接和LN、Feed Forward Network (FFN)、残差连接和LN，公式如下：
$$\begin{gathered} {\hat{\hat{h}}}_i^{\ell +1}=\text{Norm}(h_i^{\ell }+{\hat{h}}_i^{\ell +1}),(6) \\ \begin{array}{lclc}{\widehat{\hat{\hat{h}}}}^{\ell +1}& =& W_2^{\ell }\text{ReLU}(W_1^{\ell }{\hat{\hat{h}}}_i^{\ell +1}),& (7)\end{array} \\ \begin{array}{rclc}{h}_i^{\ell +1}& =& \text{Norm}({\hat{\hat{h}}}_i^{\ell +1}+{\widehat{\hat{\hat{h}}}}_i^{\ell +1}),& (8)\end{array} \end{gathered}$$

• $W_1^{\ell },\in {\mathbb{R}}^{2d\times d},W_2^{\ell },\in {\mathbb{R}}^{d\times 2d},{\hat{\hat{h}}}_i^{\ell +1},{\widehat{\hat{\hat{h}}}}_i^{\ell +1}$ 都是中间变量
• Norm可以是LayerNorm或者BatchNorm

Graph Transformer Layer with edge features（带边特征）

接下来介绍的是上图第二个模型，根据公式（5），将此分数视为边<i,j>的隐式信息，紧接着使用公式（12）为边<i,j>注入可用的边信息，如下：
$$\begin{array}{rlrlrl}& {\hat{h}}_i^{\ell +1}& & =O_h^{\ell }{\left|\right|}_{k=1}^H\left(\sum _{j\in {\mathcal{N}}_i}{w}_{ij}^{k,\ell }{V}^{k,\ell }{h}_j^{\ell }\right),& & \text{(9)}\\ & {\hat{e}}_{ij}^{\ell +1}& & =O_e^{\ell }{\left|\right|}_{k=1}^H\left({\hat{w}}_{ij}^{k,\ell }\right),\mathrm{where},& & \text{(10)}\\ & w_{ij}^{k,\ell }& & ={\mathrm{softmax}}_j({\hat{w}}_{ij}^{k,\ell }),& & \text{(11)}\\ & {\hat{w}}_{ij}^{k,\ell }& & =\left(\frac{Q^{k,\ell }{h}_i^{\ell }\cdot K^{k,\ell }{h}_j^{\ell }}{\sqrt{d_k}}\right)\cdot E^{k,\ell }{e}_{ij}^{\ell },& & \text{(12)}\end{array}$$

• $Q^{k,\ell },K^{k,\ell },V^{k,\ell },E^{k,\ell }\in {\mathbb{R}}^{d_k\times d},O_h^{\ell },O_e^{\ell }\in {\mathbb{R}}^{d\times d}$
• 这里的公式，矩阵运算过程中总感觉维度不对应，后期再看这个问题

紧接着，经历相同的过程，如下：
对于节点：
$$\begin{array}{rlrlrlrl}& {\hat{\hat{h}}}_i^{\ell +1}& & =\mathrm{Norm}(h_i^{\ell }+{\hat{h}}_i^{\ell +1}),& & & & \text{(13)}\\ & {\widehat{\hat{\hat{h}}}}_i^{\ell +1}& & =W_{h,2}^{\ell }\mathrm{ReLU}(W_{h,1}^{\ell }{\hat{\hat{h}}}_i^{\ell +1}),& & & & \text{(14)}\\ & h_i^{\ell +1}& & =\mathrm{Norm}({\hat{\hat{h}}}_i^{\ell +1}+{\widehat{\hat{\hat{h}}}}_i^{\ell +1}),& & & & \text{(15)}\end{array}$$

• $W_{h,1}^{\ell },\in {\mathbb{R}}^{2d\times d},W_{h,2}^{\ell },\in {\mathbb{R}}^{d\times 2d}$

对于边：
$$\begin{gathered} {\hat{\hat{e}}}_{ij}^{\ell +1}=\mathrm{Norm}(e_{ij}^{\ell }+{\hat{e}}_{ij}^{\ell +1}),(16) \\ {\widehat{\hat{\hat{e}}}}_{ij}^{\ell +1}=W_{e,2}^{\ell }\mathrm{ReLU}(W_{e,1}^{\ell }{\hat{\hat{e}}}_{ij}^{\ell +1}),(17) \\ {e}_{ij}^{\ell +1}=\mathrm{Norm}({\hat{\hat{e}}}_{ij}^{\ell +1}+{\widehat{\hat{\hat{e}}}}_{ij}^{\ell +1}),(18) \end{gathered}$$

• $W_{e,1}^{\ell },\in {\mathbb{R}}^{2d\times d},W_{e,2}^{\ell },\in {\mathbb{R}}^{d\times 2d}$

基于任务的 MLP 层

在 Graph Transformer 最后一层获得的节点表示被传递到基于任务的 MLP 网络，用于计算与任务相关的输出，然后将其馈送到损失函数以训练模型的参数

4 实验

为了评估提出的模型的性能，在ZINC，PATTERN,CLUSTER这三个数据集实验。

• ZINC, Graph Regression：分子数据集，node代表分子，edge代表分子之间的键。键之间有丰富的特征信息，所以用第二个模型。
• PATTERN,Node Classification：任务是把nodes分成两个communities，没有明确的edge信息，所以用第一个模型。
• CLUSTER, Node Classification：任务是为每个node分配cluster，一共有6个cluster，用第一个模型。

模型的配置：使用PyTorch，DGL。一共有10层Graph Transformer layers，每层有8个attention head和随机隐藏单元，学习率递减策略，当学习率达到$10^{-6}$就停止训练。使用 4 种不同的种子进行每个实验，并报告 4 次运行的平均值和平均性能测量值。
表1如下：

• GraphTransformer (GT) 在所有数据集上的结果。 ZINC 的性能测量是 MAE，PATTERN 和 CLUSTER的性能测量是 Acc。 结果（除了 ZINC 之外，所有结果都越高越好）是使用 4 种不同种子进行 4 次运行的平均值。
• 粗体：每个数据集表现最佳的模型。
• 使用给定的图（稀疏图）和（完整图）执行每个实验，其中完整图在所有节点之间创建完全连接；对于 ZINC 全图，边特征被丢弃。
  
  表2如下所示：
  每个数据集上的最佳表现分数（来自表 1)与 GNN baselines的比较
  
  实验结论如下：
• 由表1可知，带有PE和BN的模型实验数据更好。
• 由表2可知，提出的模型明显比GCN和GTN要好，但没有GatedGCN好。
• 提出的第二个模型的性能在ZINC上近似于GatedGCN。