ERATO感謝祭SeasonII

Efficient PageRank Tracking
in Evolving Networks
KDD’1521st ACM SIGKDD Conference on
Knowledge Discovery and Data Mining

大坂 直人 (東京大学／プロジェクト RA)
前原 貴憲 (静岡大学)
河原林 健一 (NII)はじめに

PageRankとPersonalized PageRankPageRank [Brin-Page.’98]
Webページの重要度の指標
リンク構造だけから決まる
一般化

Personalized PageRank[Jeh-Widom.’03]

バイアス付き ⇨ 関連度
昨年の感謝祭…静的グラフ上の高速計算[Maehara-Akiba-Iwata-Kawarabayashi. PVLDB’14]2

はじめにEvolving Networks … 動的グラフ
0.21

0.25

0.23

𝒕=𝟏𝒕=𝟐
 World Wide Web
新しいページ・リンク 60万ページ／秒𝒕=𝟑

http://www.internetlivestats.com/

ソーシャルネットワーク
新しい友人関係 マイクロブログ
ユーザ同士のやりとり


5000ツイート／秒

http://www.technologyreview.com/graphiti/522376/the-many-tongues-of-twitter/

グラフ全体を見ずに更新したい3

はじめに関連度としての応用
スパム検知

ユーザ推薦

スコアの時間変化を利用

友達の候補生成[Chung-Toyoda-Kitsuregawa. ’09, ’10]

[Gupta-Goel-Lin-Sharma-WangZadeh. WWW’13]

普通のページ
スパム

Link Farm
普通に見える4

はじめにPersonalized PageRank追跡の既存手法

𝒎辺の無作為挿入の時間
Aggregation/Disaggregation[Chien et al. ’04]

Monte-Carlo[Bahmani et al. ’10]

Power method
ナイーブな手法

スケーラビリティ
0.1秒以下 / 辺
誤差約10-9𝒪 𝒎 𝑺 log 1/𝜖68M 辺𝒪(𝑚 + log 𝑚 /𝝐𝟐 )68M 辺𝒪 𝒎𝟐 log 1/𝜖11M 辺本研究の貢献

成長するグラフにおけるPersonalized PageRank 追跡のための高速 & 高精度 な手法を提案
𝒎辺の無作為挿入の時間

提案手法
Aggregation/Disaggregation[Chien et al. ’04]

Monte-Carlo[Bahmani et al. ’10]

Power method
ナイーブな手法

平均⇩ 最大出次数𝓞 𝒎 + 𝚫 𝐥𝐨𝐠 𝒎 /𝝐

スケーラビリティ
0.1秒以下 / 辺
誤差約10-93,700M 辺𝒪 𝒎 𝑺 log 1/𝜖68M 辺𝒪(𝑚 + log 𝑚 /𝝐𝟐 )68M 辺𝒪 𝒎𝟐 log 1/𝜖11M 辺

予備知識
7

予備知識

Personalized PageRank の定義[Brin-Page. Comput. Networks ISDN Syst.’98] [Jeh-Widom. WWW’03]
線形方程式
次の解

バイアス𝒙 = 𝜶𝑷𝒙 + 𝟏 − 𝜶 𝒃
確率遷移行列Random walkによる解釈

非ジャンプ確率 = 0.85

定常分布

Random walkによるWeb閲覧のモデル化
𝒂JUMP!
無作為に隣接頂点に移動
w.p. 𝛼
無作為に任意頂点にジャンプ
w.p. 1 − 𝛼 𝒆𝑛JUMP!

𝒃分布 𝑏 ∈ ℝ

𝑥𝑣 = 𝑣 を訪れる確率

JUMP!

𝒅𝒄

予備知識

静的グラフ上のPageRankの計算


線形方程式 𝑥 = 𝛼𝑃𝑥 + 1 − 𝛼 𝑏 を解く
Power method 𝑥 (𝜈) = 𝛼𝑃𝑥 𝜈−1 + 1 − 𝛼 𝑏𝑣 を訪れる割合 𝑥𝑣 を見積もる
Monte-Carlo シミュレーション

9

予備知識

動的グラフ上のPageRankの追跡Aggregation/disaggregation[Chien-Dwork-Kumar-Simon-Sivakumar. Internet Math.’04]

変化のあった近傍にPower methodを適用Monte-Carlo ベース

大きい[Bahmani-Chowdhury. VLDB’10]

Random walkの軌跡を保持・更新
沢山必要
10

提案手法
11

提案手法

問題設定
時刻0の入力 : 𝐺(0)
時刻0の問題 :𝑮(𝟎)𝐺(0) の PageRank 𝑥 0 の近似計算
𝒙 𝟎 − 𝒙∗ 𝟎∞ <𝝐…

