Top-k Reliability Search on Uncertain Graphs - todo314 @ ウィキ

Top-k Reliability Search on Uncertain Graphs

• Rong Zhu, Zhaonian Zou, Jianzhong Li
• ICDM 2015

概要

• クエリ頂点sから連結する確率が上位kの頂点を返す問題
• サンプリングしたグラフからのBFSをビット並列で高速化
• サンプリングしたグラフはビットベクトルだけなので軽め
• 愚直な実装の10倍速い

問題定式化

• 入力: $$\mathcal{G}, s, k$$
• 出力: $$ \textsf{Rel}_{\mathcal{G}}(s,v) $$が上位kの頂点
  • 本当は"述語"があるがどうでもいいので割愛
• Q. Fast Reliability Search in Uncertain GraphsEDBT 2014と同じじゃね？
• A. 閾値を決めるのが難しい & 多くの状況では 順番 を知りたい

提案手法

愚直なサンプリング

• Chernoff boundのいつものが成立
• 本当は上位kが正しい保証が欲しいので、これは適当すぎでは？

最適化した手法

• BFSの共有
  • $$\Omega_v$$: sからvに到達できるサンプルグラフの添字の集合
  • どれかのサンプルグラフで辺がある限りBFSをする
  • 今vにいたら、vの入近傍のΩを使って自明に更新
    • $$\Omega_v \leftarrow \bigcup_{u \in \mathcal{N}^-(v)} (\Omega_u \cap \Omega_{(u,v)}) $$
  • これだけでは大して速くならない、（と思う）
• ビット並列BFS
  • $$ \Omega_v, \Omega_{(u,v)} $$に相当するビットベクトル$$ \mathbf{I}_v, \mathbf{I}_{(u,v)} $$を用意
  • 特に辺に関するIは不変
  • 上の更新式はビットベクトルでチョチョイのチョイ（自明）
  • ビット数倍得する
• オフラインサンプリング
  • 辺に関するIの用意に時間がかかるので、オフラインで索引として作っておく、とする
  • でも、使いまわすとクエリ間での独立性が怪しいので、適宜再生成する
    • 結局此処が遅くなるような気がする
• その他最適化: 適当なカットで$$ \textsf{Rel}_{\mathcal{G}}(s,v) $$の上限を計算して枝刈り

実験

• ベースラインより10倍近く速い
• kに大して劣線形で遅くなる
• 大きいサンプルサイズでも大丈夫（ゆっくり遅くなる）
• グラフサイズに線形
• 精度をちょろっと比較（値そのものと、上位k頂点の共通部分の大きさ）

まとめ

• 問題に対する理論的洞察はほぼ無い
  • EDBT 2014の方が頑張ってる
• 代わりに物凄く単純な戦略を頑張って実際的に高速化するのがメイン
  • でもビット並列BFSって既存だし…
• サンプリングには限界あるし、相対誤差とかで頑張りますか？

2016/11/24