1、 清华-中国工程院知识智能联合实验室 目录 1 概述篇. 1 1.1 大规模图数据时代下的图计算 . 1 1.2 图计算的特征 . 3 2 技术篇. 6 2.1 技术挑战 . 6 2.2 图算法与图计算框架简介 . 7 2.2.1 图算法 . 8 2.2.2 图计算框架 . 9 2.3 技术资源 . 13 2.4 高引论文 . 14 3 人才篇. 16 3.1 学者情况概览 . 16 3.2 典型学者简介 . 19 3.2.1 国外学者简介 . 20 3.2.2 国内学者简介 . 24 4 产业应用篇 . 28 4.1 医疗行业的应用 . 28 4.2 金融行业的应用 . 28 4.3 互联网

2、行业的应用 . 29 5 趋势篇. 32 5.1 全局热度 . 32 5.2 近期热度 . 32 5.3 交叉研究分析 . 33 5.3.1 Graph Computing & Data Mining . 33 5.3.2 Graph Computing & Machine Learning . 35 5.4 技术预见 . 37 附录 . 39 图表目录 图 1 图数据典型例子 . 1 图 2 代表性分布式图计算系统 . 3 图 3 图计算系统框架分类 . 9 图 4 Venue Colletion of OAG . 13 图 5 Paper Collection of OAG . 13 图

3、6 Author Collection of OAG . 13 图 7 全球图计算领域活跃学者分布图 . 16 图 8 中国图计算领域活跃学者分布图 . 17 图 9 全球图计算领域活跃学者迁徙图 . 18 图 10 全球图计算领域活跃学者机构分布 . 18 图 11 全球图计算领域活跃学者 h-index 分布 . 19 图 12 全球图计算领域活跃学者性别比 . 19 图 13 华为 GES 的应用场景 . 30 图 14 腾讯星图应用场景 . 31 图 15 graph computing 全局热度. 32 图 16 graph computing 近期热度. 32 图 17 2007

4、至今 graph computing 与 data mining 领域交叉分析 . 34 图 18 2007 至今 graph computing 与 machine learning 领域交叉分析 . 35 图 19 图计算技术预见图 . 37 表 1 2007 年至今 graph computing 与 data mining 交叉研究学者 h-index 分布 . 34 表 2 2007 年至今 graph computing 与 data mining 交叉研究论文 citation 分布 . 34 表 3 2007 年至今 graph computing 与 machine lear

5、ning 领域交叉研究学者 h-index 分布 . 36 表 4 2007 年至今 graph computing 与 machine learning 领域交叉研究论文 citation 分布 . 36 摘要 图计算是基于图数据的分析技术与关系技术应运而生的，图计算系统是针对处理图结 构数据的系统，图计算也是人工智能中的一个使能技术。基于此背景，本研究报告对图计算 这一课题进行了简单梳理，包括以下内容： 图计算的概念与图计算的概念与图计算图计算特征特征。 对图计算的概念进行阐述， 对代表性分布式图计算系统进 行介绍，并列出图计算的特征。 图计算技术图计算技术。从图计算面临的挑战出发，介绍图

6、算法，图计算模型主要解决的问题，并 图计算框架进行介绍。同时对技术资源和图计算的高引论文进行相关介绍。 图计算领域专家介绍。图计算领域专家介绍。依据 AMiner 数据平台信息，对图计算领域研究学者进行梳理， 重点介绍研究学者的研究方向与代表性文章， 旨在为学术界、 产业界提供图计算技术及学者 的分析依据。对顶尖学者的全球分布、迁徙概况、学者机构分布、h-index 分析进行介绍。 图计算产业应用图计算产业应用。 从医疗行业、 金融行业和互联网行业三个方面介绍领域图计算的技术 构建应用与研究现状。 图计算趋势研究图计算趋势研究。对图计算的发展趋势特点进行分析。并基于 AMiner 数据平台，对

