GraphScope
图计算之旅

背景

互联网环境下指数级增长的数据

在约十年前互联网高速发展的时代,随着业务的快速扩展,数据量也在迅速增长。许多数据可以很自然地建模为图,众多业务开始有了图计算的需求,例如:

  • 电子商务交易
  • 路线导航和 POI 推荐
  • 视频创作平台上的评分/评论等

早期方案

面向特定任务的图计算系统

2013 ~ 2020

为了图数据的洞察

图遍历 (Graph Traversal)

图遍历(Graph Traversal)是在线和交互式图查询应用中的关键原语,是一种从图中的一个或者若干顶点出发,按照一定的规则沿着边遍历图中其他顶点的操作,常见的应用场景包括:

图遍历的查询语言

Gremlin

Gremlin 是图遍历中最常用的查询语言,允许对各种图操作进行高层次和声明性的编程。

示例

环检测:在图中查找从一个顶点出发最后又回到这个顶点的路径,从而形成一个环。

g.V().has('name','tom').as('a').repeat(out().simplePath())
 .times(LENGTH).where(out().as('a')).path()

MaxGraphGAIA,
具有高可扩展性的 Gremlin 查询系统

MaxGraph 的架构。其中,GAIA 是对 MaxGraph 的编译和执行优化的组件。

示例

Gremlin 查询的编译

如环检测示例所示,一个 Gremlin 查询可以是迭代和嵌套操作的任意组合。

g.V().has('firstname','Tom').as('a')
  .repeat(out().simplePath()).times(k)
  .where(out().eq('a')).path()

Gremlin 查询被编译成数据流(Dataflow)执行计划,一些算子被分配到某个上下文中进行并行处理。

基于全图计算的
图分析 (Graph Analytics)

示例

实体分析: 识别和链接在不同数据集中的同一实体。这并非易事,挑战包括:

  • 迭代式的密集计算;
  • 大规模和异构的数据,并且数据在动态变化(数百个数据源中拥有数十亿条记录的 PB 级数据,每日更新 TB 级数据);
  • 两个实体之间可能存在着多种连接关系;
  • 噪声数据,不完整数据。

以前的解决方案

点中心的编程模型的局限性

Pregel 和 GAS 是“像顶点一样思考”编程模型的代表。

我们在阿里巴巴曾经致力于一个采用以顶点中心的编程模型的图系统 ODPSGraph,并行化地执行实体解析算法。然而,多年来随着业务的增长也显示出该系统的一些局限性。

  • 编程难度大,有时需要完全重新设计算法。
  • 不断在性能与算法的准确性之间做取舍。 对于许多算法,在以顶点中心模型中高效并行化的执行往往意味着失去精度或质量。
  • 耗时且成本巨大。 通常需要几名资深工程师花费数月的努力才能将算法上线。
  • 性能不佳。

是否有以顶点中心的编程模型的替代方案?

是的,有!

PIE 编程模型和 GRAPE 系统

我们在 SIGMOD'2017 上提出了 PIE 和 GRAPE,并在 Github 开源。
https://github.com/alibaba/libgrape-lite

给定一个查询 Q 和一个图 G,要计算 Q(G),用户只需提供 3 个函数。

  • PEval: 一个用于 Q 的(顺序的)基于当前子图的部分计算算法;
  • IncEval: 一个用于 Q 的(顺序的)增量算法;
  • Assemble: 一个通常只需合并部分结果的函数。

SIGMOD'2017

最佳论文奖(Best Paper Award)

VLDB'2017

最佳演示奖(Best Demo Award)

SIGMOD'2018

研究亮点(Research Highlight)

2018 年

图神经网络 GNN 崭露头角

示例

基于 GNN 的推荐

Graph-Learn,高性能的分布式 GNN 框架

在 VLDB'2019 上提出,并在
https://github.com/alibaba/graph-learn
开源。它已经成功应用于阿里巴巴内外的许多场景。

以及一些其他在图模式匹配、图挖掘的工作...

