圖計算

大數據時代，數據之間存在關聯關係。由於圖是表達事物之間複雜關聯關係的組織結構，因此現實生活中的諸多應用場景都需要用到圖，例如，淘寶用户好友關係圖、道路圖、電路圖、病毒傳播網、國家電網、文獻網、社交網和知識圖譜。

為了從這些數據之間的關聯關係中獲取有用信息，大量圖算法層出不窮。它們通過對大型圖數據的迭代處理，獲得圖數據中隱藏的重要信息。圖計算作為下一代人工智能的核心技術，已被廣泛應用於醫療、教育、軍事、金融等多個領域，並備受各國政府、全球研發機構和巨頭公司關注，目前已成為全球科技競爭新的戰略制高點。 ^[7] 

·圖可以將各類數據關聯起來：將不同來源、不同類型的數據融合到同一個圖裏進行分析，得到原本獨立分析難以發現的結果；

·圖的表示可以讓很多問題處理地更加高效：例如最短路徑、連通分量等等，只有用圖計算的方式才能予以最高效的解決。

然而，圖計算具有一些區別於其它類型計算任務的挑戰與特點：

·隨機訪問多：圖計算圍繞圖的拓撲結構展開，計算過程會訪問邊以及關聯的兩個頂點，但由於實際圖數據的稀疏性（通常只有幾到幾百的平均度數），不可避免地產生了大量隨機訪問；

·計算不規則：實際圖數據具有冪律分佈的特性，即絕大多數頂點的度數很小，極少部分頂點的度數卻很大（例如在線社交網絡中明星用户的粉絲），這使得計算任務的劃分較為困難，十分容易導致負載不均衡。

隨着圖數據規模的不斷增長，對圖計算能力的要求越來越高，大量專門面向圖數據處理的計算系統便是誕生在這樣的背景下。

Pregel由Google研發是專用圖計算系統的開山之作 ^[1]  。Pregel提出了以頂點為中心的編程模型，將圖分析過程分析為若干輪計算，每一輪各個頂點獨立地執行各自的頂點程序，通過消息傳遞在頂點之間同步狀態。Giraph是Pregel的一個開源實現，Facebook基於Giraph使用200台機器分析萬億邊級別的圖數據，計算一輪PageRank的用時近4分鐘 ^[2]  。

GraphLab出自於CMU的實驗室，基於共享內存的機制，允許用户使用異步的方式計算以加快某些算法的收斂速度。PowerGraph在GraphLab基礎上做了優化，針對實際圖數據中頂點度數的冪律分佈特性，提出了頂點分割的思想，可以實現更細粒度的數據劃分，從而實現更好的負載均衡 ^[3]  。其計算模型也被用在後續的圖計算系統上，例如GraphX。

儘管上述的這些圖計算系統相比MapReduce、Spark等在性能上已經有了顯著的性能提升，但是它們的計算效率依然非常低下，甚至不如精心優化的單線程程序 ^[4]  。

Gemini由清華大學計算機系的團隊提出，針對已有系統的侷限性，提出了以計算為中心的設計理念，通過降低分佈式帶來的開銷並儘可能優化本地計算部分的實現，使得系統能夠在具備擴展性的同時不失高效性 ^[5]  。針對圖計算的各個特性，Gemini在數據壓縮存儲、圖劃分、任務調度、通信模式切換等方面都提出了對應的優化措施，比其他知名圖計算系統的最快性能還要快一個數量級。ShenTu沿用並擴展了Gemini的編程和計算模型，能夠利用神威·太湖之光整機上千萬核的計算資源，高效處理70萬億邊的超大規模圖數據，入圍了2018年戈登·貝爾獎的決賽名單 ^[6]  。

除了使用向外擴展的分佈式圖計算系統來處理規模超出單機內存的圖數據，也有一些解決方案通過在單台機器上高效地使用外存來完成大規模圖計算任務，其中的代表有GraphChi、X-Stream、FlashGraph、GridGraph、Mosaic等。

由於實際圖的稀疏性，圖計算系統通常使用稀疏矩陣的存儲方法來表示圖數據，其中最常用的兩種是CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column），分別按行（列）存儲每行（列）非零元所在列（行），每一行則（列）對應了一個頂點的出邊（入邊）。

將一個大圖劃分為若干較小的子圖，是很多圖計算系統都會使用的擴展處理規模的方法；此外，圖劃分還能增強數據的局部性，從而降低訪存的隨機性，提升系統效率。

對於分佈式圖計算系統而言，圖劃分有兩個目標：

(1) 每個子圖的規模儘可能相近，獲得較為均衡的負載。

(2) 不同子圖之間的依賴（例如跨子圖的邊）儘可能少，降低機器間的通信開銷。

圖劃分有按照頂點劃分和按照邊劃分兩種方式，它們各有優劣：

(1) 頂點劃分將每個頂點鄰接的邊都放在一台機器上，因此計算的局部性更好，但是可能由於度數的冪律分佈導致負載不均衡。

