[论文笔记] Tesseract: Distributed, General Graph Pattern Mining on Evolving Graphs

本文主要是介绍[论文笔记] Tesseract: Distributed, General Graph Pattern Mining on Evolving Graphs,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Tesseract: Distributed, General Graph Pattern Mining on Evolving Graphs

Tesseract: 基于演化图的分布式通用图模式挖掘 [Paper] [Slides]
EuroSys’21

摘要

  • 第一个在演化图上执行通用图挖掘算法的分布式系统
  • 提出一种新的变化检测方法,有效地确定精确的修改
  • 一个分类的、多版本的图存储
  • 使用增量聚合(aggregation) API (处理增量后匹配)

1 介绍

  • Def: 挖掘一个图以枚举出所有匹配感兴趣模式的子图,称为 matches(匹配)。

大多数图挖掘系统关注于处理静态图, 或者在单节点上运行. Delta-BigJoin 是唯一支持演化图的分布式系统, 但不是通用图挖掘系统.
关键创新: update-based exploration(基于更新的搜索).

  • 观察现象: 匹配集中的更改必须包含图更新. 图更新只影响其邻域中有限的匹配子集.
  • 挑战:
    • 更新产生的新匹配, 以及失效的匹配 -> 多版本图存储, 差异处理技术确定更新
    • 防止重复搜索 -> 规范搜索顺序, 多版本存储
  • 优点: 可以有效扩展(每次更新都可以任意顺序独立处理). 跨 worker 动态分发更新, 以实现负载均衡. 分片图存储减轻 worker 间通信同步开销.

文章贡献:

  • Tesseract: 第一个用于演化图分布式流式通用图挖掘系统
  • 提出一种增量挖掘方法.
  • 多版本图存储可独立操作并避免重复
  • 在图更新情况下支持增量聚合
  • Tesseract 高性能低延迟

2 背景

图挖掘问题.
通用图挖掘系统: 支持任意代码定义模式图
子图查询系统: 只支持匹配固定模式图
匹配形式: 结点诱导(vertex-induced), 边诱导(edge-induced)

3 编程模型

3.1 核心挖掘 API

算法可兼容静态图挖掘算法, 图更新和增量计算对用户是隐藏.

filter-match 模型(开发者需要实现的函数接口):

  • filter(): 确定是否对子图及其扩展停止搜索或剪枝
  • match(): 确定子图是否是一个匹配(match).

应用程序需要满足的标准属性:

  • Anti-monotonicity(反单调性): 子图不满足, 子图的扩展一定不满足
  • Boundedness(有界性): 到达上界后不再继续搜索

在内部, Tesseract 在搜索算法中使用 filter()match() 函数. 算法输入图更新, 输出每个更新对应的三元组 (timestamp, status, subgraph), 其中 statusNEW(新增匹配) 或 REM(失效匹配), subgraph 为满足模式的匹配.
Tesseract 支持两种输出流模式: 无序流(立即匹配, 结果一致)和有序流(以时间戳顺序匹配).

3.2 图挖掘应用程序

在这里插入图片描述

3.3 输出处理和聚合 API

许多现有系统不支持输出处理和聚合, 而其它系统将聚合作为单独的后处理步骤. 对于演化图, 希望以流的方式执行输出处理和聚合.
Tesseract 使用并扩展了 Spark 结构化流式 API 以进行输出处理和聚合.
在这里插入图片描述

4 Tesseract 系统

4.1 概览

在这里插入图片描述

  • 入口结点(Ingress Node): 接受更新流数据, 并添加时间戳.
  • 分布式 worker: 对工作队列中的每个更新操作使用搜索算法执行图挖掘应用程序; 使用图快照计算差异并使用聚合 API 处理生成实时挖掘结果; 发送到发布/订阅(Pub/Sub)系统. Worker 对图只读, 且可处理任何更新.
  • 图存储: 分割到 worker 执行的所有集群节点上, 无需复制整个输入图且不跨 worker 对图划分.

4.2 基于更新的搜索

大多数图挖掘算法是局部化或有界的, 对输入图的更新只会影响更新周围的匹配.
在这里插入图片描述
搜索算法: 深度优先扩展和回溯, 递归地搜索图更新的邻域. 使用差异挖掘来查找匹配集的所有相应的变化.
输入: G G G(时间戳 t s ts ts 时的数据图快照), t s ts ts(时间戳), s s s(边更新所包含的边及其两个端点), C p r e C_{pre} Cpre C p o s t C_{post} Cpost(决定搜索停止的两个连续变量).
CAN_EXPAND(): 用于过滤冗余的搜索和重复的匹配
EXPAND(): 通过添加结点 v v v v v v 连接到子图 s s s 的所有边, 将子图 s s s 扩展成 s ′ s' s.
DETECT_CHANGES(): 确定扩展子图 s ′ s' s 是否导致匹配集的改变, 并确定是否进一步扩展 s ′ s' s(通过设定变量 C p r e C_{pre} Cpre C p o s t C_{post} Cpost)
Tesseract 支持边诱导子图枚举, 通过将结点扩展转化为等效的边诱导扩展.

4.3 变化检测

在这里插入图片描述
DETECT_CHANGES() 实现了一种差异处理技术, 通过搜索更新前( s s r c ′ s'_{src} ssrc)和更新后( s ′ s' s)这两状态的图以寻找更新图产生的所有变化. 在这个过程中确定每个候选子图是否匹配, 及其是新创建的(NEW)还是删除的(REM).
SUBGRAPH_AT_PREVIOUS_SNAPSHOT(): 计算 t s ts ts 前一时间点图快照中 s ′ s' s 的结点对应的子图 s p r e ′ s'_{pre} spre.

