GPUを用いたラベル伝搬法によるグラフクラスタリングの高速化

(1)

DEIM Forum 2016 A8-3

GPU を用いたラベル伝搬法によるグラフクラスタリングの高速化

小澤

佑介

†

_{天笠俊之}

††

_{北川博之}

††

†

筑波大学大学院システム情報工学研究科〒 305–8573 茨城県つくば市天王台 1–1–1

††

筑波大学システム情報系

〒 305–8573 茨城県つくば市天王台 1–1–1

E-mail:

†

[email protected],

††{

amagasa,kitagawa

}

@cs.tsukuba.ac.jp

あらまし

グラフデータからコミュニティ構造を抽出するための技術として，グラフクラスタリングが注目されてい

る．しかし，近年のグラフデータの大規模化に伴い，クラスタリング処理の高速化が重要な課題となっている．本研

究では， GPU (graphics processing unit) を用いて，グラフクラスタリング手法の一つであるラベル伝搬法の高速化

を行なう．GPU は，非常に多くの演算ユニットを搭載しており，高い並列度の処理を得意とする．提案手法では，ラ

ベル伝搬法の各ステップを，GPU 上での高並列処理に適した形式に変換することで高性能化を図る．さらに，実デー

タと合成データを用いた実験により，提案手法の性能を評価する．

キーワード

GPU，グラフクラスタリング，ラベル伝搬法

1. 序

論

グラフデータ分析手法の一種であるグラフクラスタリングが注目を集めている [11]．グラフクラスタリングは，グラフデータから，密に接続した頂点の集合をクラスタとして抽出する技術である．グラフクラスタリングは，Webやソーシャルネットワークから生物学など，多種多様なグラフデータに対する応用が考えられている [19]．しかし，近年の情報通信技術の進歩に伴い，グラフデータの大規模化が進んでいるという問題がある．例えば，Facebookの月間アクティブユーザ数は，2015年3月時点で14.4億であると報告されている．（注 1）_{このような巨大} なネットワークに対してグラフクラスタリングを適用するためには，クラスタリング処理の高速化が非常に重要な課題となる．高速なグラフクラスタリングアルゴリズムの一つとして，ラベル伝搬法が存在する[21]．ラベル伝搬法は，グラフの辺数に比例する計算量を持ち，他の多くのアルゴリズムより効率的である．また，処理性能だけでなく，クラスタリング精度においても良い性能を示すという結果が報告されている[25]．さらに，局所的な情報のみをもとにクラスタリング処理を行うため，並列化に適しているという利点もある[16]．これは，現在のプロセッサのマルチコア化・メニーコア化を考慮すると，処理の高速化を行なうにあたって極めて重要な特性であると考えられる．一方，近年特に注目されている並列処理の技術として，GPU

(graphics processing unit) コンピューティングがある [18]．

GPUは，数百から数千の処理ユニットを搭載しており，CPU と比較して非常に処理性能が高い．GPUコンピューティングでは，通常はCPUで行われる計算負荷の高い処理を，GPUを用いて並列処理することで全体の処理の高速化を図る．しかし， GPUの性能を引き出すためにはいくつかの技術的課題を解決する必要がある．特に，GPU上でグラフデータを処理するにあたって，負荷分散が重要な課題となる．これは，多くの実世（注1）：http://investor.fb.com/releasedetail.cfm?ReleaseID=908022 界のグラフデータにおいて，次数分布はべき乗則に従うことが知られており[1]，かつGPU上では千以上のスレッドが並列に動作するので，単純に頂点ごとに処理を振り分けるような並列化では非常に非効率的となってしまうためである．GPUを用いてラベル伝搬法の高速化を行なった研究[23]が既に存在するが，負荷分散に関してはあまり考慮されていないという問題点がある．本研究では，既存研究と異なり，GPU上での負荷分散を考慮したグラフクラスタリングの高速化を行なう．まず，ラベル伝搬法をベースに，アルゴリズムをGPU上での高並列処理に適した形式へと変換する．これにより，各スレッドが行なう仕事量を均一化すると同時に，GPUに適した処理である，配列上の単純な操作のみでクラスタリング処理が可能となる．さらに，segmented sortやsegmented reduce [2]などの，次数の偏りが存在するデータにおいても効率的に並列処理が可能な演算を活用する．本稿では，実世界のグラフデータと合成データを用いて評価実験を行なった．その結果，処理性能においては，既存手法と比較して最大で117倍の高速化に達成した．また，正解クラスタ情報を用いたクラスタリング精度の評価においても，提案するGPUを用いたラベル伝搬法が良い性能を示した．本稿の構成は以下の通りである．まず，2.節において，前提となる知識に関して説明する．その後，本稿で提案するGPU を用いたラベル伝搬法について3.節で述べ，その評価を4.節で行なう．関連研究については5.節で説明し，6.節で結論と今後の予定を述べる．

