A Distributed Parallel Community Detection Heuristics for Large-scale Real Graphs
Download as PPTX, PDF0 likes167 views
分割データサイズのバランスにフォーカスを置いたコミュニティ抽出手法の并列分散化
![[DL輪読会]Depth Prediction Without the Sensors: Leveraging Structure for Unsuper...](https://cdn.slidesharecdn.com/ss_thumbnails/struct2depth0301-190304050917-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Similar to A Distributed Parallel Community Detection Heuristics for Large-scale Real Graphs (20)
A Distributed Parallel Community Detection Heuristics for Large-scale Real Graphs
- 1. Symposia on VLSI Technology and Circuits A Distributed Parallel Community Detection Heuristics for Large-scale Real Graphs Guanglong Chi1,a,b Ken Wakita2,a,b Hitoshi Sato3,a,b 1 Department of Human System Science 2 Department of Mathematical and Computing Science 3 Global Scientific Information and Computing Center a Tokyo Institute of Technology b JST, CREST
- 2. 社会ネットワークの コミュニティ発見法とその応用 ? コミュニティ発見法 – 内部では密、外部とは疎 に繋いでいるノード集まり を発見 ? 応用 – 検索エンジン ? 結果のまとめ表示 – イメージセグメンテーション – 社会ネットワーク解析 ? 共著者ネットワーク: 研究分野の抽出 ? タンパク質間相互作用 ネットワーク： 機能モジュールの抽出 協働ネットワーク イメージセグメンテーション タンパク質相互作用 ネットワーク
- 3. コミュニティ発見法の様々なアプローチ ? コミュニティ発見の基本的な手法 – GN法: Edge betweenness (Girvan+, PNAS `02) – Newman法：Modularity最適化 (Newman+, Phys.Rev.E `04) – SCD法: WCC最適化 (Prat-Pérez+, WWW `14) ? Modularity最適化法の高速化、共有メモリ並列化 – CNM法 (Clauset+, Phys. Rev.E `04) – WT法 (Wakita+, WWW `07) – Louvain法 (Blondel+, JSTAT `08)： 代表的な手法(高い精度、高速) – Shiokawa法 (Shiokawa+, AAAI `13) – BS法 (Bhowmick+, DOOCN `13) – LHK法 (Lu+, Parallel Computing `15) ? 分散メモリ並列化 – PMETISNC-Louvain法 (Wickramaarachchi+, HPEC `14)
- 4. 既存手法の問題点 ? 既存手法：PMETISNC-Louvain法 – Louvain法の分散メモリ並列化手法 – ノード分割手法(PMETIS)でデータを分割 – 各部分データにLouvain法を適応 ? 問題点 – PMETIS分割の結果: edge imbalance – Edge imbalanceの結果： ? time imbalance, memory imbalance→全体の性能低下 – 従って、Louvain法の分散メモリ並列化において、 エッジのバランスも必要
- 5. 本研究の提案と成果 ? 提案 – データ分割:エッジ分割(IC手法(Bourse+,SIGKDD’14)) – 分散手法: IC-Louvain法 ? 成果 – ノード分割手法のedge imbalance問題を示唆 – 分散手法: IC-Louvain法を作成 – Wiki, Pokecなど実グラフに対する評価 ? 最大メモリ使用量 31%(Wiki), 27%(Pokec) 削減 ? 最大待ち時間 93%(Wiki), 69%(Pokec) 削減 ? Bourse, F., Lelarge, M. and Vojnovic, M.: Balanced graph edge partition, ACM SIGKDD `14, pp. 1456–1465.
- 6. 発表の流れ ? Louvain法 ? 既存研究: PMETISNC-Louvain法とその問題点 ? IC-Louvain法 ? 実験 ? まとめ
- 7. Louvain法 (Blondel+, JSTAT `08) ? 代表的なコミュニティ発見法の一つ – Modularity最適化によりコミュニティを発見 – 最大一億ノード、十億エッジまで処理可能 – 高速、高精度 ? 様々なタイプのネットワークに対して応用 – モバイルネットワーク (Blondel+, JSTAT `08) – ツイッターネットワーク (Pujol+, CoRR `09) – 人間脳の機能的ネットワーク (Meunier+, Frontiers in neuroinformatics `09)
- 8. Modularity (Newman+, Phys.Rev.E `04) ? コミュニティ発見の善し悪しを評価する指標 ? コミュニティ i と j を繋ぐエッジ数が全エッジ数に おける割合 modularity = 0.448 modularity = 0.520 ei, j
- 9. Louvain法 ? 目的：modularityの極大化 によりコミュニティを発見 ? ステップ – 初期状態：各ノードを別のコ ミュニティ（色）にする – 一個のノードに注目し、各隣 接コミュニティと同じ色になっ た場合のmodularityを計算 – 最大のmodularityを持つ隣 接コミュニティと同じ色に塗る – 上の2ステップを色が変わら なくなるまで全ノードに対して 繰り返す Modularity1 = 0.181 Modularity2 = 0.241 Modularity3 = 0.203 Modularity4 = 0.193 色：コミュニティを表す
- 10. 既存の分散手法:PMETISNC-Louvain (Wickramaarachchi+, HPEC `14) ? 前処理： PMETISグラフノード分割 (Karypis+, SIAM `98) ? 理由： – ノード分割により、 計算ノードに跨る コミュニティ数が少なくなる – 計算ノード間の通信が 無視できる ? Wickramaarachchi, C., Frincu, M., Small, P. and Prasanna, V. K.: Fast parallel algorithm for unfolding of communities in large graphs, IEEE HPEC `14, pp.1–6. ? Karypis, G. and Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on scientific Computing, Vol. 20, No. 1, pp. 359–392 (1998).
- 11. Edge imbalance (Wiki #Nodes=2.4M / #Edges=9.4M) Thenumberofedges 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 平均エッジ数 = 582,445 ?29 最大エッジ数: 5,755,636 最小エッジ数: 196,996 Computing Node ID
- 12. 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 METIS IC Computing Node ID Thenumberofedges Edge imbalance -> Memory imbalance (Wiki #Nodes=2.4M / #Edges=9.4M) 平均エッジ数 = 582,445 ?29 最大エッジ数: 5,755,636 最小エッジ数: 196,996 IC手法により
- 13. Edge imbalance -> Time imbalance (Wiki #Nodes=2.4M / #Edges=9.4M) Computing Node ID Thenumberofedges 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 平均エッジ数 = 582,445 ?29 最大エッジ数: 5,755,636 最小エッジ数: 196,996 Louvain法計算時間:エッジ数に比例 ノード１６だけの単独実行
- 14. IC-Louvain法 ? 前処理 – 目的：Edge imbalanceを解消 – IC手法(Bourse SIGKDD’14)を用いてグラフを分割 ? 分散Louvain – 目的：分割されたデータの分散処理 – 計算： ? 各計算ノードでLouvain法で計算 – 通信： ? 全ノードが一度処理された時点で集団通信 ? コミュニティIDとコミュニティ重みの同期
- 15. IC-Louvain法 ? 前処理 – 目的：Edge imbalanceを解消 – IC手法(Bourse SIGKDD’14)を用いてグラフを分割 ? 分散Louvain – 目的：分割されたデータの分散処理 – 計算： ? 各計算ノードでLouvain法で計算 – 通信： ? 全ノードが一度処理された時点で集団通信 ? コミュニティIDとコミュニティ重みの同期
- 17. 前処理: IC手法 ノード分割 (PMETIS) エッジ分割 (IC手法) オリジナル ノード レプリカ ノード #通信コス ト PMETIS 10 IC手法 9
- 18. 前処理: IC手法 ノード分割 (PMETIS) エッジ分割 (IC手法) #Node #Edge PMETIS 10/9 11/23 IC手法 14/14 18/16
- 19. IC-Louvain法 ? 前処理 – 目的：Edge imbalanceを解消 – IC手法(Bourse SIGKDD’14)を用いてグラフを分割 ? 分散Louvain – 目的：分割されたデータの分散処理 – 計算： ? 各計算ノードにおいてLouvain法で計算 – 通信： ? 全ノードが一度処理された時点で集団通信 ? コミュニティIDとコミュニティ重みの同期
- 20. 分散Louvainの通信: コミュニティID(色)の同期 全ノード一回の計算 ? 理由：計算終了時 オリジナル ノードと レプリカ ノードの色が違う 可能性 ? 色の決め方： ? もっとも大きい modularityを持つ色を 塗る ? 通信回数: ? ２回、modularity値の 収集、コミュニティ色の 配布 ? ノード分割、１回 計算ノード１ 計算ノード2 オリジナル レプリカ
- 21. 分散Louvainの通信: コミュニティID(色)の同期 全ノード一回の計算 計算ノード１ 計算ノード2 オリジナル レプリカ ? 理由：計算終了時 オリジナル ノードと レプリカ ノードの色が違う 可能性 ? 色の決め方： ? もっとも大きい modularityを持つ色を 塗る ? 通信回数: ? ２回、modularity値の 収集、コミュニティ色の 配布 ? ノード分割、１回
- 22. 分散Louvainの通信: コミュニティ重みの同期 ? 方法： ? 各計算ノードで コミュニティの重みを 集計 ? ある範囲内の コミュニティの重みを 決まった計算ノードに 収集、集計 ? 集まったコミュニティ 重みを配布 コミュニティ重みの 収集、集計 p1 p2p1 p2 + Wgreen (P2 )Wgreen (P1) +Wyellow (P2 )Wyellow (P1) + Wblue (P2 )Wblue (P1) +Wwhite(P2 )Wwhite(P1)
- 23. 分散Louvainの通信: コミュニティ重みの同期 コミュニティ重みの 配布 p1 p2p1 p2 ? 方法： ? 各計算ノードで コミュニティの重みを 集計 ? ある範囲内の コミュニティの重みを 決まった計算ノードに 収集、集計 ? 集まったコミュニティ 重みを配布 + Wgreen (P2 )Wgreen (P1) +Wyellow (P2 )Wyellow (P1) + Wblue (P2 )Wblue (P1) +Wwhite(P2 )Wwhite(P1)
- 24. コミュニティ重み情報の分割 ? 各計算ノードで処理する コミュニティの範囲 ? コミュニティIDにより割り 当てる ? この例では、 温かい色 P1、 冷たい色 P2 p1 p2 p1 p2p1 p2 コミュニティ重みの 収集
- 25. 実験 ? 目的 – IC手法を用いたエッジ分割の有効性 – 分散Louvainの有効性 ? 内容 – (PMETISとIC手法)ロードバランスと通信コストの比較 – 計算ノードごとのメモリ使用量、実行時間の内訳 – 通信時間の内訳、modularity ? 対象 – IC-Louvainと既存手法に通信部分を加えた PMETISC-Louvain
- 26. 実験 ? データセット ? 環境 – TSUBAME THIN node (x2): 54GB memory, two six-core Intel Xeon X5670 2.93GHZ processors ? 実装 – X10 v2.3.1 (Extended) Description #Nodes #Edges Wiki Communication 2,394,385 9,319,130 Pokec Social Media 1,632,803 44,603,928
- 27. ICとPMETISの比較 ? 16分割した場合、 ? #Edge差： 三十倍近い ? ノード数が増えるが、#Node差 < #Edge差のため、メモリ削減が可能 ? Edge imbalanceがない場合: – Pokec: 8分割の場合 – Amazon(334k, 1.9M): 何分割しても データ 分割手法 平均ノード数 通 信 コ ス ト (個) Wiki IC手法 164,801 1 239,228 PMETIS手法 149,650 29 2,420,369 Pokec IC手法 418,416 1 5,062,565 PMETIS手法 102,051 28 10,218,119 #Edgesmax #Edgesmin
- 28. メモリ使用量 (Wiki #Nodes=2.4M / #Edges=9.4M) PMETISC-Louvain IC-Louvain Memory consumption (MB) ComputingnodeID 0 50 100 150 200 250 300 350 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Memory consumption (MB) ComputingnodeID 0 50 100 150 200 250 300 350 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Graph data Replica Communication buffer
- 29. ComputingnodeID Memory consumption (MB) 0 50 100 150 200 250 300 350 400 450 500 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 メモリ使用量 (Pokec #Nodes=1.6M / #Edges=44.6M) PMETISC-Louvain IC-Louvain Graph data Replica Communication buffer ComputingnodeID Memory consumption (MB) 0 50 100 150 200 250 300 350 400 450 500 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- 30. Time (s) ComputingnodeID 0 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 実行時間の内訳 (Wiki #Nodes=2.4M / #Edges=9.4M) PMETISC-Louvain IC-Louvain Compute time Wait time Communication time Time (s) ComputingnodeID 0 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- 31. Compute time Wait time Communication time Time (s) ComputingnodeID 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 実行時間の内訳 (Pokec #Nodes=1.6M / #Edges=44.6M) PMETISC-Louvain IC-Louvain Time (s) ComputingnodeID 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- 32. 通信時間の内訳 時間 (ms) 0 200 400 600 800 1000 1200 1400 1600 1800 Pokec, IC Pokec, PMETIS Wiki, IC Wiki, PMETIS コミュニティIDの同期 コミュニティ重みの同期
- 33. 通信時間の内訳 時間 (ms) 0 200 400 600 800 1000 1200 1400 1600 1800 Pokec, IC Pokec, PMETIS Wiki, IC Wiki, PMETIS コミュニティIDの同期 コミュニティ重みの同期 ? コミュニティ ID同期時間差 ? 通信回数: ? PMETIS-Louvain 1回 ? IC-Louvain 2回 ? 通信必要なレプリカ（ノード）数 ? Wiki: PMETISC-Louvainの10% ? Pokec: PMETISC-Louvainの45％ ? 通信範囲 ? PMETISC-Louvain: 変更レプリカのみ ? IC-Louvain: 全レプリカ
- 34. 通信時間の内訳 時間 (ms) 0 200 400 600 800 1000 1200 1400 1600 1800 Pokec, IC Pokec, PMETIS Wiki, IC Wiki, PMETIS コミュニティIDの同期 コミュニティ重みの同期
- 35. 通信時間の内訳 時間 (ms) 0 200 400 600 800 1000 1200 1400 1600 1800 Pokec, IC Pokec, PMETIS Wiki, IC Wiki, PMETIS コミュニティIDの同期 コミュニティ重みの同期 ? コミュニティ 重み同期時間差 ? 発見されたコミュニティ数 ? Wiki: ? 両手法とも同じぐらいの数 ? Pokec: ? PMETISC-Louvain ノード数の2% ? IC-Louvain ノード数の16%
- 36. 実験結果の概略 Modularity コミュニティ数 Wiki PMETISC-Louvain 0.58 2,808 Wiki IC-Louvain 0.58 2,847 Pokec PMETISC-Louvain 0.70 44 Pokec IC-Louvain 0.68 862
- 37. 議論 ? エッジ分割（IC手法） – メモリと計算時間のimbalanceを解消 – レプリカ数のimbalanceを解消 ? IC-Louvain法 – コミュニティ数のimbalance – 実行時間の67%(Wiki)、43%(Pokec)が通信を占める – Modularityが保たれながら、違う数のコミュニティが 発見 ? Edge imbalanceのないノード分割 – Pokec: 8分割の場合 – Amazon(334k, 1.9M): 何分割しても
- 38. まとめ ? まとめ – エッジ分割手法(IC手法)を前処理として導入 ? メモリ、計算時間、レプリカ数のバランス問題が解決 – IC-Louvainを提案 ? Modularityを保ちながら、違う数のコミュニティを発見 ? 今後の課題 – もっと大規模なデータを用いた実験 – IC-Louvainに適切なデータの判断基準に関する考察 – 発見できたコミュニティ構造に関する考察 – 実装の最適化 ? 特に通信部分
Editor's Notes
- #2: Modularity モジュラリティ
- #3: ソーシャルネットワーク
- #5: 既存研究の问题点を示す。
- #7: 発表の流れ
- #9: Modularityの説明 グラフデータが各状態でmodularityの値Qを持ち、その値がcommunityがうまく発見された場合高くなることを示す
- #11: PMETISNC-Louvain: PMETIS without communication Louvain PMETISC-Louvain: PMETIS with communication Louvain ICC-Louvain: IC with communication Lovuain
- #17: Original node, replica node PMETIS: node 9:9 edge 11:23 IC: node 14:14 18:16
- #18: Original node, replica node PMETIS: node 9:9 edge 11:23 IC: node 14:14 18:16
- #19: Original node, replica node PMETIS: node 9:9 edge 11:23 IC: node 14:14 18:16
- #21: 滨苍蝉迟补苍肠别を入れる
- #23: Community情報の集計 1. 2. 3.
- #24: Community情報の集計 1. 2. 3.
- #25: 大切なのは，コミュニティの情報を分散管理するために，コミュニティごとにコ ミュニティ番号に応じて，そのコミュニティを管理する計算ノードを割り当てて いる． 今まで，色を用いてコミュニティを表現してきたので，その例えを用いる ならば，温かい色は P1 が担当し，冷たい色は P2 が担当するように定めている．
- #29: 100惭叠ぐらい减っていることがわかる
- #31: 45%ぐらい
- #33: Community IDの同期の時間差：通信回数の差 ２回しなきゃいけない Community 重みの時間差：Pokec PMETIS 2%ぐらい発見できている一方、IC 16%ぐらいしか発見できていない
- #34: Community IDの同期の時間差：通信回数の差 ２回しなきゃいけない Community 重みの時間差：Pokec PMETIS 2%ぐらい発見できている一方、IC 16%ぐらいしか発見できていない
- #35: Community IDの同期の時間差：通信回数の差 ２回しなきゃいけない Community 重みの時間差：Pokec PMETIS 2%ぐらい発見できている一方、IC 16%ぐらいしか発見できていない
- #36: Community IDの同期の時間差：通信回数の差 ２回しなきゃいけない Community 重みの時間差：Pokec PMETIS 2%ぐらい発見できている一方、IC 16%ぐらいしか発見できていない