Efficient Personalized PageRank with Accuracy Assurance - todo314 @ ウィキ

Efficient Personalized PageRank with Accuracy Assurance

• Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro
• KDD 2012

概要

• [Fujiwara-Nakatsuji-Onizuka-Kitsuregawa. VLDB'12]Fast and Exact Top-k Search for Random Walk with Restartの後続研究
• PPRに関する3つの問題
  • $$\mathbf{x}$$が入力嗜好のPPR
  1. $$ \mathbf{x}_q $$の厳密計算
  2. $$ \mathbf{x}_v $$が上位kの頂点v
  3. $$ \mathbf{x}_v > \epsilon $$な頂点v
• QR分解による厳密計算サブルーチン＋上下限推定による枝刈り
• 既存手法よりも爆速

提案手法

QR分解

• VLDB'12とほぼ同じ
• $$ \mathbf{x} = (1-\alpha)\mathbf{P}^\top (I-\alpha \mathbf{T}')\mathbf{Pv} $$
  • Pは置換行列、$$ \mathbf{T}' = \mathbf{PTP}^\top $$
• I-αT'を頑張ってQR分解しておく
• PPRは$$ \mathbf{F} = (1-\alpha)\mathbf{P}^\top \mathbf{R}^{-1} $$のi行と$$ \mathbf{g} = \mathbf{Q}^\top \mathbf{Pv} $$の内積で計算できる
  • gの計算がちょい重め（一回だけ）、内積は簡単
• 非ゼロ要素を最小化するPの計算は難しい（minimum fill-in）
  • 次数ヒューリスティック

枝刈り部分

• 下限を見積もる（反復改善では無い）
• 下限が大きいものから見ていく
  • 上限が上位kに入らないなら枝刈り
  • 入りそうなら、PPRを厳密計算

実験

• サイズ：最大で300K点1M辺
• 厳密だから精度1だし、速いよ！

まとめ

• 良い感じだが、QR分解はやはり厳しかった

KDD PageRank personalized PageRank

2017/04/19