深入解析阿里巴巴图计算的原理、应用及GraphScope架构设计-老王博客

阿里妹导读：随着大数据的爆发，图数据的应用规模不断下降，现有的图估算系统依然存在一定的局限。阿里巴巴拥有全球最大的商品知识图谱，在丰富的图场景和真实应用的驱动下，阿里巴巴达摩院智能估算实验室研制并开源了全球首个一站式超大规模分布式图估算平台GraphScope，并荣获中国科学技术协会“科创中国”平台。本文解读图估算的原理和应用及GraphScope的构架设计。

文末福利：GraphScope开源发布会。

一什么是图估算

图数据对一组对象（顶点）及其关系（边）进行建模，可以直观、自然地表示现实世界中各类实体对象以及它们之间的关系。在大数据场景下，社交网络、交易数据、知识图谱、交通和通讯网路、供应链和货运规划等都是典型的以图建模的反例。图 1 显示了阿里巴巴在电商场景下的图数据，其中有各类类型的顶点（消费者、卖家、物品和设备）和边（表示了订购、查看、评论等关系）。此外，每个顶点还有丰富的属性信息相关联。

图 1：阿里巴巴电商场景图数据示例

实际场景中的这些图数据一般包含数十亿个顶点和数万亿条边。除了规模大之外，这个图的持续更新速率也特别快，每秒可能有近百万的更新。随着近些年来图数据应用规模的不断下降，探索图数据内部关系以及在图数据上的估算遭到了越来越多的关注。根据图估算的不同目标，大致可以分为交互查询、图剖析和基于图的机器学习三类任务。

1 图的交互查询

图 2：左，金融反欺诈示例；右，图学习示例。

在图估算的应用中，业务一般须要以探求的方法来查看图数据，以进行一些问题的及时定位和剖析某个深入的信息，如图 2 （左）中的（简化）图模型可被用于金融反欺诈（信用卡非法套现）检测。通过使用伪造的标识符，“犯罪分子”可以从工行获得短期信用（顶点 4）。他尝试通过店家（顶点3）的帮助，以虚假订购（边 2->3）来兑现货币。一旦从工行（顶点4）收到付款（边 4->3），商家再通过其名下的多个账户将钱（通过边 3->1 和 1->2）退还给“犯罪分子”。这种模式最终产生一个图上的闭环（2->3->1…->2）。真实场景中，图数据在线上的规模可能包含数十亿个顶点（例如，用户）和数千亿至万亿条边（例如，支付交易），并且整个欺诈过程可能涉及到许多实体之间包含各类约束的动态交易链，因此须要复杂的实时交互剖析能够挺好的辨识。

2 图剖析

关于图剖析估算的研究早已持续了数十年，产生了好多图剖析的算法。典型的图剖析算法包括精典图算法（例如，PageRank、最短路径和最大流），社区检查算法（例如，最大团/clique、联通量估算、Louvain 和标签传播），图挖掘算法（例如，频繁集挖掘和图的模式匹配）。由于图剖析算法的多样性和分布式估算的复杂性，分布式图剖析算法常常须要遵守一定的编程模型。当前的编程模型有点中心模型“Think-like-vertex”，基于矩阵的模型和基于子图的模型等。在这种模型下，涌现出各类图剖析系统，如 Apache Giraph、Pregel、PowerGraph、Spark GraphX、GRAPE 等。

3 基于图的机器学习

经典的 Graph Embedding 技术，例如 Node2Vec 和 LINE，已在各类机器学习场景中广泛使用。近年来提出的图神经网路（GNN），更是将图中的结构和属性信息与深度学习中的特点相结合。GNN 可以为图中的任何图结构（例如，顶点，边或整个图）学习低维表征，并且生成的表征可以被许多下游图相关的机器学习任务进行分类、链路预测、聚类等。图学习技术已被证明在许多与图相关的任务上具有令人信服的性能。与传统的机器学习任务不同，图学习任务涉及图和神经网路的相关操作（见图 2 右），图中的每位顶点都使用与图相关的操作来选择其邻居，并将其邻居的特点与神经网路操作进行聚合。

二图估算：下一代人工智能的基石

不仅仅是阿里巴巴，近年来图数据和估算技术仍然是学术界和工业界的热点。特别是，在过去的六年中，图估算系统的性能已提升了 10~100 倍，并且系统仍在显得越来越高效，这促使通过图估算来加速AI和大数据任务成为了可能。实际上，由于图能非常自然地抒发各类复杂类型的数据，并且可以为常见的机器学习模型提供具象。与密集张量相比，图能提供更丰富的语义和更全面的优化功能。此外，图是稀疏高维数据的自然抒发，并且图频域网路（GCN）和图神经网路（GNN）中越来越多的研究证明，图估算是对机器学习的有效补充，在结果的可解释性、深层次推理因果等方面将饰演越来越重要的作用。

