大规模图计算是互联网基础设施的重要组成部分。社交网络中的好友关系、金融风控中的资金流转链路、供应链中的货品追溯，本质上都是图结构问题。本文从计算范式、主流引擎、流批架构、规模化算法、基准测试到生产部署决策，提供一份系统性的技术综述。

图计算范式

Pregel 与 BSP 模型

2010 年，Google 在 SOSP 上发表了 Pregel 论文，奠定了大规模图计算的编程模型基础。Pregel 采用"以顶点为中心"（vertex-centric）的编程抽象，开发者只需实现单个顶点的计算逻辑，系统负责协调全图。

执行单元是超步（superstep）：所有活跃顶点先并行执行用户定义的 compute() 函数，顶点通过消息向邻居传递结果，消息在超步间缓冲；当前超步内所有顶点计算完毕后进行全局屏障同步，再进入下一超步。

这是 Leslie Lamport 提出的 BSP（Bulk Synchronous Parallel）模型在图计算领域的直接应用。顶点通过调用 voteToHalt() 停止参与后续计算，全图所有顶点停止后算法终止。

BSP 模型的优势是容错实现简单：周期性将全图状态保存到分布式文件系统，节点故障后从最近检查点重放。代价是全局屏障带来的等待开销——在图结构呈幂律分布时，少量高度顶点（Hub 节点）的计算延迟会让所有其他顶点空等。

GAS 分解模型

PowerGraph（OSDI 2012）和 GraphLab 2.0 针对 Pregel 的高度顶点问题提出了 GAS（Gather-Apply-Scatter）分解：

  • Gather：顶点从邻居收集信息，进行聚合运算（如求和）
  • Apply：顶点利用聚合结果更新自身状态
  • Scatter：顶点将新状态散播到邻居，触发邻居的下一轮计算

GAS 的关键创新是顶点切割（vertex-cut）分区策略。传统的边切割（edge-cut）让每个顶点只存在于一个分区，高度顶点的所有边都集中到同一机器，造成计算和通信瓶颈。顶点切割让每条边只存储一次，高度顶点被复制到多个分区并行处理，再通过镜像（mirror）同步状态。对于度数服从幂律分布的真实世界图，顶点切割能显著均衡负载。

推送与拉取自适应

Ligra（EuroSys 2013，MIT）在共享内存环境中率先引入推送/拉取两种图遍历模式的自适应切换：

  • 推送（Push）：活跃顶点主动向邻居发送消息，适合活跃顶点集合稀疏（如 BFS 初始阶段）
  • 拉取（Pull）：顶点主动询问邻居状态，适合活跃集合稠密（如收敛后期）

Gemini（Tsinghua，OSDI 2016）将这一思想移植到分布式环境。Gemini 以 CSR（Compressed Sparse Row）格式存储出向边以支持推送，以 CSC（Compressed Sparse Column）格式存储入向边以支持拉取，在每个超步根据活跃顶点密度动态选择模式。其公开数据显示，在 PageRank、ALS 等典型任务上，性能是 PowerGraph/PowerLyra 的十倍以上，是 Spark 的百倍以上，内存占用仅为 Spark 的十分之一。Gemini 的核心版本作为学术研究原型可获取，但功能完整的商业版本并未完全开源。

边切割与顶点切割的权衡

策略 顶点存储 边存储 适用图类型
边切割 单一分区 跨分区（有重复） 度数均匀的图
顶点切割 镜像复制 单一分区（无重复） 幂律分布、社交图

现实互联网图几乎都呈幂律分布，少数 Hub 节点度数高达数百万，顶点切割是主流选择。

主流计算引擎

Apache Giraph：Hadoop 生态的 Pregel 实现

Apache Giraph 是 Facebook 开源的 Pregel 实现，运行在 Hadoop 集群之上。架构上分为 Master 节点和 Worker 节点：Master 协调超步同步和检查点，Worker 承载顶点计算和消息路由。开发语言为 Java，与 Hadoop 生态集成紧密。

Facebook 曾将 Giraph 用于对包含数千亿条边的好友关系图运行排序算法，验证了其在超大规模数据上的可用性。Giraph 也支持顶点切割（通过 EdgePartitioner）和异步模式，但其在 Hadoop MR 框架之上构建带来的调度开销，使其吞吐量难以和专用图计算引擎媲美。目前 Giraph 社区活跃度有所下降，新项目较少采用。

