Efficient Subgraph Search over Large Uncertain Graphs - todo314 @ ウィキ

Efficient Subgraph Search over Large Uncertain Graphs

• Ye Yuan, Guoren Wang, Haixun Wang, Lei Chen
• VLDB 2011

概要

• 閾値以上の確率でクエリが部分グラフ同型となるデータベース中のグラフをとってくる問題
• 基本的な方針に加えて、様々な確率的要素を考慮した枝刈り手法を提案
• 実験したらやったでおい

問題設定

• 入力: $$ D = \{\mathcal{G}_1, \ldots, \mathcal{G}_n\}, Q, \epsilon $$
• 出力: $$ \mathcal{G} \in \mathcal{D} \text{ s.t. } \Pr_{G \sim \mathcal{G}}[Q \subseteq G] \geq \epsilon $$

提案手法

• 愚直な手法: $$ \Pr[Q \subseteq \mathcal{G}_i] $$をそれぞれ計算、しかしやばお

構造的枝刈り

• 辺確率を除いた（1にした）グラフで部分グラフ同型でなければ枝刈り
  • 部分グラフ同型性判定は既存手法でがんばりゅ

確率的枝刈り

• Dから何か特徴集合Fを作る
• 各fについて<fを含むグラフ, fを含むその確率>を記録
• 枝刈り1: $$ \exists f \in F \text{ s.t } Q \supseteq f, \Pr[f \subseteq \mathcal{G}] < \epsilon $$なら、$$\mathcal{G}$$は刈れる
  • $$ \because \Pr[Q \subseteq \mathcal{G}] \leq \Pr[f \subseteq \mathcal{G}] < \epsilon $$
• 枝刈り2: $$ \exists f \in F \text{ s.t } Q \subseteq f, \Pr[f \subseteq \mathcal{G}] \geq \epsilon $$なら、$$\mathcal{G}$$は最終的な解に含まれる
  • $$ \because \Pr[Q \subseteq \mathcal{G}] \geq \Pr[f \subseteq \mathcal{G}] \geq \epsilon $$

Fの作り方

• クエリログΓがあるとする
• クエリQに対する特徴集合Fの貢献度を考える: (Fによる確率枝刈りで省けるグラフの個数)-|F|
• クエリログ全体に関する貢献度の和を最大化したい
• ぶっちゃけMaximum Coverageっしょ？！
• 適当に近似計算

検証

• ここまで残ったやつについては確率を計算しないといけない
• 包除原理をするが、計算途中で枝刈りが出来ることもある（省略）

実験

• AIDS antiviral screen、STRING: 前者は不確実性を適当に生成
• 基本的には、枝刈り入れたらめっちゃ速くなりましたおという主張

まとめ

• はい
• これはこうするしかないのかもしれんが、問題設定がこれで良いんだろうか？
• もっとマイニング的問題の方がやる気が出そう…

VLDB uncertain graphs 部分グラフ検索

2017/01/04