使用這些基本 REST API 最佳實踐構建出色的 API
GNN訓練旨在找到最佳參數??*，使損失最小化。訓練延遲主要來自感受野中的消息聚合，對于深度GNN，計算圖可能變得巨大。訓練加速的總體思路是減少計算圖。有兩種方法：圖修改和采樣。圖修改分為兩步：首先生成一個小圖G’，然后進行常規GNN訓練。采樣則是選擇節點/邊的子集來構建較小的計算圖，修改是動態且隱式的。兩種方法都能加速訓練，但圖修改可能會創建新的節點和邊，而采樣則保證所有節點和邊都有機會被覆蓋。
圖修改分兩步加速 GNN 訓練。圖修改方法包括圖粗化、圖稀疏化和圖壓縮。這些方法中的每一種都以不同的方式修改圖 G 以創建自己的 G ‘ ，但所有 G ‘ 都是較小的圖，可以加速 GNN 訓練。這些圖修改方法的說明如圖2所示。
圖粗化，是一種減小圖大小同時保留其整體結構的技術。通過將相同局部結構中的節點合并為“超級節點”，并將連接超級節點的邊合并為“超級邊”，可以得到粗圖。圖粗化的核心步驟是圖聚類，通常與圖譜相關。一些算法如受限譜近似和逆拉普拉斯，被用于保留一些圖屬性。黃等人提出了一種使用圖粗化來加速GNN訓練的通用框架，通過將圖劃分為K個簇，并設置超級節點特征和標簽。還有其他相關工作，如GOREN和GraphZoom，但關注點不同。
圖稀疏化，通過刪除冗余邊來減少計算圖，加速GNN訓練。現有方法通常保留原始圖的關鍵屬性，如切割總權重、光譜特性和分層結構。稀疏化算法可作為預處理步驟，降低全批次時間復雜度。一些相關工作執行基于GNN的圖稀疏化以提高GNN精度或魯棒性，但通常需要解決額外的優化問題，可能減慢訓練速度。剪枝和圖稀疏化不同，通常指對神經網絡模型的修改。
圖壓縮，通過匹配兩個GNN的訓練梯度來生成一個壓縮圖，從而減少GNN的計算量和內存占用。GCond是一種用于生成壓縮圖的方法，可以在保留原始圖訓練動態的同時顯著減小圖的大小。通過在原始圖和壓縮圖上訓練兩個具有相同架構的GNN，GCond可以生成壓縮圖，同時保持原始GNN的性能。實驗表明，GCond可以在多個圖基準上實現小于1%的壓縮比，同時保持原始GNN超過95%的準確度。因此，GCond非常適合神經架構搜索等任務。然而，為了加速單個GNN的訓練，GCond應該與其他加速方法或更好的壓縮策略相結合。
采樣是一種加速GNN訓練的技術，通過動態選擇節點和邊的子集來減小計算圖，從而提高訓練速度。研究發現，通過采樣可以保持模型精度，同時減少時間和內存消耗。需要注意的是，采樣與圖形修改不同，采樣是動態且隱式的，沒有中間修改的圖形輸出。
采樣方法分為節點方式、逐層和子圖方式三類，圖3為不同圖采樣方法的說明每種方式都有其優缺點。實驗表明，逐層采樣方法在Reddit數據集上表現更好，子圖采樣方法在PPI數據集上表現更好。不同采樣方法在不同數據集上的性能和運行時間存在差異，如表1所示。
圖3 不同圖采樣方法的說明。節點采樣方法對每個計算層的每個節點進行采樣，這可能會導致冗余節點（例如，節點E被采樣兩次）和丟失邊（例如，節點C和節點D之間的邊丟失）；逐層采樣方法基于前一層中的節點對每層進行采樣。子圖采樣方法對節點列表及其導出的子圖進行采樣，然后通過采樣子圖內的所有邊進行消息傳遞。
表1 不同采樣方法的性能比較
節點采樣。節點采樣方法應用于每層 ?? 的每個目標節點 ??。采樣程序的示例如圖 3(a) 所示。
GraphSAGE是通過節點采樣來減少節點感受野的開創性工作，對于每一層??，GraphSAGE統一對每個節點的固定數量 (?? (??) ???????? )的相鄰節點進行采樣。GraphSAGE采樣算法也可以形式化為矩陣形式，其中 ?? (??)?? (???1) 表示全鄰居聚合，?? (??) ?? (???1) 表示采樣聚合。VR-GCN提出在GraphSAGE工作流程中使用歷史嵌入來減少嵌入方差并加速訓練收斂。除了GraphSAGE和VR-GCN之外，還有許多其他工作在探索節點采樣的不同方面。
雖然節點采樣方法可以通過減小感受野來緩解大規模GNN訓練的可擴展性挑戰，并且可以保證每層的每個節點都可以有合理數量的連接鄰居來更新其隱藏表示，但仍存在局限性。
逐層采樣。逐層采樣方法從同一計算層中的所有節點中選取子集，用于構建計算圖。每個節點與下一計算層的直接鄰居和后面計算層的第二跳鄰居等相連。對于每個節點，其層采樣鄰域是層采樣節點集與原始鄰域的交集。每個計算層執行 ?? (??) ?????????? 次采樣操作，選取 ?? (??) ?????????? 個鄰居節點。最后，當前計算層的采樣節點用于構造后面計算層的鄰域以進行消息傳遞。采樣程序的示例如圖 3(b) 所示。
FastGCN通過分層重要性采樣解決節點采樣的可擴展性問題，但面臨連接性挑戰。AS-GCN提出了自適應分層采樣方法，以頂層為條件對下層進行采樣，并添加正則化減少方差。LADIES在后一層的直接鄰域內進行采樣，以確保信息傳遞。分層采樣方法克服了節點采樣的指數鄰域擴展限制，具有線性時間和內存復雜度。然而，連通性問題依然存在，可能導致模型性能下降。子圖采樣。子圖采樣方法將整個圖作為輸入，輸出樣本子圖，用于GNN訓練。由于子圖通常較小且只表示局部信息，訓練時需要添加隨機性以提高準確性。這些方法與圖修改方法類似，但并非真正修改圖，而是動態采樣。
ClusterGCN將圖劃分為簇，對每個子圖簇進行全批量GNN訓練，提高了可擴展性，但聚類結果固定。GraphSAINT提出四種不同的節點采樣算法，其中隨機游走采樣器表現更好。Shadow-GNN對每個目標節點的不同子圖進行采樣，并設計了將GNN深度與其感受野大小分開的原則。還有許多其他后續工作進行子圖采樣，如RWT的波紋步行采樣器和曾等人的并行化版本。此外，一些分層采樣方法可用于構建子圖。
子圖采樣方法不依賴GNN模型和嵌入，可在訓練前或并行完成。但僅考慮圖結構，未考慮模型訓練動態，因此如何將方差減少研究納入子圖采樣過程尚待解決。
GNN推理加速的目標是構建一個模型～GNN??～，使其在G????????上的推理與GNN??*具有相似的精度，但速度更快。與訓練加速不同，推理加速更以模型為中心，主要關注模型架構、參數數值精度和參數值。常見的推理加速方法包括剪枝、量化和蒸餾，這些方法廣泛用于加速通用DNN，也可應用于圖的GNN。主要挑戰是如何保存圖結構信息并解決消息聚合引起的延遲。
GNN剪枝是一種加速GNN推理的方法，通過選擇要剪枝的GNN權重來優化模型。最常見的方法是權重幅度剪枝，即剪枝具有較小權重的神經元連接或降低權重的L1范數。剪枝提供了模型速度和準確性之間的權衡，移除更多權重可能導致模型更快但準確性降低。
Zhou等人提出了一種通道修剪方法，將剪枝問題表述為LASSO回歸問題，交替優化可學習的掩碼和更新的GNN權重矩陣。彩票假設（LTH）是一種流行的剪枝研究，表明剪枝后的稀疏神經網絡可以重新訓練以達到與原始神經網絡相似的精度。陳等人通過迭代幅度剪枝（IMP）測試了GNN的LTH，觀察到了速度增益和邊際精度損失。剪枝可以加速模型推理，但并不總是加速模型訓練。
量化是一種廣泛使用的技術，通過降低模型參數數值精度來加速通用機器學習模型。對于DNN，延遲主要來自矩陣乘法，量化可以減少MAC運算從而加速推理。量化的另一個好處是減少內存訪問時間。量化研究的目標是在保持推理精度的同時實現推理加速。量化可以分為訓練后量化（PTQ）和量化感知訓練（QAT）。PTQ易于使用，可以應用于任何架構，但精度較低。QAT對訓練期間的量化誤差進行建模，通常可以找到更好的量化模型，但成本是模型訓練時間較長，需要數據。現有的量化方法主要用于CNN，GNN的量化有其自身的挑戰，需要特殊處理。
SGQuant和Degree-Quant是兩種研究GNN量化的方法。SGQuant是一種PTQ方法，主要關注節點表示的量化，通過多粒度量化優化量化效率。Degree-Quant是一種QAT方法，主要量化GNN權重和中間節點表示，通過保護掩模提高權重更新精度。
量化是GNN加速方法中最容易應用的一種，可顯著提升速度。與其他加速方法結合，如網絡架構搜索（NAS），可進一步提高速度。
知識蒸餾（KD）是一種將復雜模型壓縮為更小、更快的模型的技術。它通過師生方式訓練兩個模型，教師輸出概率向量（軟標簽），學生模型輸出與軟標簽的距離。通過最小化這種距離，將知識從教師轉移到學生。常見的距離度量是Kullback-Leibler (KL) 散度。
大多數情況下，先單獨訓練教師模型，再固定教師訓練學生模型。知識蒸餾損失L??????僅用于更新學生參數，不適用于教師。KD可應用于半監督環境，通過使用標記數據訓練教師并為未標記數據生成軟標簽來訓練學生。KD已廣泛用于壓縮和加速CNN等DNN，最近擴展到GNN。GNN KD方法主要在兩個方面有所不同：1）教師和學生模型是什么？2）KD目標是什么？
LSP、TinyGNN和GLNN是探索KD加速GNN的先驅工作。LSP提出了局部結構保留損失，鼓勵學生模型保留與教師模型相似的局部結構。TinyGNN通過添加特殊層 PAM鼓勵節點直接交互，提高蒸餾模型精度。GLNN采用純MLP學生模型，通過 KD實現與教師GNN競爭的性能。這些方法在不同設置下開發，具有不同的適用性和速度增益。KD在GNN上的應用仍處于早期階段，存在許多有趣的開放性問題。
推理加速技術組合可以實現更好的結果。比如將量化與蒸餾相結合，逐步量化GNN的權重和激活，最終實現二進制GNN，可在Raspberry Pi 4B上實現2倍加速，僅適度損失精度。
除了高效的GNN訓練/推理算法，優化底層系統對于提高GNN的端到端吞吐量至關重要。現有工作從三個方面加速GNN系統：GPU內核加速、用戶定義函數（UDF）優化和可擴展訓練系統。由于GNN計算遵循消息傳遞范式，需要高效的稀疏操作，人們提出了各種高效的GNN內核和UDF優化技術。然而，設計一個高效的可擴展GNN訓練系統仍然是一個開放研究問題。目前，兩個廣泛使用的GNN框架是PyG和DGL。
GPU內核是專門針對GPU進行優化的程序，可以大大提高DNN訓練和推理的計算速度。盡管GPU在深度學習加速中廣泛應用，但由于圖形的稀疏性和不規則性，使用GPU加速GNN仍具有挑戰性。
近年來，許多研究提出了新的GPU內核以加速GNN工作負載，表2總結了這些工作。PCGCN通過節點聚集的稀疏模式提高GNN數據局部性，采用雙模式計算，利用圖聚類可能產生預處理開銷。fusionGNN開發了兩種GNN聚合工作負載抽象：GAS和GAR，將操作融合以減輕內存流量，支持多GPU場景。FusedMM是可擴展到GPU加速的CPU內核，通過融合相關操作實現內存減少，采用邊緣平衡分區保證線程之間的工作負載平衡。TLPGNN通過兩級并行性提高性能，實現負載均衡和內核融合。張等人將GNN操作分解為四部分，解決冗余神經算子計算、不一致的線程映射和過多中間數據問題。
總之，工作負載重新排序對于識別GPU友好的處理模式至關重要。大多數工作順序計算輸出節點并并行處理特征，以實現內核融合和合并的內存訪問。然而，圖結構可能不規則，因此一些工作利用雙模式計算和動態工作負載分配來處理不同屬性的圖。
GNN在消息傳遞范式下成功的關鍵因素是消息、聚合和更新函數的靈活性。通過使用Python中的張量運算符，用戶可以原生表達這些函數并通過系統提供的API執行。這種編程范例稱為用戶定義函數(UDF)，可以提高代碼模塊化和減少重復。最近開發的工作簡化了用戶定義的GNN的部署。
FeatGraph、Seastar和Graphiler是深度學習系統的編譯器堆棧，提供了靈活的編程接口。FeatGraph支持用戶定義函數，Seastar為以頂點為中心的編程接口，Graphiler開發了一種用于分散/聚集相關任務的自動化工具。這些工具正在變得成熟，因為最近提出了幾個稀疏深度學習操作的后端，如SparseTIR，可以表示上述Seastar、FeatGraph和Graphier工作支持的運算符。
為了支持大規模圖 GNN 訓練，最近的工作開發了可擴展訓練的 GNN 系統。可擴展性分為垂直可擴展性和水平可擴展性。垂直可擴展性利用有限資源處理擴展數據，水平可擴展性通過擴展資源提高效率。
一些工作對分布式 GNN 訓練系統進行了總結和分類。我們關注可擴展的 GNN 訓練，包括高效的分布式訓練和大規模訓練。根據數據加載到計算設備上的方法，我們將可擴展 GNN 訓練系統分為設備上系統、基于交換的系統和基于采樣的系統。圖4展示了這些類別的概述，表3為這些類別的比較。
圖4 三種可擴展 GNN 訓練系統的概述。(a)中的虛線表示來自不同worker的節點之間的依賴關系，而(b)中的灰色節點僅作為子圖計算的輸入節點。為了獲得更好的視覺清晰度，未顯示工作人員之間的模型同步表3?三種可擴展 GNN 訓練系統的比較
設備上系統（圖 4(a)）將圖和相關特征分布式存儲在計算設備上，主要關注全圖聚合以利用計算資源，但存在通信和內存問題；基于交換的系統（圖 4(b)）將所有數據存儲在共享內存中，通過交換中間結果進行計算，但存在工作負載調度和迭代延遲問題；基于采樣的系統（圖 4(c)）將圖和特征保存在共享內存中，采用鄰居采樣進行鄰居聚合，面臨數據移動瓶頸，通過優化通信和緩存策略來提高性能。總體而言，基于采樣的系統在大規模圖GNN訓練中具有前景。
表4總結了可擴展培訓的系統。
人們對GNN的興趣日益濃厚，促使了定制加速器（FPGA或ASIC）的開發，以實現更快的處理速度。GNN與CNN在計算復雜度和通信模式上的差異使得許多CNN加速器不適合GNN。GNN需要矩陣乘法單元，并具有不規則的內存訪問。由于聚合和更新階段的計算和通信模式不同，僅使用密集或稀疏MM單元對于GNN應用效率低下。此外，GNN使用分配給每個節點的向量，與傳統圖算法不同。這些區別促使研究人員設計專門的硬件模塊來有效處理GNN。
為GNN設計定制加速器需考慮三點：
廣泛的GNN層。除了可能合并圖/子圖池化層和非線性激活函數之外，GNN模型使用不同的聚合和更新方法，這可能會影響性能和靈活性。支持多種計算模式需要通用性，可能會阻止獲得最佳性能。
計算/通信模式和稀疏率差異。不同步驟的計算和通信要求可能不同，例如，鄰接矩陣超稀疏，權重矩陣稠密，節點嵌入通常密集，但ReLU等激活函數可能產生稀疏矩陣。此外，MLP等多層感知器也產生密集乘法單元。這些差異和訪問模式給GNN硬件設計帶來挑戰，需要解決圖稀疏性、激活算子引入的稀疏性以及模塊之間的協調問題；
動態輸入和網絡結構。GNN的架構決策高度依賴于輸入圖的特征和模型的超參數，圖的大小、稀疏程度和向量維度等因素對GNN加速器的內存和計算要求有很大影響。不同尺度和結構的圖可能導致計算資源需求的差異，以及處理節點鄰居數量變化時的工作負載不平衡。
表5比較了不同定制加速器的五個主要特征，包括圖大小、目標GNN、層定制支持、稀疏性處理和并行化級別。相關工作根據工作量的靈活性進行分類，包括針對多種GNN算法的加速器和專注于GCN操作的加速器。
本節概述了設計定制加速器以支持多種GNN算法的工作。這些工作要么創建一個處理所有計算階段的統一架構，要么為不同計算和通信模式開發專用引擎。
全階段統一架構。該架構通過開發一個能夠處理這些階段的單一引擎來加速計算，盡管它們在計算和通信方面有不同的要求。EnGN、Rubik、G-CoS和GCoD等框架致力于優化圖神經網絡（GNN）的性能和效率。EnGN處理多種GNN，采用神經圖形處理單元（NGPU）作為統一架構，并開發了維度感知階段重新排序策略以減少操作數量。Rubik提出了一種用于訓練GIN和GraphSage的加速器，通過預處理器對圖進行重新排序，并使用分層加速器架構。G-CoS是一個自動化框架，包含一次性協同搜索算法和通用加速器搜索空間，以優化GNN的性能和效率。GCoD是一個協同設計框架，通過優化算法和硬件加速器來解決GNN推理中的極度稀疏問題。I-GCN提出了一種稱為“孤島化”的新方法，以提高GNN的數據局部性，其硬件架構包括孤島定位器和孤島消費者。
每級專用模塊。該類別為GNN算法的主要計算階段設計了一個專用引擎，使每個引擎都能根據各階段需求進行定制，并支持不同階段的并發執行。HyGCN加速器將GNN算法分為聚合和組合兩個階段，采用獨立的處理引擎以數據流方式處理。FlowGNN是一種通用數據流架構，可支持多種消息傳遞GNN算法。BlockGNN利用塊循環權重矩陣和FFT/IFFT加速GNN模型更新階段的計算。DeepBurning-GL是一個自動化框架，用于生成GNN硬件加速器，并提供了三個模板。
該領域的研究專注于更專業的算法，特別是GCN。第一個子組開發了一個具有自定義層修改的深層管道，而第二個子組則采用固定硬件方法處理所有層。
可分層定制的深層管道。GCN加速器的基本優化應減少與內存事務相關的費用。為此，構建了一個深度管道，避免了不同GCN層之間的片外內存事務。同時，根據每一層的單獨工作負載定制硬件參數。AWB-GCN 和 StreamGCN 是兩種高效的 GCN 加速器架構，旨在利用圖卷積網絡的稀疏性。AWB-GCN 提出了自動調整工作負載平衡技術，包括分布平滑、邪惡行重新映射和遠程切換，以克服負載不平衡問題。StreamGCN 則提出了一種高效且靈活的 GCN 加速器，用于從 DRAM、主機 CPU 和網絡傳輸小圖，并利用所有可用的稀疏性。這兩種架構都支持層內和層間并行，并且都基于內積矩陣乘法。
全層統一架構。GCN算法由多個層組成，每層具有不同特征。該類別的研究提出了跨層構建適應性更強的架構，并為所有層使用相同引擎。這些作品專注于特定的工作負載（GCN）而具有更大的定制可能性。GraphACT 開發了一種用于訓練針對 CPUFPGA 異構系統上小圖的 GCN 的加速器，通過創建小圖和定義三種類型的乘法來加速訓練。張等人的方法專注于加速大圖的 GCN 推理，通過將輸入數據劃分為更小的尺寸，應用冗余減少方案和節點重新排序階段來減少全局內存訪問。BoostGCN 提出了一個旨在優化 FPGA 上的 GCN 推理的框架，通過分區為中心的特征聚合和兩種類型的特征更新模塊來減少內存流量并解決工作負載不平衡問題。
表6回顧了加速器，重點關注驗證方法和報告的加速。
本文討論了針對特殊圖類型（異構圖和動態圖）和特殊GNN架構（異構GNN和注意力GNN）的加速技術。
異構圖是一種新的數據結構，用于表示現實世界中的復雜圖，其中節點和邊具有不同類型，彼此具有顯著不同的含義。例如，在引文圖中，節點可以是作者、地點和論文，邊可以表示作者發表的論文、在地點發表的論文等。
許多 GNN 是為異構圖設計的，面臨可擴展性挑戰，需要加速。在異構圖上，更好的采樣算法應該執行加權采樣以包括所有類型的鄰居節點。HetGNN 引入了一種新穎的異構鄰居采樣器，克服了異構圖上的特殊挑戰。HGT 是一種基于 Transformer 的異構圖 GNN，引入了高效的采樣器，使模型能夠處理具有數十億條邊的 Web 規模圖數據。Pigeon 是一種中間表示和代碼生成器，用于異構圖上的關系圖神經網絡的端到端訓練和推理，通過解耦模型語義、數據布局和特定于操作員的時間表來解決 RGNN 帶來的性能挑戰。
時空數據在科學研究和實際應用中廣泛使用，動態圖在解決此類問題時表現出色。動態圖是隨時間變化的圖，其學習與推理面臨額外挑戰。因此，研究人員開發了時空GNN，對空間和動態演化進行聯合建模。時空GNN應用于大規模動態系統模擬，面臨與靜態圖上常規GNN類似的可擴展性問題，需要加速。時空GNN加速面臨特殊挑戰，因為模型訓練需要按時間順序進行，圖操作需要同時考慮空間和時間鄰居。本節總結了最新的時空GNN加速工作，通常應用于大規模動態圖的學習和推理。
TGL提出了一種加速連續時間GNN訓練的統一框架，包括時間CSR數據結構、并行采樣器和新型隨機塊調度技術。MTGNN通過圖學習模塊自動提取節點關系，并應用集群減少內存使用。GraphODE將GNN表達能力與學習動態系統ODE建模相結合，采用自適應ODE求解器和耦合的ODE函數。GN-ETA提出了一種大規模GNN模型，用于實時估計到達時間（ETA），采用基于超路段的加速和MetaGradients方法。
動態圖的時空GNN是靜態GNN的擴展，對時間方面進行了特殊處理。傳統方法采用循環神經網絡，但耗時且無法捕獲長期依賴性。最新進展如位置編碼和神經常微分方程加速了動態GNN。硬件加速器支持各種圖形拓撲，但動態圖和異構圖面臨挑戰。為解決此問題，可擴展軟件-硬件協同設計，包括開發分析器評估圖和目標算法的要求，以及轉向更通用的設計架構或支持多種專用架構。
盡管GNN加速研究已取得進展，但仍處于早期階段，未能跟上圖數據擴張速度。近期COTS系統和定制硬件加速開始受到關注，需探索針對異構和動態圖的定制加速技術。下面介紹幾個值得進一步探索的研究方向。
更好的圖修改算法。提高圖修改算法效率，如粗化、稀疏化和壓縮，有助于加速GNN訓練。在預處理階段刪除冗余鄰居可提高效率，稀疏化保留局部性，壓縮提高訓練效率。早期識別最佳壓縮圖將使該技術更有用。好的圖修改方法有利于GNN架構的自動化設計和調整，簡化預處理可顯著加速GNN開發。
更好的采樣算法。GNN采樣方法未來可改進，如分層采樣，利用圖的多尺度結構提高效率并捕獲多尺度特征，對大規模圖特別有用。動態圖的采樣方法也可進一步研究，如節點和邊隨時間變化，單獨在每個時間戳應用采樣效果不佳。
推理加速方法。如剪枝、量化和蒸餾可以組合使用，以提高速度。例如，可以將權重量化為二進制，同時利用蒸餾。由于推理階段更靈活，這些方法可以更容易地以各種方式組合，如結合剪枝和量化實現低精度的稀疏模型，或結合剪枝和蒸餾進一步細化蒸餾后的學生模型。
系統。現有研究主要關注提高GNN的運行時效率，但內存需求仍是瓶頸。可采用重新物化、量化和數據修剪等技術減少內存開銷。由于GNN模型不規則計算和數據訪問模式，高級訓練/推理算法可能對系統不友好，系統友好的GNN算法協同設計有前景。現有文獻缺乏GNN系統全棧開發，結合不同級別技術形成超高效GNN系統是研究主題。
定制硬件。GNN加速的關鍵在于減少片外存儲器的數據獲取量。除了數據重用、緩存和優化等技術，還可以探索修剪、量化和壓縮等方法。為促進GNN加速器設計，需要開發更先進的自動化設計生成器，如神經架構搜索、基于學習的硬件設計評估模型和智能設計空間探索等技術。?
文章轉自微信公眾號@算法進階