「Efficient Subgraph Search over Large Uncertain Graphs」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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 \mathcalG}] < \epsilon $$なら、$$\mathcalG}$$は刈れる
-- $$ \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 \mathcalG}] \geq \epsilon $$なら、$$\mathcalG}$$は最終的な解に含まれる
-- $$ \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: 前者は不確実性を適当に生成
- 基本的には、枝刈り入れたらめっちゃ速くなりましたおという主張
* まとめ
- はい
- これはこうするしかないのかもしれんが、問題設定がこれで良いんだろうか？
- もっとマイニング的問題の方がやる気が出そう…
&tags()
2017/01/04
* 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: 前者は不確実性を適当に生成
- 基本的には、枝刈り入れたらめっちゃ速くなりましたおという主張
* まとめ
- はい
- これはこうするしかないのかもしれんが、問題設定がこれで良いんだろうか？
- もっとマイニング的問題の方がやる気が出そう…
&tags()
2017/01/04