𝑮(𝒕 − 𝟏)𝑮(𝒕)時刻𝑡 − 1の問題 :𝐺(𝑡 − 1) の PageRank 𝑥 𝑡 − 1 の近似計算
時刻𝑡の入力 :追加／削除される辺集合
時刻𝑡の問題 :𝐺(𝑡) の PageRank 𝑥 𝑡 の近似計算

12

提案手法

そのアイデア𝑥 𝑡 = 𝛼𝑃 𝑡 𝑥 𝑡 + 1 − 𝛼 𝑏を解く
1. 𝑥(𝑡 − 1)は𝑥(𝑡)の良い初期近似解
2. 近似解を局所的に改善できないか？
挿入誤差 < 𝜖誤差 ≥ 𝜖Gauss-Southwell 法 を採用  [Southwell. ’40, ’46]
別名 Local algorithm[Spielman-Teng. SIAM J. Comput.’13]

Bookmark coloring algorithm[Berkhin. Internet Math.’06]

13

提案手法

Gauss-Southwell 法 [Southwell. ’40, ’46]
𝜈th 近似解 𝑥 𝜈(𝜈) 𝜈 th 残差 𝑟
= 1 − 𝛼 𝑏 − 𝐼 − 𝛼𝑃 𝑥 𝜈

できるだけ𝟎に近づける𝜈 = 1,2,3, …
𝜈−1𝑖 ← 𝑟𝑖が最大の頂点
If 𝑟𝑖𝑟𝑖𝜈𝜈−1< 𝜖 terminate

𝒖+𝛼+𝛼残差次数𝒗

残差次数𝒊+𝛼残差次数𝒘= 0 となるよう 𝑥 (𝜈−1) と𝑟 (𝜈−1) を局所的に更新

近似保証: 𝒙 − 𝒙∗𝝂𝝐≤∞𝟏−𝜶14

提案手法

Gauss-Southwell 法 [Southwell. ’40, ’46]
𝜈th 近似解 𝑥 𝜈(𝜈) 𝜈 th 残差 𝑟
= 1 − 𝛼 𝑏 − 𝐼 − 𝛼𝑃 𝑥 𝜈

できるだけ𝟎に近づける𝜈 = 1,2,3, …
𝜈−1𝑖 ← 𝑟𝑖
が最大の頂点If 𝑟𝑖

𝜈−1< 𝜖 terminate(𝜈−1)𝑥 𝜈 = 𝑥 𝜈−1 + 𝑟𝑖𝑟 (𝜈) = 𝑟 𝜈−1

は 𝑟 𝜈−1≤𝒓𝟎
𝟏−𝜶 𝝐回𝑒𝑖(𝜈−1)(𝜈−1)− 𝑟𝑖
𝑒𝑖 + 𝛼𝑟𝑖𝑃𝑒𝑖を1−𝛼𝜖以上減らす
115

提案手法

その概観
時刻 𝑡:
𝑥 𝑡 (0) = 𝑥 𝑡 − 1𝑟 𝑡 0 =𝑟 𝑡−1 +𝛼 𝑃 𝑡 −𝑃 𝑡−1 𝑥 𝑡−1
Gauss-Southwell 法を適用

16

提案手法

挙動

時刻 𝑡:
𝑥 𝑡 (0) = 𝑥 𝑡 − 1𝑟 𝑡 0 =𝑟 𝑡−1 +𝛼 𝑃 𝑡 −𝑃 𝑡−1 𝑥 𝑡−1
Gauss-Southwell 法を適用
辺挿入

残差 < 𝜖残差 ≥ 𝜖17

提案手法

挙動

時刻 𝑡:
𝑥 𝑡 (0) = 𝑥 𝑡 − 1
𝒓 𝒕 𝟎 =𝒓 𝒕−𝟏 +𝜶 𝑷 𝒕 −𝑷 𝒕−𝟏 𝒙 𝒕−𝟏
Gauss-Southwell 法を適用
残差 < 𝜖残差 ≥ 𝜖18

提案手法

挙動

時刻 𝑡:
𝑥 𝑡 (0) = 𝑥 𝑡 − 1𝑟 𝑡 0 =𝑟 𝑡−1 +𝛼 𝑃 𝑡 −𝑃 𝑡−1 𝑥 𝑡−1
Gauss-Southwell 法を適用
𝝂=𝟏

伝播𝒊

残差 < 𝜖残差 ≥ 𝜖19

提案手法

挙動

