【源头活水】Graphormer：融合GNN与Transformer

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

来源：知乎—esang

地址：https://zhuanlan.zhihu.com/p/429876928

目前在各个领域，万物皆可Transformer的趋势越来越明显。介绍一篇成功的将Transformer应用于GNN模型中的工作：

https://arxiv.org/abs/2106.05234

代码：

https://github.com/microsoft/Graphormer

01

Structure Encodings

文章主要通过在self-attention模块计算attention score的过程中添加不同的，表征图结构信息的encoding来赋予Transformer编码图结构的能力。

Centrality Encoding

Centrality Encoding用于表征节点在图中的重要性，为每个节点添加两个embedding，一个出度，一个入度：

其中  是可训练的嵌入矩阵，分别编码出度与入度。

Spatial Encoding

Transformer的优势在于全局感受野（global receptive field），副作用在于必须在模型中显式地编码位置信息。

对于一个图    , 使用  来衡量节点    和    之间的空间关系，可以将其定义为两个节点之间的连通性（connectivity）。

具体地，如果节点    和    连通的话，我们可以将  定义为节点    和    之间最短路径的距离。如果不连通的话则赋给其一个特殊值-1。

这个输出的标量可以作为残差项加到对应的两个节点的attention score上：

 是  索引的可训练标量，并且全局共享。

优势：

1. 全局感受野

2. 通过  ，每个节点都能根据图的结构信息自适应关注不同的节点。比如，如果  是个减函数，那么每个节点会更多的关注离它近的节点的信息。

Edge Encoding

在很多图任务中，边也包含结构特征。常用的edge encoding方法有：

• 将边的特征附加到它所连接的点的特征上。
• 在aggregation中，将点特征和边特征一起计算。

（这里没有特别明白两种方法的区别，大概是第一种同时更新node encoding和edge encoding，第二种方法只更新node encoding?）

为了更有效地表征边的结构信息，文章在计算attention score时新加了一个残差项，通过如下方式计算：

首先找出从节点    和   的最短路径  , 然后将路径上的特征与一个可训练的embedding逐个做点积，之后计算残差项    ：

其中    是路径中第    条边的特征， 是第n个weight embedding

02

整体架构

仿照Bert设置一个特殊节点[VNode]连接图上的所有节点，[VNode]的节点特征可以作为全图的特征。【这个技巧对很多GNN模型都有提升，但有可能导致过平滑】

因为所有点到[VNode]的距离都是1，但这不是真实的物理距离。所以为了区分物理距离和虚拟距离，所有的  和  要单独训练。

03

How Powerful is Graphormer?

1. 通过选择合适的权重和距离函数    ，Graphormer可以表达如GIN、GCN、GraphSAGE等常见GNN模型的aggregate和combine过程。

2. 通过选择适当的权重，Graphormer 输出的每个节点表示无需额外编码即可表示 MEAN READOUT 函数

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！