Spark GraphX：大数据生态的一等公民

GraphX 以"属性图"（Property Graph）为抽象，其中顶点和边都可携带任意类型的用户属性，在底层由两个 RDD 表示：VertexRDD 和 EdgeRDD。

核心 API 是 aggregateMessages，接受三个函数：

1
2
3
4
5
graph.aggregateMessages[Msg](
  sendMsg,     // 在每条边上决定向哪个顶点发送什么消息
  mergeMsg,    // 将到达同一顶点的多条消息合并
  tripletFields // 控制边三元组哪些字段被序列化
)

这实际上是 GAS 模型的 Gather+Scatter 阶段；Apply 阶段通过 joinVertices 实现。GraphX 内置 PageRank、WCC、Triangle Count、LPA、SVD++ 等常用算法，并通过顶点切割分区保证幂律图上的负载均衡。

GraphX 最大的优势是与 Spark SQL、MLlib、Structured Streaming 的无缝集成，一次 ETL 流水线中可以混合结构化数据处理和图算法。代价是 RDD 的序列化和 GC 开销使其在单纯图计算基准上不如 Gemini 或 Plato 等专用引擎。

Flink Gelly 构建于 Flink DataSet（批处理）API 之上，提供三种迭代模型：

  • Vertex-Centric（类 Pregel BSP）
  • Scatter-Gather（消息从发送顶点到接收顶点）
  • GSA（Gather-Sum-Apply，类 PowerGraph GAS）

Gelly 的定位是让 Flink 流批一体生态中的图分析场景有统一编程接口。然而，2025 年 3 月发布的 Flink 2.0.0 正式宣布 DataSet API 进入弃用阶段，Gelly 作为其直接依赖库随之进入软弃用状态。

官方建议是使用 Table API 或 DataStream API 替代批处理逻辑；目前尚无基于 Flink 2.x DataStream API 的官方图库接替 Gelly。新项目在图计算场景中应谨慎评估 Gelly 的长期可维护性，对于需要与 Flink 集成的图计算场景，可考虑 GraphScope 的流图引擎或将图分析工作独立到专用引擎。

Alibaba GraphScope：一站式图计算平台

GraphScope（2021 年 VLDB 论文，持续演进）是阿里巴巴开源的综合图计算平台，在单一系统中整合了图分析、图查询和图学习三条路径：

  • GAE（图分析引擎）：基于 GRAPE 框架（SIGMOD 2017），使用 PEval/IncEval/Assemble 三函数模型实现顺序图算法到并行版本的自动化转换
  • GIE（图交互引擎）：支持 Gremlin 和 Cypher 查询语言，面向交互式图查询场景
  • GLE（图学习引擎）：提供图神经网络（GNN）的分布式训练支持

底层通过 Vineyard 共享内存对象存储实现引擎间的零拷贝数据共享，整体运行在 Kubernetes 上实现弹性扩缩容。2024 年 SIGMOD 发表的 GraphScope Flex 论文将架构进一步模块化，使各引擎可以独立部署。

在 2023 年 LDBC SNB Interactive 基准测试中，GraphScope 刷新了查询吞吐量纪录，超过前一纪录 2.45 倍，峰值 QPS 超过 33,000。需要注意的是，该纪录针对的是交互式查询（OLTP 类型），与 Gemini 在批量图分析（OLAP 类型）基准上的性能数字属于不同维度，不可直接比较。

Tencent Plato：面向工程落地的 C++ 引擎

Plato（腾讯，2019）是腾讯内部 C++ 图计算引擎的开源版本，底层基于 Gemini 的推送/拉取自适应框架，并整合了 KnightKing 随机游走模块（支持 Node2Vec、MetaPath 等图表示学习算法）。

美团技术团队的生产基准测试（已在多个镜像站验证）评估了 Apache Giraph、Spark GraphX 和 Plato 三个框架，最终选择 Plato，核心理由包括：相同任务下计算节点数量仅需 Spark 方案的十分之一左右，内存占用约为 GraphX 的一到两个数量级以下，在亿级规模顶点图上的运算时间也更短。对于需要在有限集群资源下运行图算法的团队，Plato 是值得评估的选项。Gemini 因功能完整版本未完全开源，GraphLab 因已被 Apple 收购转为商业产品，均未进入美团的对比范围。

GeaFlow / TuGraph-Analytics：流图一体化

