挖掘问题

约 2338 字大约 8 分钟

2023-11-08

5. 固定参数的易解性(FIXED PARAMETER TRACTABILITY)

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

满足性问题(Satisfiable).
是否存在一个图数据, 能满足所有GFDs.
1. GFDs 不存在冲突.
2. 至少一个 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.

6. 挖掘问题(THE DISCOVERY PROBLEM)

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

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

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

6.1 Reduced GFDs and GFD Cover

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

6.1.1 不平凡的 GFDs(Nontrivial GFDs)

一个 GFD $\varphi = Q[\bar{x}](X \rightarrow l)$ 是平凡的有两种情况:

$X$ 恒等于 $false$ , 即永远不可能被满足.
$l$ 可以被 $X$ 使用恒等变换推导出来.

6.1.2 简化的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$ 一般配置为用户最感兴趣的点. 如果不清楚 the longest shortest path 的定义, 可以查看: 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$ .

6.1.3 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.

6.2 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)$ ).

6.2.1 Support of positive GFD $\varphi$

$\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)$ .

6.2.2 Support of negative GFDs

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

现实生活中只关心有正向 GFDs 通过增加一步垂直扩展或水平扩展所变成的负G FDs, 则负的 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'\}$ .

如果 $supp(\varphi,G) \ge \sigma$ , 其中 $\sigma$ 是一个支持度阈值, 则说 GFD $\varphi$ 是频繁的.

Open World Assumption(OWA)

OWA 指出, 不存在的数据不能作为知识库中的反例.

对于正的 GFD $\varphi$ , 其支持度量化了存在并符合 $\varphi$ 的实体.
对于负 GFD $\varphi$ , 其支持度由正 GFD $\varphi'$ 的支持度所决定. 也就是说, 负 GFDs 描述了观察世界中"不存在"的案例. 未知数据对负 GFDs 的发现没有影响.