PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

えいしろうちゅうか
4 years ago
Views:

1 ERATO 感謝祭 SeasonII Efficient PageRank Tracking in Evolving Networks KDD st ACM SIGKDD Conference on Knowledge Discovery and Data Mining 大坂直人 ( 東京大学 / プロジェクト RA) 前原貴憲 ( 静岡大学 ) 河原林健一 (NII)

2 はじめに PageRank と Personalized PageRank PageRank [Brin-Page. 98] Web ページの重要度の指標リンク構造だけから決まる一般化 Personalized PageRank [Jeh-Widom. 03] バイアス付き関連度昨年の感謝祭静的グラフ上の高速計算 [Maehara-Akiba-Iwata-Kawarabayashi. PVLDB 14] 2

3 はじめに Evolving Networks 動的グラフ t = 1 t = 2 t = 3 World Wide Web 新しいページリンク 60 万ページ / 秒ソーシャルネットワーク新しい友人関係マイクロブログユーザ同士のやりとり 5000ツイート / 秒グラフ全体を見ずに更新したい 3

4 はじめに関連度としての応用スパム検知スコアの時間変化を利用 [Chung-Toyoda-Kitsuregawa. 09, 10] ユーザ推薦友達の候補生成 [Gupta-Goel-Lin-Sharma-Wang- Zadeh. WWW 13] 普通のページスパム Link Farm 普通に見える 4

5 はじめに Personalized PageRank 追跡の既存手法 m 辺の無作為挿入の時間スケーラビリティ 0.1 秒以下 / 辺誤差約 10-9 Aggregation/Disaggregation [Chien et al. 04] O m S log 1/ε 68M 辺 Monte-Carlo [Bahmani et al. 10] Power method ナイーブな手法 O(m + log m /ε 2 ) O m 2 log 1/ε 68M 辺 11M 辺

6 本研究の貢献成長するグラフにおける Personalized PageRank 追跡のための高速 & 高精度な手法を提案提案手法平均 m 辺の無作為挿入の時間 O m + Δ log m /ε スケーラビリティ 0.1 秒以下 / 辺誤差約 ,700M 辺 Aggregation/Disaggregation [Chien et al. 04] O m S log 1/ε 68M 辺 Monte-Carlo [Bahmani et al. 10] Power method ナイーブな手法最大出次数 O(m + log m /ε 2 ) O m 2 log 1/ε 68M 辺 11M 辺

7 予備知識 7

8 予備知識 Personalized PageRank の定義 [Brin-Page. Comput. Networks ISDN Syst. 98] [Jeh-Widom. WWW 03] 線形方程式次の解バイアス x = αpx + 1 α b 確率遷移行列 Random walk による解釈非ジャンプ確率 = 0.85 定常分布 Random walkによるweb 閲覧のモデル化無作為に隣接頂点に移動 w.p. α 無作為に任意頂点にジャンプ w.p. 1 α x v = v を訪れる確率分布 b R n JUMP! e d a c JUMP! b JUMP!

9 予備知識静的グラフ上の PageRank の計算線形方程式 x = αpx + 1 α b を解く Power method x (ν) = αpx ν α b v を訪れる割合 x v を見積もる Monte-Carlo シミュレーション 9

10 予備知識動的グラフ上の PageRank の追跡 Aggregation/disaggregation [Chien-Dwork-Kumar-Simon-Sivakumar. Internet Math. 04] 変化のあった近傍に Power method を適用大きい Monte-Carlo ベース [Bahmani-Chowdhury. VLDB 10] Random walk の軌跡を保持更新沢山必要 10

11 提案手法 11

12 提案手法問題設定時刻 0 の入力 : G(0) G(0) 時刻 0 の問題 : G(0) の PageRank x 0 の近似計算 x 0 x 0 < ε G(t 1) 時刻 t 1 の問題 : G(t 1) の PageRank x t 1 の近似計算 G(t) 時刻 tの入力 : 追加 / 削除される辺集合時刻 tの問題 : G(t) の PageRank x t の近似計算 12

