Extrapolation Methods for Accelerating PageRank Computations

Extrapolation Methods for Accelerating PageRank Computations

  • Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub
  • WWW 2003

概要

  • PageRankのためのPower methodの高速化
  • 25--300%速くなった
  • メモ:イントロで…
    • Dangling nodesからは一様に飛ぶとしている

Aitken Extrapolation

  • $$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする
  • $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい!
  • $$ x^{(k-2)} = u_1 + \alpha_2 u_2 $$
  • $$ x^{(k-1)} = u_1 + \alpha_2 \lambda_2 u_2 $$
  • $$ x^{(k )} = u_1 + \alpha_2 \lambda_2^2 u_2 $$
  • $$ g_i = (x_i^{(k-1)} - x_i^{(k-2)})^2 = \alpha_2^2(\lambda_2-1)^2(u_2)^2_i $$
  • $$ h_i = x_i^{(k)}-2x_i^{(k-1)}+x_i^{(k-2)} = \alpha_2(\lambda_2-1)^2(u_2)_i $$
  • $$ f_i = g_i/h_i = \alpha_2 (u_2)_i $$
  • だから,$$ f = \alpha_2 u_2 $$
  • $$ u_1 = x^{(k-2)}-f $$
  • 実際には,仮定が近似なので,u1も近似
  • でも,u2の係数は小さくなる(なりそう?)

Epsilon Extrapolation

  • $$ g_i = (x_i^{(k-1)} - x_i^{(k-2)}) (x_i^{(k)} - x_i^{(k-1)}) $$とすると,
  • $$ u_1 = x^{(k-1)} - \alpha_2 \lambda_2 u_2 = x^{(k-1)} - (g_i / h_i)_i $$

Quadratic Extrapolation

  • $$ x^{(k-3)} = u_1 + \alpha_2 u_2 + \alpha_3 u_3 $$として,
  • $$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って頑張る(式が超長いので省略)

実験

  • 「テレポーテーションが少ない=αが大きい」とPower methodはどんどん遅くなる
  • Quadratic Extrapolationはぼちぼち耐えている
    • ただし,α=0.9ではほぼ同じ
    • 現在主流の0.85ではほとんど差がつかないのかな?

収束の尺度

  • 唐突だけど,$$ \delta_k = \| Ax^{(k)}-x^{(k)} \| $$って良いの?
  • KDist :=
    • Ax^(k)基準では$$ u \preceq v $$なのに,
    • x^(k)基準では$$ v \preceq u $$なペア(u,v)の個数(割合)
  • KDistもKmin(既存の何か)もL_1も大体同じ(?!)

PageRank PageRank計算 Personalized PageRank WWW

2015/07/27 17:03

最終更新:2016年12月05日 23:23