來(lái)源：Google、新智元

[ 導(dǎo)讀 ]GNN雖牛，但也避免不了計(jì)算復(fù)雜性等問(wèn)題。為此，谷歌大腦與牛津大學(xué)、哥倫比亞大學(xué)的研究人員提出了一種全新的GNN：GKATs。不僅解決了計(jì)算復(fù)雜度問(wèn)題，還被證明優(yōu)于9種SOTA GNN。

從社交網(wǎng)絡(luò)到生物信息學(xué)，再到機(jī)器人學(xué)中的導(dǎo)航和規(guī)劃問(wèn)題，圖在各種現(xiàn)實(shí)世界的數(shù)據(jù)集中普遍存在。

于是乎，人們對(duì)專門(mén)用于處理圖結(jié)構(gòu)數(shù)據(jù)的圖神經(jīng)網(wǎng)絡(luò)（GNN）產(chǎn)生了極大的興趣。

盡管現(xiàn)代GNN在理解圖形數(shù)據(jù)方面取得了巨大的成功，但在有效處理圖形數(shù)據(jù)方面仍然存在一些挑戰(zhàn)。

例如，當(dāng)所考慮的圖較大時(shí)，計(jì)算復(fù)雜性就成為一個(gè)問(wèn)題。

相反，在空間域工作的算法避免了昂貴的頻譜計(jì)算，但為了模擬較長(zhǎng)距離的依賴關(guān)系，不得不依靠深度GNN架構(gòu)來(lái)實(shí)現(xiàn)信號(hào)從遠(yuǎn)處節(jié)點(diǎn)的傳播，因?yàn)閱蝹€(gè)層只模擬局部的相互作用。

為解決這些問(wèn)題，谷歌大腦、哥倫比亞大學(xué)和牛津大學(xué)的研究團(tuán)隊(duì)提出了一類(lèi)新的圖神經(jīng)網(wǎng)絡(luò)：Graph Kernel Attention Transformers（GKATs）。

其結(jié)合了圖核、基于注意力的網(wǎng)絡(luò)和結(jié)構(gòu)先驗(yàn)，以及最近的通過(guò)低秩分解技術(shù)應(yīng)用小內(nèi)存占用隱式注意方法的Transformer架構(gòu)。

該團(tuán)隊(duì)證明GKAT比SOTA GNN具有更強(qiáng)的表達(dá)能力，同時(shí)還減少了計(jì)算負(fù)擔(dān)。

全新GNN，降低計(jì)算復(fù)雜度

「是否有可能設(shè)計(jì)具有密集單個(gè)層的 GNN，顯式建模圖中更長(zhǎng)范圍的節(jié)點(diǎn)到節(jié)點(diǎn)關(guān)系，從而實(shí)現(xiàn)更淺的架構(gòu)，同時(shí)擴(kuò)展更大的（不一定是稀疏的）圖？」

GKATs中可分解的長(zhǎng)注意力

GKAT將每一層內(nèi)的圖注意力建模為節(jié)點(diǎn)特征向量的核矩陣和圖核矩陣的Hadamard乘積。

這使GKAT能夠利用計(jì)算效率高的隱式注意機(jī)制，并在單層內(nèi)對(duì)更遠(yuǎn)距離的依賴項(xiàng)進(jìn)行建模，從而將其表達(dá)能力提升到超越傳統(tǒng)GNN的水平。

為了在圖節(jié)點(diǎn)上定義可實(shí)現(xiàn)高效映射的表達(dá)內(nèi)核，研究人員采用了一種新穎的隨機(jī)游走圖節(jié)點(diǎn)內(nèi)核 (RWGNKs) 方法，其中兩個(gè)節(jié)點(diǎn)的值作為兩個(gè)頻率向量的點(diǎn)積給出，這些向量記錄了圖節(jié)點(diǎn)中的隨機(jī)游走。

完整的 GKAT 架構(gòu)由幾個(gè)塊組成，每個(gè)塊由注意力層和標(biāo)準(zhǔn) MLP 層構(gòu)建而成。

值得注意的是，注意層與輸入圖的節(jié)點(diǎn)數(shù)成線性關(guān)系而不是二次方，因此與其常規(guī)的圖注意力對(duì)應(yīng)物相比降低了計(jì)算復(fù)雜度。

