摘要

图是描述事物及事物间关联的一种重要数据结构，它广泛应用于多个领域。由于图具有与其他数据结构不同的特性且图数据规模逐年增长，而用通用性系统处理图数据的效率低下，因此有众多工作研究了面向图的系统设计与优化，以更好地对上层应用提供支持。

本系列文章首先回顾图的概念，并对图算法进行分类讨论，并引出图计算系统的基本分类（第一部分)；接下来，详细讨论三大类系统：基于CPU的图计算系统、基于异构器件的图计算系统和基于新兴非冯·诺依曼器件的图计算系统，并对图计算系统中使用的编程模型进行分类与介绍（第二部分，本文）。随后，文章介绍了工业界研究和使用的图计算系统特点。最后，通过分析现有系统面临的挑战，文章指出图计算系统的发展趋势，以对未来研究提供借鉴作用（第三部分）。

本系列文章笔者胡静波为清华大学清华大学电子工程系硕士生；戴国浩为清华大学电子工程系助理研究员、博士后。该文工作得到清华大学和壁仞科技研究院联合研究项目的支持。

05工业界研究或使用的图计算系统

在本节中，我们将介绍各个互联网公司所研究或使用的图计算系统，其对应关系如表5.1所示。我们总结工业界所关注的图计算系统的特点，为未来学术界的研究提供借鉴作用，并寻求图系统在创新性和实用性方面的统一。

表5.1互联网公司及其所使用或研究的图计算系统

2015年IBM提出了SQLGraph^[67]，它利用关系和非关系存储属性图,在查询性能上比Neo4j^[76]快2-8倍。2018年，Twitter提出了RecService^[68]，一种分布式实时图处理引擎，可在Twitter上处理数十亿的实时推荐任务。RecService^[68]使用用户的社交环境和与用户有关的实时事件来构建框架，并支持临时和长期查询。RecService^[68]设计了新颖的分区方案，使得所有图操作都在特定的群集节点上执行，以避免跨节点通信和因图顶点上的活动度较大而产生的“热点”。

在2019年，腾讯正式开源了其高性能的图计算框架Plato^[62]，支持包含微信在内的众多核心业务，使大规模图计算进入分钟级时代。腾讯指出其社交网络中的顶点已经达到十亿量级，但学术界中现有的分布式框架未能满足腾讯处理图数据的性能需求。因此，腾讯的图计算团队自研了Plato^[62]，其能够支持大规模的离线图计算和图表示学习。Plato^[62]拥有自适应的图计算引擎，能根据不同类型的图算法，调整适应于稀疏或稠密的计算模式，并包含了共享内存和流水线设计以及图分区、资源调度等多个模块。在性能方面，相比于GraphX^[31]，Plato^[62]的计算速度高1-2个数量级，内存消耗减少1-2个数量级。

同样在2019年，阿里巴巴提出了一个大规模图神经网络平台——AliGraph^[63]，并针对存储层、采样层和操作层进行了优化。在真实数据集上的实验表明，相比于通用型分布式图计算系统PowerGraph^[28]，AliGraph^[63]的图形构建速度提高了一个数量级，且已经部署在实际电子商务平台上，以进行产品推荐。Euler[65]是阿里开源的国内首个工业级图表征学习框架，且已经应用到多项业务中，如检索匹配、营销工具等。Euler^[65]是一个分布式框架，能够支持大规模、复杂异构图的表征。2020年，阿里巴巴达摩院开源了全球首个一站式超大规模分布式图计算平台GraphScope^[64]。GraphScope^[64]对分布式系统的中编译阶段进行了优化，并且支持自动增量化的动态图数据更新，技术层面结合了多项已发表的科研成果，提供的接口对于用户编写程序十分友好。相比于多个开源的图计算系统，GraphScope^[64]有一个数量级以上的加速。

