面向大规模图计算的系统优化（1）
摘要
图是描述事物及事物间关联的一种重要数据结构，它广泛应用于多个领域。由于图具有与其他数据结构不同的特性且图数据规模逐年增长，而用通用性系统处理图数据的效率低下，因此有众多工作研究了面向图的系统设计与优化，以更好地对上层应用提供支持。
本系列文章首先回顾图的概念，并对图算法进行分类讨论，并引出图计算系统的基本分类（本文）；接下来，详细讨论三大类系统：基于CPU的图计算系统、基于异构器件的图计算系统和基于新兴非冯·诺依曼器件的图计算系统，并对相关文献中的突出贡献和关键技术进行总结（第二部分）；随后，将图计算系统中使用的编程模型进行分类与介绍，并关注工业界研究或使用的图计算系统特点（第三部分）；最后，通过分析现有系统面临的挑战，指出图计算系统的发展趋势，以对未来研究提供借鉴作用（第四部分）。
本系列文章笔者胡静波为清华大学清华大学电子工程系硕士生；戴国浩为清华大学电子工程系助理研究员、博士后。该文工作得到清华大学和壁仞科技研究院联合研究项目的支持。
01
左中括号
引言
左中括号
随着大数据时代的来临，人们会面临大量丰富多样的数据，且数据之间往往蕴含复杂的关系。图[1]是一种能够直观地表示事物间关联的数据结构，因而受到学术界和工业界的广泛关注。图在多个领域都应用广泛，例如：社交网络[2]、生物医学[3]、推荐系统[4]等。近年来，图的规模也在不断扩大。据统计数据[5]显示，截止到2019年，包括Facebook、微信、微博在内的国内外多个社交网络平台的月活跃用户量（图中的点）已经突破十亿量级，用户关系（图中的边）已经达到百亿量级，且预计未来，用户的规模还将持续增长。鉴于此，研究面向大规模图计算的系统优化设计成为大数据时代下亟需解决的问题。
相比于其他数据结构，图结构在计算和处理上往往更为复杂，其特点主要表现为以下几个方面[6]：
非结构化
图数据通常是不规则、非结构化的，即图中顶点的度（连接边的数量）相差较大。以现实中应用广泛的幂律图为例，图中各顶点的度呈现幂律分布状态，只有少部分的顶点具有较高的度，而大部分的顶点具有较低的度。这种特征会引起数据分区的困难性，并降低图计算中的并行度，使得处理图中不同部分数据的时间不均等，存储数据所占用的内存也不同，从而带来负载不均衡、数据传输开销大等问题。 数据局部性差
在图计算问题中，对于少量顶点的访问可能遍布整个内存空间，且这种访问是随机和不可预测的。由于相关联的数据无法保证总是在存储时排列在一起，并顺序读取，因此图数据的局部性差，难以像传统的数据结构一样，利用CPU缓存等策略进行加速，从而加大了图数据系统优化的难度。 高传输计算比
图计算任务中数据传输相比于计算的比例较高。以图1.1中的顶点5为例，其计算过程如下：首先，顶点1，2，3，4将自身值传输给顶点5，顶点5进行简单运算后，再将值传输给顶点6，7，8，9。由上述阶段可知，其输入输出的数据传输部分会引起内存访问延迟，从而成为性能瓶颈。这也是图计算问题与传统计算密集型问题的不同点之一。
图1.1图计算特点之高传输计算比示意图
复杂的数据依赖性
在图数据结构中，顶点和边具有不同的连接关系，而图任务又高度依赖于这些连接关系，因此，在任务运行过程中，一部分顶点和边可能被频繁访问，而另一些顶点和边可能不会被访问到或者只访问少量的次数。图结构中存在的复杂数据依赖性使得我们无法在任务中准确预测数据访问的路径和次数，同时也无法判断限制其并行性的计算结构。
为了更好地解决上述图计算中存在的问题，并为未来大规模图计算系统的研究与发展提供借鉴思路，我们详细地调研了众多图计算系统，提炼出其关键技术点并进行不同层面的分类，如图3.1所示。特别地，我们并非只关注图计算系统中的某一分支，而是对整体进行了分析。另外，我们着重关注了工业界研究和使用的图计算系统，它们所属阿里巴巴、Facebook、IBM、Twitter等诸多知名互联网公司。例如，2015年IBM提出了SQLGraph[67]，它利用关系和非关系存储属性图,在查询性能上比Neo4j[76]快2-8倍。2018年，Twitter提出了RecService[68]，一种分布式实时图处理引擎，可在Twitter上处理数十亿的实时推荐任务。2019年，Facebook提出大规模图嵌入系统Pytorch-BigGraph[69]，它使用的分区方案能减少88%的内存消耗，且分布式训练时间减少了4倍。同年，阿里巴巴提出一个大规模图神经网络平台——AliGraph[63]，在真实数据集上的实验表明，相比于通用型分布式图计算系统PowerGraph[28]，AliGraph[63]的图形构建速度提高了一个数量级，且已经部署在实际电子商务平台（淘宝）上，以进行产品推荐。2020年，阿里巴巴达摩院开源全球首个一站式超大规模分布式图计算平台GraphScope[64]，其技术层面结合了多项已发表的科研成果，相比于多个开源的图计算系统，GraphScope[64]有一个数量级以上的加速。进一步地，我们通过提炼上述工业界中图计算系统的共性以寻求系统创新性和实用性的统一。在此基础上，我们总结出了现存图计算系统中的开放问题和未来可能的发展趋势。我们的主要贡献如下：
对图计算系统进行了详细的调研，并总结了代表性系统的关键技术。按照基于CPU的图计算系统、基于异构器件的图计算系统和基于新兴非冯·诺依曼器件的图计算系统对调研的图计算系统进行了分类。
将现有图计算系统中使用的主要编程模型划分为三类：以顶点为中心、以边为中心和以子图为中心。总结了各个模型的特点，及其适用的图算法和应用。
总结了工业界研究或使用的图计算系统，以明确目前商用图系统的特点，并探究何种系统具有更强的实用性，以增强未来研究的实际价值，寻求创新性与实用性的统一。
基于现有系统所存在的问题，提出了4个图计算系统的发展趋势，以对未来研究提供借鉴作用。例如，面向特定应用的系统设计、异构硬件、动态图等。
02
左中括号
图相关概念与图算法
左中括号
在本节中，我们首先介绍图在数学上的定义，这是与图相关问题的基础。接着，我们会介绍图在存储中的几种不同方式。最后，我们将图算法进行了分类，并进行简要分析。
2.1 图的定义
图是由顶点和边组成的数据结构，表示为G(V,E)。其中，G表示一个图，V表示图中顶点的集合，E为图中边的集合，
2.2 图的存储
在图这种数据结构中，顶点和边都具有相对位置关系，难以用单一的顺序结构进行存储。一种直接的想法是利用二维邻接矩阵进行图数据的存储，即行和列均表示图的顶点序号，数组中的元素代表两个顶点间是否存在连接关系或边的权重。但图结构往往具有稀疏特性，即在上述邻接矩阵中会存在大量0元素，从而引起存储空间的浪费。
图遍历算法经常用于网页排序、计算机网络路由等方面，其计算模型为在迭代过程中每个顶点会根据邻居节点值来更新自身节点值，再通过图的连接关系扩散到其他节点，其中，更新节点值的计算一般为轻量级的。典型的图遍历算法有PageRank[8]、宽度优先搜索(BFS)[9]等。
图挖掘算法的目标是搜索、匹配图中的特定序列或模式，其在金融风险管理、社交网络分析中都有所应用。相比于图遍历算法，图挖掘算法的计算量和存储量要大得多，由于候选的子图存在多种组合，因此，其计算和空间复杂度通常以超线性的方式增长。典型的图挖掘算法有频繁子图挖掘[10]、图聚类[11]等。
图神经网络是近年来兴起的一种图算法，其融合了图结构和神经网络，能够捕获元素间潜在的复杂而丰富的数据关系，在推荐系统等应用场景中具有优异的效果。相较于传统的图算法，图神经网络在计算节点向量值，获取节点信息时的计算复杂度更高，从而耗费更长的时间。典型的图神经网络算法有图卷积网络(GCN)[12]、图注意力网络(GAT)[13]等。
03
左中括号
图计算系统研究现状
左中括号
在本节中，我们将调研的大规模图计算系统分为以下三类：基于CPU的图计算系统、基于异构器件的图计算系统和基于新兴非冯·诺依曼器件的图计算系统。在每一类中，我们会选取有代表性的系统进行介绍，提取其关键技术，并分析不同系统间的优缺点。图3.1展示了图计算系统的时间线表示。
图3.1 图计算系统的分类及时间线表示
本系列文章的下一部分将详细讨论各种类型的图计算系统。
作者简介
胡静波，本科就读于西安电子科技大学，目前为清华大学电子工程系硕士生，专业为电子与通信工程，自2019年入学至今，一直跟随汪玉教授和戴国浩博士后进行大规模图计算方面的研究，且已经发表有关通用性图采样框架的论文一篇。
戴国浩，现清华大学电子工程系助理研究员、博士后，分别于2019年和2014年在清华大学电子工程系获得博士与学士学位。主要研究方向为大规模图计算、异构计算、存算一体、虚拟化等，曾获ASPDAC 2019最佳论文奖、DATE 2018最佳论文提名。
参考文献
[3] Eckhardt M, Zhang W, Gross A M, et al. Multiple routes to oncogenesis are promoted by the human papillomavirus–host protein network[J]. Cancer discovery, 2018, 8(11): 1474-1489.
[4] Wang J, Huang P, Zhao H, et al. Billion-scale commodity embedding for e-commerce recommendation in alibaba[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 839-848.
[5] Enberg J. Global social network users 2019[Z]. https://www.emarketer.com/content/global-social-network-users.
[6] Liu N , Li D S , Zhang Y M , et al. Large-scale graph processing systems: a survey[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(3):384-404.
[7]王海文,罗明山.一种改进的图存储结构的实现及性能分析[J].大众科技,2012,14(05):6-7.
[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.
[10] Xifeng Yan and Jiawei Han. 2002. gspan: Graph-based substructure pattern mining. In IEEE International Conference on Data Mining. 721–724.
[11] Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph clustering based on structural/attribute similarities. Proceedings of the VLDB Endowment 2, 1 (2009), 718–729.
[12] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.
[13] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.
[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.
[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
[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.
[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.
往期推荐
壁仞科技研究院作为壁仞科技的前沿研究部门，旨在研究新型智能计算系统的关键技术，重点关注新型架构，先进编译技术和设计方法学，并将逐渐拓展研究方向，探索未来智能系统的各种可能。壁仞科技研究院秉持开放的原则，将积极投入各类产学研合作并参与开源社区的建设，为相关领域的技术进步做出自己的贡献。