Task
利用transformer进行图预测，即给出一个图，预测出其类别，其中图由
来表示，
代表结点，
代表边。在阅读这篇论文之前，回顾一下经典的GNN和Transformer。
GNN
一般的图神经网络通常通过聚合邻接结点的特征更新结点表达，称为AGGREGATE-COMBINE。公式如下所示：
?其中，l代表的是图卷积的层数，h代表的是结点在每一层的特征。一般聚合操作包括mean, max, sum。
Transformer
?Transformer通过计算节点相似度对节点表示进行更新。 通常Transformer中每一层由self-attention与feed-forward （全连接）子层组成。公式如下所示：
?Transformer已经有非常多的工作，不做更多的细节介绍。
问题
?目前,Transformer在图表示学习这一个领域中，并没有取得很好的效果。这篇论文的作者认为，因为在学习的时候，并没有考虑一个图中结点与边的结构信息，只考虑了利用自注意力机制计算的彼此间的相似度。
解决办法
此文提出一个使用标准Transformer架构的模型Graphormer，Graphormer相比Tranformer使用了更多的图结构信息来增强模型的图表达能力。最核心的点是作者设计了一种基于GNN的注意力机制，而之前的工作并没有做这一个点。之前的工作只是用一些步骤替代掉GNN中的某一个部分。
方法
论文的主题框架和基本的transformer还是一致的，在self-attention机制上加入了一些新曾的图的信息，来丰富特征，整体的框架如下图所示：
作者新增加的部分为centrality encoding, edge encoding, spatial encoding。
?Centrality encoding
在一个图中，结点的中心性极大程度的代表了一个结点在图中的重要性，在图学习中十分重要。之前的很多工作中，都说明了度作为特征是十分重要的，因此作者在论文中，计算了每一个结点的入度和出度，然后通过embedding将它们上升到与结点相同的维度，然后再进行相加。这样就得到了新的特征，公式如下所示：
?Spatial?encoding
网格结构是无法表达非欧空间，所以使用了两个结点的最短路径距离来表示，将其作为bias加入到attention当中。因为两个结点之间的attn值与两个直接之间是否相邻或者经过几个节点相邻有很大的关系。因此，作者使用了弗洛伊德算法求出了最短路径。
?
??代表的是两个结点的最短路径，b代表经过nn.embedding的操作，变成一个可学习的张量。
Edge Encoding in the Attention
在图表示学习的任务中，很有可能需要用到一些边的结构特征，在文中提到了两种当前比较常用的方法，首先，将边特征上升的与节点特征维度一致，然后与节点特征相加作为该节点发送至中心节点的消息，第二种，是使用边特征来控制不同节点对于中心节点的权重。为了更好的使用边的特征，作者设计了一种编码方式，首先计算任意两个结点的最短路径，然后按照边的特征，进行加权求平均，得到一个新的偏置的值，再加到之前的相似度矩阵的计算之后，公式如下所示：
Special Node
效仿Bert的思想，增加一个特殊的结点，来学习到全局的特征。
参考文献
[1] Chengxuan Ying,?Tianle Cai,?Shengjie Luo,?Shuxin Zheng,?Guolin Ke,?Di He,?Yanming Shen,?Tie-Yan Liu: Do?Transformers?Really?Perform?Bad?for?Graph?Representation??CoRR?abs/2106.05234?(2021)
[2]?Chea Sim - 知乎