2. 前提知識

本節では，まず本研究で扱う問題に関して，2. 1節で述べる． 2. 2節では，ラベル伝搬法によるグラフクラスタリングを説明する．最後に，GPUコンピューティングに関して2. 3節で述べる．

(2)

v0 v1 v2 v3 v4 v5 v6 A B C D E F G (a) 初期状態 v0 v1 v2 v3 v4 v5 v6 A A A A D D D (b) ラベルを (v2, v4, v6, v1, v3, v0, v5) の順序で更新 v0 v1 v2 v3 v4 v5 v6 A A A D D D D (c) 最終状態図1: ラベル伝搬法の例：各頂点viの側の文字はviのラベルを示している． 2. 1 問題定義グラフを G = (V, E)と表す．ここで，V は頂点集合， E ⊂ V × V は辺集合である．また，基本的に，頂点の数を n =_{|V |}，辺の数をm =_|E|と表す．本研究では，簡単化のために，重み無し無向グラフを仮定する．ただし，重み付きや有向グラフを対象とするような拡張も容易に可能である．本研究で扱う問題であるグラフクラスタリングは以下のように定義できる．問題(グラフクラスタリング). グラフG = (V, E)が与えられたとき，以下の条件を満たすクラスタ集合_{C = {C}1, C2, . . . , Cl} を求める：(1)任意のiについてクラスタCiはV の部分集合， (2)任意のi, j (i |= j)に関してCi∩Cj=∅，(3)!li=1Ci= V， (4)同じクラスタ内の頂点は密に接続されており，異なるクラスタ間の頂点は疎に接続されている． 2. 2 ラベル伝搬法によるグラフクラスタリンググラフクラスタリング手法の一つとしてラベル伝搬に基づくアルゴリズムが提案されている[21]．ラベル伝搬法では，ある頂点が属するクラスタは多くの隣接頂点が属するクラスタと同じである，という考え方を基にクラスタリングを行う．ラベル伝搬法の擬似コードはAlgorithm 1のように書ける．まず，各頂点に対してユニークなラベルを付与する（1行目）．そして，各頂点をランダムな順番で調べ，ラベルを更新していく（3–6行目）．ある頂点のラベルは，隣接頂点のラベルを調べ，最も多く出現するラベルへと更新する（5行目）．出現回数が同じラベルが存在する場合には，ランダムに更新先のラベルを選択する．ラベル更新のイテレーションを終了条件を満たすまで継続し，最終的に同じラベルを持つ頂点を同じクラスタとして抽出する（8–9行目）．終了条件としては，ラベルの更新が行われなくなる，またはラベル更新のイテレーションを一定回数行なう，などが考えられる．ラベル伝搬法の例を図1に示す．まず，各頂点にユニークなラベルを付与する（図1(a)）．その後，頂点をランダムな順序で調べていき，ラベル更新処理を行う．ここでは，更新順序が (v2, v4, v6, v1, v3, v0, v5)である場合を考える．図1(a)における v2の隣接頂点のラベルを見ると，A, B, Dがそれぞれ1回ずつ出現している．この場合，上述の通り，実際にはランダムに更新ラベルを決定するが，簡単のためにアルファベット順で最小のラベルに更新することを考える．すなわち，v2のラベルはA へと更新される．同様に，v4のラベルはD へ，v6のラベルは Dへと更新されていき，全頂点を更新すると図1(b)のようになる．この後，もう一度全頂点を調べると，図1(c)となり，これ Algorithm 1:ラベル伝搬法 Input: グラフ G = (V, E) Output: クラスタリング結果C 1 ラベル割当て L を初期化 ◃ Liは頂点 viのラベルを表す 2 repeat 3 π← 数列 (1, 2, . . . , n) のランダムな置換 4 for i∈ π do 5 Li← arg maxl∈L ! !"j | (vi, vj)∈ E ∧ Lj= l#!! 6 end 7 until 終了条件を満たす 8 C ← 同じラベルの頂点を同じクラスタとして抽出 9 returnC 以上更新が行われない状態となる．そのため，最終的な結果として，二つのクラスタCA={v0, v1, v2}とCD={v3, v4, v5, v6} が得られる． 2. 3 GPUコンピューティング GPUコンピューティングは，元来グラフィックス処理用プロセッサであったGPUを，汎用的な計算の高速化に用いる技術のことである[18]．GPUはメニーコアプロセッサとして近年注目を集めており，科学計算やデータベース処理[13]，データマイニングアルゴリズムの高速化[24]など，幅広い応用が検討されてきている．GPUを用いたアプリケーションを開発す

る際には，NVIDIA社製のGPUと，NVIDIA社が提供する

CUDAフレームワーク（注 2）_{を用いることが主流となっている．}

GPUは複数のStreaming Multiprocessor (SM)から成り，

