大规模图计算是互联网基础设施的重要组成部分。社交网络中的好友关系、金融风控中的资金流转链路、供应链中的货品追溯，本质上都是图结构问题。本文专注计算范式、批量与增量引擎、规模化算法和基准测试；图数据库、知识图谱与 GNN 的全链路地图见《深入图工程》，Agent 编排中的图模型则由《Coding Agent 领域的 Graph Engineering》展开。

图计算范式

Pregel 与 BSP 模型

2010 年，Google 在 SIGMOD 发表 Pregel 论文，确立了大规模图计算中影响深远的"以顶点为中心"（vertex-centric）编程抽象。开发者实现单个顶点的计算逻辑，系统负责分区、消息传递和全局协调。

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

这是 Leslie G. Valiant 在 1990 年提出的 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（PPoPP 2013，MIT）在共享内存环境中实现了稀疏/稠密前沿之间的自适应切换：

  • 推送（Push）：活跃顶点主动向邻居发送消息，适合活跃顶点集合稀疏（如 BFS 初始阶段）
  • 拉取（Pull）：未访问或待更新顶点主动检查邻居状态，适合活跃集合稠密（例如 BFS 前沿扩张到图的主体时）

Gemini（Tsinghua，OSDI 2016）将这一思想移植到分布式环境。Gemini 以 CSR（Compressed Sparse Row）格式组织出向边、以 CSC（Compressed Sparse Column）格式组织入向边，在每个超步根据活跃边规模选择模式。论文在 8 节点集群、5 个应用和 5 张真实图上的结果是：相对各组实验中最快的既有分布式系统，Gemini 的加速范围为 8.91 倍至 39.8 倍。这个数字只对论文中的硬件、数据集和实现版本成立，不能外推成对 Spark 或 PowerGraph 的固定倍数。

边切割与顶点切割的权衡

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

许多社交图、Web 图和交易图具有重尾度分布，少数 Hub 节点承载大量边。顶点切割在这类图上常能改善负载均衡，但会增加镜像同步和状态一致性成本，并不是所有图和算法的默认最优解。

主流计算引擎

Apache Giraph：Hadoop 生态的 Pregel 实现

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

Facebook 曾将 Giraph 用于超大规模社交图分析。Giraph 的经典分区接口按顶点 ID 将顶点及其出边分配给分区，更接近 edge-cut，而不是 PowerGraph 式 vertex-cut。更重要的是，Apache Giraph 已于 2023 年 9 月退役，2024 年 2 月完成迁入 Apache Attic；存量系统仍可维护，但新项目不应再把它当作活跃的 Apache 选项。

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 生态内：同一应用可以把 Spark SQL 或流处理产出的数据转换为 RDD，再进入 GraphX。它本身仍是 RDD API，并不是 Structured Streaming 的原生增量图算子。代价是 RDD 的序列化、shuffle 和 GC 开销，使其在单纯图计算基准上常不如专用引擎。

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

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

Gelly 的定位是让 Flink 的批处理生态拥有统一图分析接口。但它依赖旧 DataSet API，Flink 项目在 1.17 开发周期已经移除 Gelly；Flink 2.0 又完全移除了 DataSet API。因此 Gelly 是历史组件，不是 Flink 2.x 中等待迁移的"软弃用"图库。

Flink 2.x 的批处理逻辑应转向 Table API、DataStream API 的有界流模式或独立图引擎。目前没有由 Flink 主项目维护、基于 DataStream API 的 Gelly 继任者；需要实时图计算时，应把事件处理、图状态和图算法的职责边界单独设计。

Alibaba GraphScope：一站式图计算平台

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

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

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

GraphScope 在 LDBC SNB Interactive 的公开审计中多次刷新结果：2023 年单机结果超过 30,000 QPS，2024 年公布的 SF1000 结果超过 127,000 QPS。需要注意的是，该纪录针对交互式查询，与 Gemini 的批量图分析实验属于不同工作负载，不能直接比较。

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

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

公开工程案例曾在 Giraph、GraphX 和 Plato 之间做过选型，并在特定数据集与集群上选择 Plato。此类节点数、内存和耗时数字都强依赖图规模、算法、网络与调参，不能用二手转载中的固定倍数代替本地基准。对于能维护 C++/MPI 栈、资源敏感且以离线全图算法为主的团队，Plato 仍值得评估。

Apache GeaFlow：流图一体化