Facebook在2019年提出大规模图嵌入系统Pytorch-BigGraph^[69]，其采用了如下关键技术：大参数矩阵的块分解、均匀节点负采样及重复利用、支持权重图和多关系图。结果表明，Pytorch-BigGraph^[69]使用的分区方案能减少88%的内存消耗，且分布式训练时间减少了4倍。谷歌提出GAP^[70]，一种通用的近似分区框架，该框架采用深度学习方法进行图分区，且能够推广到看不见的图形。

综上所示，工业界中应用的图计算系统往往具有以下几个特点：

·系统以分布式框架为主。工业界的图往往具有十亿量级以上的节点和百亿量级以上的边，而单机相比于分布式系统，仍然无法支撑如此大规模的图数据处理。

·系统需要支持异构、动态图和相应复杂的图算法。工业界的图往往表现出了现实世界中的属性，因而是复杂的。主要体现在顶点和边都是异构、多属性的，且图会随时间而动态变化，且更新速度快，无法用简单的图算法进行表达。

·系统具有多个层次。常见的工业级图计算系统会分为底层的图引擎层、中间的算子表达层、上层的图特征算法层等，并支持多个图应用。

·面向图神经网络的系统或利用神经网络算法进行系统优化是目前工业界关注的热点问题。如阿里巴巴、Facebook都提出了自己的图嵌入表征系统，谷歌利用神经网络完成近似图分区。

06图计算系统未来的发展趋势

·未来的图计算系统需要针对现实中图存在的异构、动态、多属性特点进行相对应的优化。随着图应用场景的不断增多，图类型和结构也逐渐变得多样和复杂，例如，现实中的图通常具有大规模、异构（顶点/边的类别不同）、动态（图随时间变化）、多属性（边包含了不同属性）的特点。然而，大多数现有系统考虑的图结构（有向/无向图、静态图、无属性图）和评估的图算法（PageRank^[8]、BFS^[9]）都较为简单，从而造成系统性能无法满足实际需求。未来，研究者们需进一步考虑上述图的复杂特性，并针对性地进行优化，如有效的增量式执行、快速地增加/减少图中顶点或边等，以减少系统在数据存储、搬运等方面的开销。另外，建议在系统评估时选用真实的复杂问题和应用场景，而非简单模型下的基准图算法，以增强系统的实用性。

·未来的图计算系统需要设计更具通用性的编程模型或依据算法特性自适应地选择编程模型。不同图算法的差异性较大，现有的单一编程模型无法适应于所有图算法。例如，目前通用性最强的以顶点为中心的模型在执行图挖掘算法时的效率仍然较低，而以子图为中心的编程模型在执行图遍历算法时又相对复杂，不易编写程序和理解。因此，如何设计出一个灵活的、更具表现力的编程模型仍是一个具有挑战性的问题。而另一种解决思路是在一个图计算系统中包含多种编程模型，并能够根据上层应用中涉及的图算法类型，自适应地选取模型以执行运算，以满足各类应用需求，使不同算法的性能达到最优。上述两种思路都是未来可能的研究方向。

·面向图神经网络和图挖掘算法的图计算系统设计与优化会成为未来的研究重点。近年来，图神经网络和图挖掘算法显示出解决实际问题的巨大潜能。例如，有研究表明^{[77] [78]}，图神经网络因能同时结合图拓扑结构和内容属性信息，其在推荐问题上的性能已经超过传统的卷积神经网络(CNN, Convolutional Neural Network)和递归神经网络(RNN, Recurrent Neural Network)，而图挖掘算法则适用于金融风险管理、社交网络等方面。然而，利用已有的通用性图计算系统在执行上述算法时的效率较低，这主要是因为算法间计算模式的差别。相比于传统的图遍历算法，图神经网络算法在更新顶点自身值时的计算复杂度更高，耗费的时间更长；而图挖掘算法则需要存储更多的中间数据。上述计算特点的不同可能使先前的系统优化不再适用，并引发分区存储、数据通信、算子优化等多个层面的问题。目前也已经涌现出针对于上述两种算法的专用型图计算系统，例如Rstream^[26]、AutoMine^[39]、AliGraph^[63]等，相信未来会有更多的工作提供系统层面的特定优化，这是同时具有创新与实用价值的。

