DEIM Forum 2017 H4-1

効率的な分散グラフ処理のためのグラフ分割
藤森 俊匡†

塩川

浩昭††

鬼塚

真†

† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1 丁目 5 番†† 筑波大学 計算科学研究センター 〒 305–8573 茨城県つくば市天王台 1 丁目 1 番 1 号
E-mail: †{fujimori.toshimasa,onizuka}@ist.osaka-u.ac.jp, ††shiokawa@cs.tsukuba.ac.jp
あらまし

実世界で扱われるグラフデータの大規模化に伴って分散グラフ処理技術の重要性が高まっている．分散グ

ラフ処理では，グラフデータを分割し複数の計算機上に割り当ててから分析処理を行うが，このグラフ分割の品質によって分析処理の性能は大きく左右される．そこで本稿では，分散グラフ処理における分析処理を高速化するためのグラフ分割手法を提案する．本手法は，Modularity に基づくクラスタリングを拡張することで，通信発生の要因となる切断エッジ数を削減すると共に計算負荷の均衡化も達成する．また，最新の逐次割り当て手法である HDRF と組み合わせることで，さらなる通信コストの削減を実現する．我々は提案手法を既存の分散グラフ処理フレームワーク上に実装し性能比較を行った．その結果，HDRF のみを用いた場合と比較して PageRank の分析処理を最大 3.2 倍高速化できることを確認した．
キーワード

グラフ分割, グラフマイニング, 分散処理

1. は じ め に

算負荷の偏りも大きくなる．その場合，処理の早い計算機の待機時間が増大し非効率的であるため，グラフ分割では導出する

近年，情報通信技術の進歩に伴って，実世界で扱われるグラ

部分グラフの内包エッジ数の偏りが小さいことが求められる．

フデータの大規模化が進んでいる．例えば，Facebook の 1 日当

ここで本稿では，各部分グラフの内包エッジ数の偏りが小さい

たりの平均アクティブユーザ数は，2016 年 12 月時点で 12.3 億状態のことを等粒度性が高いと表現することとする．また，切人であったと報告されている（注 1） が，Facebook におけるユー

断エッジまたは切断頂点の数が少なく，かつ等粒度性が高くな

ザの友達関係は巨大なグラフデータとして表現できる．このよるようなグラフ分割のことを，品質の高いグラフ分割と表現す

うな SNS から得られるグラフデータは，類似ユーザの検出や，ることとする．

類似ユーザの情報を元にした適切な広告掲示などの目的で使用

分散グラフ処理のための代表的なグラフ分割手法として，される．グラフデータはこの他にも，ウェブページのリンク関Oblivious [8] や HDRF [14] などが挙げられる．これらの手法

係や道路ネットワーク，分子構造やユーザの商品に対する購買はグラフデータの読み込み時点で頂点やエッジの割り当て先を（評価）履歴などさまざまな分野に存在し，これらのグラフデー

逐次決定することにより，大規模なグラフデータを高速に分割

タは今後もさらに大規模化が進むと予想される．

することができる．また，これらの手法は頂点を切断してエッ

大規模なグラフデータに対する分析処理をより効率的に行う

ジをいずれかの計算機に割り当てる vertex-cut 方式のグラフ分ために，近年，数多くの分散グラフ処理フレームワークが提案

割手法である．vertex-cut 方式は，エッジを切断して頂点をいされてきた [8] [10] [11] [21]．これらのフレームワークは共通しずれかの計算機に割り当てる edge-cut 方式に比べ負荷分散にて，グラフデータを分割し，得られた部分グラフを各計算機に優れており [2] [8]，Oblivious と HDRF も多くの場合において配置してから目的の分析処理を実行する．ここで，最初のグラ最適に近い等粒度性を実現することができる [8] [14]．しかし，

フ分割は，分析処理中の通信コストおよびロードバランスに大これらの手法は負荷分散には優れているものの通信コストは大きな影響を与える重要な要素である [15]．例えば，グラフ分割

きくなる傾向があり，それが分析処理性能を悪化させる要因とによって切断された頂点またはエッジは計算機間をまたがってなりやすい．

存在することになるが，分析処理時にはそれらを通じて計算機したがって本稿では，通信コストの削減と計算負荷の均衡化

間で通信が発生する．したがって，グラフ分割では通信コストとをバランスよく両立することで，分散グラフ処理における分を抑えるために切断エッジまたは切断頂点の数を少なくするこ

析処理を高速化するグラフ分割手法を提案する．提案手法では，とが求められる．また，グラフ分析アルゴリズムの多くは，処切断エッジ数を削減するために Modularity [12] という指標を理するエッジ数が多いほど計算負荷が大きくなる [18] ため，各用いる．Modularity はクラスタリングの良さを評価するため計算機に割り当てるエッジ数の偏りが大きいと，各計算機の計の指標であり，一般的にクラスタ内のエッジが密，クラスタ間のエッジ（切断エッジ）が疎であるほど高い値を示す．提案手（注 1）：https://investor.fb.com/investor-news/press-release-details/

法は，Modularity に基づくクラスタリングを拡張することで，

2017/Facebook-Reports-Fourth-Quarter-and-Full-Year-2016-Results/

切断エッジ数が少なく，かつ等粒度性の高いクラスタを導出す

default.aspx

ることを可能とする．また，得られた edge-cut 方式のクラスタ

を vertex-cut 方式に変換することで，通信コストを削減すると

2. 2 レプリケーションファクタとロードバランスファクタ