時刻 𝑡:
𝑥 𝑡 (0) = 𝑥 𝑡 − 1𝑟 𝑡 0 =𝑟 𝑡−1 +𝛼 𝑃 𝑡 −𝑃 𝑡−1 𝑥 𝑡−1Gauss-Southwell 法を適用
𝝂=𝟐残差 < 𝜖残差 ≥ 𝜖𝒊20

提案手法

性能解析
時刻 𝑡:𝑥 𝑡 (0) = 𝑥 𝑡 − 1
𝑟 𝑡 0 =𝑟 𝑡−1 +𝜶 𝑷 𝒕 −𝑷 𝒕−𝟏 𝒙 𝒕−𝟏
Gauss-Southwell 法を適用は効率的に計算可辺𝑣𝑤 の追加／削除は 𝓞 𝒅𝒗 時間
01/2
01/2
000
1
000000
1

00
𝟏/𝟐
0𝟏/𝟐

𝑃(𝑡 − 1)

1000001/2
01/2
000
1
000000
1

𝑃(𝑡)

0𝟏/𝟑
𝟏/𝟑
0𝟏/𝟑

100000000000000000000
𝟏/𝟑−𝟏/𝟔
0−𝟏/𝟔00000𝑃 𝑡 − 𝑃(𝑡 − 1)

21

提案手法

性能解析
残差の増分 ⋅ 𝟏 はどの位？
時刻 𝑡:
𝑥 𝑡 (0) = 𝑥 𝑡 − 1
𝑟 𝑡 0 =𝑟 𝑡−1 +𝛼 𝑃 𝑡 −𝑃 𝑡−1 𝑥 𝑡−1
Gauss-Southwell 法を適用


各時刻で単一辺が無作為に挿入
𝑮(𝟎)

𝑮(𝟏)

辺集合= ∅

1辺足す

…

𝑮(𝒎)
𝑚辺足し終えた𝐄 時刻𝑡での残差の増分 ≤ 2𝛼/𝑡
22

提案手法

性能解析
Gauss-Southwell 法を適用


定理 1.
任意の変更に対する反復回数は ならし 𝓞(𝟏/𝝐)⇨ ならし時間は 𝓞(𝚫/𝝐) 定理 2.
𝒎辺を無作為・逐次的に挿入
期待総反復回数は 𝓞(𝐥𝐨𝐠 𝒎 /𝝐)⇨ 期待総時間は 𝓞(𝒎 + 𝚫 𝐥𝐨𝐠 𝒎 /𝝐)Δ = 最大出次数
𝒖+𝛼+𝛼

残差
次数𝒗

残差次数𝒊+𝛼残差
次数𝒘23

実験24

実験

設定: 単一辺挿入の性能評価
𝑮(𝟎)全体のグラフから100,000辺抜いた

𝑮(𝟏)

…

𝑮(𝟏𝟎𝟓 )

1辺足す

時刻無し: 無作為
時刻付き: 時刻順

100,000辺足し終えたパラメータ設定
 𝛼 = 0.85
 𝑏 = 100要素が非ゼロのベクトル

𝜖 = 10−925

実験

性能評価: 単一辺挿入の平均時間 & 反復回数
データセット [出典]

頂点数
𝑽

辺数
𝑬

最大出次数𝚫

平均時間

平均
反復回数

wiki-Talk [SNAP]

2M

5M

100,022589.6 μs

2.3

web-Google [SNAP]

1M

5M

3,444

7.2 μs22.6

as-Skitter [SNAP]

2M

11M

35,387288.4 μs

0.8Flickr時刻 [KONECT]

2M

33M

26,36795.3 μs

16.2Wikipedia時刻 [KONECT]

2M

40M

6,975

76.8 μs

46.0

soc-LiveJournal1 [SNAP]

5M

68M

20,29217.9 μs

7.6

twitter-2010 [LAW]

42M 1,500M 2,997,469 29,382.8 μs

0.7

uk-2007-05 [LAW]

105M 3,700M

2.3 μs0.0

15,402[KONECT] The Koblenz Network Collection http://konect.uni-koblenz.de/networks/[LAW] Laboratory for Web Algorithmics http://law.di.unimi.it/datasets.php[SNAP] Stanford Large Network Dataset Collection http://snap.stanford.edu/data/
Environment: Intel Xeon E5-2690 2.90GHz CPU with 256GB memory

実験

性能評価: 辺数と反復回数の関係𝒪 𝐸 −1
辺挿入あたりの平均反復回数

辺数15グラフの結果

辺が多いほど少ない
Environment: Intel Xeon E5-2690 2.90GHz CPU with 256GB memory

27実験

