腾讯高性能图计算框架Plato及其算法应用

作者：hunteryu，腾讯 WXG 后台开发工程师

Plato 简介

腾讯高性能图计算框架 Plato

图作为一种表示和分析大数据的有效方法，已成为社交网络、推荐系统、网络安全、文本检索和生物医疗等领域至关重要的数据分析和挖掘工具。例如，定期对网页进行影响力排序以提升用户的搜索体验；分析庞大的社交网络结构以便精准地为用户推荐服务；通过子图匹配等方式了解蛋白质间的相互作用从而研制更有效的临床医药。

Plato 是腾讯图计算 TGraph 整合腾讯内部图计算资源，打造的业界领先的超大规模图计算平台。Plato 针对十亿级节点的超大规模图计算，将算法计算时间从天级缩短到分钟级，性能提升数十倍，达到业界领先水平，并且打破了动辄需要数百台服务器的资源瓶颈，最少只需十台服务器即可完成计算。Plato 赋能腾讯内部包括微信在内的众多核心业务，极大的创造了业务价值。

图1：Plato架构

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

Plato 高性能图计算框架主要有以下贡献：

1. Plato 能高效地支撑腾讯超大规模社交网络图数据的各类计算，且性能达到了学术界和工业界的顶尖水平，比 Spark GraphX 高出 1-2 个数量级，使得许多按天计算的算法可在小时甚至分钟级别完成，也意味着腾讯图计算全面进入了分钟级时代。
2. Plato 的内存消耗比 Spark GraphX 减少了 1-2 个数量级，意味着只需中小规模的集群（10 台服务器左右）即可完成腾讯数据量级的超大规模图计算，打破了动辄需要上百台服务器的资源瓶颈，同时也极大地节约了计算成本。
3. Plato 隶属腾讯图计算 TGraph，起源于超大规模社交网络图数据，但可以完美适配其他类型的图数据，同时，Plato 作为高性能、可扩展、易插拔的工业级图计算框架，推动了业界超大规模图计算框架的技术进步。

Plato 算法应用

Plato 目前已支持节点中心性指标、连通图、社团发现、图表示学习等多种图算法，本次将重点介绍基于 Plato 的社团发现算法。

社交网络往往具有聚类效应，具有相似背景或相同爱好的人，更倾向于聚集在一起，形成一个圈子（社团）。如何从一个给定的社交网络还原现实生活中的圈子，在社交推荐、社交营销等领域有着非常广泛的应用。

社团发现算法简介

复杂网络中的聚类效应

复杂网络研究用图（Graph）表示网络：将网络的参与者抽象成节点（Vertex），而将参与者之间的交互或联系抽象成节点之间的连边（Edge），这些节点的集合 V = {v1,v2,··· ,vn} 与连边的集合 E = {vivj | vi,vj ∈ V } 就构成一幅图 G(V,E)。

如图 2 所示，网络中有 4 簇内部连边稠密、与外部连边稀疏的节点，这就是聚类效应的直观体现。通常把这些聚簇称为社团（Community），社团发现算法的目标就是将节点准确地划分至不同的社团中。我们对该网络使用经典的社团发现算法，计算结果如图 3 所示，用节点颜色标记社团归属。

图2：社交网络

图3：社团发现计算结果

模块度指标

模块度指标能较好地刻画社团划分质量[1]：

对于同一个网络，不同的社团划分通常对应不同的模块度，以图 4 和图 5 为例，若以不同的颜色区分不同的社团，那么图 4 中的平凡划分的模块度为零，图 5 中的非平凡划分的模块度为 5/14。显然，后者的划分更为合理。这说明模块度的大小能在一定程度上反映社团划分的质量，其值越大，划分质量越好。

基于边介数的分裂算法

我们已经找到社团划分质量的衡量指标——模块度，接下来就要找出使模块度达到最大的社团划分。模块度的最大化问题已被证明是一个“NP 难题”[5]。因此，为了在可接受的时间内求得社团划分，我们往往使用贪心策略寻求次优解，这与数据聚类的思想是如出一辙的。

在接下来介绍的聚类算法中，又可以分为分裂算法和凝聚算法，首先介绍一个以去除连边达到聚类目的的分裂算法：首先把整个网络看作一个社团，然后不断地去除介数最大的边，使其分裂成多个社团，然后通过模块度指标来控制分裂的深度。

由于分裂算法涉及到全网边介数的计算，计算复杂度过高，工程实现困难，接下来介绍更易工程实现的算法。

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

针对分裂算法无法应用于大规模网络以及无法识别小规模社团的缺点，提出了一种能够侦测到层次化社团结构的凝聚算法[2]（Fast Unfolding 算法）：首先把每个节点分别看作一个社团，然后把使模块度增益最大的邻近社团吸纳成更大的社团，当模块度增益为零时停止。