共にロードバランスを最適に近づける．本稿では，提案手法を分散グラフ処理においては，edge-cut 方式のグラフ分割より

既存の分散グラフ処理フレームワークである PowerGraph [8]も vertex-cut 方式のグラフ分割を採用したほうが通信コストに組み込み，既存のグラフ分割手法を用いた場合との比較実験とロードバランスの両方において優れていると報告されていを行った．その結果，HDRF を用いた場合に比べ，PageRank

る [2] [14]．したがって，提案手法では得られた edge-cut 方式の分析処理を最大 3.2 倍高速化できることを確認した．

のクラスタを vertex-cut 方式のクラスタに変換することで，さ本報告の構成は以下の通りである．2. 節で本稿の前提となる知識について概説する．3. 節で提案手法の詳細について説明し，らなる品質の向上を実現している．本節では，vertex-cut 方式のグラフ分割における品質の評価指標について概説する．

4. 節にて提案手法の評価と分析を行う．5. 節で関連研究についvertex-cut 方式のグラフ分割の品質を評価するための指標とて述べ，6. 節で本報告をまとめ，今後の課題について述べる．

して，レプリケーションファクタとロードバランスファクタがある．レプリケーションファクタ [8] は通信コストを評価する

2. 前 提 知 識ための指標であり，グラフデータの本来の頂点数に対し，実際

2. 1 Modularityの分析処理において計算機上に格納される頂点の複製数がどれ提案手法では，切断エッジ数を削減するために Modular-

ぐらい多いかを表す．vertex-cut 方式のフレームワークでは，

ity [12] という指標を採用している．したがって，本節ではクラあるエッジを計算機に割り当てた時に，そのエッジの両端の頂スタリング指標である Modularity について概説する．

点の複製を計算機上に格納する．同じ頂点と隣接するエッジを

Modularity はクラスタリング結果の良さを評価するための異なる計算機に割り当てると，同じ頂点の複製が異なる計算機指標であり，クラスタ内のエッジが密で，かつクラスタ間の上に格納されることになるが，このような複製間では，分析処

エッジが疎であるほど高い値を示すように設計されている．具

理中にデータの整合性を保つための通信が発生する．したがっ体的には，実際のグラフデータにおけるクラスタ内エッジ数が，て，グラフ分割によって生成される頂点の複製数が少ないほどエッジをランダムに繋ぎ直してできるランダムグラフにおける通信コストを抑えることができる．グラフデータの頂点集合をクラスタ内エッジ数より多いほど高い値を示す．グラフデータ

V ，頂点 v ∈ V の複製を格納する計算機の集合を A(v) としたのエッジ集合を E ，クラスタリングにより得られるクラスタの時，レプリケーションファクタ RF は以下の式で定義される．

集合を C，クラスタ i からクラスタ j へ接続されているエッジの集合を Eij とした時，Modularity の値 Q は以下の式で定義される． {(∑)2 }∑ |Eii |j∈C |Eij |
Q=
−
.
2|E|
2|E|

(1)

i∈C

提案手法ではボトムアップ方式のクラスタリングを採用し，Modularity の値 Q が向上するように異なるクラスタの組をマージしていく．しかし，マージするクラスタの組を決定する
ために毎回式 (1) を計算するのは極めて非効率的である．したがって，提案手法ではマージするクラスタの組を決定する
際に，Clauset らが導出した Modularity の変化量を求める指標 [5] を用いる．隣接するクラスタの組 i, j をマージした場合の Modularity の変化量 ∆Qij は以下のように定義される．
{∆Qij = 2|Eij |−
2|E|(∑

k∈C |Eik |

)(∑

2|E|

k∈C |Ejk |

2|E|

)}

.

(2)

RF =

1 ∑
|A(v)|.
|V | v∈V(4)

上式の RF の値が小さいほど，分析処理中の通信コストを抑えることができる．
一方，ロードバランスファクタは計算負荷の偏りを評価するための指標である．vertex-cut 方式のフレームワークでは，
ロードバランスを評価するために以下のような式 [8] が用いられる．

max |E(m)| < λ

m∈M

|E|
.
|M |

(5)

ここで，M は全計算機からなる集合，E(m) は計算機 m に割り当てられているエッジ集合を表す．また，λ は 1 以上の小さな実数であり，グラフ分割によるタスク量の偏りをどの程度許上式の ∆Qij が大きくなるようなクラスタの組 i, j をマージす

容するかを表すパラメータである．すなわち式 (5) は，計算機ることによって，グラフデータ全体の Modularity を向上させに割り当てられるエッジ数の最大値を，計算機当たりの平均ることができる．また，本稿では，上記の Modularity の変化

エッジ数の何倍まで許容するかということを表している．ここ量 ∆Qij だけでなく，脇田らが提案した以下の指標 [20] を用いで，式 (5) から以下のような指標を導くことができる．

た場合についても評価を行っている．
()|Eii | |Ejj |∆Q′ij = min,× ∆Qij .
|Ejj | |Eii |(3)

ここで，右辺の ∆Qij は式 (2) で示した Modularity の変化量()
ii | |Ejj |である．一方，min |E,
はクラスタ i, j の内包エッジ|Ejj |Eii |数の比率であり，内包エッジ数の差が小さいほど大きな値を示
す．式 (3) を用いることで，式 (2) を用いた場合よりも内包エッ
ジ数が同程度のクラスタ同士がマージされるようになり，クラスタの内包エッジ数の極端な偏りを抑えることができる．

λ=

|M |
max |E(m)|.
|E| m∈M(6)

