概率意义下不确定图的频繁子图挖掘 notes
几个基本概念
l 不确定图：一个边的存在性和点得存在性都被赋予了概率值的图
l Support of (S): 图集合D中包含特定图S的图的比例
l Frequent定义：一个图S是frequent的，需满足：support(S) ≥ϕ
l ϕ-frequent probability: 某特定图S是不确定图集合D中的图的子图的比例≥ϕ的概率，即
Pr(support(S) ≥ϕ)
l 问题定义：
给定一个不确定图集合D和0< ϕ, τ<1，找到所有的图S，S满足：
Pr(support(S) ≥ϕ) ≥τ
l 所有子图都只考虑联通的
l Labeled graph：每个点都给予标记，当做不同的点，对于一个n个点得标记图，可能存在2^(n*(n-1)/2)中构造。
l #P-hard：http://www.jiahenglu.net/blog/5.html此文介绍的不错，作者是人大的一个大牛貌似，再就是wikipedia了.NP问题常常是问有没有，而#P是问有多少，所以#P更复杂。引用一句“#P-complete 问题在不确定数据管理需要计算概率的时候是非常常见的”
Introduction
l 一个不确定图G，它可以被看做一个随机变量，有很多可能取值，这些值得类型就是确定图。所以G在这些可能取值的确定图的集合上就有一个概率分布(probability distribution)。
l 在上一篇Dr.Zou的论文中讨论的是expected support(S)
l 近期有许多不确定itemset的挖掘算法，但是在针对某个item判断是否frequent的问题上，是可以多项式时间完成，但是计算某个graph的ϕ-frequent probability却是#P-hard的。
算法基本流程与思想
l 想要找到所有Pr(support(S) ≥ϕ) ≥τ的图，就找到所有可能的子图S，挨个判断它是否满足Pr(support(S) ≥ϕ) ≥τ，这个枚举所有图的过程就用那个minimum DFS code tree来做就可以。判断某图是否Pr(support(S) ≥ϕ) ≥τ过程由于是#P-hard，所以找一个渐进算法来干掉它。
l 这个渐进算法能做到如下程度：
n 找到所有Pr(support(S) ≥ϕ) ≥τ的子图
n 同时容忍混入一些τ-ε≤Pr(support(S) ≥ϕ) <τ的子图
主要贡献
l 定义了概率semantics下的不确定图挖掘问题
l 华丽丽的证明了挖掘问题是NP-hard的，计算一个子图的ϕ-frequent probability是#P-hard的
l 提出了一个有一定失败几率的渐进算法
l 讨论了那个容错参数如何设置比较好
一些定义以及前期分析
l 一个不确定图\[G = (V,E,\sum {} ,{L_V},{L_E},{P_v},{P_E})\] implicates出某一个确定图\[{G^'} = ({V^'},{E^'},{\sum {} ^'},{L^'}_V,{L^'}_E)\]的概率是
.\(\begin{array}{l}\Pr (G \Rightarrow {G^'}) = (\prod\limits_{v \in V'} {{P_V}(v)} ) \bullet (\prod\limits_{v \in V\backslash {V^'}} {(1 - {P_V}(v))} )\\ \bullet (\prod\limits_{e = (u,v) \in E'} {{P_E}(e|u,v)} ) \bullet (\prod\limits_{e = (u,v) \in E \cap ({V^'} \times {V^'})\backslash {E^'}} {(1 - {P_E}(e|u,v))} )\end{array}\). (1)
也就是存在的边的存在概率积、不存在的边的不存在概率积、存在的点的存在概率积和不存在的点的不存在概率积的乘积，非常直观。
IMP(G)是不确定图G implacte出的所有确定图的集合。集合元素数目为
.\(|{\mathop{\rm Im}\nolimits} p(G) = O(\sum\limits_{i = 1}^{|V|} {C_{|V|}^i{2^{i*(i - 1)/2}}} )|\). (2)
公式(1)就是G在集合Imp(G)上的概率分布。
l 不确定图集合\[D = \{ {G_1},{G_2}......{G_n}\} \]implicates确定图\[{D^'} = \{ {G^'}_1,{G^'}_2......{G^'}_m\} \]，其中，这是因为有些图G映射成空图了，所以还需要一个映射injection \(\sigma :\{ 1,2.....m\} \to \{ 1,2......n\} \)
l 一个不确定图的集合\[D = \{ {G_1},{G_2}......{G_n}\} \]implicates出一个确定图的集合\[{D^'} = \{ {G^'}_1,{G^'}_2......{G^'}_m\} \]的概率是
\[\begin{array}{l}\Pr (D \Rightarrow {D^'}) = (\prod\limits_{i \in \{ 1....m\} }^{} {\Pr ({G_{\sigma (i)}} \Rightarrow G_i^')} ) \bullet \\(\prod\limits_{i \in \{ 1....n\} \backslash \{ \sigma (x)|x \in \{ 1...m\} \} }^{} {\Pr ({G_i} \Rightarrow \emptyset ))} )\end{array}\]
Imp(D)相应就是D的implicate确定图集合的集合。
l 确定图之间的子图关系： 两个确定图\({G_1} = (V,E,\sum {} ,{L_V},{L_{_E}})\),\({G_2} = ({V^'},{E^'},{\sum {} ^'},{L^'}_V,{L^'}_{_E})\)，说\({G_1}\)is subgraph isomorphic to\({G_2}\)(G1是G2的子图)，即\({G_1} \triangleleft {G_2}\)，则需满足以下：
存在一个injection f: \(V \to {V^'}\)
(1)\({L_V}(v) = L_V^'(f(v))\) for any \(v \in V\)
(2)\((f(u),f(v)) \in {E^'}\) for any \((u,v) \in E\)
(3)\({L_E}((u,v)) = L_E^'((f(u),f(v)))\) for any \((u,v) \in E\)
l \(\varphi \)-frequent probability：这个就是说一个图S在不确定图数据库D中出现频率>的概率是多少，也就是
\(\Pr (\sup (SinD) \ge \varphi )\)
记为
\(\Pr (S;D,\varphi ) = \sum\limits_{{D^'} \in {\mathop{\rm Im}\nolimits} p(D),\sup (S;{D^'}) \ge \varphi } {\Pr (D \Rightarrow {D^'})} \)
上面已经说明了\(\Pr (D \Rightarrow {D^'})\)的求法，貌似只要挨个枚举S判断，问题就解决了，但是对于一个特定图S计算\(\Pr (S;D,\varphi )\)其实是#P-hard的。
l 证明：计算一个特定图S \(\Pr (S;D,\varphi )\)是#P-hard，计算D中频繁子图S数量也是#P-hard的
暂略
l 所以我们需要提出一个计算\(\Pr (S;D,\varphi )\)的Approximate挖掘算法
算法流程
l First，将D的所有子图都组织进一个DFS搜索树中，每个点都是D的一个子图，每个点都是它儿子节点的子图且都比儿子节点少一条边。
这些子图都是确定图，所以我们可以把它们编码成minimum DFS codes。树中其实有很多节点代表的是同一个图。在先序遍历DFS搜索树时，可以保证一个图的minimum DFS code是最先被访问到的，这个是跟code之间的序关系Lexicographic order of DFS codes有关。对于Parent(S)和S，有性质：Parent(S)的mDFS code是S的mDFS code的最长前缀。
l Second，DFS先序遍历树中每一个子图S，并且在多项式时间内判断S的-frequent probability>=是否成立。如果成立，继续搜索子节点，否则砍掉这个节点以及其所有子孙。
DFS过程，实际上并不如常规的那样先把树在内存中建好，然后顺着指针游走，而是在面对一个S时，通过DFS code的性质，就可以由S的minimum DFS code生成其子节点的DFS code，十分省空间。生成过程：1.对S用right-most extension获得了一个子图集合，其中每个元素都包含S，并且比S多一条边。2.对于集合中的子图S’，如果S的最小DFS code是S’的前缀，那么S’是S的儿子，否则不是。
判断过程：判断过程可以看出已经做了一个的让步了。对于每个S，预测它的Pr(S)，给出的不是一个精确结果，而是一个区间[pl,pu]，有\(\Pr (S) \in [{p_l},{p_u}]\)，并且\({p_{u - }}{p_l} \le \varepsilon \)
l 没有子图还没被发现的时候，停止算法
渐进算法
下面的问题就是如何对一个图S的Pr(sup(S)>= ϕ)给出一个区间的预测了。
如上面所说，算法对于每个S产生一个关于Pr(sup(S)>= ϕ)的区间[pl,pu]的预测，但是这个预测有最多\(0 < \delta < 1\)的失败可能，\(\delta \)是一个参数。
首先讲一个用指数级时间计算准确概率的DP算法，再找到这个DP算法之所以指数级的瓶颈点，在这个点上进行估算，让算法整体降下来复杂度。
l 首先定义一个概念——“确定图S在不确定图G中出现”，这个概念是说S至少是G可能存在的形态的一种，即S属于G implicate出的确定图集合的一个元素。符号为\(S{ \triangleleft _U}G\)
\(\Pr (S{ \triangleleft _U}G) = \sum\limits_{G' \in {\mathop{\rm Im}\nolimits} p(G),S \triangleleft {G^'}} {\Pr (G \Rightarrow {G^'})} \)【原文S写成S’了。。。】
现在我们设一个3维数组T[0..n,0..n,0..n]，T[i,j,k]表示在D中前k个不确定图中，S是i个非空图的子图，不是j个非空图的子图的概率。这样我们就能计算ϕ-frequent probability了：
\(\Pr (S) = \sum\limits_{i = 1}^n {\sum\limits_{j = 0}^{\min ((1 - \varphi )i/\varphi ,n - i)} {T[i,j,n]} } \)
对于\[\min ((1 - \varphi )i/\varphi ,n - i)\]，前者是为了保证i/(i+j)> ϕ，后者是保证i+j不会大于n，因为有的不确定图可能implicate成了空图或者和别的不确定图implicate出的图重了，所以i+j可能会小于n。
下面的问题就是利用DP算法计算T[i,j,n]，公式略，但是在计算过程中主要就是分情况讨论的思想，公式很直观，比较好理解。在计算过程中则用到了\(\Pr (S{ \triangleleft _U}G)\)，然而\(\Pr (S{ \triangleleft _U}G)\)的计算是#P-hard的，证明略，所以下面来近似计算\(\Pr (S{ \triangleleft _U}G)\)，如果能降低\(\Pr (S{ \triangleleft _U}G)\)的计算复杂度，因为DP是O(n^3)的，所以整体时间复杂度就降低了。
l \(\Pr (S{ \triangleleft _U}G)\)的渐进
蒙特卡洛方法可以用来估计一个DNF范式取真的概率，但是估计出来的有一个绝对误差值，同时还有一定概率不满足这个绝对误差值。而本处对\(\Pr (S{ \triangleleft _U}G)\)进行渐进。之后再用\(\Pr (S{ \triangleleft _U}G)\)去计算Pr(S)，所以Pr(S)的区间性和失败几率就是这么来的，下面开始讲述将\(\Pr (S{ \triangleleft _U}G)\)计算转化成构造一个DNF范式F，并通过随机独立的取真值指派开DNF范式的结果。对于不确定图G，我们去除G的不确定性，得到一个确定图G，在美剧S父节点的儿子节点时，S同构于G中的embeddings(即所有G中和S同构的部分)M1,M2……Mm都已经获得了。下面构建那个DNF F：
第一步：给{v|v属于(M1 V M2 V….VMm)}都指派一个独特的变量。这个变量取真的概率就是那个点存在的概率。
第二步：给{e|e属于(M1 V M2 V….VMm)}都指派一个独特的变量。这个变量取真的概率就是那个边存在的概率。
第三步：对于每一个Mi，构建一个clause Ci，由它的所有边和点得变量“取与”组成，代表Mi存在的意思。
第四步：F = C1 V C2 V C3 V……..V Cm，代表G中有S同构的部分存在的意思。
很显然能计算出Pr(F=True)就是\(\Pr (S{ \triangleleft _U}G)\)的值了。
而这个DNF范式用蒙特卡洛方法就可以进行估计，给一个\(0 < \delta ',\varepsilon ' < 1\)，蒙特卡洛可以给\(\Pr (S{ \triangleleft _U}G)\)一个估计 \(\Pr' (S{ \triangleleft _U}G)\)，满足：
\[|\Pr '(S{ \triangleleft _U}G) - \Pr (S{ \triangleleft _U}G) \ge \varepsilon '| \le \delta '\]
所以我们就可以按照如下计算出Pr(S)的估算区间[pl,pu]，误差\[{p_u} - {p_l} < \varepsilon ,0 < \varepsilon < 1\]，估算失败的概率是\(0 < \delta < 1\)
步骤一：计算\(\Pr ({G_i} \Rightarrow \emptyset )\)\(1 \le i \le n\) by 公式一(一劳永逸)
步骤二：估算\(\Pr (S{ \triangleleft _U}{G_i})\)，得到\(\Pr '(S{ \triangleleft _U}{G_i}),for1 \le i \le n\)，取\(\delta ' \ge {(1 - \delta )^{1/n}},\varepsilon ' = \frac{\varepsilon }{{2n}}\)，这样就可以保证计算Pr(S)的误差在\[{p_u} - {p_l} < \varepsilon ,0 < \varepsilon < 1\]，失败概率是\(0 < \delta < 1\)了
步骤三：现在到了用DP计算Pr(S)的估算区间的时候了~
步骤四：返回结果咯~\[{p_l} = \Pr '(S) - \varepsilon /2,{p_u} = \Pr '(S) + \varepsilon /2\]
所有算法完成，整体的思路总结：
首先利用DFS code tree的结构来逐渐用DFS先序遍历来枚举D={G1,G2…..Gn}中的每一个子图S，其中从父到子的过程是用rightmost extension完成DFS code转换的。
然后，对于每一个子图S，我们要判断S在G中出现频率大于ϕ的概率是否大于τ，即S是否是ϕ-frequent的，然而这个判断是#P难得，所以我们需要找一个渐进算法来计算这个问题。
首先先看一个可以在指数时间内解决判断问题的DP算法，发现主要是由于\(\Pr (S{ \triangleleft _U}G)\)值得计算式#P难得导致整体算法成了\(\Pr (S{ \triangleleft _U}G)\)#P-hard的了，于是可以想到如果能用渐进算法在多项式时间内解决了\(\Pr (S{ \triangleleft _U}G)\)的估算，也就能在多项式时间内解决的计算问题了ϕ-frequent概率的计算问题了。
\(\Pr (S{ \triangleleft _U}G)\)代表的是确定图S是不确定图G的子图的意思(满足S和至少G的一个子结构同构)，不难发现可以将这个问题转成一个DNF范式来表达。在枚举S的儿子时，我们得到了副产品——G去掉不确定性后图内所有与S同构的子图，这样可以发现只要这些子图任意存在一个，那么就有S是G的子图成立，而每个子图的存在依赖于它的边和点的存在，根据上述思想，很容易就可以写出DNF范式来表达S是G的子图了。
对于一个DNF范式为真的概率，可以用蒙特卡洛方法来估算，估算有一个绝对误差和超出绝对误差的概率。当我们估算完S是G子图的概率后，就可以利用DP算法来估算Pr(S)了，也就是可以判断每个S是否frequent了：）
7 Comments
Other Links to this Post
RSS feed for comments on this post. TrackBack URI
By 数字, October 29, 2011 @ 12:06 am
哥，你太强大了，算法好犀利呀。
By kinslover, October 29, 2011 @ 2:14 am
啥玩意。。。这论文又不是我写的。。。别人的论文做的笔记而已。。。
By 数字, October 29, 2011 @ 10:36 am
= = 知道不是哥哥写的（因为博文中出现了“原文”字样呀，哈哈），我就觉得哥哥能找到这么好的算法，就很犀利呀。
而且还研究的那么明白，最关键是博文中写的那么仔细。
By kinslover, October 29, 2011 @ 1:58 pm
T..T，作者是目前带我的老师，基本类似全文翻译了。。。省略了一些证明，原论文是Discovering Probabilistic Frequent Subgraphs over Uncertain Graph Databases。我如果能写出这个，现在就top 10稳妥了
By 数字, October 29, 2011 @ 6:39 pm
木事，哥哥加油。
CMU再向哥哥招手。
哥哥的老师好强大呀。
By kinslover, October 30, 2011 @ 1:48 am
别说CMU了，，，能有前30的Offer那都是神迹，奇迹发生了。。。
By 数字, November 4, 2011 @ 9:44 am
哥哥加油。。。