图 3：图估算在AI各个领域具有宽广的应用前景

可以预见，图估算将在下一代人工智能的各类应用中发挥重要作用，包括反欺诈，智能货运，城市脑部，生物信息学，公共安全，公共卫生，城市规划，反洗钱，基础设施，推荐系统，金融技术和供应链等领域。

三图估算现况

经过那些年的发展，已有针对各类图估算需求的多种系统和工具。例如在交互查询方面，有图数据库Neo4j、ArangoDB和OrientDB等、也有分布式系统和服务JanusGraph、Amazon Neptune和Azure Cosmos DB等；在图剖析方面，有 Pregel、Apache Giraph、Spark GraphX、PowerGraph 等系统；在图学习上有 DGL、pytorch geometric 等。尽管如此，面对丰富的图数据和多元化的图场景，有效借助图估算提高业务疗效仍然面临着巨大的挑战：

下面我们通过一个具体的示例瞧瞧现有系统的局限性。

1 示例：论文分类预测

数据集 ogbn-mag 是一个来自于谷歌学术的数据集。数据中包含四种类型的点，分别表示论文、作者、机构、研究领域；在这种点之间有表示关系的四种边：分别是作者“撰写”了论文，论文“引用”了另一篇论文，作者“隶属于”某个机构，和论文“属于”某个研究领域。这个数据很自然的可以用图来建模。

一个用户期望在这个图上对 2014-2020 年间发表的“论文”做一个分类任务，期望能按照论文在数据图中的结构属性、自身的主题特点、以及 kcore、三角计数 triangle-counting 等团聚度的评判参数，将其归类并预测文章的主题类别。实际上，这是一个非常常见和有意义的任务，这个预测因为考虑了论文的引用关系和论文的主题，可以帮助研究人员更好的发觉领域内的潜在合作和研究热点。

让我们分解一下这个估算任务：首先我们须要对论文及其相关的点边做一个依照年份的筛选，再须要在这个图上估算 kcore、triangle-counting 等全图估算，最后将这两个参数和图上的原始特点一起，放入一个机器学习框架进行分类训练和预测。我们发觉当前已有的系统并不能挺好的端到端解决这个问题，我们只能通过将多个系统组织成一个 pipeline 的方式运行：

图 4：论文分类预测多系统组成的工作流

这个任务看起来是解决了，实际上这样流水线的方案背后隐藏着许多问题。例如多个系统之间相互独立和割裂，中间数据频繁落盘进行系统间的数据传递；图剖析的程序不是声明性语言，没有固定范式；图的规模影响机器学习框架的效率等等。这些都是我们在现实图估算场景中常碰到的问题，总结一下可以概括为以下三点：

为了解决以上的问题，我们设计并研制了一站式开源图估算系统：GraphScope。

四 GraphScope 是哪些

GraphScope 是阿里巴巴达摩院智能估算实验室研制并开源的一站式图估算平台。依托于阿里海量数据和丰富场景，与达摩院的高水平研究，GraphScope 致力于针对实际生产中图估算的上述挑战，提供一站式高效的解决方案。

GraphScope 提供 Python 客户端，能非常便捷的对接上下游工作流，具有一站式、开发方便、性能极至等特性。它具有高效的跨引擎内存管理，在业界首次支持 Gremlin 分布式编译优化，同时支持算法的手动并行化和支持手动增量化处理动态图更新，提供了企业级场景的极至性能。在阿里巴巴内部和外部的应用中，GraphScope 已经证明在多个关键互联网领域（如风控，电商推荐，广告，网络安全，知识图谱等）实现重要的业务新价值。

GraphScope 集合了达摩院的多项学术研究成果，其中的核心技术曾获得数据库领域顶尖学术会议 SIGMOD2017 最佳论文奖、VLDB2017 最佳演示奖、VLDB2020 最佳论文提名奖、世界人工智能创新竞赛SAIL奖。GraphScope 的交互查询引擎的论文也已被 NSDI 2021 录用，即将发表。还有其它围绕 GraphScope 的十多项研究成果发表在领域顶尖的学术会议或刊物上，如 TODS、SIGMOD、VLDB、KDD 等。

1 架构介绍

图 5：GraphScope 系统构架图

GraphScope 的底层是一个分布式显存数据管理系统 vineyard[1]。vineyard 也是我们开源的一个项目，它提供了高效和丰富的 IO 接口负责与更底层的文件系统交互，它提供了高效和高层次的数据抽象（包括但不限于图，tensor，vector 等），支持管理数据的分区、元数据等，可以为下层应用提供本机零拷贝的数据读取。正是这一点支持了 GraphScope 的一站式能力：在跨引擎之间，图数据按分区的方式存在于 vineyard，由 vineyard 统一管理。