Apache GeaFlow（Incubating，源自蚂蚁集团）的核心设计目标是让批量图计算和流式图更新运行在同一引擎上。项目当前官方名称仍是 Apache GeaFlow；代码演进历史与 TuGraph-family 的 tugraph-analytics 仓库有关，但不应写成已经统一更名。其主要工程价值是把持续到达的边、点更新与有状态图计算放进同一运行时。

GeaFlow 支持多种状态与外部存储连接器，适合图持续更新且需要周期性全量分析的场景。TuGraph 数据库的 LDBC 成绩属于另一套查询引擎，不能拿来证明 GeaFlow 的流图性能。流批一体减少了快照搬运，却增加了状态一致性、事件时间和恢复语义的复杂度。

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（EuroSys 2019）提出依赖驱动的同步增量处理：边更新以批次进入，运行时追踪受影响的聚合值和顶点，只重新执行必要部分，同时保留 BSP 语义。这里的 GraphBolt 指 Simon Fraser University 的流图系统，不是 DGL 中同名的 GNN 数据加载组件。增量收益取决于更新稀疏度、算法依赖和图结构，不能概括为把复杂度固定地从 O(E) 降到 O(V)。

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

批流权衡

维度 批处理 增量/流处理
新鲜度 通常分钟级至小时级 取决于批次、状态和恢复设计
计算成本 每轮扫描范围大 更新稀疏时可能更低
实现复杂度 低 高
适用场景 离线特征、报表 实时风控、推荐
代表引擎 Plato、GraphX 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) 个 BSP 超步。

基准测试体系

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（由蚂蚁集团贡献）针对金融场景的路径查询和子图匹配。

GraphScope 公布的 2024 年 LDBC SNB Interactive 审计结果超过 127,000 QPS，并扩展到 SF1000 数据集。基准结果必须同时记录版本、数据规模、硬件、可用性要求和审计配置；只摘一个倍数或 QPS 无法指导选型。

Graph500

Graph500 面向高性能计算领域，核心测量指标是 GTEPS（Giga Traversed Edges Per Second），评估大规模 BFS 和 SSSP 的遍历效率。榜单按实测 GTEPS 排名；节点数、核心数、内存带宽和互联网络都会影响结果，但"节点最多"不是排名规则，也不能解释所有名次。

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

性能比较的注意事项

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

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

任何"快若干倍"的结论都只属于对应实验设置，不能把两篇论文的相对结果串成传递关系。实际选型应在同一数据集、硬件、算法实现和正确性约束下复测。

生产部署决策

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

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

Neo4j Graph Data Science（GDS）通过"图投影"（graph projection）机制缩短了这一距离：将子图从 Neo4j 的事务存储投影到内存中的专用格式，运行数十种内置算法，再把结果写回节点属性。这适合投影后的图能够容纳在可用内存、算法受 GDS 支持的场景，也可以避免单独维护图计算集群。

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

选型决策框架

投影后的图、算法状态和中间结果能够容纳在单机内存时，图数据库内置分析或 NetworkX/igraph/NetworKit 等单机库通常更省事。边数阈值取决于属性宽度、算法和内存布局，不能用"数亿边"作为通用分界。

已有 Spark 集群、数据管线以 RDD/SQL 为主且图算法不是延迟敏感路径时，GraphX 的集成摩擦较低。若团队能维护 C++/MPI 栈、计算资源敏感且工作负载以离线全图算法为主，可以用 Plato 做同条件基准。无论十亿边还是百亿边，都应先用代表性子图测算内存、shuffle 和迭代次数。

图查询、图分析与 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）为高性能优化
  • 引擎层：GraphX、Plato、GraphScope 满足不同技术栈和规模需求；Giraph 已进入 Apache Attic，Gelly 已从 Flink 主线移除
  • 计算模式层：批处理（快照图）和流处理（增量图）的适用场景边界较清晰，GeaFlow 是活跃的流图项目，GraphBolt 则是依赖驱动增量计算的研究系统
  • 评估层：LDBC 和 Graph500 提供不同角度的基准参考，工程选型需结合实际数据和硬件独立评估

当前值得关注的技术方向包括：图分析与 GNN 数据管线的衔接、GPU 加速图计算（RAPIDS cuGraph 等），以及图数据库与图计算引擎的功能边界融合（Neo4j GDS、GraphScope Flex 等）。

参考资料