<dfn id="yhprb"><s id="yhprb"></s></dfn><dfn id="yhprb"><delect id="yhprb"></delect></dfn><dfn id="yhprb"></dfn><dfn id="yhprb"><delect id="yhprb"></delect></dfn><dfn id="yhprb"></dfn><dfn id="yhprb"><s id="yhprb"><strike id="yhprb"></strike></s></dfn><small id="yhprb"></small><dfn id="yhprb"></dfn><small id="yhprb"><delect id="yhprb"></delect></small><small id="yhprb"></small><small id="yhprb"></small> <delect id="yhprb"><strike id="yhprb"></strike></delect><dfn id="yhprb"></dfn><dfn id="yhprb"></dfn><s id="yhprb"><noframes id="yhprb"><small id="yhprb"><dfn id="yhprb"></dfn></small><dfn id="yhprb"><delect id="yhprb"></delect></dfn><small id="yhprb"></small><dfn id="yhprb"><delect id="yhprb"></delect></dfn><dfn id="yhprb"><s id="yhprb"></s></dfn> <small id="yhprb"></small><delect id="yhprb"><strike id="yhprb"></strike></delect><dfn id="yhprb"><s id="yhprb"></s></dfn><dfn id="yhprb"></dfn><dfn id="yhprb"><s id="yhprb"></s></dfn><dfn id="yhprb"><s id="yhprb"><strike id="yhprb"></strike></s></dfn><dfn id="yhprb"><s id="yhprb"></s></dfn>
"); //-->

博客專(zhuān)欄

EEPW首頁(yè) > 博客 > 比9種SOTA GNN更強!谷歌大腦提出全新圖神經(jīng)網(wǎng)絡(luò )GKATs

比9種SOTA GNN更強!谷歌大腦提出全新圖神經(jīng)網(wǎng)絡(luò )GKATs

發(fā)布人:數據派THU 時(shí)間:2021-08-07 來(lái)源:工程師 發(fā)布文章

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

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

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

于是乎,人們對專(zhuān)門(mén)用于處理圖結構數據的圖神經(jīng)網(wǎng)絡(luò )(GNN)產(chǎn)生了極大的興趣。

盡管現代GNN在理解圖形數據方面取得了巨大的成功,但在有效處理圖形數據方面仍然存在一些挑戰。

例如,當所考慮的圖較大時(shí),計算復雜性就成為一個(gè)問(wèn)題。

相反,在空間域工作的算法避免了昂貴的頻譜計算,但為了模擬較長(cháng)距離的依賴(lài)關(guān)系,不得不依靠深度GNN架構來(lái)實(shí)現信號從遠處節點(diǎn)的傳播,因為單個(gè)層只模擬局部的相互作用。

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

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

1.jpg

該團隊證明GKAT比SOTA GNN具有更強的表達能力,同時(shí)還減少了計算負擔。

全新GNN,降低計算復雜度

「是否有可能設計具有密集單個(gè)層的 GNN,顯式建模圖中更長(cháng)范圍的節點(diǎn)到節點(diǎn)關(guān)系,從而實(shí)現更淺的架構,同時(shí)擴展更大的(不一定是稀疏的)圖?」

2.jpg

GKATs中可分解的長(cháng)注意力

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

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

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

3.png

完整的 GKAT 架構由幾個(gè)塊組成,每個(gè)塊由注意力層和標準 MLP 層構建而成。

值得注意的是,注意層與輸入圖的節點(diǎn)數成線(xiàn)性關(guān)系而不是二次方,因此與其常規的圖注意力對應物相比降低了計算復雜度。

優(yōu)于9種SOTA GNN

Erd?s-Rényi隨機圖:

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

對于每個(gè)數據集,構建S個(gè)正例和S個(gè)負例,其中S=2048。

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

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

每個(gè)模體的數據集被隨機分成75%的訓練集和25%的驗證集。

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

對于模型來(lái)說(shuō),作者選擇使用雙層架構,并通過(guò)調整使所有模型的規模相當。

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

在SGC中,將每個(gè)隱層與2個(gè)多項式局部過(guò)濾器結合。

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

在GKAT中,使用長(cháng)度為τ=3的隨機游走。

4.png

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