在图模式匹配、图挖掘及其应用等方面,我们也做了一系列的工作:

  • [VLDB'2018] Real-time Constrained Cycle Detection in Large Dynamic Graphs.
  • [VLDB'2020] Maximum Biclique Search at Billion Scale.
  • ...

VLDB'2020

Best Paper (Runner-up)

然而,一个个图系统变成了孤岛

整合为一站式系统

GraphScope 的诞生和发展

2018 ~ 2024

现实世界的图应用通常涉及多种类型的图计算

示例

一个简化的电商平台欺诈检测工作流:

  • 使用 SQL 从原始数据构建属性图;
  • 使用 Gremlin 提取一个子图;
  • 使用标签传播算法识别欺诈实体;
  • 图采样按权重进行 k-hop 采样;
  • 使用 TensorFlow 训练一个 GNN 模型。

GraphScope:超大规模的一站式图计算系统

我们在 VLDB'2021 上提出了 GraphScope,并在 Github 开源。
https://github.com/alibaba/graphscope

  • 简单而统一的编程接口;
  • 分布式数据流运行时,使每个图算子能在一个精心设计的框架中进行单独优化;
  • 分布式内存数据管理框架,自动管理中间数据的表示、转换和移动;
  • 拥抱 Python 生态,使我们能够将 GraphScope 与其他数据处理系统无缝结合;

为什么选择 Python?

交互式计算,所见即所得
  • Jupyter Notebook
  • 分析、建模、提取、可视化……
丰富的生态系统,端到端一站式的解决方案
处理各种数据和任务的能力,例如:
  • Json、文本、Tensor、SQL、图像、视频…
  • 科学/图计算、机器学习…
高层次的数据和操作抽象
  • Tensor、DataFrame、图、标量、Objects …
  • 在高层次上定义的算子和操作

易用性:兼容 NetworkX

pip install graphscope

与 NetworkX 兼容的图操作算子和算法 API

示例

如何与其他 PyData 系统互操作?

Vineyard:管理内存不可变数据

我们在 SIGMOD'2023 上提出了 Vineyard,并在
https://github.com/v6d-io/v6d 开源,现在 Vineyard 也是一个 CNCF 沙盒(Sandbox)项目。

为什么需要 Vineyard?

  • 许多大数据系统支持在不可变内存数据上工作,但是,
  • 适配 I/O 接口,实现数据分区/分块策略、容错机制、数据访问 RPC、扩容/缩容需要付出巨大的努力。
  • 尽管 I/O 成本通常很高,系统之间共享中间结果依赖于外部文件系统。
  • 没有高效的方法将不可变数据与外部可变数据源动态同步

使用 Vineyard 可以重新定义跨系统数据共享

在 PyData 生态系统中共享数据

Vineyard 提供:

  • 开箱即用的高级抽象(例如图上的边/顶点迭代器,而不是键/值查找)和用于高级开发人员定制特定需求的中低级 API。
  • 通过共享内存以零拷贝的方式进行本地数据共享。
  • 无感的(或与访问本地数据非常相似的)远程数据访问,支持广泛的数据源/格式和数据分区策略。
  • 与可变数据源的(快速)同步。
  • 容错。
  • ...

这些够了吗?已经解决图计算所有问题了吗?

持续迭代

GraphScope Flex
模块化的图计算

2023 ~ 现在

GraphScope 视角下的缺憾

一站式太过理想
“One-Size-Fits-All”的方法是不够的

示例

这张图展示了现实世界中的图计算任务,它有如下特点:

  • 各种业务场景
  • 多样的图工作负载
  • 许多不同格式的图

多样性来自于

1. 各种图模型和组织方式

即使是同一数据集,也可以根据其特定需求以不同的方式建模。

引自 SIGMOD'2024 Panel: The Future of Graph Analytics

2. 多样的图计算工作负载

和编程接口

图查询

  • Cypher
  • Gremlin
  • ISO/GQL

图分析

  • 以顶点为中心:Pregel, Gather-Apply-Scatter(GAS)…
  • 以子图为中心:Pregel++, Blogel, PIE…
  • 其他 DSL:FLASH, GraphIt…

图学习

  • 主要使用 Python
  • PyG, DGL, …

3. 性能的考虑

  • 追求系统的高吞吐还是单个查询的低延迟?
  • 数据存在于内存还是外存?
  • 追求系统的极致性能还是系统的整体资源利用?
  • 是否需要支持高可用?

多样化的图计算促使 GraphScope 演进

GraphScope Flex,模块化的图计算系统

  • 采用类似 LEGO 的模块化设计;
  • 由多个组件组成,每个组件都像一个 LEGO 积木;
  • 一个命令行工具 flexbuild,用于选择组件并构建部署个性化的系统。
GraphScope Flex 的架构

如何处理图存储的多样性?

理解图存储的复杂性

图存储是多样的,计算引擎访问数据的需求也不同。

图存储的多样化功能需求。

GRIN:统一的图访问接口

https://github.com/graphscope/GRIN 上开源

GRIN 是 GraphScope Flex 提出的标准图访问接口,其目标是将不同计算引擎和存储引擎之间的集成从 M * N 简化为 M + N。

GRIN 给计算引擎和存储对接带来的改变。

支持 GRIN 的一种存储后端

GraphAr:一个用于存档和交换图数据的开源文件格式

作为 Apache 孵化项目开源
https://github.com/apache/GraphAr

GraphAr("Graph Archive" 的缩写)是一个旨在让各种应用程序和系统能够更加方便和高效地构建、访问和共享图数据的项目。

GraphAr 给图数据共享带来的改变。

如何处理图查询?

GraphScope Flex 中的图查询组件

  • 前端同时支持GremlinCypher
  • 提供统一的中间表示(IR)抽象,解析 Gremlin/Cypher 到统一的中间表示;
  • 基于 IR 的查询优化器,会根据任务目标的不同,分别生成以下两个引擎的物理执行计划:
  • Gaia,使用数据流模型,用于类似 OLAP 的任务;
  • Hiactor,使用 Actor 模型,用于类似 OLTP 的任务。
示例

实际应用:实时欺诈检测

问题:通过检查每个订单与已知欺诈行为的关联关系,识别电子商务中的可疑交易。

基于 Cypher 的欺诈检测解决方案。

该问题可以通过部署带有这些模块的 GraphScope Flex 来解决。

性能如何?

在 LDBC SNB 基准测试中取得了 No.1 的成绩

如何处理图分析任务?

GraphScope Flex 中的图分析组件

  • 支持多种接口
    • Python,兼容 NetworkX 的 API
    • Java SDK,兼容 Pregel(Giraph)/GraphX 的 API
    • C++ SDK,GRAPE API
  • 100+ 内置算法,开箱即用
    • PageRank,顶点重要性分析…
    • 可达性和最短路径…
    • 社区检测,LPA,Louvain…
  • 其核心是 GRAPE 引擎
    • 支持自动并行化的分布式图计算引擎
    • 集成的 Ingress 提供增量图算法的支持
    • 集成的 FLASH 使得用户更加方便地编写复杂图算法
    • 支持 GPU 加速
示例

实际应用:股权分析

问题:识别公司的实控人,即拥有超过 51% 股份的自然人。

自然人 C 通过公司 2(0.8*0.6 = 0.48)和公司 3(0.8*0.3*0.7 = 0.168)拥有公司 1 超过 51% 的股份。

通过 GraphScope Flex 图分析组件,使用基于标签传播的图分析算法来解决该问题。

想要了解更多细节?

GraphScope Flex
技术预览版现已推出!

https://github.com/alibaba/graphscope

未来工作

  • 增强核心能力
    • 支持 GQL
    • 新的存储后端
    • GraphAr 与数据湖集成
    • 图上的 HTAP 处理
    • 在实际场景中的应用
    • ...
  • 与其他系统的互操作性
    • 专门用于图的 ETL,使来自同一数据集的不同图模型的应用集成更加流畅。
    • 在图任务与类 SQL 操作相结合的场景中,跨多个引擎的统一编译器能显著增强工作流的互操作性,并扩展图计算的范围。
    • ...

我们的最终目标

人人可用的图计算!

欢迎加入我们!

参考文献

  1. GraphScope Flex: LEGO-like Graph Computing Stack, SIGMOD2024, Tao He, Shuxian Hu, Longbin Lai, Dongze Li, Neng Li, Xue Li, Lexiao Liu, Xiaojian Luo, Binqing Lyu, Ke Meng, Sijie Shen, Li Su, Lei Wang, Jingbo Xu, Wenyuan Yu, Weibin Zeng, Lei Zhang, Siyuan Zhang, Jingren Zhou, Xiaoli Zhou, Diwen Zhu.
  2. Dynamic Graph Sampling Service for Real-time GNN Inference at Scale, EuroSys 2023. Jie Sun, Li Su, Wenting Shen, Zichao Zhang, Zuocheng Shi, Jingbo Xu, Yong Li, Wenyuan Yu, Zeke Wang, Fei Wu, Jingren Zhou.
  3. Bridging the Gap between Relational OLTP and Graph-based OLAP, USENIX ATC 2023. Sijie Shen, Zihang Yao, Lin Shi, Lei Wang, Longbin Lai, Qian Tao, Li Su, Rong Chen, Wenyuan Yu, Haibo Chen, Binyu Zang, Jingren Zhou.
  4. GLogS: Interactive Graph Pattern Matching Query At Large Scale, USENIX ATC 2023. Longbin Lai, Yufan Yang, Zhibin Wang, Yuxuan Liu, Haotian Ma, Sijie Shen, Bingqing Lyu, Xiaoli Zhou, Wenyuan Yu, Zhengping Qian, Chen Tian, Sheng Zhong, Yeh-Ching Chung, Jingren Zhou.
  5. Legion: Automatically Pushing the Envelope of Multi-GPU System for Billion-Scale GNN Training, USENIX ATC 2023. Jie Sun, Li Su, Zuocheng Shi, Wenting Shen, Zeke Wang, Lei Wang, Jie Zhang, Wenyuan Yu, Yong Li, Jingren Zhou, Fei Wu.
  6. Vineyard: Optimizing Data Sharing in Data-Intensive Analytics, SIGMOD 2023. Wenyuan Yu, Tao He, Lei Wang, Ke Meng, Ye Cao, Diwen Zhu, Sanhong Li, Jingren Zhou.
  7. Efficient Multi-GPU Graph Processing with Remote Work Stealing, ICDE 2023. Ke Meng, Liang Geng, Xue Li, Qian Tao, Wenyuan Yu, Jingren Zhou.
  8. FLASH: A Framework for Programming Distributed Graph Processing Algorithms, ICDE 2023. Xue Li, Ke Meng, Lu Qin, Longbin Lai, Wenyuan Yu, Zhengping Qian, Xuemin Lin, Jingren Zhou.
  9. GNNLab: A Factored System for Sample-based GNN Training over GPUs, EuroSys 2022. Jianbang Yang, Dahai Tang, Xiaoniu Song, Lei Wang, Qiang Yin, Rong Chen, Wenyuan Yu, and Jingren Zhou.
  10. GraphScope: A Unified Engine For Big Graph Processing, VLDB 2021. Wenfei Fan, Tao He, Longbin Lai, Xue Li, Yong Li, Zhao Li, Zhengping Qian, Chao Tian, Lei Wang, Jingbo Xu, Youyang Yao, Qiang Yin, Wenyuan Yu, Jingren Zhou, Diwen Zhu, and Rong Zhu.
  11. GraphScope: A One-Stop Large Graph Processing System. VLDB, demo, 2021. Jingbo Xu, Zhanning Bai, Wenfei Fan, Longbin Lai, Xue Li, Zhao Li, Zhengping Qian, Lei Wang, Yanyan Wang, Wenyuan Yu, and Jingren Zhou.
  12. Automating Incremental Graph Processing with Flexible Memoization. VLDB 2021. Shufeng Gong, Chao Tian, Qiang Yin, Wenyuan Yu, Yanfeng Zhang, Liang Geng, Song Yu, Ge Yu, and Jingren Zhou.
  13. GAIA: A System for Interactive Analysis on Distributed Graphs Using a High-Level Language, NSDI 2021. Zhengping Qian, Chenqiang Min, Longbin Lai, Yong Fang, Gaofeng Li, Youyang Yao, Bingqing Lyu, Xiaoli Zhou, Zhimin Chen, and Jingren Zhou.
  14. FlexGraph: A Flexible and Efficient Distributed Framework for GNN Training. EuroSys 2021. Lei Wang, Qiang Yin, Chao Tian, Jianbang Yang, Rong Chen, Wenyuan Yu, Zihang Yao, and Jingren Zhou.
  15. Maximum Biclique Search at Billion Scale, VLDB 2020. Best Paper Runner-up Bingqing Lyu, Lu Qin, Xuemin Lin, Ying Zhang, Zhengping Qian, and Jingren Zhou.
  16. Adaptive Asynchronous Parallelization of Graph Algorithms. TODS. 45(2): 6:1-6:45, 2020. Wenfei Fan, Ping Lu, Wenyuan Yu, Jingbo Xu, Qiang Yin, Xiaojian Luo, Jingren Zhou, and Ruochun Jin.
  17. Parallelizing Sequential Graph Computations TODS 43(4): 18:1-18:39, 2018. Wenfei Fan, Wenyuan Yu, Jingbo Xu, Jingren Zhou, Xiaojian Luo, Qiang Yin, Ping Lu, Yang Cao and Ruiqi Xu
  18. Real-time Constrained Cycle Detection in Large Dynamic Graphs. VLDB, 2018. Xiafei Qiu, Wubin Cen, Zhengping Qian, You Peng, Ying Zhang, Xuemin Lin, and Jingren Zhou.
  19. GRAPE: Parallelizing Sequential Graph Computations. VLDB, demo, 2017. Wenfei Fan, Jingbo Xu , Yinghui Wu, Wenyuan Yu, Jiaxin Jiang

Copyrights

  1. Some images are designed by Freepik (https://freepik.com).
  2. Some fonts and icons from FontAwesome (https://fontawesome.com).
  3. Other copyrights are reserved in GraphScope Team © 2020-2025.