情報処理学会第 75 回全国大会

4C-2

Personalized PageRank の高速計算手法
藤原靖宏†
NTT ソフトウェアイノベーションセンタ†
1. はじめに
Personalized PageRank(PPR) [1] は グ ラ フ の ノードの関連度として最も注目を集めているもののひとつで，様々なアプリケーションに応用されている[2]．しかし PPR には計算量が高いという問題がある．そのため本論文では PPR による関連度を高速に計算する問題を取り組む．
2. Personalized PageRank
PPR では問い合わせ分布から各ノードの存在確率を決定し，そのノードからランダムウォークを行う．そしてノードに到達するたびに一定の確率 で問い合わせ分布に基づき各ノードに戻る．
グラフのノード数を とする． を行列とし，要素をノード にランダムウォークする確率を表すとする．また を問い合わせ分布で決定される行列とする．また を列が正規化されたグラフの隣接行列とする（すなわち要素はノード からノード へランダムウォークする確率を表す）．定常状態における各ノードにおける存在確率は以下の式を再帰的に収束するまで繰り返すことで計算できる．
()
PPR は定常状態における確率を関連度とする方法である．すなわち 行列の要素はノード の分布 に対する関連度となる．
Algorithm 1 に関連度を計算するアルゴリズムを示す．このアルゴリズムにおいて と をそれぞれグラフにおける全てのノードの集合及びノード から出ているエッジがつながっている隣接ノードの集合とする．また を繰り返しにおいて計算される更新後の関連度とし， をノード間で計算される関連度の伝搬値とする．
Algorithm 1 ははじめに関連度の分布 を問い合わせ分布 に初期化する（1 行目）．繰り返し計算のなかでまず更新後の関連度を 0 に初期化する（3～5 行目）．そしてすべてのノードに対してそれらのノードから出ているエッジが他のノードに伝搬する関連値を計算する（6～11 行目）．
そして伝搬された関連度から更新後の関連度を求める（12～13 行目）．これらの処理は所定の繰り返し回数まで再帰的に実行される.
この繰り返し計算による処理はグラフのサイズが大きくなると関連度の計算を高速に行えない．
これは このアルゴリズムがグラフ全体を用いて関連度の計算を行っているからである．

3. 提案手法
本論文では関連度の計算を高速に行うために，繰り返し計算の中で関連度の小さいノードを枝刈りする方法と，関連度の小さいエッジを枝刈りする方法の２つの手法を述べる．
3.1 ノードを枝刈りする手法
この手法では繰り返し計算のなかで関連度が 以上の関連度の高いノードからのみ関連度の伝搬値を計算し，結果高速に関連度の計算を行う．
Algorithm 2 にこの手法のアルゴリズムを示す．
ここで を枝刈り後のノードの集合とし， を枝刈りにおける閾値とする．まず関連度の分布 とノードの集合 をそれぞれ問い合わせ分布とノード全体の集合に初期化する（1～2 行目）．繰り返し計算の中で各ノードからの伝搬値は全てのノードからでなく，枝刈り後のノードの集合から計算する（7～12 行目）．枝刈り後のノードの集合は各繰り返し計算の中で更新された関連度から求める（15～20 行目）．
3.2 エッジを枝刈りする手法
この手法は関連度の伝搬値の小さなエッジを枝刈りする．すなわち各ノードから伝搬値を計算する過程でその後に計算する伝搬値が小さくなることがわかった段階で計算を枝刈りし，高速な関連度の計算を行う．
Algorithm 3 にこの手法におけるアルゴリズムを示す．まず関連度の分布 を問い合わせ分布に初期化する（１行目）．そして繰り返し計算のなかで効率的な計算の枝刈りを行うために，各ノードに対してそれらのノードから出ているノードをエッジの重みが大きい順で並び替える（2～Efficient computation for Personalized PageRank†Yasuhiro Fujiwara, NTT Software Innovation Center

1-537

Copyright 2013 Information Processing Society of Japan.
All Rights Reserved.

情報処理学会第 75 回全国大会

表 1 実験結果
4 行目）．繰り返し計算のなかでは各ノードから他のノードへの伝搬値を計算するが（11～12 行目），もし計算された伝搬値が より小さければそ の ノ ード か らの 伝 搬値 の 計 算を 枝 刈り する（13～15 行目）．これはエッジが重みの大きい他のノードへの伝搬値を計算するが（11～12 行目），もし計算された伝搬値が より小さければそ の ノ ード か らの 伝 搬値 の 計 算を 枝 刈り する（13～15 行目）．これはエッジが重みの大きい順に並び替えられているため，その後に計算される伝搬量が より大きくならないからである．
この手法は伝搬量が小さいエッジを効率的に枝刈りできるため，高速に関連度を計算できる．
4. 実験結果
提案手法の有効性を確認するために実験を行った．結果を表 1 に示す．実験では各手法の計算時間と計算により得られた関連度の平均誤差を調べた．実験データとしてはヨーロッパにおける研究機関から得られたメールのデータを用いた．このデータにおいてノード数はでエッジ数である．実験においては，とし，ランダムウォークを開始するノードはランダムに１つ設定した．またノードの枝刈りによる手法とエッジの枝刈りによる手法においては枝刈りの閾値 を及びにして実験を行った．
実験結果から提案手法はオリジナルの手法と比較して高速に関連度を計算できることがわかる．
また同時に枝刈りの閾値が大きいほうがより高計算時間[s]平均誤差

ノード枝刈りエッジ枝刈りθ =10-3
θ =10-7
θ =10-3
θ =10-7
0.05
0.46
0.93
0.96
3.15･10 -8
4.81･10 -11
3.54･10 -8
3.17･10 -10

オリジナル
1.01
-

速な関連度の計算が可能であることがわかる．
これは閾値が大きい方がより多くのノードまたはエッジを枝刈りできるからである．
また結果から提案手法における関連度の誤差は非常に小さい値になることがわかる．提案手法
はノードまたはエッジを枝刈りするが，関連度の値に影響がないようにしているからである．
また結果から提案手法は閾値が小さい方がより高い精度で関連度を計算できることがわかる．
これは閾値が小さい方がより多くのノードまたはエッジが計算対象となるため，関連度の計算精度が向上するためである．
これらの結果から本発明において高速な計算を行いたい場合は閾値を大きくし，高精度な計算を行いたい場合は閾値を小さくすればいいことがわかる．
5. まとめ
本論文では PPR に対する高速な関連度の計算方法を提案した．実験から提案手法は関連度の精度はそれほど犠牲にせずに計算時間を削減できることを示した．
6. 参考文献[1] Jeh et al., “Scaling Personalized Web Search”,
WWW 2003[2] Fujiwara et al., “Efficient Personalized
PageRank with Accuracy Assurance”, KDD 2012

1-538

Copyright 2013 Information Processing Society of Japan.
All Rights Reserved.