好的軟件不是靠程序分析、查錯查出來的，而是由正確的人構建出來的。

圖成為日益重要的運算對象，圖結構是對群體關系的一種抽象，可以描述豐富的對象和關系。圖計算的核心是如何將數據建模為圖結構以及如何將問題的解法轉化為圖結構上的計算問題，當問題涉及到關聯分析時，圖計算往往能夠使得問題的解法很自然地表示為一系列對圖結構操作和計算的過程。例如，使用基于網頁鏈接的圖結構的PageRank算法得到網頁權重，作為搜索引擎排序的參考，利用圖結構的用戶行為數據來得到精確的群體偏好分析和個性化產品推薦結果。

1.什么是圖計算？

圖計算是研究人類世界的事物和事物之間的關系，對其進行描述、刻畫、分析和計算的一門技術。這里的圖是“graph”，而不是圖“image”，源自于數學中的圖論（graph theory）。

圖是一種最為靈活的連接方式，讓實體之間可以不受限制地連接。圖計算不僅僅只是一個技術，更是一種理解世界的方式。圖數據可以很好地描述事物之間的聯系，包括描述聯系的方向和屬性。從數據結構上看，圖是對事物之間關系的一種原生表達。在某種程度上，關系數據庫應該叫表數據庫，而圖數據庫反而應該叫關系數據庫。廣義的圖計算是指基于圖數據來做各種各樣的處理，包括了圖數據庫。

圖計算技術解決了傳統的計算模式下關聯查詢的效率低、成本高的問題，在問題域中對關系進行了完整的刻畫，并且具有豐富、高效和敏捷的數據分析能力，其特征有如下：

• 基于圖抽象的數據模型
• 圖數據模型并行抽象
• 圖模型系統優化

對于圖計算而言，性能成本、容錯機制以及可拓展性都是非常重要的。

2. 從歷史發展看圖計算

圖計算最早可追溯到 20 世紀 60 年代面向樹狀結構的數據庫，70-80 年代出現面向屬性圖的模型和技術，如 LDM（邏輯數據模型）等。直到2007 年，第一款商用圖數據庫 Neo4j 公司成立，標志著圖計算進入了發展的階段。

圖計算研究真正開始的標志是 2004 年 Google 開發出面向大數據并行處理的計算模型MapReduce，這一模型的推出給大數據并行處理帶來了巨大的革命性影響。隨后，2006 年Apache Hadoop 團隊引入了 Hadoop 分布式文件系統（HDFS）以及新的 Hadoop MapReduce框架。2009 年，加州大學伯克利分校 AMP Lab 開發出 Spark 系統。

從2010年開始，大規模分布式架構、多模態支持、圖查詢語言設計等圖計算研究方向逐漸受到關注。Google 提出了 Pregel，一個針對圖算法特點設計的分布式圖計算系統，遵循 BSP 運算模型；之后 CMU Select 實驗室 GraphLab 項目組提出了GAS 運算模型。。雖然pregel 和 GraphLab 都是對于復雜機器學習計算的處理框架，用于迭代型（iteration）計算，但是二者的實現方法卻采取了不同的路徑：Pregel 是基于大塊的消息傳遞機制，GraphLab 是基于內存共享機制，對后續其他圖計算系統的設計都產生了深遠的影響。

Google在2012年5月提出了知識圖譜的概念，這是一種信息間全新的連接方式，其基本組成單位是“實體—關系—實體”三元組，實體之間通過關系相互聯結，構成網狀的知識結構。知識圖譜能夠成立的核心是計算機的知識推理機制，圖計算為其提供了重要的底層技術支持。

2015年隨著數據量級迅速增長，應用市場逐漸打開，對圖計算系統擴展性和效率需求不斷提高。中國圖計算領域學術界和產業界研究開始逐漸發力，發布了自己的圖計算系統和平臺 ，比如清華大學的Gemini等等。

