k-Nearest Neighbors in Uncertain Graphs - todo314 @ ウィキ

k-Nearest Neighbors in Uncertain Graphs

• Michalis Potamias, Francesco Bonchi, Aristides Gionis, George Kollios
• VLDB 2010

概要

• k近傍クエリ
• 最短距離や酔歩に基づく尺度を拡張
  • 厳密計算は難しい
• Monte-Carloサンプリングで近似アルゴリズム
• グラフ変形，枝刈り
• 実験：数十M辺

メモ

• VLDB版ではない原稿を読んだのでちょっと違う

イントロ

• 確率的グラフ
  • 辺に確率が割り振られている
  1. センサや実験による雑音
  2. 不安定な通信
  3. リンク予測
  4. 秘匿性のための摂動
• 気になること
  • 確率的グラフ上の距離とは？
  • 頂点のk近傍は？
  • ランキングは？
• 応用
  • ソーシャルネットワーク
    • リンク／影響予測
  • モバイルアドホックネットワーク(MANET)
    • 配送確率→確率的経路問題
  • 生物学ネットワーク
    • 遺伝子・蛋白質間の相互作用
• あるグラフで(距離,確率)を考える
• <(1,0.3), (2,0.26), (∞,0.44)>
  • 最確距離 = ∞
  • 中央値 = 2
  • やばめ
• 統計の概念（？）とグラフ理論のを混ぜる

予備知識

• s-t間の最短経路長の分布
• $ \mathbf{P}_{s,t}(d) := \sum_{G \mid d_G(s,t)=d} \Pr[G] $
• 確率的最短経路長

問題 最確最短経路

• s-t間の最確経路を求めよ
• w'(e)=-log p(e)としてDijkstra

多数距離

• 最確最短経路長
• $$ d_{\mathrm{J}}(s,t) = \arg \max_d \mathbf{P}_{s,t}(d) $$
• RGを標本すると一番出現しやすい最短経路長に注目

期待距離

• $$ d_{\mathrm{E}}(s,t) = \sum_d d \cdot \mathbf{P}_{s,t}(d) $$
• 非連結な時があるから∞になる
• →有限の時だけ考慮して信頼性もくっつける

期待信頼距離

• <dER(s,t), p(s,t)>
• $$ d_{\mathrm{ER}}(s,t) = \sum_{d \mid d < \infty}d \cdot \frac{\mathbf{p}_{s,t}(d)}{1- \mathbf{p}_{s,t}(\infty)} $$
• $$ p(s,t) = \sum_{d \mid d < \infty} \mathbf{p}_{s,t}(d) $$

中央値距離

• $$ d_{\mathrm{M}}(s,t) = \arg \max_{D} \left\{ \sum_{0 \leq d \leq D} \mathbf{P}_{s,t}(d) \leq \frac{1}{2} \right\} $$

• Pr[sとtが連結]の厳密計算は#P-complete
  • reliability problem
• 特に最近のデカイグラフでは厳密計算はやばげ

近似アルゴリズム

• 期待信頼距離と中央値距離
• 標本して近似が王道

1. r=数百標本で十分
2. 最短距離や連結度を測る

• Chernoff bound
  • $$ r \geq \frac{3}{\epsilon^2 \mu} \ln \frac{2}{\delta} $$ならPr[(1±ε)近似からずれる]≦δ
• Hoeffding inequality
  • Xi∈[ai, bi]
  • S = Σ_i Xi
  • $$ \Pr[|S-E[S]|\geq \epsilon] \leq 2 \exp \left( -\frac{2\epsilon^2}{\sum_i (b_i - a_i)^2} \right) $$
• 期待信頼距離を↑でbound
• $$ r = \max\{ \frac{3}{\epsilon^2 \rho}, \frac{(n-1)^2}{2 \epsilon^2} \} \cdot \ln \frac{2}{\delta} $$必要
• (n-1)^2がでかそう←(bi-ai)^2の項から
• でもSmall worldだし実際は小さそう
  • 自分の疑惑：本当か？bi=n-1な部分グラフはある（ランダムグラフとして発生しうる）んだよなぁ…

• 期待中央値距離の計算
• Chernoff boundで何か抑えられる

k-近傍

• 基本戦略: Monte-Carloで標本を取りながら枝刈り
• 問題 k-NN
  • d_P(s,t_i)がtop-kなT_k(S)={t_1,…,t_k}を見つける
• 挑戦: d_P(s,t)を全tについて計算したくない

中央値距離の場合

• $$ \tilde{\mathbf{p}}_{D,s,t}(d) = $$
  • $$ \mathbf{p}_{s,t}(d) $$ if d<D
  • $$ \sum_{x \geq D}\mathbf{p}_{s,t}(x) $$ if d=D
  • $$ 0 $$ if d > D
• 補題
  • $$ \tilde{d}_{D,M}(s,t) $$: $$ \tilde{\mathbf{p}}_{D,s,t}(d) $$からの中央値
  • $$ d_{M}(s,t) $$: $$ \mathbf{p}_{s,t}(d) $$からの中央値
  • $$ \tilde{d}_{D,M}(s,t_1) $$ < $$ \tilde{d}_{D,M}(s,t_2) $$ なら $$ d_{M}(s,t_1) $$ < $$ d_{M}(s,t_2) $$
  • ≦だと多分まずいが論文では無視してるように見える

アルゴリズム

1. |Tk|<kの間
   1. D←D+γ
   2. r回繰り返し
      1. ランダムグラフ上で距離D未満までsからDijkstra
      2. $$ \tilde{\mathbf{p}}_{D,s,t}(d) $$をカウントアップ
   3. Tkに無い頂点tで，median < D
      1. Tk << t

多数距離の場合

• 違い1: medianみたいに50%に到達すればOKではない
• 違い2: もうこいつはtop-kに入らないお，みたいに判定ができない

Random Walks in Possible Worlds

• 辺が使える確率があるようなRWだけど，結局普通のRWになるよみたいな話

実験

• リンク予測への応用
• 効率
  • 確率密度とか，どのくらい標本いるかとか

まとめ

• データマイニング・データベースでのUncertain graphsの割りと大事そうな論文
• やってることは普通
  • 実験は読んでないので，そこも評価されたのかも
• 精度がtop-kの問題を解く上で放置なのでどうにかした方がいいのでは？
  • k番目とk+1番目の差(?)みたいなののの，確率的に保証するとか．別にいらのかなあ
• reliability系を普通に昔からあるはずなので調べる必要あり

VLDB k-近傍 uncertain graphs 最短経路

2015/07/13 15:38