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

SAT

論文標(biāo)題：Structure-Aware Transformer for Graph Representation Learning收錄會(huì)議：ICML 2022

論文鏈接：

https://arxiv.org/abs/2202.03036

代碼鏈接：

https://github.com/BorgwardtLab/SAT

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

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

1.1 方法

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

Structure-Aware Self-Attention

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

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

是定義在節(jié)點(diǎn)特征上的可訓(xùn)練指數(shù)核函數(shù)，這就帶來(lái)了一個(gè)問(wèn)題：當(dāng)節(jié)點(diǎn)特征相似時(shí)，結(jié)構(gòu)信息無(wú)法被識(shí)別并編碼。為了同時(shí)考慮節(jié)點(diǎn)之間的結(jié)構(gòu)相似性，我們考慮了一個(gè)更一般化的核函數(shù)，額外考慮了每個(gè)節(jié)點(diǎn)周?chē)木植孔咏Y(jié)構(gòu)。通過(guò)引入以每個(gè)節(jié)點(diǎn)為中心的一組子圖，定義結(jié)構(gòu)感知注意力如下：

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

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

1.2 實(shí)驗(yàn)

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

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

GraphGPS

論文標(biāo)題：Recipe for a General, Powerful, Scalable Graph Transformer收錄會(huì)議：NeurIPS 2022

論文鏈接：

https://arxiv.org/abs/2205.12454

代碼鏈接：

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

2.1 方法

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

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

2.2 實(shí)驗(yàn)

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

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

總結(jié)

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

審核編輯 ：李倩