Efficient Personalized PageRank with Accuracy Assurance (KDD'12)

• 問題
  1. p2p PPR
  2. top-k PPR
  3. threshold PPR （しきい値以上を取得）
• 提案手法
  • 3.2.1
    • 行列． s = c{I-(1-c)A}^{-1} d なので，I-(1-c)A を QR 分解する
    • クエリは，cR^(-1) の v 行と Q^T d の内積
    • cR^(-1) と Q^T を覚えておくっぽい
  • 3.2.2
    • Q, R をスパースにするために頂点順を入れ替えよう
    • まだ選んでない頂点への次数が最小のものから選ぶ
    • 既に選んだ頂点への次数で tie break
    • いわゆる min-degree heuristics
  • 3.3 top-K
    • lower bound: BFS みたいにして伝えていく，BFS DAG 上の影響のみを考える感じ
    • upper bound: 全体での和が 1 になることのみを使う
    • algorithm: 全頂点を見る．lower bound で枝狩り．狩れなかった奴 p2p．下界が大きいやつから見ていく．
  • 3.4 threshold
• 実験
  • Q と R^{-1} は少なくともこれらのデータセットでは確かにスパースっぽい
  • 前処理時間，web-NotreDame で 10^4 秒