Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and ... - todo314 @ ウィキ

Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments

• Dániel Fogaras, Balázs Rácz, Károly Csalogány, Tamás Sarlós
• Internet Mathematics 2005

概要

• fully personalizationが良いです
• ランダムウォーク手法を考案
• 分解定理を使って少し精度改善
• 実験もしました

関連研究

• Topic-sensitive PageRank [Haveliwala '02]
  • tトピックの線形結合のみ、O(tV)空間
• Hub Decomposition [Jeh-Widom '03]
  • 上位H頂点に限定、O(H^2)空間
• Basic Dynamic Programming [Jeh-Widom '03]
  • 任意、O(V(k-近傍))空間

提案手法

• 任意、O(NV)空間（Nは標本数）
• 各頂点からNランダムウォーク標本し、終了頂点を記録
• 普通のクエリは、ただの頂点数
• 分解定理
  • $$ \mathbf{\pi}_u = (1-\alpha)\mathbf{1} + \alpha |\mathcal{N}^+(u)|^{-1}\sum_{u \in \mathcal{N}^+(u)} \mathbf{\pi}_v $$
  • ∑で得をする; 「個々がε誤差」では無くて、「$$|\mathcal{N}^+(u)|$$倍の量の標本」があると思う

色々

• 厳密計算しようと思った時のデータベースサイズの下限 $$ \Omega(V^2) $$bits
• 厳密、近似、比較、等に関する理論的な情報量（？）について議論
• 主張「厳密は無理なので、近似でしょ」

まとめ

• [Jeh-Widom '03]はもう一回読むべきだな

Internet Mathematics PageRank personalized PageRank

2017/04/19