symposium_talk

Size: px

Start display at page:

Download "symposium_talk"

えりかみおか
6 years ago
Views:

1 規模グラフデータ分析塩川浩昭筑波学計算科学研究センター計算情報学研究部助教第 8 回学際計算科学による新たな知の発統合創出シンポジウム 2016 年

2 Graph is everywhere l データエンティティと, データエンティティ間の関係性を表現した基本的なデータ構造のひとつノードエッジ 2

3 近にあるグラフデータ l 交通ネットワークノード : 駅交差点などエッジ : 路線道路など 3

4 近にあるグラフデータ l ソーシャルネットワーク Web グラフノード : Webページエッジ : 間関係リンク関係 4

5 グラフデータ分析の重要性 l グラフデータを分析することによりデータ間の関係性や類似グループなどを発代表的な分析技術クラスタリング PageRank 最短経路探索など Web/SNS コミュニティ抽出男性俳優性俳優タンパク質相互作 NW 代謝に関わる酵素の特定転写因の特定宝塚男性モデルタレント (バラエティ) ジャニーズ系道路ネットワーク混雑予測交通案内性モデル性アナウンサーお笑い芸ハロプロ系タレント (司会者) AKB 系例. SNSからのコミュニティ抽出 5

6 規模グラフデータ分析 l 規模化に伴い分析に要する時間が爆発的に増加分野種類ノード数 OR 等交通ネットワーク全 :2 10 % 以上 Web 等物情報ソーシャルネットワーク Web グラフタンパク質間の相互作脳神経ネットワーク Twitter:2 10 & 以上 Facebook:5 10 & 以上 Google:10 ( 以上 10 ( 以上 PFN 秋葉さんの資料より億ノード規模以上 (10 8 以上 ) のグラフデータに対してどのようにしたら速かつ精度な分析ができるか? 6

7 規模グラフ分析への関のまり l SIGMOD ( データベース分野のトップ会議 ) 2016 年では Graph Data セッションが 4 つ Query Processing と並ぶ巨な勢に l SC(HPC 分野のトップ会議 ) 2010 年頃から毎年 Graph Algorithms セッションが存在 7

8 HPC 分野における関 l Graph500 Top500 のあたらしい仲間性能計算機をグラフ処理能でランク付け 2016 年 6 時点で京コンピュータが 1 位 8

互いに密に接続したノード集合をクラスタとして抽出 SNS からのコミュニティ発 [Zhou et al.

9 本の本講演の概要 l グラフデータ分析技術を紹介グラフクラスタリング分析を題材に最新の研究動向を解説するとともに, 性能計算機をいた今後の展望を述べる l グラフからコミュニティ構造 ( クラスタ ) を抽出するグラフ分析技術のひとつ互いに密に接続したノード集合をクラスタとして抽出 SNS からのコミュニティ発 [Zhou et al. 2010] 脳神経ネットワークからの発部位特定 [Yu et al. 2010] グラフクラスタリング密なエッジ接続疎なエッジ接続 9

10 クラスタリングの 2 つの課題 1. どんなクラスタを定義するか? 2. どうやって速計算するか? 10

11 Min-cut / Normalized Cut 法 [Shi and Malik, TPAMIʻ01] l クラスタ間のエッジが最クラスタ内のエッジが最になるようにグラフを 2 分割にする法クラスタのサイズに偏りが発してしまうため, クラスタのきさが均等になるように調整する時間計算量は O(N 3 ) ときいクラスタの精度がイマイチ事前にクラスタの個数を決めなければならないクラスタサイズは必ずしも均等ではない cut cut 11

Girvan, Finding and evaluating community structure in networks, Phys. Rev.

12 Modularity クラスタリング l クラスタの質を表す指標 Modularity の最化によるクラスタリング法 M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, (2004) Q = 0 e 22 2m a 2 2m 実際にクラスタ i に含まれるエッジ数の割合実際のグラフのクラスタリング結果ランダムグラフにおいてクラスタ i に含まれるエッジ数の割合ランダムグラフのクラスタリング結果どれだけ違うか 12

13 Modulraity クラスタリングの例 A 案 B 案実際のグラフランダムグラフ A 案 =(3 本 -2 本 )+(1 本 -1 本 ) +(1 本 -1 本 )=1 本 B 案 = (6 本 -2 本 )+(3 本 -1 本 ) =5 本最も直感に従った B 案が最もい値になっていることがわかる 13

14 クラスタリングの 2 つの課題 1. どんなクラスタを定義するか? 2. どうやって速計算するか? 14

15 モジュラリティをいたコミュニティの抽出 l 最も単純な法全てのコミュニティのパターンを列挙して, モジュラリティが最もいものをみつける 2つのコミュニティを探す場合 % % <=> = 127 通り < 3 つのコミュニティを探す場合 % %@< A=> % < %@< A <=> = 1932 通りノード数やコミュニティ数が増えると組合せ数が爆発的に増加し計算が終わらない 15

16 Modularity によるグラフクラスタリング Girvan-Newman 法 [Girvan et al., 2004] トップダウンにクラスタに存在しそうなエッジを削除する法 1 時間当たりの処理データ量 1 万ノード 16

17 Girvan-Newman 法 [Girvan et al., 2004] l グラフから適当にエッジを削除してその時のModularityを評価 l Modularityが最もきくなったものを結果として出 Min-Max 法やNormalized-cutに近いトップダウン式の法計算量はO(N F ) ときい小 Modularity Q 大 17

18 Modularity によるグラフクラスタリング Girvan-Newman 法 [Girvan et al., 2004] トップダウンにクラスタに存在しそうなエッジを削除する法 Newman 法 [Newman et al., 2004] 貪欲法によりボトムアップからModularityを向上させる法 CNM 法 [Clauset et al., 2004] ヒープの導やヒューリスティクスによるNewman 法の速化 1 時間当たりの処理データ量 1 万ノード数百万ノード 18

19 Newman 法 / CNM 法 l 2 つノードを同じクラスタにした時にじる Modularity の上昇量 Modularity gain Q を定義 Modularity Q = 0 e 22 2m a 2 2m 2 9 l Q を最にするノードペアを貪欲法で探索しクラスタリング l 計算量は O N 2 ~O(M log N) 6 Modularity gain Q 2A = 2{2me 2A a 2 a A } 19

20 Modularity によるグラフクラスタリング Girvan-Newman 法 [Girvan et al., 2004] トップダウンにクラスタに存在しそうなエッジを削除する法 Newman 法 [Newman et al., 2004] 貪欲法によりボトムアップからModularityを向上させる法 CNM 法 [Clauset et al., 2004] ヒープの導やヒューリスティクスによるNewman 法の速化 1 時間当たりの処理データ量 1 万ノード数百万ノード Louvain 法 [Blondel et al., 2008] 隣接するノード同にのみを計算する計算量のさな法最速かつ最精度の法として広く利されている数千万ノード 20

21 Louvain 法 l 以下のパスを Modularity が向上する限り繰り返す第 1 フェーズ : ノードのローカルクラスタリングランダムな順序でノードを選択し, 選択したノードを Modularity が最もくなる隣接ノードと同クラスタとする第 2 フェーズ : クラスタに含まれるノードの括集約同クラスタ内のノードとエッジを括集約し重み付きグラフに変換 l 計算量は O(M) ただし定数項が極めてきい第 1 フェーズ第 2 フェーズ第 2 パスへ処理を繰り返す 21

22 Modularity によるグラフクラスタリング Girvan-Newman 法 [Girvan et al., 2004] トップダウンにクラスタに存在しそうなエッジを削除する法 Newman 法 [Newman et al., 2004] 貪欲法によりボトムアップからModularityを向上させる法 CNM 法 [Clauset et al., 2004] ヒープの導やヒューリスティクスによるNewman 法の速化 1 時間当たりの処理データ量 1 万ノード数百万ノード Louvain 法 [Blondel et al., 2008] 隣接するノード同にのみを計算する計算量のさな法最速かつ最精度の法として広く利されている Incremental Aggregation 法既存技術と同程度の精度を保ち 10 倍 20 倍以上きなデータを処理性能標既存法 Louvain 法より 10 倍以上の速な法の確 1 千万ノード 1 億数億ノード 22

23 Incremental Aggregation [Shiokawa et al., AAAIʼ13] l 実世界のグラフデータが持つ構造特徴に着グラフの Power-Law 特性とグラフのクラスタ性上記の特徴に基づき不要な計算を削減する l グラフの Power-Law 特性多数のノードは低次数で, ごく部のノードのみ次数となる l グラフのクラスタ性隣接するノードペアは互いに多くの隣接ノードを共有する 23

24 Incremental Aggregation [Shiokawa et al., AAAIʼ13] l 逐次集約 (Incremental Aggregation) の提案グラフのクラスタ性を利した計算不要なエッジの集約グラフの Power-Law 特性を利した計算エッジ数の削減 24

25 グラフのクラスタ性をとらえる l クラスタが決定したノードを即座に集約する同クラスタを 1 ノード, エッジを重み付きエッジに変換することで, 計算対象となるノードとエッジを削減逐次集約同クラスタと判明 2 2 集約されたノードとエッジクラスタ内 : エッジ数の 2 倍クラスタ間 : エッジ数を加算集約処理前集約処理後 25

26 グラフの Power-law 特性を捉える l 次数の少ない順に計算対象ノードを選択するグラフデータ中から他ノードへの次数が少ないノードを優先選択することでモジュラリティの計算回数を抑制 p ノード A と B が同のクラスタとなる場合逐次集約 C A A 2 2 B D ノードAから選択エッジ3 本分計算ノードBから選択エッジ2 本分計算逐次集約による効果次数の少ないノード B を選択したほうが効率が良いノード A B 間のエッジが集約されるため, 後続の処理で計算が必要となるエッジ数を削減する C D 26

27 実データによる評価実験 l データセット Stanford Network Analysis Project および Laboratory of Web Algorithms から取得した 5 種類のデータセットを使 Dataset V E Skewness of degree distribution dblp 326,186 1,615, live 5,363,260 79,023, uk ,459, ,364, webbase 118,142,155 1,019,903, uk ,896,555 3,738,733, l 実験環境 Linux server Intel Xeon CPU L GHz and 144GB RAM State of the art の法 BGLL,CNM と較 27

28 評価 1: 実時間の較 l 既存法 BGLL と較して最 60 倍速逐次集約のみ (Proposed-Limited) では約 20 倍の速化次数分布の偏りがきいグラフの速化率がい傾向 1 億ノード /10 億エッジを 156 秒でクラスタリング 3.2 万ノードのグラフを 1 秒未満でクラスタリング 28

29 評価 2: クラスタリング結果のモジュラリティ l BGLL と較してほぼ同程度のモジュラリティ値をすクラスタリング結果を得ることを確認 Incremental aggregation dblp live uk-2005 webbase uk BGLL CNM

30 さらなる速化に向けて (1/2) l GPU をいた並列化 Single-GPU [Wu et al., 2010] グラフの固有値固有ベクトルをいたモジュラリティクラスタリングべき乗法による固有値固有ベクトルの計算を GPU で実装 Multi-GPU [Soman et al, 2011] Label propagation をモジュラリティクラスタリングに利した法 Label propagation 処理部を GPU で実装 l 分散メモリ環境における並列化 [Wickramaarachchi et al., 2014] グラフを最エッジカットで事前分割し分割統治的にクラスタを求める - [Bae and Bill, SCʼ15] グラフ並列処理フレームワーク GraphLab をいた実装 ParMETIS BGLL 1 BGLL 1 BGLL n BGLL 30

さらなる速化に向けて (2/2) l Multi-CPU をいた並列化 Rabbit Order [Arai et al.

AAAIʼ13] の並列化実装を利 CAS を利して分析結果の整合性を確保高速化率 6 5 4 3 2 1 0

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 H28 年度学際共同利

31 さらなる速化に向けて (2/2) l Multi-CPU をいた並列化 Rabbit Order [Arai et al., IPDPSʼ16] Incremental Aggregation クラスタリング [Shiokawa et al, AAAIʼ13] の並列化実装を利 CAS を利して分析結果の整合性を確保高速化率実効最大メモリ帯域高速化率 l スパコン (COMA) をいた並列化全コア合計消費メモリ帯域 H28 年度学際共同利プログラム 46 規模グラフ分析アルゴリズムの速化に関する研究 Read メモリ帯域 [GB/s] 31

32 まとめ l 本の講演内容分析グラフクラスタリングを題材に, 規模グラフ分析アルゴリズムの研究動向を紹介した l Interesting Open Problems スケーラブルなグラフ分析に向けたデータ構造とアルゴリズム分析処理法に応じて幅に変わる Real-world property を捉えることが重要分析アルゴリズムのツール化 Xeon Phi, GPU, etc. アプリケーション分野での応命情報, 宇宙, 物理, 化学, 医療, 32

にゃんぱすー

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