Distance Constraint Reachability Computation in Uncertain Graphs - todo314 @ ウィキ

Distance Constraint Reachability Computation in Uncertain Graphs

• Ruoming Jin, Lin Liu, Bolin Ding, Haixun Wang
• VLDB 2011

概要

• 経路長に制限を入れた到達可能性確率計算クエリ
• 普通のシミュレーションは遅いので，頭のいい方法を考案
• 最大で1M辺規模で動く

問題定義と動機付け

• 距離制約到達可能性クエリ (Distance-constraint reachability)
• 入力: 2頂点s,t, uncertainグラフ G, 閾値d
• 出力: s-t間の最短経路長がd以下である確率$$ R_{s,t}^d(\mathcal{G}) $$は？
• P2Pネットワークでの応用例
  • ただの信頼度よりは便利
• 道路ネットワーク
  • 予測不可能な交通渋滞を表現
• ソーシャルネットワーク
  • 辺が信頼を表す，hop数はある程度制限したほうが良い

• 精度尺度
  • 期待自乗誤差
  • $$ \mathbf{E}[(X-\mu)^2] = \mathbf{Var}[X^2] + (E[X]-\mu)^2 $$
  • 不偏ならば，Var[X^2]が大事
• 目標: 最小分散＋低計算費用を達成する不偏推定量の開発
• 前処理: d(s,v)+d(v,t)≦dを満たす頂点tだけ残す（辺も同様）

ベースライン

直接的標本 $$ \hat{R}_B $$

• ランダムグラフをシミュレーションで生成して数えるだけ
• $$ \mathbf{Var}[\hat{R}_B] \approx \frac{1}{T} \hat{R}_B (1-\hat{R}_B) $$
• 流石にアホなので，Dijkstraをsからしながら枝刈りする

経路利用 $$ \hat{R}_P $$

• 長さd以下のs-t経路を列挙$$ P_1, P_2, \ldots, P_L $$
• $$ \mathbf{Pr}[P_1 \vee P_2 \vee \cdots \vee P_L] $$をMCシミュレーションで計算
• $$ \mathbf{Var}[\hat{R}_P] = \frac{1}{T}R_{s,t}^d(\mathcal{G}) (\sum_{i} \mathbf{Pr}[P_i]-R_{s,t}^d(\mathcal{G}) ) $$
• 全列挙が指数的で重すぎ

新しい標本推定

分割統治による厳密アルゴリズム

• 選んだeの生／死で分岐
  • p(e)(eを生に固定した確率)+(1-p(e))(eを死に固定した確率)
  • 信頼度の展開公式とほぼ同じ
  • 生は縮約と考えてもOKだと思う
• 枝刈り
  • 生の辺がs-tの長さd以下の経路を構成: Return 1
  • 死の辺がs-tカット: Return 0
• 当然再帰の深さは抑えたい

不等確率標本枠組

• 分割統治の再帰の木を考える
  • 葉は枝刈りされた自明な状態(0/1)
• 葉の重み$\mathbf{Pr}_i$: 固定した生／死の発生する確率
• 葉の標本確率$q_i$: 後で決める（実は標本が簡単になる）
• Hansen-Hurwitz 推定器
  • $$ \hat{R}_{HH} = \frac{1}{T} \sum_{i}\frac{\mathbf{Pr}_i \mathbb{I}}{q_i} $$
  • 分散を最小化すると$$ q_i = \mathbf{Pr}_i $$で
  • $$ \mathbf{Var}[\hat{R}_HH] = \frac{1}{T}R_{s,t}^d(\mathcal{G})(1-R_{s,t}^d(\mathcal{G})) $$
  • 単に葉に到達するまでコインフリップして分岐すればOK
  • ってただの直接的標本じゃ～ん！（ほぼおなじ）
• Horvitz-Thomson 推定器
  • 推定量の分子が$$ \pi_i = 1-(1-q_i)^n $$
  • $$ \hat{R}_{HT} = \frac{1}{T} \sum_{i}\frac{\mathbf{Pr}_i \mathbb{I}}{\pi_i} $$
  • 結局q_i=Pr_iが最適なんだけど，分散値自体はHHよりも小さくなりうる

最適再帰標本推定器

• 全部でT標本するとする
• ある辺eを選んで分岐するときに生／死の標本数をT_1／T_2に分岐させる
  • 適当にTが細かくなったら普通のHH／HT標本に切り替え
• 真の確率がわからないのでどう分岐させればいいか分からんので，辺の確率に比例させてみる
  • $$ T_1 = p(e)T, T_2 = (1-p(e))T $$
• と，HHよりも良いと証明できる
• 選んだeの有無で極端に確率が変化する場合にこの戦略が有効

実験

• 標本サイズ=1000
• 評価基準: 相対誤差，100回の不偏分散，計算時間
• 5K頂点・50K辺のランダムグラフでの実験
  • 精度は僅かに改善，高速化の方が見た目すごい（標本サイズ固定なので）
• 実データ 最大で1.4M辺

  In order to report the relative error, we limit the extracted subgraphs with number of edges from 20 to 50
  

• ちょっと不穏（時間は全部計測したのかな？）

まとめ

• やはり実験がお粗末に感じる
• 平均とかのざっくりした推定値しか見ていないので，
• 例えばs-t間の距離とかdの値によってどう挙動が変わるのかが分からん
• （一応，関係あるグラフの辺の数では見ているが…
• 手法は現時点ではこういうシミュレーションベースだけどちょっと工夫する，くらいしか見当たらないなあ…
• というかどういう評価尺度が良いかさえも議論の余地があると思う
  • 確率の値が10^-6とか小さのか0.0Xくらいの大きさなのかどうなのか…

VLDB uncertain graphs 到達可能性

2015/12/15