·基于GPU/FPGA异构平台的大规模图计算系统加速设计会成为未来的研究重点。随着图应用中不同计算任务的多样性，单一硬件平台可能无法达到性能的最优化。近年来，随着异构硬件的兴起，人们开始在GPU、FPGA平台上处理图数据，并展现出比单CPU系统更优秀的性能和巨大的潜力。例如，基于FPGA平台的GraphGen^[40]相比于CPU平台，在处理图计算问题时具有2.9倍以上的加速比；基于GPU平台的Gunrock^[37]在图算法上的平均执行速度比基于CPU平台的PowerGraph^[28]至少高出一个数量级。但基于异构平台的图计算系统仍存在一些问题，例如，受限于GPU显存和FPGA片上存储容量，系统能处理的数据规模较小，传统的图分区策略将不再适用，另一方面，数据如何在诸如CPU、GPU等不同硬件上进行存储和调度也会成为新的问题。虽然目前已有工作针对上述问题提出有效的解决方案，但随着硬件和工艺的不断发展，研究如何在GPU/FPGA异构平台上进行高效大规模图计算系统的设计与优化，例如，资源调度、内存分配、有效的数据传输等仍是一个长远而又具实际意义的课题。

07总结

图数据结构能够直观地表达事物间的联系，在多个重要领域有所应用。图计算系统能够基于图数据对上层应用提供支持，因而成为了学术界和工业界关注的重点。本文对已提出的大规模图计算系统进行了详细的调研，并根据其使用的硬件平台，分为以下三类：基于CPU的图计算系统、基于异构器件的图计算系统和基于新兴非冯·诺依曼器件的图计算系统。本文提取了上述主要系统的关键技术，并分析了系统间的优缺点。接着，本文总结了现有系统使用的编程模型，并结合模型特点指出了其适用性。之后，本文对众多互联网公司研究或使用的图计算系统进行了回顾，并总结了具有实用性图计算系统的主要特点。最后，通过对现有系统中问题的详细分析，本文提出了4个大规模图计算系统的发展趋势，以供未来研究借鉴。（全文完）

作者简介

胡静波，本科就读于西安电子科技大学，目前为清华大学电子工程系硕士生，专业为电子与通信工程，自2019年入学至今，一直跟随汪玉教授和戴国浩博士后进行大规模图计算方面的研究，且已经发表有关通用性图采样框架的论文一篇。

戴国浩，现清华大学电子工程系助理研究员、博士后，分别于2019年和2014年在清华大学电子工程系获得博士与学士学位。主要研究方向为大规模图计算、异构计算、存算一体、虚拟化等，曾获ASPDAC 2019最佳论文奖、DATE 2018最佳论文提名。
 

参考文献

[8] Gao, R., Xu, H., Hu, P., & Lau, W. C.. “Accelerating graph mining algorithms via uniform random edge sampling.” 2016 IEEE International Conference on Communications (ICC). IEEE, pp. 1-6, 2016.

