Graphormer阅读笔记 —— Huixuan Chi (AML@ByteDance)

• paper：https://arxiv.org/abs/2106.05234
• code：https://github.com/microsoft/Graphormer （main分支）

Graphormer主要策略

1. Transformer结构

主要有Transformer layer组成，每一层包括MHA（多头自注意）和FFN（前馈）模块，并增加了LN。
$$\begin{gathered} h^{{}^{\prime }(l)}=\text{MHA}(\text{LN}(h^{(l-1)}))+h^{(l-1)} \\ {h}^{(l)}=\text{FFN}(\text{LN}(h^{{}^{\prime }(l)}))+h^{{}^{\prime }(l)} \end{gathered}$$
Graphormer主要是在MHA模块内进行了改动，Transformer原始的self-attention如下：
$$\begin{gathered} Q=H{W}_Q,K=H{W}_K,V=H{W}_V, \\ A=\frac{Q{K}^{\top }}{\sqrt{d_K}},attn(H)=softmax(A)V, \end{gathered}$$
原始的$H\in R^{n\times d}$​，最后算出来的$attn(H)\in R^{n\times d}$​​。

缺点，Transformer是全局视野，不能有效的使用图的结构信息。

2、图结构信息编码

2.1 degree centrality

在输入层中，将节点特征x和由入读和出度索引的可学习的embedding相加。
$$h_i^{(0)}=x_i+z_{{\text{deg}}^{-}(v_i)}^{-}+z_{{\text{deg}}^{+}(v_i)}^{+},$$

# init
self.in_degree_encoder = nn.Embedding(512, hidden_dim, padding_idx=0)
self.out_degree_encoder = nn.Embedding(512, hidden_dim, padding_idx=0)
# degree encoder
# in_degree, out_degree = batched_data.in_degree, batched_data.in_degree
node_feature = node_feature + self.in_degree_encoder(in_degree) + self.out_degree_encoder(out_degree)  

所有节点的度embedding是共享的，由度的数值进行索引。

2.2 spatial encoding

self-attention模块内，公式里面A可以视为节点相互之间的边权重（相似程度）。元素值$A_{ij}$代表节点i到节点j之间的边权重。
$$A_{ij}=\frac{(h_i{W}_Q)(h_j{W}_K{)}^T}{\sqrt{d}}+b_{\varphi (v_i,v_j)},$$
Spatial encoding是$b_{\varphi (v_i,v_j)}$，它作为bias加到原始值上面。$\varphi (v_i,v_j)$表示节点i到节点j之间的最短路径（SPD），$b_{\varphi (v_i,v_j)}$​有所有层共享，由SPD索引，输出一个可学习的标量。这样做的优点是可以自适应的和不同距离的节点进行消息传递。

多源最短路径使用Floyd算法求解，得到shortest_path矩阵。

2.3 edge encoding

对edge feature进行编码，
$$A_{ij}=\frac{(h_i{W}_Q)(h_j{W}_K{)}^T}{\sqrt{d}}+b_{\varphi (v_i,v_j)}+c_{ij},\text{where}{c}_{ij}=\frac{1}{N}\sum _{n=1}^N{x}_{e_n}(w_n^E{)}^T,$$
编码信息$c_{ij}$（标量）​的计算，取节点i到节点j的最短路径SPD上所有（edge feature $\odot$​ 可学习的embedding）的平均值，可学习的embedding由序号n来索引。

3. 图分类Tricks

3.1 Virtual Node (VN)

新增一个虚拟节点和所有节点相连，最终图表示的结果就是虚拟节点的嵌入表示。

3.2 FLAG

对抗性数据增强方法（Adversarial Train）。

实验

主要在化学分子图数据集中进行。

• PCQM4M-LSC
• OGBG-MolPCBA
• OGBG-MolHIV

---

Graphormer消融实验

1. OGB-LSC（PCQM4M-LSC）

200个epoch，OGB-LSC的test没有对外公布，只有valid数据。

