How to Partition a Billion-Node Graph - todo314 @ ウィキ

How to Partition a Billion-Node Graph

• Lu Wang, Yanghua Xiao, Bin Shao, Haixun Wang
  • MSR
• ICDE 2014

概要

• 分散メモリシステムにグラフを載せることを考える
• どうやって分割すればイイ？
• 部分グラフのサイズ、辺カット、等が評価基準
• 提案手法
  • multi-level propagation
• G頂点のグラフでも数時間で処理できたよ！

背景

Kerninghan-Lin

• メモリベース
• グラフを二分していく
• クラスタ間の頂点を辺カットが小さくなるように交換

METIS

• Graph Coarseningをする
• 先にある程度小さくする（クラスタをまとめるとか
• そのあとKLを適用する
• 問題点: この処理が超重い

1. Coarsening the graph
   • 極大マッチングに入る2頂点をつぶす
2. partitioning the coarsened graph
   • KLとか使う
3. uncoarsening

Label Propagation (LP)

• ホントはクラスタリング手法
• 拡張頂点にユニークなラベルを割り当てる
• ラベルを更新、というかマージしていく
  • 近傍に多いのを選ぶ感じ
• 変化がなくなるまで反復

利点

1. 軽い、メモリとか

• ソートもインデクシングも必要ない
• つまりO(t|E|)、反復回数tは5~6とか

1. semantic-aware（意味論

• クラスタとかが勝手に出てくる感じらしい

挑戦

1. Imbalance

• 各部分グラフのサイズがバランスしていない
• やばお！
• コミュニティサイズが歪んでるせい

1. Efficiency

• 特に効率は意識されていなかった
• やばお！

1. Parallelization

• 並列化は簡単目
• いろいろめんどい

1. Convergence

• 収束の理論的補償なし
• 二部グラフとか振動する
• やばお！
• しょーがないので、ランダムに頂点を選んだり

問題定義

• Edge cut
  • vの近傍でvと同じ分割じゃない頂点の個数の和
• Communication volume
  • vの近傍が属する分割の個数の和
  • 近傍を処理する時どのくらい分割をチェックしないといけないか？
• Graph partitioning
  • V を P = {C_1, C_2, …, C_k} に分割
  • |C_i|≒|V|/k
  • minimize ec(P) or cv(P)

提案手法 Multi-level propagation

1. 繰り返しcoarsening
   • パラメータ
   • αラベル以下になるまで
   • 高々βiteration
   • 各分割のサイズ？は|V|(/kγ)以下
2. coarsenedグラフを分割（KLとかMETIS
3. 元のグラフに対応させる(Refinement

• ラベルの更新
  • 沢山同じ近傍を共有している頂点対は同じ分割に入れたい！
  • 近傍のラベルをランダムに選ぶ？ or 一番値の小さいラベルを選ぶ？
  • 後者の方が条件を満たしやすい
  • さらに、何回もつぶすので、重み付きの更新も考えちゃう

• Refinement
• multiprocessor scheduling (MS)とweighted graph partitioning (WGP)を考えた

• {C_1, C_2, …, C_n}がもらえるので、イイ感じにマージして{S_1, S_2, …, S_k}にしてね
• n > k
• max{|S_i|}を最小化したい

実験

• METISだけは、質がよいんだけど、時間がやばすぎる
• Randomは当然早いんだけど、質はおわてる
• MLP+METISとLP+MSは良い

まとめ

• あんまちゃんと読めなかった
  • メモリにどのくらいのるのか？とかよくわからんかった
• とりあえずデカイグラフを扱うのは大変だなー

ICDE graph partitioning

2013-12-27 01:05:31 (Fri)