性能評価: 単一辺挿入の平均時間 & 反復回数
データセット [出典]

頂点数𝑽

辺数
𝑬

最大出次数𝚫

平均時間

平均反復回数wiki-Talk [SNAP]

2M

5M

100,022589.6 μs

2.3

web-Google [SNAP]

1M

5M

3,444

7.2 μs22.6

as-Skitter [SNAP]

2M

11M

35,387288.4 μs

0.8

Flickr時刻 [KONECT]

2M

33M

26,36795.3 μs

16.2

Wikipedia時刻[KONECT]

2M

40M

6,97576.8 μs

46.0

soc-LiveJournal1 [SNAP]

5M

68M

20,29217.9 μs

7.6

twitter-2010 [LAW]

42M 1,500M 2,997,469 29,382.8 μs

0.7

uk-2007-05 [LAW]

105M 3,700M

2.3 μs0.0

15,402[KONECT] The Koblenz Network Collection http://konect.uni-koblenz.de/networks/[LAW] Laboratory for Web Algorithmics http://law.di.unimi.it/datasets.php[SNAP] Stanford Large Network Dataset Collection http://snap.stanford.edu/data/
Environment: Intel Xeon E5-2690 2.90GHz CPU with 256GB memory

実験

性能評価: 単一辺挿入の平均時間 & 反復回数
データセット [出典]

頂点数
𝑽

辺数
𝑬

最大出次数𝚫

平均時間平均
反復回数

wiki-Talk [SNAP]

2M

5M

100,022589.6 μs

2.3

web-Google [SNAP]

1M

5M

3,444

7.2 μs22.6

as-Skitter [SNAP]

2M

11M

35,387288.4 μs

0.8

Flickr時刻 [KONECT]

2M

33M

26,36795.3 μs

16.2

Wikipedia時刻 [KONECT]

2M

40M

6,975

76.8 μs

46.0

soc-LiveJournal1 [SNAP]

5M

68M

20,29217.9 μs

7.6

twitter-2010 [LAW]

42M 1,500M 2,997,469 29,382.8 μs

0.7

uk-2007-05 [LAW]

105M 3,700M

2.3 μs0.0

15,402[KONECT] The Koblenz Network Collection http://konect.uni-koblenz.de/networks/[LAW] Laboratory for Web Algorithmics http://law.di.unimi.it/datasets.php[SNAP] Stanford Large Network Dataset Collection http://snap.stanford.edu/data/
Environment: Intel Xeon E5-2690 2.90GHz CPU with 256GB memory

実験

次数分布の違いtwitter-2010 𝑢, 𝑣 𝑣が𝑢をフォロー
uk-2007-05 𝑢, 𝑣 ページ𝑢から𝑣へリンク

出次数 ≥ 𝒌の頂点数

𝒌30

実験

既存手法との比較: 単一辺挿入の平均時間

提案手法
Aggregation/Disaggregation[Chien et al. ’04]

Monte-Carlo[Bahmani et al. ’10]

Warm start
power method

From scratch
power method

web-Google

Wikipedia

uk-2007-05[SNAP][KONECT]

[LAW]

𝑉 =1M
𝐸 =5M

𝑉 =2M
𝐸 =40M

𝑉 =105M
𝐸 =3,700M7 μs

77 μs

2.3 μs320 μs40,336 μs >100,000 μs

444 μs9,196 μs >100,000 μs

80,994 μs >100,000 μs >100,000 μs>100,000 μs >100,000 μs >100,000 μs

Environment: Intel Xeon E5-2690 2.90GHz CPU with 256GB memory

実験

既存手法との比較: 精度
提案手法
Aggregation/Disaggregation [Chien et al.’04]

Monte-Carlo [Bahmani et al.’10]
Warm start (power method)
From scratch (power method)

平均 𝐿1 誤差の遷移

soc-Epinions1[SNAP] 𝑉 =76K 𝐸 =509K

Wikipedia[KONECT] 𝑉 =2M 𝐸 =40M

愚直な手法に匹敵(~10-9)
Environment: Intel Xeon E5-2690 2.90GHz CPU with 256GB memory

32

まとめ
成長するネットワークにおけるPersonalized PageRank追跡のための高速 & 高精度な手法を提案
理論的任意の変更にならし𝓞(𝚫/𝝐)時間
𝒎辺の無作為挿入に期待𝓞(𝒎 + 𝚫 𝐥𝐨𝐠 𝒎 /𝝐)時間𝒙 − 𝒙∗ ∞ ≤ 𝝐
実験的37億辺をもつグラフへの単一辺挿入に3μs
10-9 𝐿1 誤差33

KDD’15は来週シドニー