具有内置并行性的图算法之美

2015-02-09

很多人都知道,图算法是复杂业务场景中最有效的、有时甚至是唯一的解决方案,例如将不同的用户群体聚类(社区检测),找到有影响力的人或实体(PageRank算法),或预测用户行为以进行个性化推荐(标签传播算法)。但少有人知道,对于解决两实体间存在未知跳数的连接的问题,图也是一把能手。这类问题在很多行业中都很常见,包括企业知识图谱、供应链分析和能源流计算等场景。


本文描述了图是如何以自然、简洁而又有效的方式解决这类问题的,以及面对涉及数亿个实体和关系的查询时,如何仍能做到亚秒级响应的。


问题描述


让我们看一个分析公司之间关系的简单例子。


这个例子只有一张关于所有权的表,这张表有公司、控股公司以及比例三列,每一行描述的是某家公司的控股公司对该公司的持股比例。(译者注:这里隐含着一个事实,同一家公司的所有控制公司的持股比例之和为100%。)


业务查询(输出):找到拥有A公司最多的前K家“最终控股公司”。所谓“最终控股公司”,指的是不由任何其他公司控股的公司。


输入:公司A的名称,整数K.


以下图举例,输入为公司1,则公司6和公司9都是公司1的“最终控股公司”,其中公司9占有了更大的持股比例。



挑战

这里有两个挑战:


1.连接的跳数未知。我们始终不清楚一家公司会有多少层/跳的控股公司(这里包括直接的控股公司,也包括间接的控股公司)。


2.从公司A到其间接控股公司X,很可能有多条路径。例如,从某条控股路径上看,公司X与公司A中间隔着5家控股公司,而从另一条控股路径上看,公司X与公司A隔着3家控股公司。更麻烦的是,这两条路径上的中间控股公司还可能是有重叠的。


具有内置并行性的图解决方案

接下来我们介绍如何使用具有内置并行性的图数据库及其图查询语言(比如TigerGraph及其查询语言GSQL),来轻松高效地解决这类问题。并行性之所以重要,是因为它解决起许多图相关问题时,既自然又有效。


研究过一些图算法的计算机科学家知道,他们常常会有一些步骤是以“对于每个顶点/对于每个边/对于顶点V的每个邻居”开始的,这里的“对于每个”(for each)意味着我们需要为一个集合中的每个成员执行相同的任务。


如果集合很大,那么要快速地完成这项工作,自然是要并行运算的。GSQL具有内置的并行性,因此很容易描述这种“对于每个”的任务。


解决以上公司所有权问题有几种不同的方法,这恰恰说明了GSQL的强大和灵活性。TigerGraph通过并行地执行读取-计算-更新操作,让查询和算法执行起来就像对图的分布式游走/遍历过程一样:首先指定一些顶点,然后按计划一步一步地游走/遍历到它们相邻的顶点上去。在遍历的同时,我们从顶点或边上收集数据。我们还可以运算出一些中间数据传递给我们途经的顶点,也可以运算出一些结果数据。


方法一




总体设计是这样的,要两次遍历公司所有权图,每次都从输入的公司A开始,并一步一步通过控股关系的边向外跳。

 

第一次遍历是为了做准备工作。它只是简单地统计一下,对于公司A的任一直接或间接的控股公司Y,公司Y直接控股的公司中,有多少公司也是A直接或间接的控股公司的。(译者注:如果把公司A的所有控股公司及相关控股关系当成一张新图的话,这里计算的相当于这张新图的入度indegree。


比如以公司1为输入,那么公司1、2、3、7、4、9组成新图。这样,公司4的入度为2,上级节点为公司3和公司7;公司2的入度为1,上级节点为1,因为虽然公司8也是公司2的上级节点,但它不在新图上。)。


这个控股公司数的作用在于,当第二次遍历时,我们能通过它确保,在通过公司Y跳向公司Y的直接控股公司(即Y的下级节点)之前,已经把公司Y直接控股的所有公司(即它的上级节点)都已经遍历过了。举个例子,图1中公司4的控股公司数是2,因为有两个它直接控股的公司也是公司1的控股公司,即公司3和公司7。

 

第二次遍历过程中,将持股比例传递给公司A的所有直接或间接控股公司。每家控股公司通过第一步计算出的数字,等待确定已经遍历过其所有上级节点,才会跳向其下级节点。


接着,它将自己对公司A的持股比例,按给它的控股公司(下级节点)对它的持股比例,传递给它的控股公司(下级节点)。对于图1的示例,在公司2算出自身对公司A的股权比例为70%之后,将这个数字传递给其直接控股公司(下级节点)公司5和公司3。公司5得到的数字即为42%(70%*0.6),公司3得到的数字则为28%(70%*0.4)。


