FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs - todo314 @ ウィキ

FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs

• Peter Lofgren, Siddhartha Banerjee, Ashish Goel, C. Seshadhri
• KDD 2014

概要

• $$ \pi_s(t) > \delta $$を$$ \mathcal{O}(\sqrt{d/\delta}) $$時間で近似計算
  • 相対誤差が小さい
  • 既存は$$ \Omega(1/\delta) $$時間で、$$ \delta=\Theta(1/n) $$にしたいので遅い□
• 計算時間の下限$$ \Omega(1/\sqrt{\delta}) $$を示した
• 実験的には数十倍速い

提案手法

設定

• 閾値$$\delta$$について$$ \pi_s(t) > \delta $$を小相対誤差で求めたい
• 注意: この論文ではPPRをRandom walk with restartの意味で書いている

大事な数式

• 洞察は最短路の双方向探索
• $$ \pi_s(t) = \sum_{w \in B} \Pr[H_B = w] \cdot \pi_w(t) $$
  • sから酔歩してBの頂点を経由してtに酔歩する確率
  • $$B$$: s-tカットを包む集合
  • $$ H_B $$: sから酔歩して初めて当たるBの頂点（の確率変数）
• $$ \pi_w(t) > \sqrt{\delta} $$な頂点wを溜める
  • $$\mathcal{O}(1/\sqrt{\delta})$$時間で計算可能
• sからの酔歩
  • $$\mathcal{O}(1/\sqrt{\delta})$$本で十分
• それぞれの手法は$$\mathcal{O}(1/\delta)$$時間だったのが解決！

双方向推定器

• 目標集合$$ T_t(\epsilon_r) = \{ w \mid \pi_w(t) > \epsilon_r \} $$
• フロンティア集合$$ F_t(\epsilon_r) = \mathcal{N}^-(T_t(\epsilon_r)) \setminus T_t(\epsilon_r) $$
• 命題1 (妥当な仮定の下)
  1. $$ F_t(\epsilon_r) $$はs-tカット
  2. $$ \Pr[\mathrm{RW}(s) \mathrm{\ hits\ } F_t(\epsilon_r)] \geq \frac{\pi_s(t)}{\epsilon_r} $$
• 2つ目が大事: 結構良くHITする、「$$F_t$$にHITする」事が大事で$$T_t$$は駄目

手法詳細

• Frontier-Aided Significance Thresholding (FAST-PPR)
• 精度パラメタ（定数でOK）
  • c=350: #酔歩
  • β=1/6: $$\pi_t^{-1}(\cdot)$$近似用
• Backward: [WAW'07]を適用し、精度$$ \beta \epsilon_r $$で$$ T_t(\epsilon_r) $$と$$ F_t(\epsilon_r) $$を計算
• Forward: $$ k=c\epsilon_r/\delta $$本の酔歩を生成する（HITする確率の逆数）
• 定理2: s,tが無作為選択なら$$ \mathcal{O}(\alpha^{-1}(d/\epsilon_r + \epsilon_r/\delta)) $$時間
• 定理3: $$ T_t(\epsilon_r), F_t(\epsilon_r), \pi_t^{-1}(w) $$が厳密なら、確率>0.99で$$ |\pi_s(t) - \hat{\pi}_s(t)| \leq \max(\delta, \pi_s(t))/4 $$
  • 証明の方針:
  • いい感じに正規化すると、$$ \pi_s(t) = (\delta/c)\mathbb{E}[Y] $$と書ける
  • 期待値=$$\pi_s(t)$$が大きい時に有効なChernoff boundを適用
  • 小さい時はまた違う変種を適用
  • 但し本当は$$F_t$$中の$$ \pi_t^{-1}(\cdot) $$は粗くしか分からない
    • 理論: ちょい変える（付録、激ムズ）
    • 実際: そのままでOK
• Balanced FAST-PPR
  • $$ \epsilon_r $$の値を動的に制御する

実験

• 速度・精度・性能解析をする
• データセット: 6.7M～3.7B辺
• 比較手法: FAST-PPRの個々のサブルーチンであるMonte-Carlo、Local-Update
• 無作為な(s,t)に対するPPRの分布
  • 1/n以上が全体の2.8%
  • 4/n以上が全体の1%未満
  • δをかなり小さくする必要有
• 実行時間
  • tを一様／PRに従いサンプル
  • 総時間: 圧倒的な差
  • 個々の時間: PR(t)が大きいと時間が掛かる
• 実際の精度
  • 相対（平均）15%
  • 相対（最悪）65%
• $$F_t(\epsilon_r)$$の代わりに$$T_t(\epsilon_r)$$で良さそう…ともーじゃん？
  • 全然駄目(´・ω・`)
  • T_t中のinverse-PPRは高いので、分散がヤバイことになる
• FAST-PPR vs. BALANCED-FAST-PPR
  • PR(t)高→Reverse多すぎ、PR(t)低→Forward多すぎ: これを解決

まとめ

• 発想と説明がうますぎ君
• 定理3の証明は（それ自体を理解するのは簡単だけど）設定も含めて上手い気がする
• 最悪時保証を頑張るとかが考えられるのかな

KDD PageRank PageRank計算 Personalized PageRank

2016/12/06