近年來，隨著人工智能技術的發展， 圖神經網絡也已經在業界展露身手了。

3.從框架模型看圖計算

圖計算的框架基本上都遵循BSP(Bulk Synchronous Parallell)的計算模式。BSP模式批量同步(bulk synchrony)機制，其獨特之處在于超步(superstep)概念的引入。一次計算過程由一系列全局超步組成，每一個超步包含并行計算(local computation)、全局通信(非本地數據通信)以及柵欄同步(等待通信行為結束)三個階段。

BSP模式有如下特點：

將計算劃分為一個一個的超步(superstep)，有效避免死鎖;

將處理器和路由器分開，強調了計算任務和通信任務的分離，而路由器僅僅完成點到點的消息傳遞，不提供組裝、復制和廣播等功能，既掩蓋了具體的互連網絡拓撲，又簡化了通信協議；

采用同步方式以硬件實現的全局同步和可控的粗粒度級，執行緊耦合同步式并行算法。

一些有代表性的圖計算框架如下：

• Neo4j-APOC ：在圖數據庫的基礎上，支持一些基本圖算法，分布式版本不開源。
• Pregel ：Google 在 2009 年提出，是圖計算模型的開山祖師，后續很多工作都受到它的思想影響。不開源。
• Giraph ：Facebook 基于 Pregel 思想的開源實現。
• Gemini ：清華大學基于 Pregel 思想進行了多項改進的實現，性能優秀。僅提供免費 Demo，商業版不開源。
• KnightKing ：針對 Walker 游走類算法專門設計的圖計算框架，不具有通用性。
• GraphX ：Apache 基金會基于 Spark 實現的圖計算框架，社區活躍度較高。
• GraphLab（PowerGraph）：商業軟件，不開源。已被蘋果收購。
• Plato ：騰訊基于 Gemini 和 KnightKing 思想的 C++ 開源實現，是一款高性能、可擴展、易插拔的圖計算框架。

4. 從算法看圖計算

圖算法指利用特指的頂點和邊求得答案的一種簡便方法，無向圖、有向圖和網絡能運用很多常用的圖算法。對于圖數據，遍歷算法（深度/廣度優先）是其它算法的基礎。典型的圖算法有 PageRank、最短路徑、連通分支、極大獨立集、最小生成樹以及 Bayesian Belief Propagation 等。圖的最小生成樹在生活中常代表著最低的成本或最小的代價，常用 Prim 算法和 Kruskal 算法。社區發現、最短路徑、拓撲排序、關鍵路徑也都有對應的算法。

圖算法包括了 搜索、匹配、分類、評估等多樣化數據分析技術，從算法結構維度大約可以分成兩類：以遍歷為中心的算法和以計算為中心的算法。以遍歷為中心的算法，需要以特定方式從特定頂點遍歷圖，存在著大量的隨機訪問。以計算為中心的算法，需要在一個迭代周期中有大量的運算進行，數據局部性相對較好。

5.從計算機體系結構看圖計算

圖計算一般都是數據驅動的計算，計算結構無法在運行前準確地進行預測，形態上沒有明顯規律，難以高效優質地進行劃分?，F有的緩存機制往往只能對局部性好的數據訪問提速，大量數據的存取會使處理器頻繁處于等待I/O的狀態。

圖計算的負載具有復雜性，沒有單一最具代表性的圖計算負載。連接頂點的邊，只是無數可能連接中的一個小子集，存在高度不規則性。在圖計算的過程中，讀寫的時空局部性難以掌握，帶寬占用情況難以預測。

