我用Awesome-Graphs看论文:解读GraphBolt

GraphBolt论文《GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs》

前面通过文章《论文图谱当如是:Awesome-Graphs用200篇图系统论文打个样》向大家介绍了论文图谱项目Awesome-Graphs,并分享了Google的Pregel、OSDI'12的PowerGraph、SOSP'13的X-StreamNaiad。这次向大家分享一篇流图处理系统论文GraphBolt,看如何基于计算历史的方式实现增量图计算,并保证与全量图计算语义的一致性。

对图计算技术感兴趣的同学可以多做了解,也非常欢迎大家关注和参与论文图谱的开源项目:

提前感谢给项目点Star的小伙伴,接下来我们直接进入正文!

摘要

GraphBolt通过抓取计算过程中的中间值依赖实现依赖驱动的增量计算,并保证了BSP语义。

1. 介绍

流图处理的核心是动态图,图的更新流会频繁地修改图的结构,增量图算法会及时响应图结构的变更,生成最新图快照的最终结果。因此,增量图算法的核心目标是最小化重复计算。典型系统如:GraphIn、KickStarter、Differential Dataflow等。

GraphBolt通过依赖驱动的流图处理技术最小化图变更带来的重复计算。

  • 描述并跟踪迭代过程中产生的中间值的依赖关系。
  • 图结构变更时,根据依赖关系逐迭代地产生最终结果。

关键优化:

  • 利用图结构信息以及点上聚合值的形式,将依赖信息的规模从O(E)降低为O(V)。
  • 支持依赖驱动的优化策略和传统的增量计算的动态切换,以适应因剪枝导致依赖信息不可用的情况。
  • 提供通用的增量编程模型支持将复杂聚合拆解为合并增量值的方式。

2. 背景与动机

2.1 流图处理

流图G会一直被ΔG更新流修改,ΔG包含了点/边的插入/删除,算法S在最新的图快照上迭代计算最终结果。为了保证一致性,迭代计算过程中的更新被分批写入到ΔG,并在下次迭代开始前合并到G。

同步处理

BSP模型将计算分为多个迭代,当前迭代的计算只依赖于上次迭代计算的结果。这让图算法的开发更简单,并能清晰的推导收敛信息以及准确性验证。因此,同步处理模型是大规模图计算系统的首选。

增量计算

  • I:点初始值。
  • k:迭代次数。
  • Si(G, I):以I为输入的图G上算法S的第i次迭代。
  • S*(G, I):以I为输入的图G上算法的最后一次迭代。
  • RGi:图G的第i次迭代结果。
  • RG:图G的迭代结果。
  • GT:G+ΔG。
  • Zs:转换函数,\(R_{G^T}^k = Z^s(R_G^k)\)

2.2 问题:不正确的结果

如何在面向图变更的流图的增量计算中最小化重复计算,而又保证同步处理的语义?

2.3 技术概览

依赖驱动增量计算面临的挑战:

  • 在线跟踪依赖信息成本高,复杂度|E|。
    • 基于点聚合值的方式,将复杂度降低到|V|。
    • 现实图一般是稀疏倾斜的,可以对依赖信息进行保守的剪枝。
  • 处理复杂聚合计算的困难性。
    • 开发通用增量编程模型将复杂聚合分解为增量的值变更。
    • 简单聚合,如sum、count可以直接表达,而无需走分解的流程。
  • 计算感知的混合执行能力。
    • 支持依赖驱动的优化策略和传统的增量计算的动态切换。

3. 依赖感知处理

3.1 同步处理语义

基于图结构定义值依赖关系:

  • (u, v):计算图中任意边。
  • ut:第t次迭代,点u的值。
  • ->:依赖关系,后者依赖前者。

3.2 跟踪值依赖关系

假设第L次迭代后,图G被修改为GT,CL对应迭代L结束后的点值集合。为了保证结果的准确性,需要跟踪计算过程中所有对CL有贡献的点值信息。

\(\mathcal{D}_G=(\mathcal{V}_D,\mathcal{E}_D)\),则有:


每次迭代,DG增加|V|个点和|E|和边信息。空间复杂度O(|E|·t)。

基于点聚合值跟踪点依赖

一般点值计算分为两个步骤。

  • \(\bigoplus\):聚合上次迭代的邻居点的值。
  • \(\oint\):根据聚合值计算点值。

\(g_i(v)=\bigoplus_{\forall e=(u,v)\in E}(c_{i-1}(u))\)\(\mathcal{A}_G=(\mathcal{V}_\mathcal{A},\mathcal{E}_\mathcal{A})\),则有:


