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
提案手法
-
大まかな流れ
-
Google行列をLU分解
-
RWR値の上限の降順に頂点vを見ていく
-
もうvが(暫定の)上位kに入らない→打ち切り
-
vのRWR値を厳密計算
疎行列LU分解による厳密計算
-
Google行列をLU分解しておくと、RWRベクトルは、$$ \mathbf{U}^{-1}\mathbf{L}^{-1}\mathbf{v} $$な感じで得られる
-
LU分解前に、非ゼロ要素数が減るように行と列を並べ替えます
-
最適解計算はNP-困難なので、次数/クラスタ(Louvain法)ベースの並べ替え法
木による上限推定
-
クエリ頂点からBFSした感じにレイヤを構成し、その順で頂点を判定するとする
-
レイヤに沿って上限をいい感じに推定出来る
-
今まで見た頂点のRWRは厳密計算済みとする
-
レイアが大きくなると、上限は減る(非増加)
-
今見ている頂点から上位kに入ら無さそうなら、その後はもう見なくて良い
-
実際には、逐次計算で頂点辺り定数時間で推定可能
実験
まとめ
-
結構いい話
-
上下限の方法はそれらがどの位タイトかは知りたい
-
けど、上位kの場合は順序が大事なので、それを解析してもあまり意味ないかも
PageRank VLDB personalized PageRank
2017/04/19
最終更新:2017年04月19日 15:35