文档章节

图计算:一张图秒级洞察千亿级复杂关系

 透明的鱼
发布于 2018/08/29 09:46
字数 2283
阅读 12
收藏 0

在数据规模越来越大、数据结构越来越复杂的大数据时代,传统的关系型数据暴露出了建模缺陷、水平伸缩等问题,于是具有更强大表达能力的图数据受到业界极大的重视。如果把关系数据模型比做火车的话,那么现在的图数据建模可比做高铁。

什么是图呢?

图(Graph),将信息中的实体,以及实体之间的关系,分别抽象表达成为顶点以及顶点间的边这样的结构数据。

像Facebook和Twitter这样的社交网络,其数据天生就适合于图表示法。诸多典型的大数据应用易于通过图来进行建模,如交通网络、CDR通话图、用户与产品之间的二分图、论文中作者之间的合作关系网、文章之间的索引关系、金融交易网络等等。

于是,基于图数据的分析技术—关系分析(图计算)应运而生。图计算系统就是针对图结构数据处理的系统,并在这样的数据上进行针对性优化的高效计算。

我们可以用图这个通用的、富有表现力的结构来建模各种场景,从宇宙火箭的建造到道路系统,从食物的供应链及原产地追踪到人们的病历。

在许多实际场合中我们都能找到图分析的应用。

例如:

在金融风控中,将多种变量(如账号、交易、资金)之间的关系通过图联系在一起,共同分析其对金融安全的影响,典型的金融异构系统,如洗钱、庞氏骗局等都能反映出特定的图结构。

在大图上做环路检测可以有效识别循环转账,帮助预防信用卡诈骗;

分析可疑人物的近邻好友和基于属性图的社团发现可以进一步挖掘出骗子团伙或者僵尸账号。

知识图谱通过图来建立知识概念之间的联系,并在此基础上设计推理算法。

知识图谱常用来进行知识推理,从语义层面理解用户意图,改进搜索质量。

LinkedIn的知识图谱对会员显式输入的技能,比如“分布式系统”、“Hadoop”等,自动推理出其他技能,比如“产品管理”、“NoSQL”等。特别是AI和机器学习中需要处理很多由实体和关系构成的信息。例如,在推荐系统中,用户和电影就是实体,他们之间的喜好构成了实体间的关系;搜索查询和商品也是实体,他们之间的点击率构成了实体间的关系。

业界洞察

整个图计算领域可进一步细分为查询分析、计算引擎、存储管理、可视化等子方向。目前并没有一种涵盖所有子方向的图引擎。例如图数据库Neo4j、Titan等擅长于图数据的实时查询,但并不能高效地据进行离线分析;分析引擎Turi、GraphX侧重图数据的离线分析和挖掘,却不能对属性图进行管理,且不支持实时查询。

同时,图计算领域也面临大数据环境下带来的巨大挑战。就当前的社交网络而言,对全网做查询分析就意味着对数十亿节点(人物)数百亿边(关系)的大图进行操作。而规模更大的互联网、物联网可达到百亿节点千亿边甚至以上。在如此巨大数据量的情况下,实现高效高并发的查询是当前一大难点。

一方面,鉴于图数据结构的稀疏性,并不能通过GPU等硬件手段上取得很好的加速。

另一方面,图的局部性也有别于传统机器学习系统的数据组织形式。

社交网络中一个人的平均好友数达到数百,那他的2度好友就会达到数十万之多,于是探索一个人ego-net(对图中某节点做扩线查询得到的子图)往往会遍历上千万甚至更多条边。

在多机环境下,这些边往往分布在不同的机器上,进一步增大了遍历的难度。此外,随着数据复杂性的增加,节点和边往往带有属性信息。这些信息既可以是固有属性(如年龄、性别等),也可以是计算得到的结果(如介数中心度、pagerank值等),这些计算结果往往又是下一次查询的输入。属性管理与交互式计算查询,是图领域的另一大挑战。

华为图引擎服务GES

华为人工智能平台上的EYWA图引擎提供了从底层的图存储和管理、核心的高性能计算引擎、直到面向上层的图分析和图查询,一整套的关系网络分析解决方案,其基本特征如下:

 高性能

EYWA基于边集流的块状数据组织兼顾了图计算与图数据查询的性能要求,并集成了多种面向行业领域的优化算法。它通过优化的prefetch策略降低磁盘的IO操作的性能损耗,同时也通过松弛BSP模型来降低通信IO带来的性能损耗。相比Powergraph, GraphX, Powerlyra等计算速度提速4~10倍以上,而图数据查询的性能提升更加明显,具备秒级多跳实时查询的强大性能。

 一体化