各SMは数十から数百のScalar Processor (SP)を搭載している．例えば，NVIDIA Tesla K40は15個のSMを持ち，各SM には192のSPが含まれている．各SPは単純な処理のみが可能な小さなプロセッサであるため，GPUは複雑な条件分岐などが含まれる処理を苦手とする．一方，比較的単純な処理を大量に行うような場合には，多数のSPによる並列処理が有効となり，高い性能を発揮できる．またGPU上には主要なメモリが三種類存在する．一つは， GPU上で最も容量の大きいデバイスメモリである．例えば， NVIDIA Tesla K40は12 GBのデバイスメモリを搭載している．しかし，デバイスメモリはSMの外に存在するため，デバイスメモリへのアクセスは比較的低速となる．SM上には，容量は数十KBと小さいが高速にアクセス可能なオンチップメモリがある．このメモリは，L1キャッシュやSM内でデータをやりとりするための共有メモリとして用いられる．また，最も高（注2）：http://www.nvidia.com/object/cuda_home_new.html

(3)

速にアクセス可能なメモリとして，各SM上にレジスタが存在する． CUDAでは上記の階層的なプロセッサやメモリ構成に対応するスレッディングモデルを定義している．まず，GPU全体に対応するものとしてグリッドがあり，グリッドは複数のブロックを含む．ブロックはSMに対応しており，一つのブロックはあるSMに割り当てられ，処理される．一方，一つのSMは複数のブロックを同時に動作させることが可能となっている．このとき，SMの資源（オンチップメモリなど）は複数ブロックで共有して用いられる．一つのブロックは多数のスレッドを持ち，各スレッドの処理はSPによって実行される．本節の残りでは，本研究で用いるデータ並列プリミティブについて説明する．データ並列プリミティブは，並列計算において頻出する処理であり，GPU向けに最適化された提案・ライブラリが存在する[2, 13]．本研究では，これらのプリミティブを活用することで，負荷分散を考慮した，高速なGPU上のラベル伝搬法を実現する． 2. 3. 1 Reduce Reduceは，入力として配列"a0, a1, . . . , an−1#と二項演算子 ⊕を受け取り，スカラ値a0⊕ · · · ⊕ an−1を返す演算である[13]．例えば，二項演算子として加算+が与えられた場合， reduceは入力配列中の値の和を返す． 2. 3. 2 Scan Scanは，入力として配列"a0, a1, . . . , an−1#，二項演算子⊕，単位元Iを受け取り，配列"I, a0, a0⊕ a1, . . . , a0⊕ a1⊕ · · · ⊕ an−2#を返す演算である[12]．Scanは，並列に出力を行なう際のオフセットの計算などによく用いられる． 2. 3. 3 Segmented Sort Segmented sort は，入力として二つの配列 A = " a0, a1, . . . , an−1#とS = "s0, s1, . . . , sm−1, sm = n#を受け取り，Aの各部分配列"asi, . . . , asi+1−1 #_{をそれぞれソートす} る演算である [2]．配列Sの各要素siは部分配列の先頭からのオフセットを示している．ナイーブな実装として，一つの部分配列に一つのブロックを割り当てソートするものが考えられるが，これは負荷分散の観点から見て良い実装とは言えない． Modern GPU [2]では，負荷分散を考慮して，各スレッドがほぼ同じ処理量となる実装をしている． 2. 3. 4 Segmented Reduce Segmented reduce は，入力として二つの配列 A = " a0, a1, . . . , an−1#, S ="s0, s1, . . . , sm−1, sm= n#と二項演算子_⊕を受け取り，Aの各部分配列"asi, . . . , asi+1−1 #_に対して reduceを適用した結果の配列"r0, r1, . . . , rm−1#を返す演算である[2]．ここで，ri= asi⊕ asi+1· · · ⊕ asi+1−1であり，配列 S の各要素siは，segmented sortの場合と同様に，部分配列の先頭からのオフセットを示している．Segmented reduceも， Modern GPUの一関数として，負荷分散を考慮した高速な実装が公開されている．

3. GPU

を用いたラベル伝搬法の高速化

