GraphScope在图处理领域的探索之旅

背景

阿里巴巴数据的指数级增长

大约十年前,业务呈指数级扩张,数据也随之迅猛增长。 其中许多数据天然适合建模为图结构,因此图计算的需求在多个领域涌现,例如

  • 电商交易
  • 导航路线与兴趣点
  • 视频创作者评分

早期采用

最初的图问题都是孤立处理的。

2013 ~ 2020

获取图数据的洞察

图遍历探索

图遍历——访问图中节点的过程——是许多在线和交互式图应用中的关键基础操作,例如,

事实标准

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查询被编译为数据流计划,部分算子被分配了SCOPE上下文以实现并行处理

图分析,
全图计算

示例

实体解析:识别并关联现实世界中同一实体的不同表示形式。这一任务并非易事,面临的挑战包括:

  • Iterative and intensive computation
  • Large scale and heterogeneous data, dynamic changes (PBs of data with billions of records across hundreds data sources with TBs of update daily)
  • Multi-domain connections/relations between possible entities
  • 噪声和错误,不完整/缺失的数据

之前的解决方案?

顶点中心模型的局限性

Pregel和GAS范式的代表,体现了"像顶点一样思考"的模型。

我们过去使用内部开发的顶点中心图系统ODPSGraph来实现实体解析的并行化。然而,多年来面临的挑战与日俱增。

  • 编程难度高,有时需要完全重新设计算法。
  • 临时性权衡的持续困扰。对于许多算法而言,在顶点中心模型中高效实现并行化往往意味着要牺牲精度或质量。
  • 耗时且成本高昂。通常需要多名资深工程师投入数月时间才能将一个算法上线。
  • 性能不尽如人意。

顶点中心模型的替代方案?

我们的回答是肯定的!

PIE模型与GRAPE系统

我们在SIGMOD'2017上展示了PIE和GRAPE,并将其开源发布于 https://github.com/alibaba/libgrape-lite

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

  • PEval: 用于Q的(顺序)算法,用于部分求值
  • IncEval: 用于Q的(顺序)增量算法
  • Assemble: 通常只需对部分结果进行合并的函数

SIGMOD'2017

最佳论文奖

VLDB'2017

最佳演示奖

SIGMOD'2018

研究亮点

2018年

图神经网络崛起

示例

基于GNN的推荐系统

Graph-Learn, 一个图神经网络框架

在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

最佳论文(亚军)

问题所在:图系统成为孤岛

凝聚我们的力量

GraphScope的诞生

2018 ~ 2024

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

示例

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

  • 使用SQL从原始数据构建属性图;
  • 使用Gremlin提取子图;
  • 通过标签传播算法识别欺诈实体;
  • 基于权重的k跳图采样;
  • 使用TensorFlow训练GNN模型

GraphScope: 面向大规模图处理的一体化引擎

我们在VLDB'2021大会上发布了GraphScope,并开源在
https://github.com/alibaba/graphscope

  • 简单统一的编程接口;
  • 分布式数据流运行时,能在精心设计的统一框架中为每个图操作单独优化
  • 内存数据存储,自动管理中间数据的表示、转换和移动
  • 支持Python,可无缝集成GraphScope与其他数据处理系统

为什么选择Python?

交互式计算,所见即所得
  • Jupyter Notebook
  • 分析、建模、提取、可视化...
丰富的生态系统,端到端一站式服务
Ability to process various data and tasks, e.g.,
  • Json, text, tensor, SQL, image, video…
  • 科学/图计算、机器学习等
高层次的数据与操作抽象
  • Tensor、Dataframe、Graph、Scalar、Objects …
  • 定义在高层级的操作

易用性:兼容NetworkX

pip install graphscope

兼容NetworkX的图操作和算法API

示例

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

Vineyard: 内存中的不可变数据管理

我们在SIGMOD'2023上展示了Vineyard,并在
https://github.com/v6d-io/v6d开源了该项目,Vineyard是CNCF沙箱项目。

为什么我们需要vineyard?

  • many big data systems work with (partitioned) immutable in-memory data, however,
  • it takes huge effort just to implement I/O adaptors, data partition/chunking strategies, fault-tolerance mechanisms, data access RPC, scale in/out.
  • sharing intermediate results between systems relies on external FS, although I/O cost is usually very high.
  • 缺乏高效的方法将不可变数据与外部可变数据源动态同步

使用Vineyard重新审视案例研究

在PyData生态系统中共享数据

Vineyard提供:

  • Out-of-box high-level abstraction (e.g. Edge/Vertex Iterator over graphs instead of k/v lookup) and mid-to low-level APIs for advanced developers to tailor special needs.
  • zero-copy local data access through shared memory
  • Transparent (or very similar to accessing local data) remote data access support wide range of data sources/formats, data partition strategies
  • (fast) sync with mutable data sources
  • Fault-tolerant
  • ...

