Fast Single-Pair SimRank Computation - todo314 @ ウィキ

Fast Single-Pair SimRank Computation

• Pei Li, Hongyan Liu, Jeffrey Xu Yu, Jun He, Xiaoyong Du
• SDM 2010

概要

• 全点対間SimRankはあるけど、クエリしたいよねー
• ペアのSimRankを高速に計算するよ
• 精度を落とさずにやったね

SimRank

• 一般的には下の式を収束するまで反復
• $$ R_{k+1}(a,b) = \frac{C}{|I(a)||I(b)|}\sum_{i \in I(a)}\sum_{j \in I(b)}R_k(i,j) $$
• 行列でも書ける
• Q. SimRankってそもそも何だ？
• A. 2人が出会うまでのランダムウォーク
• M_k(a,b): kステップ目で最初にである確率
• R_k(a,b)はM_iの和で表される

提案手法

• M_k(a,b)を頑張って計算していくスタイル
• kの最大値は…？
  • 絶対誤差をΔとすると、K=floor(log_C Δ)
• パスで考えよう
  • パスを決定すると、それを辿る確率は簡単に計算できる
  • a/bから出発した長さkのパスが最後でだけ一致する（初めて出会う）なら
  • そういうパスの出現確率を計算してM_k(a,b)に足す

A Naive Path-Tree Matching Method

• G=(V,E), C, (a,b), kが与えられる
• a,bから出発する長さkのパスを列挙する
• 2つのパスをループ
• 最後だけ一致するパスのペアを見つけ、出現確率の和をとってかえす

A New Single-Pair SimRank Method

• 流石に遅すぎる
• Position Matrix P_k^{ab}
  • (i,j)成分は、kステップ目で、a/bがi/jにいる確率を表す

• P_k^{ab}

  • P_k^{ab}で、kより前では2人は合っていない状態だけ考慮する
• 直感的に$$ M_k(a,b) = \sum_i (\tilde{P}_k^{ab})_{ii} $$
• この行列を頑張って計算する
  • 非ゼロの要素の数があまり無いことをいっている？
• 後なんか適当に速くする

実験

• データセットは小さめ
• 手法（最後2つは高速化
  • SimRank: All-pair
  • NSP: naive Single-Pair SimRank
  • ISP: iterative Single-Pair SimRank
  • AR: Access Reduction
  • TF: Threshold Filtering
• Threshold Filteringというのをしないとちょっと遅い
  • ステップを重ねると非ゼロの要素がめっちゃ増える
• 6反復くらいで十分？？？
• 大体100倍位速い

まとめ

• 関係ないけどSimRankの意味が分かって良かった
• 100倍ってどうなんでしょう？
• そう考えると1対全の方が需要ありそう
• 計算量評価があんまりタイトじゃないなあ…

SDM SimRank

2013-11-13 23:51:05 (Wed)