Example: 在这里插入图片描述

4.4 避免重复搜索

重复(duplicate, 即自同构)出现的原因:

  • 模式对称(pattern symmetry), 即以不同顺序搜索子图找到同一匹配两次
  • 同一匹配从两个不同的更新中被搜索到, 即该匹配包含两条更新的边.
  • 此外, 由于更新在图中可能比较接近, 会导致同一子图被重复且失败的搜索.

通过 CAN_EXPAND() 函数实现避免重复搜索.

4.4.1 Breaking Symmetry(破坏对称)

对于单个更新(模式对称)的去重.
在搜索图时强制执行一个扩展顺序, 即更新规范顺序(update canonical order).

  • Rule 1: 更新的边 ( v 1 , v 2 ) (v_1,v_2) (v1,v2) 满足 v 1 < v 2 v_1 < v_2 v1<v2.
  • Rule 2: 忽略更新边的结点 v 1 v_1 v1 v 2 v_2 v2, 扩展添加的结点 v v v 是子图 s s s 尚未扩展的领域结点中 ID 最小的结点.

此外, 扩展是从更新的边开始的, 即子图 s s s 开始.

4.4.2 避免重叠搜索

对于多个更新的相同匹配的去重.
使用多版本控制策略避免重复搜索和重复匹配的输出, 该策略在图存储中对更新排序来确保 worker 看不到未来的更新.
worker 只能看到时间戳低于更新时间戳的扩展, 且只能发现有最高时间戳的搜索(即从更新的边开始扩展).

4.4.3 基于快照的搜索

使用包含多个更新的快照优化搜索 -> 减少快照开销, 跳过中间匹配的工作.
为多个连续更新分配同一时间戳. 从而让输入图快照包含所有更新, 而上一图快照都不包含所有更新.
除更新时间戳的顺序外, 对图的边添加严格的总顺序(如基于结点 ID), 以确保多更新产生的匹配只会被找到一次.

4.4.4 子图扩展规则

在这里插入图片描述

  1. 根据边扩展的顺序, 排除具有相同时间戳但边的值比子图 s s s 中的值低的边, 即 ( v , u ) < ( s [ 0 ] , s [ 1 ] ) (v,u)<(s[0],s[1]) (v,u)<(s[0],s[1]) (§4.4.3).
  2. 根据更新规范性顺序, 检查待添加加的结点要比之前扩展的结点有更大的标识符(§4.4.1)。
  3. 算法执行是基于更新边的时间戳的图快照((§4.4.2).

4.5 并行搜索

每次更新的搜索任务独立于其它任务, 可以按任意顺序执行.
独立性是通过结合变化检测(§4.3)和重复消除(§4.4)机制实现的.
并行搜索无需其它变化, 没有额外开销.

5 实现

使用 Apache Spark Structured Streaming 流处理引擎, 并由专为图模式挖掘设计的图处理引擎作为补充.

5.1 入口结点

处理输入图更新, 并按时间戳顺序(用户可自定义)存入图存储中.
对已删除的旧边进行垃圾回收.

5.2 图存储

基于 MongoDB 进行图存储, 使用邻接链表格式.
删除的边会被保留, 以特殊标识标记.

5.3 工作队列

使用 Apache Kafka 实现.
工作队列满足先进先出(FIFO), 更新按时间戳排序.
动态工作分配: 任何 worker 可以处理任何更新, 其可从图存储中访问输入图的任何部分, 无需对队列中的更新划分.
[疑问] 分布式 worker 为何可以访问图的任意部分, 前文提到图存储是分割到多个 worker 上的, 可访问性是由 MongoDB 的图存储保证的么?

5.4 输出处理

输出处理和聚合 API 由 Spark Structured Streaming 实现.
输出端利用 Kafka 来存储发出(EMIT)的匹配, 并为用户提供一个发布-订阅平台.
输出排序: 发布-订阅平台支持按时间戳对匹配重排序. 支持通过低水印(low watermarks)提供同步点, 以确保小于等于目标时间戳的更新都已发出(EMIT).

5.5 容错性

图存储在 worker 机器上进行复制(replicated)和分片(sharded), 且在出现故障时可恢复. 缓存在 worker 中的图可能丢失但不影响正确性.
通过 Spark 处理 worker 崩溃, 以及重启和工作重分配.
使用 Kafka 确保更新的语义仅为一次(即每个更新只被处理一次).

5.6 优化

子图的边使用邻接矩阵位图(bitset)实现. 搜索使用固定大小的位图.
子图上的许多操作也使用位运算.

6 评估

与分布式通用静态图挖掘系统性能比较: Table 4
增量计算带来的性能提升: Figure 3 (优于周期性完全计算)
与分布式演化图子图查询系统(Delta-BigJoin)性能比较: Figure 5
与单机通用静态图挖掘系统性能比较: Table 5
在大型图上的处理性能和扩展性: Table 6
扩展性及性能损失: Figure 6


笔者总结

本文的核心在于提出了针对演化图挖掘的基于更新的搜索(update-based exploration)的挖掘算法, 以及针对更新过程中的避免重复搜索的去重方法.

这篇关于[论文笔记] Tesseract: Distributed, General Graph Pattern Mining on Evolving Graphs的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/415476

相关文章

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新,又或者克隆了某个项目之后,你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

忽略某些文件 —— Git 学习笔记 05

忽略某些文件 忽略某些文件 通过.gitignore文件其他规则源如何选择规则源参考资料 对于某些文件,我们不希望把它们纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。通常它们都是些自动生成的文件,比如日志文件、编译过程中创建的临时文件等。 通过.gitignore文件 假设我们要忽略 lib.a 文件,那我们可以在 lib.a 所在目录下创建一个名为 .gi