GeaFlow（蚂蚁集团，Apache Incubating，现更名 TuGraph-Analytics）的核心设计目标是让批量图计算和流式图更新运行在同一引擎上。其独特的 FIFO-GNN 流水线将图的增量更新和图神经网络推理串联：新事务数据进入时，引擎实时更新图结构并触发 GNN 特征刷新，用于检测资金链路中的多跳异常模式（据公开信息，蚂蚁在生产中用于六跳异常资金链的实时检测）。

引擎支持 RocksDB、Redis、Paimon 等可插拔存储后端，声称可扩展至十亿至万亿边规模。2020 年 LDBC SNB 基准测试中，TuGraph（蚂蚁，查询引擎）的吞吐量是当时纪录的 7.6 倍。流批一体化使其适合需要实时更新图并定期运行全量分析的场景，但架构复杂度也相应更高。

Galois 与 Katana Graph：HPC 视角

Galois（UT Austin）从高性能计算角度出发构建图计算框架，专注 NUMA 感知的共享内存调度和分布式扩展，赢得了 2017 年 MIT/IEEE/Amazon Graph Challenge 冠军。其子项目 Pangolin 专攻图模式挖掘（图同构搜索），是 Galois 在数据挖掘领域的延伸。

Katana Graph 是 Galois 的商业化衍生公司，将学术框架包装成企业级产品。Katana 采用基于属性图的存储格式（Katana Graph Format），内置 NUMA 感知调度器，支持 GPU 加速，并提供 Python 接口降低使用门槛。其定位更接近提供高性能图分析能力的商业平台，而非社区驱动的开源项目。

批处理、流处理与增量计算

批量图处理

批量图处理的经典模型是先将图快照加载到内存或分布式存储，完整运行算法后输出结果。Giraph、早期 GraphX、Plato 均属于此类。批处理对图的静态视图有天然的优化空间：可以做全局分区优化、预排序边表、离线调整负载均衡策略。

对于每日或每小时更新一次的图数据（如隔夜结算的金融风控、周期性推荐系统特征更新），批处理模式就足够，维护成本也低。

GridGraph（Tsinghua，ATC 2015）针对单机场景进一步优化了批处理：对超出内存容量的大图采用二级分层分区，将边集划分为多个块，顺序读取以减少随机 I/O，使单台服务器可以处理存储在 SSD 上的千亿边图。

流式与增量图计算

对于实时更新的图（如社交网络新关注、金融交易实时入账），每次有新边或顶点到达时重跑全量算法代价极高。增量计算引擎的目标是只重新计算受新增/删除边影响的顶点。

GraphBolt（SOSP 2019）提出依赖驱动的增量更新模型：系统维护顶点间的依赖关系图，新边到达时沿依赖关系向前传播影响，只激活真正需要重算的顶点。在 PageRank 等算法上，激活顶点集可以从 O(E) 收缩到 O(V) 甚至更小，大幅降低增量更新成本，同时保持 BSP 语义。

GeaFlow / TuGraph-Analytics 将流批融合推进得更彻底：图结构更新事件（边的插入/删除）直接触发算子图中的下游计算，与批量快照分析共享同一套调度框架。

批流权衡

维度 批处理 增量/流处理
新鲜度 分钟级至小时级 秒级至毫秒级
计算成本 高（全量） 低（增量）
实现复杂度 低 高
适用场景 离线特征、报表 实时风控、推荐
代表引擎 Giraph、Plato GeaFlow、GraphBolt

规模化图算法的生产实现

PageRank

PageRank 是图计算基准测试中出现频率最高的算法，也是推断顶点重要性的基础方法。生产实现中有两类常见优化。

Delta PageRank 不传递绝对值，而是传递与上次超步的差值，只有差值超过阈值的顶点才参与下一超步，显著减少收敛后期的无效计算量。在 GraphX 中，aggregateMessages 通过 TripletFields 参数控制序列化范围；在 Plato 中，顶点消息在发送前先在本地合并（combiner），减少跨机器传输量。

社区发现

标签传播算法（LPA/CDLP）是最常见的分布式社区发现方案，因其计算模式天然适合顶点中心模型：每个顶点取邻居中出现频率最高的标签作为自身新标签，迭代至收敛。LPA 计算代价低，但结果随机性强。

Louvain 算法在模块度最大化上效果更好，但其局部移动阶段难以并行化。生产中常见的实现是先用 LPA 做粗粒度分区，再在子图内运行 Louvain 精化，兼顾效率和质量。

