一文带你浏览Graph Transformers

©作者 | Dream 单位 | 浙江大学 研究方向 | 图表示学习

写在前头

为什么图上要使用 Transformer？

简要提一下 GT 带来的好处：

1. 能捕获长距离依赖

2. 减轻出现过平滑，过挤压现象

3. GT 中甚至可以结合进 GNN 以及频域信息（Laplacian PE），模型会有更强的表现力。

4. 利用好 [CLS] token，不需要额外使用 pooling function。

5. etc

Graph-Bert

Graph-Bert: Only Attention is Needed for Learning Graph Representations (arXiv 2020)

https://arxiv.org/abs/2001.05140

GNN 过度依赖图上的链接，此外由于大图非常耗显存，可能无法直接进行操作。该论文提出了一种新的只依赖 attention 机制的图网络 Graph-BERT，Graph-BERT 的输入不是全图，而是一堆采样得到的子图（不带边）。作者使用节点属性重构以及结构恢复两个任务进行预训练，然后在下游数据集上进行微调。该方法在节点分类和图聚类任务上达到了 SOTA。

▲ 图1：Graph-BERT

和之前 NLP 中的 BERT 不一杨的地方主要是 position encoding，Graph-BERT使用了三种 PE，分别是 WL absolute PE，intimacy based relative PE 和 Hop based relative PE，这里三个 PE 都是根据 complete graph 计算得到的。

为了便于操作，作者将 subgraph 根据图亲密度矩阵进行排序 [i, j, ...m]，其中 S(i,j) > S(i,m)，得到序列化的结果。

其中 Weisfeiler-Lehman Absolute Role Embedding 如下：

经过 WL 之后，子结构一样的节点就会得到相同的 hash code，如果是 1-WL 有点像 degree centrality（针对无向图而言）。因此，WL PE 可以捕获全局节点角色信息。

Intimacy based Relative Positional Embedding

这个 PE 捕获的是偏 local 的信息，因为输入已经根据图亲密度矩阵进行排序过了，这里只需要简单地设 ，越接近i的节点 会越小。映射公式如下：

Hop based Relative Distance Embedding

该 PE 捕获的是介于 global 和 local 之间的信息：

将节点 embedding 和这些 PE 加起来，然后输入到 Transformer 中得到 subgraph 每个节点的表征 。因为 subgraph 中有很多节点，作者希望最后只得到 target node 的表征 ，因此作者还设计了一个 Fusion function，原文中是把所有节点表征做一下 average。 都会被输出，根据下游任务选择所需的进行使用。

节点分类效果（没有进行pre-training）

▲ 节点分类

总的来说这篇论文比较新颖的地方在于提出了多种图上的 PE，并且在子图上的效果也可以达到之前 GNN 在全图上的效果，但是实验的数据集太少了，而且也没有使用比较大的图数据集，由于这些数据集较小也没有较好地展现预训练的效果。此外，采样得到的子图最后只是用目标节点进行 loss 计算，这样利用效率太低了，inference 效率同样也很低。

GROVER

Self-Supervised Graph Transformer on Large-Scale Molecular Data (NeurIPS 2020)

https://papers.nips.cc/paper/2020/file/94aef38441efa3380a3bed3faf1f9d5d-Paper.pdf

GNN 在分子领域被广泛研究，但是该领域存在两个主要问题：（1）没有那么多标签数据，（2）在新合成的分子上表现出很差的泛化能力。为了解决这连个问题，该论文设计了 node-，edge-，graph-level 的自监督任务，希望可以从大量的未标注数据中捕获分子中的丰富的语义和结构信息。作者在一千万未标注的分子图上训练了一个 100M 参数量的 GNN，然后根据下游任务进行 fine-tuning，在 11 个数据集上都达到了 SOTA（平均提升超过 6 个点）。

模型结构如下：

▲ 结构图

因为 message passing 的过程可以捕获到图中的局部结构信息，因此将数据先通过 GNN 得到 Q，K，V，可以使得每个节点表征得到 local subgraph structure 的信息。然后，这些表征通过 self-attention 可以捕获到 global 的信息。为了防止 message passing 出现 over-smoothing 现象，该论文将残差链接变成了 long-range residual connection，直接将原始特征接到后面。