13 提案手法そのアイデア x t = αp t x t + 1 α b を解く 1. x(t 1) は x(t) の良い初期近似解 2. 近似解を局所的に改善できないか? 挿入誤差 < ε 誤差 ε Gauss-Southwell 法を採用別名 Local algorithm [Spielman-Teng. SIAM J. Comput. 13] Bookmark coloring algorithm [Berkhin. Internet Math. 06] [Southwell. 40, 46] 13

14 提案手法 Gauss-Southwell 法 [Southwell. 40, 46] ν th 近似解 x ν ν th 残差 r (ν) = 1 α b I αp x ν ν = 1,2,3, i r i ν 1 If r i ν 1 r i ν できるだけ 0 に近づけるが最大の頂点 < ε terminate = 0 となるよう x (ν 1) と r (ν 1) を局所的に更新 u 残差 +α 次数 v 残差 +α 次数 i 残差 +α 次数 w 近似保証 : x x ν ε 1 α 14

15 提案手法 Gauss-Southwell 法 [Southwell. 40, 46] ν th 近似解 x ν ν th 残差 r (ν) = 1 α b I αp x ν できるだけ0に近づける ν = 1,2,3, i r i ν 1 If r i ν 1 が最大の頂点 < ε terminate x ν = x ν 1 + r i (ν 1) ei r (ν) = r ν 1 r i (ν 1) ei + αr i (ν 1) Pei は r ν 1 1 を 1 α ε 以上減らす r 0 1 α ε 回 15

16 提案手法その概観時刻 t: x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用 16

17 提案手法挙動時刻 t: x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用辺挿入残差 < ε 残差 ε 17

18 提案手法挙動時刻 t: x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用残差 < ε 残差 ε 18

19 提案手法挙動時刻 t: x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用 ν = 1 伝播 i 残差 < ε 残差 ε 19

20 提案手法挙動時刻 t: x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用 ν = 2 残差 < ε 残差 ε i 20

21 提案手法性能解析時刻 t: x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用は効率的に計算可辺 vw の追加 / 削除は O d v / /2 0 1/ /2 0 P(t 1) 時間 / / /3 0 1/ /3 0 P(t) / / /6 0 P t P(t 1) 21

22 提案手法性能解析時刻 t: 残差の増分 1 はどの位? x t (0) = x t 1 r t 0 = r t 1 + α P t P t 1 x t 1 Gauss-Southwell 法を適用各時刻で単一辺が無作為に挿入 G(0) G(1) G(m) 辺集合 = 1 辺足す m 辺足し終えた E 時刻 t での残差の増分 2α/t 22

23 提案手法性能解析 Gauss-Southwell 法を適用定理 1. 任意の変更に対する反復回数はならし O(1/ε) ならし時間は O(Δ/ε) 定理 2. m 辺を無作為逐次的に挿入期待総反復回数は O(log m /ε) 期待総時間は O(m + Δ log m /ε) Δ = 最大出次数 u 残差 +α 次数 v 残差 +α 次数 i 残差 +α 次数 w 23

24 実験 24

25 実験設定 : 単一辺挿入の性能評価 G(0) G(1) G(10 5 ) 全体のグラフから 100,000 辺抜いた 1 辺足す時刻無し : 無作為時刻付き : 時刻順 100,000 辺足し終えたパラメータ設定 α = 0.85 b = 100 要素が非ゼロのベクトル ε =

26 実験性能評価 : 単一辺挿入の平均時間 & 反復回数データセット [ 出典 ] 頂点数 V 辺数 E 最大出次数 Δ 平均時間平均反復回数 wiki-talk [SNAP] 2M 5M 100, μs 2.3 web-google [SNAP] 1M 5M 3, μs 22.6 as-skitter [SNAP] 2M 11M 35, μs 0.8 Flickr 時刻 [KONECT] 2M 33M 26, μs 16.2 Wikipedia 時刻 [KONECT] 2M 40M 6, μs 46.0 soc-livejournal1 [SNAP] 5M 68M 20, μs 7.6 twitter-2010 [LAW] 42M 1,500M 2,997,469 29,382.8 μs 0.7 uk [LAW] 105M 3,700M 15, μs 0.0 [KONECT] The Koblenz Network Collection [LAW] Laboratory for Web Algorithmics [SNAP] Stanford Large Network Dataset Collection Environment: Intel Xeon E GHz CPU with 256GB memory

