Press "Enter" to skip to content

图计算 101:图计算的类型、语言与系统

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

本文是图计算 101 系列的第二篇文章,将繁杂的图计算任务根据其计算模式的特性进行分类,并对每一类的图计算任务进行简要的介绍。

 

背景

 

现实生活中的很多数据都可以建模成图(Graph)这一抽象的结构。这种高效紧凑的数据形式可以表示出拓扑、属性、时序等丰富的信息,而图计算的目标就是从图结构中挖掘出有价值的知识或规律,例如频繁模式、因果关系等。随着信息时代的到来,数据规模呈爆炸式增长,产生了对大规模的图数据进行高效处理的需求,图计算已经成为了工业界和学术界的热点话题,并因此诞生了一系列的图计算系统及优化研究工作。

 

复杂的业务场景,致使图数据的计算类型也是多种多样的。目前,存在着三种最主要的图计算类型,分别是图查询、图分析和图学习,下面我们就逐一地进行介绍。

 

图查询

 

通常来说,图数据非常庞大,而图数据的交互式查询只关心其中满足条件的比较少量的点和边。如下图所示,这些点和边会形成特定的路径,或者子图模式。例如,从一个地方到另一个地方的最优路线,或者物流的路径信息,都是典型的路径查询场景。子图模式是另一种类型的图查询,它用子图表示某种模式,然后用这个子图在全图中进行匹配查询。

 

路径查询(右)和子图查询(左)

 

路径查询的本质是图的遍历,通常按照如下的步骤进行:首先将图上特定的顶点设为待查点;然后每个待查点通过自己所连接的满足条件的边找到目标端点集合,检查目标端点是否满足查询目标;如果满足则将该目标端点放入结果集,否则将该目标端点设置为新的待查点。一直重复这样的步骤,直到没有待查点。简单来说,就是在图查询的整个过程中,按照用户指定的条件,一步一步在图上游走遍历,并最终获得想要的结果。

 

另一种类型的图查询,即子图查询,其理论基础是子图同构。用户需要给定待查询的子图(点、边以及它们所要满足的条件),然后从数据图上查找所有满足条件的结果,使得:每个结果是数据图上的子图;该子图和查询图是同构的;且该子图所映射的点和边满足查询图上对应点和边的查询条件。简单来说,就是在大图中去寻找用户关心的某种特定结构。

 

图查询最典型的两大主流语言,分别是 Gremlin [1] 和  Cypher [2] 。Gremlin 基于 Groovy,但有许多语言变体,允许开发者以 Java、Python 等编程语言原生编写查询。它既包含命令式也包含声明式的语义,能方便表达图遍历的逻辑,所以被众多图数据库系统采用,例如 JanusGraph、InfiniteGraph、Cosmos DB、DataStax Enterprise(5.0+)、Amazon Neptune 等。另一种图查询语言 Cypher 则采用了基于描述式的模式匹配。因为与 SQL 类似,具有语法简单和灵活性高的特点,因此被 neo4j、RedisGraph、AgensGraph 等系统采用。

 

例如,在包含 person 和 location 类型点的图中,查询与 mike 一起居住的人,用 Gremlin 和 Cypher 编写的查询语句分别如下所示。

 

# Gremlin
g.V().has('name', 'mike').as('a')
.out('lives').in('lives').where(neq('a'))
.values('name')
# Cypher 
MATCH
(src:person{name:"mike"})-[:lives]->()<-[:lives]-(dst:person)
RETURN dst.name

 

对比其他类型的数据处理,图查询具有鲜明的计算特征。海量数据和局部性差的特点,需要系统在分布式任务划分、负载均衡、通信调度等方面进行优化;高计算复杂度和用户的低延迟要求让系统的并发能力变得尤为重要;超点导致的内存膨胀、交互环境内存受限等特点,给系统的内存管理带来了很大的挑战。

 

图分析

 

图查询,一般只访问满足特定条件的少量点或边,并实时返回结果,如从某个点出发按一定条件走两跳,返回满足条件的路径。而图分析则一般包含更复杂的计算,侧重于分析、挖掘全图的整体特征或实体之间的关联信息,例如把全图所有点按一定规则进行聚类。

 

事实上,图论是一个已有几百年研究历史的传统数学分支,因此有关图分析的算法也是不胜枚举。从最短路径、连通分量等经典算法,到社区发现、协同过滤、模式挖掘等人工智能领域的实际问题,图分析被应用在了越来越多的场景中,大规模图分析也成为了一个研究热点。参考 GraphX,常见的图分析算法分类包括:

简单的图分析算法

PageRank
Shortest path
Graph coloring
Connected component

社区发现类的算法
Triangle counting
K-core decomposition
K-Truss
模式匹配类的算法
Graph simulation
(Sub)graph isomorphism
Keyword search
协同推荐类的算法
Alternating least squares (ALS)
Stochastic gradient descent (SGD)
Tensor Factorization
结构预测类的算法
Loopy belief propagation
Max-product linear programs
Gibbs sampling

2010年 Google 公开的 Pregel [3] 系统是首个专门用于分析大规模图数据的分布式系统,它首次提出了以点为中心的编程模型,并催生了后续一系列的学术研究和开源系统。这种编程模型采用局部的、面向点的计算思想,促使用户“像点一样思考”。由于这一模型具有天然的可扩展性和并行性,因而被广泛使用。延续这一模型的系统也从编程接口、任务划分、执行机制等各个角度对其进行优化,如  PowerGraph [4] 的经典编程模型 GAS。另一类系统采取了更加高级的编程模型,如  Giraph++ [5] 率先提出将子图作为计算的基本单元,因而执行效率更高。 GRAPE [6] 提出的 PIE 模型可以将单机图算法自动并行化,在兼具高效性能的同时,大大降低了用户的编程难度。

 

