Fast Random Walk with Restart and Its Applications - todo314 @ ウィキ

Fast Random Walk with Restart and Its Applications

• Hanghang Tong, Christos Faloutsos, Jia-Yu Pan
• ICDM 2006

概要

• ベストペーパー
• RWRを高速にクエリ計算した

提案手法

B_LIN

• グラフを（METISとかで）k分割する
• 確率遷移行列W（論文中では正規化Laplacianもどき）をW_1+W_2に分割する
• RWR行列は$$ (1-c)(I-cW)^{-1} $$
• W_1：分割内だけ；diag(W_11, …, W_1k)な感じ
• W_2：分割間だけ；
• Q_1 := diag(Q_11, …, Q_1k)
  • Q_1i := (I-cQ_1i)の逆行列
  • これは即ち(I-cW_1)の逆行列
• W_2を低ランク近似して、USVで表す
  • 適当に頑張る
• $$ \Lambda = W^{-1} \approx (S^{-1}-cVQ_1^{-1}U)^{-1} $$
  • すごく小さいので陽に計算してもOK
• 更にもう少しゴニョゴニョして返す
  • もしW_2=USVなら厳密に一致 by Sherman-Morrison lemma

NB_LIN

• k=nとした場合; W_1=0, W_2=W

1. W=USVを低ランク近似
2. (S^-1-cVU)^-1を計算
3. ゴニョゴニョした結果を返す

• 誤差評価は低ランク近似の一般的な結果による（普通）
• community structure…分割すると良さそう
• linear correlation…W_2を低ランク近似して良さそう

実験

• 二百万辺のグラフ
• まぁまぁ

まとめ

• まぁやるよねぇという内容（今考えたら）
• fully personalized設定を更に高速化するには、
• どう次元削減するかをもう少し真面目に考えるべき？

ICDM PageRank personalized PageRank

2017/04/25