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