(2) 邊劃分能夠最大程度地改善負載不均衡的問題，但是需要將每個頂點分成若干副本分佈於不同機器上，因此會引入額外的同步/空間開銷。

所有的類Pregel系統採用的均為頂點劃分的方式，而PowerGraph/GraphX採用的是邊劃分的方式。Gemini採用了基於頂點劃分的方法來避免引入過大的分佈式開銷；但是在計算模式上卻借鑑了邊劃分的思想，將每個頂點的計算分佈到多台機器上分別進行，並儘可能讓每台機器上的計算量接近，從而消解頂點劃分可能導致的負載不均衡問題。

在以頂點為中心的圖計算模型中，每個頂點程序可以並行地予以調度。大部分圖計算系統採用基於BSP模型的同步調度方式，將計算過程分為若干超步（每個超步通常對應一輪迭代），每個超步內所有頂點程序獨立並行地執行，結束後進行全局同步。頂點程序可能產生髮送給其它頂點的消息，而通信過程通常與計算過程分離。

同步調度容易產生的問題是：

(1) 一旦發生負載不均衡，那麼最慢的計算單元會拖慢整體的進度。

(2) 某些算法可能在同步調度模型下不收斂。

為此，部分圖計算系統提供了異步調度的選項，讓各個頂點程序的執行可以更自由，例如：每個頂點程序可以設定優先級，讓優先級高的頂點程序能以更高的頻率執行，從而更快地收斂。

然而，異步調度在系統設計上引入了更多的複雜度，例如數據一致性的維護，消息的聚合等等，很多情況下的效率並不理想。因此，大多數圖計算系統採用的還是同步的調度方式；少數支持異步計算的系統也默認使用同步方式進行調度。

圖計算系統使用的通信模式主要分為兩種，推動（Push）和拉取（Pull）：

(1) 推動模式下每個頂點沿着邊向鄰居頂點傳遞消息，鄰居頂點根據收到的消息更新自身的狀態。所有的類Pregel系統採用的幾乎都是這種計算和通信模式。

(2) 拉取模式通常將頂點分為主副本和鏡像副本，通信發生在每個頂點的兩類副本之間而非每條邊連接的兩個頂點之間。GraphLab、PowerGraph、GraphX等採用的均為這種模式。

除了通信的模式有所區別，推動和拉取在計算上也有不同的權衡：

(1) 推動模式可能產生數據競爭，需要使用鎖或原子操作來保證狀態的更新是正確的。

(2) 拉取模式儘管沒有競爭的問題，但是可能產生額外的數據訪問。

Gemini則將兩種模式融合起來，根據每一輪迭代參與計算的具體情況，自適應地選擇更適合的模式。

將網頁作為頂點，網頁之間的超鏈接作為邊，整個互聯網可以建模成一個非常巨大的圖（十萬億級邊 ^[6]  ）。搜索引擎在返回結果時，除了需要考慮網頁內容與關鍵詞的相關程度，還需要考慮網頁本身的質量。

PageRank是最早Google用於對網頁進行排序的算法，通過將鏈接看成投票來指示網頁的重要程度。PageRank的計算過程並不複雜：在首輪迭代開始前，所有頂點將自己的PageRank值設為1；每輪迭代中，每個頂點向所有鄰居貢獻自己當前PageRank值除以出邊數作為投票，然後將收到的所有來自鄰居的投票累加起來作為新的PageRank值；如此往復，直到所有頂點的PageRank值在相鄰兩輪之間的變化達到某個閾值為止。

社交網絡也是一種典型的圖數據：頂點表示人，邊表示人際關係；更廣義的社交網絡可以將與人有關的實體也納入進來，例如手機、地址、公司等。社區發現是社交網絡分析的一個經典應用：將圖分成若干社區，每個社區內部的頂點之間具有相比社區外部更緊密的連接關係。社區發現有非常廣泛的用途，在金融風控、國家安全、公共衞生等大量場景都有相關的應用。

標籤傳播是一種常用的社區發現算法：每個頂點的標籤即為自己的社區，初始化時設置自己的頂點編號；在隨後的每一輪迭代中，每個頂點將鄰居中出現最頻繁的標籤設置為自己新的標籤；當所有頂點相鄰兩輪之間的標籤變化少於某個閾值時則停止迭代。

在圖上發現頂點與頂點之間的最短路徑是一類很常見的圖計算任務，根據起始頂點與目標頂點集合的大小，又可分為單對單（一個頂點到一個頂點）、多對多（多個頂點到多個頂點）、單源（一個頂點到所有其它頂點）、多源（多個頂點到所有其它頂點）、所有點對（所有頂點到其它所有頂點）等。對於無權圖，通常使用基於BFS的算法；對於有權圖，比較常見的有SPFA算法、Bellman-Ford算法等。

最短路徑的用途十分廣泛：在知識圖譜中經常需要尋找兩個實體之間的最短關聯路徑；基於黑名單和實體之間的關聯可以發現其它頂點與黑名單之間的距離；而所有點對的最短路徑可以幫助衡量各個頂點在整個圖的拓撲結構所處的位置（中心程度）。