面向大規模圖計算的系統最佳化（1）

摘要

圖是描述事物及事物間關聯的一種重要資料結構，它廣泛應用於多個領域。由於圖具有與其他資料結構不同的特性且圖資料規模逐年增長，而用通用性系統處理圖資料的效率低下，因此有眾多工作研究了面向圖的系統設計與最佳化，以更好地對上層應用提供支援。

本系列文章首先回顧圖的概念，並對圖演算法進行分類討論，並引出圖計算系統的基本分類（本文）；接下來，詳細討論三大類系統：基於CPU的圖計算系統、基於異構器件的圖計算系統和基於新興非馮·諾依曼器件的圖計算系統，並對相關文獻中的突出貢獻和關鍵技術進行總結（第二部分）；隨後，將圖計算系統中使用的程式設計模型進行分類與介紹，並關注工業界研究或使用的圖計算系統特點（第三部分）；最後，透過分析現有系統面臨的挑戰，指出圖計算系統的發展趨勢，以對未來研究提供借鑑作用（第四部分）。

本系列文章筆者胡靜波為清華大學清華大學電子工程系碩士生；戴國浩為清華大學電子工程系助理研究員、博士後。該文工作得到清華大學和壁仞科技研究院聯合研究專案的支援。

左中括號

引言

左中括號

隨著大資料時代的來臨，人們會面臨大量豐富多樣的資料，且資料之間往往蘊含複雜的關係。圖^[1]是一種能夠直觀地表示事物間關聯的資料結構，因而受到學術界和工業界的廣泛關注。圖在多個領域都應用廣泛，例如：社交網路^[2]、生物醫學^[3]、推薦系統^[4]等。近年來，圖的規模也在不斷擴大。據統計資料^[5]顯示，截止到2019年，包括Facebook、微信、微博在內的國內外多個社交網路平臺的月活躍使用者量（圖中的點）已經突破十億量級，使用者關係（圖中的邊）已經達到百億量級，且預計未來，使用者的規模還將持續增長。鑑於此，研究面向大規模圖計算的系統最佳化設計成為大資料時代下亟需解決的問題。

相比於其他資料結構，圖結構在計算和處理上往往更為複雜，其特點主要表現為以下幾個方面^[6]：

非結構化

圖資料通常是不規則、非結構化的，即圖中頂點的度（連線邊的數量）相差較大。以現實中應用廣泛的冪律圖為例，圖中各頂點的度呈現冪律分佈狀態，只有少部分的頂點具有較高的度，而大部分的頂點具有較低的度。這種特徵會引起資料分割槽的困難性，並降低圖計算中的並行度，使得處理圖中不同部分資料的時間不均等，儲存資料所佔用的記憶體也不同，從而帶來負載不均衡、資料傳輸開銷大等問題。
資料區域性性差

在圖計算問題中，對於少量頂點的訪問可能遍佈整個記憶體空間，且這種訪問是隨機和不可預測的。由於相關聯的資料無法保證總是在儲存時排列在一起，並順序讀取，因此圖資料的區域性性差，難以像傳統的資料結構一樣，利用CPU快取等策略進行加速，從而加大了圖資料系統最佳化的難度。
高傳輸計算比

圖計算任務中資料傳輸相比於計算的比例較高。以圖1.1中的頂點5為例，其計算過程如下：首先，頂點1，2，3，4將自身值傳輸給頂點5，頂點5進行簡單運算後，再將值傳輸給頂點6，7，8，9。由上述階段可知，其輸入輸出的資料傳輸部分會引起記憶體訪問延遲，從而成為效能瓶頸。這也是圖計算問題與傳統計算密集型問題的不同點之一。

圖1.1圖計算特點之高傳輸計算比示意圖

複雜的資料依賴性

在圖資料結構中，頂點和邊具有不同的連線關係，而圖任務又高度依賴於這些連線關係，因此，在任務執行過程中，一部分頂點和邊可能被頻繁訪問，而另一些頂點和邊可能不會被訪問到或者只訪問少量的次數。圖結構中存在的複雜資料依賴性使得我們無法在任務中準確預測資料訪問的路徑和次數，同時也無法判斷限制其並行性的計算結構。

