摘要
圖是描述事物及事物間關聯的一種重要資料結構，它廣泛應用於多個領域。由於圖具有與其他資料結構不同的特性且圖資料規模逐年增長，而用通用性系統處理圖資料的效率低下，因此有眾多工作研究了面向圖的系統設計與最佳化，以更好地對上層應用提供支援。
本系列文章首先回顧圖的概念，並對圖演算法進行分類討論，並引出圖計算系統的基本分類（第一部分)；接下來，詳細討論三大類系統：基於CPU的圖計算系統、基於異構器件的圖計算系統和基於新興非馮·諾依曼器件的圖計算系統，並對圖計算系統中使用的程式設計模型進行分類與介紹（第二部分）。隨後，文章介紹了工業界研究或使用的圖計算系統特點。最後，透過分析現有系統面臨的挑戰，文章指出圖計算系統的發展趨勢，以對未來研究提供借鑑作用（第三部分，本文）。
本系列文章筆者胡靜波為清華大學清華大學電子工程系碩士生；戴國浩為清華大學電子工程系助理研究員、博士後。該文工作得到清華大學和壁仞科技研究院聯合研究專案的支援。
前文回顧：面向大規模圖計算的系統最佳化（1）
05
工業界研究或使用的圖計算系統
在本節中，我們將介紹各個網際網路公司所研究或使用的圖計算系統，其對應關係如表5.1所示。我們總結工業界所關注的圖計算系統的特點，為未來學術界的研究提供借鑑作用，並尋求圖系統在創新性和實用性方面的統一。
表5.1網際網路公司及其所使用或研究的圖計算系統
2015年IBM提出了SQLGraph[67]，它利用關係和非關係儲存屬性圖,在查詢效能上比Neo4j[76]快2-8倍。2018年，Twitter提出了RecService[68]，一種分散式即時圖處理引擎，可在Twitter上處理數十億的即時推薦任務。RecService[68]使用使用者的社交環境和與使用者有關的即時事件來構建框架，並支援臨時和長期查詢。RecService[68]設計了新穎的分割槽方案，使得所有圖操作都在特定的群集節點上執行，以避免跨節點通訊和因圖頂點上的活動度較大而產生的“熱點”。
在2019年，騰訊正式開源了其高效能的圖計算框架Plato[62]，支援包含微信在內的眾多核心業務，使大規模圖計算進入分鐘級時代。騰訊指出其社交網路中的頂點已經達到十億量級，但學術界中現有的分散式框架未能滿足騰訊處理圖資料的效能需求。因此，騰訊的圖計算團隊自研了Plato[62]，其能夠支援大規模的離線圖計算和圖表示學習。Plato[62]擁有自適應的圖計算引擎，能根據不同型別的圖演算法，調整適應於稀疏或稠密的計算模式，幷包含了共享記憶體和流水線設計以及圖分割槽、資源排程等多個模組。在效能方面，相比於GraphX[31]，Plato[62]的計算速度高1-2個數量級，記憶體消耗減少1-2個數量級。
同樣在2019年，阿里巴巴提出了一個大規模圖神經網路平臺——AliGraph[63]，並針對儲存層、取樣層和操作層進行了最佳化。在真實資料集上的實驗表明，相比於通用型分散式圖計算系統PowerGraph[28]，AliGraph[63]的圖形構建速度提高了一個數量級，且已經部署在實際電子商務平臺上，以進行產品推薦。Euler[65]是阿里開源的國內首個工業級圖表徵學習框架，且已經應用到多項業務中，如檢索匹配、營銷工具等。Euler[65]是一個分散式框架，能夠支援大規模、複雜異構圖的表徵。2020年，阿里巴巴達摩院開源了全球首個一站式超大規模分散式圖計算平臺GraphScope[64]。GraphScope[64]對分散式系統的中編譯階段進行了最佳化，並且支援自動增量化的動態圖資料更新，技術層面結合了多項已發表的科研成果，提供的介面對於使用者編寫程式十分友好。相比於多個開源的圖計算系統，GraphScope[64]有一個數量級以上的加速。
Facebook在2019年提出大規模圖嵌入系統Pytorch-BigGraph[69]，其採用瞭如下關鍵技術：大引數矩陣的塊分解、均勻節點負取樣及重複利用、支援權重圖和多關係圖。結果表明，Pytorch-BigGraph[69]使用的分割槽方案能減少88%的記憶體消耗，且分散式訓練時間減少了4倍。谷歌提出GAP[70]，一種通用的近似分割槽框架，該框架採用深度學習方法進行圖分割槽，且能夠推廣到看不見的圖形。
綜上所示，工業界中應用的圖計算系統往往具有以下幾個特點：
-
系統以分散式框架為主。工業界的圖往往具有十億量級以上的節點和百億量級以上的邊，而單機相比於分散式系統，仍然無法支撐如此大規模的圖資料處理。
-
系統需要支援異構、動態圖和相應複雜的圖演算法。工業界的圖往往表現出了現實世界中的屬性，因而是複雜的。主要體現在頂點和邊都是異構、多屬性的，且圖會隨時間而動態變化，且更新速度快，無法用簡單的圖演算法進行表達。
-
系統具有多個層次。常見的工業級圖計算系統會分為底層的圖引擎層、中間的運算元表達層、上層的圖特徵演算法層等，並支援多個圖應用。
-
面向圖神經網路的系統或利用神經網路演算法進行系統最佳化是目前工業界關注的熱點問題。如阿里巴巴、Facebook都提出了自己的圖嵌入表徵系統，谷歌利用神經網路完成近似圖分割槽。
06
圖計算系統未來的發展趨勢
-
未來的圖計算系統需要針對現實中圖存在的異構、動態、多屬性特點進行相對應的最佳化。隨著圖應用場景的不斷增多，圖型別和結構也逐漸變得多樣和複雜，例如，現實中的圖通常具有大規模、異構（頂點/邊的類別不同）、動態（圖隨時間變化）、多屬性（邊包含了不同屬性）的特點。然而，大多數現有系統考慮的圖結構（有向/無向圖、靜態圖、無屬性圖）和評估的圖演算法（PageRank[8]、BFS[9]）都較為簡單，從而造成系統性能無法滿足實際需求。未來，研究者們需進一步考慮上述圖的複雜特性，並針對性地進行最佳化，如有效的增量式執行、快速地增加/減少圖中頂點或邊等，以減少系統在資料儲存、搬運等方面的開銷。另外，建議在系統評估時選用真實的複雜問題和應用場景，而非簡單模型下的基準圖演算法，以增強系統的實用性。
-
未來的圖計算系統需要設計更具通用性的程式設計模型或依據演算法特性自適應地選擇程式設計模型。不同圖演算法的差異性較大，現有的單一程式設計模型無法適應於所有圖演算法。例如，目前通用性最強的以頂點為中心的模型在執行圖挖掘演算法時的效率仍然較低，而以子圖為中心的程式設計模型在執行圖遍歷演算法時又相對複雜，不易編寫程式和理解。因此，如何設計出一個靈活的、更具表現力的程式設計模型仍是一個具有挑戰性的問題。而另一種解決思路是在一個圖計算系統中包含多種程式設計模型，並能夠根據上層應用中涉及的圖演算法型別，自適應地選取模型以執行運算，以滿足各類應用需求，使不同演算法的效能達到最優。上述兩種思路都是未來可能的研究方向。
-
面向圖神經網路和圖挖掘演算法的圖計算系統設計與最佳化會成為未來的研究重點。近年來，圖神經網路和圖挖掘演算法顯示出解決實際問題的巨大潛能。例如，有研究表明[77] [78]，圖神經網路因能同時結合圖拓撲結構和內容屬性資訊，其在推薦問題上的效能已經超過傳統的卷積神經網路(CNN, Convolutional Neural Network)和遞迴神經網路(RNN, Recurrent Neural Network)，而圖挖掘演算法則適用於金融風險管理、社交網路等方面。然而，利用已有的通用性圖計算系統在執行上述演算法時的效率較低，這主要是因為演算法間計算模式的差別。相比於傳統的圖遍歷演算法，圖神經網路演算法在更新頂點自身值時的計算複雜度更高，耗費的時間更長；而圖挖掘演算法則需要儲存更多的中間資料。上述計算特點的不同可能使先前的系統最佳化不再適用，並引發分割槽儲存、資料通訊、運算元最佳化等多個層面的問題。目前也已經湧現出針對於上述兩種演算法的專用型圖計算系統，例如Rstream[26]、AutoMine[39]、AliGraph[63]等，相信未來會有更多的工作提供系統層面的特定最佳化，這是同時具有創新與實用價值的。
-
基於GPU/FPGA異構平臺的大規模圖計算系統加速設計會成為未來的研究重點。隨著圖應用中不同計算任務的多樣性，單一硬體平臺可能無法達到效能的最最佳化。近年來，隨著異構硬體的興起，人們開始在GPU、FPGA平臺上處理圖資料，並展現出比單CPU系統更優秀的效能和巨大的潛力。例如，基於FPGA平臺的GraphGen[40]相比於CPU平臺，在處理圖計算問題時具有2.9倍以上的加速比；基於GPU平臺的Gunrock[37]在圖演算法上的平均執行速度比基於CPU平臺的PowerGraph[28]至少高出一個數量級。但基於異構平臺的圖計算系統仍存在一些問題，例如，受限於GPU視訊記憶體和FPGA片上儲存容量，系統能處理的資料規模較小，傳統的圖分割槽策略將不再適用，另一方面，資料如何在諸如CPU、GPU等不同硬體上進行儲存和排程也會成為新的問題。雖然目前已有工作針對上述問題提出有效的解決方案，但隨著硬體和工藝的不斷發展，研究如何在GPU/FPGA異構平臺上進行高效大規模圖計算系統的設計與最佳化，例如，資源排程、記憶體分配、有效的資料傳輸等仍是一個長遠而又具實際意義的課題。
07
總結
圖資料結構能夠直觀地表達事物間的聯絡，在多個重要領域有所應用。圖計算系統能夠基於圖資料對上層應用提供支援，因而成為了學術界和工業界關注的重點。本文對已提出的大規模圖計算系統進行了詳細的調研，並根據其使用的硬體平臺，分為以下三類：基於CPU的圖計算系統、基於異構器件的圖計算系統和基於新興非馮·諾依曼器件的圖計算系統。本文提取了上述主要系統的關鍵技術，並分析了系統間的優缺點。接著，本文總結了現有系統使用的程式設計模型，並結合模型特點指出了其適用性。之後，本文對眾多網際網路公司研究或使用的圖計算系統進行了回顧，並總結了具有實用性圖計算系統的主要特點。最後，透過對現有系統中問題的詳細分析，本文提出了4個大規模圖計算系統的發展趨勢，以供未來研究借鑑。（全文完）
作者簡介
胡靜波，本科就讀於西安電子科技大學，目前為清華大學電子工程系碩士生，專業為電子與通訊工程，自2019年入學至今，一直跟隨汪玉教授和戴國浩博士後進行大規模圖計算方面的研究，且已經發表有關通用性圖取樣框架的論文一篇。
戴國浩，現清華大學電子工程系助理研究員、博士後，分別於2019年和2014年在清華大學電子工程系獲得博士與學士學位。主要研究方向為大規模圖計算、異構計算、存算一體、虛擬化等，曾獲ASPDAC 2019最佳論文獎、DATE 2018最佳論文提名。
參考文獻
[8] Gao, R., Xu, H., Hu, P., & Lau, W. C.. “Accelerating graph mining algorithms via uniform random edge sampling.” 2016 IEEE International Conference on Communications (ICC). IEEE, pp. 1-6, 2016.
[27]Malewicz G, Austern MH, Bik AJ, et al., 2010.Pregel: a system for large-scale graph processing. Proc ACM SIGMOD Int Conf onManagement of Data, p.135-146.
[62]https://github.com/tencent/plato
[66]Khayyat Z, Awara K, Alonazi A, et al. Mizan: asystem for dynamic load balancing in large-scale graphprocessing[C]//Proceedings of the 8th ACM European Conference on ComputerSystems. 2013: 169-182.
[68] Grewal A, Jiang J, Lam G, et al. Recservice: distributed real-time graph processing at Twitter[C]//10th {USENIX} Workshop on Hot Topics in Cloud Computing (HotCloud 18). 2018.
[75]Prabhakaran V, Wu M, Weng X, et al. Managing largegraphs on multi-cores with graph awareness[C]//Presented as part of the 2012{USENIX} Annual Technical Conference ({USENIX}{ATC} 12). 2012: 41-52.
[76] F. Holzschuher and R. Peinl. Performance of graph query languages: Comparison of Cypher, Gremlin and native access in Neo4J. In Proceedings of the Joint EDBT/ICDT 2013 Workshops, pages 195{204, New York, NY, USA, 2013. ACM.
壁仞科技研究院作為壁仞科技的前沿研究部門，旨在研究新型智慧計算系統的關鍵技術，重點關注新型架構，先進編譯技術和設計方法學，並將逐漸拓展研究方向，探索未來智慧系統的各種可能。壁仞科技研究院秉持開放的原則，將積極投入各類產學研合作並參與開源社群的建設，為相關領域的技術進步做出自己的貢獻。
關鍵詞
問題
圖計算
圖資料
神經網路
圖計算系統