本節では，GPUを用いたラベル伝搬法の高速化について述 ptr 0 1 2 3 4 5 6 7 0 2 4 7 10 13 16 18 id 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 2 0 2 0 1 3 2 4 5 3 5 6 3 4 6 4 5 v1の隣接頂点図2: GPU上のグラフデータ：二つの配列ptr とid によって図1中のグラフを表現している．べる．ラベル伝搬法では，ある頂点のラベルを更新する際，隣接頂点のラベル（以下，隣接ラベルと呼ぶ）を集計し，最も出現回数が多い隣接ラベルを求める必要がある．このとき，単純に頂点ごとにGPUのブロックを割り当て並列処理すると，次数の偏りのため，非効率的な並列化となってしまう．そこで，本研究では，次数の偏りによる影響を受けないような並列化を行なうことで，GPU上で効率的にラベル伝搬法を処理する．以降では，まず，3. 1節でGPU上のデータ表現形式について説明する．その後，隣接ラベルの出現回数を並列に集計する方法について3. 2節で，ラベル更新処理について3. 3節で述べる． 3. 1 GPU上のデータ表現形式ラベル伝搬法を処理するためには，以下の二種類のデータを GPU上に格納しておく必要がある：(1)入力グラフ，(2)各頂点のラベル情報．GPU上でこれらのデータを扱うためには，並列処理に適していると同時に，グラフの巨大さを考慮して，省メモリな構造を用いることが望ましい．ラベル情報は，単純に，各頂点のラベルを要素として持つ配列に格納すれば十分である．なお，本稿では説明の都合上，ラベルを文字で表すが，実際には0からn_{− 1}までの整数値によって表現している．一方，実世界のグラフデータを隣接行列として表した場合，疎行列になると考えられる．そこで，本研究では，疎行列表現形式の一つであるCSR (compressed sparse row) [3]を用いてグラフを表現する． CSRを用いたグラフデータの例を図2に示す．一つのグラフは二つの配列ptrとid によって表現される．配列idは各頂点の隣接頂点IDを格納しており，配列ptr はある頂点の隣接頂点IDが配列id中のどこに格納されているかを示している．例えば，図1中のv1の隣接頂点がv0とv2であるという情報は，配列id中のptr [1] = 2（注 3）_から_{ptr [2] = 4}_{番目の要素とし} て格納されている．通常，CSRでは行列の各成分の値を保持するために配列をもう一つ用いるが，重み無しグラフでは行列中の値が1か0のみであるため，ここでは省略している． 3. 2 隣接ラベル出現回数の計算上述のデータ構造をもとに，GPU上で隣接ラベルの出現回数を並列に計算する手法について説明する．この処理は，GPU 上での効率的な並列化のために，以下の4ステップに分けて行われる：(1)頂点IDから隣接ラベルへの射影，(2)頂点毎に隣接ラベルをソート，(3)隣接ラベル境界の抽出，(4)出現回数を計算．この4ステップへの分割は以下の考え方に基づいてい（注3）：A[i] は配列 A の i 番目の要素を表す．

(4)

id 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 2 0 2 0 1 3 2 4 5 3 5 6 3 4 6 4 5 L 0 1 2 3 4 5 6 B B A C D C D L′ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 B A B A B B C A D C C C D C D D D C 図3: 頂点IDから隣接ラベルへの射影：配列Lのi番目の要素はviのラベルを示している．る．頂点毎に隣接ラベルがソートされていれば，ある頂点に関する同じ隣接ラベルは配列中に連続して格納されている．すなわち，配列中で隣接ラベルが変わる位置（隣接ラベル境界）の情報があれば，同じ隣接ラベルが何回出現するかの計算が，特別にデータ構造を用意しなくとも，配列上の簡単な操作のみで可能となる．以降では，各ステップの具体的な処理方法について説明していく． 3. 2. 1 隣接ラベルへの射影図3に示しているように，隣接頂点IDの配列id と現在のラベル情報Lをもとに，各頂点の隣接ラベルの配列L′_を作成する．この例では，v0からv6のラベルが，それぞれB, B, A, C, D, C, D である場合を考えている．このステップは，単純に，1スレッドが配列idとLの各要素を調べ，出力を行うことで高速に並列処理可能である．具体的には，i番目のスレッドはL′_[i]_{← L[id[i]]}_{という処理をする．} 3. 2. 2 隣接ラベルのソート次に，前ステップで得られた隣接ラベルの配列L′を，頂点毎にソートする．すなわち，頂点viに関する部分配列をそれぞれ別々にソート対象として処理する．これは，2. 3. 3節で説明した，segmented sortを利用することで効率的に実現可能である．具体的には，入力配列Aとして隣接ラベルの配列L′を， S としてptr を渡してsegmented sortを実行することで達成できる． 3. 2. 3 隣接ラベル境界の抽出ソートされた隣接ラベル配列をもとに，隣接ラベル境界の抽出を行なう（図4）．このステップは，以下の三つの処理に分けて行われる：(1)隣接ラベル境界判定，(2)隣接ラベル境界出力オフセットの計算，(3)隣接ラベル境界抽出．隣接ラベル境界判定は，隣接ラベルがどの位置で変わるかを示すフラグの配列Fを作成する．ここでは，配列L′_の₁_要素に₁_スレッドを割り当て並列に処理する．具体的には，i番目の要素を担当するスレッドは，L′中の右隣りの要素を調べ，配列Fのi番

目にフラグを格納する．すなわち，L[i] |= L[i + 1]ならばF [i]

