[[318509]]

Plato 簡(jiǎn)介

騰訊高性能圖計(jì)算框架 Plato

圖作為一種表示和分析大數(shù)據(jù)的有效方法，已成為社交網(wǎng)絡(luò)、推薦系統(tǒng)、網(wǎng)絡(luò)安全、文本檢索和生物醫(yī)療等領(lǐng)域至關(guān)重要的數(shù)據(jù)分析和挖掘工具。例如，定期對(duì)網(wǎng)頁(yè)進(jìn)行影響力排序以提升用戶的搜索體驗(yàn);分析龐大的社交網(wǎng)絡(luò)結(jié)構(gòu)以便精準(zhǔn)地為用戶推薦服務(wù);通過(guò)子圖匹配等方式了解蛋白質(zhì)間的相互作用從而研制更有效的臨床醫(yī)藥。

Plato 是騰訊圖計(jì)算 TGraph 整合騰訊內(nèi)部圖計(jì)算資源，打造的業(yè)界領(lǐng)先的超大規(guī)模圖計(jì)算平臺(tái)。Plato 針對(duì)十億級(jí)節(jié)點(diǎn)的超大規(guī)模圖計(jì)算，將算法計(jì)算時(shí)間從天級(jí)縮短到分鐘級(jí)，性能提升數(shù)十倍，達(dá)到業(yè)界領(lǐng)先水平，并且打破了動(dòng)輒需要數(shù)百臺(tái)服務(wù)器的資源瓶頸，最少只需十臺(tái)服務(wù)器即可完成計(jì)算。Plato 賦能騰訊內(nèi)部包括微信在內(nèi)的眾多核心業(yè)務(wù)，極大的創(chuàng)造了業(yè)務(wù)價(jià)值。

圖1：Plato架構(gòu)

Plato 開源地址：https://github.com/tencent/plato

Plato 高性能圖計(jì)算框架主要有以下貢獻(xiàn)：

1. Plato 能高效地支撐騰訊超大規(guī)模社交網(wǎng)絡(luò)圖數(shù)據(jù)的各類計(jì)算，且性能達(dá)到了學(xué)術(shù)界和工業(yè)界的頂尖水平，比 Spark GraphX 高出 1-2 個(gè)數(shù)量級(jí)，使得許多按天計(jì)算的算法可在小時(shí)甚至分鐘級(jí)別完成，也意味著騰訊圖計(jì)算全面進(jìn)入了分鐘級(jí)時(shí)代。
2. Plato 的內(nèi)存消耗比 Spark GraphX 減少了 1-2 個(gè)數(shù)量級(jí)，意味著只需中小規(guī)模的集群(10 臺(tái)服務(wù)器左右)即可完成騰訊數(shù)據(jù)量級(jí)的超大規(guī)模圖計(jì)算，打破了動(dòng)輒需要上百臺(tái)服務(wù)器的資源瓶頸，同時(shí)也極大地節(jié)約了計(jì)算成本。
3. Plato 隸屬騰訊圖計(jì)算 TGraph，起源于超大規(guī)模社交網(wǎng)絡(luò)圖數(shù)據(jù)，但可以完美適配其他類型的圖數(shù)據(jù)，同時(shí)，Plato 作為高性能、可擴(kuò)展、易插拔的工業(yè)級(jí)圖計(jì)算框架，推動(dòng)了業(yè)界超大規(guī)模圖計(jì)算框架的技術(shù)進(jìn)步。

Plato 算法應(yīng)用

Plato 目前已支持節(jié)點(diǎn)中心性指標(biāo)、連通圖、社團(tuán)發(fā)現(xiàn)、圖表示學(xué)習(xí)等多種圖算法，本次將重點(diǎn)介紹基于 Plato 的社團(tuán)發(fā)現(xiàn)算法。

社交網(wǎng)絡(luò)往往具有聚類效應(yīng)，具有相似背景或相同愛好的人，更傾向于聚集在一起，形成一個(gè)圈子(社團(tuán))。如何從一個(gè)給定的社交網(wǎng)絡(luò)還原現(xiàn)實(shí)生活中的圈子，在社交推薦、社交營(yíng)銷等領(lǐng)域有著非常廣泛的應(yīng)用。

