挖掘问题

约 2263 字大约 8 分钟

2023-11-08

固定参数的易解性（FIXED PARAMETER TRACTABILITY）

我们重新回顾 GFDs 的三个关键问题：

满足性问题（Satisfiable）。
是否存在一个图数据，能满足所有 GFDs。
- GFDs 不存在冲突。
- 至少一个 GFD 是可以用在非空图数据上的。
蕴含问题（Implication）。
判断一个 GFD 是否能被一个 GFDs 的集合推导出来。对于判断多余的 GFDs 来说很有必要。
比如： $Q[x,y,z](x.A=y.B \wedge x.C=z.D \rightarrow L)$ 和 $Q[x,y,z](x.A=y.B \rightarrow L)$ ，明显第二个可以推出前一个，所以第一个是多余的。
验证问题（Validation）。
判断一个 GFDs 集合能否满足一个特定的图数据 $G$ 。
和满足性问题的区别在于此处的 $G$ 是给定的，而满足性问题里面的 $G$ 是任意的，存在即可。

提示

satisfiablilty，implication 和 validation 三个问题分别是 coNP-complete，NP-complete 以及 coNP-complete 问题。

对于一个可以参数化的问题 $P$ 是一对 $(x, k)$ ，其中 $x$ 在传统的复杂性理论中表示输入， $k$ 是表征 $x$ 结构的参数。固定参数的易解性是指：当存在一个函数 $f$ 和一个算法可以在 $O(f(k)\cdot {\lvert x \rvert}^c)$ 的时间内计算出任意一个 $(x, k)$ 实例，其中 $c$ 是一个常量。显然，当 $k$ 的值比较小的时候，我们是可以有效地计算出问题的答案的，虽然 $f(k)$ 本身可能是指数增长的。

工程实践经验

事实上工程中 $k$ 都较大，所以计算复杂度非常高，需要额外的剪枝策略来提高计算效率。

对于一个集合的 GFDs $\Sigma$ ，我们使用 $k$ 来表示 $Q$ 中 $\bar{x}$ 的向量长度，即 $max(\lvert \bar{x} \rvert)$ ，我们可以将蕴含问题用 $k$ 表示为：

输入：一个 GFDs 的集合 $\Sigma$ 和一个 GFD $\varphi$ 。
参数： $k=max\{ \lvert \bar{x} \rvert \ | \ Q[\bar{x}](X \rightarrow Y) \in \Sigma \cup \{\varphi \} \}$ 。
问题： $\Sigma \models \varphi$ 是否成立？

k-bounded GFDs

模式 $Q[\bar{x}]$ 是 k-bounded 当其满足 $\lvert \bar{x} \rvert \le k$ ， $k$ 是一个常量。

当其中所有的 $Q[\bar{x}](X\rightarrow Y)$ 中的 $Q[\bar{x}]$ 都是 k-bounded 时，一个 GFDs 的集合 $\Sigma$ 是 k-bounded。

挖掘问题（THE DISCOVERY PROBLEM）

给定一个图 $G$ ，挖掘目标为找到一个 GFDs 的集合 $\Sigma$ ，使得 $G \models \Sigma$ 。

当然，我们并不希望计算出所有的 GFDs，因为中间有很多平凡的和重复的 GFD。我们希望计算出的 GFDs 是：

没有平凡的和多余的 GFD。
是频繁的规律和约束。

Reduced GFDs and GFD Cover

我们先来定义一下不平凡和简化的 GFDs。

