本文主要是介绍[论文笔记] 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)
, 其中 status
为 NEW
(新增匹配) 或 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 子图扩展规则
- 根据边扩展的顺序, 排除具有相同时间戳但边的值比子图 s s s 中的值低的边, 即 ( v , u ) < ( s [ 0 ] , s [ 1 ] ) (v,u)<(s[0],s[1]) (v,u)<(s[0],s[1]) (§4.4.3).
- 根据更新规范性顺序, 检查待添加加的结点要比之前扩展的结点有更大的标识符(§4.4.1)。
- 算法执行是基于更新边的时间戳的图快照((§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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!