WSDM2016報告会−論文紹介(Distributed Balanced Partitioning via Linear Embedding Google Research)#yjwsdm

論文紹介 Distributed Balanced Partitioning via Linear Embedding Google Research 矢野 将之 ヤフー株式会社 2016/4/27

この論文の目的 P2 大規模グラフ分割時のカットサイズ最小化方式の提案 分割 分割 G=(V, E) できるだけカットサイズが小さい分割位置を見つける

この論文の目的 P3 分割したグラフを分散サーバに配置 ネットワーク通信 Server A ネットワーク通信 Server B Server C 小カットサイズなら、別Serverにリクエストする可能性が減る

この提案の必要性 グラフ分割の必要性 • １サーバではリソース不足 • 並列処理による高速化 カットサイズ最小化の必要性 • 高速化 • ネットワークコスト この提案の必要性 • シンプルなのでMapReduceで実装可能 • 先行研究より少ないカットサイズを実現 P4

提案手法 主には３つのステップ 1. グラフの頂点を直線状にマッピング 2. 頂点を入れ替え順番を変更 3. カット位置を変更しカットサイズを改善 P5

1. グラフの頂点を直線状にマッピング G=(V, E) Initial ordering 0 1 2 3 4 5 6 7 8 9 10 11 • 局所最適化できる問題への切り替え P6

2. 頂点を入れ替え順番を変更 Initial ordering Semi-local moves 0 1 3 2 6 5 4 11 8 9 10 7 • 均等に分割 • カットサイズが少なくなるように頂点をスワップ P7

3. カット位置を変更しカットサイズを改善 Semi-local moves 0 1 3 2 6 5 4 11 8 9 10 7 Imbalance 0 1 3 2 6 5 4 11 8 9 10 7 • カットサイズが小さくなるようにカット位置を変更 P8

提案手法 主には３つのステップ 1. グラフの頂点を直線状にマッピング 2. 頂点を入れ替え順番を変更 3. カット位置を変更しカットサイズを改善 P9

1. グラフの頂点を直線状にマッピング • Random mapping • 頂点をランダムに並べる • Hilbert curve mapping • 空間充填曲線 • 空間的に近いものを直線上の近い位置に配置 • Affinity-based mapping • 凝集型階層クラスタリング • 近似指標には共通隣接頂点数の割合を利用 P10

凝集型階層的クラスタリングイメージ G=(V, E) v2 v0 v1 • 最初は各頂点自体がクラスタリング • 各クラスタにラベルをつける(v0, v1, …) P11

凝集型階層的クラスタリングイメージ G=(V, E) A2 A3 A0 A1 • 赤同士で距離が近いものをクラスタリング(オレンジ) • 各クラスタにラベルをつける （A0, A1, A2, A3） ※ここでの距離は共通隣接頂点数の割合。上の図はその意味で正確ではありません P12

凝集型階層的クラスタリングイメージ P13 G=(V, E) B1 B0 • オレンジ同士で距離が近いものをクラスタリング（緑） • 各クラスタにラベルをつける（ B0, B1 ）

Affinity-based mapping P14 C0 B0 B1 A0 A2 v0 v5 v2 0 1 v0のラベル v5のラベル 2 3 4 5 6 7 8 9 10 C0#B0#A0#v0 C0#B1#A2#v5 • ラベルでソートすることで頂点の位置を並び替え 11

提案手法 主には３つのステップ 1. グラフの頂点を直線状にマッピング 2. 頂点を入れ替え順番を改善 3. カット位置を変更しカットサイズを改善 P15

Minimum Linear Arrangement P16 G = (V, E) 𝜙 ∶ 𝑉 → 0,1, … ,𝑛 − 1 𝑚𝑖𝑛 𝜙 𝑣 − 𝜙(𝑢) 𝓌𝓊𝓋 (𝑢,𝑣)∈𝐸 0 1 2 3 4 5 6 7 8 9 10 11 3-0=3 2-1=1 4-1=3 … 11-9=2 11-10=1 合計 23

Minimum Linear Arrangement グラフ上で繋がりのある頂点は できるだけ直線上の近くに配置する グラフ上で密な箇所は ある程度固まった箇所に配置されるので 分割しやすいはず 0 1 2 3 4 5 6 7 8 9 10 11 P17

Minimum Linear Arrangement MapReduceで収束するまで(または指定回数)実行 MR Phase 1 1. 現在の位置と隣の位置の重みからweighted medianを算出 2. その位置を新しいRankとする MR Phase 2 1. 位置が重複したらIDベース順などで並べる 2. 各ノードに新しいRankをつける グラフによって収束するまでの回数は異なる P18

Rank Swap P19 分割したパーティションをさらにいくつかのグループに分ける 0 1 2 3 4 5 6 7 8 9 10 11 I0 I1 I0 I1 各グループからランダムにペアを選ぶ (例えば左 l1 と 右 l0のペア) 3 4 5 6 7 8 I1 I0 カットサイズが小さくなるようにこのペアの頂点を入替え

提案手法 主には３つのステップ 1. グラフの頂点を直線状にマッピング 2. 頂点を入れ替え順番を改善 3. カット位置を変更しカットサイズを改善 P20

Windowの定義 P21 与えられたグラフを k 分割 均等な分割場所 𝑗𝑛 𝑞𝑗 = , 1 ≤ 𝑗 < 𝑘, 1 ≤ 𝑖 < 𝑛 𝑘 許容可能なバランス 𝛼>0 Window 𝑊𝑗 = 𝜋 𝜋𝑞𝑗 −𝛼′ → 𝜋𝑞𝑗 +𝛼′ , 𝛼 ′ = W1 −𝛼 ′ 𝛼𝓃 2𝑘 W2 𝛼′ −𝛼 ′ W3 𝛼′ −𝛼 ′ 𝛼′

Windowの詳細 W1 P22 W2 −𝛼 ′ 𝛼′ W2 −𝛼 ′ W3 𝛼′ −𝛼 ′ 𝛼′ 1 2 3 4 5 6 7 8 • W2の頂点に繋がっていない辺は未記述 • 反対側の頂点はカットサイズに影響しないので未記述

Scalable linear boundary optimization W2 1 2 3 4 5 6 7 8 • window内の順序は維持 • 分割の位置のみ最適化 • この図では１と２の間でのカットが最適 （カットサイズは４） P23

Scalable minimum-cut optimization W2 1 7 3 8 6 2 4 5 • window内での順序は自由に入替え • この図では8と6の間でのカットが最適 （カットサイズは1） P24

実験(テストデータ) P25 頂点 辺 その他 World-roads 数億 10億以上 • 辺の重さなし • 緯度経度を持つ • 少数のサーバ Twitter 4100万 24億 • 辺の重さなし • 無向グラフ LiveJournal 480万 4290万

Metric, Swapとアンバランス(Twitter) 論文引用 Metric: Minimum Linear Arrangement Swap: Rank Swap Combination: Metric+Swap+アンバランス P26

Metric, Swapとアンバランス(World-roads) 論文引用 Metric: Minimum Linear Arrangement Swap: Rank Swap Combination: Metric+Swap+アンバランス(3%) P27

他システムとの比較 LiveJournal Twitter P28 論文引用 論文引用

Conclusion • 大規模グラフの分割アルゴリズムを提案 • 頂点を直線上に配置するアルゴリズム • 凝集型階層クラスタリング • Random-swapとminimum cutによる最適化 • 他のシステムよりも良いカットサイズ • Google Maps Driving Directionにてヒルベルト曲線のアルゴ リズムより共有クエリ数を40%削減 P29

P30