一文帶你瀏覽Graph Transformers

作者丨whistle@知乎 （已授權(quán)）

來源丨h(huán)ttps://zhuanlan.zhihu.com/p/536489997編輯丨極市平臺

導(dǎo)讀

 

本文通過整理分析2020-2022年不同頂會關(guān)于Graph Transformers的論文，匯總并對比了該領(lǐng)域的各種前沿方法。

寫在前頭為什么圖上要使用Transformer？

簡要提一下GT帶來的好處：

1. 能捕獲長距離依賴

2. 減輕出現(xiàn)過平滑，過擠壓現(xiàn)象

3. GT中甚至可以結(jié)合進(jìn)GNN以及頻域信息（Laplacian PE），模型會有更強(qiáng)的表現(xiàn)力。

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

5. etc...

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

GNN過度依賴圖上的鏈接，此外由于大圖非常耗顯存，可能無法直接進(jìn)行操作。該論文提出了一種新的只依賴attention機(jī)制的圖網(wǎng)絡(luò)Graph-BERT，Graph-BERT的輸入不是全圖，而是一堆采樣得到的子圖（不帶邊）。作者使用節(jié)點屬性重構(gòu)以及結(jié)構(gòu)恢復(fù)兩個任務(wù)進(jìn)行預(yù)訓(xùn)練，然后在下游數(shù)據(jù)集上進(jìn)行微調(diào)。該方法在節(jié)點分類和圖聚類任務(wù)上達(dá)到了SOTA。圖1：Graph-BERT和之前NLP中的BERT不一樣的地方主要是position encoding，Graph-BERT使用了三種PE，分別是WL absolute PE，intimacy based relative PE和Hop based relative PE，這里三個PE都是根據(jù)complete graph計算得到的。

為了便于操作，作者將subgraph根據(jù)圖親密度矩陣（https://zhuanlan.zhihu.com/p/272754714）進(jìn)行排序[i, j, ...m]，其中S(i,j) > S(i,m)，得到序列化的結(jié)果。

其中Weisfeiler-Lehman Absolute Role Embedding如下：經(jīng)過WL之后，子結(jié)構(gòu)一樣的節(jié)點就會得到相同的hash code，如果是1-WL有點像degree centrality（針對無向圖而言）。因此，WL PE可以捕獲全局節(jié)點角色信息。Intimacy based Relative Positional Embedding這個PE捕獲的是偏local的信息，因為輸入已經(jīng)根據(jù)圖親密度矩陣進(jìn)行排序過了，這里只需要簡單地設(shè)  ，越接近i的節(jié)點  會越小。映射公式如下：
Hop based Relative Distance Embedding該PE捕獲的是介于global和local之間的信息：將節(jié)點embedding和這些PE加起來，然后輸入到Transformer中得到subgraph每個節(jié)點的表征  。因為subgraph中有很多節(jié)點，作者希望最后只得到target node  的表征  ，因此作者還設(shè)計了一個Fusion function，原文中是把所有節(jié)點表征做一下average。 都會被輸出，根據(jù)下游任務(wù)選擇所需的進(jìn)行使用。

節(jié)點分類效果（沒有進(jìn)行pre-training）節(jié)點分類總的來說這篇論文比較新穎的地方在于提出了多種圖上的PE，并且在子圖上的效果也可以達(dá)到之前GNN在全圖上的效果，但是實驗的數(shù)據(jù)集太少了，而且也沒有使用比較大的圖數(shù)據(jù)集，由于這些數(shù)據(jù)集較小也沒有較好地展現(xiàn)預(yù)訓(xùn)練的效果。此外，采樣得到的子圖最后只是用目標(biāo)節(jié)點進(jìn)行l(wèi)oss計算，這樣利用效率太低了，inference效率同樣也很低。

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

