论文简介
论文提出：当前图神经网络（GNN）的主要方法过度依赖图中的连接关系，这样造成了三大问题：（1）模型假死；（2）过度平滑；（3）难以并行计算
- 模型假死：随着神经网络层数的不断加深，模型对于输入的数据开始不进行相应。这个问题的具体原因没在论文里看到，个人理解是由于层之间的非线性变换使得数据分布变换置导数较小的区域，从而使得梯度消失。
- 过度平滑：由于图神经网络大多依靠聚合操作（mean，max，sum）的信息更新方式，这样随着层的不断堆叠，每个节点都会大量受到其他节点信息的影响，从而使得每个节点的embedding愈发趋同。这也是GNN一般不超过2层的原因。
- 难以并行计算：由于内存的限制，尤其是在大型图里面，图中的关联关系难以并行计算。
根据以上问题，论文提出了Graph-Bert，仅仅使用Attention机制完成GNN，而不需要使用任何卷积或者聚合操作。
在该方案中，不会把整个完整的大图输入给模型。而是先采样得到大图的一些无边子图，即只抽取子节点，而不考虑这些节点之间的边关系。这样便解决了传统GNN不能并行计算的问题。另外，传统GNN由于图的结构多样性，不能进行跨任务的预训练工作，但Graph-Bert不考虑边之间的联系，因此并不受限于图结构，可以很好地进行预训练和迁移学习。
模型结构
Graph-Bert模型主要分为五个步骤：
- 从子图中采样获得无边子图
- 子图节点特征的嵌入表示（embedding）
- 基于图transformer的节点表征学习编码器，编码器的输出作为学习到的节点特征表示。
- 基于图transformer的解码器
- 下游功能模块，该模块取决于模型所解决的任务
模型实现详解
1.无边子图采样
子图的采样基于图亲密度矩阵S∈R∣ν∣?∣ν∣S\in\R^{|\nu|*|\nu|}S∈R∣ν∣?∣ν∣的采样方案：「top-k intimacy」,其中S(i,j)S(i,j)S(i,j)代表节点viv_ivi?和vjv_jvj?之间的亲密度，计算公式为：
其中：
A?=AD?1\overline{A} = AD^{-1}A=AD?1是列规范化邻接矩阵,AAA为图的邻接矩阵( A?(i,j)\overline{A}(i,j)A(i,j)代表A(i,j)/A(i,j)/A(i,j)/节点viv_ivi?的出度，即i,ji,ji,j的亲密值/iii的总亲密值)
α\alphaα是一个[0, 1]之间的超参数（通常取0.15
DDD为对应的对角矩阵，D(i,j)=∑jS(i,j)D(i,j) = \sum_jS(i,j)D(i,j)=∑j?S(i,j)
那么对于一个给定的目标结点，就可以利用上面定义的亲密度矩阵来找出其相关节点（上下文结点），计算公式为：
Γ(vi)={vj∣vj∈ν、{vi}∧S(i,j)≥θi}\Gamma(v_i) = \{v_j|v_j\in\nu、\{v_i\}\land S(i,j)\ge \theta_i\}Γ(vi?)={
vj?∣vj?∈ν、{
vi?}∧S(i,j)≥θi?}
其实这一步就是把图结构的数据转变成了我们平时常见的NLP序列化输入，把每个结点看成是一个个字或词，然后后面就可以直接套transformer了。
2.节点Embedding
由于经过采样出来的结点们是无序的，这里按照与target node的亲密度打分来对结点集合进行排序。结点emdedding由四部分组成：
2.1. 原始特征embedding
使用一个映射操作将原始特征表示到新的共享的特征空间，对于不同的输入可以有不同的映射函数：
其中函数Embed(?)Embed(·)Embed(?)可以使CNN/RNN/LSTM
2.2. Weisfeiler-Lehman 绝对角色embedding
Weisfeiler-Lehman算法是用来确定两个图是否是同构的，其基本思路是通过迭代式地聚合邻居节点的信息来判断当前中心节点的独立性(Identity)，从而更新整张图的编码表示。
2.3. 基于亲密度的相对位置embedding
上一节计算的嵌入可以表示全局的信息，而这一步主要是获取局部信息:
2.4. 基于相对距离embedding
对两个结点在原始大图中的距离（间隔边的数量）进行embedding表示，主要是为了平衡上述两步的embedding:
3.Transfomer编码器
3.1 输入
对2中得到的四个embeeding进行聚合：
聚合的方法跟传统GNN一样，可以有很多选择，论文使用了简单的加和，聚合完成后就得到了所有节点的输入表示：
3.2 更新
然后就是进行N层的transformer encoder的迭代更新
3.3 输出
经过D层的编码之后，我们就可以得到对应每个结点的表示：
之后就可以根据具体的下游任务来使用这些向量表示。
4.GRAPH-BERT Learning
图神经网络的预训练大致分为两部分：对结点的预训练以及对链接关系的预训练。
4.1结点预训练
对于目标结点 $v_i $，原始特征为 $x_i $，我们通过GRAPH-BERT编码层可以得到其隐藏表示 $z_i ，然后经过一层FC映射后基于， 然后经过一层FC映射后基于，然后经过一层FC映射后基于xi^=FC(zi)\hat{x_i} = FC(z_i)xi?^?=FC(zi?) 重建原始特征。重建损失如下：
4.2 链接关系预训练
这一部分其实是考虑了图的结构信息，利用两个节点表示的cos距离与之前提前算好的亲密度打分，来做损失：