為了更好地解決上述圖計算中存在的問題，併為未來大規模圖計算系統的研究與發展提供借鑑思路，我們詳細地調研了眾多圖計算系統，提煉出其關鍵技術點並進行不同層面的分類，如圖3.1所示。特別地，我們並非只關注圖計算系統中的某一分支，而是對整體進行了分析。另外，我們著重關注了工業界研究和使用的圖計算系統，它們所屬阿里巴巴、Facebook、IBM、Twitter等諸多知名網際網路公司。例如，2015年IBM提出了SQLGraph^[67]，它利用關係和非關係儲存屬性圖,在查詢效能上比Neo4j^[76]快2-8倍。2018年，Twitter提出了RecService^[68]，一種分散式即時圖處理引擎，可在Twitter上處理數十億的即時推薦任務。2019年，Facebook提出大規模圖嵌入系統Pytorch-BigGraph^[69]，它使用的分割槽方案能減少88%的記憶體消耗，且分散式訓練時間減少了4倍。同年，阿里巴巴提出一個大規模圖神經網路平臺——AliGraph^[63]，在真實資料集上的實驗表明，相比於通用型分散式圖計算系統PowerGraph^[28]，AliGraph^[63]的圖形構建速度提高了一個數量級，且已經部署在實際電子商務平臺（淘寶）上，以進行產品推薦。2020年，阿里巴巴達摩院開源全球首個一站式超大規模分散式圖計算平臺GraphScope^[64]，其技術層面結合了多項已發表的科研成果，相比於多個開源的圖計算系統，GraphScope^[64]有一個數量級以上的加速。進一步地，我們透過提煉上述工業界中圖計算系統的共性以尋求系統創新性和實用性的統一。在此基礎上，我們總結出了現存圖計算系統中的開放問題和未來可能的發展趨勢。我們的主要貢獻如下：

對圖計算系統進行了詳細的調研，並總結了代表性系統的關鍵技術。按照基於CPU的圖計算系統、基於異構器件的圖計算系統和基於新興非馮·諾依曼器件的圖計算系統對調研的圖計算系統進行了分類。
將現有圖計算系統中使用的主要程式設計模型劃分為三類：以頂點為中心、以邊為中心和以子圖為中心。總結了各個模型的特點，及其適用的圖演算法和應用。
總結了工業界研究或使用的圖計算系統，以明確目前商用圖系統的特點，並探究何種系統具有更強的實用性，以增強未來研究的實際價值，尋求創新性與實用性的統一。
基於現有系統所存在的問題，提出了4個圖計算系統的發展趨勢，以對未來研究提供借鑑作用。例如，面向特定應用的系統設計、異構硬體、動態圖等。

左中括號

圖相關概念與圖演算法

左中括號

在本節中，我們首先介紹圖在數學上的定義，這是與圖相關問題的基礎。接著，我們會介紹圖在儲存中的幾種不同方式。最後，我們將圖演算法進行了分類，並進行簡要分析。

2.1 圖的定義

圖是由頂點和邊組成的資料結構，表示為G(V,E)。其中，G表示一個圖，V表示圖中頂點的集合，E為圖中邊的集合，

，即邊連線了兩個頂點。根據圖中邊是否有向，圖又進一步劃分為有向圖和無向圖，在有向圖中，邊從源頂點指向目標頂點，無向圖也可理解為有向圖的一種特例。

2.2 圖的儲存

在圖這種資料結構中，頂點和邊都具有相對位置關係，難以用單一的順序結構進行儲存。一種直接的想法是利用二維鄰接矩陣進行圖資料的儲存，即行和列均表示圖的頂點序號，陣列中的元素代表兩個頂點間是否存在連線關係或邊的權重。但圖結構往往具有稀疏特性，即在上述鄰接矩陣中會存在大量0元素，從而引起儲存空間的浪費。

鄰接表可以有效地解決上述問題，是一種常見的儲存方式。在鄰接表中，每一行代表不同的頂點，一列代表與該行所指頂點相連線的鄰居節點。當然，還有許多變形的儲存結構，例如行壓縮儲存格式CSR、座標壓縮儲存格式COO^[7]等，本文不再一一詳細介紹，感興趣的讀者可參考其他文獻。

2.3 圖演算法

本文按照計算特徵的不同，將現有圖演算法主要分為以下三類：圖遍歷、圖挖掘和圖神經網路，並分別對其特點和應用進行了分析。

2.3.1 圖遍歷演算法

圖遍歷演算法經常用於網頁排序、計算機網路路由等方面，其計算模型為在迭代過程中每個頂點會根據鄰居節點值來更新自身節點值，再透過圖的連線關係擴散到其他節點，其中，更新節點值的計算一般為輕量級的。典型的圖遍歷演算法有PageRank^[8]、寬度優先搜尋(BFS)^[9]等。

2.3.2 圖挖掘演算法