優(yōu)于9種SOTA GNN

Erd?s-Rényi隨機(jī)圖：

作者使用了五個(gè)二元分類(lèi)數(shù)據(jù)集，包括與主題相連的隨機(jī)ER圖（正例）或與模體具有相同平均度的其他較小ER圖（負(fù)面例子）。

對(duì)于每個(gè)數(shù)據(jù)集，構(gòu)建S個(gè)正例和S個(gè)負(fù)例，其中S=2048。

作者對(duì)GKAT、圖卷積網(wǎng)絡(luò)（GCNs）、譜圖卷積網(wǎng)絡(luò)（SGCs）和圖注意網(wǎng)絡(luò)（GATs）進(jìn)行了測(cè)試。

每個(gè)頂點(diǎn)的特征向量長(zhǎng)度為l=5，并包含其相鄰的頂序度數(shù)l（如果少于l，則填充0）。

每個(gè)模體的數(shù)據(jù)集被隨機(jī)分成75%的訓(xùn)練集和25%的驗(yàn)證集。

同時(shí)，采用學(xué)習(xí)率為η=0.001的Adam優(yōu)化器，如果驗(yàn)證損失和驗(yàn)證準(zhǔn)確率在c=80個(gè)連續(xù)的epoch中都沒(méi)有改善，則提前停止訓(xùn)練。

對(duì)于模型來(lái)說(shuō)，作者選擇使用雙層架構(gòu)，并通過(guò)調(diào)整使所有模型的規(guī)模相當(dāng)。

在GCN和SGC中，隱層中有h=32個(gè)節(jié)點(diǎn)。

在SGC中，將每個(gè)隱層與2個(gè)多項(xiàng)式局部過(guò)濾器結(jié)合。

在GAT和GKAT中，使用2個(gè)注意頭，隱層中有h=9個(gè)節(jié)點(diǎn)。

在GKAT中，使用長(zhǎng)度為τ=3的隨機(jī)游走。

可以看出，GKAT在所有的模體上都優(yōu)于其他方法。

檢測(cè)長(zhǎng)誘導(dǎo)循環(huán)和深度與密度注意力測(cè)試：

算法需要決定在給定的常數(shù)T下，圖形是否包含一個(gè)長(zhǎng)度大于T的誘導(dǎo)循環(huán)。

因此，模體本身成為一個(gè)全局屬性，不能只通過(guò)探索一個(gè)節(jié)點(diǎn)的近鄰來(lái)檢測(cè)。

在這個(gè)實(shí)驗(yàn)中，還要關(guān)注「深度與密度」的權(quán)衡。

具有密集注意力的淺層神經(jīng)網(wǎng)絡(luò)能夠?qū)σ揽肯∈鑼拥纳顚泳W(wǎng)絡(luò)進(jìn)行建模，然而代價(jià)是每層的額外計(jì)算成本。

在實(shí)驗(yàn)中需要控制GCN、GAT和SGC的隱層的節(jié)點(diǎn)數(shù)，以及GAT的每個(gè)注意頭的數(shù)量，使它們的可訓(xùn)練參數(shù)總量與雙層GKAT相當(dāng)。

對(duì)于GKAT，在第一層應(yīng)用8個(gè)頭，在第二層應(yīng)用1個(gè)頭，每個(gè)頭的尺寸為d=4。

最后一層是全連接層，輸出維數(shù)為o=2，用于二進(jìn)制分類(lèi)，并采用τ=6的隨機(jī)游走長(zhǎng)度。

GKAT不同長(zhǎng)度的隨機(jī)游走結(jié)果

雙層GKAT與不同隱層數(shù)量（2-6）的GCN、GAT和SGC的比較

可以看到，更淺的GKAT幾乎擊敗了所有的GCN變體以及小于4層的GATs和SGCs。

此外，GKAT在趨勢(shì)上等同于四層GAT和SGC，但它在訓(xùn)練和運(yùn)行推理方面更快。

生物信息學(xué)任務(wù)和社交網(wǎng)絡(luò)數(shù)據(jù)測(cè)試：

作者將GKAT與其他的SOTA GNN方法進(jìn)行比較，其中包括：DCGNN, DiffPool, ECC, GraphSAGE和RWNN 。

