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

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

1. 满足性问题 ( Satisfiable ) 。

   是否存在一个图数据，能满足所有 GFDs。

   • GFDs 不存在冲突。
   • 至少一个 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。

挖掘问题 ( THE DISCOVERY PROBLEM )

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

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

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

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}'（在新窗口打开） $，如果 $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 ))$$

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$ 是频繁的。

OWA

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

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

挖掘问题

我们将 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$ 通常是我们最感兴趣的属性或者是我们认为最"干净"的，可信任度最高的数据。

贡献者

dingyuqi

更新日志

2025/10/11 02:26

查看所有更新日志

• 941fa-feat(theme): upgrade and use collections于 2025/10/11
• eb6eb-improve(docs): use pangu formatter于 2025/8/5
• 2185e-improve(docs): use chinese punctuation于 2025/3/6
• fea7c-improve(docs): delete extra whitespace and blank lines于 2025/1/21
• c1c02-modify(docs): remanage folders and rename files于 2024/12/17
• d3d20-docs: add icon于 2024/11/22
• d5800-docs: update docs于 2024/11/21

版权所有

版权归属：dingyuqi

许可证：署名-非商业性-禁止演绎 4.0 国际 (CC-BY-NC-ND-4.0)

编辑此页