Efficient Personalized PageRank with Accuracy Assurance
-
Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro
-
KDD 2012
概要
提案手法
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} $$の内積で計算できる
-
非ゼロ要素を最小化するPの計算は難しい(minimum fill-in)
枝刈り部分
-
下限を見積もる(反復改善では無い)
-
下限が大きいものから見ていく
-
上限が上位kに入らないなら枝刈り
-
入りそうなら、PPRを厳密計算
実験
-
サイズ:最大で300K点1M辺
-
厳密だから精度1だし、速いよ!
まとめ
KDD PageRank personalized PageRank
2017/04/19
最終更新:2017年04月19日 13:39