に1を，そうでなければ0を格納する．また，ラベルが等しい場合でも，異なる頂点に関する隣接ラベルである場合には，F に1を格納する．例えば，図4では，L′[3] = L′[4]であるが， F [3] = 1としている．次に，フラグ配列Fを用いて，隣接ラベル境界出力オフセットの計算を行なう．そのためには，2. 3. 2節で説明した，scan プリミティブを用いる．入力として，配列F，加算+，単位元 0を渡すことで，図4の配列F′が出力される． L′ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 A B A B B B C A C D C C D C D D C D F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 A= B?| → 1 B→ 0= B?| F′ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 2 3 4 4 5 6 7 8 9 9 10 11 12 12 13 14 Scan S 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 3 4 6 7 8 9 10 12 13 14 16 17 18 Sptr 0 1 2 3 4 5 6 7 0 2 4 6 9 11 13 15 0= 1?| +1 4= 4?| 図4: 隣接ラベル境界の抽出 Sptr 0 1 2 3 4 5 6 7 0 2 4 6 9 11 13 15 W 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 1 1 2 1 1 1 1 2 1 1 2 1 1 Segmented reduce Wmax 0 1 2 3 4 5 6 1 1 2 1 2 2 1 I 0 1 2 3 4 5 6 1 3 4 8 9 12 14 L 0 1 2 3 4 5 6 B B B D C D D 図5: ラベルの更新処理この配列をもとに，隣接ラベル境界の配列Sを作成する．隣接ラベル境界判定の場合と同様に，配列F′の1要素に1スレッドを割り当て並列に処理する．このとき，i番目の要素を担当するスレッドは，F′[i]とF′[i + 1]を比較し，異なればラベル境界を出力し，そうでなければ何も出力せずに処理を終える．出力を行う場合，i番目のスレッドは，配列S中のF′_[i]_番目に i + 1を書き込む．すなわち，S[F′[i]]_{← i}とする．また，同時に，配列Sにおいて隣接ラベル境界がどの頂点に関するものかを示すために，配列Sptrも計算しておく．この配列は，グラフデータにおけるptrと同様の役割を果たしている．Sptr は， Sptr [i]_{← F}′_{[ptr [i]]}_{とすることで並列に計算可能である．} 3. 2. 4 出現回数の計算前ステップで計算した配列Sを用い，隣接ラベル出現回数を持つ配列W を計算する．ここでも，配列Sの1要素に1スレッドを割り当て，並列に処理する．W [i]は，配列S中の隣

接する2要素の差，すなわちW [i]_{← S[i + 1] − S[i]}となる．

配列の境界部分においては（例えば，図4の配列SからW [0] を計算する場合），S[i]がそのまま出現回数となる． 3. 3 ラベル更新処理 3. 2節で計算した結果を用いて，実際にラベルの更新を行なう．そのためには，隣接ラベル出現回数の配列Wから，各頂点毎に，最も出現回数が多い隣接ラベルを求める必要がある．この処理は，2. 3. 4節で説明した，segmented reduceを利用することで，高速に実現可能となる．入力配列としてWとSptr，また二項演算子として二つの値を受け取り大きい値を返す関数 maxを渡すことで，各頂点毎に隣接ラベルの最大出現回数を求

(5)

Louvain CPU-LP GPU-LP 0 .0 0 .2 0 .4 0 .6 0 .8 1 .0 1 .2 1 .4 1 .6 1 .8

P

roc

es

si

n

g

T

im

e

(s

)

1.53 0.79 0.03 (a) amazon 0 .0 0 .5 1 .0 1 .5 2 .0 2 .5 2.10 1.10 0.03 (b) dblp 0 1 2 3 4 5 6 7 6.20 2.78 0.08 (c) youtube 0 20 40 60 80 100 120 103.75 30.46 0.88 (d) livejournal 0 50 100 150 200 192.75 83.49 3.32 (e) orkut 図6: クラスタリング処理時間表1: 使用した実データセットデータセット名 n m amazon 334 863 925 872 dblp 317 080 1 049 866 youtube 1 134 890 2 987 624 livejournal 3 997 962 34 681 189 orkut 3 072 441 117 185 083 果の配列のみを計算していたが，それだけでは実際にどのラベルに更新すれば良いかが判別できない．そのため，本研究では，

segmented reduceを拡張し，各reduce結果の値が入力配列の

どの位置から来たものかを示す配列Iも返すようにした．この結果を用いることで，最終的に，ラベルの更新処理が可能となる．具体的には，L[i]_{← L}′_[S[I[i]]]_{を計算することで，並列に} 更新可能である．

4. 評価実験

本節では，3.節で提案した，GPUを用いたラベル伝搬法の性能を評価する．まず，評価実験に用いた環境と比較手法を4. 1 節で説明し，その後，4. 2節において実データを用いたグラフクラスタリング処理時間の評価を，4. 3節で合成データを用いたグラフクラスタリング処理時間とクラスタリング精度の評価を行なう． 4. 1 実験設定

