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

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

1. 满足性问题(Satisfiable)

   是否存在一个图数据, 能满足所有GFDs.

   1. GFDs不存在冲突.
   2. 至少一个GFD是可以用在非空图数据上的.

2. 蕴含问题(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)$, 明显第二个可以推出前一个, 所以第一个是多余的.

3. 验证问题(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是

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

6.1 Reduced GFDs and GFD Cover

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

6.1.1 不平凡的GFDs(Nontrivial GFDs)

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

1. $X$恒等于$false$, 即永远不可能被满足
2. $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$的一个子集, 满足:

1. $G \models \Sigma_c$
2. $\Sigma_c \equiv \Sigma$
3. $\Sigma_c$中的所有GFD都是最小的
4. $\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通过增加一步垂直扩展或水平扩展所变成的负GFDs, 则负的GFDs 的支持度定义为:

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

1. 若$X= \emptyset$, $\emptyset'$由模式$Q'$组成, 这些模式$Q'$有相同的轴$z$使得$supp(Q',G) > 0$, 且$Q'$是通过去除$Q$的边(也有可能是节点)得到的
2. 若$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指出, 不存在的数据不能作为知识库中的反例.

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

6.3 The Discovery Problems

我们将GFDs的挖掘问题表述为:

• 输入: 一个图$G$, 一个自然数$k \ge 2$和一个支持度阈值$\sigma > 0$
• 输出: 一个$supp(\varphi, G) \ge \sigma$, k-bounded最小GFDs$\varphi$的覆盖集$\Sigma_c$

验证问题和蕴含问题被包含在GFD的挖掘过程中, 对应步骤: 检查$G \models \varphi$和计算一个k-bounded GFDs$\varphi$的覆盖集$\Sigma_c$

我们使用$k$这个参数来平衡挖掘过程和对GFDs解释的复杂性. 因为显然地:

1. 如果GFDs拥有太多属性则不太可能频繁, 并且也很难跟终端用户进行解释
2. $k$过大的时候计算复杂度过高, 验证问题和蕴含问题是当$k$是固定的时候是PTIME的

工程实践经验

真实的数据分析中我们会精心挑选参与计算的属性, 我们通常会选择属性集合$\Gamma$.
$\Gamma$通常是我们最感兴趣的属性或者是我们认为最"干净"的, 可信任度最高的数据.