此外，由于 GNN 的层数直接影响到感受野，这将影响到 message passing model 的泛化性。由于不同类型的数据集可能需要的 GNN 层数不同，提前定义好 GNN 的层数可能会影响到模型的性能。作者在训练的时候随机选择层数，随机选择 跳的 MPNN，其中 或者 。这种 MPNN 称为 Dynamic Message Passing networks（dyMPN），实验证明这种结构会比普通的 MPNN 好。

预训练：

论文中使用的自监督任务主要有两个：

1. Contextual property prediction(node/edge level task)

▲ Contextual property prediction

一个好的 node-level 自监督任务应该满足两个性质：（1）预测目标是可信的并且是容易得到的（2）预测目标应该反应节点或者边的上下文信息。基于这些性质，作者设计了基于节点和边的自监督任务（通过 subgraph 来预测目标节点/边的上下文相关的性质）

▲ 例子

举一个例子，给定一个 target node C 原子，我们首先获取它的 k-hop 邻居作为subgraph，当 k=1，N 和 O 原子会包含进来以及单键和双键。然后我们从这个 subgraph 中抽取统计特征（statistical properties），我们会计数出针对 center node（node-edge）pairs的共现次数，可表示为 node-edge-counts，所有的 node-edge counts terms 按字母顺序排，在这个例子中，我们可以得到 C_N-DOUBLE1_O-SINGLE1。这个步骤可以看作是一个聚类过程：根据抽取得到的特征，subgraphs 可以被聚类起来，一种特征（property）对应于一簇具有相同统计属性的子图。

通过这种具有 context-aware property 的定义，全局性质预测任务可以分为以下流程：

输入一个分子图，通过 GROVER encoder 我们可以得到原子和边的 embeddings，随机选择原子 （它的 embedding 为 ）。我们不是预测原子 的类别，而是希望 能够编码 node 周围的一些上下文信息（contextual information），实现这一目的的方式是将 输入到一个非常简单的 model（一层全连接），然后使用它的输出去预测节点 的上下文属性（contextual properties），这个预测是一个 multi-class classification（一个类别对应一种contextual property）。

2. Graph-level motif prediction

▲ Graph-level motif prediction

Graph-level 的自监督任务也需要可信和廉价的标签，motifs 是 input graph data 中频繁出现的 sub-graphs。一类重要的 motifs 是官能团，它编码了分子的丰富的领域知识，并且能够被专业的软件检测到（e.g. RDKit）。因此，我们可以将 motif prediction task 公式化成一个多分类问题，每一个 motif 对应一个 label。假设分子数据集中存在 p 个 motifs ，对于某个具体的分子，我们使用 RDKit 检测该分子中是否出现了 motif，然后把其构建为 motif prediction task 的目标。

针对下游任务进行微调：

在海量未标注数据上完成 pre-training 后，我们获得了一个高质量的分子 encoder，针对具体的下游任务（e.g. node classification, link prediction, the property prediction for molecules, etc），我们需要对模型进行微调，针对 graph-level 的下游任务，我们还需要一个额外的 readout 函数来得到全图的表征（node-level 和 edge-level 就不需要 readout 函数了），然后接一个 MLP 进行分类。

实验：

注：绿色表示进行了pre-training

性能的提升还是比较明显的。

Graph Transformer Architecture

A Generalization of Transformer Networks to Graphs (DLG-AAAI 2021)

https://arxiv.org/abs/2012.09699

▲ 模型结构

主要提出使用 Laplacian eigenvector 作为 PE，比 GraphBERT 中使用的 PE 好。

▲ 不同 PE 的效果比较

但是该模型的效果在 self-attention 只关注 neighbors 的时候会更好，与其说是 graph transformer，不如说是带有 PE 的 GAT。Sparse graph 指的是 self-attention 只计算邻居节点，full graph 是指 self-attention 会考虑图中所有节点。

▲ 实验结果

GraphiT

GraphiT: Encoding Graph Structure in Transformers (arXiv 2021)

https://arxiv.org/abs/2106.05667

该工作表明，将结构和位置信息合并到 transformer 中，能够优于现有的经典 GNN。GraphiT（1）利用基于图上的核函数的相对位置编码来影响 attention scores，（2）并编码出 local sub-structures 进行利用。实现发现，无论将这种方法单独使用，还是结合起来使用都取得了不错的效果。

(i) leveraging relative positional encoding strategies in self-attention scores based on positive definite kernels on graphs, and (ii) enumerating and encoding local sub-structures such as paths of short length