[9] M. Kurant, A. Markopoulou and P. Thiran, “On the bias of BFS (Breadth First Search).” 2010 22nd International Teletraffic Congress (lTC 22), Amsterdam, 2010, pp. 1-8.[17]Sundaram N, Satish N, Patwary M M A, et al.Graphmat: High performance graph analyticsmade productive[J]. VLDB Endowment, 2015, 8(11):1214-1225.[26]Wang K, Zuo ZQ, Thorpe J, et al., 2018. RStream:marrying relational algebra with streaming for efficient graph mining on asingle machine. Proc 12th USENIX Conf on Operating Systems Design andImplementation, p.763-782.[27]Malewicz G, Austern MH, Bik AJ, et al., 2010.Pregel: a system for large-scale graph processing. Proc ACM SIGMOD Int Conf onManagement of Data, p.135-146.
[28] Gonzalez JE, Low Y, Gu H, et al., 2012. PowerGraph: distributed graph-parallel computation on natural graphs. Proc 10th USENIX Conf on Operating Systems Design and Implementation, p.17-30.[30]Shao B, Wang HX, Li YT, 2013. Trinity: adistributed graph engine on a memory cloud. Proc ACM SIGMOD Int Conf onManagement of Data, p.505-516.[37]Wang Y, Davidson A, Pan Y, et al. Gunrock: Ahigh-performance graph processing library onthe gpu[C]//ACM SIGPLAN Notices: volume 51. ACM,2016: 11.[39]Mawhirter D, Wu B. AutoMine: harmonizing high-levelabstraction and high performance for graph mining[C]//Proceedings of the 27thACM Symposium on Operating Systems Principles. 2019: 509-523.[40]Nurvitadhi E, Weisz G, Wang Y, et al. Graphgen: Anfpga framework for vertex-centric graphcomputation[C]//FCCM. IEEE, 2014: 25-28.[62]https://github.com/tencent/plato
[63] Yang H. Aligraph: A comprehensive graph neural network platform[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 3165-3166.[64] Zhengping Qian, et al. GraphScope: A System for Interactive Analysis on Distributed Graphs Using a High-Level Language. https://github.com/alibaba/GraphScope[65]https://github.com/alibaba/euler[66]Khayyat Z, Awara K, Alonazi A, et al. Mizan: asystem for dynamic load balancing in large-scale graphprocessing[C]//Proceedings of the 8th ACM European Conference on ComputerSystems. 2013: 169-182.
[67] Sun W, Fokoue A, Srinivas K, et al. Sqlgraph: An efficient relational-based property graph store[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015: 1887-1901.[68] Grewal A, Jiang J, Lam G, et al. Recservice: distributed real-time graph processing at Twitter[C]//10th {USENIX} Workshop on Hot Topics in Cloud Computing (HotCloud 18). 2018.
[69]Lerer A, Wu L, Shen J, et al. Pytorch-biggraph: Alarge-scale graph embedding system[J]. arXiv preprint arXiv:1903.12287, 2019.[70]Nazi A, Hang W, Goldie A, et al. Gap: Generalizableapproximate graph partitioning framework[J]. arXiv preprint arXiv:1903.00614,2019.[71]Roy A, Bindschaedler L, Malicevic J, et al. Chaos:Scale-out graph processing from secondary storage[C]//Proceedings of the 25thSymposium on Operating Systems Principles. 2015: 410-424.[72]Anderson M J, Sundaram N, Satish N, et al.Graphpad: Optimized graph primitives for parallel and distributedplatforms[C]//2016 IEEE International Parallel and Distributed Processing Symposium(IPDPS). IEEE, 2016: 313-322.[73]Ham T J, Wu L, Sundaram N, et al. Graphicionado: Ahigh-performance and energy-efficient accelerator for graph analytics[C]//201649th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO).IEEE, 2016: 1-13.[74]Ozdal M M, Yesil S, Kim T, et al. Energy efficientarchitecture for graph analytics accelerators[J]. ACM SIGARCH ComputerArchitecture News, 2016, 44(3): 166-177.[75]Prabhakaran V, Wu M, Weng X, et al. Managing largegraphs on multi-cores with graph awareness[C]//Presented as part of the 2012{USENIX} Annual Technical Conference ({USENIX}{ATC} 12). 2012: 41-52.
[76] F. Holzschuher and R. Peinl. Performance of graph query languages: Comparison of Cypher, Gremlin and native access in Neo4J. In Proceedings of the Joint EDBT/ICDT 2013 Workshops, pages 195{204, New York, NY, USA, 2013. ACM.
[77] Hamilton W L, Ying R, Leskovec J.Representation learning on graphs: Methods and applications[J]. arXiv preprintarXiv:1709.05584, 2017.[78] Ying R, He R, Chen K, et al. Graphconvolutional neural networks for web-scale recommender systems[C]//Proceedingsof the 24th ACM SIGKDD International Conference on Knowledge Discovery &Data Mining. 2018: 974-983.