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$(时间戳 $ts$ 时的数据图快照), $ts$(时间戳), $s$(边更新所包含的边及其两个端点), $C_{pre}$ $C_{post}$(决定搜索停止的两个连续变量).
CAN_EXPAND(): 用于过滤冗余的搜索和重复的匹配
EXPAND(): 通过添加结点 $v$ 和 $v$ 连接到子图 $s$ 的所有边, 将子图 $s$ 扩展成 $s^{\prime }$.
DETECT_CHANGES(): 确定扩展子图 $s^{\prime }$ 是否导致匹配集的改变, 并确定是否进一步扩展 $s^{\prime }$(通过设定变量$C_{pre}$ $C_{post}$)
Tesseract 支持边诱导子图枚举, 通过将结点扩展转化为等效的边诱导扩展.

4.3 变化检测

DETECT_CHANGES() 实现了一种差异处理技术, 通过搜索更新前($s_{src}^{\prime }$)和更新后($s^{\prime }$)这两状态的图以寻找更新图产生的所有变化. 在这个过程中确定每个候选子图是否匹配, 及其是新创建的(NEW)还是删除的(REM).
SUBGRAPH_AT_PREVIOUS_SNAPSHOT(): 计算 $ts$ 前一时间点图快照中 $s^{\prime }$ 的结点对应的子图 $s_{pre}^{\prime }$.

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$.
• Rule 2: 忽略更新边的结点 $v_1$ $v_2$, 扩展添加的结点 $v$ 是子图 $s$ 尚未扩展的领域结点中 ID 最小的结点.

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

4.4.2 避免重叠搜索

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

4.4.3 基于快照的搜索

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

4.4.4 子图扩展规则

1. 根据边扩展的顺序, 排除具有相同时间戳但边的值比子图 $s$ 中的值低的边, 即 $(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)的挖掘算法, 以及针对更新过程中的避免重复搜索的去重方法.