之前 GT 发现 self-attention 在只关注 neighboring nodes 的时候会取得比较好的效果，但是在关注到所有节点的时候，性能就不行。这篇论文发现 transformer with global communication 同样可以达到不错的效果。因此，GraphiT 通过一些策略将 local graph structure 编码进模型中，（1）基于正定核的注意力得分加权的相对位置编码策略 （2）通过利用 graph convolution kernel networks（GCKN）将 small sub-structure（e.g.，paths或者subtree patterns）编码出来作为transformer的输入。

Transformer Architectures

Encoding Node Positions

Relative Position Encoding Strategies by Using Kernels on Graphs

Encoding Topological Structures

Graph convolutional kernel networks（GCKN）

实验结果

▲ 实验结果

GraphTrans

Representing Long-Range Context for Graph Neural Networks with Global Attention (NeurIPS 2021)

https://arxiv.org/abs/2201.08821

该论文提出了 GraphTrans，在标准 GNN 层之上添加T ransformer。并提出了一种新的 readout 机制（其实就是 NLP 中的 [CLS] token）。对于图而言，针对 target node 的聚合最好是 permutation-invariant，但是加上 PE 的 transformer 可能就没法实现这个了，因此不使用 PE 在图上是比较自然的。

▲ pipeline

可解释性观察

[CLS]token 是 18，可以发现它和其他 node 交互很频繁。它也许能抽取到更 general 的信息。

虽然这篇论文方法很简单，但做了大量的实验，效果也不错。

NCI biological datasets

▲ NCI biological datasets

OpenGraphBenchmark Molpcba dataset

▲ Molpcba dataset

OpenGraphBenchmark Code2 dataset

▲ Code2 dataset

SAN

Rethinking Graph Transformers with Spectral Attention (NeurIPS 2021)

https://arxiv.org/abs/2106.03893

这篇论文使用 learnable PE，对为什么 laplacian PE 比较有效进行了比较好的说明，

Graphormer

Do Transformers Really Perform Bad for Graph Representation？ (NeurIPS 2021)

https://arxiv.org/abs/2106.05234

原作者自己进行了解读：

https://www.msra.cn/zh-cn/news/features/ogb-lsc

核心点在于利用结构信息对 attention score 进行修正，这样比较好地利用上了图的结构信息。

SAT

Structure-Aware Transformer for Graph Representation Learning (ICML 2022)

https://arxiv.org/abs/2202.03036

这篇论文和 GraphTrans 比较类似。也是先通过 GNN 得到新的节点表征，然后再输入到 GT 中。只是这篇论文对抽取结构信息的方式进行了更抽象化的定义（但是出于便利性，还是使用了 GNN）。还有一点不同就是这篇论文还使用了PE（RWPE）。

在这篇论文中，作者展示了使用位置编码的 Transformer 生成的节点表示不一定捕获节点之间的结构相似性。为了解决这个问题，Chen et al. 提出了一种 structure-aware transformer，这是一种建立在新的 self-attention 机制上的 transformer。这种新的 self-attention 在计算 attention 之前会抽取子图的表征（rooted at each node），这样融合进了结构信息。

作者提出了若干种可以自动生成 subgraph representation 的方法，从理论上证明这些表征至少和 subgraph representations 表现力一样。该 structure-aware 框架能够利用已有的 GNN 去抽取 subgraph representation，从实验上证明了模型的性能提升和 GNN 有较大的关系。仅对 Transformer 使用绝对位置编码会表现出过于宽松的结构归纳偏差，这不能保证两个节点具有相似的局部结构的节点生成相似的节点表示。

GraphGPS

Recipe for a General, Powerful, Scalable Graph Transformer (NeurIPS 2022 Under Review)

https://arxiv.org/abs/2205.12454

在这篇论文中，作者对之前使用的 PE 进行了细致的归类（local，global or relative，详见下方表格）。此外，该论文还提出了构建 General，Powerful，Scalable Graph Transformer 的要素有三：（1）positional/structural encoding，（2）local message-passing mechanism，（3）global attention mechanism。针对这三要素，作者设计了一种新的 graph transformer。

针对 layer 的设计，该论文采用 GPSlayer = a hybrid MPNN+Transformer layer。

该设计与 GraphTrans 的不同在于，GraphTrans 在输入到 Transformer 之前先输入到一个包含若干层的 MPNNs 中，这可能会有 over-smoothing，over-squashing 以及 low expressivity against the WL test 的问题，也就是说这些层可能无法在早期保存一些信息 ，输入到 transfomer 的信息就会有缺失。GPS 的设计是每一层都是一层的 MPNN+transformer layer，然后反复堆叠 L 层。

