AMiner出品|迅速带你入门图计算领域，技术人才趋势产业一应俱全

AMiner今日发布2019年第三期研究报告《人工智能之图计算》。

目前已发布两期报告：

第一期《人工智能之数据挖掘》：微信公众号后台回复“15”即可获取。

第二期《人工智能之知识图谱》：微信公众号后台回复“16”即可获取。

如需《人工智能之图计算》，请在微信公众号菜单栏获取或在后台回复“17”。

如今，数据已经渗透到每一个行业和业务职能领域，尤其近年来，全球大数据进入加速发展时期，数据量呈现爆发式增长，大数据吸引了越来越多的关注，大数据时代已然来临。

图计算简单来讲就是研究在这些大量数据中，如何高效计算、存储并管理图数据等问题的领域。传统的关系型数据暴露出了建模缺陷、水平伸缩等问题，于是具有更强大表达能力的图数据受到业界极大的重视。如果把关系数据模型比作火车的话，那么现在的图数据建模可比作高铁。

大规模图数据时代下的图计算

图（Graph）是一种重要的数据结构，它由节点V（或称为顶点，即个体），与边E（即个体之间的联系）构成，我们一般将图表示为G（V，E）。图数据的典型例子有网页链接关系、社交网络、商品推荐等。

对应互联网来说，可以把web网页看作顶点，页面之间的超链接关系作为边；对应社交网络来说，可以把用户看作顶点，用户之间建立的关系看作边。

比如微信的社交网络，是由节点（个人、公众号）和边（关注、点赞）构成的图；淘宝的交易网络，是由节点（个人、商品）和边（购买、收藏）构成的图。

如此一来，抽象出来的图数据便可作为研究和商用的基础，由此探究出“世界上任意两个人之间的人脉距离”、“关键意见领袖”等。将这些应用到商业领域，其底层的运算往往是图相关的算法。

比如图的最短路径算法可以做好友推荐，计算关系紧密程度；对图做PageRank可以用于传播影响力分析，找出问题的中心，做搜索引擎的网页排名；最小连通图可以识别洗钱或虚假交易等等。

近年来，图数据规模呈指数级增长，可能达到数十亿的顶点和数万亿的边，且还在不断增长，单机模式下的图计算已经不适合目前数据的增长，传统的分布式大数据处理平台比如MapReduce、Spark也出现网络和磁盘读写开销大、运算速度慢、处理效率极低的问题。

图计算的特征

初提图计算，很多人会以为这是一种专门进行图像处理的技术。事实上，图计算中的“图”是针对“图论”而言的，是一种以“图论”为基础的对现实世界的一种“图”结构的抽象表达，以及在这种数据结构上的计算模式。

图数据结构很好的表达了数据之间的关联性，关联性计算是大数据计算的核心——通过获得数据的关联性，可以从噪音很多的海量数据中抽取有用的信息。

图计算技术解决了传统的计算模式下关联查询的效率低、成本高的问题，在问题域中对关系进行了完整的刻画，并且具有丰富、高效和敏捷的数据分析能力，其特征有如下三点：

a. 基于图抽象的数据模型

图计算系统将图结构化数据表示为属性图，它将用户定义的属性与每个顶点和边缘相关联。属性可以包括元数据（例如，用户简档和时间戳）和程序状态（例如，顶点的PageRank或相关的亲和度）。源自社交网络和网络图等自然现象的属性图通常具有高度偏斜的幂律度分布和比顶点更多的边数。

b. 图数据模型并行抽象

图的经典算法中，从PageRank到潜在因子分析算法都是基于相邻顶点和边的属性迭代地变换顶点属性，这种迭代局部变换的常见模式形成了图并行抽象的基础。在图并行抽象中，用户定义的顶点程序同时为每个顶点实现，并通过消息（例如Pregel）或共享状态（例如PowerGraph）与相邻顶点程序交互。每个顶点程序都可以读取和修改其顶点属性，在某些情况下可以读取和修改相邻的顶点属性。

c. 图模型系统优化

对图数据模型进行抽象和对稀疏图模型结构进行限制，使一系列重要的系统得到了优化。

比如GraphLab的GAS模型更偏向共享内存风格，允许用户的自定义函数访问当前顶点的整个邻域，可抽象成Gather、Apply和Scatter三个阶段。GAS模式的设计主要是为了适应点分割的图存储模式，从而避免Pregel模型对于邻域很多的顶点、需要处理的消息非常庞大时会发生的假死或崩溃问题。

面临的技术挑战

图计算领域面临大数据环境带来的巨大挑战。随着图数据量上升速度的加快，图数据库和图计算受关注程度也在不断提高。虽然各类图计算系统在不断优化，但是挑战依然存在。