社團(tuán)發(fā)現(xiàn)算法簡(jiǎn)介

復(fù)雜網(wǎng)絡(luò)中的聚類效應(yīng)

復(fù)雜網(wǎng)絡(luò)研究用圖(Graph)表示網(wǎng)絡(luò)：將網(wǎng)絡(luò)的參與者抽象成節(jié)點(diǎn)(Vertex)，而將參與者之間的交互或聯(lián)系抽象成節(jié)點(diǎn)之間的連邊(Edge)，這些節(jié)點(diǎn)的集合 V = {v1,v2,··· ,vn} 與連邊的集合 E = {vivj | vi,vj ∈ V } 就構(gòu)成一幅圖 G(V,E)。

如圖 2 所示，網(wǎng)絡(luò)中有 4 簇內(nèi)部連邊稠密、與外部連邊稀疏的節(jié)點(diǎn)，這就是聚類效應(yīng)的直觀體現(xiàn)。通常把這些聚簇稱為社團(tuán)(Community)，社團(tuán)發(fā)現(xiàn)算法的目標(biāo)就是將節(jié)點(diǎn)準(zhǔn)確地劃分至不同的社團(tuán)中。我們對(duì)該網(wǎng)絡(luò)使用經(jīng)典的社團(tuán)發(fā)現(xiàn)算法，計(jì)算結(jié)果如圖 3 所示，用節(jié)點(diǎn)顏色標(biāo)記社團(tuán)歸屬。

圖2：社交網(wǎng)絡(luò)

圖3：社團(tuán)發(fā)現(xiàn)計(jì)算結(jié)果

模塊度指標(biāo)

模塊度指標(biāo)能較好地刻畫社團(tuán)劃分質(zhì)量[1]：

對(duì)于同一個(gè)網(wǎng)絡(luò)，不同的社團(tuán)劃分通常對(duì)應(yīng)不同的模塊度，以圖 4 和圖 5 為例，若以不同的顏色區(qū)分不同的社團(tuán)，那么圖 4 中的平凡劃分的模塊度為零，圖 5 中的非平凡劃分的模塊度為 5/14。顯然，后者的劃分更為合理。這說(shuō)明模塊度的大小能在一定程度上反映社團(tuán)劃分的質(zhì)量，其值越大，劃分質(zhì)量越好。

基于邊介數(shù)的分裂算法

我們已經(jīng)找到社團(tuán)劃分質(zhì)量的衡量指標(biāo)——模塊度，接下來(lái)就要找出使模塊度達(dá)到最大的社團(tuán)劃分。模塊度的最大化問(wèn)題已被證明是一個(gè)“NP 難題”[5]。因此，為了在可接受的時(shí)間內(nèi)求得社團(tuán)劃分，我們往往使用貪心策略尋求次優(yōu)解，這與數(shù)據(jù)聚類的思想是如出一轍的。

在接下來(lái)介紹的聚類算法中，又可以分為分裂算法和凝聚算法，首先介紹一個(gè)以去除連邊達(dá)到聚類目的的分裂算法：首先把整個(gè)網(wǎng)絡(luò)看作一個(gè)社團(tuán)，然后不斷地去除介數(shù)最大的邊，使其分裂成多個(gè)社團(tuán)，然后通過(guò)模塊度指標(biāo)來(lái)控制分裂的深度。由于分裂算法涉及到全網(wǎng)邊介數(shù)的計(jì)算，計(jì)算復(fù)雜度過(guò)高，工程實(shí)現(xiàn)困難，接下來(lái)介紹更易工程實(shí)現(xiàn)的算法。

基于模塊度增益的凝聚算法

針對(duì)分裂算法無(wú)法應(yīng)用于大規(guī)模網(wǎng)絡(luò)以及無(wú)法識(shí)別小規(guī)模社團(tuán)的缺點(diǎn)，提出了一種能夠偵測(cè)到層次化社團(tuán)結(jié)構(gòu)的凝聚算法[2](Fast Unfolding 算法)：首先把每個(gè)節(jié)點(diǎn)分別看作一個(gè)社團(tuán)，然后把使模塊度增益最大的鄰近社團(tuán)吸納成更大的社團(tuán)，當(dāng)模塊度增益為零時(shí)停止。