圖挖掘演算法的目標是搜尋、匹配圖中的特定序列或模式，其在金融風險管理、社交網路分析中都有所應用。相比於圖遍歷演算法，圖挖掘演算法的計算量和儲存量要大得多，由於候選的子圖存在多種組合，因此，其計算和空間複雜度通常以超線性的方式增長。典型的圖挖掘演算法有頻繁子圖挖掘^[10]、圖聚類^[11]等。

2.3.3 圖神經網路演算法

圖神經網路是近年來興起的一種圖演算法，其融合了圖結構和神經網路，能夠捕獲元素間潛在的複雜而豐富的資料關係，在推薦系統等應用場景中具有優異的效果。相較於傳統的圖演算法，圖神經網路在計算節點向量值，獲取節點資訊時的計算複雜度更高，從而耗費更長的時間。典型的圖神經網路演算法有圖卷積網路(GCN)^[12]、圖注意力網路(GAT)^[13]等。

左中括號

圖計算系統研究現狀

左中括號

在本節中，我們將調研的大規模圖計算系統分為以下三類：基於CPU的圖計算系統、基於異構器件的圖計算系統和基於新興非馮·諾依曼器件的圖計算系統。在每一類中，我們會選取有代表性的系統進行介紹，提取其關鍵技術，並分析不同系統間的優缺點。圖3.1展示了圖計算系統的時間線表示。

圖3.1 圖計算系統的分類及時間線表示

本系列文章的下一部分將詳細討論各種型別的圖計算系統。

作者簡介

胡靜波，本科就讀於西安電子科技大學，目前為清華大學電子工程系碩士生，專業為電子與通訊工程，自2019年入學至今，一直跟隨汪玉教授和戴國浩博士後進行大規模圖計算方面的研究，且已經發表有關通用性圖取樣框架的論文一篇。

戴國浩，現清華大學電子工程系助理研究員、博士後，分別於2019年和2014年在清華大學電子工程系獲得博士與學士學位。主要研究方向為大規模圖計算、異構計算、存算一體、虛擬化等，曾獲ASPDAC 2019最佳論文獎、DATE 2018最佳論文提名。

參考文獻

[1] Graph theory and sparse matrix computation[M]. Springer Science & Business Media, 2012.

[2] Leão J C, Brandão M A, de Melo P O S V, et al. Who is really in my social circle?[J]. Journal of Internet Services and Applications, 2018, 9(1): 20.

[3] Eckhardt M, Zhang W, Gross A M, et al. Multiple routes to oncogenesis are promoted by the human papillomavirus–host protein network[J]. Cancer discovery, 2018, 8(11): 1474-1489.

[4] Wang J, Huang P, Zhao H, et al. Billion-scale commodity embedding for e-commerce recommendation in alibaba[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 839-848.

[5] Enberg J. Global social network users 2019[Z]. https://www.emarketer.com/content/global-social-network-users.

[6] Liu N , Li D S , Zhang Y M , et al. Large-scale graph processing systems: a survey[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(3):384-404.

[7]王海文,羅明山.一種改進的圖儲存結構的實現及效能分析[J].大眾科技,2012,14(05):6-7.

[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.

[9] M. Kurant, A. Markopoulou and P. Thiran, “On the bias of BFS (Breadth First Search).” 2010 22nd International Teletraffic Congress (lTC 22), Amsterdam, 2010, pp. 1-8.

[10] Xifeng Yan and Jiawei Han. 2002. gspan: Graph-based substructure pattern mining. In IEEE International Conference on Data Mining. 721–724.

[11] Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph clustering based on structural/attribute similarities. Proceedings of the VLDB Endowment 2, 1 (2009), 718–729.

[12] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

[13] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.

[28] Gonzalez JE, Low Y, Gu H, et al., 2012. PowerGraph: distributed graph-parallel computation on natural graphs. Proc 10th USENIX Conf on Operating Systems Design and Implementation, p.17-30.

[63] Yang H. Aligraph: A comprehensive graph neural network platform[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 3165-3166.

[64] Zhengping Qian, et al. GraphScope: A System for Interactive Analysis on Distributed Graphs Using a High-Level Language. https://github.com/alibaba/GraphScope

[67] Sun W, Fokoue A, Srinivas K, et al. Sqlgraph: An efficient relational-based property graph store[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015: 1887-1901.

[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.

[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.

往期推薦

1、貝葉斯方法與深度學習的結合及應用（1）

2、貝葉斯方法與深度學習的結合及應用（2）

3、加入圖卷積的多智慧體強化學習