GNN在分子領(lǐng)域被廣泛研究，但是該領(lǐng)域存在兩個主要問題：（1）沒有那么多標(biāo)簽數(shù)據(jù)，（2）在新合成的分子上表現(xiàn)出很差的泛化能力。為了解決這連個問題，該論文設(shè)計了node-，edge-，graph-level的自監(jiān)督任務(wù)，希望可以從大量的未標(biāo)注數(shù)據(jù)中捕獲分子中的豐富的語義和結(jié)構(gòu)信息。作者在一千萬未標(biāo)注的分子圖上訓(xùn)練了一個100M參數(shù)量的GNN，然后根據(jù)下游任務(wù)進(jìn)行fine-tuning，在11個數(shù)據(jù)集上都達(dá)到了SOTA（平均提升超過6個點）。模型結(jié)構(gòu)如下：結(jié)構(gòu)圖因為message passing的過程可以捕獲到圖中的局部結(jié)構(gòu)信息，因此將數(shù)據(jù)先通過GNN得到Q，K，V，可以使得每個節(jié)點表征得到local subgraph structure的信息。然后，這些表征通過self-attention可以捕獲到global的信息。為了防止message passing出現(xiàn)over-smoothing現(xiàn)象，該論文將殘差鏈接變成了long-range residual connection，直接將原始特征接到后面。此外，由于GNN的層數(shù)直接影響到感受野，這將影響到message passing model的泛化性。由于不同類型的數(shù)據(jù)集可能需要的GNN層數(shù)不同，提前定義好GNN的層數(shù)可能會影響到模型的性能。作者在訓(xùn)練的時候隨機(jī)選擇層數(shù)，隨機(jī)選擇  跳的MPNN，其中  或者  。這種MPNN稱為Dynamic Message Passing networks(dyMPN)，實驗證明這種結(jié)構(gòu)會比普通的MPNN好。預(yù)訓(xùn)練：論文中使用的自監(jiān)督任務(wù)主要有兩個：（1）Contextual property prediction(node/edge level task)Contextual property prediction一個好的node-level自監(jiān)督任務(wù)應(yīng)該滿足兩個性質(zhì)：

• 預(yù)測目標(biāo)是可信的并且是容易得到的。

• 預(yù)測目標(biāo)應(yīng)該反應(yīng)節(jié)點或者邊的上下文信息。基于這些性質(zhì)，作者設(shè)計了基于節(jié)點和邊的自監(jiān)督任務(wù)（通過subgraph來預(yù)測目標(biāo)節(jié)點/邊的上下文相關(guān)的性質(zhì)）。

例子舉一個例子，給定一個target node C原子，我們首先獲取它的k-hop鄰居作為subgraph，當(dāng)k=1，N和O原子會包含進(jìn)來以及單鍵和雙鍵。然后我們從這個subgraph中抽取統(tǒng)計特征(statistical properties)，我們會計數(shù)出針對center node (node-edge) pairs的共現(xiàn)次數(shù)，可表示為node-edge-counts，所有的node-edge counts terms按字母順序排，在這個例子中，我們可以得到 C_N-DOUBLE1_O-SINGLE1。這個步驟可以看作是一個聚類過程：根據(jù)抽取得到的特征，subgraphs可以被聚類起來，一種特征(property)對應(yīng)于一簇具有相同統(tǒng)計屬性的子圖。通過這種具有context-aware property的定義，全局性質(zhì)預(yù)測任務(wù)可以分為以下流程：輸入一個分子圖，通過GROVER encoder我們可以得到原子和邊的embeddings，隨機(jī)選擇原子  (它的embedding為  )。我們不是預(yù)測原子  的類別，而是希望  能夠編碼node  周圍的一些上下文信息(contextual information)，實現(xiàn)這一目的的方式是將  輸入到一個非常簡單的model(一層全連接)，然后使用它的輸出去預(yù)測節(jié)點  的上下文屬性(contextual properties)，這個預(yù)測是一個multi-class classification(一個類別對應(yīng)一種contextual property)。（2）Graph-level motif predictionGraph-level的自監(jiān)督任務(wù)也需要可信和廉價的標(biāo)簽，motifs是input graph data中頻繁出現(xiàn)的sub-graphs。一類重要的motifs是官能團(tuán)，它編碼了分子的豐富的領(lǐng)域知識，并且能夠被專業(yè)的軟件檢測到(e.g. RDKit)。因此，我們可以將motif prediction task公式化成一個多分類問題，每一個motif對應(yīng)一個label。假設(shè)分子數(shù)據(jù)集中存在p個motifs  ，對于某個具體的分子，我們使用RDKit檢測該分子中是否出現(xiàn)了motif，然后把其構(gòu)建為motif prediction task的目標(biāo)。針對下游任務(wù)進(jìn)行微調(diào)：在海量未標(biāo)注數(shù)據(jù)上完成pre-training后，我們獲得了一個高質(zhì)量的分子encoder，針對具體的下游任務(wù)（e.g. node classification, link prediction, the property prediction for molecules, etc），我們需要對模型進(jìn)行微調(diào)，針對graph-level的下游任務(wù)，我們還需要一個額外的readout函數(shù)來得到全圖的表征（node-level和edge-level就不需要readout函數(shù)了），然后接一個MLP進(jìn)行分類。實驗：注：綠色表示進(jìn)行了pre-training性能的提升還是比較明顯的。

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

