Balanced Graph Edge Partition - todo314 @ ウィキ

Balanced Graph Edge Partition

• Florian Bourse, Marc Lelarge, Milan Vojnovic
• KDD 2014

概要

• 平衡辺分割…並列計算の効率化
• メッセージの集約の有無について期待費用を特徴付け
• 平衡辺分割に対する近似アルゴリズム

疑問

1. 頂点分割に比べた辺分割の定量的な良さ
   • メッセージの集約有
     • 頂点分割: 分割の境界にある辺数
     • 辺分割: クラスタをまたぐ頂点の複製(?)の数
   • メッセージの集約無
2. 辺分割の近似保証は？自然なストリームアルゴリズムはイイ感じになる？

定式化

• C(x)を最小化したい
• ∀j L_j(x)≦(1+ν)ave(L_i(x))
  • L_i: クラスタiの何らかの負荷

集約無頂点分割

• 通信費用: クラスタ間を跨ぐ辺の数
• 負荷: クラスタ内の（重み付き）頂点の総和

集約有頂点分割

• 通信費用: 各頂点uについて，uを含むクラスタiに入る（頂点を含む）クラスタjの種類数
• 負荷: 同じ

集約無頂点分割

• 同じ頂点が複数のクラスタに属しうる
• マスター頂点: 複数の頂点の内，情報を集約する奴
• 通信費用: マスター頂点がクラスタiの各頂点uについて，
  • （uの入次数）-（クラスタがiでuに入る辺の数）
• 負荷: そのクラスタをマスターとする頂点の入次数の和

集約有頂点分割

• 通信費用: マスター頂点クラスタiの各頂点uについて，
  • （uに入りi以外のクラスタの辺の数）-n
• 負荷: そのクラスタ内の辺数

解析

• 適当にクラスタを割り当てた時の各問題の通信費用の期待値

KDD グラフ分割 良 辺分割

2015/03/20 0:54