图提供了非常灵活的抽象，用于描述离散对象之间的关系。科学计算、数据分析和其他领域的许多实际问题可以通过图以其基本形式建模，并通过适当的图算法求解。随着图的问题规模越来越大，复杂性越来越大，它们很容易超过单处理器的计算和内存容量。鉴于并行计算在许多科学计算领域取得了成功，并行处理似乎可以克服图计算中单个处理器资源受到的限制。

当整体计算问题解决方法得到很好的平衡时，应用程序可以更好地执行和扩展，即，当需要解决的问题、用于解决问题的算法、用于表达算法的软件以及运行软件的硬件使两者都能很好地相互匹配。在很大程度上，并行科学计算的成功归功于这些方面，与典型的科学应用完全匹配。

解决科学领域中典型问题（通常涉及求解偏微分方程系统）的常用习语已经发展并成为科学计算界的标准实践。同样，适用于典型问题的硬件平台和编程模型也变得很普遍。世界各地的机房包含运行用MPI编码的商用集群。

不过，对于开发主流并行科学应用程序而言，效果良好的算法、软件和硬件对于大规模图问题并不一定有效。图问题具有一些固有的特征，使它们与当前的计算问题解决方法不匹配。大图计算是大数据计算中的一个子问题，除了满足大数据的基本特性之外，大图计算还有着自身的计算特性，相应地面临着新的挑战。特别是，图问题的以下属性对高效并行性提出了重大挑战。

a. 局部性差

图表示着不同实体之间的关系，而在实际的问题当中，这些关系经常是不规则和无结构的，因此图的计算和访存模式都没有好的局部性，而在现有的计算机体系架构上，程序的性能获得往往需要利用好局部性。所以，如何对图数据进行布局和划分，并且提出相应的计算模型来提升数据的局部性，是提高图计算性能的重要方面，也是面临的关键挑战。

b. 数据及图结构驱动的计算

图计算基本上完全是由图中的数据所驱动的。当执行图算法时，算法是依据图中的点和边来进行指导，而不是直接通过程序中的代码展现出来。所以，不同的图结构在相同的算法实现上，将会有着不同的计算性能。因此，如何使得不同图结构在同一个系统上都有较优的处理结果，也是一大难题。

c. 图数据的非结构化特性

图计算中图数据往往是非结构化和不规则的，在利用分布式框架进行图计算时，首先需要对图进行划分，将负载分配到各个节点上，而图的这种非结构化特性很难实现对图的有效划分，从而达到存储、通信和计算的负载均衡。一旦划分不合理，节点间不均衡的负载将会使系统的拓展性受到严重的限制，处理能力也将无法符合系统的计算规模。

d. 高访存/计算比

绝大部分的大图计算规模使得内存中无法存储下所有的数据，计算中磁盘的I/O必不可少，而且大部分图算法呈现出迭代的特征，即整个算法需要进行多次迭代，每次迭代需要遍历整个图结构，而且每次迭代时所进行的计算又相对较少。因此，呈现出高的访存/计算比。另外，图计算的局部性差，使得计算在等待I/O上花费了巨大的开销。

图计算框架

接下来对主流的图计算框架进行简介。

依据大规模图计算系统的使用场景以及计算平台架构的不同，我们将其分为单机内存图计算系统、单机外存图计算系统、分布式内存图计算系统和分布式外存图计算系统。

单机内存图处理系统就是图处理系统运行在单机环境，并且将图数据全部缓冲到内存当中。单机外存图处理系统就是图处理系统运行在单机环境，并且通过计算将图数据不断地与内存和磁盘进行交互的高效图算法。

分布式内存系统就是图处理系统运行在分布式集群环境，并且所有的图数据加载到内存当中。分布式外存图计算系统将单机外存系统（Single-machine out-of-core systems）拓展为集群，能够处理边数量级为trillion的图。

技术资源

Open Academic Graph（OAG）是通过链接Microsoft Academic Grapg（MAG）和AMIner两个大型学术图表生成的。（https://www.aminer.cn/oag2019 ）我们将OAG2019的统计数据呈现为下面三个图，包括Venue Collection、Paper Collection和Author Collection三部分。

Venue Colletion

Paper Collection

Author Collection

学者情况概览

本节对这些学者进行了简单的统计分析，包括他们的分布地图、迁徙状况、机构分布等。

全球图计算领域活跃学者分布图

由AMiner绘制的全球图计算领域活跃学者所在地区的分布地图（如上图所示）可以看出，图计算领域学者在北美洲最为集中，亚洲次之，欧洲西部该领域的人才分布也较多。

分国家来看，美国东部该领域学者较为集中，其次是中国，欧洲主要在德国和英国拥有该领域较多数量的学者。

