Discovering Frequent Subgraphs over Uncertain Graph Databases under ... - todo314 @ ウィキ

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$$な部分グラフを探す
• 例のごとく失敗確率δを与える
• 実験したら良さ気

動機付け等

• Frequent Subgraph Pattern Mining on Uncertain Graph Dataは期待値（サポート）
• 期待値→構造パターン
• 確率(この研究)→特徴抽出
  • ほんとか？よくわからん

問題定義

• 入力: $$ \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] $$な範囲で計算
  1. $$ p_l \geq \tau - \epsilon \wedge p_u \geq \tau $$
     • 確実に≥τ-ε、多分≥τ、なのでSを出力
  2. $$ 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