大多數算法對內存帶寬的占用可能不到50%，是什么限制了內存帶寬的利用呢？處理器需獲取指令， 指令窗口間存在空間，寄存器操作數需要等待，直到操作數可用，相關依賴才會解除。由于指令命中率較高，可能導致內存層面的并行度下降，難以充分利用平臺的內存帶寬。較低的緩存數據使用比又意味著應用難以從空間局 部性中獲利，數據預取策略會失效。數據預取一般對提升性能有幫助，但也會生成大量無用的預取操作。對于內存帶寬或者說緩存容量有限的應用來說，數據預取可能造成一定資源浪費。在多線程計算的情況下，若觸發延遲較高的遠程內存訪問，也會抵消多線程的收益。

圖計算需要怎樣的處理器核心呢？一般地，會采用許多小計算核心加高線程數的架構，適合處理傳統多核處理器所不擅長的大圖計算。在多圖并發計算的時候，有共享分配與獨占分配兩種策略。共享分配策略指將 m 項請求中的每一項都使用 n 個邏輯核心并行處理，由OS管理不同請求在邏輯核心上的切換。獨占分配策略指為每一項請求分配 n/m 個邏輯核心，使邏輯核心不需要在任務間切換。獨占分配策略更適合并發圖計算，獨占通?？蓽p少相同并發請求下整體的運行時間。重排序緩存競爭度低可能是獨占策略在并發圖計算場景中優于共享策略的原因。

就圖計算產生的功耗而言，負載變化導致系統功率波動，會出現峰谷交錯的情形。若增加并發任務，會改變峰谷比率并抬升功耗。一般地，對CPU的功耗而言，以計算為中心的算法平均每條指令能耗大，以遍歷為中心的算法則相反；對內存的功耗而言，以計算為中心的算法內存的平均能耗小，以遍歷為中心的算法則相反。

大多基于圖計算的應用都是內存受限的，但也存在受核心部件限制帶來的內存利用率不足。足夠的活躍線 程創造并發訪問，或可提升利用率。更多線程是需要的，但由于線程間不均衡性，可能使用起來效率不高，需要提供更可擴展的并行策略，來優化多核處理器的高帶寬內存使用。功耗和能耗行為從指令角度和頂點計算角度來看都各有不同，需要精準的功耗管理方法，粗放型調整恐難起到作用。

6.從系統看圖計算

依據大規模圖計算系統的使用場景以及計算平臺架構的不同，可以將其分為單機內存圖計算系統、單機外存圖計算系統、分布式內存圖計算系統和分布式外存圖計算系統。

單機內存圖處理系統就是圖處理系統運行在單機環境，并且將圖數據全部緩沖到內存當中。單機外存圖處理系統就是圖處理系統運行在單機環境，并且通過計算將圖數據不斷地與內存和磁盤進行交互的高效圖算法。分布式內存系統就是圖處理系統運行在分布式集群環境，并且所有的圖數據加載到內存當中。分布式外存圖計算系統將單機外存系統（Singlemachine out-of-core systems）拓展為集群，能夠處理邊的數量級為 trillion 的圖。

7. 從AI 看圖計算

AI 和圖計算融合產生的圖神經網絡（GNN），是目前正在快速發展且重要的領域。各種實體之間的關系數據，它怎么和神經網絡進行結合？圖神經網絡，利用了表示學習，通過圖的結構先把每一個節點或者邊都用向量來表示特征，然后再進一步地使用神經網絡來處理。這就擴展了神經網絡使用的范圍，把實體之間的關系也引入到 AI 的處理中。

圖神經網絡可以看作一個圖特征的學習過程，比如節點的代表特征或者圖級的代表特征，一般以圖的屬性和圖的結構作為輸入，輸出一組更新后的節點表示。一般這個過程也稱作圖濾波操作。圖濾波會更新節點特征但不會改變圖的結構。圖神經網絡的發展是從不同的理論動機中發展出來的，比如，將GNN看作為非歐距離的卷積推廣，那它是基于圖信號發展起來的；現在大多的GNN基于神經消息傳遞方法是通過類比圖模型中概率推理的消息傳遞算法提出的。