7、近 期图计算领域研究热点进行可视化分析， 与其他学科进行交叉分析研究， 对未来图计算研究 方向进行预测。 1 1 概述篇概述篇 如今，数据已经渗透到每一个行业和业务职能领域，尤其近年来，全球大数据进入加速 发展时期，数据量呈现爆发式增长，大数据吸引了越来越多的关注，大数据时代已然来临。 图计算简单来讲就是研究在这些大量数据中， 如何高效计算、 存储并管理图数据等问题 的领域。传统的关系型数据暴露出了建模缺陷、水平伸缩等问题，于是具有更强大表达能力 的图数据受到业界极大的重视。 如果把关系数据模型比作火车的话， 那么现在的图数据建模 可比作高铁。 1.1 大规模图数据时代下的图计算 图（Grap

8、h）是一种重要的数据结构，它由节点 V（或称为顶点，即个体） ，与边 E（即 个体之间的联系）构成，我们一般将图表示为 G（V，E） 。图数据的典型例子有网页链接关 系、社交网络、商品推荐等。对应互联网来说，可以把 web 网页看作顶点，页面之间的超链 接关系作为边；对应社交网络来说，可以把用户看作顶点，用户之间建立的关系看作边。比 如微信的社交网络，是由节点（个人、公众号）和边（关注、点赞）构成的图；淘宝的交易 网络，是由节点（个人、商品）和边（购买、收藏）构成的图。 图 1 图数据典型例子 如此一来，抽象出来的图数据便可作为研究和商用的基础，由此探究出“世界上任意两 个人之间的人脉距离”

9、、 “关键意见领袖”等。将这些应用到商业领域，其底层的运算往往是 图相关的算法。比如图的最短路径算法可以做好友推荐，计算关系紧密程度；对图做 PageRank 可以用于传播影响力分析，找出问题的中心，做搜索引擎的网页排名；最小连通 图可以识别洗钱或虚假交易等等。 近年来，图数据规模呈指数级增长，可能达到数十亿的顶点和数万亿的边，且还在不断 增长， 单机模式下的图计算已经不适合目前数据的增长， 传统的分布式大数据处理平台比如 MapReduce、Spark 也出现网络和磁盘读写开销大、运算速度慢、处理效率极低的问题1。 2 对于图计算而言，性能成本、容错机制以及可拓展性都是非常重要的。如果性能可

10、以显 著提高，结点显著减少，那么就能极大地缩短运行时间。在此基础上，如果使用更大开销的 容错技术，例如检查点的方式，那么故障产生的概率将更低。 但是，传统的大数据分析平台往往只在性能与可拓展性中选择了一方。比如 MPI、 OpenMP 等注重性能的平台只支持可读写的数据， 容错困难， 可扩展性差， 自动负载不平衡； 专注于拓展性的大数据分析平台，如 MapReduce、Spark 等支持只读数据集，容错机制和扩 展性好，自动负载平衡，但性能较低。以 Spark 为例，其基于 Scala 语言，运行在 JVM 上， 内存表示冗余，占用内存大，垃圾收集对性能影响大。在一些迭代的图算法上，开启 12

11、8 个 线程的 Spark 程序性能有时候还不如优化很好的单线程程序， 并且需要的内存容量是原始数 据集的 20 倍对于 10TB 级的数据，往往需要数百 TB 的内存，这在绝大部分生产环境 中是不可能的。以 Sogou 的网页链接数据为例，Sogou 的网页链接数据量为 137TB，这是很 难使用 Spark 进行计算的。 此外， 早期的图计算方法主要局限于智能社区或社交网络分析， 如果图计算方案的性能 和容量限制可以克服，图计算可以应用于更广泛的场景，如资本市场风险管理、生命科学研 究、医疗保健交付、监控和应对道路事故、智能基础设施管理和其他领域。 因此， 为应对图计算中对高效处理大规模图

12、数据的巨大挑战， 可扩展分布式图计算成为 了当前热点研究问题。 自从 2001 年以来，分布式方法就一直是比较热议的处理大图数据的方法，特别是 2003 年和 2004 年，Google 公布了 MapReduce 的基本原理和主要设计思想，这一模型的推出给 大数据并行处理带来了巨大的革命性影响。此后提出的图处理系统，比如 2006 年发布的 Apache Hadoop、2009 年诞生于加州大学伯克利分校 AMPLab 的 Spark 等，大多基于 MapReduce 的思想， 并采用并行 BSP 模型。 但是， 这些系统与 MapReduce 一样依赖于磁盘， 仍然存在局限性，执行速度慢，

