使用這些基本 REST API 最佳實踐構建出色的 API
表1列出了本文相關綜述。綜述[29-32]關注圖神經網絡模型的全圖訓練模式及其應用。然而，當節點或邊數量龐大時，訓練過程受限于單塊GPU內存。為解決此問題，采樣算法支持圖神經網絡模型從全圖訓練轉向分批訓練，并應用于大規模數據。圖神經網絡編程框架結合深度學習框架和圖結構特征，提高存儲利用率和計算效率，促進大規模數據應用。綜述[33-34]主要總結圖神經網絡編程框架進展。綜述[36-38]關注分布式平臺，總結分析分布式GNN在算法模型、軟件框架和硬件平臺等方面的進展。
本文針對大規模圖神經網絡，從算法模型和框架優化兩方面進行調研、總結和分析。首先介紹GNN基礎知識和典型算法，接著總結不同粒度采樣策略的圖神經網絡模型，以及主流加速框架及相關技術。為后續圖神經網絡在大規模數據應用中框架-算法的協同優化提供思路。
本文內容組織如圖2所示：
圖神經網絡(GNN)是一種用于圖結構數據的神經網絡模型，結合圖計算和神經網絡優勢，捕捉圖結構并抽象節點特征。圖計算模型擅長捕捉拓撲結構，但無法處理高維特征。典型神經網絡適用于歐氏空間數據，如卷積神經網絡處理網格數據，循環神經網絡處理序列信息。針對非歐氏空間復雜圖數據，建模過程需要新處理機制。目前受歡迎的消息傳播模式通過獲取高階鄰居信息提升節點表達能力，包括鄰居聚合和節點更新兩步。
本節從消息傳遞機制出發，介紹圖神經網絡模型的聚合和更新操作，分類介紹圖卷積神經網絡、圖注意力網絡、循環圖神經網絡和自編碼器圖神經網絡，分析其在大規模數據訓練中的挑戰，并總結挑戰。
基于神經網絡的消息傳遞機制描述了節點特征在網絡中進行傳播的過程, 傳播結果最終會通過神經網絡操作迭代地更新在節點表示中。圖神經網絡表示模型能夠捕捉圖結構信息和建模復雜的節點特征
圖卷積神經網絡（Graph Convolutional?Network, GCN）。GCN是常見圖神經網絡模型，通過卷積操作實現鄰居節點聚合。GCN模型分為基于譜域和基于空間域兩類，其中基于譜域的方法基于圖信號分析和圖譜論，基于空間域的方法關注鄰居節點的直接聚合方式。
大規模數據訓練中，GCN面臨內存不足和鄰居爆炸問題。分批訓練可緩解內存限制，但增加計算和內存消耗。隨著層數增加，資源消耗呈指數級增長。
圖注意力網絡（Graph Attention Network,GAT）。GAT是一種深度學習模型，用于處理圖結構數據。它通過引入注意力機制，為每個節點分配不同權重，以捕捉節點間的依賴關系。GAT在圖神經網絡中具有高效性和可擴展性，廣泛應用于社交網絡、推薦系統和生物信息學等領域。
大規模數據訓練中，GAT與GCN均存在內存不足和鄰居爆炸問題。GAT采用注意力權重加權聚合，計算和存儲資源消耗更多。
循環圖神經網絡（Gated Graph Neural Network，GGNN）。循環神經網絡（RNN）用于建模序列信息，如文本、用戶歷史記錄和音視頻。長短期記憶網絡（LSTM）和門控循環單元（GRU）是RNN的兩種常見形式。GGNN模型基于GRU，針對輸出狀態序列的任務，而GCN和GAT模型以靜態圖為輸入。GGNN以時間演化圖為輸入，通過遺忘門和更新門等結構捕捉圖結構演化特征。
大規模數據訓練中，GGNN需載入整個鄰接矩陣，占用更大內存。訓練涉及大量參數，內存挑戰顯著。分批訓練中，圖數據不規則性增加冗余計算。
基于自編碼器的圖神經網絡（Structural Deep Network Embedding，SDNE）。自動編碼器由編碼器和解碼器組成，通過無監督學習高效學習節點表示。SDNN模型將自動編碼器應用于圖結構數據，和典型自動編碼器模型相同, SDNN 需要減小節點的重構損失。此外, 還考慮節點間的相似性。
SDNE無法捕捉節點間的高階關聯，需通過損失函數捕捉節點間直接關聯，但在大規模數據訓練中，內存限制導致分批訓練產生冗余計算。盡管采用負樣本采樣，圖數據的不規則性仍帶來挑戰。
表3概括了圖神經網絡模型、圖數據結構以及數據規模三個方面基于不同模型訓練方式（整批訓練和分批訓練）的挑戰。
針對圖神經網絡在大規模數據訓練中面臨的挑戰，已經開展了一些有意義的算法優化工作。大部分的工作都集中在數據的優化上，其中最主要的方法是使用不同粒度的采樣算法實現分批訓練。這些算法主要可以按照采樣粒度分為以下三類：基于節點的采樣算法、基于層的采樣算法以及基于子圖的采樣算法。
GraphSage。GraphSage采用節點采樣進行表示學習，優化模型參數。如圖3(b)所示，針對目標節點，隨機采樣固定數目鄰居節點，使用聚合函數進行特征聚合，借助反向傳播學習。通過優化模型實現新數據表示，并借助隨機節點采樣算法將不規則圖結構數據規則化，實現參數共享。
PinSage。PinSage算法結合隨機游走和圖卷積操作，用于大規模推薦系統。通過節點采樣構建計算圖，捕捉圖結構特征，提高圖卷積神經網絡模型在大規模數據上的可拓展性。提出基于重要性的節點采樣算法，如圖 3(c)所示，利用隨機游走策略評估節點重要性，對每個節點選擇最重要的k個節點作為采樣節點，并在聚合過程中進行重要性加權。
VR-GCN。VR-GCN是一種新的采樣算法，解決了大規模圖神經網絡參數共享問題，通過方差消減保證收斂性，并證明采樣規模不影響局部最優性能。如圖 3(d)所示，針對目標節點，VR-GCN僅采樣兩個節點，利用歷史激活節點減小方差，顯著減小估計梯度的偏置和方差。與考慮所有鄰居節點的情況相比，VR-GCN僅考慮2個鄰居節點，大大減小了模型訓練的時間復雜度和內存開銷。
LGCL。LGCL將圖數據結構化以滿足卷積操作的要求，通過節點特征重組將不規則圖結構數據轉化為歐氏空間，便于利用CNN算法進行優化。然而，基于顯著特征的重組方式在一定程度上破壞了節點特征多樣性，加劇了節點表示過度平滑問題。以圖3(e)為例，采樣均值聚合方式導致節點特征值趨于接近對應特征最大值，最終所有節點表示趨于相似，加劇圖卷積神經網絡的過度平滑問題。
總結。針對圖神經網絡中直推式訓練模型存在的局限性，GraphSage提出了基于節點的采樣算法，通過隨機采樣一階和二階鄰居以適應歸納式任務。PinSage提出了基于重要性的采樣算法，并在節點聚合中進行重要性加權。VR-GCN關注采樣算法的收斂性，通過減小梯度估計的偏置和方差來提高算法收斂性。LGCL從特征粒度進行篩選重組為新的節點進行聚合。
FastGCN?。FastGCN通過將圖卷積操作轉化為概率分布積分形式，如圖4(a)所示，并利用蒙特卡洛法估計積分值，解決了圖神經網絡大規模數據訓練中的時間和內存開銷問題。FastGCN采用層級采樣避免鄰居節點爆炸，并基于采樣的損失函數和梯度函數進行模型訓練，同時通過重要性采樣優化性能。
AS-GON。AS-GON是一種自適應層級采樣算法，通過逐層固定采樣節點數避免GCN中鄰居節點爆炸問題。基于上層采樣結果對下層節點進行采樣，使下層采樣鄰居節點被盡可能多的上層節點共享。AS-GON還通過連接跳躍捕捉二階相似性，利用連接跳躍策略獲取二階鄰居特征，傳播高階鄰居特征信息，無需額外采樣開銷。
LADIES。LADIES是一種新的采樣算法，旨在解決基于節點和基于層的采樣算法中存在的挑戰。如圖4(d)所示，該算法根據上層節點及其鄰居節點構建二分圖，計算重要性分數作為采樣概率，并依概率采樣固定數目的鄰居節點作為下層節點。通過迭代構建整個計算圖，可以有效地降低計算和內存開銷。
總結。PastGCN通過層級采樣估計積分值，避免鄰居節點爆炸，但存在連接稀疏和冗余節點問題。AS-GCN通過顯式方差消減保證收斂性，并捕捉二階關聯性。LADIDS基于二分圖構建相鄰兩層節點，進行層級重要性采樣，緩解鄰居節點爆炸問題，但全局節點復用有限。
Cluster-GCN。Cluster-GCN通過子圖采樣算法提高了GCN分批訓練的計算效率。通過聚類感知的劃分算法Metis將節點劃分為c塊，并將鄰接矩陣轉化為對角矩陣A和B。將GCN的表示函數分解到不同的聚類分塊中，并通過隨機組合分塊來緩解存在的邊遺漏和估計誤差的問題。在分批訓練中，每一批隨機選擇多個聚類分塊而不是將單個分塊作為訓練數據。
RWT。RWT是一種逐層游走的訓練策略，用于解決 Cluster-GCN 在大規模圖應用中的時間和空間開銷問題。通過子圖采樣算法實現圖數據分批，每批次構建圖神經網絡模型進行訓練。采樣策略綜合考慮隨機性和圖結構連接性，采用逐層擴張方式從當前子圖鄰居節點中采樣并更新子圖，直至達到閾值。RIWT 在 GCN 和 GAT 上驗證了有效性。
GraphSAINT。GraphSAINT是一種基于采樣的圖神經網絡模型，通過先采樣子圖再構建網絡模型，消除分批訓練偏差，并降低分批方差。首先，估計節點和邊的采樣概率，然后在每個訓練批次中進行子圖采樣，并構建完整的GON模型進行訓練。通過歸一化方法消除偏差，同時借助隨機游走策略優化采樣算法。Zeng等提出了GraphSAINT，通過偏差消除和誤差降低提高精度。他們提出了一個并行訓練框架，通過子圖采樣分批訓練，提高程序并行性。采樣器間和采樣器內并行化理論上帶來近線性加速比。特征傳播方面，通過數據劃分提高緩存利用率，減小通信開銷。此外，他們還提出了運行時調度器，通過重排操作順序和調整分批圖優化并行性能。
SHADOW-GNN。SHADOW-GNN是一種圖神經網絡模型，旨在解決大規模數據帶來的挑戰，并緩解過度平滑問題。通過解耦節點接受區域與圖神經網絡深度之間的關聯，實現深層網絡表達能力，同時避免過度平滑。SHADOWGNN采用子圖采樣策略，形成不同子圖，然后在子圖上應用任意深度的圖神經網絡模型，獲得節點表示。
總結。Cluster-GCN通過節點聚類提高節點利用率，如圖 5(c)所示；RWT借助隨機游走策略逐層擴張子圖，如如圖 5(b)所示；GraphSAINT側重減小估計偏差與方差，提高模型性能；SHADOWGNNI63借助圖采樣策略增強模型可拓展性，緩解過度平滑問題，如圖 5(d)所示。
Zeng等人在5個數據集上（表4）比較了4種采樣算法在節點分類任務上的準確性性能對比結果如表 5所示，基于子圖的采樣算法在不同數據集上表現更好，micro E1指數更高且方差較小。GraphSage在數據集Flickr、Reddit、Yelp和Amazon上的節點分類準確性與基于子圖的采樣算法接近，但訓練時間較長。
針對大規模數據訓練中存在的挑戰，本節總結了不同粒度的采樣算法（如表6所示），如節點級、層級和子圖級采樣算法。這些算法在一定程度上緩解了大規模數據訓練中存在的內存限制問題，增加了模型的可拓展性，并通過重要性采樣、方差消減、隨機組合等方式提高模型收斂性。然而，目前的采樣算法主要基于靜態的同構圖進行優化，忽略了現實應用中圖數據的異構性、動態性、冪律分布等復雜特征。
圖神經網絡計算過程涉及不規則訪存和復雜特征計算，傳統框架在圖計算上性能較差。針對此問題，研究者提出面向圖神經網絡的編程框架并探索優化技術，為大規模圖神經網絡模型運行和優化奠定基礎。
本節將對 Deep Graph Library、PyTorchGeometric、Graph-Learn 等主流的編程框架進行總結, 如表 7所示：
將圖神經網絡編程框架相關的優化技術按照其優化方面分為 5 個部分, 分別是數據劃分、任務調度、并行執行、內存管理和其他方面, 總結如表8所示：
常見圖神經網絡模型及其挑戰分析。本文首先介紹了圖卷積神經網絡、圖注意力神經網絡、圖循環神經網絡和基于自編碼器的圖神經網絡四種常見的圖神經網絡模型，對應分析了其在大規模數據應用中存在的挑戰，并分類總結分析了模型層相關的挑戰。然后從算法模型和編程框架兩個方面就相關研究進行了總結和分析。
算法模型。針對大規模數據在圖神經網絡模型訓練中帶來的挑戰，大部分優化工作集中在采樣算法方面.根據采樣粒度本文將現有工作分為基于節點、層和子圖的采樣算法三類。針對每一類采樣算法，介紹相關的主要模型并進行分析·最后進行了全面的總結和分析。
編程框架。本文首先總結了 DGL、PyG 等主流的編程框架.然后將現有優化技術分為數據劃分、任務調度、并行執行、內存管理和其他方面五類。針對每一個類別,簡要介紹了其優化目標并列舉了具體的優化策略。最后進行了全面的總結和分析。
展望。本文就面向大規模數據的圖神經網絡優化的相關進展進行了總結，涵蓋了模型優化和框架加速兩個方面。以下，我們將從這兩個方面展望未來的工作，詳見圖6所示：
本文章轉載微信公眾號@算法進階