27 実験性能評価 : 辺数と反復回数の関係 O E 1 辺挿入あたりの平均反復回数辺数辺が多いほど少ない Environment: Intel Xeon E GHz CPU with 256GB memory 15 グラフの結果 27

28 実験性能評価 : 単一辺挿入の平均時間 & 反復回数データセット [ 出典 ] 頂点数 V 辺数 E 最大出次数 Δ 平均時間平均反復回数 wiki-talk [SNAP] 2M 5M 100, μs 2.3 web-google [SNAP] 1M 5M 3, μs 22.6 as-skitter [SNAP] 2M 11M 35, μs 0.8 Flickr 時刻 [KONECT] 2M 33M 26, μs 16.2 Wikipedia 時刻 [KONECT] 2M 40M 6, μs 46.0 soc-livejournal1 [SNAP] 5M 68M 20, μs 7.6 twitter-2010 [LAW] 42M 1,500M 2,997,469 29,382.8 μs 0.7 uk [LAW] 105M 3,700M 15, μs 0.0 [KONECT] The Koblenz Network Collection [LAW] Laboratory for Web Algorithmics [SNAP] Stanford Large Network Dataset Collection Environment: Intel Xeon E GHz CPU with 256GB memory

29 実験性能評価 : 単一辺挿入の平均時間 & 反復回数データセット [ 出典 ] 頂点数 V 辺数 E 最大出次数 Δ 平均時間平均反復回数 wiki-talk [SNAP] 2M 5M 100, μs 2.3 web-google [SNAP] 1M 5M 3, μs 22.6 as-skitter [SNAP] 2M 11M 35, μs 0.8 Flickr 時刻 [KONECT] 2M 33M 26, μs 16.2 Wikipedia 時刻 [KONECT] 2M 40M 6, μs 46.0 soc-livejournal1 [SNAP] 5M 68M 20, μs 7.6 twitter-2010 [LAW] 42M 1,500M 2,997,469 29,382.8 μs 0.7 uk [LAW] 105M 3,700M 15, μs 0.0 [KONECT] The Koblenz Network Collection [LAW] Laboratory for Web Algorithmics [SNAP] Stanford Large Network Dataset Collection Environment: Intel Xeon E GHz CPU with 256GB memory

30 実験次数分布の違い twitter-2010 u, v vがuをフォロー uk u, v ページuからvへリンク出次数 k の頂点数 k 30

31 実験既存手法との比較 : 単一辺挿入の平均時間 web-google [SNAP] V =1M E =5M Wikipedia [KONECT] V =2M E =40M uk [LAW] V =105M E =3,700M 提案手法 7 μs 77 μs 2.3 μs Aggregation/Disaggregation [Chien et al. 04] 320 μs 40,336 μs >100,000 μs Monte-Carlo [Bahmani et al. 10] Warm start power method 444 μs 9,196 μs >100,000 μs 80,994 μs >100,000 μs >100,000 μs From scratch power method >100,000 μs >100,000 μs >100,000 μs Environment: Intel Xeon E GHz CPU with 256GB memory

32 実験既存手法との比較 : 精度提案手法 Aggregation/Disaggregation [Chien et al. 04] Monte-Carlo [Bahmani et al. 10] Warm start (power method) From scratch (power method) 平均 L 1 誤差の遷移 soc-epinions1[snap] V =76K E =509K Wikipedia[KONECT] V =2M E =40M 愚直な手法に匹敵 (~10-9 ) Environment: Intel Xeon E GHz CPU with 256GB memory 32

33 まとめ成長するネットワークにおける Personalized PageRank 追跡のための高速 & 高精度な手法を提案理論的任意の変更にならしO(Δ/ε) 時間 m 辺の無作為挿入に期待 O(m + Δ log m /ε) 時間 x x ε 実験的 37 億辺をもつグラフへの単一辺挿入に3μs 10-9 L 1 誤差 33

34 KDD 15 は来週シドニー

にゃんぱすー

にゃんぱすービッグデータ分析技術ワークショップ ~ グラフマイニング研究の最新動向と応用事例 ~ 平成 28 年 2 月 28 日頂点順序の最適化による高速なグラフ分析新井淳也日本電信電話株式会社ソフトウェアイノベーションセンタこの発表について下記論文についての発表です Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis