[[318509]]

Plato 簡介

騰訊高性能圖計算框架 Plato

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

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

圖1：Plato架構

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

Plato 高性能圖計算框架主要有以下貢獻：

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

Plato 算法應用

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

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

社團發(fā)現(xiàn)算法簡介

復雜網(wǎng)絡中的聚類效應

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

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

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

圖3：社團發(fā)現(xiàn)計算結果

模塊度指標

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

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

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

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

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

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

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

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

標簽傳播算法

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

然而，LPA 也有一個不容忽視的弱點：計算結果的高隨機性，重復運行兩次 LPA 的社團劃分結果往往并不一致。LPA 用鄰居標簽來在更新節(jié)點標簽時，每個鄰居的重要性是等同的、每個標簽的重要性也是等同的，結合到 LPA 在傳播過程中的隨機性，某一次隨機傳播帶來的誤差，可能被多次傳播，從而被不斷擴散、放大。

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

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

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

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

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

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

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

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

社團識別算法的計算模式多種多樣，對于 LPA 和 HANP 等算法，已有計算模式存在很大的性能問題，圖 6 以 Gemini 系統(tǒng)為例來詳細介紹：

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

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

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

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

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

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

Plato 算法示例

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

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

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

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

總結

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

參考文獻

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.