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