本稿では，式 (6) の λ をロードバランスファクタと呼び，等粒度性を評価するための指標として用いる．

2. 3 HDRF
本稿では，提案手法の edge-cut 方式から vertex-cut 方式への変換時に HDRF [14] を適用することで，単純なエッジ振り分けを行った場合よりも分析処理を高速化できることを示す．したがって，本節では最新のグラフ分割手法である HDRF についAlgorithm 1 Modularity クラスタリングステップの流れて概説する．HDRF(High Degree (are) Replicated First) は，

Input: G(V, E), k, avertex-cut 方式の手法であり，グラフデータの読み込み時点でOutput: C

エッジの割り当て先を逐次決定するストリーム方式の手法である．HDRF はその名の通り，次数の高い頂点の複製を優先的に

1: C ← ∅2: for each v ∈ V do3:c ← {v}

生成するよう設計されている．これは，実世界で多く見られる

4:

C ← C + {v}次数の分布確率がべき乗則に従うようなグラフデータ [7] では，

5: end for

次数の高い頂点（ハブ）を取り除くだけでも独立したクラスタ

6: Ctmp ← ∅7: while C =| Ctmp doを検出することができる [3] [6] という性質から着想を得ている．

8:

Ctmp ← C

HDRF は，過去のエッジ割り当ての情報から通信コストに関す

9:for each c ∈ Ctmp do

るスコアとロードバランスに関するスコアを計算し，その合計

10:N ← {n | n ∈ neighbors(c) and size constraint(c, n)}11:

値が最大となる計算機をエッジの割り当て先とする．具体的な

m = arg maxn∈N {modularity gain(c, n)}12:

if modularity gain(c, m) > 0 then

スコアの定義は以下の通りである．エッジ (u, v) を読み込んだ

13:c′ ← merged cluster(c, m)

時点での計算機 m に割り当てられたエッジの集合を E(m) と14:

C ← C − {c, m} + {c′ }15:

if |C| = a × k thenする．また，頂点 u, v の複製が格納される計算機の集合をそれ

16:

break

ぞれ A(u), A(v) とする．HDRF では，以下のように定義され17:

るスコア S が最大となるような計算機 m をエッジ (u, v) の割

18:

end if

り当て先とする．

19:

end forend if

20: end while

S(u, v, m) = Srep (u, v, m) + Sbal (m)表 1 アルゴリズム 1 で使用する主な記号の定義

