Random Walks with Random Projections - todo314 @ ウィキ

Random Walks with Random Projections

• Purnamrita Sarkar, Geoffrey J. Gordon
• NIPS 2009 Workshop

概要

• 無向グラフのRWRをRandom projectionで効率的計算

提案手法

• iからのRWR: $$ \mathbf{x_i} = \alpha(I-(1-\alpha)AD^{-1})\mathbf{e_i} $$
• $$ \frac{v_i(j)}{d(j)} = \alpha L^{-1}_\alpha(i,j) $$が欲しい
  • $$ L_\alpha = D-(1-\alpha)A $$
• Laplacianは(接続行列)^T(接続行列)で書けるけど、L_αの場合はちょっと変形が必要
• $$ \mathbf{e_i}^\top L^{-1}_\alpha \mathbf{e_j} = \mathbf{e_i}^\top L^{-1}_\alpha B_\alpha^\top W_\alpha B_\alpha L^{-1}_\alpha \mathbf{e_j} $$
• $$ \mathbf{\chi} = L^{-1}_\alpha B_\alpha^\top W_\alpha^{1/2} $$
• χをrandom projectionしてχQを持っておく; k=O(log n/ε^2)次元ならk回Laplacianの線形方程式を解く
  • Laplacianの線形方程式はほぼ線形時間で解ける
  • 疑問: Q.||f(x)-f(y)||は保持されるけど、内積は？
  • 答え: 絶対誤差で保持される、まぁまぁ良い

実験

• たった数千辺

まとめ

• 無向じゃない場合はこういう変形は出来ないかな？
• 線形方程式を適当に解けば良いなら、そのままrandom projectionすれば良い…？

NIPS PageRank personalized PageRank

2017/04/24