图的遍历

我们一般说的的图算法是指在图结构上进行迭代计算的计算过程,例如有最短路径算法、最小生成树算法、PageRank算法等。 这些算法往往用于解决图上的特定一类问题。例如最短路径算法主要用于寻找两个节点之间的最短路径,PageRank算法则可以给节点重要性排序。

然而,还有一类被广泛使用的’图算法’,它们也通过迭代计算处理,且在实际应用中有着广泛的应用,如金融风险管理、社交网络分析等。

它们就是图遍历,又被称之为Traversal。图Traversal解决遍历图中节点的问题,通过可控的顺序访问图中节点和边,以便对图进行处理或收集信息。

一般的图遍历算法可以分为两种主要类型:深度优先搜索(DFS)和广度优先搜索(BFS)。手工实现算法只有既定的走图遍历模式,很难解决特定的图查询问题。

举例来说,在这个简单示例图中,如果要查找所有的’人创建软件’的模式,无论DFS还是BFS都需要实现复杂的计算逻辑,无法直观取得结果。

image

因此,基于图查询中的多元化走图需要,图查询语言自然产生。人们希望使用诸如 (:person)-[:created]->(:software) 的描述来达成需求。

图查询语言GQL

主流的图查询语言有Gremlin和GQL等,其中Gremlin是直接命令式语言,每一个调用都明确地声明了下一步走图的方向。对于命令语言,查询本身就是执行计划,计算机容易理解,但人类学习成本较高,理解困难。

GQL则是声明式语言,简单直观,例如’(:person)-[:created]->(:software)’就表示了我们要查找人创建软件的模式。’Return person.name, software.name;’就可以立即获得作者和软件的名称,大大降低了人理解语言的成本,学习成本接近于零。

然而声明式语言的缺点是描述不直接反应计算机执行的过程,因此需要执行平台将其’翻译’为计算机可以理解的执行计划来处理。

分布式图遍历执行计划

图数据的规模往往十分庞大,例如Github交互的图规模可以到达数百TB规模,金融交易数据的规模可以达到万亿规模。如此复杂的图无法通过单机完成遍历计算。

因此分布式图计算引擎需要的是可以分布式执行的计划,这对执行计划的效率、可扩展性、负载均衡性提出了极高要求。

我们来看几个常见GQL语句的执行计划,一探究竟。这里以蚂蚁集团开源的图计算系统GeaFlow(品牌名为TuGraph-Analytics)为例,感兴趣的同学文末有开源地址。

走图

以示例图为例,我们要查看人与人之间的好友关系时,可以使用如下GQL描述。

MATCH (a:person)-[e:knows]-(b:person where b.id != 1)
RETURN a.id as a_id, e.weight as weight, b.id as b_id;

该描述非常直观,表示了查询两个人a, b之间类型为knows的边,要求b的id不能为1,返回三个结果字段作为结果表。

image

由于查询并不复杂,其产生的执行计划也不复杂,只有6个步骤。

StepSource表示读取图,数字表示步骤的标识ID。MatchVertex步骤表示匹配对应类型的点,例如点a被声明为person类型,则必须把其他类型的点过滤掉。

MatchEdge步骤表示匹配对应类型的边,BOTH表示边的方向不限,因为好友关系是一种相互的关系。

StepFilter步骤对应了GQL查询中的b.id != 1条件,类似SQL语言的WHERE语句,会被翻译成一个特定步骤。StepEnd步骤表示执行计划结束。

关注细节的同学可能发现了,在MatchEdge(e)和MatchVertex(b)之间被标记为不能串联。

这实际对应了走图的Shuffle过程,匹配点和边都可以在一个点原地完成,这在物理上对应了一台机器。如果我们从出边走到其对端点,则对端点可能并不存储在这台机器上,因此会产生数据Shuffle过程,相当于DFS/BFS算法中的深度+1,在执行计划上反映为两个单步不可串联。

聚合

简单的走图过程几乎可以被BFS/DFS算法的实现所替代,例如上面走图的简单例子,可以转化为2轮迭代的遍历完成。

