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

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

1.什么是圖計(jì)算？

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

圖是一種最為靈活的連接方式,，讓實(shí)體之間可以不受限制地連接。圖計(jì)算不僅僅只是一個(gè)技術(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ù)庫,。廣義的圖計(jì)算是指基于圖數(shù)據(jù)來做各種各樣的處理，包括了圖數(shù)據(jù)庫,。

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

• 基于圖抽象的數(shù)據(jù)模型

• 圖數(shù)據(jù)模型并行抽象

• 圖模型系統(tǒng)優(yōu)化

對于圖計(jì)算而言,，性能成本,、容錯(cuò)機(jī)制以及可拓展性都是非常重要的。

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

圖計(jì)算最早可追溯到 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ì)算進(jìn)入了發(fā)展的階段。

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

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

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

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

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

3.從框架模型看圖計(jì)算

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

BSP模式有如下特點(diǎn)：

1. 將計(jì)算劃分為一個(gè)一個(gè)的超步(superstep),，有效避免死鎖;

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

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

一些有代表性的圖計(jì)算框架如下：

• Neo4j-APOC ：在圖數(shù)據(jù)庫的基礎(chǔ)上,，支持一些基本圖算法，分布式版本不開源,。

• Pregel ：Google 在 2009 年提出,，是圖計(jì)算模型的開山祖師,，后續(xù)很多工作都受到它的思想影響。不開源,。

• Giraph ：Facebook 基于 Pregel 思想的開源實(shí)現(xiàn),。

• Gemini ：清華大學(xué)基于 Pregel 思想進(jìn)行了多項(xiàng)改進(jìn)的實(shí)現(xiàn)，性能優(yōu)秀,。僅提供免費(fèi) Demo,，商業(yè)版不開源。

• KnightKing ：針對 Walker 游走類算法專門設(shè)計(jì)的圖計(jì)算框架,，不具有通用性,。

• GraphX ：Apache 基金會(huì)基于 Spark 實(shí)現(xiàn)的圖計(jì)算框架，社區(qū)活躍度較高,。

• GraphLab（PowerGraph）：商業(yè)軟件,，不開源。已被蘋果收購,。

• Plato ：騰訊基于 Gemini 和 KnightKing 思想的 C++ 開源實(shí)現(xiàn),，是一款高性能、可擴(kuò)展,、易插拔的圖計(jì)算框架,。

4. 從算法看圖計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

7. 從AI 看圖計(jì)算

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

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

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

7.1 GNN VS MLP/CNN/RNN

圖數(shù)據(jù)中結(jié)點(diǎn)鄰居具有兩個(gè)特點(diǎn),，一是數(shù)量不定，二是順序不定,，因此MLP/CNN/RNN無法直接處理這樣的非歐式數(shù)據(jù)而只能用GNN建模,。實(shí)際上，可以將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è)計(jì),，從最初的的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+Attention=GAT,。GNN可以適用Inductive的任務(wù),，即當(dāng)圖的結(jié)構(gòu)發(fā)生變化后，加入了一些新的結(jié)點(diǎn),，如果是Graph Embedding方法就需要重新訓(xùn)練模型,，而GNN可以使用類似GraphSage Node-Wise Sampling的方式，使用已經(jīng)訓(xùn)練好的模型直接對新的結(jié)點(diǎn)進(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ù)中加入正則項(xiàng)使得相鄰的結(jié)點(diǎn)更相似,，但是一方面它是一種隱式的方式,，另一方面想確保學(xué)習(xí)到高階的相似關(guān)系，就需要加入更復(fù)雜的K階正則項(xiàng),，這也是GCN提出時(shí)的出發(fā)點(diǎn)之一,。相比這三種方法，GNN可以通過堆疊多層顯示地學(xué)習(xí)高階的關(guān)聯(lián)信息,。

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

8. 小結(jié)

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