算法最終可能輸出多個(gè)社團(tuán)劃分：每一次凝聚都對(duì)應(yīng)一個(gè)層次的社團(tuán)劃分。層次越低，社團(tuán)規(guī)模越小，從而避免了小規(guī)模社團(tuán)的偵測(cè)遺漏現(xiàn)象。

標(biāo)簽傳播算法

標(biāo)簽傳播算法[3](簡(jiǎn)稱 LPA)不以目標(biāo)函數(shù)為導(dǎo)向，大體流程是：將節(jié)點(diǎn)所屬社團(tuán)的名稱作為節(jié)點(diǎn)標(biāo)簽，標(biāo)簽通過(guò)某種方式在網(wǎng)絡(luò)中傳播開來(lái)，當(dāng)標(biāo)簽的傳播穩(wěn)定后，每個(gè)節(jié)點(diǎn)都有一個(gè)標(biāo)識(shí)其所屬社團(tuán)的標(biāo)簽，也就完成了社團(tuán)劃分。

然而，LPA 也有一個(gè)不容忽視的弱點(diǎn)：計(jì)算結(jié)果的高隨機(jī)性，重復(fù)運(yùn)行兩次 LPA 的社團(tuán)劃分結(jié)果往往并不一致。LPA 用鄰居標(biāo)簽來(lái)在更新節(jié)點(diǎn)標(biāo)簽時(shí)，每個(gè)鄰居的重要性是等同的、每個(gè)標(biāo)簽的重要性也是等同的，結(jié)合到 LPA 在傳播過(guò)程中的隨機(jī)性，某一次隨機(jī)傳播帶來(lái)的誤差，可能被多次傳播，從而被不斷擴(kuò)散、放大。

因此提出了 HANP 算法[4]，在采集鄰居的標(biāo)簽時(shí)，綜合考慮各個(gè)鄰居對(duì)節(jié)點(diǎn)的重要性，以及各標(biāo)簽經(jīng)過(guò)多輪傳播后的衰減，從而降低誤差產(chǎn)生的概率以及控制誤差放大。

社團(tuán)發(fā)現(xiàn)算法基于 Plato 的高性能實(shí)現(xiàn)

業(yè)界實(shí)現(xiàn)方案

在圖計(jì)算發(fā)展的近些年來(lái)，涌現(xiàn)出許多優(yōu)秀的圖計(jì)算框架。

使用 C/C++語(yǔ)言編寫的 GraphLab 和 PowerGraph 系統(tǒng)提供了基于消息傳遞的編程接口以及一套圖算法的高性能分布式實(shí)現(xiàn)，但系統(tǒng)實(shí)現(xiàn)層面的 COST(the Configuration that Outperforms a Single Thread)[6]較高。

Spark GraphX 系統(tǒng)結(jié)合了 Spark 的大數(shù)據(jù)生態(tài)環(huán)境，在編程接口上相對(duì) GraphLab 和 PowerGraph 提高了易用性，同時(shí)很好的處理了計(jì)算容錯(cuò)問(wèn)題，但由于 Java/Scala 語(yǔ)言本身的開銷，無(wú)法達(dá)到理想的性能。

Gemini[7]系統(tǒng)提供了一種低 COST 且可擴(kuò)展的分布式圖計(jì)算設(shè)計(jì)方案。

圖6：不同計(jì)算模式下LPA算法執(zhí)行示意圖

社團(tuán)識(shí)別算法的計(jì)算模式多種多樣，對(duì)于 LPA 和 HANP 等算法，已有計(jì)算模式存在很大的性能問(wèn)題，圖 6 以 Gemini 系統(tǒng)為例來(lái)詳細(xì)介紹：

Dense 模式下，節(jié)點(diǎn) D 從鄰居節(jié)點(diǎn)獲取標(biāo)簽，并嘗試合并為一個(gè)消息(包含兩個(gè)元素(La,1),(Lb,1)分別表示 A 和 B 的標(biāo)簽值)。由于無(wú)法合并為定長(zhǎng)消息，因此 D 和 E 的消息總長(zhǎng)度為 5。

