Scalable Maximum Clique Computation Using MapReduce - todo314 @ ウィキ

Scalable Maximum Clique Computation Using MapReduce

• Jingen Xiang, Cong Guo, Ashraf Aboulnaga
• ICDE 2013

概要

• MapReduceを使った最大クリークアルゴリズム
• グラフの分割が味噌
  • Multi-depth Color-based (BMC) partitioning
• 分割した後は個々に解く
• この時も枝刈りをして早くする
• 実験は10^2~10^3オーダー頂点で密なグラフ

最大クリークアルゴリズム

• 分割後に使う最大クリークアルゴリズム
• MCRアルゴリズム（すでにある手法）
• 分枝限定法
• ωを最大クリークのサイズとするとω(G)は下のどれか
  • $$ \omega(N(G,v_1)) + 1 $$
  • $$ \omega(N(G-\{v_1\},v_2)) + 1 $$
  • $$ \omega(N(G-\{v_1,v_2\},v_3)) + 1 $$
  • …
  • $$ \omega(N(G-\{v_1,v_2,\cdots,v_k\},v_{k+1})) + 1 $$
  • $$ \omega(N(G-\{v_1,v_2,\cdots,v_{|V|-2}\},v_{|V|-1})) + 1 $$
• N(G,v1)を求めるには再帰的に頑張る
• 今のところ見つかっている最大クリークサイズで枝刈りをしないと意味が無い
• グラフを彩色する
  • （厳密じゃなくても）最大クリークサイズの上限になる
  • 彩色の複雑さと出てくる上限のトレードオフがある
  • 次数の降順でやるといい感じ？

分割戦略

• いっぱいある
• Bisection Partitioning
  • GA,GBに分けて、その間をつなぐ頂点・辺からなるグラフI(G,GA,GB)を作る
  • 上手く分割するのがNP-hard
• k-way Partitioning
  • k個の似たサイズに分割
  • クリーク求めるためには、その後くっつけたりする？
• PICS Partitioning
• One-Depth Partitioning
  • MCRでの分割をそのまま使う
  • 既にこれで最大クリークはなされている
  • 欠点: 物凄くでかいのがあったりバランスが悪い（ロードバランス
• Multi-Depth Partitioning
  • 分割して、各々の実行時間を推定
  • 60secを切るまで再帰的に分割
• Sorting Vertices Based on Color
  • MCRでは彩色してソートしてた
  • これを使おう

提案: Balanced Multi-depth Color-based (BMC) partitioning

• 最後の2つを合わせた感じ

1. 次数順にソート
2. 彩色
3. 彩色を考慮してソート
4. その順に分割を適用

実行時間

• T(G)=f(|G|,ρ(G))^{|G|g(ρ(G))} でフィッティング

実装と最適化

• MapReduceに合わせて頑張る
• 何か込み入った話をしているように見える

実装

Hadoopでの最適化

• グローバルパラメータMAX
  • 見つかった最大クリークのサイズ
• BOUNDは実行時間のしきい値
  • これより少ない部分グラフについて実行する

実験

データセット

• |V|: 250~4000
• |E|: 28K~4M
• DIMACSからとってこれる

実験環境

• Hadoop 1.0.0で組んでAmazon EC2で実行

実行時間

Scalability

• ほとんど理想的じゃなイカ
• ノード数（マシンの）に比例して実行時間が減っていく

分割戦略の比較

• 他の手法は大体駄目
• 提案は密度とかにも影響されず、分割後の頂点数の最大がある程度小さい

その他の調査

• Sorting By Color vs. Random Ordering
  • ランダムはちょっと悪い
• Global Parameter MAX
  • このパラメータが無いとダメポ
• One-depth Partitioning vs. Multi-depth Partitioning
• Comparison with an MPI Algorithm

まとめ

• アルゴリズムの方針は普通なのかな
• 実験では色々と調べててすごいぽよ～とおもった
• 他の最大クリーク論文も多分読むべき

ICDE MapReduce maximum clique parallel computing

2013-11-10 00:38:17 (Sun)