Degree Encoding	Spatial Encoding	Edge Encoding	Valid MAE
----	✅	✅	0.1298
✅	----	✅	0.1279
✅	✅	----	0.1361
✅	✅	✅	0.1294
✅	Adj.	Adj.	0.1297
----	Adj.	Adj.	0.1307

SPD换成Adj.好像差的不是很大。去掉Spatial Encoding效果居然还要好一点？
官方给出的LSC上的简化版（为节省计算资源）Graphormer消融实验结果。

2. OGBG-Molhiv

• 在OGB-LSC上进行预训练，保存checkpoints （seed=1, ../../checkpoints/epoch=200-step=298886.ckpt）
  • 预训练模型包含3种encoder
  • 为节省时间和磁盘空间，每个run跑200个epoch，（实际应该跑300个），和原文结果有一些偏差
  • Tesla V100 * 8
• 在OGBG-Molhiv上进行fine-tuning （seed=1）
  • 对3种encoder进行消融实验
  • 5个epoch进行微调
  • Tesla V100 * 1

2.1. Version 1 （在LSC上正常预训练，实际上是不对的）

Degree Encoding	Spatial Encoding	Edge Encoding	Valid AUC (%)	Test AUC (%)
----	----	----	78.49	67.43
✅	----	----	72.39	63.40
----	✅	----	61.62	36.88
----	----	✅	78.11	77.31
----	✅	✅	76.56	75.53
✅	----	✅	76.49	78.35
✅	✅	----	46.01	30.12
✅	✅	✅	79.70	79.68
✅	Adj.	Adj.	79.78	77.14

一个有趣的现象，有Spatial Encoding、无Edge Encoding，效果要比什么都不加差。

用Adj替换SPD矩阵，test auc下降不是很多，但是减少了Floyd（$O(N^3)$）的计算量。从消融实验中可以发现，基于SPD的edge encoding与spatial encoding配合使用是比较有用的，单独使用degree encoding是比较有效的。edge encoding对于auc的提升影响是很大的。

2.2. Version 2 （预训练时就进行消融）

Degree Encoding	Spatial Encoding	Edge Encoding	Valid AUC (%)	Test AUC (%)
----	✅	✅
✅	----	✅	78.19	77.80
✅	✅	----	83.97	74.89
✅	✅	✅	79.70	79.68
✅	Adj.	Adj.
----	Adj.	Adj.

2.3. GCN/GIN + Degree Encoding

Model	Test ROC-AUC	Valid ROC-AUC
GCN+Vn+FLAG	76.83	81.76
GCN+VN+FLAG+DE	71.28	81.83
GIN+Vn+FLAG	77.48	84.38
GIN+VN+FLAG+DE	76.29	82.24

加上Degree Encoding (DE)，Test auc震荡的很厉害，并且表现也并不好。

2.4. Graphormer + FPs

• https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-molhiv

• 代码和具体做法：https://github.com/ytchx1999/Graphormer/tree/main/examples/ogb

  • 处理得到 MorganFingerprint 和 MACCSFingerprint ，拼接后得到feat

  • 使用Random Forest进行分类训练任务，保存训练结果

  • 作为平滑项，和Graphormer学到的graph_pred进行加权求和
    $$output=(1-\alpha )\cdot Sigmoid(output)+\alpha \cdot mgf\_maccs\_pred$$

Model	Test ROC-AUC	Valid ROC-AUC	Parameters	Hardware
Graphormer (without pre-train)	72.60	72.94	47085378	Tesla V100 (32GB)
Graphormer	80.51 ± 0.53	83.10 ± 0.89	47183040	Tesla V100 (16GB)
Graphormer + FPs	82.25 ± 0.01	83.96 ± 0.01	47085378	Tesla V100 (32GB)

OGB冲榜

test auc提升2%左右，榜三（但标准差更小），前三名差距比较小。

3. MLP+C&S复现和OGB冲榜

代码：https://github.com/ytchx1999/PyG-ogbn-products/tree/main/spectral%2Bmlp%2Bcs
论文：https://arxiv.org/abs/2010.13993
排行榜：https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-products