具体计算如下：

利用 Linear transformer，GPS 可以将时间复杂度降到 。

实验结果

1. 使用不同的 Transformer，MPNN：可以发现不使用 MPNN 掉点很多，使用 Transformer 可以带来性能提升。

▲ 消融实验：使用不同的 transformer，MPNN

2. 使用不同的 PE/SE：在低计算成本下，使用 RWSE 效果最佳。如果不介意计算开销可以使用效果更好的 。

▲ 消融实验：使用不同的PE\SE

3. Benchmarking GPS

3.1 Benchmarking GNNs

3.2 Open Graph Benchmark

▲ Open Graph Benchmark

3.3 OGB-LSC PCQM4Mv2

方法汇总

注：这篇文章主要汇总的是同质图上的 graph transformers，目前也有一些异质图上 graph transformers 的工作，感兴趣的读者自行查阅哈。

1. 图上不同的 transformers 的主要区别在于（1）如何设计 PE，（2）如何利用结构信息（结合 GNN 或者利用结构信息去修正 attention score, etc）。
2. 现有的方法基本都针对 small graphs（最多几百个节点），Graph-BERT 虽然针对节点分类任务，但是首先会通过 sampling 得到子图，这会损害性能（比 GAT 多了很多参数，但性能是差不多的），能否设计一种针对大图的 transformer 还是一个比较难的问题。

▲ 各方法的区别

参考文献

[1] GRAPH-BERT: Only Attention is Needed for Learning Graph Representations：https://github.com/jwzhanggy/Graph-Bert

[2] (GROVER) Self-Supervised Graph Transformer on Large-Scale Molecular Data：https://github.com/tencent-ailab/grover

[3] (GT) A Generalization of Transformer Networks to Graphs：https://github.com/graphdeeplearning/graphtransformer

[4] GraphiT: Encoding Graph Structure in Transformers [Code is unavailable]

[5] (GraphTrans) Representing Long-Range Context for Graph Neural Networks with Global Attention：https://github.com/ucbrise/graphtrans

[6] (SAN) Rethinking Graph Transformers with Spectral Attention [Code is unavailable]

[7] (Graphormer) Do Transformers Really Perform Bad for Graph Representation？：https://github.com/microsoft/Graphormer

[8] (SAT) Structure-Aware Transformer for Graph Representation Learning [Code is unavailable]

[9] (GraphGPS) Recipe for a General, Powerful, Scalable Graph Transformer：https://github.com/rampasek/GraphGPS

其他资料

[1] Graph Transformer综述：https://arxiv.org/abs/2202.08455 [ Code]

[2] Tutorial: [Arxiv 2022,06] A Bird's-Eye Tutorial of Graph Attention Architectures：https://arxiv.org/pdf/2206.02849.pdf

[3] Dataset: [Arxiv 2022,06]Long Range Graph Benchmark [ Code]：https://arxiv.org/pdf/2206.08164.pdf

简介：GNN 一般只能捕获 k-hop 的邻居，而可能无法捕获长距离依赖信息，Transformer 可以解决这一问题。该 benmark 共包含五个数据集（PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func and Peptides-struct），需要模型能捕获长距离依赖才能取得比较好的效果，该数据集主要用来验证模型捕获 long range interactions 的能力。

还有一些同质图上Graph Transformers的工作，感兴趣的同学自行阅读：

[1] [KDD 2022] Global Self-Attention as a Replacement for Graph Convolution：https://arxiv.org/pdf/2108.03348.pdf

[2] [ICOMV 2022] Experimental analysis of position embedding in graph transformer networks：https://www.spiedigitallibrary.org/conference-proceedings-of-spie/12173/121731O/Experimental-analysis-of-position-embedding-in-graph-transformer-networks/10.1117/12.2634427.short

[3] [ICLR Workshop MLDD] GRPE: Relative Positional Encoding for Graph Transformer [Code]：https://arxiv.org/abs/2201.12787

[4] [Arxiv 2022,05] Your Transformer May Not be as Powerful as You Expect [Code]：https://arxiv.org/pdf/2205.13401.pdf

[5] [Arxiv 2022,06] NAGphormer: Neighborhood Aggregation Graph Transformer for Node Classification in Large Graphs：https://arxiv.org/abs/2206.04910