Srep (u, v, m) = f (u, v, m) + f (v, u, m){d(v), if m ∈ A(u)1 + d(u)+d(v)f (u, v, m) =0,
otherwise記号

意味

G(V, E)

グラフデータ．V は頂点集合，E はエッジ集合k

最終的に得たいクラスタの数a

終了条件を決めるパラメータC

クラスタ集合neighbors(c)クラスタ c の隣接クラスタ集合

size constraint(c, n)

サイズ制約を満たすかどうかを判定する関数

ここで，d(u), d(v) はそれぞれ，エッジ (u, v) が読み込まれた

modularity gain(c, n)

Modularity の変化量（式 (2) または式 (3)）

時点での頂点 u, v の隣接エッジ数であり，maxsize と minsize

merged cluster(c, n)

クラスタ c, n をマージして得られるクラスタ(7)

maxsize − |E(m)|Sbal = λ ·ϵ + maxsize − minsize

はそれぞれ計算機に割り当てられているエッジ数の最大値と最小値である．また，λ はロードバランスの重みを決定するためのパラメータであり，ϵ は小さな正の定数である．スコア Srep

3. 提 案 手 法は通信コストに関するスコアであり，頂点 u, v の複製がすで提案手法は，3 つのステップを経て計算機台数と同じ数であに格納されている計算機ほど高い値となる．すなわち，エッジ

る k 個のクラスタを導出する．1 つ目のステップは，Modu-(u, v) を割り当てて新たに格納される複製が少ない計算機ほど

larity に基づくクラスタリングにより切断エッジ数を削減する

スコアが高くなる．また，スコア f は，頂点 u, v のうち，次

Modularity クラスタリングステップである．2 つ目のステップ

数の低い頂点を格納する計算機の方が高い値となる．これによは，Modularity クラスタリングステップによって得られたクり，次数の高い頂点の複製が優先的に格納されることになる．

ラスタを，等粒度性が高くなるように k 個のクラスタに割りd(u), d(v) は正確な次数ではないが，次数分布がべき乗則に従当てていく等粒度マージステップである．3 つ目のステップは，うようなグラフにおいては，ごく一部の次数の高い頂点がそのedge-cut 方式のクラスタを vertex-cut 方式のクラスタに変換

他の多くの頂点と隣接しているために，多くの場合，エッジをする vertex-cut 変換ステップである．各ステップの詳細についランダムに読みこめば次数の高い頂点を上手に切断できるとて，それぞれ 3. 1 節，3. 2 節，3. 3 節で述べる．

Petroni らは述べている [14]．スコア Sbal はロードバランスに

3. 1 Modularity クラスタリングステップ

関するスコアであり，割り当てられているエッジ数が少ない計

Modularity クラスタリングステップでは，2. 1 節で述べた算機ほど高い値となる．λ が 1 以下の場合，Sbal は 1.0 より大式 (2) または式 (3) を用いて，Modularity の値が向上するよ

きな値となることはないため，頂点の複製数の削減が優先されうにクラスタの組をマージしていく．このステップでは，最新る．λ の値を大きくするほどロードバランスの向上が優先されの Modularity クラスタリング手法である塩川らの逐次集約手る．HDRF は最適なロードバランスを実現しつつ，ランダムな法 [16] を用いる．この手法は，Louvain 法 [1] と同等の品質で割り当て手法やその他の逐次割り当て手法よりも通信コストをクラスタリングが可能であり，かつクラスタのマージを逐次行削減することができる [14] が，グラフ構造全体を見る手法に比うことでマージ判定の際に参照するエッジ数を削減し，その他

べると通信コストが高くなってしまう．

の既存手法よりも高速なクラスタリングを可能にする．

Algorithm 2 等粒度マージステップその 1 の流れ

Algorithm 3 等粒度マージステップその 2 の流れ

Input: C, k

Input: C, k

Output: S

Output: S

1: S ← top k clusters(C, k)

1: S ← top k clusters(C, k)

2: C ← C − S

2: C ← C − S

3: sort desc(C)3: while C =| ∅ do4: for each c ∈ C do

4:

Snei ← {s | s ∈ S and neighbors(s) ∩ C =
| ∅}

5:

s ← arg mins∈S {|inner edges(s)|}5:

if Snei = ∅ then6:s′ ← merged cluster(s, c)

6:7:S ← S − {s} + {s′ }7:

end if8:s ← arg mins∈Snei {|inner edges(s)|}9:N ← neighbors(s) ∩ C

10:m ← arg maxn∈N {|inner edges(n)|}Modularity クラスタリングステップの処理の流れをアルゴリ

11:s′ ← merged cluster(s, m)

ズム 1 に示す．また，主な記号の定義を表 1 に示す．このアル

12:

R ← R − {s} + {s′ }13:C ← C − {m}8: end for

ゴリズムは，入力としてグラフデータ G(V, E) と最終的に得た

break

14: end while

いクラスタの数 k ，アルゴリズムの終了条件を決めるための 1

15: for each c ∈ C do

以上のパラメータ a を受け取る．このアルゴリズムは，全ての16:M ← connected clusters(c)頂点が異なるクラスタに属した状態から始まり (1 行目)，それ17:

for each m ∈ M do

以上 Modularity の値が向上しなくなるか，あるいはクラスタの数が a × k になるまでクラスタのマージ処理 (2 行目〜14 行

18:
19:

c ← merged cluster(c, m)
end for20:s ← arg mins∈S {|inner edges(s)|}目) を行う．クラスタ c とマージするクラスタ m は，c の隣接ク

21:s′ ← merged cluster(s, c)

ラスタ集合 N の中で，サイズ制約を満たし，かつ Modularity

22:

S ← S − {s} + {s′ }

23:

C←C−M

の変化量が最大となるものを選択する．ここで，サイズ制約と24: end for

は，クラスタ c とクラスタ m をマージして生成されるクラス
タの内包エッジ数が，平均エッジ数 |E|/k より大きくなっては

表 2 アルゴリズム 2，3 で使用する主な記号の定義
記号

意味

C

入力クラスタ集合k

最終的に得たいクラスタの数

S

種クラスタの集合

top k clusters(C, k)

C 内の内包エッジ数の多いクラスタ上位 k 個

sort desc(C)

クラスタ集合を内包エッジ数により降順にソート

inner edges(c)クラスタ c の内包エッジ集合

merged cluster(s, c)

クラスタ s, c をマージして得られるクラスタ

3. 2 等粒度マージステップ

neighbors(c)クラスタ c の隣接クラスタ集合

等粒度マージステップでは，Modularity クラスタリングス

connected clusters(c)クラスタ c と連結する全クラスタの集合

ならないという制約のことである．この制約により，最終的なロードバランスファクタの悪化を防ぐことができる．

Modularity クラスタリングステップでは，最終的なクラス
タの等粒度性を高めるために k 個よりも多いクラスタを導出す
るにとどめ，次のステップで k 個のクラスタへの割り当て処理を行う．

テップで得られた a × k 個のクラスタを，最終的な等粒度性が高くなるように k 個のクラスタに割り当てていく．このステッの定義を表 2 に示す．等粒度マージステップは，入力として，

プでは，処理開始時点で内包エッジ数が多い上位 k 個のクラス

Modularity クラスタリングステップの出力として得られたク

タを種クラスタとする．そして，種クラスタの中で内包エッジ

ラスタ集合 C と最終的に得たいクラスタの数 k を受け取る．い

数が最少のクラスタと，その他のクラスタの中で内包エッジ数

ずれのアルゴリズムにおいても，最初に C 内の内包エッジ数のの多いクラスタとをマージしていく．こうすることで，ステッ多いクラスタ上位 k 個を種クラスタ集合 S として取得する（1プの終盤に内包エッジ数が少ないクラスタによる調整が可能と行目）．以降の処理では，S 内の種クラスタと C 内のクラスタ

なり，等粒度性を向上させることができる．本稿では，等粒度をマージしていく．まず，内包エッジ数のみを考慮したアルゴ

マージステップにおける処理の方法を 2 種類示す．1 つ目は，

リズム 2 について説明する．このアルゴリズムでは，まずクラ種クラスタとマージするクラスタを，内包エッジ数のみで決定

スタ集合 C を内包エッジ数で降順にソートする（3 行目）．そする方法である．2 つ目は，種クラスタとマージするクラスタ

して，内包エッジ数の多いクラスタから順に，マージ時点で内を，種クラスタの隣接クラスタから優先して選択する方法であ

包エッジ数が最少の種クラスタとマージを行っていく（4 行目

る．後者の方法は前者の方法に比べて，マージ候補のクラスタ〜8 行目）．次に，種クラスタと隣接するクラスタとのマージに制限があるため等粒度性が悪化しやすいが，隣接クラスタ同を優先するアルゴリズム 3 について説明する．このアルゴリ

士をマージすることでより多くの切断エッジ数を削減すること

ズムは，大きく 1 つの処理に分けられる．1 つ目の処理は，種ができる．

クラスタと隣接するクラスタとをマージする処理である（3 行

等粒度マージステップにおける 2 種類の処理の流れをそれぞ目〜14 行目）．この処理では，隣接クラスタを持つ種クラスタ

れアルゴリズム 2 とアルゴリズム 3 に示す．また，主な記号の中で内包エッジ数が最少の種クラスタからマージを行ってい

0

20

40

60

16
14
12
10
8
6
4
2
0

80

レプリケーションファクタ

レプリケーションファクタ

レプリケーションファクタ

14
12
10
8
6
4
2
0

0

20

40

分割数

6
4
2
0
0

80

20

40

80

60

80

(c) webbase-2001
提案手法

HDRF

1.03
1.02

1.01
1
0.99

1.04

ロードバランスファクタ

1.04

60

Oblivious60

分割数

分割数を変化させた場合のレプリケーションファクタ

ロードバランスファクタ

ロードバランスファクタ

図1

40

8

(b) uk-2002
Random

20

10

分割数

(a) soc-LiveJournal1

0

60

12

1.03
1.02

1.01
1
0.99

80

0

20

分割数

40

60

1.04
1.03
1.02

1.01
1
0.99
0

80

20

(a) soc-LiveJournal1(c) webbase-2001(b) uk-2002
RandomOblivious

40

分割数

分割数
提案手法

HDRF

図 2 分割数を変化させた場合のロードバランスファクタ

表3

く．2 つ目の処理は，種クラスタと，種クラスタからエッジを比較実験で用いたデータセット

通じて辿りつけない非連結なクラスタとをマージする処理であ

データ名

|V |

|E|

る（15 行目〜24 行目）．実世界で見られるグラフデータの多く

soc-LiveJournal1 [22]4,847,571

68,993,773

uk-2002 [23]18,520,486

298,113,762

0.986

webbase-2001 [23]118,142,155 1,019,903,190

0.976

は，最大の連結成分以外の連結成分に属する頂点数は少ないこ

Modularity
0.721とから，アルゴリズム 3 では，これらの連結成分をすべて 1 つにまとめ，内包エッジ数が最少の種クラスタにマージするという処理を行っている．これにより，切断エッジ数のさらなる削減が可能である．

3. 3 vertex-cut 変換ステップ
vertex-cut 変換ステップでは，前述のステップにより得られた edge-cut 方式のクラスタを vertex-cut 方式のクラスタに変換する．vertex-cut 方式への変換を行うためには，切断エッジをいずれかのクラスタに一意に割り当てる必要がある．本稿では，切断エッジの割り当て先を決定する方法を 2 種類示す．1
つ目の方法は，切断エッジの両端のクラスタのうち，内包エッ
ジ数が少ない方に割り当てるという方法である．この単純な振り分け手法は，等粒度性を高めつつ 1 つの切断エッジによって生成される頂点の複製をたかだか 1 つに制限することができる．
しかし，格納される頂点の複製数は考慮していないことから，通信コストの削減に関して改善の余地がある．2 つ目の方法は，
切断エッジの割り当て先を 2. 3 節で述べた HDRF [14] を用いて決定する方法である．HDRF は格納される頂点の複製数が少なくなるようにエッジを割り当てるため，通信コストをより効
果的に削減できる．また，HDRF はロードバランスが向上する
ようにも設計されており，等粒度マージステップ終了時のクラ
スタの等粒度性も高いことから，最終的に得られるクラスタの等粒度性も十分高くなることが考えられる．

価実験を行った．本実験で用いたデータセットを表 3 に示す．
いずれも，ソーシャルグラフや Web グラフなどの実データをもとに形成されたグラフデータである．提案手法のパラメータa は，多くの場合グラフデータの頂点数およびエッジ数が多いほど大きな値とする必要がある．本実験では，分割数を k とした時に，soc-LiveJournal では a × k = 8, 000, uk-2002 では

a × k = 16, 000，webbase-2001 では a × k = 160, 000 となる
ように a を設定した．
本実験では，実験環境として Amazon EC2 を使用した．使用したインスタンスは r3.2xlarge の linux インスタンスである．

CPU は Intel(R) Xeon(R) CPU E5-2670 v2 であり，クロッ
ク数は 2.50GHz，コア数は 4 である．メモリは 60GB である．
また，インスタンス間のデータ伝送速度はおよそ 1.03Gbps であり，hdparm を-t オプションをつけ実行することで得られたディスク読み込み速度はおよそ 103MB/sec であった．提案手法の実装には C++を用いた．コンパイルに使用した g++のバージョンは 4.8.1 であり，最適化オプションとして-O3 を使用した．また，PowerGraph も C++で実装されており，上記と同様の条件でコンパイルを行った．
本実験では，2. 2 節で述べた評価指標と実際に分析処理を実行した場合の分析処理時間による評価を行う．まず，4. 1 節で
既存手法との比較結果を示す．次に，4. 2 節で各ステップの処4. 評 価 実 験
提案手法の性能を評価するために，提案手法を既存の分散グ
ラフ処理フレームワークである PowerGraph [8] に組み込み評

理方法を変えた複数の提案手法の比較結果を示す．

4. 1 既存手法との比較
本節では，既存手法と提案手法との比較結果を示す．既存
手法として，Random, Oblivious [8], HDRF [14] の 3 つの手

1.2

1
0.8
0.6
0.4
0.2
0

1.2

分析処理時間の比率

分析処理時間の比率

分析処理時間の比率

1.2

1
0.8
0.6
0.4
0.2

SSSP
分析処理

CC

PageRank(a) soc-LiveJournal1

0.4

0.2

SSSP
分析処理

PageRankCC(b) uk-2002
Random

図3

0.6

0

0
PageRank

1
0.8

Oblivious

SSSP
分析処理

CC

(c) webbase-2001
提案手法

HDRF

計算機台数を 64 台とした場合の Random に対する分析処理時間の比率法を用いた．Random は，エッジの割り当て先をハッシュ値を

表 4 webbase-2001 に対する計算機あたりの平均通信バイト量

PageRank

用いてランダムに決定する最も単純な手法である．Oblivious
は，エッジ割り当てにより格納される頂点の複製数が最少であり，かつ割り当てられているエッジ数が最少の計算機にエッジ

SSSP

CC

HDRF

16.2GB 688.2MB 1207.5MB

提案手法

1.07GB 131.5MB

176.0MBを割り当てる手法である．Oblivious に次数の高い頂点の複製を優先的に格納するように変更を加えた手法が HDRF である．

HDRF のパラメータ λ は文献 [14] に従い 1 とした．既存手法はいずれも PowerGraph に実装されているプログラムを使用

3) CC (Connected Component): グラフデータ内から頂点が連結された部分グラフを抽出する分析処理．
図 3 に結果を示す．縦軸は Random を用いた場合の分析処理した．提案手法に関しては，既存手法との比較を明瞭にするた

