圖（Graph）是用於表示對象之間關聯關係的一種抽象數據結構，使用頂點（Vertex）和邊（Edge）進行描述：頂點表示對象，邊表示對象之間的關係。可抽象成用圖描述的數據即為圖數據。圖計算，便是以圖作為數據模型來表達問題並予以解決的這一過程。以高效解決圖計算問題為目標的系統軟體稱為圖計算系統。
基本介紹
- 中文名：圖計算
- 外文名：Graph Processing
背景,圖計算,圖計算系統,關鍵技術,圖數據的組織,圖數據的劃分,頂點程式的調度,計算與通信模式,套用,網頁排序,社區發現,最短路徑,
背景
圖計算
將數據按照圖的方式建模可以獲得以往用扁平化的視角很難得到的結果：
·圖可以將各類數據關聯起來：將不同來源、不同類型的數據融合到同一個圖里進行分析，得到原本獨立分析難以發現的結果；
·圖的表示可以讓很多問題處理地更加高效：例如最短路徑、連通分量等等，只有用圖計算的方式才能予以最高效的解決。
然而，圖計算具有一些區別於其它類型計算任務的挑戰與特點：
·隨機訪問多：圖計算圍繞圖的拓撲結構展開，計算過程會訪問邊以及關聯的兩個頂點，但由於實際圖數據的稀疏性（通常只有幾到幾百的平均度數），不可避免地產生了大量隨機訪問；
·計算不規則：實際圖數據具有冪律分布的特性，即絕大多數頂點的度數很小，極少部分頂點的度數卻很大（例如線上社交網路中明星用戶的冬粉），這使得計算任務的劃分較為困難，十分容易導致負載不均衡。
圖計算系統
隨著圖數據規模的不斷增長，對圖計算能力的要求越來越高，大量專門面向圖數據處理的計算系統便是誕生在這樣的背景下。
Pregel由Google研發是專用圖計算系統的開山之作。Pregel提出了以頂點為中心的編程模型，將圖分析過程分析為若干輪計算，每一輪各個頂點獨立地執行各自的頂點程式，通過訊息傳遞在頂點之間同步狀態。Giraph是Pregel的一個開源實現，Facebook基於Giraph使用200台機器分析萬億邊級別的圖數據，計算一輪PageRank的用時近4分鐘。
GraphLab出自於CMU的實驗室，基於共享記憶體的機制，允許用戶使用異步的方式計算以加快某些算法的收斂速度。PowerGraph在GraphLab基礎上做了最佳化，針對實際圖數據中頂點度數的冪律分布特性，提出了頂點分割的思想，可以實現更細粒度的數據劃分，從而實現更好的負載均衡。其計算模型也被用在後續的圖計算系統上，例如GraphX。
Gemini由清華大學計算機系的團隊提出，針對已有系統的局限性，提出了以計算為中心的設計理念，通過降低分散式帶來的開銷並儘可能最佳化本地計算部分的實現，使得系統能夠在具備擴展性的同時不失高效性。針對圖計算的各個特性，Gemini在數據壓縮存儲、圖劃分、任務調度、通信模式切換等方面都提出了對應的最佳化措施，比其他知名圖計算系統的最快性能還要快一個數量級。ShenTu沿用並擴展了Gemini的編程和計算模型，能夠利用神威·太湖之光整機上千萬核的計算資源，高效處理70萬億邊的超大規模圖數據，入圍了2018年戈登·貝爾獎的決賽名單。
除了使用向外擴展的分散式圖計算系統來處理規模超出單機記憶體的圖數據，也有一些解決方案通過在單台機器上高效地使用外存來完成大規模圖計算任務，其中的代表有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則將兩種模式融合起來，根據每一輪疊代參與計算的具體情況，自適應地選擇更適合的模式。
套用
網頁排序
將網頁作為頂點，網頁之間的超連結作為邊，整個網際網路可以建模成一個非常巨大的圖（十萬億級邊）。搜尋引擎在返回結果時，除了需要考慮網頁內容與關鍵字的相關程度，還需要考慮網頁本身的質量。
PageRank是最早Google用於對網頁進行排序的算法，通過將連結看成投票來指示網頁的重要程度。PageRank的計算過程並不複雜：在首輪疊代開始前，所有頂點將自己的PageRank值設為1；每輪疊代中，每個頂點向所有鄰居貢獻自己當前PageRank值除以出邊數作為投票，然後將收到的所有來自鄰居的投票累加起來作為新的PageRank值；如此往復，直到所有頂點的PageRank值在相鄰兩輪之間的變化達到某個閾值為止。
社區發現
社交網路也是一種典型的圖數據：頂點表示人，邊表示人際關係；更廣義的社交網路可以將與人有關的實體也納入進來，例如手機、地址、公司等。社區發現是社交網路分析的一個經典套用：將圖分成若干社區，每個社區內部的頂點之間具有相比社區外部更緊密的連線關係。社區發現有非常廣泛的用途，在金融風控、國家安全、公共衛生等大量場景都有相關的套用。
標籤傳播是一種常用的社區發現算法：每個頂點的標籤即為自己的社區，初始化時設定自己的頂點編號；在隨後的每一輪疊代中，每個頂點將鄰居中出現最頻繁的標籤設定為自己新的標籤；當所有頂點相鄰兩輪之間的標籤變化少於某個閾值時則停止疊代。
最短路徑
在圖上發現頂點與頂點之間的最短路徑是一類很常見的圖計算任務，根據起始頂點與目標頂點集合的大小，又可分為單對單（一個頂點到一個頂點）、多對多（多個頂點到多個頂點）、單源（一個頂點到所有其它頂點）、多源（多個頂點到所有其它頂點）、所有點對（所有頂點到其它所有頂點）等。對於無權圖，通常使用基於BFS的算法；對於有權圖，比較常見的有SPFA算法、Bellman-Ford算法等。
最短路徑的用途十分廣泛：在知識圖譜中經常需要尋找兩個實體之間的最短關聯路徑；基於黑名單和實體之間的關聯可以發現其它頂點與黑名單之間的距離；而所有點對的最短路徑可以幫助衡量各個頂點在整個圖的拓撲結構所處的位置（中心程度）。