実験には，CentOS release 6.5 (Final)が動作するコンピュー

タを用いた．CPUとしてIntel Xeon Processor E5-2687W v2 (3.40 GHz)を，メモリは128 GBを搭載している．また，GPU

はNVIDIA Tesla K40 (15 SM, 2880 SP, 12 GB) を備えている．

提案のGPUによるラベル伝搬法(GPU-LP )は，CUDA 7.0

を用いて実装した．比較手法として，ラベル伝搬法のCPUによる逐次処理 (CPU-LP )と近年注目されているグラフクラスタリングアルゴリズムの一つであるLouvain法[4]を用いた． Louvain法は，グラフクラスタリング結果の評価指標であるモジュラリティ[17]を，貪欲法により最適化する手法であり，高 CPU-LP GPU-LP 1 2 3 4 5 6 7 8 9 10 Iteration 0 1 2 3 4 5 6 7 8 P roc es si n g T im e (s ) (a) livejournal 1 2 3 4 5 6 7 8 9 10 Iteration 0 5 10 15 20 25 (b) orkut 図7: 各イテレーションにおける処理時間速かつ高いモジュラリティの結果を出力できることで知られている[19]．Louvain法の実装には，著者らによって公開されているものを利用した．（注4）_{なお，本実験ではラベル伝搬法の終} 了条件を，「ラベルが更新された頂点数が10−5n以下になる，またはラベル更新処理のイテレーションを10回行なう」と設定した． 4. 2 実データによる評価本節では，実データを用いたグラフクラスタリング処理時間の評価を行なう．具体的には，CPU側のメモリ上にグラフデータが準備できている状態から，クラスタリング結果を計算し終えるまでの時間を計測した．提案手法GPU-LP では， CPUとGPU間のデータ転送時間も含めている．データセット

は，Stanford Network Analysis Project [14]で公開されてい

るデータセットの一部を利用した．用いたデータセットを表1 にまとめる．これらは，全て実世界のソーシャルネットワークやウェブグラフを表している．図6に，五つのデータセットを用いた場合のクラスタリング処理時間を示す．全体としては，GPU-LP が最も高速で，次にCPU-LP，Louvainという順の性能になっている．この結果から，GPU-LP はGPUを用いることで，大幅なクラスタリング処理の高速化に成功していることがわかる．具体的には，

Louvainと比較して，amazonとorkutと用いた場合には約55

(6)

