时序的 GFD 发掘

约 1550 字大约 5 分钟

2023-11-22

时序的 GFD 发掘（SEQUENTIAL GFD DISCOVERY）

我们将时间顺序的 GFD 发掘算法记作：SeqDisGFD。

这里面包含两个问题：

SeqDis：给定 $G$ ， $k$ 和 $\sigma$ ，发现一个 k-bounded 的，具备 $\sigma$ 频繁的 GFDs 集合 $\Sigma$ 。
SeqCover：给定 $\Sigma$ ，如何计算它的一个覆盖 $\Sigma_c$ 。

SeqDis

如果使用暴力枚举算法，首先根据传统图挖掘算法枚举出图 $G$ 中所有频繁模式 $Q$ ，然后通过增加属性来生成 GFDs。但是这种枚举 k-bounded GFDs 的方法在图 $G$ 非常大的时候代价很大。

为了降低代价，SeqDis 算法将这两个步骤合并为一个，可以尽早地淘汰不感兴趣的 GFDs。

算法在 $k^2$ 次迭代中运行。对于每个迭代 $i$ ，发现并存储所有的大小为 $i$ （有 $i$ 条边）且 $\sigma$ 频繁的最小 GFDs 在 $\Sigma_i$ 集合中。在最初的迭代中，初始化一个 GFD 生成树 $T$ ，存储只包含单点的模式的频繁 GFDs。之后通过两个方向的扩展来扩展这个树：

垂直扩展：扩展模式 $Q$ 。
水平扩展：生成依赖 $X \rightarrow Y$ 。

每次迭代 $i(0<i<k^2)$ ，SeqDis 生成并证实 GFD 的候选项，并填充在树 $T$ 的第 $i$ 层。具体的操作为下面的两个步骤：

模式证实。
SeqDis 算法先进行垂直扩展。在 $T$ 的第 $i$ 层生成一个新的图模式。而每个图模式 $Q'$ 都是由第 $i-1$ 层的模式 $Q$ 通过扩展一条边（或者一条边和一个新点）得到的。然后通过模式匹配找到第　 $i$ 　层所有模式的匹配。
GFD 验证。
算法随后进行水平扩展，将一组属性与 $T$ 的第 $i$ 层上新验证的图形模式关联起来，以生成一组 GFD 候选项。对于每一组候选项，执行 GFD 验证去找到 $\Sigma_i$ 中的 GFDs，即第 $i$ 层上满足 $G$ ，并且是频繁的，并且是最小的 GFD。验证过程一致持续到第 $i$ 层的模式相关的所有的GFD候选项都被验证过。

这两个步骤不断迭代知道没有新的 GFDs 可以被生成，或者所有的 k-bouned GFDs 都被遍历过。

接下来详细介绍垂直扩展和水平扩展，算法的核心就是如何维持用来保存 GFD 候选项的生成树。

生成树

树 $T=(V_T, E_T)$ 控制着 GFD 候选项的迭代。

每个在 $T$ 的第 $i$ 层的点 $v \in V_T$ 都存储着一个元组 $(Q[\bar{x}], lvec)$ 。其中：
- $v.Q[\bar{x}]$ 是一个拥有 $i$ 个边的图模式。
- $v.lvec$ 是一个向量，每个条目 $levc[l]$ 存储着一个以属性 $l$ 为根的属性树。此时， $l$ 是 $x.A=c$ 或者 $x.A=y.B$ ，其中 $x,y \in \bar{x}$ ，且 $A,B$ 是 $\Gamma$ 中的属性， $c$ 是 $G$ 中的常量。
每个第 $j$ 层的点的 $levc[l]$ 是一个属性集合 $X$ ，使得 $Q[\bar{x}](X \rightarrow l)$ 是一个 GFD 的候选项。对于一个属性 $l'$ 来说，如果 $X_1 =X_2 \cup {l'}$ ，则 $v.levc[l]$ 中有一个边 $(X_1, X_2)$ 。
每个点 $v(A[\bar{x}], lvec)$ 拥有一个边 $(v, v') \in E_T$ 连接到另一个点 $v'(Q'[\bar{x}], lvec')$ 如果 $Q'$ 是由 $Q$ 扩展了一条单边形成的。

上图就是一棵 GFD 生成树 $T$ ，展示了前文中提到过的两个 GFD，分别是：

GFD $\varphi_1= Q1[x,y](y.type = film \rightarrow x.type =producer)$ 。
GFD $\varphi_4= Q'1[x,y,z]({x.type = producer,z.name =Academy \ best \ picture} \rightarrow y.type = film)$ 。

该生成树就只有两个节点，第一层的节点存储了 $v(Q_1,Q_1.lvec)$ ，其中 $Q_1$ 是节点左边展示的图模式， $Q_1.lvec$ 则是一个以 $x.type=producer$ 为根的树，相当于将 $\varphi_1$ 的函数依赖存储到一棵树。第二层的节点存储了 $v(Q_1',Q_1'.lvec)$ ，而 $Q1'.lvec$ 以 $y.type=film$ 为根节点。

因为 $X''$ 是由 $X'$ 扩展一个属性得来的，即 $X''=X'\cup {z.name=Academy\ best\ picture}$ ，所以 $X'$ 和 $X''$ 之间存在一条边。又因为 $Q_1'$ 是通过给 $Q_1$ 增加一条 $y\rightarrow z$ 的边得到的，所以 $Q_1$ 到 $Q_1'$ 有一条边。

注

对于第 $i$ 层的 $\varphi=Q[\bar{x}](X \rightarrow l)$ ，长度 $\left|X\right|$ 最大为 $J=i \left|\Gamma\right| ( \left|\Gamma\right| + 1)$ ，其中 $\Gamma$ 由 $G$ 中的属性组成。

当验证 $G\models Q[\bar{x}](X \rightarrow l)$ 时，水平扩展终止。
当 $supp(Q,G) < \sigma$ 时，垂直扩展终止。

这两条策略可以保证 GFDs 发现在实际应用时的可行性。

引理 4

对于一个支持度高于 $\sigma$ 的 GFDs 覆盖集 $\Sigma_c$ ：

$\Sigma_c$ 不包含任何的平凡 GFD。
对于任意的 $\varphi =Q[\bar{x}](X \rightarrow l)$ ，如果 $G\models \varphi$ ，则 $\Sigma_c$ 不包含 $\varphi'=Q[\bar{x}](X'\rightarrow l)$ 如果 $X\not \subseteq X$ 。
如果一个 GFD $\varphi =Q[\bar{x}](X \rightarrow l)$ 满足支持度 $supp(Q,G)<\sigma$ ，则 $\Sigma_c$ 不包含 $\varphi'=Q[\bar{x}](X'\rightarrow l)$ 如果 $Q\ll Q'$ 。