0
| 本文作者： AI研習(xí)社-譯站 | 2020-09-15 10:31 |
字幕組雙語原文：Twitter團隊最新研究:快速高效的可擴展圖神經(jīng)網(wǎng)絡(luò)SIGN
英語原文：Simple scalable graph neural networks
前言：迄今為止，阻礙圖神經(jīng)網(wǎng)絡(luò)在行業(yè)應(yīng)用中被廣泛采用的挑戰(zhàn)之一是難以將其縮放到大型圖（例如Twitter跟隨圖）。 節(jié)點之間的相互依賴性使損失函數(shù)分解成單個節(jié)點的貢獻具有挑戰(zhàn)性。 在這篇文章中，我們描述了Twitter開發(fā)的一種簡單的圖神經(jīng)網(wǎng)絡(luò)架構(gòu)，該架構(gòu)可以處理大量的圖。
本文由Fabrizo Frasca 和 Emanuele Rossi 合著。
圖神經(jīng)網(wǎng)絡(luò)（GNN）是一種新型的ML模型，專門用于處理圖數(shù)據(jù)。在不同領(lǐng)域，GNN可成功實現(xiàn)領(lǐng)域內(nèi)關(guān)系及相互作用建模，如社會科學(xué)，計算機圖形與視覺，粒子物理學(xué)，化學(xué)和醫(yī)學(xué)。但是令人失望的是，對GNN模型的研究和應(yīng)用都是在規(guī)模較小的圖上進行的(比如被廣泛使用的引用網(wǎng)絡(luò)數(shù)據(jù)集-Cora，該數(shù)據(jù)集僅僅包含約5K節(jié)點[1])，大規(guī)模圖數(shù)據(jù)的研究卻很少受到關(guān)注。與之矛盾的是，在實際工業(yè)場景中，需要處理的確實超大規(guī)模的圖，例如包含數(shù)億節(jié)點和數(shù)十億邊的Twitter或Facebook社交網(wǎng)絡(luò)，先前的研究工作很難用于這些圖的處理分析。
簡單來說，圖神經(jīng)網(wǎng)絡(luò)的核心就是鄰域聚合，即整合鄰居節(jié)點的特征。將特征維數(shù)為d的n個節(jié)點表示為 n×d 的矩陣X，經(jīng)典的GCN模型[2]就是通過整合鄰居節(jié)點的特征實現(xiàn)某一節(jié)點的表示，這就是圖神經(jīng)網(wǎng)絡(luò)中的卷積操作：
Y = ReLU(AXW)
其中，W是所有節(jié)點共享的可學(xué)習(xí)參數(shù)矩陣，A是線性擴散算子，等于鄰域中特征的加權(quán)平均值[3]。與傳統(tǒng)CNN類似，可以將這種模式依序排列實現(xiàn)多層網(wǎng)絡(luò)。圖神經(jīng)網(wǎng)絡(luò)可用于節(jié)點預(yù)測（如檢測社交網(wǎng)絡(luò)中的惡意用戶），邊預(yù)測（如推薦系統(tǒng)中的鏈接預(yù)測），整個圖的預(yù)測（如預(yù)測分子圖的化學(xué)性質(zhì)）。另外，通過以下形式構(gòu)架一個兩層的GCN，可實現(xiàn)節(jié)點分類任務(wù)：
Y = softmax(A ReLU(AXW)W’)
那么，將圖神經(jīng)網(wǎng)絡(luò)擴展到大規(guī)模圖難在哪里呢？在上述節(jié)點預(yù)測問題中，節(jié)點作為GNN的訓(xùn)練樣本。傳統(tǒng)的機器學(xué)習(xí)通常假設(shè)樣本是服從某一分布的、相互獨立的。這樣，可以根據(jù)單個樣本分解損失函數(shù)，并采用隨機優(yōu)化技術(shù)批次處理訓(xùn)練數(shù)據(jù)（mini-batches）?，F(xiàn)今幾乎每個深度神經(jīng)網(wǎng)絡(luò)都是用mini-batches批次訓(xùn)練。
然而在圖中，節(jié)點通過邊相互連接，這使得訓(xùn)練集中的樣本并不完全獨立。此外，由于節(jié)點間的依賴性，采樣可能會引入偏差（例如，可能會使某些節(jié)點或邊被采樣的概率更大），需要對此“副作用”進行處理。還有很重要的一點，采樣過程中必須保證采樣子圖的有效結(jié)構(gòu)，確保GNN可以處理。
但之前的許多研究工作忽略了這些問題，如GCN、ChebNet[2]、MoNet[4]和GAT[5]等直接使用全批次數(shù)據(jù)進行梯度下降，這就導(dǎo)致必須將圖的整個鄰接矩陣和節(jié)點特征保存在內(nèi)存中。即使中等大小的圖，L層GCN模型的時間復(fù)雜度為?（Lnd2）和空間復(fù)雜度為?（Lnd +Ld2）[7]，更不必說大規(guī)模圖了。
Will Hamilton及其合作者提出GraphSAGE [8]，這是第一次考慮到GNN的擴展性問題。GraphSAGE結(jié)合鄰域采樣以及小批次訓(xùn)練在大型圖上訓(xùn)練GNN（首字母縮寫SAGE即代表“樣本和集合”）。論文的主要思想是，為了在L層GCN中計算單個節(jié)點的訓(xùn)練損失，可以只考慮該節(jié)點的L跳鄰居，因為更遠的節(jié)點不參與計算。但問題是，符合“小世界”特征的圖（如社交網(wǎng)絡(luò)）的某些節(jié)點的2跳鄰域可能已經(jīng)包含數(shù)百萬個節(jié)點，這樣巨大數(shù)據(jù)無法存儲在內(nèi)存中[9]。GraphSAGE通過對L跳內(nèi)的鄰居采樣來解決該問題：對于初始節(jié)點，在其1跳鄰居節(jié)點中采樣k個節(jié)點，然后再對采樣節(jié)點進行類似操作，直至采樣到L跳的鄰域節(jié)點。通過這樣的方式，每個節(jié)點有?（k?）個節(jié)點，這些節(jié)點分布在L跳鄰域內(nèi)。如果用b個訓(xùn)練節(jié)點批次訓(xùn)練，由于每個訓(xùn)練節(jié)點都有自己獨立的L跳鄰域，得到與圖大小n無關(guān)的空間復(fù)雜度為?（bk?），計算時間復(fù)雜度則為?（bLd2k?）。
GraphSAGE的鄰域采樣過程。對圖中b個節(jié)點批量采樣進行訓(xùn)練（圖示中b = 2，見淺黃色節(jié)點和紅色節(jié)點）；右側(cè)圖表示在初始節(jié)點的2跳領(lǐng)域內(nèi)的k 節(jié)點采樣過程（k=2，按圖顯示應(yīng)該是k=5），這些采樣節(jié)點用于GNN的嵌入訓(xùn)練，避免了初始節(jié)點領(lǐng)域過大的消耗。
GraphSAGE的一個顯著缺點是：某些節(jié)點會被采樣多次，從而引入大量的冗余計算。例如，在上圖中，深綠色節(jié)點在兩個訓(xùn)練節(jié)點的單跳鄰域中均有出現(xiàn)，這就導(dǎo)致批次處理時對其進行兩次嵌入。隨著批量大小b和樣本數(shù)量k的增加，冗余計算量也隨之增加。此外，盡管訓(xùn)練每個batch時內(nèi)存中有?（bk?）個節(jié)點，但僅對其中的b個節(jié)點計算了損失，從某種意義上講，其他節(jié)點沒有被充分利用。
針對這樣的問題，后續(xù)工作重點關(guān)注對小批次數(shù)據(jù)的采樣，以消除GraphSAGE的冗余計算，提高批次訓(xùn)練效率。典型的工作包括ClusterGCN [11]和GraphSAINT [12]，采用了圖采樣的方法，這與GraphSAGE的鄰域抽樣正好相反。具體而言，在圖采樣方法中，每批次訓(xùn)練數(shù)據(jù)會對原始圖的一個子圖進行采樣，然后在整個子圖上運行類似GCN的模型。該方法的關(guān)鍵在于這些子圖保留大多數(shù)原始邊信息，并且保留了拓撲結(jié)構(gòu)。
ClusterGCN通過對圖進行聚類實現(xiàn)此目的，然后，批次訓(xùn)練過程中，模型都在一個集群上訓(xùn)練。 這就保證了每批次中的節(jié)點的緊密連接。
GraphSAINT則是提出了一種通用概率圖采樣器，通過采樣原始圖的子圖來構(gòu)造訓(xùn)練批次。進一步，可以根據(jù)任務(wù)設(shè)計不同的圖形采樣器，例如通過隨機游走來計算節(jié)點的重要性并將其用作采樣的概率分布，從而執(zhí)行統(tǒng)一節(jié)點采樣、邊采樣或“重要性采樣”。
另外，在訓(xùn)練過程中，采樣還起到某種邊隨機失活的作用（edge-wise dropout），從而正則化模型，提高模型性能[13]。但是，在推理階段則要求看到所有邊，這種情況下不需要失活。另外，圖采樣還可以避免鄰域的指數(shù)擴展而導(dǎo)致的“過度擠壓”現(xiàn)象，突破過去的研究瓶頸[14]。
在我們與Ben Chamberlain，Davide Eynard和Federico Monti發(fā)表的新論文中[15]，我們針對節(jié)點分類問題，探究了設(shè)計簡潔、無采樣架構(gòu)的可能性。你也許會問，既然采樣方法有上文提到的諸多優(yōu)點，為什么要研究無采樣的方法。有以下兩個原因：第一，節(jié)點分類問題的具體實例之間存在很大差異，據(jù)我們所知，除了降低復(fù)雜度外，目前為止沒有任何研究表明采樣策略有其他積極的意義；其次，采樣會帶來額外的復(fù)雜性。因此，我們認為研究簡單、強大、無采樣、可擴展的基準架構(gòu)是有必要的。
我們的研究基于以下發(fā)現(xiàn)。首先，在許多情況下，簡單的固定聚合器（如GCN）通常都優(yōu)于GAT或MPNN等復(fù)雜模型[16]；其次，雖然深度學(xué)習(xí)的成功取決于更深的層，但是在圖深度學(xué)習(xí)中，是否需要無腦增加深度仍然是一個懸而未決的問題。特別是Wu等人[17]認為單個多跳擴散層的GCN模型不遜于具有多個層的模型。
通過在單個卷積層中組合不同的、確定的鄰域聚合器，可以在不依靠圖采樣的情況下獲得可擴展性良好的模型[18]。換句話說，所有與圖相關(guān)的操作都在模型的第一層中，因此可以預(yù)計算；然后將預(yù)先聚合的信息作為其余部分的輸入。由于不再受鄰域聚合影響，因此可以使用多層感知器（MLP）。值得注意的是，通過采用若干專門的、更復(fù)雜的擴散算子，即使淺層卷積也可以實現(xiàn)圖采樣的表達能力。例如，可以設(shè)置擴散算子為local substructure counting [19]或graph motifs[20]。
SIGN結(jié)構(gòu)包括一個具有多個線性擴散算子的類GCN層，根據(jù)這些擴散算子作用于多跳鄰域，然后在節(jié)點層次上應(yīng)用MLP。通過對擴散特征（紅色標記）進行預(yù)計算可極大提升模型效率。
我們將上述可擴展模型稱為Scalable Inception-like Graph Network（SIGN），通過下式可直接用于節(jié)點分類：
Y = softmax(ReLU(XW? | A?XW? | A?XW? | … | A?XW?) W’)
其中，A?是線性擴散矩陣（如歸一化的鄰接矩陣或其冪，基序矩陣等），W?和W'是可學(xué)習(xí)的參數(shù)。如上圖所示，通過附加的節(jié)點層可以加深網(wǎng)絡(luò)：
Y = softmax(ReLU(…ReLU(XW? | A?XW? | … | A?XW?) W’)… W’’)
最后，當(dāng)對同一個擴散算子采用不同的冪（如A?=B1, A?=B2）時，相當(dāng)于從節(jié)點更多跳范圍內(nèi)聚合信息，這樣類似于在一層網(wǎng)絡(luò)中具有不同接收場的卷積濾波器。類比經(jīng)典CNN中的inception模塊[21]可以更好的理解我們的模型。
如上所述，等式中的矩陣乘積A?X，…，A?X不依賴于模型參數(shù)，因此可以預(yù)計算。特別是對于超大規(guī)模的圖，可以使用分布式計算結(jié)構(gòu)（如Apache Spark）高效執(zhí)行該計算。通過這樣的方式，整個模型的計算復(fù)雜度僅僅取決于MLP。此外，將擴散轉(zhuǎn)移到預(yù)計算步驟，可以聚集所有鄰居的信息，避免采樣可能導(dǎo)致的信息丟失偏差[22]。
可擴展性和高效率是的優(yōu)勢，由于可以使用小批量梯度下降法進行訓(xùn)練，SIGN可擴展性良好，效率高。試驗表明我們的模型在推理時比ClusterGCN和GraphSAINT快兩個數(shù)量級，同時在確保精度與最新的GraphSAINT一致的情況下，訓(xùn)練速度也明顯更快。
不同方法在OGBN-Products數(shù)據(jù)集上的收斂情況。與GraphSaint和ClusterGCN相比，SIGN收斂速度更快，同時具有更高的F1得分。
不同方法在OGBN-Products數(shù)據(jù)集上的預(yù)處理、訓(xùn)練和推理時間（以秒為單位）。相比其他方法，盡管SIGN的預(yù)處理速度較慢，但其在訓(xùn)練中的速度更快，在推理時的速度甚至快了將近兩個數(shù)量級。
此外，我們的模型支持任何擴散算子。不同類型的圖形可能需要不同的擴散算子，我們發(fā)現(xiàn)三角形基序這樣的算子很適合某些任務(wù)。
SIGN和其他可擴展方法在不同數(shù)據(jù)集上進行節(jié)點分類任務(wù)的表現(xiàn)?；谌切位虻臄U散算子在Flickr上獲得明顯的性能提升，對PPI和Yelp數(shù)據(jù)集也有改進。
盡管僅具有單個圖卷積層以及線性擴散算子存在局限性，在實際應(yīng)用中SIGN表現(xiàn)出色，達到甚至超過同等或更復(fù)雜模型的結(jié)果。鑒于其高效性和簡便性，SIGN可作為基線圖學(xué)習(xí)方法應(yīng)用于不同大規(guī)模圖數(shù)據(jù)。更重要的是，這種簡單模型的成功引起我們的思考：是否真的需要深度圖神經(jīng)網(wǎng)絡(luò)？我們發(fā)現(xiàn)在社交網(wǎng)絡(luò)和“小世界”圖學(xué)習(xí)的許多問題中，應(yīng)該使用更豐富的本地結(jié)構(gòu)，而不是野蠻的堆積深度架構(gòu)。不過值得注意的是，由于計算迅速。可用簡單結(jié)構(gòu)抽取復(fù)雜特征，傳統(tǒng)的CNN架構(gòu)越堆越深，用更小的濾波器組成更深的網(wǎng)絡(luò)。我們不確定相同的方法是否適用于圖，因為圖的組成要復(fù)雜得多，無論網(wǎng)絡(luò)多深，某些結(jié)構(gòu)都無法通過消息傳遞來計算。不過可以肯定的是，究竟將來會是哪個方向都需要更多、更復(fù)雜的實驗來進行檢驗。
雷鋒字幕組是一個由AI愛好者組成的翻譯團隊，匯聚五五多位志愿者的力量，分享最新的海外AI資訊，交流關(guān)于人工智能技術(shù)領(lǐng)域的行業(yè)轉(zhuǎn)變與技術(shù)創(chuàng)新的見解。
團隊成員有大數(shù)據(jù)專家，算法工程師，圖像處理工程師，產(chǎn)品經(jīng)理，產(chǎn)品運營，IT咨詢?nèi)耍谛熒?；志愿者們來自IBM，AVL，Adobe，阿里，百度等知名企業(yè)，北大，清華，港大，中科院，南卡羅萊納大學(xué)，早稻田大學(xué)等海內(nèi)外高校研究所。
如果，你也是位熱愛分享的AI愛好者。歡迎與雷鋒字幕組一起，學(xué)習(xí)新知，分享成長。
雷鋒網(wǎng)雷鋒網(wǎng)
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