Sparse 模式下，A 將自己的標(biāo)簽發(fā)送到 A 的鏡像節(jié)點(diǎn)中，因此 ABC 三個(gè)節(jié)點(diǎn)發(fā)送消息總長(zhǎng)度為 3，相比 dense 模式減少了不錯(cuò)的通信量。但 Sparse 模式下 ABC 三個(gè)節(jié)點(diǎn)通過(guò) push 的方式將消息傳遞到 DE 兩個(gè)節(jié)點(diǎn)，需要加鎖避免寫沖突，同時(shí) D 和 E 需要維護(hù)長(zhǎng)度為 5 的變長(zhǎng) buffer 來(lái)保存標(biāo)簽。

從上述例子我們發(fā)現(xiàn)：發(fā)送的消息不可以被合并為定長(zhǎng)消息，內(nèi)存占用過(guò)多，無(wú)法在有限資源內(nèi)高效的完成計(jì)算。

Plato 高性能實(shí)現(xiàn)方案

Plato 借鑒并簡(jiǎn)化了 Cyclops[8]論文中的方法，使用 MPI 的高性能通訊原語(yǔ)來(lái)實(shí)現(xiàn)。如圖 6 所示，ABC 三點(diǎn)首先將自己的狀態(tài)(標(biāo)簽值)同步至 server-1 中，在這個(gè)過(guò)程中產(chǎn)生 3 個(gè)單位的通信量，相比 Dense 模式通信更少。之后，節(jié)點(diǎn) D 和 E 使用 Pull 的方式訪問(wèn)周圍所有節(jié)點(diǎn)的標(biāo)簽來(lái)確定自己的標(biāo)簽值。

通過(guò)以上方式，可以極大的減少計(jì)算過(guò)程中的內(nèi)存消耗以及通信開銷，能夠做到在有限資源內(nèi)迅速完成 LPA 和 HANP 等消息不可合并為定長(zhǎng)數(shù)據(jù)類型的圖算法計(jì)算。

Plato 算法示例

上述 FastUnfolding、LPA 和 HANP 等社團(tuán)發(fā)現(xiàn)算法已在 github 開源，感興趣的讀者可通過(guò)如下地址獲取算法介紹和源代碼：

開源地址：https://github.com/Tencent/plato

算法介紹：https://github.com/Tencent/plato/wiki

代碼示例：https://github.com/Tencent/plato/tree/master/example

總結(jié)

騰訊高性能分布式圖計(jì)算框架 Plato，已集成了最常用的 Fast Unfolding、LPA 和 HANP 等社團(tuán)發(fā)現(xiàn)算法的高性能實(shí)現(xiàn)，可以在分鐘級(jí)完成超大規(guī)模網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)，期待能為業(yè)界圖計(jì)算的技術(shù)進(jìn)步貢獻(xiàn)一份力量。

參考文獻(xiàn)

M. E. J. Newman, M. Girvan. Finding and Evaluating Community Structure in Networks [ J ].Physical Review E, 2004, 69(2): 026113.

V. D. Blondel, J. L. Guillaume, R. Lambiotter, et al. Fast Unfolding of Community Hierarchies in Large Networks [J]. Journal of Statistical Machanics: Theory and Experiment, 2008, 10: 10008.

U. N. Raghavan, R. Albert, S. Kumara. Near Linear Time Algorithm to DetectCommunity Structures in Large-Scale Networks [J/OL]. Eprint arXiv,2007, 0709:2938. [2012-6-18]. http://www.arXiv.org.

Ian X.Y. Leung, Pan Hui, Pietro Li`o, et al. Towards real-time community detection in large networks [J/OL]. Eprint arXiv, 2009, 0808:2633.[2019-12-18]. http://www.arXiv.org.

S. Fortunato. Community Detection in Graphs [J/OL]. Eprint arXiv. 2009,0906:0612. [2012-12-24]. http://www.arXiv.org.

McSherry, Frank, Michael Isard, and Derek G. Murray. "Scalability! But at what {COST}?." 15th Workshop on Hot Topics in Operating Systems (HotOS {XV}). 2015.

Zhu, Xiaowei, et al. "Gemini: A computation-centric distributed graph processing system." 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.

Chen, Rong, et al. "Computation and communication efficient graph processing with distributed immutable view." Proceedings of the 23rd international symposium on High-performance parallel and distributed computing. ACM, 2014.