時間に対する比率である．図 3 から，ほぼすべての分析処理おめに，本節では Modularity クラスタリングステップにおいてよびグラフデータにおいて，既存手法と比べ提案手法の方が分等粒度性を考慮した Modularity 変化量を用い，等粒度マージ

析処理時間を高速化できていることが分かる．特に，PageRank

ステップで内包エッジ数だけを考慮してクラスタのマージを行

においては，既存手法に対しレプリケーションファクタをよりい，vertex-cut 変換ステップにおいて HDRF を用いる手法に削減できているグラフデータほど高速化の効果が大きいことがついての結果のみ示す．

分かる．しかし，soc-LiveJournal1 を用いて SSSP を実行した

4. 1. 1 グラフ分割指標による評価

場合は，HDRF を用いた場合と比べて分析処理時間が長くなっ

図 1 に分割数を変化させた場合の各手法のレプリケーションている．この結果に関しては，HDRF を用いた場合の分析処理

ファクタを示す．図 1 から，すべてのグラフデータおよび分割

時間が 3.4 秒，提案手法を用いた場合の分析処理時間が 3.6 秒

数において，既存手法と比べ提案手法の方がレプリケーションと非常に短いため，分析処理中のその他のオーバヘッドの影響

ファクタを削減できていることが分かる．本実験では，HDRF

