Discovering Frequent Subgraphs over Uncertain Graph Databases under Probabilistic Semantics
-
Zhaonian Zou, Hong Gao, Jianzhong Li
-
KDD 2010
概要
-
Uncertain graphs上の頻出グラフマイニング
-
$$\Pr [\{G_1, \ldots, G_n\}$$の$$\phi$$割合以上出現$$] \geq \tau$$な部分グラフを探す
-
例のごとく失敗確率δを与える
-
実験したら良さ気
動機付け等
問題定義
-
入力: $$ \mathcal{D} = \{G_1, \ldots, G_n\}, \phi, \tau $$
-
出力: 全て$$(\phi, \tau)$$-確率的頻出部分グラフ
-
「Pr[Dのある具現化においてサポート≧φ]≧τ」なグラフ
提案手法
-
基本的に探索
-
(よく知らないけど)よく見るminimum DFS codesを利用して(多分)探索の重複を避けたりしてる
-
補題1「ある種の単調性が成立」なので、まぁ簡単
-
部分グラフの検証
-
Pr(S) := Sのφ-頻出確率の計算
-
$$ \Pr(S) \in [p_l, p_u] $$な範囲で計算
-
$$ p_l \geq \tau - \epsilon \wedge p_u \geq \tau $$
-
$$ p_u < \tau $$
$$\phi$$-頻出確率の計算
-
DP
-
何割出現したかが知りたいので、CIKM'09を直接は使えない
-
T[i,j,k] := k個のグラフにおいて、i個と同型、j個と同型となる確率
-
再帰で頑張る
-
Pr(S)は上を使って適当にループ(DP)すればOK
-
近似計算
-
結局「DNF数え上げ」を近似で解く
-
あとはゴチャゴチャと目的のものを求める+禁じ保証を与える
-
計算量がすさまじいことになっている
実験
-
データセット
-
生物学関係: BioGRID, STRING
-
頂点がタンパク質、辺が相互作用、辺確率が何か存在確率があるらしい(相互作用の観測結果とかだろうか)
-
時間 vs. $$\phi, \tau, \epsilon, \delta$$: εが一番ヤバメ
-
適合率(precision)、再現率(recall) vs. $$\epsilon, \delta$$: 割りと高そう>90%
まとめ
-
やっぱり速度がやばい
-
現時点(2016年)でもあんまり変わって無さそう…
-
方針は変えられない…?
-
$$ \Pr[S \sqsubseteq_{\mathrm{U}} G] $$の計算の効率化は?
KDD uncertain graphs 頻出グラフ
2016/04/22
最終更新:2016年04月22日 14:10