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

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

1.什么是圖計算？

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

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

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

• 基于圖抽象的數(shù)據(jù)模型
• 圖數(shù)據(jù)模型并行抽象
• 圖模型系統(tǒng)優(yōu)化

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

2. 從歷史發(fā)展看圖計算

圖計算最早可追溯到 20 世紀(jì) 60 年代面向樹狀結(jié)構(gòu)的數(shù)據(jù)庫，70-80 年代出現(xiàn)面向?qū)傩詧D的模型和技術(shù)，如 LDM（邏輯數(shù)據(jù)模型）等。直到2007 年，第一款商用圖數(shù)據(jù)庫 Neo4j 公司成立，標(biāo)志著圖計算進(jìn)入了發(fā)展的階段。

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

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

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

2015年隨著數(shù)據(jù)量級迅速增長，應(yīng)用市場逐漸打開，對圖計算系統(tǒng)擴展性和效率需求不斷提高。中國圖計算領(lǐng)域?qū)W術(shù)界和產(chǎn)業(yè)界研究開始逐漸發(fā)力，發(fā)布了自己的圖計算系統(tǒng)和平臺 ，比如清華大學(xué)的Gemini等等。

近年來，隨著人工智能技術(shù)的發(fā)展， 圖神經(jīng)網(wǎng)絡(luò)也已經(jīng)在業(yè)界展露身手了。

3.從框架模型看圖計算

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

BSP模式有如下特點：

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

將處理器和路由器分開，強調(diào)了計算任務(wù)和通信任務(wù)的分離，而路由器僅僅完成點到點的消息傳遞，不提供組裝、復(fù)制和廣播等功能，既掩蓋了具體的互連網(wǎng)絡(luò)拓?fù)?，又簡化了通信協(xié)議；

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

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

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

4. 從算法看圖計算

圖算法指利用特指的頂點和邊求得答案的一種簡便方法，無向圖、有向圖和網(wǎng)絡(luò)能運用很多常用的圖算法。對于圖數(shù)據(jù)，遍歷算法（深度/廣度優(yōu)先）是其它算法的基礎(chǔ)。典型的圖算法有 PageRank、最短路徑、連通分支、極大獨立集、最小生成樹以及 Bayesian Belief Propagation 等。圖的最小生成樹在生活中常代表著最低的成本或最小的代價，常用 Prim 算法和 Kruskal 算法。社區(qū)發(fā)現(xiàn)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑也都有對應(yīng)的算法。

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

5.從計算機體系結(jié)構(gòu)看圖計算

圖計算一般都是數(shù)據(jù)驅(qū)動的計算，計算結(jié)構(gòu)無法在運行前準(zhǔn)確地進(jìn)行預(yù)測，形態(tài)上沒有明顯規(guī)律，難以高效優(yōu)質(zhì)地進(jìn)行劃分?，F(xiàn)有的緩存機制往往只能對局部性好的數(shù)據(jù)訪問提速，大量數(shù)據(jù)的存取會使處理器頻繁處于等待I/O的狀態(tài)。

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

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

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

就圖計算產(chǎn)生的功耗而言，負(fù)載變化導(dǎo)致系統(tǒng)功率波動，會出現(xiàn)峰谷交錯的情形。若增加并發(fā)任務(wù)，會改變峰谷比率并抬升功耗。一般地，對CPU的功耗而言，以計算為中心的算法平均每條指令能耗大，以遍歷為中心的算法則相反；對內(nèi)存的功耗而言，以計算為中心的算法內(nèi)存的平均能耗小，以遍歷為中心的算法則相反。

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

6.從系統(tǒng)看圖計算

依據(jù)大規(guī)模圖計算系統(tǒng)的使用場景以及計算平臺架構(gòu)的不同，可以將其分為單機內(nèi)存圖計算系統(tǒng)、單機外存圖計算系統(tǒng)、分布式內(nèi)存圖計算系統(tǒng)和分布式外存圖計算系統(tǒng)。

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

7. 從AI 看圖計算

AI 和圖計算融合產(chǎn)生的圖神經(jīng)網(wǎng)絡(luò)（GNN），是目前正在快速發(fā)展且重要的領(lǐng)域。各種實體之間的關(guān)系數(shù)據(jù)，它怎么和神經(jīng)網(wǎng)絡(luò)進(jìn)行結(jié)合？圖神經(jīng)網(wǎng)絡(luò)，利用了表示學(xué)習(xí)，通過圖的結(jié)構(gòu)先把每一個節(jié)點或者邊都用向量來表示特征，然后再進(jìn)一步地使用神經(jīng)網(wǎng)絡(luò)來處理。這就擴展了神經(jīng)網(wǎng)絡(luò)使用的范圍，把實體之間的關(guān)系也引入到 AI 的處理中。

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

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

7.1 GNN VS MLP/CNN/RNN

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

7.2 GNN VS Graph Embedding

在GNN之前已經(jīng)涌現(xiàn)出很多Graph Embedding方法，并被廣泛應(yīng)用在搜索類服務(wù)的向量召回階段，這類方法受Word2vec啟發(fā)設(shè)計，從最初的的Item2Vec到Node2Vec基于平衡同質(zhì)性和結(jié)構(gòu)性的改進(jìn)，再到MetaPath2Vec基于對圖的異構(gòu)性改進(jìn)，以及引入屬性數(shù)據(jù)緩解行為數(shù)據(jù)的稀疏性，這類方法都遵循著Skip-Gram的范式。

相比于這些方法，GNN可以結(jié)合目標(biāo)任務(wù)端到端地進(jìn)行訓(xùn)練，而Graph Embedding更像是預(yù)訓(xùn)練，其學(xué)習(xí)到的Embedding不一定與目標(biāo)任務(wù)相關(guān)，特別是在樣本規(guī)模龐大的業(yè)務(wù)場景，端到端訓(xùn)練得到的Embedding比預(yù)訓(xùn)練得到的Embedding更有效。

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

7.3 GNN VS Feature Concat & Collaborative Filtering & Proximity Loss

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

圖神經(jīng)網(wǎng)絡(luò)的設(shè)計中有個關(guān)鍵的條件要滿足就是置換不變性或者置換等變性，就是設(shè)計的函數(shù)在處理圖數(shù)據(jù)時，不受節(jié)點順序的影響，或者輸入時的順序變換域輸出的順序一致。

8. 小結(jié)

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

【參考資料】 

“人工智能之圖計算”，清華大學(xué)人工智能研究院，北京智源人工智能研究院，清華-工程院知識智能聯(lián)合研究中心，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??