が大きくなり，提案手法による高速化の効果がでなかったために対して，レプリケーションファクタを soc-LiveJournal1 ではであると考えられる．

最大 38.0%，uk-2002 では最大 71.5%，webbase-2001 では最大分析処理によって提案手法の高速化の効果が異なるのは，各65.9%削減することに成功した．表 3 と合わせて，Modularity

分析処理の通信量が異なるためであると考えられる．グラフの値が大きいグラフデータほどレプリケーションファクタの削データとして webbase-2001 を用いた場合の各分析処理中の減率が大きいことが分かる．これは，Modularity の値が大き計算機あたりの通信バイト量を表 4 に示す．表 4 から，分析

いグラフデータほど，Modularity クラスタリングステップで処理によって分析処理中の通信バイト量が大きく異なること

より多くの切断エッジを削減することができたためであると考が分かる．また，図 3 と合わせて，通信バイト量の差が大きえられる．

い分析処理ほど提案手法の高速化の効果が大きいことが分か

また，図 2 に分割数を変化させた場合の各手法のロードバラ

る．soc-LiveJournal1 および uk-2002 を用いた場合においてンスファクタを示す．図 2 から，uk-2002, webbase-2001 におも，同様の傾向の結果となった．本実験では，HDRF に対し

いては Random と比べロードバランスが悪化しているものの，て，PageRank の分析処理を最大 3.2 倍，SSSP の分析処理を

ロードバランスファクタの悪化を 1%ほどに抑えられているこ最大 1.2 倍，CC の分析処理を最大 1.3 倍高速化することに成とが分かる．

功した．

4. 1. 2 分析処理時間による評価

4. 2 各ステップの性能評価

本実験では，PowerGraph を用いて実際にグラフ分析アルゴ

本稿では，提案手法の各ステップにおける処理の方法を 2 種

リズムを実行し，分析処理に要した時間を計測した．本実験で類ずつ示した．本稿で示した各ステップの処理方法をまとめる

用いたグラフ分析アルゴリズムは以下の 3 つである．

と，以下の通りである．

1) PageRank [13]: ウェブページの重要度を計算するために考えられた分析処理

2) SSSP (single-source shortest path): ある 1 つの頂点から他の全ての頂点への最短距離を求める分析処理•

Modularity クラスタリングステップ：通常の Modularity

変化量を用いるか (normal)，等粒度性を考慮した Modularity
変化量を用いるか (balanced)•

等粒度マージステップ：クラスタの内包エッジ数のみを

4
3
2

