Discovering Highly Reliable Subgraphs in Uncertain Graphs - todo314 @ ウィキ

Discovering Highly Reliable Subgraphs in Uncertain Graphs

• Ruoming Jin, Lin Liu, Charu C. Aggarwal
• KDD 2011

概要

• 高信頼部分グラフ問題…連結な確率が閾値以上の（誘導）部分グラフをとってくる
• 厳密は無理→近似

イントロ

• 電気通信網 (telecommunication network)
• タンパク質間相互作用ネットワーク (protein interaction network)
• ソーシャルネットワーク
  • …信頼／影響
• 部分グラフ発見の応用は上の面で色々ある
• 密部分グラフ抽出っぽいが違う

問題定式化

• $$ G=(V,E,p) $$のネットワーク信頼性$$ \mathbf{R}[G] $$
  • G全体が連結である確率
  • 誘導部分グラフでも考えられる
• 高信頼部分グラフ問題 (Highly Reliable Subgraph Problem)
  • 入力: $$ G=(V,E,p), \alpha \in [0,1] $$
  • 出力: ネットワーク信頼性がα以上の誘導部分グラフ全て
• 補題1
  • $$ \mathbf{E}[G[V_s]] $$は単調性が成立しない
• 補題2 (Edge-cut lemma)
  • $$V$$の分割$$ V_1, V_2 $$があり，$$ \sum_{e \in V_1 \times V_2}p_e < \alpha $$ならば，
  • どのHRSもV1,V2をまたがない
• （カットがあるので当たり前）
• 最小カットでどんどん分割していける

標本近似計画

• 近似でやりたいけれど偽陽・偽陰を避けたい
• $$N$$ランダムグラフ作り，信頼性を（不偏）推定する
• $$ N \geq \frac{2}{\epsilon^2} \log \frac{2}{\delta} $$だと「いつもの」
• precisionとrecall
  • 精度・適合率…選択したものが正の割合
  • 再現率…正のものが選択された割合

高信頼集合の発見

• 2つの集合を生成して両方を制御
  • Step 1. $$ \overline{S} $$…Vから推定値$$ \geq \alpha-\epsilon $$を抽出
    • 再現率を最大化したい
  • Step 2. $$ \underline{S} $$…$$ \overline{S} $$から$$ \geq \alpha+\epsilon $$を抽出
    • 精度を最大化したい
• 定理1
  1. $$\overline{S}$$の期待再現率は$$ 1-\delta $$以上
  2. 確率$$1-\delta$$以上で，$$\underline{S}$$の精度は1
  3. 確率$$1-\delta$$以上で，$$\overline{S}$$の精度は$$ \beta = \frac{|\underline{S}|}{|\overline{S}|} $$
  4. $$\underline{S}$$の期待再現率は$$ \beta-\delta $$以上
• $$\delta$$の役目…精度と再現率
• $$\epsilon$$…$$\overline{S},\underline{S}$$の差
  • 実験で調整する

頻出密集合の発見

• 頻出密集合問題 (Frequent Cohesive Set Problem)
  • θの割合で$$G[V_s]$$が連結な$$V_s$$を見つける
• 極大頻出密集合 (Maximal Frequent Cohesive Set)
  • supersetはcohesiveでない
  • 単調ではないが一旦そうする
• Step 1ができればStep 2は簡単

頻出密集合の発掘

• まず，maximalを見つけてから，non-maximalを探す

MFCSに対する剥くアルゴリズム

• 極大頻出密集合を見つけてから，「剥いて」いく

1. 最初のパターンが大事
2. 正しく収束して欲しい

緩和

• 連結性を緩和…外部を伝っても良い→かなり簡単になる
• 極大頻出連結集合問題 (Maximal Frequent Linked Set Problem)
  • G中（正確には各ランダムグラフ）で連結な割合が閾値以上
• freq. cohesive⇒freq. linked
• MFLSを初期パターンとすると良さそう
• どうやって取り出すか？
  • 単調性が有る
  • 各ランダムグラフの連結成分の族の「極大頻出アイテム集合」がほしいもの
  • 変換は線形時間

ナイーブ

• 各MFLS mについて…
  • IF mがFCS: 実質終わり
  • O.W.: mの誘導部分グラフ（に対するランダムグラフ）において再帰的に実行
• 探索するMFLSが重複しうる…冗長
• 大部分は無駄なので避けたい

速い剥くアルゴリズム

Layered Peeling

• 階層的に探索していく
  • もし，どちらかが部分集合なら小さい方は探索しなくても良い
  • つまり，探索でも極大なものだけ見ればOK

Transaction Reduction

• ﾄﾊﾞｼﾏｼﾀ
• 総計算時間…全体のMFIの2倍いかないくらい（実験的に）

非極大FCSのためのDFS

• MFCSの1頂点ずつ除く(?)
• どれかのMFCSに含まれる連結頂点集合を列挙
  • 部分集合判定とか連結性判定とかを色々頑張る

実験

• データセット: 大体PPI
• 評価項目: 精度と効率
• 調べたこと
  • ε,δ,αに対するβ

まとめ

• シミュレーションしたら終わりじゃね？と思ったが意外とそうでもなかった
• 単調が無いので，緩く緩和して単調性を入れるのは良いかもと思った
• もっと直接的にズバッととけないかな？
• 重複が多そうなので，既存のもっと良い部分グラフ抽出を適応させたら良さそう

KDD uncertain graphs 密グラフ

2015/11/27