Frequent Subgraph Pattern Mining on Uncertain Graph Data

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] $$: 見逃さない
  • 上界・下界を計算してその場で判定
  1. 上界≧θ AND 下界≧(1-ε)θ: OK
  2. 上界<θ: NG
  3. 上界≧θ 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