作者丨whistle@知乎 （已授权）

来源丨https://zhuanlan.zhihu.com/p/536489997

极市平台编辑

导读

本文通过对2020-2022年不同顶会的整理分析Graph Transformers本文总结并比较了该领域的各种前沿方法。

写在前头

为什么要用图？Transformer？

简要提一下GT好处：

1. 能捕捉长距离依赖

2. 减少过度平滑和过度挤压

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

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

5. etc...

文章汇总

[Arxiv 2020] GRAPH-BERT: Only Attention is Needed for Learning Graph Representations

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

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

为便于操作，作者将subgraph根据图亲密度矩阵（https://zhuanlan.zhihu.com/p/272754714[i, j, ...m]，其中S(i,j) > S(i,m)，序列化结果。

其中Weisfeiler-Lehman Absolute Role Embedding如下：

402 Payment Required

经过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。根据下游任务游任务选择所需的使用。

402 Payment Required

节点分类效果(无pre-training）

总的来说，这篇论文的新颖之处在于提出了各种图片PE，而且子图上的效果也可以达到前的效果GNN整个图片的效果，但实验数据集太少，没有使用相对较大的图形数据集，因为这些数据集很小，。此外，从采样中获得的子图最终只使用目标节点loss计算，利用效率太低，inference效率也很低。

[NIPS 2020] (GROVER) Self-Supervised Graph Transformer on Large-Scale Molecular Data

GNN在分子领域被广泛研究，但是该领域存在两个主要问题：（1）没有那么多标签数据，（2）在新合成的分子上表现出很差的泛化能力。该论文设计了解决这一连续问题的方法node-，edge-，graph-level希望从大量未标注的数据中捕获分子中丰富的语义和结构信息。作者在1000万未标记的分子图上训练了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)

一个好的node-level自我监督任务应满足两个性质：

• 预测目标是可且易于获得。

• 预测目标应反映节点或边缘的上下文信息。基于这些性质，作者设计了基于节点和边缘的自我监督任务(通过subgraph预测目标节点/边上下文的性质)。

