Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

迅速带你入门图计算领域,技术人才趋势产业一应俱全

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

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

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

图(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等平台。

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
入门图计算图像处理
23
相关数据
Amazon机构

亚马逊(英语:Amazon.com Inc.,NASDAQ:AMZN)是一家总部位于美国西雅图的跨国电子商务企业,业务起始于线上书店,不久之后商品走向多元化。目前是全球最大的互联网线上零售商之一,也是美国《财富》杂志2016年评选的全球最大500家公司的排行榜中的第44名。

https://www.amazon.com/
相关技术
华为机构

华为创立于1987年,是全球领先的ICT(信息与通信)基础设施和智能终端提供商。

https://www.huawei.com/cn/
Microsoft机构

微软是美国一家跨国计算机科技公司,以研发、制造、授权和提供广泛的计算机软件服务为主。总部位于美国华盛顿州的雷德蒙德,最为著名和畅销的产品为Microsoft Windows操作系统和Microsoft Office办公室软件,以及Xbox的游戏业务。微软是美国《财富》杂志2015年评选的世界500强企业排行榜中的第95名。

https://www.microsoft.com/en-us/about
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

数据分析技术

数据分析是一类统计方法,其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系,并绘制出统计信息图,以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据,以便弄清哪些是同质的,从而更好地了解数据。 数据分析可以处理大量数据,并确定这些数据最有用的部分。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

MapReduce技术

MapReduce,一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(归约)",是其主要思想,皆从函数式编程语言借用。它还借用了矢量编程语言的特性。它极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。 当前的软件实现是指定一个Map(映射)函数,用来把一组键值对映射成一组新的键值对,指定并发的Reduce(归约)函数,用来保证所有映射的键值对中的每一个共享相同的键组。

噪音技术

噪音是一个随机误差或观测变量的方差。在拟合数据的过程中,我们常见的公式$y=f(x)+\epsilon$中$\epsilon$即为噪音。 数据通常包含噪音,错误,例外或不确定性,或者不完整。 错误和噪音可能会混淆数据挖掘过程,从而导致错误模式的衍生。去除噪音是数据挖掘(data mining)或知识发现(Knowledge Discovery in Database,KDD)的一个重要步骤。

大数据技术技术

大数据,又称为巨量资料,指的是传统数据处理应用软件不足以处理它们的大或复杂的数据集的术语。

图论技术

图论是以“图”为研究对象的一个数学分支,是组合数学和离散数学的重要组成部分。图是用来对对象之间的成对关系建模的数学结构,由“顶点”(又称“节点”或“点”)以及连接这些顶点的“边”(又称“弧”或“线”)组成。值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。

图像处理技术

图像处理是指对图像进行分析、加工和处理,使其满足视觉、心理或其他要求的技术。 图像处理是信号处理在图像领域上的一个应用。 目前大多数的图像均是以数字形式存储,因而图像处理很多情况下指数字图像处理。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

因子分析技术

因子分析在统计学中是一种常用的降维方法,目的在于用更少的、未观测到的变量(factor)描述观测到的、相关的变量。更准确的来说,因子分析假设在观测到的变量间存在某种相关关系,从观测变量的矩阵内部相关关系出发找到潜变量(latent variables)从而使得潜变量和观测变量之间的关系成立

阿里云机构

阿里云创立于2009年,是全球领先的云计算及人工智能科技公司,致力于以在线公共服务的方式,提供安全、可靠的计算和数据处理能力,让计算和人工智能成为普惠科技。 阿里云服务着制造、金融、政务、交通、医疗、电信、能源等众多领域的领军企业,包括中国联通、12306、中石化、中石油、飞利浦、华大基因等大型企业客户,以及微博、知乎、锤子科技等明星互联网公司。在天猫双11全球狂欢节、12306春运购票等极富挑战的应用场景中,阿里云保持着良好的运行纪录。 阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。 2014年,阿里云曾帮助用户抵御全球互联网史上最大的DDoS攻击,峰值流量达到每秒453.8Gb 。在Sort Benchmark 2016 排序竞赛 CloudSort项目中,阿里云以1.44$/TB的排序花费打破了AWS保持的4.51$/TB纪录。在Sort Benchmark 2015,阿里云利用自研的分布式计算平台ODPS,377秒完成100TB数据排序,刷新了Apache Spark 1406秒的世界纪录。 2018年9月22日,2018杭州·云栖大会上阿里云宣布成立全球交付中心。

https://www.aliyun.com/about?spm=5176.12825654.7y9jhqsfz.76.e9392c4afbC15r
百度智能云机构

百度是全球最大的中文搜索引擎,是一家互联网综合信息服务公司,更是全球领先的人工智能平台型公司。2000年1月1日创立于中关村,公司创始人李彦宏拥有“超链分析”技术专利,也使中国成为美国、俄罗斯、和韩国之外,全球仅有的4个拥有搜索引擎核心技术的国家之一。

http://www.baidu.com
腾讯机构

腾讯,1998年11月诞生于中国深圳,是一家以互联网为基础的科技与文化公司。我们的使命是“通过互联网服务提升人类生活品质”。腾讯秉承着 “一切以用户价值为依归”的经营理念,为亿万网民提供优质的互联网综合服务。 腾讯的战略目标是“连接一切”,我们长期致力于社交平台与数字内容两大核心业务:一方面通过微信与QQ等社交平台,实现人与人、服务及设备的智慧连接;另一方面为数以亿计的用户提供优质的新闻、视频、游戏、音乐、文学、动漫、影业等数字内容产品及相关服务。我们还积极推动金融科技的发展,通过普及移动支付等技术能力,为智慧交通、智慧零售、智慧城市等领域提供有力支持。

http://www.tencent.com/
相关技术
推荐文章
zan
作者讲的不错,其实我们在现实图计算场景中常遇到的问题,总结一下可以概括为以下三点:图计算问题十分复杂,计算模式多样,解决方案碎片化。图计算学习难度强,成本大,门槛高。图的规模和数据量大,计算复杂,效率低。GraphScope的研发方向主要就是解决以上问题。它的底层是一个分布式内存数据管理系统 vineyard。它提供了高效和高层次的数据抽象(包括但不限于图,tensor,vector 等),支持管理数据的分区、元数据等,可以为上层应用提供本机零拷贝的数据读取。中间是引擎层,分别由交互式查询引擎 GIE,图分析引擎 GAE,和图学习引擎 GLE 组成。有机会给大家细说,这里就不展开了。最上层是开发工具和算法库。GraphScope 提供了各类常用的分析算法,包括连通性计算类、社区发现类和 PageRank、中心度等数值计算类的算法,后续会不断扩展算法包,在超大规模图上提供与 NetworkX 算法库兼容的分析能力。我们公司的项目也会用到图计算,最近同事都在研究使用GraphScope ,目前得到的反馈都还挺不错的,据说运算速度比想象得要快。
1
有没详细点的介绍