我们完成了吗?

下一步迭代

GraphScope Flex
GraphScope演进的下一阶段

2023年 ~ 至今

GraphScope 的实际挑战

一刀切的方法并不适用

示例

该图展示了现实世界中图系统的简化视图。它具有以下特点

  • 多样化的业务场景
  • 多样化的图计算工作负载
  • 多种不同格式的图数据

多样性来源于

1. 多样化的图模型与组织结构

即使是同一个数据集,也可以根据具体需求以不同方式进行建模。

引自SIGMOD'2024专题讨论会:图分析的未来

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

与编程接口

用于图查询

  • Cypher
  • Gremlin
  • ISO/GQL

用于图分析

  • 类顶点思维模型:Pregel、Gather-Apply-Scatter(GAS)等
  • 图式思维:Pregel++、Blogel、PIE…
  • 其他领域特定语言:FLASH、GraphIt…

用于图学习

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

3. 性能考量

  • High request throughput? vs. low latency with data-parallel execution?
  • In-memory vs. out-of-core?
  • Efficient processing vs. resources utilization
  • High availability?

图计算领域的多样化需求催生了GraphScope

演进至GraphScope Flex

  • Employs a LEGO-like modularity;
  • Comprises many components, each like a LEGO brick;
  • 一个命令行工具 flexbuild,用于选择组件并构建部署所需的工件。
GraphScope Flex 架构

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

理解图存储抽象的复杂性

图存储可以多种多样。计算引擎访问数据的需求也各不相同。

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

GRIN: 统一图检索接口

开源地址: https://github.com/graphscope/GRIN

GRIN是GraphScope中提出的标准图检索接口。其目标是将不同计算引擎与存储引擎之间的集成复杂度从M*N降低到M+N。

不带/带GRIN的存储系统。

其中一个存储后端支持GRIN

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

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

GraphAr(全称“Graph Archive”)是一个旨在让各类应用和系统(包括内存与外部存储、数据库、图计算系统以及交互式图查询框架)能更便捷高效地构建和访问图数据的项目。

不使用/使用GraphAr时的数据共享。

图查询

在GraphScope Flex中查询堆栈

  • Supports both Gremlin and Cypher in front-ends;
  • Provides a unified Intermediate Representation(IR) Abstraction, parsing Gremlin/Cypher… to unified IR;
  • And IR based Optimizer, and two engines,
  • Gaia, using a dataflow model, for OLAP-like jobs;
  • Hiactor,采用智能体模型,适用于类OLTP任务。
示例

实际应用:实时欺诈检测

问题:通过将每笔订单与已知欺诈行为进行比对,识别电子商务中的可疑交易。

欺诈检测及其Cypher解决方案。

这个问题可以通过部署GraphScope Flex并使用这些组件来解决。

性能

第一名 在LDBC SNB基准测试中

图分析

GraphScope Flex中的分析栈

  • Supports multiple interfaces
    • Python, NetworkX compatible APIs
    • Java SDK, Pregel(Giraph)/GraphX compatible APIs
    • C++ SDK, GRAPE API
  • 100+ Built-in algorithms, out-of-the-box ready to use.
    • PageRank, Centralities…
    • Reachability and shortest paths…
    • 社区检测、LPA、Louvain算法等
  • At its core, is the GRAPE engine.
    • Supports distributed graph computing engine with auto-parallelization
    • Integrated Ingress for auto-incrementalization
    • Integrated FLASH model with great expressive capability
    • 支持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

未来工作

  • Enhancing the core capabilities
    • GQL support
    • New storage backends
    • GraphAr with Data Lakes
    • HTAP processing on graphs
    • Applications in real-life scenarios
    • ...
  • Inter-operations with other systems
    • Graph-specific ETL to streamline the integration of applications across different graph models derived from the same dataset.
    • In scenarios blending graph tasks with SQL-like operations, a unified compiler across multiple engines can significantly enhance work- flow interoperability and expand the scope of graph computations.
    • ...

我们的终极目标

让图计算变得简单易用,人人可用!

欢迎加入我们,携手合作!

参考文献

  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: 并行化顺序图计算。VLDB, 演示, 2017. 作者:Wenfei Fan, Jingbo Xu, Yinghui Wu, Wenyuan Yu, Jiaxin Jiang

版权

  1. 部分图片由Freepik设计 (https://freepik.com).
  2. 部分字体和图标来自FontAwesome (https://fontawesome.com)。
  3. 其他版权归GraphScope团队所有 © 2020-2025。