一文帶你瀏覽Graph Transformers
加入技術交流群
來源丨https://zhuanlan.zhihu.com/p/536489997編輯丨極市平臺 導讀
本文通過整理分析2020-2022年不同頂會關于Graph Transformers的論文，匯總并對比了該領域的各種前沿方法。
寫在前頭為什么圖上要使用Transformer？簡要提一下GT帶來的好處：
能捕獲長距離依賴
減輕出現過平滑，過擠壓現象
GT中甚至可以結合進GNN以及頻域信息（Laplacian PE），模型會有更強的表現力。
利用好[CLS] token，不需要額外使用pooling function。
etc...
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根據圖親密度矩陣（https://zhuanlan.zhihu.com/p/272754714）進行排序[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效率同樣也很低。
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自監督任務應該滿足兩個性質：
預測目標是可信的并且是容易得到的。
預測目標應該反應節點或者邊的上下文信息。基于這些性質，作者設計了基于節點和邊的自監督任務（通過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的自監督任務也需要可信和廉價的標簽，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性能的提升還是比較明顯的。
模型結構主要提出使用Laplacian eigenvector作為PE，比GraphBERT中使用的PE好
不同PE的效果比較但是該模型的效果在self-attention只關注neighbors的時候會更好，與其說是graph transformer，不如說是帶有PE的GAT。Sparse graph指的是self-attention只計算鄰居節點，full graph是指self-attention會考慮圖中所有節點。
實驗結果
該工作表明，將結構和位置信息合并到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 PositionsRelative Position Encoding Strategies by Using Kernels on Graphs
Encoding Topological StructuresGraph convolutional kernel networks (GCKN)實驗結果實驗結果
該論文提出了GraphTrans，在標準GNN層之上添加Transformer。并提出了一種新的readout機制（其實就是NLP中的[CLS] token）。對于圖而言，針對target node的聚合最好是permutation-invariant,但是加上PE的transformer可能就沒法實現這個了，因此不使用PE在圖上是比較自然的。pipeline可解釋性觀察[CLS]token是18，可以發現它和其他node交互很頻繁。它也許能抽取到更general的信息。
雖然這篇論文方法很簡單，但做了大量的實驗，效果也不錯。NCI biological datasets
NCI biological datasetsOpenGraphBenchmark Molpcba dataset
Molpcba datasetOpenGraphBenchmark Code2 dataset
Code2 dataset
這篇論文使用learnable PE，對為什么laplacian PE比較有效進行了比較好的說明。
原作者自己進行了解讀（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使用絕對位置編碼會表現出過于寬松的結構歸納偏差，這不能保證兩個節點具有相似的局部結構的節點生成相似的節點表示。
在這篇論文中，作者對之前使用的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層。具體計算如下：利用Linear transformer，GPS可以將時間復雜度降到 。實驗結果
- 使用不同的Transformer，MPNN：可以發現不使用MPNN掉點很多，使用Transformer可以帶來性能提升。
消融實驗：使用不同的transformer，MPNN
- 使用不同的PE/SE: 在低計算成本下，使用RWSE效果最佳。如果不介意計算開銷可以使用效果更好的 。
消融實驗：使用不同的PE\SE
- Benchmarking GPS
- Benchmarking GNNs
- Open Graph Benchmark
- OGB-LSC PCQM4Mv2
注：這篇文章主要匯總的是同質圖上的graph transformers，目前也有一些異質圖上graph transformers的工作，感興趣的讀者自行查閱哈。
圖上不同的transformers的主要區別在于（1）如何設計PE，（2）如何利用結構信息（結合GNN或者利用結構信息去修正attention score, etc）。
現有的方法基本都針對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)
本文僅做學術分享，如有侵權，請聯系刪文。
*博客內容為網友個人發布，僅代表博主個人觀點，如有侵權請聯系工作人員刪除。