中间是引擎层，分别由交互式查询引擎 GIE，图剖析引擎 GAE，和图学习引擎 GLE 组成，我们将在后续的章节中详尽介绍。

最上层是开发工具和算法库。GraphScope 提供了各种常用的剖析算法，包括连通性计算类、社区发觉类和 PageRank、中心度等数值估算类的算法，后续会不断扩充算法包，在超大规模图上提供与 NetworkX 算法库兼容的剖析能力。此外也提供了丰富的图学习算法包，内置支持 GraphSage、DeepWalk、LINE、Node2Vec 等算法。

2 重解问题：论文分类预测

有了一站式估算平台 GraphScope，我们可以用一种更简单的方法解决上面示例中的问题。

GraphScope 提供 Python客户端，让数据科学家可以在自己熟悉的环境中完成所有图估算相关的工作。打开 Python 后，我们首先须要构建一个 GraphScope 会话。

import graphscopefrom graphscope.dataset.ogbn_mag import load_ogbn_mag
sess = graphscope.sesson()g = load_ogbn_mag(sess, "/testingdata/ogbn_mag/")

在前面的代码中，我们构建了一个 GraphScope 的 session，并载入了图数据。

GraphScope 面向云原生设计，一个 session 的背后对应了一组 k8s 的资源，该session 负责这个会话中所有资源的申请和管理。具体来说，在用户这行代码的背后，session首先会恳求一个前端总入口 Coordinator 的 pod。Coordinator 负责跟 Python 客户端的所有通讯，在完成自身的初始化后，它会拉起一组引擎 pod。这组 pod 中每一个 pod 都有一个 vineyard 实例，共同组成一个分布式显存管理层；同时，每一个 pod 中都有 GIE、GAE、GLE 三个引擎，它们的启停状态由 Coordinator 在后续按需管理。当这组 pod 拉起并与 Coordinator 建立稳定联接、完成健康检测后，Coordinator 会返回状态到客户端，告诉用户，session 已拉起成功，资源就绪可以开始载图或估算了。

interactive = sess.gremlin(g)
# count the number of papers two authors (with id 2 and 4307) have co-authoredpapers = interactive.execute("g.V().has('author', 'id', 2).out('writes').where(__.in('writes').has('id', 4307)).count()").one()

首先我们在图 g 上完善了一个交互式查询对象 interactive。这个对象在引擎 pod 中拉起了一组交互式查询引擎 GIE。接着下边是一个标准的 Gremlin 查询句子，用户想在这个数据中查看两个具体作者的合作论文。这个 Gremlin 语句会发送给 GIE 引擎进行拆解和执行。

GIE 引擎由并行化 Compiler、内存和调度管理、Operator 运行时、自适应的周游策略和分布式 Dataflow 引擎等核心组件组成。在收到交互式查询的句子后，该句子首先会被 Compiler 拆分，编译成多个运行算子。这些算子再以分布式数据流的模型被驱动和执行，在这个过程中，每一个持有分区数据的估算节点都跑一份该数据流的拷贝，并行处理本分区的数据，并在过程中按需进行数据交换，从而并行化的执行 Gremlin 查询。

Gremlin 复杂的句型下，游历策略至关重要并影响着查询的并行度，它的选择直接影响着资源的占用和查询的性能。只靠简单的 BFS 或是 DFS 在现实中并不能满足需求。最优的周游策略常常须要依照具体的数据和查询动态调整和选择。GIE 引擎提供了自适应的周游策略配置，根据查询数据、拆解的 Op 和 Cost 模型选择周游策略，以达到算子执行的高效性。

# extract a subgraph of publication within a time rangesub_graph = interactive.subgraph("g.V().has('year', inside(2014, 2020)).outE('cites')")
# project the projected graph to simple graph.simple_g = sub_graph.project_to_simple(v_label="paper", e_label="cites")
ret1 = graphscope.k_core(simple_g, k=5)ret2 = graphscope.triangles(simple_g)
# add the results as new columns to the citation graphsub_graph = sub_graph.add_column(ret1, {"kcore": "r"})sub_graph = sub_graph.add_column(ret2, {"tc": "r"})

在通过一系列单点查看的交互式查询后，用户通过以上句子开始做图剖析任务。

首先它通过一个 subgraph 的操作子从原图中按照筛选条件抽取了一个子图。这个操作子的背后，是交互式引擎 GIE 执行了一个查询，再将结果图写入了 vineyard。

然后用户在这个新图上抽取了 label 为论文的点和她们之间关系为引用（cites）的边，产出了一张同构图，并在里面调用了 GAE 的外置算法 k-core 和三角计数 triangles 在全图做了分析型估算。产出结果后，这两个结果被作为点上的属性加回了原图。这里，借助于 vineyard 元数据管理和高层数据具象，新的 sub_graph 是通过原图上新增一列的变换来生成的，不需要重建整张图的全部数据。