模型結(jié)構(gòu)主要提出使用Laplacian eigenvector作為PE，比GraphBERT中使用的PE好不同PE的效果比較但是該模型的效果在self-attention只關(guān)注neighbors的時候會更好，與其說是graph transformer，不如說是帶有PE的GAT。Sparse graph指的是self-attention只計算鄰居節(jié)點，full graph是指self-attention會考慮圖中所有節(jié)點。實驗結(jié)果

[Arxiv 2021] GraphiT: Encoding Graph Structure in Transformers

該工作表明，將結(jié)構(gòu)和位置信息合并到transformer中，能夠優(yōu)于現(xiàn)有的經(jīng)典GNN。GraphiT：（1）利用基于圖上的核函數(shù)的相對位置編碼來影響attention scores，（2）并編碼出local sub-structures進(jìn)行利用。實現(xiàn)發(fā)現(xiàn)，無論將這種方法單獨使用，還是結(jié)合起來使用都取得了不錯的效果。

(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發(fā)現(xiàn)self-attention在只關(guān)注neighboring nodes的時候會取得比較好的效果，但是在關(guān)注到所有節(jié)點的時候，性能就不行。這篇論文發(fā)現(xiàn)transformer with global communication同樣可以達(dá)到不錯的效果。因此，GraphiT通過一些策略將local graph structure編碼進(jìn)模型中，（1）基于正定核的注意力得分加權(quán)的相對位置編碼策略 （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)實驗結(jié)果實驗結(jié)果

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

該論文提出了GraphTrans，在標(biāo)準(zhǔn)GNN層之上添加Transformer。并提出了一種新的readout機(jī)制（其實就是NLP中的[CLS] token）。對于圖而言，針對target node的聚合最好是permutation-invariant,但是加上PE的transformer可能就沒法實現(xiàn)這個了，因此不使用PE在圖上是比較自然的。pipeline可解釋性觀察[CLS]token是18，可以發(fā)現(xiàn)它和其他node交互很頻繁。它也許能抽取到更general的信息。雖然這篇論文方法很簡單，但做了大量的實驗，效果也不錯。NCI biological datasetsNCI biological datasetsOpenGraphBenchmark Molpcba datasetMolpcba datasetOpenGraphBenchmark Code2 datasetCode2 dataset

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

這篇論文使用learnable PE，對為什么laplacian PE比較有效進(jìn)行了比較好的說明。

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

原作者自己進(jìn)行了解讀（https://www.msra.cn/zh-cn/news/features/ogb-lsc）：核心點在于利用結(jié)構(gòu)信息對attention score進(jìn)行修正，這樣比較好地利用上了圖的結(jié)構(gòu)信息。

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

這篇論文和GraphTrans比較類似。也是先通過GNN得到新的節(jié)點表征，然后再輸入到GT中。只是這篇論文對抽取結(jié)構(gòu)信息的方式進(jìn)行了更抽象化的定義（但是出于便利性，還是使用了GNN）。還有一點不同就是這篇論文還使用了PE（RWPE）。