13、处理大型图数据效率较低。 直到 2010 年谷歌推出以顶点为中心的图处理系统 Pregel，其专为大规模图数据处理而 设计， 将图数据保存在主存储器中并采用并行计算的 BSP 模型， 因此比 MapReduce 更有效。 此后， 对于商用集群和云的图处理系统变得格外受欢迎， 并且又出现多个具有不同编程模型 和功能的分布式图处理框架，并被广泛应用以促进大规模图数据的操作，比如 GraphLab、 Giraph、GraphX、PowerLyra、Gemini 等。这些框架都有自身的优缺点，在技术篇我们将做 详细介绍。 3 图 2 代表性分布式图计算系统 由于本文着重介绍为应对大规模图数据而提出的分

14、布式图计算，因此对于单机图计算 不做过多描述。 对于分布计算的开发和维护需要考虑的情形是复杂多变的。对计算过程中信息的控制、 每个任务的数据获取、 对计算结果的合并和对错误计算的回归， 在分布式计算的时候都需要 保证正常运行。如果这些任务全部都由开发人员负责，则对程序员的要求是非常高的。分布 式计算框架则能够解决这种瓶颈， 通过分布式框架封装计算细节， 完成分布式计算程序的开 发。 通过使用分布式计算框架， 程序员可以很容易享受到分布式计算所带来的高速计算的好 处， 而且不必对分布式计算过程中各种问题和计算异常进行控制， 这就让程序员的开发效率 成倍地提高。 研究高效处理大规模数据的图计算，能

15、推动社交网络分析、语义 web 分析、生物信息 网络分析、自然语言处理等新兴应用领域的发展。 1.2 图计算的特征 初提图计算，很多人会以为这是一种专门进行图像处理的技术。事实上，图计算中的 “图”是针对“图论”而言的，是一种以“图论”为基础的对现实世界的一种“图”结构 的抽象表达， 以及在这种数据结构上的计算模式。 图数据结构很好的表达了数据之间的关联 性， 关联性计算是大数据计算的核心通过获得数据的关联性， 可以从噪音很多的海量数 据中抽取有用的信息。 图计算技术解决了传统的计算模式下关联查询的效率低、 成本高的问 题，在问题域中对关系进行了完整的刻画，并且具有丰富、高效和敏捷的数据分析能

16、力，其 特征有如下三点。 4 1)1) 基于基于图图抽象的抽象的数据模型数据模型 图计算系统将图结构化数据表示为属性图，它将用户定义的属性与每个顶点和边缘相 关联。 属性可以包括元数据 （例如， 用户简档和时间戳） 和程序状态 （例如， 顶点的 PageRank 或相关的亲和度） 。 源自社交网络和网络图等自然现象的属性图通常具有高度偏斜的幂律度 分布和比顶点更多的边数。 图计算系统中最基础的数据结构由顶点 V（或节点）、边 E、权重 D 这三因素组成，即 G=(V，E，D)，其中 V 为顶点（vertex），E 为边（edge），D 为权重（data）。顶点表示某 一事件中的对象， 而边则是

17、对不同对象关系的描述。 图计算系统基于顶点和边的方式存储图 数据和计算， 能够建构任意复杂的网络和模型， 完整且形象地映射分析人员想要研究的问题 域。 比如说， 对于一个消费者的原始购买行为， 有两类节点： 用户和产品， 边就是购买行为， 权重是边上的一个数据结构， 可以是购买次数和最后购买时间。 对于许多我们面临的物理世 界的数据问题，都可以利用图结构的来抽象表达：比如社交网络，网页链接关系，用户传播 网络，用户网络点击、浏览和购买行为，甚至消费者评论内容，内容分类标签，产品分类标 签等。 图计算系统的数据结构很好地表达了数据之间的关联性，关联性计算是大数据计算的 核心通过获得数据的关联性，