举个例子，给出一个例子target node C原子，我们首先得到它k-hop邻居作为subgraph，当k=1，NO原子包括单键和双键。然后我们从这个开始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自我监督任务也需要可靠和廉价的标签，motifs是input graph data频繁出现sub-graphs。一类重要的moifs是官能团，它编码了分子的丰富的领域知识，并且能够被专业的软件检测到(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

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

[AAAI 2020 Workshop] (GT) A Generalization of Transformer Networks to Graphs

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

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

[Arxiv 2021] GraphiT: Encoding Graph Structure in Transformers

该工作表明，将结构和位置信息合并到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

402 Payment Required

Encoding Node Positions

Relative Position Encoding Strategies by Using Kernels on Graphs

Encoding Topological Structures

Graph convolutional kernel networks (GCKN)

实验结果

[NIPS 2021] (GraphTrans) Representing Long-Range Context for Graph Neural Networks with Global Attention

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

可解释性观察

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

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

NCI biological datasets

OpenGraphBenchmark Molpcba dataset

OpenGraphBenchmark Code2 dataset

[NIPS 2021] (SAN) Rethinking Graph Transformers with Spectral Attention

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

[NIPS 2021] (Graphormer) Do Transformers Really Perform Bad for Graph Representation？

原作者自己进行了解读（https://www.msra.cn/zh-cn/news/features/ogb-lsc）：

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

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

这篇论文和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使用绝对位置编码会表现出过于宽松的结构归纳偏差，这不能保证两个节点具有相似的局部结构的节点生成相似的节点表示。

[NIPS 2022 Under Review] (GraphGPS) Recipe for a General, Powerful, Scalable Graph Transformer

在这篇论文中，作者对之前使用的PE进行了细致的归类（local, global or relative, 详见下方表格）。此外，该论文还提出了构建General, Powerful, Scalable Graph Transformer的要素有三：

• positional/structural encoding,

• local message-passing mechanism,

• 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层。

402 Payment Required

具体计算如下：

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

实验结果

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

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

1. Benchmarking GPS

• Benchmarking GNNs

• Open Graph Benchmark

• OGB-LSC PCQM4Mv2

方法汇总

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

1. 图上不同的transformers的主要区别在于（1）如何设计PE，（2）如何利用结构信息（结合GNN或者利用结构信息去修正attention score, etc）。

2. 现有的方法基本都针对small graphs（最多几百个节点），Graph-BERT虽然针对节点分类任务，但是首先会通过sampling得到子图，这会损害性能（比GAT多了很多参数，但性能是差不多的），能否设计一种针对大图的transformer还是一个比较难的问题。

代码参考

• GRAPH-BERT: Only Attention is Needed for Learning Graph Representations (https://github.com/jwzhanggy/Graph-Bert)

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

• (GT) A Generalization of Transformer Networks to Graphs (https://github.com/graphdeeplearning/graphtransformer)

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

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

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

• (Graphormer) Do Transformers Really Perform Bad for Graph Representation？(https://github.com/microsoft/Graphormer)

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

• (GraphGPS) Recipe for a General, Powerful, Scalable Graph Transformer(https://github.com/rampasek/GraphGPS)

其他资料

• Graph Transformer综述（https://arxiv.org/abs/2202.08455）；Code（https://github.com/qwerfdsaplking/Graph-Trans）

• Tutorial: A Bird's-Eye Tutorial of Graph Attention Architectures (https://arxiv.org/pdf/2206.02849.pdf)

• Dataset: Long Range Graph Benchmark (https://arxiv.org/pdf/2206.08164.pdf)；Code（https://github.com/vijaydwivedi75/lrgb）

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

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

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

• [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)

• [ICLR Workshop MLDD] GRPE: Relative Positional Encoding for Graph Transformer (https://arxiv.org/abs/2201.12787)；[Code] (https://github.com/lenscloth/GRPE)

• [Arxiv 2022,05] Your Transformer May Not be as Powerful as You Expect (https://arxiv.org/pdf/2205.13401.pdf)；[Code] (https://github.com/lenscloth/GRPE)

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

本文仅做学术分享，如有侵权，请联系删文。

干货下载与学习

后台回复：巴塞罗那自治大学课件，即可下载国外大学沉淀数年3D Vison精品课件

后台回复：计算机视觉书籍，即可下载3D视觉领域经典书籍pdf

后台回复：3D视觉课程，即可学习3D视觉领域精品课程

计算机视觉工坊精品课程官网：3dcver.com

1.面向自动驾驶领域的多传感器数据融合技术

2.面向自动驾驶领域的3D点云目标检测全栈学习路线！(单模态+多模态/数据+代码)
3.彻底搞透视觉三维重建：原理剖析、代码讲解、及优化改进
4.国内首个面向工业级实战的点云处理课程
5.激光-视觉-IMU-GPS融合SLAM算法梳理和代码讲解
6.彻底搞懂视觉-惯性SLAM：基于VINS-Fusion正式开课啦
7.彻底搞懂基于LOAM框架的3D激光SLAM: 源码剖析到算法优化
8.彻底剖析室内、室外激光SLAM关键算法原理、代码和实战(cartographer+LOAM +LIO-SAM)

9.从零搭建一套结构光3D重建系统[理论+源码+实践]

10.单目深度估计方法：算法梳理与代码实现

11.自动驾驶中的深度学习模型部署实战

12.相机模型与标定(单目+双目+鱼眼）

13.重磅！四旋翼飞行器：算法与实战

14.ROS2从入门到精通：理论与实战

15.国内首个3D缺陷检测教程：理论、源码与实战

16.基于Open3D的点云处理入门与实战教程

重磅！计算机视觉工坊-学习交流群已成立

扫码添加小助手微信，可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群，旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。

同时也可申请加入我们的细分方向交流群，目前主要有ORB-SLAM系列源码学习、3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、深度估计、学术交流、求职交流等微信群，请扫描下面微信号加群，备注：”研究方向+学校/公司+昵称“，例如：”3D视觉 + 上海交大 + 静静“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进去相关微信群。原创投稿也请联系。

▲长按加微信群或投稿

▲长按关注公众号

3D视觉从入门到精通知识星球：针对3D视觉领域的视频课程（三维重建系列、三维点云系列、结构光系列、手眼标定、相机标定、激光/视觉SLAM、自动驾驶等）、知识点汇总、入门进阶学习路线、最新paper分享、疑问解答五个方面进行深耕，更有各类大厂的算法工程人员进行技术指导。与此同时，星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息，打造成集技术与就业为一体的铁杆粉丝聚集区，近4000星球成员为创造更好的AI世界共同进步，知识星球入口：

学习3D视觉核心技术，扫描查看介绍，3天内无条件退款

 圈里有高质量教程资料、答疑解惑、助你高效解决问题

觉得有用，麻烦给个赞和在看~