Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases - todo314 @ ウィキ

Efficient Discovery of Frequent Subgraph Patterns in Uncertain Graph Databases

• Odysseas Papapetrou, Ekaterini Ioannou, Dimitrios Skoutas
• EDBT 2011

概要

• MUSEFrequent Subgraph Pattern Mining on Uncertain Graph Dataの高速化
• 期待頻度の推定とかの，基本は同じ
• ↑をしない色々な上限見積もりで枝刈りをする
• subgraph isomorphismがかなり減って速くなる

提案手法

Edge index

• 各$$ (L_u, L_v, L_{uv}) $$について以下を保存
  • $$ L(u)=L_u, L(v)=L_v, L(uv)=L_{uv} $$な辺を含むD中のグラフG
  • Gにそういう辺（複数有る）が一つ以上出現する確率

Connectivity index

• 各$$ (L_u, L_v, \ell) $$について以下を保存
  • 端点のラベルが$$L_u, L_v$$の頂点対間に長さ$$\ell$$の経路があるか？
  • 実際には，メモリを食い過ぎるので，Bloom filterを使う
    • あれば1，なければ0(w.p.1-ε) or 1(w.p.ε)
  • $$ \ell \leq \ell_\max = 3 $$

枝刈り

• 結局，期待頻度（サポート）の上限を高速に欲しい
• S＝今見ているパターン
• $$I_S =$$ Sの全辺を含むD中のグラフからなる集合
  • Edge indexを使う
• 上限1
  • $$ |I_S|/|D| $$
  • 確率とか考えない自明な上限
• 上限2
  • グラフGにSが出現する確率≦(Sの各辺が一回以上出現する確率)
  • ↑をD中のグラフについて総和をとる
  • グラフの構造は何も考えない
• その他枝刈り
  • Connectivity indexをナイーブに使う
  • S中の距離$$\ell$$のラベル対があるか，みたいなことを計算して，一致するかみる

期待頻度計算

• それでもダメなら期待頻度をCIKM'09の手法で計算
• Dにはグラフが沢山あるので，良い順番で計算したい
• (適当な計算量による見積もりコスト)／(出現の上限)が低いものから優先的に見る
• 閾値を超えたり，閾値を超えない（上限を引いていけば分かる）と分かったらすぐ抜ける

実験

• 比較手法MUSE
• 精度の比較なし（MUSEとほぼ同じ）
• subgraph isomorphismの計算がかなり減ったことが大きい
  • 数百倍以上速くなる

まとめ

• こんなもんだなあという感じ
• センスの良い枝刈りはないものか
  • 今回のはとりあえずぶっこんだ感がある

EDBT uncertain graphs 頻出部分グラフ

2016/10/13