18、可以从噪音很多的海量数据中抽取有用的信息。比如，通 过为购物者之间的关系建模，就能很快找到口味相似的用户，并为之推荐商品；或者在社交 网络中，通过传播关系发现意见领袖与其操作符（例如，连接）可以跨越多个集合的数据流 系统相比，图处理系统（例如，顶点程序）中的操作通常相对于具有预先声明的稀疏结构的 单个属性图来定义。 虽然这有助于进行一系列优化， 但它也会使可能跨越多个图和子图的分 析任务的表达变得复杂。 2)2) 图图数据模型数据模型并行抽象并行抽象 图的经典算法中，从 PageRank 到潜在因子分析算法都是基于相邻顶点和边的属性迭代 地变换顶点属性， 这种迭代局部变换的常见模式形成了图并行

19、抽象的基础。 在图并行抽象中， 用户定义的顶点程序同时为每个顶点实现，并通过消息（例如 Pregel）或共享状态（例如 PowerGraph）与相邻顶点程序交互。每个顶点程序都可以读取和修改其顶点属性，在某些情 况下可以读取和修改相邻的顶点属性。 5 顶点程序并发运行的程度因系统而异。 大多数系统采用批量同步执行模型， 其中所有顶 点程序以一系列“超级步”同时运行。但是也有一些系统支持异步执行模型，通过在资源变 得可用时运行顶点程序来减轻落后者的影响。 3)3) 图图模型模型系统优化系统优化 对图数据模型进行抽象和对稀疏图模型结构进行限制，使一系列重要的系统得到了优 化。 比如 GraphLa

20、b 的 GAS 模型更偏向共享内存风格，允许用户的自定义函数访问当前顶点的 整个邻域，可抽象成 Gather、Apply 和 Scatter 三个阶段。GAS 模式的设计主要是为了适应 点分割的图存储模式，从而避免 Pregel 模型对于邻域很多的顶点、需要处理的消息非常庞 大时会发生的假死或崩溃问题。 6 2 技术篇技术篇 从上文的概述中我们看到， 图计算领域面临大数据环境带来的巨大挑战。 随着图数据量 上升速度的加快，图数据库和图计算受关注程度也在不断提高。 虽然各类图计算系统在不断优化，但是挑战依然存在。 2.1 技术挑战 图提供了非常灵活的抽象，用于描述离散对象之间的关系。科学计算、数

21、据分析和其他 领域的许多实际问题可以通过图以其基本形式建模， 并通过适当的图算法求解。 随着图的问 题规模越来越大，复杂性越来越大，它们很容易超过单处理器的计算和内存容量。鉴于并行 计算在许多科学计算领域取得了成功，并行处理似乎可以克服图计算中单个处理器资源受 到的限制。 当整体计算问题解决方法得到很好的平衡时，应用程序可以更好地执行和扩展，即，当 需要解决的问题、 用于解决问题的算法、 用于表达算法的软件以及运行软件的硬件使两者都 能很好地相互匹配。在很大程度上，并行科学计算的成功归功于这些方面，与典型的科学应 用完全匹配。解决科学领域中典型问题（通常涉及求解偏微分方程系统）的常用习语已经发

22、 展并成为科学计算界的标准实践。 同样， 适用于典型问题的硬件平台和编程模型也变得很普 遍。世界各地的机房包含运行用 MPI 编码的商用集群。 不过，对于开发主流并行科学应用程序而言，效果良好的算法、软件和硬件对于大规模 图问题并不一定有效。 图问题具有一些固有的特征， 使它们与当前的计算问题解决方法不匹 配。大图计算是大数据计算中的一个子问题，除了满足大数据的基本特性之外，大图计算还 有着自身的计算特性，相应地面临着新的挑战。特别是，图问题的以下属性对高效并行性提 出了重大挑战。 1)1) 局部性差局部性差 图表示着不同实体之间的关系， 而在实际的问题当中， 这些关系经常是不规则和无结构 的

