DGFD论文笔记(一)
2105字约7分钟
大数据算法图
2023-10-31
论文原文: Discovering Graph Functional Dependencies
其中涉及到的一些非常重要的基本概念, 在Functional Dependencies for Graphs论文中有详细阐述.
本论文是樊文飞院士图计算理论中非常重要的一环, 也是钓鱼城数据挖掘系统的主要参考论文之一. 接下来我将提取该论文中的主要论点和推理, 并结合实际的工程实现和项目经验(应该会单独写一篇博客)阐述个人一部分的理解. 中间有理解不到位的地方, 希望各位大佬及时指正.
本章节会对论文的工作和基础概念进行梳理, 会有部分内容是论文的翻译, 我会对翻译部分和我自己的理解部分分别进行标识. 翻译部分如果有表达不通顺的地方, 请大家谅解.
1. 摘要 翻译
本文研究了GFDs的发现, GFDs是一类在图上定义的函数依赖关系. 我们研究了与GFD发现相关的三个基本问题的固定参数的可处理性. 我们表明, 隐含和满足性问题是固定参数的, 但验证问题是co-W困难的. 我们引入了减少GFD(reduced GFD)及其拓扑支持度的概念, 并形式化了GFD的发现问题. 我们开发了用于发现GFD并计算其集合(covers)的算法. 此外, 我们通过提供用于发现GFD的并行可扩展算法来证明GFD发现在大规模图上是可行的, 这些算法保证在使用更多处理器时减少运行时间. 使用现实生活和合成数据, 我们通过实验验证了算法的有效性和可扩展性.
关键词: GFD发现, 并行扫描, 固定参数易解性
2. 文章的主要贡献以及相关工作
2.1 贡献
- 研究了三个GFD挖掘相关的基础问题.
- 满足性问题: 决定GFDs是否是"脏"的, 即GFDs有一个模型.
- 蕴含问题: 决定GFD挖掘是否是"多余的".
- 验证性问题: 是为了确保从图 G 中挖掘的 GFD 满足 G.
- 形式化了GFDs的挖掘过程.
- 开发了一个时间顺序的GFDs的挖掘算法.
- 我们开发了一种并行算法, 用于在分裂的图中发现GFDs.
- 使用生活中的数据和构造数据, 我们评估了算法.
2.2 相关工作
- 图的FDs
- 依赖发现
- 图模式最小化
3. 挖掘目标
我们先来看一下, 通过算法我们最终会得到一个什么样的结果以及这个结果有什么含义.
上面是3个论文中给出的GFD的例子, 其中φ1,φ2,φ3就是我们最后算法得到的结果.
- GFD φ1=Q1[x,y](y.type=′′film′′→x.type=′′producer′′). 其中Q1在图中已经展示, x和y是两个变量表示Q1中的两个点, 每个点拥有一个属性type(图中并没有显示). φ1表示在图中如果任意子图的拓扑结构与Q1是同构的, 且标签为product的点y拥有属性type="film", 那么标签为person的点的属性type就会是"producer".
- GFD φ2=Q2[x,y,z](ϕ→y.name=z.name). 该规则表明如果city x位于y和z则y和z必须是同一个地点. 注意: y和z的label是通配符"_", 所以可以同时匹配图G2中的country和city两种label.
- GFD φ3=Q3[x,y](ϕ→false). 该规则表明没有任何两个人可以互为对方的父母, 即Q3是一个"非法"的结构.
4. GFD相关概念解释
4.1 基础概念
4.1.1 图(Graph)
一个有向图G=(V,E,L,FA)
- V 表示实体点(后文中简称"点")的有限集合
- E⊆V×V 表示实体关系(后文中简称"边"), 其中(v,v′) 是点 v 到点 v′ 的边
- L 表示label(点或边的标识, 可以理解为名字).每一个点v∈V都会属于一个label: L(v)∈Θ, 每一个边e∈E都会属于一个label: L(E)∈Θ
- 对于每一个点v, FA(v)是一个元组(A1=a1,...,An=an), 其中ai是一个约束, Ai是点v 的一个属性, 写作v.Ai=ai (即, 实体点v的属性Ai的具体值为ai). 并且当i=j时Ai=Aj.
4.1.2 图模式(Graph patterns)
一个图模式是一个图Q[xˉ]=(VQ,EQ,LQ,μ)
- VQ(resp. EQ)是一个点(resp. 边)模式的集合
- LQ是一个函数, 为每一个点u∈VQ(resp. 边e∈EQ)分配一个label LQ(u)(resp. LQ(e)). 我们允许LQ(u)和LQ(e)使用通配符'_'.
- xˉ是一系列的变量(a list of variables)
- μ 是一个从xˉ到VQ的双射映射, 它为VQ中的每个节点v分配一个不同的变量. 对于x∈xˉ, 当语义确定的时候, 我们会等价地使用μ(x)和x
4.1.3 图模式匹配(Pattern matching)
对于标签 l 和 l′, 如果l∈Θ并且l′是'_', 我们写作l≺l′. 如果l≺l′或者l=l′则我们写作l⪯l′.
模式Q在图G中"匹配(match)"是指一个G的一个子图G′=(V′,E′,L′,FA′)与Q是同构的. 即存在一个VQ到V′的双向映射函数h, h满足:
- 对于每一个点u∈VQ, L′(h(u))⪯LQ(u)
- e=(u,u′)是一个Q中的边, 当且仅当e′=(h(u),h(u′))是G′中的一条边并且L′(E′)⪯LQ(e)
4.2 图中的函数依赖(Functional Depandecies for Graphs)
一个图的函数依赖(GFD)写作 Q[xˉ](X→Y), 其中:
- Q[xˉ]是一个图模式, 被称为φ模式.
- X和Y是xˉ的两个(可能是空的)属性的集合.
显然, φ 是两个约束的组合:
- 模式Q约束的拓扑结构
- X→Y指定的属性依赖关系
这里 Q 指定了 φ 的范围, 使得 X→Y 只强加给 Q 的匹配项
4.2.1 语义表述(Semantics)
当h(xˉ)满足其集合X中所有属性约束, 我们记作 h(xˉ)⊨X. 如果 h(xˉ)⊨X 可以推出 $h(\bar{x}) \models Y $, 我们记作 h(xˉ)⊨X→Y.
一个图G满足GFD φ, 表示为 G⊨φ, 如果Q的所有h(xˉ)都在G中找到匹配, h(xˉ)⊨X→Y. 图G满足一个集合Σ的GFDs, 记作 G⊨Σ, 如果所有的 φ∈Σ,G⊨φ.
想要得知是否G⊨Σ, 我们需要检查Q在G中的所有匹配. 更多的, 我们考虑无模式图, 所以:
- 对于X中的x.A=c, 如果h(x)没有属性A, 则h(xˉ)满足X→Y. 确实, 点 h(x)并不需要拥有属性A因为图没有模式. 相反的, 如果x.A=c在Y中并且h(xˉ)⊨Y, 则根据满足性定义h(x)必须拥有属性A. 对于x.A=Y.b来说也是一样的.
- 当X是ϕ时, 对于Q的任意匹配h(xˉ)都有h(xˉ)⊨X. 当Y=ϕ时, Y始终为真, φ是平凡的.
显然, 如果一个Q的匹配h(xˉ)在G中违反X→Y, 例如 h(xˉ)⊨X但是h(xˉ)⊨Y, 则由h(xˉ)导致的子图不一致, 例如它的实体点有不一致性.
4.2.2 正向和负向(Positive and negative)
只有两种GFDs φ是负向的:
- 当X=ϕ时, 即φ具有形式Q[xˉ](ϕ→false). 这表明图模式就是不合理的.
- 当X=ϕ时, 图模式和属性结合是不一致的. Figure 1中φ1和φ2是positive, φ3是negative. 因为图模式本身不合理.