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