23、，因此图的计算和访存模式都没有好的局部性，而在现有的计算机体系架构上，程序的性 能获得往往需要利用好局部性。所以，如何对图数据进行布局和划分，并且提出相应的计算 模型来提升数据的局部性，是提高图计算性能的重要方面，也是面临的关键挑战。 2)2) 数据及图结构驱动的计算数据及图结构驱动的计算 图计算基本上完全是由图中的数据所驱动的。 当执行图算法时， 算法是依据图中的点和 边来进行指导，而不是直接通过程序中的代码展现出来。所以，不同的图结构在相同的算法 7 实现上，将会有着不同的计算性能。因此，如何使得不同图结构在同一个系统上都有较优的 处理结果，也是一大难题。 3)3) 图数据的非结构化特性图

24、数据的非结构化特性 图计算中图数据往往是非结构化和不规则的， 在利用分布式框架进行图计算时， 首先需 要对图进行划分， 将负载分配到各个节点上， 而图的这种非结构化特性很难实现对图的有效 划分，从而达到存储、通信和计算的负载均衡。一旦划分不合理，节点间不均衡的负载将会 使系统的拓展性受到严重的限制，处理能力也将无法符合系统的计算规模。 4)4) 高访存高访存/ /计算比计算比 绝大部分的大图计算规模使得内存中无法存储下所有的数据， 计算中磁盘的 I/O 必不可 少，而且大部分图算法呈现出迭代的特征，即整个算法需要进行多次迭代，每次迭代需要遍 历整个图结构， 而且每次迭代时所进行的计算又相对较少

25、。 因此， 呈现出高的访存/计算比。 另外，图计算的局部性差，使得计算在等待 I/O 上花费了巨大的开销。 2.2 图算法与图计算框架简介 本节将重点介绍图算法与图计算框架， 为便于读者理解， 接下来先简要介绍一下图数据 库。 在众多不同的数据模型里， 关系数据模型自 20 世纪 80 年代就处于统治地位， 而且出现 了不少巨头，如 Oracle、MySQL，它们也被称为关系数据库管理系统（RDBMS）。然而， 随着关系数据库使用范围的不断扩大， 也暴露出一些它始终无法解决问题， 其中最主要的是 数据建模中的一些缺陷和问题，以及在大数据量和多服务器之上进行水平伸缩的限制。 因此，近年来诞生了

26、Neo4j，InfiniteGraph 等专注于图结构化存储与查询的图数据库。 与传统的关系型数据库相比， 图数据库善于处理大量的、 复杂的、 互联的、 多变的网状数据， 效率远远高于传统型数据库， 性能约有百倍以上的提升， 特别适合用于社交网络、 实时推荐、 银行交易环路、金融征信系统等领域。 图计算是基于图数据的分析技术与关系技术应运而生的，图计算系统就是针对处理图 结构数据的系统，并对这样的数据进行针对性优化的高效计算。与传统计算模型相比，图计 算模型主要针对解决以下问题： 1) 图计算的频繁迭代带来的读写数据等待和通信开销大的问题； 2) 图算法对节点和边的邻居信息的计算依赖问题； 3

27、) 图数据的复杂结构使得图算法难以实现分布不均匀的分块上并行计算的问题。 8 为应对以上问题， Google 基于 BSP （Bulk Synchronous Parallel） 推出了新的 “计算框架” Pregel。之后，CMU 提出了开源图计算框架 GraphLab。虽然二者都是对于复杂机器学 习计算的处理框架，用于迭代型（iteration）计算，但是二者的实现方法却采取了不同的路 径：Pregel 是基于大块的消息传递机制，GraphLab 是基于内存共享机制。同样的，Spark 也 提供了专门支持图计算的模块GraphX，可以用于实现复杂的图数据挖掘。 2.2.1 图算法图算法 对