算法最终可能输出多个社团划分：每一次凝聚都对应一个层次的社团划分。层次越低，社团规模越小，从而避免了小规模社团的侦测遗漏现象。

标签传播算法

标签传播算法[3]（简称 LPA）不以目标函数为导向，大体流程是：将节点所属社团的名称作为节点标签，标签通过某种方式在网络中传播开来，当标签的传播稳定后，每个节点都有一个标识其所属社团的标签，也就完成了社团划分。

然而，LPA 也有一个不容忽视的弱点：计算结果的高随机性，重复运行两次 LPA 的社团划分结果往往并不一致。LPA 用邻居标签来在更新节点标签时，每个邻居的重要性是等同的、每个标签的重要性也是等同的，结合到 LPA 在传播过程中的随机性，某一次随机传播带来的误差，可能被多次传播，从而被不断扩散、放大。

因此提出了 HANP 算法[4]，在采集邻居的标签时，综合考虑各个邻居对节点的重要性，以及各标签经过多轮传播后的衰减，从而降低误差产生的概率以及控制误差放大。

社团发现算法基于 Plato 的高性能实现

业界实现方案

在图计算发展的近些年来，涌现出许多优秀的图计算框架。

使用 C/C++语言编写的 GraphLab 和 PowerGraph 系统提供了基于消息传递的编程接口以及一套图算法的高性能分布式实现，但系统实现层面的 COST(the Configuration that Outperforms a Single Thread)[6]较高。

Spark GraphX 系统结合了 Spark 的大数据生态环境，在编程接口上相对 GraphLab 和 PowerGraph 提高了易用性，同时很好的处理了计算容错问题，但由于 Java/Scala 语言本身的开销，无法达到理想的性能。

Gemini[7]系统提供了一种低 COST 且可扩展的分布式图计算设计方案。

图6：不同计算模式下LPA算法执行示意图

社团识别算法的计算模式多种多样，对于 LPA 和 HANP 等算法，已有计算模式存在很大的性能问题，图 6 以 Gemini 系统为例来详细介绍：

Dense 模式下，节点 D 从邻居节点获取标签，并尝试合并为一个消息（包含两个元素(La,1),(Lb,1)分别表示 A 和 B 的标签值）。由于无法合并为定长消息，因此 D 和 E 的消息总长度为 5。

Sparse 模式下，A 将自己的标签发送到 A 的镜像节点中，因此 ABC 三个节点发送消息总长度为 3，相比 dense 模式减少了不错的通信量。但 Sparse 模式下 ABC 三个节点通过 push 的方式将消息传递到 DE 两个节点，需要加锁避免写冲突，同时 D 和 E 需要维护长度为 5 的变长 buffer 来保存标签。

从上述例子我们发现：发送的消息不可以被合并为定长消息，内存占用过多，无法在有限资源内高效的完成计算。

Plato 高性能实现方案

Plato 借鉴并简化了 Cyclops[8]论文中的方法，使用 MPI 的高性能通讯原语来实现。如图 6 所示，ABC 三点首先将自己的状态（标签值）同步至 server-1 中，在这个过程中产生 3 个单位的通信量，相比 Dense 模式通信更少。之后，节点 D 和 E 使用 Pull 的方式访问周围所有节点的标签来确定自己的标签值。

通过以上方式，可以极大的减少计算过程中的内存消耗以及通信开销，能够做到在有限资源内迅速完成 LPA 和 HANP 等消息不可合并为定长数据类型的图算法计算。

Plato 算法示例

上述 FastUnfolding、LPA 和 HANP 等社团发现算法已在 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 等社团发现算法的高性能实现，可以在分钟级完成超大规模网络的社团发现，期待能为业界图计算的技术进步贡献一份力量。

参考文献

1. M. E. J. Newman, M. Girvan. Finding and Evaluating Community Structure in Networks [ J ].Physical Review E, 2004, 69(2): 026113.
2. 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.
3. 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.
4. 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.
5. S. Fortunato. Community Detection in Graphs [J/OL]. Eprint arXiv. 2009,0906:0612. [2012-12-24]. http://www.arXiv.org.
6. McSherry, Frank, Michael Isard, and Derek G. Murray. "Scalability! But at what {COST}?." 15th Workshop on Hot Topics in Operating Systems (HotOS {XV}). 2015.
7. Zhu, Xiaowei, et al. "Gemini: A computation-centric distributed graph processing system." 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.
8. 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.

推荐阅读：

鹅厂程序员最喜欢用什么编程语言？Leader写代码么？