图数据的复杂性,使得图分析系统在设计上有很多需要考虑的难点,比如:如何更有效地利用底层硬件资源,如何划分数据和维护分布式一致性,更高效的执行模式和任务调度策略,更先进的计算模式和编程模型,以及更好的系统容错机制等等。

 

图学习

 

图学习,即基于图的机器学习,旨在将图的结构信息整合到机器学习模型中。随着以深度学习为代表的人工智能技术广泛应用,且图结构具有更强的表达能力,图学习成为了一个热点话题,也在因果关系、可解释性方面带来了突破进展。现在,图学习已经被应用在了搜索推荐、广告、金融风控、智能交通、医疗、城市等各个领域。另一方面,图学习也面临着一些新的技术挑战,例如数据规模庞大、点和边的异构性、多模态的属性特征、结构或属性随时间动态变化等。

 

图学习的传统方法,是表征学习。图表征学习(Graph Embedding),就是将图中的每一个顶点都表示成一个低维向量,并使该向量能够尽可能多的保存图的结构和内容信息。该表示向量可以作为特征用于后续的学习任务,如链接预测、顶点分类等。下图展示了一个经典的例子,其中左边是原始的图结构,右边是表征学习得到的一种映射方案,它把图A中的每个顶点转化成了二维坐标系中的一个点,也就是一个二维向量。原始图中紧密相连的点(即相同颜色的点)在映射得到的坐标空间中,依然距离较近。

 

Graph Embedding示例 (https://dl.acm.org/doi/abs/10.1145/2623330.2623732)

 

对于图表征学习这一问题,已经开展了非常多的研究工作。这些工作针对同构图、异构图、属性图、动态图等不同类型的数据,提出了各式各样的方案,包括经典算法 DeepWalk [7] 、 LINE [8] 、 Node2Vec [9] 等。这些工作的基本做法是基于随机游走生成数据,然后通过训练优化参数,生成概率模型。

 

另一种图学习的重要类型是图神经网络。传统的神经网络只能解决欧式空间的问题,要求数据是完整、整齐、规则的。例如一张照片,每个像素点固定与八个点相邻,因此每个点可以对应一个等长向量,包含了它本身的信息和邻居信息。而图神经网络(GNN),将经典神经网络模型如 Recurrent Neural Networks(RNN) 、Convolutional Neural Networks(CNN)等扩展到了图上。它解决的是非欧式空间的问题,这是因为图结构是不规则的,每个点的邻居个数不一样,导致局部的维度不定长。与图表征学习试图学习出每个点的 embedding 不同,图神经网络的目的其实是学习出聚合函数,所有点通过同一个函数就可以利用局部信息计算出自身的 embedding。即使是图结构发生变化,甚至是完全新的图,也能用原来的函数计算出有意义的结果。有关图神经网络,也已经诞生了一系列经典算法,读者可以阅读 有关文献 [10] 做进一步的了解。

 

总结

 

由于图数据具有依赖性强、局部性差、不规则分布、结构多样等特点,导致传统的数据并行系统难以适用。另外,不同类型的计算特征和计算范式,也给图计算系统的设计带来了多元化的要求。

 

一个理想的图计算系统,应该兼具通用性、高性能和易用性。在通用性上,我们希望它支持图查询、图分析、图学习等多种类型的计算,同时,兼容语言标准与业界生态。在性能方面,可以实现低延时的交互式查询,具备高性能的图分析能力,支持大规模图存储,提供高可扩展性等。在易用性上,应该提供统一的编程模型,高度抽象、简单灵活的语言,并且实现系统部署简单、集群方便管理,提供可视化的界面等等。

 

应对图计算系统面临的种种挑战、满足真实应用场景的需求、提供一站式高效的解决方案,正是 GraphScope 的设计初衷。GraphScope 系统提出了多个重要的创新性技术,同时也在持续快速迭代着,已经证明在多个关键互联网领域 (如风控、电商推荐、广告、网络安全、知识图谱等)实现了重要的业务新价值,并致力于助力越来越多的重要应用场景。

 

参考资料

 

[1]

 

Gremlin: https://tinkerpop.apache.org/docs/current/reference/

 

[2]

 

Cypher: https://dl.acm.org/doi/abs/10.1145/3183713.3190657

 

[3]

 

Pregel: https://dl.acm.org/doi/abs/10.1145/1807167.1807184

 

[4]

 

PowerGraph: https://www.usenix.org/conference/osdi12/technical-sessions/presentation/gonzalez

 

[5]

 

Giraph++: https://dl.acm.org/doi/abs/10.14778/2732232.2732238

 

[6]

 

GRAPE: https://dl.acm.org/doi/abs/10.14778/3137765.3137801

 

[7]

 

DeepWalk: https://dl.acm.org/doi/abs/10.1145/2623330.2623732

 

[8]

 

LINE: https://dl.acm.org/doi/abs/10.1145/2736277.2741093

 

[9]

 

Node2Vec: https://dl.acm.org/doi/abs/10.1145/2939672.2939754

 

[10]

 

有关文献: https://www.sciencedirect.com/science/article/pii/S2666651021000012

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。