28、于图数据，遍历算法是其它算法的基础。典型的图算法有 PageRank、最短路径、连 通分支、极大独立集、最小代价生成树以及 Bayesian Belief Propagation 等。图的最小生成树 在生活中常代表着最低的成本或最小的代价，常用 Prim 算法和 Kruskal 算法。社区发现， 最短路径，拓扑排序，关键路径也都有对应的算法。下面简单对图算法进行介绍。 社区发现（Community Detection） 社区发现算法是用来发现网络中的社区结构， 也可以看做是一种聚类算法。 社区发现算 法可以用来发现社交网络中三角形的个数（圈子），可以分析出哪些圈子更稳固，关系更紧 密，用来衡量

29、社群耦合关系的紧密程度。从一个人的社交圈子里面可以看出，三角形个数越 多，说明他的社交关系越稳固、紧密。在图计算的社交应用当中，像 Facebook、Twitter 等 社交网站，常用到的的社交分析算法就是社群发现。 PageRank PageRank 是 Sergey Brin 与 Larry Page 于 1998 年提出来的，用来解决链接分析中网页 排名的问题。PageRank 的计算充分利用了两个如果：数量如果和质量如果。PageRank 源自 搜索引擎，它是搜索引擎里面非常重要的图算法，可用来对网页做排序。比如我们在网页里 搜索 weibo，会出来非常多有着 weibo 关键字的网页

30、，可能有上千上万个相关网页，而 PageRank 可以根据这些网页的排序算法将其排序， 将一些用户最需要的网页进行优先展示。 最短路径 最短路径用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心 向外层层扩展，直到扩展到终点为止。最短路径在社交网络里面，有一个六度空间的理论， 表示你和任何一个陌生人之间所间隔的人不会超过五个。 最短路径是图算法中的一种， 在图 计算应用上很常见。 9 2.2.2 图计算框架图计算框架 接下来对主流的图计算框架进行简介。 依据大规模图计算系统的使用场景以及计算平台架构的不同，我们将其分为单机内存 图计算系统、单机外存图计算系统、分布式内存图计算系

31、统和分布式外存图计算系统。 图 3 图计算系统框架分类 单机内存图处理系统就是图处理系统运行在单机环境，并且将图数据全部缓冲到内存 当中。 单机外存图处理系统就是图处理系统运行在单机环境， 并且通过计算将图数据不断地 与内存和磁盘进行交互的高效图算法。分布式内存系统就是图处理系统运行在分布式集群 环境，并且所有的图数据加载到内存当中。分布式外存图计算系统将单机外存系统（Single- machine out-of-core systems）拓展为集群，能够处理边数量级为 trillion 的图。 下面对各类图计算框架逐一做简单介绍： 单机内存图处理系统 此类图计算系统单机运行， 可直接将图完全

32、加载到内存中进行计算。 但是单机的计算能 力和内存空间总是有限，故只能解决较小规模的图计算问题，比较有代表性的系统有 2013 年发布的 Ligra 和 Galois，以及 2015 年发布的 GraphMat 和 Polymer。 10 其中 Ligra 提出了根据图稠密情况自适应的切换计算模式，并提供了一种基于边映射， 顶点映射以及顶点集映射的并行编程算法。Galois 使用 DSLs（domain-specific languages）写 出更复杂的算法完成图分析工作，并发现当输入图是道路网络或者具有较大直径的图时能 获得一个数量级的性能提升，在现有的三种图 DSLs 基础上提供了轻量级

33、的 API，简化了图 算法的实现。 GraphMat 是第一个对多核 CPU 进行优化的以顶点为编程中心的轻量级图计算框架， 为 用户和开发者提供了友好的接口。 Polymer 则是针对在 NUMA 特性的计算机结构上运行图算法的优化，作者发现无论是 随机或者交错地分配图数据都会重大地束缚数据的本地性和并行性，无论是 intra-node 还是 inter-node，顺序访存都比随机访存的带宽高的多。 单机外存图处理系统 此类图计算系统单机运行， 但是将存储层次由 RAM 拓展到外部存储器如 SSD， Flash， SAS，HDD 等，使其所能处理的图规模增大。但受限于单机计算能力和外存存储系统的数 据交换的带宽限制也无法在可接受的情形下处理超大规模的图数据。典型的图计算系统有 GraphC