但实际上,随着图研发的深入,走图需求会越来越复杂,相应地GQL查询会越来越长,执行计划也会变得复杂。一旦执行计划复杂到一定程度,人工实现就变得不现实了。

来看这个点上聚合的例子,当我们从点a走到点b后,发起一个聚合子查询,该查询过滤了b点创建软件的数量,要求该数量为0。待子查询返回后,根据其结果,我们可以按照条件过滤路径,然后输出结果所需的a, b对。

MATCH (a:person where a.id = 1)-[e:knows]->(b:person)
WHERE COUNT((b)-[:created]->(c:software) => c) = 0
RETURN a.id as a_id, b.id as b_id;

该查询产生的执行计划如图。这个执行计划包含了一个嵌套关系,在步骤14进入子查询1。子查询1在步骤13返回,根据返回结果我们才能继续执行步骤15。

image

多么的复杂!我相信没有人愿意手工实现这个图算法的。

细心的同学不难发现,COUNT()算子被翻译为点上聚合步骤,且分为了局部聚合(步骤10)和全局聚合(步骤12)。这是分布式计算的考虑,如果在每个点上,把本地的结果计数,提前产生COUNT值的中间结果,再发送到全局加和,就能够降低通信和计算的开销。

循环

好了!我们已经学会了图计算执行计划的思路,让我们实现更多的查询吧。

这个是社交分析的一个例子,来自LDBC测试集的BI03测试。

MATCH (forum:Forum)-[:hasModerator]->(person:Person)
-[:isLocatedIn]-(:City)
-[:isPartOf]->(:Country where name = 'Belarus')
, (forum:Forum)-[:containerOf]->(:Post)
<-[:replyOf]-{0,}(msg:Post|Comment)
-[:hasTag]->(tag)
, (:TagClass where name = 'Comedian')<-[:hasType]-(tag)
RETURN forum.id as forumId, forum.title, forum.creationDate,
person.id as personId, Count(DISTINCT msg.id) as messageCount
GROUP BY forumId, title, creationDate, personId
ORDER BY messageCount DESC, forumId LIMIT 20
;

在该查询中我们处理了一个循环’<-[:replyOf]-{0,}’,从而递归地获取博文post的所有回复。这对应着执行计划中的步骤15的LoopUtil算子。

image

全局标记

走图过程中,通过LET语句,可以将状态暂存在点上,以便在后续使用。例如以下查询,来自LDBC BI08测试,该测试中我们先计算每个人的分数,在Person类型点上进行标记,以便在走图到firend时取值使用。

MATCH (person:Person)
LET person.hasInterest = COUNT((person:Person)-[:hasInterest]->(tag where id = 1020002) => tag.id)
LET person.messageScore = COUNT((person:Person)<-[:hasCreator]-(message:Post|Comment)
                                -[:hasTag]->(tag where id = 1020002) => tag.id)
LET GLOBAL person.score = person.messageScore + IF(person.hasInterest > 0, 100, 0)
MATCH (person:Person)-[:knows]-{0,1}(friend:Person)
RETURN person.id as personId, person.score as personCentralityScore,
SUM(IF(friend.id = person.id, CAST(0 as BIGINT), CAST(friend.score as BIGINT))) as friendScore
GROUP BY personId, personCentralityScore
ORDER BY personCentralityScore + friendScore DESC, personId LIMIT 100
;

这在执行计划中体现为StepMap步骤,三个StepMap步骤分别完成三个LET语句的功能。可以数一数,这个执行计划总共需要多少轮迭代呢?

image

总结

本文介绍了GeaFlow图计算引擎如何使用GQL图查询语言进行走图查询,并介绍了几类查询语句对应生成的图计算执行计划。

GeaFlow(品牌名TuGraph-Analytics) 已正式开源,欢迎大家关注!!!

欢迎给我们 Star 哦!

Welcome to give us a Star!

GitHub👉https://github.com/TuGraph-family/tugraph-analytics

微信群

image

请点击项目链接下方微信二维码添加微信用户群:https://github.com/TuGraph-family/tugraph-analytics