需要注意的是,由于我们对公司Y的持腔比例的计算往往是一次性的,因此遍历两回仍然足够高效。但像在供应链和能源流分析这样的场景下,它们的计算过程(例如,计算价格、电压或电流的变化量)则是计算密集度更高的,因此要达到实时性能,单次遍历完成计算就显得尤为重要。


请参见图2中的GSQL查询。完整的解决方案包括图形模型和GSQL查询可在TigerGraph的Github(https://github.com/tigergraph/ecosys/tree/master/blog_scripts/company_ownership_graph)获得。

CREATE QUERY getOwnershipPert (vertex<Company> inputComp) FOR GRAPH FinalOwner {
SumAccum<int> @msgCnt1, @msgCnt2; OrAccum<bool> @visited; SumAccum<float> @score = 0; SetAccum<vertex> @@results;
Start = {inputComp};
WHILE Start.size() > 0 limit 8 DO Start = SELECT t FROM Start:s-(ControlledBy:e)-:t ACCUM t.@msgCnt1 += 1 POST-ACCUM s.@visited = true HAVING t.@visited == false; // don't start again for the second visit; end;
Start = {inputComp};
Start = SELECT s FROM Start:s ACCUM s.@score = 1; // initialize @score
WHILE Start.size() > 0 LIMIT 8 DO Start = SELECT t FROM Start:s-(ControlledBy:e)-:t ACCUM t.@msgCnt2 += 1, t.@score += s.@score * e.weight POST-ACCUM CASE WHEN t.outdegree("ControlledBy") == 0 THEN @@results += t END HAVING t.@msgCnt2 == t.@msgCnt1; // make sure got all the scores END;
Start = @@results;
Start = SELECT s FROM Start:s ORDER BY s.@score desc LIMIT 5; PRINT Start;}


方法二




具有内置并行性的高级图查询语言(如GSQL)表达业务逻辑的能力很强,相比之下,使用非关系性数据库(NoSQL)的低级API表达起来则显得相当笨重,而对于SQL来说甚至会是不可实现的。


我们的第二种方法不需要第一种方法中的准备阶段。原因在于可以利用这样一个业务常识,即公司Y对公司A的持股比例是可以累加的。这意味着,我们可以沿着各条路径单独计算公司的持股比例,如果多条路径都经过同一个顶点,不管路径何时到达该顶点,我们只需添加每条路径的贡献量即可。


如图1所示,在第2跳时,公司7告诉其控股公司4,它拥有公司A 30%的股份。在第3跳时,公司4告诉其控股公司9,它拥有公司A 30%的股份;公司3告诉公司4,它拥有公司 28%的股份。


在第4跳时,公司4再次传递公司9一个信息,告诉它拥有公司A另外28%的股份,这样其股份就从30%更新为58%。


 

CREATE QUERY getOwnershipPertDelta(vertex<Company> inputComp) FOR GRAPH FinalOwner {     SumAccum<float> @deltaOld, @deltaNew, @score;  SetAccum<vertex> @@results;    Start = {inputComp};    Start = SELECT s FROM Start:s ACCUM s.@score = 1, s.@deltaOld = 1;
WHILE Start.size() > 0 LIMIT 8 DO Start = SELECT t FROM Start:s-(ControlledBy:e)-:t ACCUM t.@deltaNew += s.@deltaOld * e.weight POST-ACCUM t.@score += t.@deltaNew, t.@deltaOld = t.@deltaNew, t.@deltaNew = 0, CASE WHEN t.outdegree("ControlledBy") == 0 THEN @@results += t END; END;
Start = @@results; Start = SELECT s FROM Start:s ORDER BY s.@score desc LIMIT 5; PRINT Start;}


结论

现实世界中的问题(如供应链优化、物流路径、企业知识图谱、反欺诈、风险管理等)由于数据高度互联,可能会非常复杂。关系型数据库和非关系型数据库(NoSQL)的设计初衷并未考虑到,如何有效地表达和解决这些重要的问题。


开发人员也不想通过Java或C++之类的语言,从头开始编码来解决这类问题,因为这样耗时耗力,容易出错,难以维护,不可复用,而且缺少并行或分布式计算的能力。惟有使用具有内置并行性的高级图查询语言,才能漂亮地解决这类问题。


点击底部“阅读原文下载原生并行图》电子书看更多图数据库技术干货

了解更多TigerGraph应用

点击图片阅读


企业为什么要重视图数据库?

使用TigerGraph是一种怎样的体验?

新型图查询语言GSQL好用吗?

相关文章

基于图的算法在美联风控中的应用实践

2015-02-16
图相关的算法中我们主要使用了标签图模型,即在大规模图属性结构中实现社区发现算法,从而打击风险团伙.二、算法在调研多种大...

基于Delaunay图的快速最大内积搜索算法

2015-02-14
算法很简单,trade-off有两个:只在当前图上已有的点中去找最近的M个点,这点可以用上面的贪心算法来做.本来德劳内图是无向边...

图网络中的社群及社群发现算法

2015-02-14
验证了图当中的强弱连接,从而引出社群概念,然后介绍了一种简单的社群发现算法Louvain Algorithm,通过最大化Modularity Q来保...

「多图警告」手撕排序算法 - iOS进阶必备

2015-02-13
加个“星标”,一起学算法作者 | Lefex来源 | 超越技术整理 | 程序... arr[i] > 6 和 arr[j] =j,停止移动.图中的 L,R 是指快速排序开始时序...

【2020新书】图机器学习Neo4j算法与应用,142页pdf

2015-02-13
图驱动机器学习教你如何使用基于图形的算法和数据组织策略来开发高级的机器学习应用程序.对这项技术对于任何涉及到大型数据集...

【人大】图实现算法综述与评测分析

2015-02-13
四类图实现算法的设计思想、适用条件、算法流程等进行综述分析, 通过实验对算法进行准确性、计算复杂度、可靠性等方面的比较和...

鲸品课 | 鲸厂高级风控之图算法,教你抵御金融欺诈

2015-02-13
下面分享的图算法,就能解决上述问题.“图”可以将这些一个个看似有良好记录的个体关联起来,发现破绽,并一网打尽.Graph简...

百变应用场景下,优酷基于图执行引擎的算法服务框架筑造之路!

2015-02-11
作者| 阿里文娱高级专家 随方,阿里文娱开发专家 轩成责编 | 屠敏头图 | CSDN 下载自视觉中国背景在阿里的业务中,有广泛的算法应...

图的基础概念—《真实世界的算法: 初学者指南》

2015-02-11
这么多问题可用图的术语描绘,又有这么多用来求解图相关问题的算法.其原因是,如我们刚刚发现的,很多事物都是由对象及对象间...

GIF图讲算法之符合要求的子区间有几个?

2015-02-11
题目描述:560和为K的子数组给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数.示例 1 :输入:...

随机推荐

php面试经典问题

2020-08-31
原文出处: Toptal 译文出处:JackPu Q1第一个问题关于弱类型PHP1234567$str1 = 'yabadabadoo';$str2 = 'yaba';if (strpos($str1,$str2))...

腾讯年薪50万的PHP架构师是什么水平?

2020-08-13
里面覆盖了1-8年PHP开发者!每天都会有技术干货、技术动向、职业生涯晋升等一切有关于程序员内容分享,更有海量PHP中级→高...

【高危安全通告】Drupal任意PHP代码执行漏洞

2020-06-27
Drupal是使用PHP语言编写的开源内容管理框架.11月25日Drupal官方发布安全更新,修复了Drupal 远程代码执行漏洞(CVE-2020-...

世纪天成(上海) 聘手游运营专员/PHP开发工程师/网络工程师

2020-06-17
PHP开发工程师岗位职责:1、负责手机游戏渠道接入工作.2、负责手机游戏的数据后台开发工作3、负责后台网站页面的开发工作....

【第21-25题】利用空闲的5-10分钟巩固一下PHP基础知识

2020-05-06
php中函数传递参数的方式有哪些?两者有什么区别? 按值传递和按地址传递(或按引用传递) (1)按值传递: 待传递的变量,与传...

php编译安装扩展redis及swoole

2020-04-07
php中文网最新课程每日17点准时技术干货分享一.安装redis扩展下载redis扩展包以及解压wget https://github.com/edtechd/phpredis/...

PHP使用curl请求实现post方式上传图片文件功能示例

2020-03-16
php代码:/* 使用curl函数 */$url = "https://api.weixin.qq.com/cgi-bin/material/add_material?access_token=ACCESS_TOKEN&type=...

(基础篇)PHP概述,大概了解一下

2020-02-07
PHP几乎支持所有的操作系统平台(如Windows/UNIX/Linux/Macintosh/FreeBSD/ OS2等),并且支持Apache、IIS等多种Web服务器...

阿里云PHP Composer全量镜像正式上线!(附下载地址)

2020-01-15
今天,阿里云正式上线PHP Composer全量镜像,所有PHP开发者都可以通过我们的开发者社区developer.aliyun.com/composer加速...

苹果iOS界面图标调整,加入3D效果

2015-01-03
结合全新的图标来看,其仍旧采用了螺旋桨元素,但外观增加了3D效果,消除了之前图标的简单性.基于以上的信息,接下来将到来...