圖神經網絡（GNNs）正逐漸應用于對圖結構資料的機器學習研究。GNNs在許多任務上實作了最先進的性能，但是當面對具有大量資料和嚴格延遲要求的實際應用時，它們面臨可擴充性挑戰。已經進行了許多研究，探讨如何加速GNNs以應對這些挑戰。這些加速技術涉及GNN流程的各個方面，從智能訓練和推理算法到高效系統和定制硬體。由于GNN加速的研究數量迅速增長，缺乏一個系統的處理方法來提供一個統一的視角并解決相關工作的複雜性。在這篇綜述中，我們提供了一個GNN加速的分類法，回顧了現有的方法，并提出了未來的研究方向。我們對GNN加速的分類處理聯系了現有的工作，并為該領域的進一步發展奠定了基礎。
1. 引言
圖是一種自然而強大的資料結構，用于表示實體及其關系。許多真實世界的資料可以表示為圖，其中節點表示一組實體，邊表示它們之間的成對關系，例如社交網絡中的個人，公司和銀行之間的金融交易，分子中的原子和鍵，以及交通系統中的車輛。圖神經網絡（GNNs）[45, 71, 125] 最近已經成為學習圖資料知識并進行預測的最廣泛使用的圖機器學習（ML）模型。GNNs在許多圖ML應用中取得了最先進的性能。例如，它們用于社交圖上的推薦[89, 136, 165]，金融圖上的欺詐賬戶檢測[31]，分子圖上的藥物發現[64]，交通圖上的交通預測[65]等。GNNs在圖上的優越性能主要歸因于它們能夠結合實體資訊（表示為節點特征）和關系（表示為圖結構）。
GNNs以節點特征和圖結構作為輸入，并輸出節點表示，這些表示可用于各種圖ML任務，如節點分類，邊預測和圖分類。對于圖中的每個節點，GNN通過資訊傳遞來學習其表示，它聚合來自節點鄰居的消息（特征），并通過使用神經網絡轉換聚合的消息來更新表示。每個聚合和更新操作稱為一個GNN層，它允許節點表示結合來自節點的直接鄰居的資訊。堆疊多個GNN層将遞歸應用這種操作，是以節點表示可以從多跳鄰居獲得資訊。是以，表示可以捕獲本地鄰域的上下文資訊，并用于回答圖上的複雜ML問題。對于目标節點，在其上應用層GNN，其跳内的所有鄰居形成目标節點的接收場。以目标節點為根，以每個節點的鄰居為其子節點的遞歸構造的層樹圖稱為目标節點的計算圖。
随着圖機器學習（ML）領域的快速發展，圖資料變得龐大，單個圖中含有衆多節點和邊。例如，截至2015年3月，Twitter使用者圖有2.88億月活躍使用者（節點）以及每使用者估計有208個關注關系（邊）；截至2014年12月，Facebook使用者圖有13.9億活躍使用者和超過4000億總邊[22]。這些數字已經增長得更大，并且變得難以估算。常用的學術基準也從數千個節點（例如，Cora [108]）增加到最近的Open Graph Benchmark (OGB) [50]中的多達2.4億個節點。大圖為GNN訓練和推理帶來了可擴充性挑戰。盡管當DNN參數數量變大時，其他資料類型的深度神經網絡（DNNs）也面臨可擴充性挑戰，但GNNs的挑戰是獨特的，更強調大圖資料[63, 163]，而不是模型參數的大量。
在對圖像或文本訓練DNNs時，即使資料量很大，也可以通過随機抽樣小批量來處理資料，因為假定所有資料執行個體都是獨立同分布的（iid）。DNN推理也可以獨立地為每個執行個體完成。然而，對于圖上的GNNs，節點彼此依賴，這帶來了好處也帶來了挑戰。GNNs利用節點依賴性來學習資訊豐富的表示并進行預測，但節點依賴性也意味着每個節點的GNN計算都涉及多跳鄰居。是以，考慮到節點依賴性，将圖節點劃分為GNN訓練的小批量非常重要。此外，節點依賴性意味着計算圖的大小在GNN層數的數量上呈指數增長[2]。在大圖上，通常需要更深的GNNs以獲得更好的性能[14, 73]，這不僅需要處理巨大的計算圖來進行小批量訓練，而且在單個節點上的推理也需要這樣做。以Twitter使用者圖為例，每個節點有208個鄰居，三層GNN的計算圖涉及節點三步内的所有鄰居，可能包含數百萬個節點（即，大緻208的3次方減去重疊的節點）。這個節點依賴性問題使得在大圖上應用GNNs非常具有挑戰性。對于大資料集的另一種情況是具有許多圖的圖資料庫，例如化學分子。
2 GNN加速
訓練算法 在給定具有随機初始化參數的GNN和一個具有節點特征和标簽的圖G的情況下，GNN訓練的目标是找到一組最優參數*，使得損失最小化，即* = arg min L (GNN (G,), )。GNN訓練算法的主要延遲來自于在感受野内從（多跳）鄰近節點聚合消息，對于大圖上的深度GNN，計算圖可能變得非常大。是以，GNN訓練加速的一般思路是減少計算圖。此外，人們希望通過加速訓練得到的GNN具有與不加速訓練得到的GNN相似的性能。在本節中，我們讨論兩類訓練加速技術：圖修改和抽樣。這兩種方法的目标都是為了加速訓練而減少計算圖。二者的差別在于是否有一個修改後的圖G'作為中間輸出。對于圖修改，過程可以分為兩個步驟。第一步輸出一個比G小的圖G'，可以在其上進行快速訓練。第二階段是以G'為輸入的正常GNN訓練。對于抽樣，每次訓練疊代中選擇一組節點/邊的子集來建構較小的計算圖。一般來說，抽樣也會修改G，但是修改是動态且隐式完成的，是以沒有中間的G'輸出。由于計算圖可能在每次疊代時不同，所有的節點和邊都有機會通過抽樣被覆寫。相比之下，對于圖修改，不是所有的節點和邊都會出現在G'中，但可能會建立新的節點和邊。