在這篇論文中，作者展示了使用位置編碼的Transformer生成的節(jié)點表示不一定捕獲節(jié)點之間的結(jié)構(gòu)相似性。為了解決這個問題，Chen et al. 提出了一種structure-aware transformer，這是一種建立在新的self-attention機(jī)制上的transformer。這種新的self-attention在計算attention之前會抽取子圖的表征（rooted at each node），這樣融合進(jìn)了結(jié)構(gòu)信息。作者提出了若干種可以自動生成subgraph representation的方法，從理論上證明這些表征至少和subgraph representations表現(xiàn)力一樣。該structure-aware框架能夠利用已有的GNN去抽取subgraph representation，從實驗上證明了模型的性能提升和GNN有較大的關(guān)系。僅對Transformer使用絕對位置編碼會表現(xiàn)出過于寬松的結(jié)構(gòu)歸納偏差，這不能保證兩個節(jié)點具有相似的局部結(jié)構(gòu)的節(jié)點生成相似的節(jié)點表示。

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

在這篇論文中，作者對之前使用的PE進(jìn)行了細(xì)致的歸類（local, global or relative, 詳見下方表格）。此外，該論文還提出了構(gòu)建General, Powerful, Scalable Graph Transformer的要素有三：

• positional/structural encoding,

• local message-passing mechanism,

• global attention mechanism。

針對這三要素，作者設(shè)計了一種新的graph transformer。針對layer的設(shè)計，該論文采用GPSlayer = a hybrid MPNN+Transformer layer。該設(shè)計與GraphTrans的不同在于，GraphTrans在輸入到Transformer之前先輸入到一個包含若干層的MPNNs中，這可能會有over-smoothing，over-squashing以及l(fā)ow expressivity against the WL test的問題，也就是說這些層可能無法在早期保存一些信息 ，輸入到transfomer的信息就會有缺失。GPS的設(shè)計是每一層都是一層的MPNN+transformer layer，然后反復(fù)堆疊L層。具體計算如下：利用Linear transformer，GPS可以將時間復(fù)雜度降到  。實驗結(jié)果

1. 使用不同的Transformer，MPNN：可以發(fā)現(xiàn)不使用MPNN掉點很多，使用Transformer可以帶來性能提升。

消融實驗：使用不同的transformer，MPNN

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

消融實驗：使用不同的PE\SE

1. Benchmarking GPS

• Benchmarking GNNs

• Open Graph Benchmark

• OGB-LSC PCQM4Mv2

方法匯總

注：這篇文章主要匯總的是同質(zhì)圖上的graph transformers，目前也有一些異質(zhì)圖上graph transformers的工作，感興趣的讀者自行查閱哈。

1. 圖上不同的transformers的主要區(qū)別在于（1）如何設(shè)計PE，（2）如何利用結(jié)構(gòu)信息（結(jié)合GNN或者利用結(jié)構(gòu)信息去修正attention score, etc）。

2. 現(xiàn)有的方法基本都針對small graphs（最多幾百個節(jié)點），Graph-BERT雖然針對節(jié)點分類任務(wù)，但是首先會通過sampling得到子圖，這會損害性能（比GAT多了很多參數(shù)，但性能是差不多的），能否設(shè)計一種針對大圖的transformer還是一個比較難的問題。

各方法的區(qū)別

代碼參考

• 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共包含五個數(shù)據(jù)集（PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func and Peptides-struct），需要模型能捕獲長距離依賴才能取得比較好的效果，該數(shù)據(jù)集主要用來驗證模型捕獲long range interactions的能力。

還有一些同質(zhì)圖上Graph Transformers的工作，感興趣的同學(xué)自行閱讀：

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

本文僅做學(xué)術(shù)分享，如有侵權(quán)，請聯(lián)系刪文。

*博客內(nèi)容為網(wǎng)友個人發(fā)布，僅代表博主個人觀點，如有侵權(quán)請聯(lián)系工作人員刪除。