1
0

1.16
レプリケーションファクタ

1.2
レプリケーションファクタ

レプリケーションファクタ

5

1.15
1.1
1.05

1

1.14
1.12
1.1
1.08
1.06
1.04

1.02

0.95

(a) soc-LiveJournal1
normal+any+naivebalanced+any+naive

1(b) uk-2002
normal+any+HDRF
normal+neighbors+naivebalanced+any+HDRF
balanced+neighbors+naive(c) webbase-2001
normal+neighbors+HDRF
balanced+neighbors+HDRF

1.05
1.04

1.00061.00041.0002
1
0.99980.9996

ロードバランスファクタ

1.001
1.0008

ロードバランスファクタ

ロードバランスファクタ

図 4 各提案手法のレプリケーションファクタ ((a)(c) の normal は計測不可)

1.03
1.02
1.01
1
0.99
0.98

(a) soc-LiveJournal1
normal+any+naivebalanced+any+naive

図5

normal+any+HDRF
balanced+any+HDRF

1.014
1.012
1.01
1.008
1.006
1.004
1.002
1
0.998
0.996

(b) uk-2002
normal+neighbors+naivebalanced+neighbors+naive(c) webbase-2001
normal+neighbors+HDRF
balanced+neighbors+HDRF

各提案手法のロードバランスファクタ ((a)(c) の normal は計測不可)

考慮してマージするか (any)，隣接クラスタのマージを優先す法に比べて neighbors を用いた手法の方がロードバランスファ

るか (neighbors)

クタが増大していることが分かる．Modularity クラスタリン•

vertex-cut 変換ステップ：単純な振り分け手法を用いるか (naive)，HDRF を用いるか (HDRF)

グステップの比較では，balanced を用いる手法よりも normalを用いる手法の方がレプリケーションファクタを削減できてい以降，説明の簡略化のために，各ステップでどの処理方法を用ることが分かる．そして，ロードバランスファクタに関しても，いるかを略称を用いて記述することとする．例えば，Modular-

normal を用いる手法の方がロードバランスの悪化を抑制できて

ity クラスタリングステップでは等粒度性を考慮した Moduarity

いることが分かる．これは，等粒度性を考慮しない Moduarity

変化量を用い，等粒度マージステップではクラスタの内包エッ

変化量を用いる場合でも，サイズ制約を設けることによって内ジ数のみを考慮し，vertex-cut 変換ステップでは HDRF を使

包エッジ数の偏りを抑制できているためと考えられる．

用する提案手法は，balanced+any+HDRF と記述する．

図 6 に，各ステップの処理方法を変えた複数の提案手法を用各ステップの処理方法を変えた複数の提案手法におけるレプ

いた場合の分析処理時間を示す．計算機台数は 64 台であり，用リケーションファクタおよびロードバランスファクタを，それいた分析処理は PageRank である．図 6 から，vertex-cut 変換

ぞれ図 4，図 5 に示す．分割数は 64 である．soc-LiveJournal1

ステップにおいて，naive を用いる手法に比べ HDRF を用いる

および webbase-2001 の図における Modularity クラスタリン

手法の方が分析処理を高速化できていることが分かる．これは，グステップで normal を用いた場合の結果に関しては，長時間経HDRF を用いた手法の方が通信コストを削減できるからだと過してもグラフ分割処理が終了しなかったために結果を記載し考えられる．一方，レプリケーションファクタが同程度となっていない．この原因として，Modularity クラスタリングステッている手法同士を比較すると，ロードバランスファクタが増大

プにおけるサイズ制約の影響が考えられる．Modularity クラするような場合であっても分析処理時間が早くなっている場合

スタリングステップでは，内包エッジ数が計算機あたりの平均があるのが分かる．この原因として，頂点単位で更新処理を行

エッジ数を超過するようなクラスタのマージは行わないといううという分散グラフ処理における効率化の影響が考えらえる．

制約を設けている．soc-LiveJournal1 および webbase-2001 で分散グラフ処理では，頂点単位で更新処理を並列に実行し，値は，normal を用いた場合は内包エッジ数の多いクラスタが生成が収束した頂点から更新処理を終えることで効率化を図っていされてしまい，サイズ制約を満たすクラスタの組を見つけるのる．そのため，分析処理途中に各計算機上で更新処理を行う頂に膨大な時間を要するのだと考えられる．図 4 から，vertex-cut

点の数にばらつきが生じる場合がある．提案手法ではいずれの変換ステップにおいて naive を用いた手法に比べ，HDRF を組み合わせにおいてもロードバランスの悪化を抑制できている

用いた手法の方がレプリケーションファクタを削減できていことから，更新処理を終了した頂点のばらつきによる計算負荷

ることが分かる．また，naive と HDRF ほどの差はないものの偏りの影響が大きくなるのだと考えられる．

の，等粒度マージステップにおいて any を用いた手法に比べ，

neighbors を用いた手法の方がレプリケーションファクタを削減できていることが分かる．一方，図 5 から，any を用いた手

5. 関 連 研 究
著名なグラフ分割ライブラリとして METIS [9] が挙げられ

63.5

152

95
90
85
80

62.5
62
61.5
61
60.5

分析処理時間（秒）63100

分析処理時間（秒）

分析処理時間（秒）

105

60

75

59.5

(a) soc-LiveJournal1
normal+any+naivebalanced+any+naive

150
148
146
144
142
140

(b) uk-2002
normal+any+HDRF
normal+neighbors+naivebalanced+any+HDRF
balanced+neighbors+naive(c) webbase-2001
normal+neighbors+HDRF
balanced+neighbors+HDRF

