Fast Reliability Search in Uncertain Graphs - todo314 @ ウィキ

Fast Reliability Search in Uncertain Graphs

• Arijit Khan, Francesco Bonchi, Aristides Gionis, Francesco Gullo
• EDBT 2014

概要

• 信頼性検索…確率η以上でSから到達可能な頂点集合
• 索引RQ-tree
  • 階層的クラスタリング
• クエリ評価
  • 候補生成…最大流ベース
  • 検証…
    • 下界ベース
    • 候補集合に関するサンプリング
• 精度>0.95、再現率>0.75で爆速

提案手法

• RQ-tree…頂点集合の階層的分割

クエリ処理:候補生成

• Rout(S,C) := Sから「Cの外の頂点」へ到達する確率
• Rout(S,C)<ηならR(S,t)<η (t∈V-C)
  • なのでV-Cの頂点を省ける
• 上限: Rout(S,C) ≦ 1-((S,V-C)カットの最大発生確率)
  • SからV-Cへ到達不可な確率の良い下限が欲しいから
  • 辺重み-log(1-p(e))な最大流で計算（C+N(C)の誘導部分グラフだけなので速い）
• 単一始点の場合
  • クエリは{s}とη
  • RQ-treeを葉{s}から上に辿りながら、Rout(S,ノードの集合)の上限を計算
  • Rout(S,C*)<ηとなったC*で止まれば、(i)C*は最小、(ii)t∈V-C* R({s},t)<η
• 複数始点の場合
  • 頑張る（イッパイ書いてある）

クエリ処理:検証

• R(S,t)の下限が欲しい
• ①高精度検証
  • 下限 := Sからtの最尤経路の発生確率
  • いつもの感じで最短経路計算
• ②高再現率
• サンプリングする

RQ-tree の構築

• $$ \mathsf{RQ\mathrm{-}tree} \; \mathcal{T} $$に求められる条件

1. バランスして頂点集合を分割していく
2. ある程度の高さがあると良い
3. Rout({s},C)は小さいと良い

• ので、並行分割
• 本当にやりたいこと: 二分割した時、Rout(S,C1/C2)と|C1|/|C2|の観点でバランスして欲しい
• 実際: 難しいので、METISに投げまーす

実験

• やったこと…
• 索引構築の時間／空間
• クエリ処理の精度／効率: 流石にMonte-Carloより速い、簡単な下限で端折れるのが強い
• RQ-treeの枝刈り: η大→#解減→枝刈り良
• 始点集合の大きさ・性能・スケーラビリティ: クエリ時間=O(|始点集合|)くらい？
• 影響最大化への応用: 一応10倍速くなった

まとめ

• 手法がごつすぎる割には、あまり最終的な保証が無い
• こんな単純な問題ですら実用的にでも満足に解けない現状は、（個人的には）つらぽよ感ある

EDBT uncertain graphs 信頼性 影響最大化

2016/12/12