一文淺談Graph Transformer領(lǐng)域近期研究進展

在圖表示學(xué)習(xí)中，Graph Transformer 通過位置編碼對圖結(jié)構(gòu)信息進行編碼，相比 GNN，可以捕獲長距離依賴，減輕過平滑現(xiàn)象。本文介紹 Graph Transformer 的兩篇近期工作。

SAT

論文標題：Structure-Aware Transformer for Graph Representation Learning收錄會議：ICML 2022

論文鏈接：

https://arxiv.org/abs/2202.03036

代碼鏈接：

https://github.com/BorgwardtLab/SAT

本文分析了 Transformer 的位置編碼，認為使用位置編碼的 Transformer 生成的節(jié)點表示不一定捕獲它們之間的結(jié)構(gòu)相似性。為了解決這個問題，提出了結(jié)構(gòu)感知 Transformer，通過設(shè)計新的自注意機制，使其能夠捕獲到結(jié)構(gòu)信息。新的注意力機制通過在計算注意力得分之前，提取每個節(jié)點的子圖表示，并將結(jié)構(gòu)信息合并到原始的自注意機制中。

本文提出了幾種自動生成子圖表示的方法，并從理論上表明，生成的表示至少與子圖表示具有相同的表達能力。該方法在五個圖預(yù)測基準上達到了最先進的性能，可以利用任何現(xiàn)有的 GNN 來提取子圖表示。它系統(tǒng)地提高了相對于基本 GNN 模型的性能，成功地結(jié)合了 GNN 和 Transformer。

1.1 方法

本文提出了一個將圖結(jié)構(gòu)編碼到注意力機制中的模型。首先，通過 Structure extractor 抽取節(jié)點的子圖結(jié)構(gòu)，進行子圖結(jié)構(gòu)的注意力計算。其次，遵循 Transformer 的結(jié)構(gòu)進行計算。

Structure-Aware Self-Attention

Transformer 原始結(jié)構(gòu)的注意力機制可以被重寫為一個核平滑器：

其中， 是一個線性函數(shù)。 是 空間中，由 和 參數(shù)化的（非對稱）指數(shù)核：

是定義在節(jié)點特征上的可訓(xùn)練指數(shù)核函數(shù)，這就帶來了一個問題：當節(jié)點特征相似時，結(jié)構(gòu)信息無法被識別并編碼。為了同時考慮節(jié)點之間的結(jié)構(gòu)相似性，我們考慮了一個更一般化的核函數(shù)，額外考慮了每個節(jié)點周圍的局部子結(jié)構(gòu)。通過引入以每個節(jié)點為中心的一組子圖，定義結(jié)構(gòu)感知注意力如下：

其中， 是節(jié)點 在圖 中的子圖，與節(jié)點特征 相關(guān)， 是可以是任意比較一對子圖的核函數(shù)。該自注意函數(shù)不僅考慮了節(jié)點特征的相似度，而且考慮了子圖之間的結(jié)構(gòu)相似度。因此，它生成了比原始的自我關(guān)注更有表現(xiàn)力的節(jié)點表示。定義如下形式的 ：

其中 是一個結(jié)構(gòu)提取器，它提取以 為中心、具有節(jié)點特征 的子圖的向量表示。結(jié)構(gòu)感知自我注意力十分靈活，可以與任何生成子圖表示的模型結(jié)合，包括 GNN 和圖核函數(shù)。在自注意計算中并不考慮邊緣屬性，而是將其合并到結(jié)構(gòu)感知節(jié)點表示中。文章提出兩種生成子圖的方法：k-subtree GNN extractor 和 k-subgraph GNN extractor，并進行相關(guān)實驗。

1.2 實驗

下圖是模型在圖回歸和圖分類任務(wù)上的效果。

使用 GNN 抽取結(jié)構(gòu)信息后，再用 Transformer 學(xué)習(xí)特征，由下圖可以看出，Transformer 可以增強 GNN 的性能。

GraphGPS

論文標題：Recipe for a General, Powerful, Scalable Graph Transformer收錄會議：NeurIPS 2022

論文鏈接：

https://arxiv.org/abs/2205.12454

代碼鏈接：

https://github.com/rampasek/GraphGPS 本文首先總結(jié)了不同類型的編碼，并對其進行了更清晰的定義，將其分為局部編碼、全局編碼和相對編碼。其次，提出了模塊化框架 GraphGPS，支持多種類型的編碼，在小圖和大圖中提供效率和可伸縮性。框架由位置/結(jié)構(gòu)編碼、局部消息傳遞機制、全局注意機制三個部分組成。該架構(gòu)在所有基準測試中顯示了極具競爭力的結(jié)果，展示了模塊化和不同策略組合所獲得的經(jīng)驗好處。

2.1 方法

在相關(guān)工作中，位置/結(jié)構(gòu)編碼是影響 Graph Transformer 性能的最重要因素之一。因此，更好地理解和組織位置/結(jié)構(gòu)編碼將有助于構(gòu)建更加模塊化的體系結(jié)構(gòu)，并指導(dǎo)未來的研究。本文將位置/結(jié)構(gòu)編碼分成三類：局部編碼、全局編碼和相對編碼。各類編碼的含義和示例如下表所示。 現(xiàn)有的 MPNN + Transformer 混合模型往往是 MPNN 層和 Transformer 層逐層堆疊，由于 MPNN 固有結(jié)構(gòu)帶來的過平滑問題，導(dǎo)致這樣的混合模型的性能也會受到影響。因此，本文提出新的混合架構(gòu)，使 MPNN 和 Transformer 的計算相互獨立，獲得更好的性能。具體框架如圖所示。

框架主要由位置/結(jié)構(gòu)編碼、局部消息傳遞機制（MPNN）、全局注意機制（Self Attention）三部分組成。根據(jù)不同的需求設(shè)計位置/結(jié)構(gòu)編碼，與輸入特征相加，然后分別輸入到 MPNN 和 Transformer 模型中進行訓(xùn)練，再對兩個模型的結(jié)果相加，最后經(jīng)過一個 2 層 MLP 將輸出結(jié)果更好的融合，得到最終的輸出。更新公式如下：

2.2 實驗

在圖級別的任務(wù)上，效果超越主流方法：

通過消融實驗，研究框架中各個結(jié)構(gòu)的作用，可以看到，MPNN 和位置/結(jié)構(gòu)編碼模塊對 Transformer 的效果均有提升作用。

總結(jié)

兩篇文章都有一個共同特點，就是采用了 GNN + Transformer 混合的模型設(shè)計，結(jié)合二者的優(yōu)勢，以不同的方式對兩種模型進行融合，GNN 學(xué)習(xí)到圖結(jié)構(gòu)信息，然后在 Transformer 的計算中起到提供結(jié)構(gòu)信息的作用。在未來的研究工作中，如何設(shè)計更加合理的模型，也是一個值得探討的問題。

審核編輯 ：李倩