EYWA实现图计算、图查询和图存储的一体化:提供基于属性图模型的数据存储,支持基本查询(点查、边查、遍历、属性过滤等),常用的图算法(PageRank, SSSP, K-core, graph metrics等)可以基于图的结构和属性进行计算,并将结果回写到图的某一属性中便于后续查询。

EYWA已经在百亿节点和千亿边的大规模图实践上验证了其高并发、低时延的能力。

其中一份实验用到的公开数据集是基于斯坦福大学SNAP研究组提供的Friendster, 来自真实的社会网络。我们用全球计算机排名Graph500提供的Kronecker代码在对该数据集进行扩展,形成了具有2.5亿点110亿边的大图和5.2亿点和1011亿边的超大图。通过扩线查询模拟对社交网络节点的ego-net的探索,我们的实验结果显示在百亿边图100并发下的3跳扩线查询总响应时间基本在0.1秒以内。

以下是针对不同并发请求数EYWA系统的响应时间(上:并发状态下单个请求的执行时间;下:所有并发请求执行完成的总时间);千亿边图100并发下3跳扩线查询总响应时间在0.5~3秒(随种子节点不同而变化)。

EYWA图引擎支持基于属性图模型的复杂属性管理、内置了20余种拓扑度量和基本图分析算法,并通过服务化API将图引擎的能力开放出去,提供全方位的关系网络洞察。

在电信网络等行业实践中,利用EYWA我们很自然地表达了各类交换机、路由器、终端设备等网元构成的物理通信网络,以及在其上抽象出来的逻辑网络,并在此基础上运行复杂的网络规划仿真算法,极大提升了业务工作效率;

在金融、公共安全等行业实践中,利用EYWA可表达大量的人物、账户、商家、手机等相互关联的不同实体,并通过顶点和边上的属性(如人物的年龄、性别,账户的创建时间,人和商家之间的交易金额等)精细描述真实世界的信息。基于EYWA大规模高并发的支持,以及内置的最短路径、中间人查找、回路分析、邻居子图等分析功能,客户能够高效地进行反欺诈、团伙发现等业务计算、帮助业务人员发现大量关联数据背后有价值的隐藏信息。

转自:华为云社区  作者:mr.FangYang 

原文链接:http://t.cn/RFADb7C

华为图引擎服务:http://t.cn/RFz2GBP

© 著作权归作者所有

粉丝 0
博文 96
码字总数 153598
作品 0
私信 提问
可视化大数据分析挖掘工具 - OpenFEA

一、简介 FEA是一站式大数据敏捷分析中间件,融合了内存计算、机器学习、交互分析、可视化分析等技术,涵盖数据收集、数据探索、构建模型、发布模型、可视化展示、分析门户等功能,无需复杂编...

openfea
2017/05/27
15.2K
8
分析型数据仓库中读写分离的实现

作者:张广强 和以 MySQL 为代表的传统事务型数据库相比,数据仓库有一个很大的特点,就是主要面向批量写和查询进行优化,可以不支持更新、事务这些高级特性。一些商用的数据仓库分析系统,例...

小数点
2017/11/27
0
0
分析型数据仓库中读写分离的实现

本文作者为神策数据(ID:SensorsDataCrop)资深研发工程师张广强,版权归神策数据所有。 和以 MySQL 为代表的传统事务型数据库相比,数据仓库有一个很大的特点,就是主要面向批量写和查询进...

dev_csdn
2017/11/24
0
0
腾讯技术工程 |腾讯数据平台部总监刘煜宏:这5大产品平台,展示了腾讯大数据的核心能力

12月13日,“2017互联网+大数据高峰论坛”在北京中国大饭店拉开帷幕。来自政府、研究机构及高校、企业的大数据专业人士共聚一堂,以“慧聚数据之力,赋能智慧政企”为主题,畅谈大数据的现状...

腾讯技术
2018/01/31
0
0
2019 年第 3 期 | Apache Kylin Meetup

5月25日,由 Kyligence 主办的Apache Kylin Meetup 即将在成都登陆!在北京站召开之际,小编就在后台收到了很多成都 “Kyliner” 的活动请求,为了响应大家的深情呼唤,我们特地寻找了四位来...

ApacheKylin
04/28
22
0

没有更多内容

加载失败,请刷新页面

加载更多

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
40分钟前
2
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
1
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
3
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部