下图是国内图计算领域活跃学者的分布图，由该图可见，国内学者集中分布在长三角、珠三角以及京津冀等地区。从全局来看，内陆地区的学者分布数量相对沿海地区要少，沿海地区珠三角是全国学者分布最为集中的地区，内陆地区的学者则主要集中分布在华北及我国东北三省地区，学者数量呈由南到北逐渐减少的分布状态。

中国图计算领域活跃学者分布图

除了地区分布，我们还对图计算领域学者的迁徙路径做了分析。由下图可以看出，美国是图计算领域人才流动大国，人才输入和输出幅度领先于其他国家，且从数据来看人才流入大于人才流出。中国、英国、印度等国人才迁徙流量小于美国，其中中国与印度有轻微的人才流失现象。除美国和中国外，其余各国图计算学者的流失和引进是相对比较均衡的。

全球图计算领域活跃学者迁徙图

人才的频繁流入流出，使得该领域的学术交流活动增加，带动了人才质量的提升的同时，也促进了领域理论及技术的更新迭代，至此逐渐形成一种良性循环的过程。

全球图计算领域活跃学者机构分布

如上图所示，是对全球计算机图计算领域学者所属机构的统计，数据显示多名学者就职于同一机构的现象较为普遍，机构所拥有的学者数量越多，一定程度上越能反映出该机构的科研与创新能力，直观地印证其在该领域具备更强的竞争力，因此我们对表现最突出的机构进行了以上排名。

在图计算领域，Microsoft（微软）拥有的影响力学者数量最多，共55人，位于榜首，Facebook以26名位居第二，University of California（加利福尼亚大学）共拥有20名学者位居第三。中国拥有10位以上学者的机构有香港中文大学和中国科学技术大学，分别拥有17名和11名学者。中国拥有该领域学者数10人以下的机构分别有Peking University（北京大学）、Hong Kong University of Science and Technology（香港科技大学）、Fudan University（复旦大学）以及Tsinghua University（清华大学）。

产业应用

图就在我们身边，它们遍布各地，如Facebook、谷歌、Twitter、电信、生物、医药、营销和股票市场。同时，它们影响计算机科学的众多领域，包括软件工程、数据库和集成电路的设计。

目前，图计算已应用于医疗、金融、社交分析、自然科学以及交通等领域，很多互联网公司以及很多年轻的人工智能领域创业公司也都开展了图计算相关的业务。以下我们就图计算的主要应用场景与公司进行简介。

a. 医疗行业的应用

图计算的出现使得对病人的智能诊断成为可能。对病人开具处方需要依据病人的病情特征与以往的健康情况，以及药物的相关情况。过去的医疗大多依赖于医生的个人经验与病人的自我描述，传统的数据处理系统无法一次性调出多个与病人情况、保险情况、药物情况相关的数据库——挑战在于信息必须由多个在线资源拼凑而成，包括列出疾病和治疗的电子病历、医疗保险或其他跟踪医疗服务的数据库、描述药物的数据库，在某些情况下，还有跟踪临床试验的独立数据库。

b. 金融行业的应用

在金融实体模型中，存在着许许多多不同类型的关系，以及数十亿的结点和边。有些是相对静态的，如企业之间的股权关系、个人客户之间的亲属关系，有些则是不断地在动态变化，如转账关系、贸易关系等等。这些静态或者动态的关系背后，隐藏着很多以前我们不知道的信息。

之前，我们在对某个金融业务场景进行数据分析和挖掘过程中，通常都是从个体（如企业、个人、账户等）本身的角度出发，去分析个体与个体之间的差异和不同，很少从个体之间的关联关系角度去分析，因此会忽略很多原本的客观存在，也就更无法准确达到该业务场景的数据分析和挖掘目标。而图计算和基于图的认知分析正是在这方面弥补了传统分析技术的不足，帮助我们从金融的本质角度来看这个问题，从实体和实体之间的经济行为关系出发来分析问题。

c. 互联网行业的应用

目前大数据在互联网公司主要应用在广告、报表、推荐系统等业务上。在广告业务方面需要大数据做应用分析、效果分析、定向优化等，在推荐系统方面则需要大数据优化相关排名、个性化推荐以及热点点击分析等。图计算的出现满足了这些计算量大、效率要求高的应用场景的需求。

图计算模型在大数据公司，尤其是IT公司是非常流行的一大模型，它是很多实际问题最直接的解决方法。近几年，随着数据的多样化，数据量的大幅度提升和算力的突破性进展，超大规模图计算在大数据公司发挥着越来越重要的作用，尤其是以深度学习和图计算结合的大规模图表征为代表的系列算法。

图计算的发展和应用有井喷之势，各大公司也相应推出图计算平台，例如Google Pregel、Facebook Graph、腾讯星图、华为图引擎服务GES、百度Hugegraph、阿里云关系网络分析、费马科技、亚马逊Neptune、TigerGraph等平台。