Fast and Exact Top-k Search for Random Walk with Restart - todo314 @ ウィキ

Fast and Exact Top-k Search for Random Walk with Restart

• Yasuhiro Fujiwara, Makoto Nakatsuji, Makoto Onizuka, Masaru Kitsuregawa
• VLDB 2012

概要

• RWR上位k頂点を抽出したい
• 提案手法K-dash
  • 厳密に答える

提案手法

• 大まかな流れ
  1. Google行列をLU分解
  2. RWR値の上限の降順に頂点vを見ていく
     1. もうvが（暫定の）上位kに入らない→打ち切り
     2. vのRWR値を厳密計算

疎行列LU分解による厳密計算

• Google行列をLU分解しておくと、RWRベクトルは、$$ \mathbf{U}^{-1}\mathbf{L}^{-1}\mathbf{v} $$な感じで得られる
• LU分解前に、非ゼロ要素数が減るように行と列を並べ替えます
• 最適解計算はNP-困難なので、次数／クラスタ（Louvain法）ベースの並べ替え法

木による上限推定

• クエリ頂点からBFSした感じにレイヤを構成し、その順で頂点を判定するとする
• レイヤに沿って上限をいい感じに推定出来る
  • 今まで見た頂点のRWRは厳密計算済みとする
  • レイアが大きくなると、上限は減る（非増加）
    • 今見ている頂点から上位kに入ら無さそうなら、その後はもう見なくて良い
  • 実際には、逐次計算で頂点辺り定数時間で推定可能

実験

• 最大で1M未満の規模
• NB_LINFast Random Walk with Restart and Its Applicationsと比較
• 厳密だけど圧倒的に速い
• 省空間で、実験的には線形サイズ位しか食わない
• 前処理=LU分解が結構重い; 数時間かかる
• 木で枝刈り・打ち切りを入れた効果が大きいときもある

まとめ

• 結構いい話
• 上下限の方法はそれらがどの位タイトかは知りたい
• けど、上位kの場合は順序が大事なので、それを解析してもあまり意味ないかも

PageRank VLDB personalized PageRank

2017/04/19