最短路径

单源最短路径（SSSP）的生产实现通常基于 Bellman-Ford 的分布式变体，结合 Delta-Stepping 思想控制并行粒度：将顶点按距离估算值分桶，每个 bucket 内的顶点并行松弛，减少超步数量。

Dijkstra 的朴素版本难以并行化，但在 NUMA 共享内存架构（如 Galois）中可以通过优先队列的细粒度锁或无锁实现达到较好的并发度。

连通分量

并行 WCC 的主流做法是"钩子-压缩"（Hook-Compress）迭代：在每个超步中，每个顶点尝试将自身的根节点更新为邻居的最小根节点（钩子），然后进行路径压缩。这比朴素标签传播收敛更快，通常在 O(log n) 个超步内收敛。

基准测试体系

LDBC Graphalytics

LDBC（Linked Data Benchmark Council，非营利组织）是图数据库和图计算领域最具影响力的独立基准测试机构。Graphalytics 定义了六个核心算法：

算法 缩写
广度优先搜索 BFS
PageRank PR
弱连通分量 WCC
社区标签传播 CDLP
局部聚集系数 LCC
单源最短路径 SSSP

Graphalytics 在多个标准数据集规模上运行上述算法，输出每算法每规模的处理时间，并向公开排行榜提交，供横向比较。

LDBC 还维护 SNB（Social Network Benchmark）系列：SNB Interactive 测量图数据库的交互式查询吞吐量（QPS）；SNB BI 测量复杂分析查询延迟；FinBench（由蚂蚁集团贡献）针对金融场景的路径查询和子图匹配。

2023 年，GraphScope 在 LDBC SNB Interactive 基准上以超过 33,000 QPS 的成绩刷新纪录，超过前纪录 2.45 倍。2024 年，AtlasGraph 又将该纪录进一步提升约 45%。2020 年，TuGraph 在 SNB 基准上的吞吐量达到当时纪录的 7.6 倍。

Graph500

Graph500 面向高性能计算领域，核心测量指标是 GTEPS（Giga Traversed Edges Per Second），评估大规模 BFS（及 SSSP）的遍历效率。榜单每半年在 SC（SuperComputing）和 ISC 会议上更新，长期由超算节点数量最多的系统占据前列；日本 Fugaku 超级计算机曾长期保持 BFS 榜首，中国超算机构也多次进入前十。

Graph500 对系统集成和编程模型要求不高，更多反映互联网络带宽和内存访问效率，不直接对应工程实践中的图计算框架选型。

性能比较的注意事项

跨论文的性能数字对比需要特别谨慎：

  • 不同论文使用的基准数据集（Twitter 图、UK-Web、RMAT 合成图）规模和结构差异很大
  • 硬件配置（服务器数量、内存大小、网络带宽）往往不同
  • 图切割策略（边切割 vs 顶点切割）、内存布局（CSR vs adjacency list）的差异会影响单一算法的表现
  • 同一引擎在不同算法上的相对排名可能截然不同

Gemini 和 Spark 的百倍差距、GraphScope 和 Gemini 的百倍差距，均基于各自论文中的实验设置，不构成可传递的性能链，实际选型时应以自身数据集和硬件配置为准进行实测。

生产部署决策

图数据库内置分析 vs 专用图计算引擎

图数据库（如 Neo4j、TuGraph、JanusGraph）的设计目标是事务性工作负载（OLTP）：低延迟的多跳查询、实时写入、ACID 事务。这类系统的图存储格式（如邻接链表、Native 图存储）针对局部遍历优化，当需要对全图运行 PageRank 或社区发现时，往往要将数据加载到独立的分析路径。

Neo4j Graph Data Science（GDS）通过"图投影"（graph projection）机制缩短了这一距离：将子图从 Neo4j 的事务存储投影到内存中的专用格式，然后运行 65+ 个内置算法，结果写回图数据库节点属性。这适合算法逻辑简单、数据量不超过单机内存的场景，且可以避免为分析需求单独维护一套图计算集群。

当数据规模超出单机内存、算法复杂度高（如多跳路径枚举、大规模 GNN 训练），或需要与 Spark/Flink 等数据平台深度集成时，专用图计算引擎的优势才得以体现。

选型决策框架