不平凡的 GFDs（Nontrivial GFDs）
一个 GFD $\varphi = Q[\bar{x}](X \rightarrow l)$ 是平凡的有两种情况：
1. $X$ 恒等于 $false$ ，即永远不可能被满足。
2. $l$ 可以被 $X$ 使用恒等变换推导出来。
简化的GFD（Reduced GFD）
reduced pattern
给定一个模式 $Q[\bar{x}](V_Q, E_Q, L_Q, \mu)$ 和 $Q'[\bar{x}'](V_Q',E_Q',L_Q',\mu')$ ，如果 $Q$ 是通过 $Q'$ 减少点（或者边）亦或者是将 $Q'$ 中的一些 label 变为通配符得到的，那么我们称 $Q$ 简化了 $Q'$ ，记作 $Q[\bar{x}] \ll Q'[\bar{x}']$ 。这意味着 $Q$ 是 $Q'$ 拓扑结构相同，但是约束更少的版本。
pivot
在一个图模式 $Q[\bar{x}]$ 中，指定一个变量 $z \in \bar{x}$ 并将其指定为 $Q$ 的 $pivot$ 。我们使用 $pivot$ 来探讨子图同构问题的数据局部性。对于 $G$ 中任意的 $v$ ，如果存在 $h$ 使得 $h(z)=v$ ，则 $h(\bar{x})$ 只包含 $d_Q$ 跳以内的点。其中 $d_Q$ 我们称之为 $Q$ 的半径，即 $z$ 到 $Q$ 中任意点的最长的最短路径（the longest shortest path）。
在工程实践中， $pivot$ 一般配置为用户最感兴趣的点。
如果不清楚最长的最短路径的定义，可以查看：longest-shortest-path-in-an-undirected-unweighted-graph。
结论：如果 $\varphi_1=Q_1[\bar{x_1}](X_1\rightarrow l_1)$ ， $\varphi_2=Q_2[\bar{x_2}](X_2\rightarrow l_2)$ 。显然，当 $Q_1 \ll Q_2$ 并且 $X_1 \ll X_2$ 时， $\varphi_1 \ll \varphi_2$ 。

GFDs 的覆盖（Cover of GFDs）

当所有的 $\varphi \in\Sigma, \Sigma \not\equiv \Sigma \verb|\| \{\varphi\}$ ，即 $\Sigma$ 不包含任何多余的 GFDs 的时候，我们称 $\Sigma$ 是 $minimal$ （最小的）。

图 $G$ 上 $\Sigma$ 的一个覆盖集合 $\Sigma_c$ 是一个 $\Sigma$ 的一个子集，满足：

$G \models \Sigma_c$ 。
$\Sigma_c \equiv \Sigma$ 。
$\Sigma_c$ 中的所有 GFD 都是最小的。
$\Sigma_c$ 本身是最小的。

这说明 $\Sigma_c$ 不包含任何无趣的多余的 GFDs。

频繁的 GFDs（Frequent GFDs）

support 的传统定义

对于 GFD $\varphi = Q[\bar{x}](X \rightarrow) Y$ ， $\varphi$ 的 $surport$ 为 $Q$ 在 $G$ 中匹配并满足 $X \rightarrow Y$ 的数量。

但是这个定义并不是反单调性的。例如 $Q[\bar{x}]$ 表示一个点 $person$ ， $Q'[x,y]$ 表示一个边从 $person \, x$ 到 $person \, y$ ，label 是 $hasChild$ 。在现实生活中，我们会发现即便 $Q$ 是 $Q'$ 的一个子集， $Q'$ 的数量是远远大于 $Q$ 的数量的，因为一个人可能有多个孩子。

我们会发现，当我们的限制增多了之后，匹配的数量不仅没有减少，反而增多了。

为此，我们给出新的定义：

Pattern support（模式支持度）

对于一个图 $G$ ，和一个正向 GFD $\varphi$ 拥有模式 $Q[\bar{x}]$ ，其中 $Q$ 有 $pivot \, z$ 。用 $Q(G,z)$ 表示由 $h(z)$ 推导出来的匹配 $z$ 的节点的集合，其中 $h(z)$ 是 $Q$ 在 $G$ 中所有的匹配。

模式 $Q$ 的 support：

supp(Q, G)=\left| Q(G,z)\right|

这个公式量化了实体在 $G$ 中满足拓扑结构 $Q$ 且以 $z$ 为 $pivot$ 的频繁程度。

pivot 的作用

为了 GFDs support 的反单调性，我们在上述的定义中引入了 $pivot$ 的概念。反单调性允许我们沿着与传统数据挖掘相同的路线加速挖掘过程。

为了量化在 $Q[\bar{x}]$ 中属性的依赖程度，我们定义 $correlation \, \rho(\varphi, G)$ 如下：

Correlation measure（相关度）

$\rho(\varphi,G)=\frac{\left| Q(G,Xl,z)\right|}{\left|Q(G,z)\right|}$

这里的 $Q(G,Xl,z)$ 表示 $Q(G,z)$ 的子集以至于 $h(\bar{x})\models X$ 并且 $h(\bar{x})\models l$ （前文曾提到过： $\varphi=Q[\bar{x}](X\rightarrow l)$ ）。

正向 GFDs 的支持度

$\varphi$ 的支持度定义为： $supp(\varphi,G)=supp(Q,G)*\rho(\varphi,G)=\left| Q(G,Xl,z) \right|$ 。

定理 3

对于任何图 $G$ 和非平凡的正向 GFDs $\varphi_1$ 和 $\varphi_2$ ，如果 $\varphi_1 \ll \varphi_2$ 则 $supp(\varphi_1,G) \ge supp(\varphi_2,G)$ 。

负向 GFDs 的支持度

由于负的 GFDs 无法被满足，所以无论如何都有 $Q(G,Xl,z) = \emptyset$ ，则不再使用 $Q(G,Xl,z) = \emptyset$ 来定义负的 GFDs 的支持度。

现实生活中只关心有正向 GFDs 通过增加一步垂直扩展或水平扩展所变成的负 GFDs，则负的 GFDs 的支持度定义为：

supp(\varphi,G)=max_{\varphi' \in \Phi'}(supp(\varphi',G))

若 $X= \emptyset$ ， $\emptyset'$ 由模式 $Q'$ 组成，这些模式 $Q'$ 有相同的轴 $z$ 使得 $supp(Q',G) > 0$ ，且 $Q'$ 是通过去除 $Q$ 的边（也有可能是节点）得到的。
若 $X \neq \emptyset$ ， $\emptyset'$ 由正的 GFDs $\Phi'$ 组成，这些 GFDs 有相同的 $pivot \ z$ 使得 $G\models \varphi'$ ， $X$ 中存在字段 $l'$ 使得 $X=X'\cup \{l'\}$ 。