VLDB'14 論文採択：グラフの構造を活用した Personalized PageRank の高速計算

論文が国際学会 VLDB'14 に採択されました．VLDB (International Conference on Ver Large Data Bases) は SIGMOD と並ぶデータベースの最も有名な学会です．学会は 9 月に中国の杭州です．

今回の論文は "Computing Personalized PageRank Quickly by Exploiting Graph Structures" というタイトルで，NII の前原さん，同じ研究室の岩田, NII の河原林先生との共著です．

内容

この論文は大規模なソーシャルネットワークやウェブグラフにおいて Personalized PageRank を高速に計算する手法を提案する論文です．Personalized PageRank は有名な PageRank の一般化です．PageRank が担っていた重要度の計算の他，関連度としても使われ，幅広い応用を持ちます．

今回の提案手法は，Tree-decomposition を拡張した Core-tree-decomposition を用い，グラフの性質を活用して計算を効率化します．

Core-Tree-Decomposition による Core と Whisker の分離

グラフ理論における有名な概念である tree-decomposition (木分解) を拡張した core-tree-decomposition という道具を用いることにより，グラフを Core 部分と Whisker 部分に分離することができます．Whisker 部分は木に類似した構造を持ち，グラフ理論の言葉を用いて言えば treewidth (木幅) が小さいです．一方，Core 部分は密に絡みあっており，グラフ理論の言葉を用いて言えば expander graph に近いです．

Core-Tree-Decomposition の高速な計算

core-tree-decomposition を利用していくための問題点の 1 つとして，計算コストがありました．そこで本論文では，まず，データ構造の工夫により core-tree-decomposition をより高速かつ省メモリに計算するための新たなアルゴリズムを提案しています．

Whisker 部分の処理: LU 分解による Preconditioning

Personalized PageRank の計算は連立方程式の球解に他なりません．ただし，そのままでは LU 分解のような直接法はスケールせず，一般的には反復法が用いられます．

ただし，上記の通り，Whisker 部分は木幅が小さく，これは，この部分に関しては LU 分解が効率的に動作するということを意味します．従って，Whisker 部分に関しては LU 分解により直接的に解を求め，その解を用いて連立方程式を Core 部分のみの問題に帰着します．

Core 部分の処理: GMRES 法

一方，Core 部分は expander graph に近いため，LU 分解のような直接法の性能は絶望的です．しかし，逆に Core 部分は Core 部分で，expander graph に近いという性質を活用し計算を効率化することができます．

通常の Personalized PageRank の計算では基本的な反復法であるヤコビ法や Gauss–Seidel 法が用いられます．しかし，今回提案しているのは，Core 部分には GMRES 法 (generalized minimal residual method) を用いることです．expander graph から来る性質の良い連立方程式において GMRES が効率的に収束することは，理論的にも実験的にも言うことができます．

ここで面白いのは，Core と Whisker の分離を行わないでそのままの連立方程式に適用した時は，GMRES 法はヤコビ法等よりも低速であるという点です．これは，そのままの問題ではあまり性質が良くなく，GMRES の高い収束性能を発揮できず，反復回数で差をつけることができないため，オーバーヘッドの部分で負けてしまうからです．一方，今回は Core 部分を抽出したことにより，オーバーヘッドを加味してもなお GMRES 法が優位に立ちます．

論文採択について

今まで VLDB はとにかく負け続きだったので，第二著者とはいえ，VLDB への初の論文採択は本当に待ち望んでいたものであり嬉しいです．アルゴリズムが面白いという点が査読者にも気に入ってもらえたのが良かったのだと思います．