一文帶你瀏覽Graph Transformers
加入技術(shù)交流群
掃碼加入
和技術(shù)大咖面對(duì)面交流
海量資料庫(kù)查詢
來(lái)源丨h(huán)ttps://zhuanlan.zhihu.com/p/536489997編輯丨極市平臺(tái) 導(dǎo)讀
本文通過(guò)整理分析2020-2022年不同頂會(huì)關(guān)于Graph Transformers的論文，匯總并對(duì)比了該領(lǐng)域的各種前沿方法。
寫在前頭為什么圖上要使用Transformer？簡(jiǎn)要提一下GT帶來(lái)的好處：
能捕獲長(zhǎng)距離依賴
減輕出現(xiàn)過(guò)平滑，過(guò)擠壓現(xiàn)象
GT中甚至可以結(jié)合進(jìn)GNN以及頻域信息（Laplacian PE），模型會(huì)有更強(qiáng)的表現(xiàn)力。
利用好[CLS] token，不需要額外使用pooling function。
etc...
GNN過(guò)度依賴圖上的鏈接，此外由于大圖非常耗顯存，可能無(wú)法直接進(jìn)行操作。該論文提出了一種新的只依賴attention機(jī)制的圖網(wǎng)絡(luò)Graph-BERT，Graph-BERT的輸入不是全圖，而是一堆采樣得到的子圖（不帶邊）。作者使用節(jié)點(diǎn)屬性重構(gòu)以及結(jié)構(gòu)恢復(fù)兩個(gè)任務(wù)進(jìn)行預(yù)訓(xùn)練，然后在下游數(shù)據(jù)集上進(jìn)行微調(diào)。該方法在節(jié)點(diǎn)分類和圖聚類任務(wù)上達(dá)到了SOTA。圖1：Graph-BERT和之前NLP中的BERT不一樣的地方主要是position encoding，Graph-BERT使用了三種PE，分別是WL absolute PE，intimacy based relative PE和Hop based relative PE，這里三個(gè)PE都是根據(jù)complete graph計(jì)算得到的。
為了便于操作，作者將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)過(guò)WL之后，子結(jié)構(gòu)一樣的節(jié)點(diǎn)就會(huì)得到相同的hash code，如果是1-WL有點(diǎn)像degree centrality（針對(duì)無(wú)向圖而言）。因此，WL PE可以捕獲全局節(jié)點(diǎn)角色信息。Intimacy based Relative Positional Embedding這個(gè)PE捕獲的是偏local的信息，因?yàn)檩斎胍呀?jīng)根據(jù)圖親密度矩陣進(jìn)行排序過(guò)了，這里只需要簡(jiǎn)單地設(shè) ，越接近i的節(jié)點(diǎn) 會(huì)越小。映射公式如下：
Hop based Relative Distance Embedding該P(yáng)E捕獲的是介于global和local之間的信息：將節(jié)點(diǎn)embedding和這些PE加起來(lái)，然后輸入到Transformer中得到subgraph每個(gè)節(jié)點(diǎn)的表征 。因?yàn)閟ubgraph中有很多節(jié)點(diǎn)，作者希望最后只得到target node 的表征 ，因此作者還設(shè)計(jì)了一個(gè)Fusion function，原文中是把所有節(jié)點(diǎn)表征做一下average。 都會(huì)被輸出，根據(jù)下游任務(wù)選擇所需的進(jìn)行使用。
節(jié)點(diǎn)分類效果（沒有進(jìn)行pre-training）節(jié)點(diǎn)分類總的來(lái)說(shuō)這篇論文比較新穎的地方在于提出了多種圖上的PE，并且在子圖上的效果也可以達(dá)到之前GNN在全圖上的效果，但是實(shí)驗(yàn)的數(shù)據(jù)集太少了，而且也沒有使用比較大的圖數(shù)據(jù)集，由于這些數(shù)據(jù)集較小也沒有較好地展現(xiàn)預(yù)訓(xùn)練的效果。此外，采樣得到的子圖最后只是用目標(biāo)節(jié)點(diǎn)進(jìn)行l(wèi)oss計(jì)算，這樣利用效率太低了，inference效率同樣也很低。
GNN在分子領(lǐng)域被廣泛研究，但是該領(lǐng)域存在兩個(gè)主要問題：（1）沒有那么多標(biāo)簽數(shù)據(jù)，（2）在新合成的分子上表現(xiàn)出很差的泛化能力。為了解決這連個(gè)問題，該論文設(shè)計(jì)了node-，edge-，graph-level的自監(jiān)督任務(wù)，希望可以從大量的未標(biāo)注數(shù)據(jù)中捕獲分子中的豐富的語(yǔ)義和結(jié)構(gòu)信息。作者在一千萬(wàn)未標(biāo)注的分子圖上訓(xùn)練了一個(gè)100M參數(shù)量的GNN，然后根據(jù)下游任務(wù)進(jìn)行fine-tuning，在11個(gè)數(shù)據(jù)集上都達(dá)到了SOTA（平均提升超過(guò)6個(gè)點(diǎn)）。模型結(jié)構(gòu)如下：結(jié)構(gòu)圖因?yàn)閙essage passing的過(guò)程可以捕獲到圖中的局部結(jié)構(gòu)信息，因此將數(shù)據(jù)先通過(guò)GNN得到Q，K，V，可以使得每個(gè)節(jié)點(diǎn)表征得到local subgraph structure的信息。然后，這些表征通過(guò)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ù)可能會(huì)影響到模型的性能。作者在訓(xùn)練的時(shí)候隨機(jī)選擇層數(shù)，隨機(jī)選擇 跳的MPNN，其中 或者 。這種MPNN稱為Dynamic Message Passing networks(dyMPN)，實(shí)驗(yàn)證明這種結(jié)構(gòu)會(huì)比普通的MPNN好。預(yù)訓(xùn)練：論文中使用的自監(jiān)督任務(wù)主要有兩個(gè)：（1）Contextual property prediction(node/edge level task)
Contextual property prediction一個(gè)好的node-level自監(jiān)督任務(wù)應(yīng)該滿足兩個(gè)性質(zhì)：
預(yù)測(cè)目標(biāo)是可信的并且是容易得到的。
預(yù)測(cè)目標(biāo)應(yīng)該反應(yīng)節(jié)點(diǎn)或者邊的上下文信息?；谶@些性質(zhì)，作者設(shè)計(jì)了基于節(jié)點(diǎn)和邊的自監(jiān)督任務(wù)（通過(guò)subgraph來(lái)預(yù)測(cè)目標(biāo)節(jié)點(diǎn)/邊的上下文相關(guān)的性質(zhì)）。
例子舉一個(gè)例子，給定一個(gè)target node C原子，我們首先獲取它的k-hop鄰居作為subgraph，當(dāng)k=1，N和O原子會(huì)包含進(jìn)來(lái)以及單鍵和雙鍵。然后我們從這個(gè)subgraph中抽取統(tǒng)計(jì)特征(statistical properties)，我們會(huì)計(jì)數(shù)出針對(duì)center node (node-edge) pairs的共現(xiàn)次數(shù)，可表示為node-edge-counts，所有的node-edge counts terms按字母順序排，在這個(gè)例子中，我們可以得到 C_N-DOUBLE1_O-SINGLE1。這個(gè)步驟可以看作是一個(gè)聚類過(guò)程：根據(jù)抽取得到的特征，subgraphs可以被聚類起來(lái)，一種特征(property)對(duì)應(yīng)于一簇具有相同統(tǒng)計(jì)屬性的子圖。通過(guò)這種具有context-aware property的定義，全局性質(zhì)預(yù)測(cè)任務(wù)可以分為以下流程：輸入一個(gè)分子圖，通過(guò)GROVER encoder我們可以得到原子和邊的embeddings，隨機(jī)選擇原子 (它的embedding為 )。我們不是預(yù)測(cè)原子 的類別，而是希望 能夠編碼node 周圍的一些上下文信息(contextual information)，實(shí)現(xiàn)這一目的的方式是將 輸入到一個(gè)非常簡(jiǎn)單的model(一層全連接)，然后使用它的輸出去預(yù)測(cè)節(jié)點(diǎn) 的上下文屬性(contextual properties)，這個(gè)預(yù)測(cè)是一個(gè)multi-class classification(一個(gè)類別對(duì)應(yīng)一種contextual property)。（2）Graph-level motif prediction
Graph-level的自監(jiān)督任務(wù)也需要可信和廉價(jià)的標(biāo)簽，motifs是input graph data中頻繁出現(xiàn)的sub-graphs。一類重要的motifs是官能團(tuán)，它編碼了分子的豐富的領(lǐng)域知識(shí)，并且能夠被專業(yè)的軟件檢測(cè)到(e.g. RDKit)。因此，我們可以將motif prediction task公式化成一個(gè)多分類問題，每一個(gè)motif對(duì)應(yīng)一個(gè)label。假設(shè)分子數(shù)據(jù)集中存在p個(gè)motifs ，對(duì)于某個(gè)具體的分子，我們使用RDKit檢測(cè)該分子中是否出現(xiàn)了motif，然后把其構(gòu)建為motif prediction task的目標(biāo)。針對(duì)下游任務(wù)進(jìn)行微調(diào)：在海量未標(biāo)注數(shù)據(jù)上完成pre-training后，我們獲得了一個(gè)高質(zhì)量的分子encoder，針對(duì)具體的下游任務(wù)（e.g. node classification, link prediction, the property prediction for molecules, etc），我們需要對(duì)模型進(jìn)行微調(diào)，針對(duì)graph-level的下游任務(wù)，我們還需要一個(gè)額外的readout函數(shù)來(lái)得到全圖的表征（node-level和edge-level就不需要readout函數(shù)了），然后接一個(gè)MLP進(jìn)行分類。實(shí)驗(yàn)：注：綠色表示進(jìn)行了pre-training性能的提升還是比較明顯的。
模型結(jié)構(gòu)主要提出使用Laplacian eigenvector作為PE，比GraphBERT中使用的PE好
不同PE的效果比較但是該模型的效果在self-attention只關(guān)注neighbors的時(shí)候會(huì)更好，與其說(shuō)是graph transformer，不如說(shuō)是帶有PE的GAT。Sparse graph指的是self-attention只計(jì)算鄰居節(jié)點(diǎn)，full graph是指self-attention會(huì)考慮圖中所有節(jié)點(diǎn)。
實(shí)驗(yàn)結(jié)果
該工作表明，將結(jié)構(gòu)和位置信息合并到transformer中，能夠優(yōu)于現(xiàn)有的經(jīng)典GNN。GraphiT：（1）利用基于圖上的核函數(shù)的相對(duì)位置編碼來(lái)影響attention scores，（2）并編碼出local sub-structures進(jìn)行利用。實(shí)現(xiàn)發(fā)現(xiàn)，無(wú)論將這種方法單獨(dú)使用，還是結(jié)合起來(lái)使用都取得了不錯(cuò)的效果。
(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的時(shí)候會(huì)取得比較好的效果，但是在關(guān)注到所有節(jié)點(diǎn)的時(shí)候，性能就不行。這篇論文發(fā)現(xiàn)transformer with global communication同樣可以達(dá)到不錯(cuò)的效果。因此，GraphiT通過(guò)一些策略將local graph structure編碼進(jìn)模型中，（1）基于正定核的注意力得分加權(quán)的相對(duì)位置編碼策略 （2）通過(guò)利用graph convolution kernel networks (GCKN)將small sub-structure（e.g.，paths或者subtree patterns）編碼出來(lái)作為transformer的輸入。Transformer Architectures
Encoding Node PositionsRelative Position Encoding Strategies by Using Kernels on Graphs
Encoding Topological StructuresGraph convolutional kernel networks (GCKN)實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果
該論文提出了GraphTrans，在標(biāo)準(zhǔn)GNN層之上添加Transformer。并提出了一種新的readout機(jī)制（其實(shí)就是NLP中的[CLS] token）。對(duì)于圖而言，針對(duì)target node的聚合最好是permutation-invariant,但是加上PE的transformer可能就沒法實(shí)現(xiàn)這個(gè)了，因此不使用PE在圖上是比較自然的。pipeline可解釋性觀察[CLS]token是18，可以發(fā)現(xiàn)它和其他node交互很頻繁。它也許能抽取到更general的信息。
雖然這篇論文方法很簡(jiǎn)單，但做了大量的實(shí)驗(yàn)，效果也不錯(cuò)。NCI biological datasets
NCI biological datasetsOpenGraphBenchmark Molpcba dataset
Molpcba datasetOpenGraphBenchmark Code2 dataset
Code2 dataset
這篇論文使用learnable PE，對(duì)為什么laplacian PE比較有效進(jìn)行了比較好的說(shuō)明。
原作者自己進(jìn)行了解讀（https://www.msra.cn/zh-cn/news/features/ogb-lsc）：核心點(diǎn)在于利用結(jié)構(gòu)信息對(duì)attention score進(jìn)行修正，這樣比較好地利用上了圖的結(jié)構(gòu)信息。
[ICML 2022] (SAT) Structure-Aware Transformer for Graph Representation Learning這篇論文和GraphTrans比較類似。也是先通過(guò)GNN得到新的節(jié)點(diǎn)表征，然后再輸入到GT中。只是這篇論文對(duì)抽取結(jié)構(gòu)信息的方式進(jìn)行了更抽象化的定義（但是出于便利性，還是使用了GNN）。還有一點(diǎn)不同就是這篇論文還使用了PE（RWPE）。
在這篇論文中，作者展示了使用位置編碼的Transformer生成的節(jié)點(diǎn)表示不一定捕獲節(jié)點(diǎn)之間的結(jié)構(gòu)相似性。為了解決這個(gè)問題，Chen et al. 提出了一種structure-aware transformer，這是一種建立在新的self-attention機(jī)制上的transformer。這種新的self-attention在計(jì)算attention之前會(huì)抽取子圖的表征（rooted at each node），這樣融合進(jìn)了結(jié)構(gòu)信息。作者提出了若干種可以自動(dòng)生成subgraph representation的方法，從理論上證明這些表征至少和subgraph representations表現(xiàn)力一樣。該structure-aware框架能夠利用已有的GNN去抽取subgraph representation，從實(shí)驗(yàn)上證明了模型的性能提升和GNN有較大的關(guān)系。僅對(duì)Transformer使用絕對(duì)位置編碼會(huì)表現(xiàn)出過(guò)于寬松的結(jié)構(gòu)歸納偏差，這不能保證兩個(gè)節(jié)點(diǎn)具有相似的局部結(jié)構(gòu)的節(jié)點(diǎn)生成相似的節(jié)點(diǎn)表示。
在這篇論文中，作者對(duì)之前使用的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。
針對(duì)這三要素，作者設(shè)計(jì)了一種新的graph transformer。針對(duì)layer的設(shè)計(jì)，該論文采用GPSlayer = a hybrid MPNN+Transformer layer。
該設(shè)計(jì)與GraphTrans的不同在于，GraphTrans在輸入到Transformer之前先輸入到一個(gè)包含若干層的MPNNs中，這可能會(huì)有over-smoothing，over-squashing以及l(fā)ow expressivity against the WL test的問題，也就是說(shuō)這些層可能無(wú)法在早期保存一些信息 ，輸入到transfomer的信息就會(huì)有缺失。GPS的設(shè)計(jì)是每一層都是一層的MPNN+transformer layer，然后反復(fù)堆疊L層。具體計(jì)算如下：利用Linear transformer，GPS可以將時(shí)間復(fù)雜度降到 。實(shí)驗(yàn)結(jié)果
- 使用不同的Transformer，MPNN：可以發(fā)現(xiàn)不使用MPNN掉點(diǎn)很多，使用Transformer可以帶來(lái)性能提升。
消融實(shí)驗(yàn)：使用不同的transformer，MPNN
- 使用不同的PE/SE: 在低計(jì)算成本下，使用RWSE效果最佳。如果不介意計(jì)算開銷可以使用效果更好的 。
消融實(shí)驗(yàn)：使用不同的PE\SE
- Benchmarking GPS
- Benchmarking GNNs
- Open Graph Benchmark
- OGB-LSC PCQM4Mv2
注：這篇文章主要匯總的是同質(zhì)圖上的graph transformers，目前也有一些異質(zhì)圖上graph transformers的工作，感興趣的讀者自行查閱哈。
圖上不同的transformers的主要區(qū)別在于（1）如何設(shè)計(jì)PE，（2）如何利用結(jié)構(gòu)信息（結(jié)合GNN或者利用結(jié)構(gòu)信息去修正attention score, etc）。
現(xiàn)有的方法基本都針對(duì)small graphs（最多幾百個(gè)節(jié)點(diǎn)），Graph-BERT雖然針對(duì)節(jié)點(diǎn)分類任務(wù)，但是首先會(huì)通過(guò)sampling得到子圖，這會(huì)損害性能（比GAT多了很多參數(shù)，但性能是差不多的），能否設(shè)計(jì)一種針對(duì)大圖的transformer還是一個(gè)比較難的問題。
各方法的區(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）
簡(jiǎn)介：GNN一般只能捕獲k-hop的鄰居，而可能無(wú)法捕獲長(zhǎng)距離依賴信息， Transformer可以解決這一問題。該benmark共包含五個(gè)數(shù)據(jù)集（PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func and Peptides-struct），需要模型能捕獲長(zhǎng)距離依賴才能取得比較好的效果，該數(shù)據(jù)集主要用來(lái)驗(yàn)證模型捕獲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)，請(qǐng)聯(lián)系刪文。
*博客內(nèi)容為網(wǎng)友個(gè)人發(fā)布，僅代表博主個(gè)人觀點(diǎn)，如有侵權(quán)請(qǐng)聯(lián)系工作人員刪除。
