图的遍历

我们一般说的的图算法是指在图结构上进行迭代计算的计算过程，例如有最短路径算法、最小生成树算法、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