對(duì)于生物信息學(xué)數(shù)據(jù)集，使用分子指紋（Molecular Fingerprint, MF）方法作為基線。 

對(duì)于社交網(wǎng)絡(luò)數(shù)據(jù)集，使用深度多重集合（DeepMultisets, DM）方法作為基線。

在GKAT配置方面，首先應(yīng)用了一個(gè)有k個(gè)頭的注意層（一個(gè)有待調(diào)整的超參數(shù)）。

然后是另一個(gè)有一個(gè)頭的注意層，以聚合圖上的拓?fù)湫畔ⅰ?/p>

接下來(lái)，應(yīng)用MF方法或DM方法來(lái)進(jìn)一步處理聚合的信息。

每個(gè)GKAT層中的隨機(jī)游走長(zhǎng)度τ滿足：τ≤4，并且取決于所評(píng)估的數(shù)據(jù)集。

長(zhǎng)的隨機(jī)游走原則上可以捕獲更多的信息，但代價(jià)是要增加非相關(guān)節(jié)點(diǎn)。

生物信息學(xué)數(shù)據(jù)集

社交網(wǎng)絡(luò)數(shù)據(jù)集

其中，平均圖徑（每對(duì)節(jié)點(diǎn)的最長(zhǎng)最短路徑的平均值）有助于校準(zhǔn)游走長(zhǎng)度，并在實(shí)驗(yàn)中選擇節(jié)點(diǎn)數(shù)與平均節(jié)點(diǎn)數(shù)最相似的圖。

作者在9個(gè)標(biāo)準(zhǔn)和公開(kāi)的生物信息學(xué)和社交網(wǎng)絡(luò)數(shù)據(jù)集上測(cè)試了GKAT的圖分類(lèi)任務(wù)。

對(duì)于每個(gè)數(shù)據(jù)集，表現(xiàn)最好的方法被加粗顯示，第二的由下劃線表示。

GKAT在生物信息學(xué)數(shù)據(jù)集的四個(gè)任務(wù)中有三個(gè)結(jié)果最好

GKAT在社交網(wǎng)絡(luò)數(shù)據(jù)集的五個(gè)任務(wù)中有四個(gè)位居前兩位

值得注意的是，除了一個(gè)生物信息學(xué)數(shù)據(jù)集之外，GKAT是唯一一個(gè)在所有的生物信息學(xué)數(shù)據(jù)集上持續(xù)優(yōu)于基線的GNN方法。

GKAT的空間和時(shí)間復(fù)雜度增益：

作者對(duì)比了加入可分解注意力機(jī)制的GKAT（GKAT+）與GAT在速度和記憶上的改進(jìn)，以及與常規(guī)的GKAT在準(zhǔn)確性上的損失。

可以看到，相應(yīng)的GKAT和GKAT+模型的準(zhǔn)確率差距很小。

但是與GAT相比，GKAT+在每個(gè)注意層中產(chǎn)生了一致的速度和記憶增益，特別是對(duì)于那些來(lái)自Citeseer和Pubmed的非常大的圖形來(lái)說(shuō)，這種增益是非?？捎^的。

GKAT+在速度和空間復(fù)雜度方面的提升

第一行：通過(guò)graphot對(duì)圖形進(jìn)行內(nèi)存壓縮（越低越好）。

第二行和第三行：與GAT相比，每一個(gè)注意力層的訓(xùn)練和推理速度分別提高。

第四行：與不應(yīng)用可分解注意力機(jī)制的GKAT相比，準(zhǔn)確率的下降。

訓(xùn)練不同網(wǎng)絡(luò)的時(shí)間，均為雙層結(jié)構(gòu)

此外，在達(dá)到特定精度水平所需的時(shí)間方面，常規(guī)的GKAT也比相應(yīng)的模型（GCN、GAT和SGC）快。 

總結(jié)

作者提出了一個(gè)全新的基于注意力的圖神經(jīng)網(wǎng)：Graph Kernel Attention Transformers（GKATs）：

利用了圖核方法和可擴(kuò)展注意力

在處理圖數(shù)據(jù)方面更具表現(xiàn)力

具有低時(shí)間復(fù)雜性和內(nèi)存占用

在廣泛的任務(wù)上優(yōu)于其他SOTA模型

參考資料：

https://arxiv.org/pdf/2107.07999.pdf