首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

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

编程知识
2024年07月31日 22:54

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算法
From:https://www.cnblogs.com/fanzhidongyzby/p/18332148/graphbolt
本文地址: http://www.shuzixingkong.net/article/646
0评论
提交 加载更多评论
其他文章 在 Hub 上使用 Presidio 进行自动 PII 检测实验
我们在 Hugging Face Hub 上托管的机器学习 (ML) 数据集中发现了一个引人关注的现象: 包含个人未经记录的私密信息。这一现象为机器学习从业者带来了一些特殊挑战。 在本篇博客中,我们将深入探讨含有一种称为个人识别信息 (PII) 的私密信息的各类数据集,分析这些数据集存在的问题,并介
在 Hub 上使用 Presidio 进行自动 PII 检测实验
代码随想录Day1
704.二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释:
代码随想录Day1 代码随想录Day1 代码随想录Day1
从C++看C#托管内存与非托管内存
进程的内存 一个exe文件,在没有运行时,其磁盘存储空间格式为函数代码段+全局变量段。加载为内存后,其进程内存模式增加为函数代码段+全局变量段+函数调用栈+堆区。我们重点讨论堆区。 进程内存 函数代码段 全局变量段 函数调用栈 堆区 托管堆与非托管堆 C# int a=10这种代码申请的内存空间位于
从C++看C#托管内存与非托管内存 从C++看C#托管内存与非托管内存 从C++看C#托管内存与非托管内存
架构演化思考总结(2)
架构演化思考总结(2) ​ —-–从命令模式中来探索处理依赖关系 在正式引入命令模式的概念之前,我们先从简单的案例来逐步演化大家在书面上常见到的内容。 public interface ICommand { void Execute(); } public class PlayMusicComman
架构演化思考总结(2)
C#/.NET/.NET Core优秀项目和框架2024年7月简报
前言 公众号每月定期推广和分享的C#/.NET/.NET Core优秀项目和框架(每周至少会推荐两个优秀的项目和框架当然节假日除外),公众号推文中有项目和框架的介绍、功能特点、使用方式以及部分功能截图等(打不开或者打开GitHub很慢的同学可以优先查看公众号推文,文末一定会附带项目和框架源码地址)。
C#/.NET/.NET Core优秀项目和框架2024年7月简报 C#/.NET/.NET Core优秀项目和框架2024年7月简报 C#/.NET/.NET Core优秀项目和框架2024年7月简报
《最新出炉》系列初窥篇-Python+Playwright自动化测试-61 - 隐藏元素定位与操作
1.简介 对于前端隐藏元素,一直是自动化定位元素的隐形杀手,让人防不胜防。脚本跑到隐藏元素时位置时报各种各样的错误,可是这种隐藏的下拉菜单又没有办法避免,所以非常头痛,这一篇只为交流隐藏元素自动化定位处理方法以及宏哥自己的一点浅薄见解。 2.什么是隐藏元素 隐藏元素,熟悉前端的或者HTML的小伙伴或
《最新出炉》系列初窥篇-Python+Playwright自动化测试-61 - 隐藏元素定位与操作 《最新出炉》系列初窥篇-Python+Playwright自动化测试-61 - 隐藏元素定位与操作 《最新出炉》系列初窥篇-Python+Playwright自动化测试-61 - 隐藏元素定位与操作
BI 工具助力企业解锁数字化工厂,开启工业智能新视界
背景 在 2022 年公布的《“十四五”数字经济发展规划》中,政府不断增加对制造业数字化转型的政策支持力度,积极倡导制造企业采用最新技术,提升自动化、数字化和智能化水平。这一举措旨在强化国际竞争力,推动制造业由制造大国向制造强国转变。 然而,在制造业数字化和智能化升级的过程中,涉及以下一系列挑战和难
BI 工具助力企业解锁数字化工厂,开启工业智能新视界 BI 工具助力企业解锁数字化工厂,开启工业智能新视界 BI 工具助力企业解锁数字化工厂,开启工业智能新视界
救园行动——赞助商计划
在发出求救信后,很多园友出手相救,非常感谢大家的支持! 在求救的同时,我们也在想办法奋力自救,会采取一系列的救园行动,这一次一定要把园子救下来,因为没有下一次了。 今天发布的救园行动是赞助商计划,想找10家企业赞助园子,并成为园子的创始赞助商。 有人可能会笑话这个救园计划是一个幼稚的想法,没有直接的
救园行动——赞助商计划