GAE 引擎核心承继了曾获得 SIGMOD2017 最佳论文奖的 GRAPE 系统[2]。它由高性能运行时、自动并行化组件、多语言支持的 SDK 等组件组成。上面的事例用到了 GAE 自带的算法，此外，GAE 也支持用户非常简单的编撰自己的算法并在其上即插即用。用户以基于子图编程的 PIE 模型编撰算法，或者重用已有图算法，而不用考虑分布式细节，由 GAE 来做手动并行化，大幅减少了分布式图估算对用户的高门槛。目前，GAE 支持用户通过C++、Python（后续将支持 Java）等多语言编撰自己的算法逻辑，即插即用在分布式环境。GAE 的高性能运行时基于 MPI，对通信、数据排布，硬件特点做了非常细致的优化，以达到极至性能。

# define the features for learningpaper_features = []for i in range(128):    paper_features.append("feat_" + str(i))
paper_features.append("kcore")paper_features.append("tc")
# launch a learning engine.lg = sess.learning(sub_graph, nodes=[("paper", paper_features)],                  edges=[("paper", "cites", "paper")],                  gen_labels=[                      ("train", "paper", 100, (1, 75)),                      ("val", "paper", 100, (75, 85)),                      ("test", "paper", 100, (85, 100))                  ])

接下来我们开始用图学习引擎为论文分类。首先我们配置将数据中论文类节点的 128 维特点以及我们在上一步中估算出的 kcore 和 triangles 两个属性共同作为训练特点。然后我们从 session 中拉起图学习引擎 GIE。在拉起 GIE中图 lg 时，我们配置了图数据，特征属性，指定了哪一类的边，以及将点集界定为了训练集、验证集和测试集。

from graphscope.learning.examples import GCNfrom graphscope.learning.graphlearn.python.model.tf.trainer import LocalTFTrainerfrom graphscope.learning.graphlearn.python.model.tf.optimizer import get_tf_optimizer
# supervised GCN.
def train_and_test(config, graph):    def model_fn():        return GCN(graph, config["class_num"], ...)
    trainer = LocalTFTrainer(model_fn,                             epoch=config["epoch"]...)    trainer.train_and_evaluate()
config = {...}
train_and_test(config, lg)

然后我们通过前面的代码选用模型以及做一些训练相关的参数配置就可以非常方便的用 GLE 开始做图分类任务。

GLE 引擎包含 Graph 与 Tensor 两部份，分别由各类 Operator 构成。Graph 部分涉及图数据与深度学习的对接，如按 Batch 迭代、采样和负取样等，支持同布光和异构图。Tensor 部分则由各种深度学习算子构成。在估算模块中，图学习任务被拆解成一个个算子，算子再被运行时分布式的执行。为了进一步优化取样性能，GLE 将缓存远程邻居、经常访问的点、属性索引等，以推动每位分区中顶点及其属性的查找。GLE 采用支持异构硬件的异步执行引擎，这使 GLE 可以有效地重叠大量并发操作，例如 I/O、采样和张量估算。GLE 将异构估算硬件具象为资源池（例如 CPU 线程池和 GPU 流池），并协作调度细细度的并发任务。

五性能

GraphScope 不仅在易用性上一站式的解决了图估算问题，在性能上也达到极至，满足了企业级需求。我们使用 LDBC Benchmark 对 GraphScope 的性能进行了评估和对比测试。

如图 6 所示，在交互式查询测试 LDBC SNB Benchmark上，单节点布署的 GraphScope 与开源系统 JanusGraph 相比，多数查询快一个数量级以上；在分布式布署下，GraphScope 的交互式查询基本能达到线性加速的扩展性。

图 6：GraphScope 交互式查询性能

在图剖析测试 LDBC GraphAnalytics Benchmark 上，GraphScope 与 PowerGraph 以及其他最新系统比较，几乎在所有算法和数据集的组合中稳居领先水平。在个别算法和数据集上，跟其他平台比较最低也有五倍的性能优势。局部数据见右图。

图 7：GraphScope 图剖析性能

关于实验的设定、重现和完整的性能比较可以参见交互式查询性能[3]和图剖析性能[4]。

六拥抱开源

GraphScope 的蓝皮书、代码已然在 github.com/alibaba/graphscope 开源[5]，项目遵循 Apache License 2.0。欢迎你们 star、试用，参与到图估算中来。也欢迎你们贡献代码，一起构建业界最好的图估算系统。我们的目标是持续更新该项目，不断提高功能的完整性和系统的稳定性。也欢迎你们关注网站 graphscope.io 来跟进项目的最新状态。