Louvain CPU-LP GPU-LP 1 2 3 4 5 6 7 8 9 10 Number of vertices (×105₎ 0 1 2 3 4 5 6 P roc es si n g T im e (s ) (a) クラスタリング処理時間 1 2 3 4 5 6 7 8 9 10 Number of vertices (×105₎ 0.0 0.2 0.4 0 .6 0 .8 1 .0 NMI (b) NMI 1 2 3 4 5 6 7 8 9 10 Number of vertices (×105₎ 0.0 0.2 0.4 0 .6 0 .8 1 .0 F -m ea s u r e (c) F 値 1 2 3 4 5 6 7 8 9 10 Number of vertices (×105₎ 0.0 0.2 0.4 0 .6 0 .8 1 .0 ARI (d) ARI 図8: 合成データを用いた実験結果倍の高速化，dblpとyoutubeを用いた場合には約70倍の高速化に成功している．livejournalの場合（図6(d)）には，特に高速化の度合いが大きく，117倍の高速化を達成している．

GPU-LP とCPU-LP を比較すると，GPU-LP が25倍か

ら36倍の処理性能となった．具体的には，三つのデータセットdblp, youtube, livejournalの場合には，35倍前後の高速化に達成した．一方，今回使用したデータセット中で最も巨大な orkutの場合には，25倍の性能向上と，他のデータセットにおける高速化度合いよりは多少劣る結果となった．これは，図7 に示すように，CPU-LPはイテレーションが進み，ラベル数が少なくなるに連れて処理時間が大きく減少するためである．図から分かるように，livejournalの場合と比較して，orkutの場合の方が処理時間の減少度合いがより急であるため，CPU-LP が相対的に短い時間で処理を完了した．一方，GPU-LPでは，負荷分散の達成のためにラベル数に依存しない実装としているため，イテレーション毎の処理時間はほぼ一定であり，概ねグラフの辺数に比例した時間となる．以上のことから，orkutの場合には，25倍の性能向上に収まったと考えられる． 4. 3 合成データによる評価本節では，クラスタリング処理時間だけでなくクラスタリング結果の精度も評価するために，合成データを用いた実験結果を示す．合成データとしては，グラフクラスタリングアルゴリズムの評価において良く用いられている，LFR (Lancichinetti– Fortunato–Radicchi)ベンチマーク[15]によって生成したものを用いた．LFRベンチマークは，正解クラスタ情報を持ったグラフを生成するため，この情報を用いて精度の評価を行う．精度の評価には以下の三つの指標を用いた[5]：(1) NMI

(normal-ized mutial information)，(2) F値，(3) ARI (adjusted Rand index)．

NMIは情報理論的考え方に基づき，二つのクラスタリング

結果_{C, C}′_{間の類似度を測る指標である：}

NMI(_{C, C}′) = −2 $

i,jNijlog(NijNt/Ni·N·j)

$ iNi·log(Ni·/Nt) + $ jN·jlog(N·j/Nt) ここで，Nは混同行列であり，Nijは正解クラスタCiとアルゴリズムによって検出されたクラスタCj′に共通して現れる頂点の数である．また，Ni·とN·jはそれぞれ行列Nのi行の和とj列の和であり，Ntは行列N全体の和を示している．NMI は0から1の値を取り，もっとも良い場合，すなわち正解と同じクラスタが得られた場合に1となる． F値は二つのクラスタリング結果間のクラスタのマッチングに基づき，類似度を求める指標である： F(_{C, C}′) = 1 n % Ci∈C |Ci| max C′ j∈C′ 2|Ci∩ Cj′| |Ci| + |Cj′| F値は，NMIと同様に，0から1の値を取り，最良の場合に1 となる． ARIはペアの数え上げによって，クラスタリング結果を評価する指標である： ARI(C, C′) = $ i,j &Nij 2 ' − M 1 2 ($ i &Ni· 2 ' +$_j&N·j 2 ') − M ここで，N はNMIの場合と同様の混同行列であり，M = "$ i &Ni· 2 ' $ j &N_·j 2 '# /&n₂'である．ARIも，他の二つの指標と同様に，最良の場合に1となる． LFRベンチマークによる合成データを用いた実験結果を図8 に示す．データ生成の際，パラメタは平均次数を20，最大次数を50とし，頂点数を10万から100万まで10万刻みで変化させた．図8(a)は横軸を頂点数とし，縦軸に処理時間を示している．また，図8(b)から図8(d)は各評価指標の値を示している．

GPU-LP は，Louvainと比較して平均24倍の性能，

CPU-LPと比較して平均10倍の性能となった（図8(a)）．実データを用いた場合よりも性能向上率が低い原因はGPU-LP 収束の遅さである．このデータでは，CPU-LP は3回または4回のイテレーションでラベルの更新を終了するが，GPU-LPは上限の10回まで行なっている．これは，ラベルの更新タイミングの違いに起因すると考えられる：CPU-LPでは，ある頂点の更新先ラベルを計算したら，すぐにその頂点のラベルを更新する．一方，GPU-LPでは，現在のラベルの状態をもとに，全ての頂点のラベルを一斉に計算し，同時に更新するという方式となっている．この方式は，CPU-LPが取っている方式と比較して，収束が遅いことが知られている[16]．この欠点は，近年提案された半同期的方式[6, 9]を採用することで解消できると考えられる．精度に関しては，Louvainと比較して，ラベル伝搬法に基づく手法（CPU-LP，GPU-LP）が非常に良い性能を示している

(7)

（図8(b)–(d)）．CPU-LPとGPU-LPは同等の性能を示しており，また頂点数によらず一定の値を取っている．一方，Louvain は頂点数を増やすにつれて，精度が劣化していくという現象が見られる．これは，Louvainが利用している指標であるモジュラリティが持つ欠点の一つの，resolution limit [10]（5.節）に起因するものと考えられる．以上の結果から，ラベル伝搬法が，処理性能と精度の両方において優れた性能を達成可能なことが確認できた．

5.

6. 結

論

本稿では，GPUを用いたグラフクラスタリングの高速化手法を提案した．具体的には，ラベル伝搬法をベースに，GPU上での高並列な処理に適した並列化を行なうことで高速化を図った．特に，segmented sortやsegmente reduceなどの，次数の偏りが存在するデータにおいても効率的に並列処理可能な演算を活用した．実世界のデータと合成データを用いた評価実験により，GPUによるラベル伝搬法が，既存手法と比較して，最大で117倍の高速化を達成可能なことを示した．また，クラスタリング精度の観点においても，良い性能を示すことを確認した．今後の課題としては，GPUによるラベル伝搬法のさらなる高速化が挙げられる．例えば，収束を早めるために半同期的方式を導入することで高速化が可能であると考えられる．謝辞本研究の一部は科学研究費補助金基盤研究 B （26280037）および科学研究費補助金特別研究員奨励費（15J02121）によるものである．文献

[1] A.-L. Barab´asi and R. Albert, “Emergence of scaling in ran-dom networks,” Science, vol. 286, pp. 509–512, Oct. 1999. [2] S. Baxter, “Modern GPU,” http://nvlabs.github.io/

moderngpu/, 2013.

[3] N. Bell and M. Garland, “Implementing sparse matrix-vector multiplication on throughput-oriented processors,” in Proceedings of the Conference on High Performance Com-puting Networking, Storage and Analysis (SC), pp. 18:1– 18:11, Nov. 2009.

(8)

[4] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefeb-vre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, pp. P10008:1–P10008:12, Oct. 2008. [5] M. Chen, K. Kuzmin, and B. K. Szymanski,

“Commu-nity detection via maximization of modularity and its vari-ants,” IEEE Transactions on Computational Social Sys-tems, vol. 1, no. 1, pp. 46–65, Mar. 2014.

[6] G. Cordasco and L. Gargano, “Label propagation algo-rithm: A semi-synchronous approach,” International Jour-nal of Social Network Mining, vol. 1, no. 1, pp. 3–26, 2012. [7] L. Danon, A. Daz-Guilera, J. Duch, and A. Arenas, “Com-paring community structure identification,” Journal of Sta-tistical Mechanics: Theory and Experiment, vol. 2005, no. 09, pp. P09008:1–P09008:10, Sep. 2005.

[8] H. N. Djidjev and M. Onus, “Scalable and accurate graph clustering and community structure detection,” IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 5, pp. 1022–1029, May 2013.

[9] E. Duriakova, N. Hurley, D. Ajwani, and A. Sala, “Anal-ysis of the semi-synchronous approach to large-scale paral-lel community finding,” in Proceedings of the Second ACM Conference on Online Social Networks (COSN), pp. 51–62, Oct. 2014.

[10] S. Fortunato and M. Barthlemy, “Resolution limit in com-munity detection,” Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no. 1, pp. 36–41, Dec. 2007.

[11] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3–5, pp. 75–174, Feb. 2010.

[12] M. Harris, “Parallel prefix sum (scan) with CUDA,” http: //developer.download.nvidia.com/compute/cuda/2_2/sdk/ website/projects/scan/doc/scan.pdf, 2009.

[13] B. He, M. Lu, K. Yang, R. Fang, N. K. Govindaraju, Q. Luo, and P. V. Sander, “Relational query coprocessing on graph-ics processors,” ACM Transactions on Database Systems, vol. 34, no. 4, pp. 21:1–21:39, Dec. 2009.

[14] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/ data, Jun. 2014.

[15] A. Lancichinetti, S. Fortunato, and F. Radicchi, “Bench-mark graphs for testing community detection algorithms,” Physical Review E, vol. 78, no. 4, pp. 046110:1–046110:5, Oct. 2008.

[16] I. X. Y. Leung, P. Hui, P. Li`o, and J. Crowcroft, “Towards real-time community detection in large networks,” Physical Review E, vol. 79, no. 6, pp. 066107:1–066107:10, Jun. 2009. [17] M. E. J. Newman and M. Girvan, “Finding and evaluat-ing community structure in networks,” Physical Review E, vol. 69, no. 2, pp. 026113:1–026113:15, Feb. 2004.

[18] J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone, and J. C. Phillips, “GPU computing,” Proceedings of the IEEE, vol. 96, no. 5, pp. 879–899, May 2008.

[19] S. Papadopoulos, Y. Kompatsiaris, A. Vakali, and P. Spyri-donos, “Community detection in social media,” Data Min-ing and Knowledge Discovery, vol. 24, no. 3, pp. 515–554, May 2012.

[20] X. Que, F. Checconi, F. Petrini, and J. Gunnels, “Scalable community detection with the Louvain algorithm,” in Pro-ceedings of the 2015 IEEE International Parallel & Dis-tributed Processing Symposium (IPDPS), pp. 28–37, May 2015.

[21] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Physical Review E, vol. 76, no. 3, p. 036106, Sep. 2007.

[22] H. Shiokawa, Y. Fujiwara, and M. Onizuka, “Fast algorithm for modularity-based graph clustering,” in Proceedings of

the Twenty-Seventh AAAI Conference on Artificial Intelli-gence (AAAI), pp. 1170–1176, Jul. 2013.

[23] J. Soman and A. Narang, “Fast community detection algo-rithm with GPUs and multicore architectures,” in Proceed-ings of the 2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS), pp. 568–579, May 2011. [24] T. R. Stovall, S. Kockara, and R. Avci, “GPUSCAN:

GPU-based parallel structural clustering algorithm for networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 12, pp. 3381–3393, Dec. 2015.

[25] M. Wang, C. Wang, J. X. Yu, and J. Zhang, “Community detection in social networks: An in-depth benchmarking study with a procedure-oriented framework,” Proceedings of the VLDB Endowment, vol. 8, no. 10, pp. 998–1009, Jun. 2015.

[26] X. Xu, N. Yuruk, Z. Feng, and T. A. J. Schweiger, “SCAN: A structural clustering algorithm for networks,” in Proceed-ings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 824– 833, Aug. 2007.

GPUを用いたラベル伝搬法によるグラフクラスタリングの高速化

DEIM Forum 2016 A8-3