通过跟踪点上的聚合值,而非单独的点值,将空间复杂度降低到O(|V|·t)。

裁剪值聚合信息

现实图上一般都是倾斜的,所以算法最开始的时候大多数点值会发生变化,但随着迭代的推进,更新点的数量将逐渐减少。


当点值稳定时,点上的聚合值也趋于稳定,这就为聚合值的依赖信息跟踪提供了优化机会。

  • 水平裁剪:当到达确定的迭代后,停止跟踪聚合值,对应上图中的红线。
  • 垂直裁剪:对于已经稳定的点值,将不再跟踪聚合值,对应上图中红线上的白色区域。

3.3 依赖驱动的值优化

令Ea表示新增的边,Ed表示删除的边,则有\(G^T=G \cup E_a \backslash E_d\),对于依赖图\(\mathcal{A}_G\),如何转换CL到CLT。

优化什么?

每次迭代的优化动作有两种:

  1. Ea、Ed中边的终点,对应的点值会被边修改影响。
  2. 终点的邻居,邻居点值会在下次迭代中被优化。


例如,新增边1->2时,聚合值的更新如上图。其中实线表示值的传播,虚线表示值的变化。
整个过程依赖于图\(\mathcal{A}_G\),聚合值变化来源于边的修改。优化过程中涉及的计算远小于在原图上重新计算。

如何优化?



对于简单的聚合操作,如sum、product,可以直接计算出变化的贡献。但是对于复杂的聚合操作,如向量操作,就比较难以直接表示。

复杂聚合

对于MLDM算法,如BP、ALS,将点值增量化就比较困难。将复杂聚合转换为增量方式,可以分为两步。

静态拆解为简单子聚合

复杂聚合可以被分解为多个简单的子聚合,如ALS算法。


聚合值可以表示为:

独立贡献的动态求值

子聚合对点值的计算发生在sum之前,会带来重复计算。因此需要独立计算每个部分,再计算聚合的差异值。

聚合属性和扩展

三个增量聚合算子(+、-、Δ)的特点:

  • 算子是可交换、可结合的。
  • 算子的定义域包含点上的聚合值以及边上的关联值。
  • 算子可以增量的处理单个输入带来的影响。

这类算子属于可分解的,如sum、count。

相对的则是不可分解的算子,如max、min。对+操作可以可增量的,但是-和Δ则不可。
因此聚合值就退化为输入点值的集合,实现方式是动态拉取输入边的值。

4. GraphBolt处理引擎

4.1 流图和依赖布局

点/边的增加/删除以以下两种方式进行:

  1. 单个点/边的变更。
  2. 批量点/边的变更。

变更一旦生效会立即触发值优化,在优化过程中的的变更会被缓存,并在接下来的优化步中继续处理。
聚合值被维护在一个和点对应的数组中,保存了跨迭代的值数据。随着计算过程,聚合值信息被更新并动态增长。

4.2 依赖驱动的处理模型

BP算法使用restract+propagate模拟update。


PangeRank算法直接定义propagate_delta实现update。

选择性调度

GraphBolt只会在邻居值更新后才会重新计算点值,并允许用户指定选择性调度的逻辑,如比较值变化的容忍范围来决定是否发起重新计算。

计算感知的混合执行

水平裁剪导致超过指定迭代后,聚合值将不再有效,GraphBolt会动态切换为不带值优化的增量计算模式。

4.3 保证同步语义

定理:使用依赖驱动的值优化方式,基于ci-1T(u)计算giT(v)可以满足ET定义的依赖关系。

5 相关工作

  • 流图处理框架
    • Tornado:在图更新时,分叉执行用户查询。
    • KickStarter:使用依赖树增量修正单调图算法。
    • GraphIn:使用固定大小的批处理动态图,提供了5阶段处理模型。
    • Kineograph:基于pull/push模型实现图挖掘的增量计算。
    • STINGER:提出动态图数据结构,为特定问题研发算法。
  • 图快照的批处理
    • Chronos:使用增量的方式实现跨快照的计算。
    • GraphTau:维护快照上的值历史记录,通过值的回退实现数据修正。
    • 静态图处理系统:处理离散的图快照。
  • 通用流处理
    • 通用流处理系统:操作无边界的非结构化数据流。
    • Differential Dataflow:扩展了Timely Dataflow的增量计算,它强依赖于差分算子。
  • 增量算法
    • 增量PageRank
    • Triangle Counting
    • IVM算法
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接,否则作者保留追究法律责任的权利。
若本文对你有所帮助,您的 关注 推荐 是我分享知识的动力!