規模グラフデータ分析 塩川浩昭筑波 学計算科学研究センター 計算情報学研究部 助教 第 8 回 学際計算科学による新たな知の発 統合 創出 シンポジウム 2016 年 10 18 1
Graph is everywhere l データエンティティと, データエンティティ間の関係性を表現した基本的なデータ構造のひとつ ノード エッジ 2
近にあるグラフデータ l 交通ネットワーク ノード : 駅 交差点など エッジ : 路線 道路など 3
近にあるグラフデータ l ソーシャルネットワーク Web グラフ ノード : Webページ エッジ : 間関係 リンク関係 4
グラフデータ分析の重要性 l グラフデータを分析することによりデータ間の関係性や類 似グループなどを発 代表的な分析技術 クラスタリング PageRank 最短経路探索 など Web/SNS コミュニティ抽出 男性俳優 性俳優 タンパク質相互作 NW 代謝に関わる酵素の特定 転写因 の特定 宝塚 男性 モデル タレント (バラエティ) ジャニーズ系 道路ネットワーク 混雑予測 交通案内 性 モデル 性 アナウンサー お笑い芸 ハロプロ 系 タレント (司会者) AKB 系 例. SNSからのコミュニティ抽出 5
規模グラフデータ分析 l 規模化に伴い分析に要する時間が爆発的に増加 分野種類ノード数 OR 等交通ネットワーク全 :2 10 % 以上 Web 等 物情報 ソーシャルネットワーク Web グラフ タンパク質間の相互作 脳神経ネットワーク Twitter:2 10 & 以上 Facebook:5 10 & 以上 Google:10 ( 以上 10 ( 以上 PFN 秋葉さんの資料より 億ノード規模以上 (10 8 以上 ) のグラフデータに対してどのようにしたら 速かつ 精度な分析ができるか? 6
規模グラフ分析への関 の まり l SIGMOD ( データベース分野のトップ会議 ) 2016 年では Graph Data セッションが 4 つ Query Processing と並ぶ巨 な勢 に l SC(HPC 分野のトップ会議 ) 2010 年頃から毎年 Graph Algorithms セッションが存在 7
HPC 分野における関 l Graph500 Top500 のあたらしい仲間 性能計算機をグラフ処理能 でランク付け 2016 年 6 時点で京コンピュータが 1 位 8
本 の本講演の概要 l グラフデータ分析技術を紹介 グラフクラスタリング分析を題材に最新の研究動向を解説するとともに, 性能計算機を いた今後の展望を述べる l グラフからコミュニティ構造 ( クラスタ ) を抽出するグラフ分析技術のひとつ 互いに密に接続したノード集合をクラスタとして抽出 SNS からのコミュニティ発 [Zhou et al. 2010] 脳神経ネットワークからの発 部位特定 [Yu et al. 2010] グラフクラスタリング 密なエッジ接続 疎なエッジ接続 9
クラスタリングの 2 つの課題 1. どんなクラスタを定義するか? 2. どうやって 速計算するか? 10
Min-cut / Normalized Cut 法 [Shi and Malik, TPAMIʻ01] l クラスタ間のエッジが最 クラスタ内のエッジが最 になるようにグラフを 2 分割にする 法 クラスタのサイズに偏りが発 してしまうため, クラスタの きさが均等になるように調整する 時間計算量は O(N 3 ) と きい クラスタの精度がイマイチ 事前にクラスタの個数を決めなければならない クラスタサイズは必ずしも均等ではない cut cut 11
Modularity クラスタリング l クラスタの質を表す指標 Modularity の最 化によるクラスタリング 法 M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004) Q = 0 e 22 2m a 2 2m 2 9 6 実際にクラスタ i に含まれるエッジ数の割合 実際のグラフのクラスタリング結果 ランダムグラフにおいてクラスタ i に含まれるエッジ数の割合 ランダムグラフのクラスタリング結果 どれだけ違うか 12
Modulraity クラスタリングの例 A 案 B 案 実際のグラフ ランダムグラフ A 案 =(3 本 -2 本 )+(1 本 -1 本 ) +(1 本 -1 本 )=1 本 B 案 = (6 本 -2 本 )+(3 本 -1 本 ) =5 本 最も直感に従った B 案が最も い値になっていることがわかる 13
クラスタリングの 2 つの課題 1. どんなクラスタを定義するか? 2. どうやって 速計算するか? 14
モジュラリティを いたコミュニティの抽出 l 最も単純な 法 全てのコミュニティのパターンを列挙して, モジュラリティが最も いものをみつける 2つのコミュニティを探す場合 % % <=> = 127 通り < 3 つのコミュニティを探す場合 % %@< A=> % < %@< A <=> = 1932 通り ノード数やコミュニティ数が増えると組合せ数が爆発的に増加し計算が終わらない 15
Modularity によるグラフクラスタリング Girvan-Newman 法 [Girvan et al., 2004] トップダウンにクラスタに存在しそうなエッジを削除する 法 1 時間当たりの処理データ量 1 万ノード 16
Girvan-Newman 法 [Girvan et al., 2004] l グラフから適当にエッジを削除してその時のModularityを評価 l Modularityが最も きくなったものを結果として出 Min-Max 法やNormalized-cutに近いトップダウン式の 法 計算量はO(N F ) と きい 小 Modularity Q 大 17
Modularity によるグラフクラスタリング Girvan-Newman 法 [Girvan et al., 2004] トップダウンにクラスタに存在しそうなエッジを削除する 法 Newman 法 [Newman et al., 2004] 貪欲法によりボトムアップからModularityを向上させる 法 CNM 法 [Clauset et al., 2004] ヒープの導 やヒューリスティクスによるNewman 法の 速化 1 時間当たりの処理データ量 1 万ノード 数百万ノード 18
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
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
Louvain 法 l 以下のパスを Modularity が向上する限り繰り返す 第 1 フェーズ : ノードのローカルクラスタリング ランダムな順序でノードを選択し, 選択したノードを Modularity が最も くなる隣接ノードと同 クラスタとする 第 2 フェーズ : クラスタに含まれるノードの 括集約 同 クラスタ内のノードとエッジを 括集約し重み付きグラフに変換 l 計算量は O(M) ただし定数項が極めて きい 12 2 6 1 1 1 第 1 フェーズ 第 2 フェーズ 3 14 2 第 2 パスへ処理を繰り返す 21
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
Incremental Aggregation [Shiokawa et al., AAAIʼ13] l 実世界のグラフデータが持つ構造特徴に着 グラフの Power-Law 特性とグラフのクラスタ性 上記の特徴に基づき不要な計算を削減する l グラフの Power-Law 特性 多数のノードは低次数で, ごく 部のノードのみ 次数となる l グラフのクラスタ性 隣接するノードペアは互いに多くの隣接ノードを共有する 23
Incremental Aggregation [Shiokawa et al., AAAIʼ13] l 逐次集約 (Incremental Aggregation) の提案 グラフのクラスタ性を利 した計算不要なエッジの集約 グラフの Power-Law 特性を利 した計算エッジ数の削減 24
グラフのクラスタ性をとらえる l クラスタが決定したノードを即座に集約する 同 クラスタを 1 ノード, エッジを重み付きエッジに変換することで, 計算対象となるノードとエッジを削減 逐次集約 同 クラスタと判明 2 2 集約されたノードとエッジ クラスタ内 : エッジ数の 2 倍クラスタ間 : エッジ数を加算 集約処理前 集約処理後 25
グラフの Power-law 特性を捉える l 次数の少ない順に計算対象ノードを選択する グラフデータ中から他ノードへの次数が少ないノードを優先選択することでモジュラリティの計算回数を抑制 p ノード A と B が同 のクラスタとなる場合 逐次集約 C A A 2 2 B D ノードAから選択エッジ3 本分計算 ノードBから選択エッジ2 本分計算 逐次集約による効果 次数の少ないノード B を選択したほうが効率が良い ノード A B 間のエッジが集約されるため, 後続の処理で計算が必要となるエッジ数を削減する C D 26
実データによる評価実験 l データセット Stanford Network Analysis Project および Laboratory of Web Algorithms から取得した 5 種類のデータセットを使 Dataset V E Skewness of degree distribution dblp 326,186 1,615,400 2.82 live 5,363,260 79,023,142 2.29 uk-2005 39,459,925 936,364,282 1.71 webbase 118,142,155 1,019,903,190 2.14 uk-2007 105,896,555 3,738,733,648 1.51 l 実験環境 Linux 2.6.18 server Intel Xeon CPU L5640 2.27GHz and 144GB RAM State of the art の 法 BGLL,CNM と 較 27
評価 1: 実 時間の 較 l 既存 法 BGLL と 較して最 60 倍 速 逐次集約のみ (Proposed-Limited) では約 20 倍の 速化 次数分布の偏りが きいグラフの 速化率が い傾向 1 億ノード /10 億エッジを 156 秒でクラスタリング 3.2 万ノードのグラフを 1 秒未満でクラスタリング 28
評価 2: クラスタリング結果のモジュラリティ l BGLL と 較してほぼ同程度のモジュラリティ値を すクラスタリング結果を得ることを確認 Incremental aggregation dblp live uk-2005 webbase uk-2007 0.90 0.74 0.98 0.98 0.97 BGLL 0.88 0.74 0.97 0.96 0.97 CNM 0.82 - - - - 29
さらなる 速化に向けて (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., IPDPSʼ16] Incremental Aggregation クラスタリング [Shiokawa et al, AAAIʼ13] の並列化実装を利 CAS を利 して分析結果の整合性を確保 高速化率 6 5 4 3 2 1 0 実効最大メモリ帯域 高速化率 l スパコン (COMA) を いた並列化 全コア合計消費メモリ帯域 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 H28 年度学際共同利 プログラム 46 規模グラフ分析アルゴリズムの 速化に関する研究 50 40 30 20 10 0 Read メモリ帯域 [GB/s] 31
まとめ l 本 の講演内容分析 グラフクラスタリングを題材に, 規模グラフ分析アルゴリズムの研究動向を紹介した l Interesting Open Problems スケーラブルなグラフ分析に向けたデータ構造とアルゴリズム 分析処理 法に応じて 幅に変わる Real-world property を捉えることが重要 分析アルゴリズムのツール化 Xeon Phi, GPU, etc. アプリケーション分野での応 命情報, 宇宙, 物理, 化学, 医療, 32