読者です 読者をやめる 読者になる 読者になる

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 秒