檢測長(cháng)誘導循環(huán)和深度與密度注意力測試:

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

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

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

5.png

具有密集注意力的淺層神經(jīng)網(wǎng)絡(luò )能夠對依靠稀疏層的深層網(wǎng)絡(luò )進(jìn)行建模,然而代價(jià)是每層的額外計算成本。

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

對于GKAT,在第一層應用8個(gè)頭,在第二層應用1個(gè)頭,每個(gè)頭的尺寸為d=4。

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

6.png

GKAT不同長(cháng)度的隨機游走結果

7.png

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

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

此外,GKAT在趨勢上等同于四層GAT和SGC,但它在訓練和運行推理方面更快。

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

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

對于生物信息學(xué)數據集,使用分子指紋(Molecular Fingerprint, MF)方法作為基線(xiàn)。 

對于社交網(wǎng)絡(luò )數據集,使用深度多重集合(DeepMultisets, DM)方法作為基線(xiàn)。

在GKAT配置方面,首先應用了一個(gè)有k個(gè)頭的注意層(一個(gè)有待調整的超參數)。

然后是另一個(gè)有一個(gè)頭的注意層,以聚合圖上的拓撲信息。

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

每個(gè)GKAT層中的隨機游走長(cháng)度τ滿(mǎn)足:τ≤4,并且取決于所評估的數據集。

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

8.png

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

9.png

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

其中,平均圖徑(每對節點(diǎn)的最長(cháng)最短路徑的平均值)有助于校準游走長(cháng)度,并在實(shí)驗中選擇節點(diǎn)數與平均節點(diǎn)數最相似的圖。

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

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

10.png

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

11.png

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

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

GKAT的空間和時(shí)間復雜度增益:

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

可以看到,相應的GKAT和GKAT+模型的準確率差距很小。

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

12.png

GKAT+在速度和空間復雜度方面的提升

第一行:通過(guò)graphot對圖形進(jìn)行內存壓縮(越低越好)。

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

第四行:與不應用可分解注意力機制的GKAT相比,準確率的下降。

13.png

訓練不同網(wǎng)絡(luò )的時(shí)間,均為雙層結構

此外,在達到特定精度水平所需的時(shí)間方面,常規的GKAT也比相應的模型(GCN、GAT和SGC)快。 

總結

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

利用了圖核方法和可擴展注意力

在處理圖數據方面更具表現力

具有低時(shí)間復雜性和內存占用

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

參考資料:

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

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



關(guān)鍵詞: AI

相關(guān)推薦

技術(shù)專(zhuān)區

關(guān)閉
国产精品自在自线亚洲|国产精品无圣光一区二区|国产日产欧洲无码视频|久久久一本精品99久久K精品66|欧美人与动牲交片免费播放
<dfn id="yhprb"><s id="yhprb"></s></dfn><dfn id="yhprb"><delect id="yhprb"></delect></dfn><dfn id="yhprb"></dfn><dfn id="yhprb"><delect id="yhprb"></delect></dfn><dfn id="yhprb"></dfn><dfn id="yhprb"><s id="yhprb"><strike id="yhprb"></strike></s></dfn><small id="yhprb"></small><dfn id="yhprb"></dfn><small id="yhprb"><delect id="yhprb"></delect></small><small id="yhprb"></small><small id="yhprb"></small> <delect id="yhprb"><strike id="yhprb"></strike></delect><dfn id="yhprb"></dfn><dfn id="yhprb"></dfn><s id="yhprb"><noframes id="yhprb"><small id="yhprb"><dfn id="yhprb"></dfn></small><dfn id="yhprb"><delect id="yhprb"></delect></dfn><small id="yhprb"></small><dfn id="yhprb"><delect id="yhprb"></delect></dfn><dfn id="yhprb"><s id="yhprb"></s></dfn> <small id="yhprb"></small><delect id="yhprb"><strike id="yhprb"></strike></delect><dfn id="yhprb"><s id="yhprb"></s></dfn><dfn id="yhprb"></dfn><dfn id="yhprb"><s id="yhprb"></s></dfn><dfn id="yhprb"><s id="yhprb"><strike id="yhprb"></strike></s></dfn><dfn id="yhprb"><s id="yhprb"></s></dfn>