数据量不超过单机内存（通常数亿边以内）时，图数据库内置 GDS 或 Networkx/igraph 等单机库即可满足需求，无需引入分布式复杂度。

数据量在十亿至百亿边区间、团队有 Java/Scala 背景时，Spark GraphX 在已有 Spark 集群的前提下是最低摩擦的选项，与 DataBricks、阿里云 EMR 等托管环境兼容。同等数据量下若团队对 C++ 有掌控力且计算资源有限，Plato 以显著更少的节点完成相同任务；美团、网易等公司已在生产中使用。

图查询、图分析与 GNN 训练需求并存、Kubernetes 基础设施完善时，GraphScope 的统一接口可减少多套引擎的运维负担。需要实时更新图结构并触发下游计算的场景，GeaFlow / TuGraph-Analytics 或基于 Flink DataStream API 的自研方案是更合适的选择，批处理引擎启动延迟过高无法满足实时性要求。HPC 集群或图模式挖掘（子图同构）场景，Galois/Katana 在 NUMA 感知调度和 pattern mining 支持上有专门优化。

常见架构误区

误区一：用图数据库做全图分析
图数据库的存储引擎针对事务路径优化，全图扫描往往需要将所有顶点和边遍历一遍，性能远不如专用图计算引擎。适合做的事情是通过 GDS 插件将图数据 project 到内存后再运行算法。

误区二：用图计算引擎做实时查询
Giraph、GraphX 等批处理框架的启动开销以分钟计，无法响应毫秒级的交互式查询请求，两种需求应由不同系统承担。

误区三：用同一基准数字比较不同引擎
同一个"百倍"的性能声明，可能对应的是不同数据集、不同硬件、不同算法，在相同实验条件下重现基准是选型的基本前提。

综述结论

大规模图计算的技术格局经过十余年演化，已形成清晰的分层架构：

  • 编程范式层：BSP（Pregel）和 GAS（PowerGraph）两种顶点中心模型为基础，推送/拉取自适应（Gemini/Ligra）为高性能优化
  • 引擎层：Giraph、GraphX、Plato、GraphScope 满足不同技术栈和规模需求；Gelly 随 Flink DataSet API 进入弃用，需评估迁移路径
  • 计算模式层：批处理（快照图）和流处理（增量图）的适用场景边界已较清晰，GraphBolt、GeaFlow 代表了增量计算的主要方向
  • 评估层：LDBC 和 Graph500 提供不同角度的基准参考，工程选型需结合实际数据和硬件独立评估

当前值得关注的技术方向包括：图与 GNN 的联合计算（GraphScope GLE、GeaFlow FIFO-GNN）、GPU 加速图计算（Katana Graph、RAPIDS cuGraph）、以及图数据库与图计算引擎的功能边界融合（Neo4j GDS、TuGraph 的 AP/TP 统一）。

参考资料

  • Malewicz, G. et al. Pregel: A System for Large-Scale Graph Processing. SOSP 2010.
  • Gonzalez, J. et al. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. OSDI 2012.
  • Shun, J. & Blelloch, G. Ligra: A Lightweight Graph Processing Framework for Shared Memory. PPoPP 2013.
  • Zhu, X. et al. Gemini: A Computation-Centric Distributed Graph Processing System. OSDI 2016.
  • Fan, W. et al. Parallelizing Sequential Graph Computations (GRAPE). SIGMOD 2017.
  • Sahu, S. et al. The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing. VLDB 2017.
  • GraphScope Team. GraphScope: A Unified Engine for Big Graph Processing. VLDB 2021.
  • Fan, W. et al. GraphScope Flex: LEGO-Like Graph Computing Stack. SIGMOD 2024.
  • Mariappan, M. & Vora, K. GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs. EuroSys 2019.
  • Zhu, X. et al. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. ATC 2015.
  • LDBC Benchmark Council. LDBC SNB Interactive Results. https://ldbcouncil.org/
  • Graph500 Steering Committee. Graph500 Benchmark. https://graph500.org/
  • Apache Giraph Documentation. https://giraph.apache.org/
  • Apache Spark GraphX Documentation. https://spark.apache.org/graphx/
  • GeaFlow / TuGraph-Analytics GitHub. https://github.com/TuGraph-family/tugraph-analytics
  • Plato Graph Engine GitHub. https://github.com/Tencent/plato
  • 美团技术团队. 图计算引擎对比实践（Plato vs GraphX vs Giraph）. 2020.