図 6 各提案手法の分析処理時間 ((a)(c) の normal は計測不可)

る．METIS は，グラフデータを圧縮するフェーズ，圧縮されたグラフデータを分割するフェーズ，分割の品質を向上させながらグラフデータを元のサイズに戻していくフェーズの 3 つのフェーズによってグラフデータを分割する．METIS は品質の高いグラフ分割が可能であるものの，大規模なグラフデータの分割には膨大な時間がかかるため，分散グラフ処理では用いられていない．
分散グラフ処理では，Oblivious [8] や HDRF [14] のようなストリーミンググラフ分割手法 [17] が多く用いられている．

Fennel [19] は edge-cut 方式の手法であり，割り当てにより切断されるエッジ数が少なく，かつ内包する頂点数が少ないような部分グラフに頂点を割り当てる．Ginger [4] は，次数の高い頂点と隣接するエッジは vertex-cut 方式により別の部分グラフに割り当て，次数の低い頂点は edge-cut 方式の Fennel により割り当て先を決定することで，HDRF と同様に次数の高い頂点の複製を優先的に格納する．

6. お わ り に
本稿では，通信コストの削減と計算負荷の均衡化とをバラン
スよく両立し，分散グラフ処理における分析処理を高速化できるグラフ分割手法を提案した．提案手法は，Modularity に基づくクラスタリングを拡張することで，切断エッジ数が少なく，かつ等粒度性の高いクラスタを導出することを可能とする．また，得られた edge-cut 方式のクラスタを vertex-cut 方式のク
ラスタに変換することでさらなる品質の向上を実現する．本稿では，提案手法を既存の分散グラフ処理フレームワークである PowerGraph に組み込み評価実験を行った．実験の結果，HDRF のみを利用した場合に比べ，PageRank の分析処理を最大 3.2 倍高速化することに成功した．今後の課題として，グラ
フデータの構造によって，各ステップにおける最適な処理方法を自動で決定する方法についての検討が考えられる．
文

献[1] V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre,“Fast unfolding of communities in large networks,” Journalof Statistical Mechanics: Theory and Experiment, 2008.
[2] F. Bourse, M. Lelarge and Milan Vojnovic, “Balanced graphedge partition,” Proceedings of KDD, 2014.
[3] D. S. Callaway, M. E. Newman, S. H. Strogatz and D. J.
Watts, “Network robustness and fragility: Percolation on
random graphs.”, Phys. Rev. Lett., 2000.
[4] Y. C. R. Chen, J. Shi and H. Chen, ”Powerlyra:Diﬀerentiated graph computation and partitioning on

skewed graphs.”, Proceedings of SIGOPS ,2015.
[5] A. Clauset, M. E. J. Newman and C. Moore, “Finding community structure in very large networks,” Phys. Rev. E,
2004.
[6] R. Cohen, K. Erez, D. Ben-Avraham and S. Havlin, “Breakdown of the internet under intentional attack.”, Phys. Rev.
Lett., 2001.
[7] M. Faloutsos, P. Faloutsos and Christos Faloutsos, “Onpower-law relationships of the Internet topology,” Proceedings of SIGCOMM, 1999.
[8] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson and C. Guestrin,“PowerGraph: distributed graph-parallel computation on
natural graphs,” Proceedings of OSDI, 2012.
[9] G. Karypis and V. Kumar, “Multilevelk-way partitioning scheme for irregular graphs,” Parallel and Distributed
Computing, 1998.
[10] Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola
and J. M. Hellerstein, ”Distributed GraphLab: a framework for machine learning and data mining in the cloud,”
PVLDB, 2012.
[11] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert,
I. Horn, N. Leiser and G. Czajkowski, “Pregel: a system
for large-scale graph processing,” Proceedings of SIGMOD,
2010.
[12] M. E. J. Newman and M. Girvan. “Finding and evaluating
community structure in networks,” Phys. Rev. E, 2004.
[13] L. Page, S. Brin, R. Motwani and T. Winograd, “The pagerank citation ranking: Bringing order to the web,” Technical
Report, 1999.
[14] F. Petroni, Leonardo Querzoni, K. Daudjee, S. Kamali and
G. Iacoboni. “HDRF: Stream-Based Partitioning for PowerLaw Graphs,” Proceedings of CIKM, 2015.
[15] S. Salihoglu and J. Widom, “GPS: a graph processing system.”, Proceedings of SSDBM, 2013.
[16] H. Shiokawa, Y. Fujiwara, and M. Onizuka, “Fast algorithm for modularity-based graph clustering,” Proceedingsof AAAI, 2013.
[17] I. Stanton and G. Kliot, “Streaming graph partitioning forlarge distributed graphs,” Proceedings of KDD, 2012.
[18] S. Suri and S. Vassilvitskii, “Counting triangles and thecurse of the last reducer,” Proceedings of WWW, 2011.
[19] C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic, “Fennel: Streaming graph partitioning for massive
scale graphs,” Proceedings of ACM, 2014.
[20] K. Wakita and T. Tsurumi, “Finding community structure in mega-scale social networks,” Proceedings of WWW,
2007.
[21] R. S. Xin, J. E. Gonzalez, M. J. Franklin and I. Stoica,“GraphX: a resilient distributed graph system on Spark,”
Proceeding of GRADES, 2013.
[22] Stanford Large Network Dataset Collection. http://snap.stanford.edu/data/[23] Laboratory for Web Algorithmics. http://law.di.unimi.it.