Frequent Subgraph Pattern Mining on Uncertain Graph Data
-
Zhaonian Zou, Jianzhong Li, Hong Gao, Shuo Zhang
-
CIKM 2009
概要
-
部分グラフをパターンマイニングをしたい
-
期待サポートという新しい尺度を提案
-
これが高い部分グラフを探す近似アルゴリズムを作ったよ
問題定義
-
期待サポート
-
不確実グラフのデータベース(というか集合)Dの,実体化全体を考える
-
各実体化について,部分グラフSのサポート=(#{Sが出現する実体化中のグラフ}/|D|)をとる
-
入力: 不確実グラフの集合D,閾値θ
-
出力: 期待サポート≧θの部分グラフパターン
-
自明に分かること
-
D中の各不確実グラフGiについてSの出現する確率を考えれば良い
-
$$ \frac{1}{|D|}\sum_{i} \Pr[S \sqsubseteq_U G_i] $$
提案手法
-
目標
-
$$ [0, (1-\epsilon)\theta) $$: 入れない
-
$$ [(1-\epsilon)\theta, \theta) $$: 入っちゃうかも?
-
$$ [\theta, 1] $$: 見逃さない
-
上界・下界を計算してその場で判定
-
上界≧θ AND 下界≧(1-ε)θ: OK
-
上界<θ: NG
-
上界≧θ AND 下界<(1-ε)θ: ?
-
こういうことが無いように,上界-下界がεθに収まるように推定する
探索アルゴリズム
-
一般的なDFSで,一辺ずつ増やしていく
-
キューから取り出したら:
-
上界・下界を計算
-
枝刈り or 出力+子生成
期待サポートの近似計算
主なテク
-
$$ \Pr[S \sqsubseteq_U G] $$を厳密に計算したい
-
Gを普通のグラフだと思ってsubgraph isomorphismなところを全計算
-
各辺集合を$$ S_1, \ldots, S_\ell $$とすると,
-
$$ \Pr[S \sqsubseteq_U G]= $$($$S_1$$が全部生)∨…∨($$S_\ell$$が全部生)
-
DNF countingになる
厳密計算
-
包除原理すれば,$$ O(2^{\ell}) $$時間とかでできる
-
全体では$$ \Theta(2^{\ell-1}\ell |E(S)|) $$
近似計算
-
各Giについて,ギャップが≦εθとなるように,$$ [l_i, u_i] $$を計算する
-
そうすると,全体の和$$ [\bar{l}, \bar{u}] $$がギャップ≦εθで嬉しいから
-
有名なFPRASアルゴリズムで近似するよ
トレードオフ
-
近似より厳密の方が速いことが有るので,その場で比べて速い方を使う
実験
-
基本的にグラフは小さい: |E|<10K
-
計算時間: θ,ε,δが小さいと結構時間食う(30分とかそのくらい)
-
近似の質
-
precision: ε下げると上がる(あやふやな所もちゃんと省くから)
-
recall: δ下げるといくから上がる(期待サポートのミス推定が減るから)
-
割りと簡単に95%くらいまであげられるっぽい
-
スケーラビリティ: よくわかんないけど線形
-
不確実性の影響: 確率を適当な線形関数で上げた時の変化を見る(出力サイズが変わるの遅くなるのはしゃーない)
まとめ
-
探索はベーシック
-
近似がMonte-CarloじゃなくてImportance samplingの奴(だと思う)なのでちょっとおもしろい
-
Sを全部バーっと計算するのは得策じゃない気がする
-
全部やらずに上限・下限できませんか?そうじゃないともっとデカイグラフで全然動かない
最終更新:2016年01月30日 19:20