不管是譜方法還是基于空間的思想，圖神經網絡最后都可統一到基于消息傳遞的框架下。GNN消息傳遞框架基本思想是在每次迭代時，每個節點都聚合其鄰居節點的信息。隨著迭代次數的增加，每個節點包含圖上更大范圍的信息。比如，經過k次迭代后，中心節點可以獲取其k跳鄰域的信息。其關鍵思想是基于圖結構和已知的特征信息生成節點表示。GNN利用了圖上的結構和節點特征信息，生成深層的嵌入表示，而傳統的圖嵌入方法只利用了圖的結構信息，通過查表的方式生成層嵌入。

7.1 GNN VS MLP/CNN/RNN

圖數據中結點鄰居具有兩個特點，一是數量不定，二是順序不定，因此MLP/CNN/RNN無法直接處理這樣的非歐式數據而只能用GNN建模。實際上，可以將GNN看做一種更加泛化的模型，例如，RNN相當于線性圖上的GNN，而Transformer相當于完全圖上的GNN。

7.2 GNN VS Graph Embedding

在GNN之前已經涌現出很多Graph Embedding方法，并被廣泛應用在搜索類服務的向量召回階段，這類方法受Word2vec啟發設計，從最初的的Item2Vec到Node2Vec基于平衡同質性和結構性的改進，再到MetaPath2Vec基于對圖的異構性改進，以及引入屬性數據緩解行為數據的稀疏性，這類方法都遵循著Skip-Gram的范式。

相比于這些方法，GNN可以結合目標任務端到端地進行訓練，而Graph Embedding更像是預訓練，其學習到的Embedding不一定與目標任務相關，特別是在樣本規模龐大的業務場景，端到端訓練得到的Embedding比預訓練得到的Embedding更有效。

GNN的層級網絡結構方便與其他深度學習技術結合，例如GCN+Attentinotallow=GAT。GNN可以適用Inductive的任務，即當圖的結構發生變化后，加入了一些新的結點，如果是Graph Embedding方法就需要重新訓練模型，而GNN可以使用類似GraphSage Node-Wise Sampling的方式，使用已經訓練好的模型直接對新的結點進行推斷，在消息傳遞的過程中可以使用多種特征。

7.3 GNN VS Feature Concat & Collaborative Filtering & Proximity Loss

Feature Concat表示將特征拼接到一起然后通過特征交叉可以學習到一階的屬性關聯信息。Collaborative Filtering也可以通過用戶歷史行為學習到一階的行為關聯信息。Proximity Loss表示在損失函數中加入正則項使得相鄰的結點更相似，但是一方面它是一種隱式的方式，另一方面想確保學習到高階的相似關系，就需要加入更復雜的K階正則項，這也是GCN提出時的出發點之一。相比這三種方法，GNN可以通過堆疊多層顯示地學習高階的關聯信息。

圖神經網絡的設計中有個關鍵的條件要滿足就是置換不變性或者置換等變性，就是設計的函數在處理圖數據時，不受節點順序的影響，或者輸入時的順序變換域輸出的順序一致。

8. 小結

圖是一種最為靈活的連接方式，讓實體之間可以不受限制地連接。圖計算是研究在大量數據中如何高效計算、存儲并管理圖數據等問題的領域，可以應用于相當廣泛的業務場景，如資本市場風險管理、生命科學研究、醫療保健交付、監控和應對道路事故、智能基礎設施管理扽等。高效處理大規模數據的圖計算，能推動社交網絡分析、語義 web 分析、生物信息網絡分析、自然語言處理等新興應用領域的發展。

【參考資料】 

“人工智能之圖計算”，清華大學人工智能研究院，北京智源人工智能研究院，清華-工程院知識智能聯合研究中心，2019-2

??https://zhuanlan.zhihu.com/graphComputing??

??https://www.zhihu.com/column/c_1496512305013219328??

??https://www.aminer.cn/oag2019??

??https://www.oreilly.com/library/view/graph-algorithms/9781492047674??