DEIM Forum 2017 E2-2

メニーコアプロセッサを用いた構造的類似度に基づく
グラフクラスタリングの高速化
高橋 知克†

塩川 浩昭††博之††北川† 筑波大学大学院システム情報工学研究科 〒 305–8573 つくば市天王台 1–1–1†† 筑波大学計算科学研究センター 〒 305–8573 つくば市天王台 1–1–1
E-mail: †shihakata@kde.tsukuba.ac.jp, ††{shiokawa,kitagawa}@cs.tsukuba.ac.jp
あらましグラフクラスタリングはグラフの中に存在するコミュニティ構造を理解する上で重要な要素技術である．

その中でもノード間の構造的類似度に基づいた手法である SCAN は，高い精度でクラスタを検出するとともにハブや外れ値を同時に抽出できることから幅広く利用されている．しかしながら，SCAN は全てのエッジに対して構造的類
似度計算を行う必要があることから計算量が大きく大規模なグラフへの適用が難しい．そこで本稿では，メニーコア
プロセッサ Intel Xeon Phi を活用し，そのハードウェア特性を考慮した SCAN の高速化手法 SCAN-XP を提案する．
提案手法では，(1) 実グラフにおける次数分布の偏りやクラスタ検出処理における計算の衝突等の並列化ボトルネッ
クを解消するともに，(2)Intel Xeon Phi の持つ 512 ビット SIMD 演算へのアルゴリズムの最適化を行う．本稿では実データを用いた評価実験を行い提案手法の有効性を示す．
キーワード グラフクラスタリング，Intel Xeon Phi，SIMD 演算
CLUSTER

1. は じ め にグラフとはデータエンティティ間の関係をノードとエッジに
近年では，グラフを解析することで有用な情報を抽出する技術に注目が集まっており，データマイニング [1, 2] やソーシャルサイエンス [3] などの幅広い分野で研究されている. しかし，イ100より表現したデータ構造であり，様々な分野で活用されている.

3
4

7
OUTLIER

CLUSTER

2

1

6

14

HUB
8

9

11

5

13
12

図 1: SCAN によるグラフクラスタリングの例

ンターネットの普及に伴いグラフデータの大規模化が進んでお従来手法と SCAN の違いを示すために，実際に SCAN をグり，例えば Twitter のユーザをノード，ユーザ間のフォロー/

ラフに対して適用した例を図 1 に示す．SCAN によりクラスタ

フォロワー関係をグラフとして表現すると，数億ノードから構

リングを行った場合，クラスタとの橋渡しをしているノードと成される大規模グラフとなる. したがって，このような大規模クラスタとの関連性が薄いノードはそれぞれハブと外れ値としグラフを高速に解析する手法の需要が高まっている.

て判定されるため，クラスタとして {0, . . . , 6} と {9, . . . , 14}

グラフクラスタリングはグラフ構造解析手法のひとつである．

が得られ，ハブとしてノード 8，外れ値としてノード 7 が検出

グラフクラスタリングは密に接続されたノードの集合をクラスされる. 一方で従来手法の中で最も代表的な Modularity を用タとして検出することで，隠れたコミュニティ構造を抽出する

いた手法を図 1 と同様のグラフに対して適応した場合，2 つのことができる．そのため，近年では多くの手法が提案されておクラスタとして {0, . . . , 7} と {8, . . . , 14} の 2 つの集合が得らり，min-max cut による手法 [4, 5] や Modularity [6] に基づく

れるが，ハブと外れ値を検出することはできない．このように，

手法 [7–10] など様々な研究が行われてきた．

SCAN はグラフの構造をより高い精度で検出できる．

特に 2007 年に Xu らにより提案された SCAN [11] は多次元

しかしながら，SCAN は計算コストが大きいという問題点がベクトルに対する密度ベースのクラスタリング DBSCAN [12]ある．SCAN はクラスタを抽出するためにグラフ G = {V, E}

を基に考案された構造的類似度に基づくグラフクラスタリングに含まれる全てのエッジに対しての構造的類似度と呼ばれる手法であり，高精度にクラスタリングが可能であることが知ら

ノード間の接続の強さを示す評価指標を計算する必要がある．

れている. SCAN の大きな特徴は，ノード間の構造的類似度をこの処理は |E| をエッジ数，|V | をノード数とした場合，最悪計算することで，従来手法で検出されるようなクラスタだけで計算量が O(|E|) = O(|V |2 ) となる. さらに，各エッジの構造なく，グラフ中の特別な役割を持つノードであるハブと外れ値的類似度を計算するためには対象とするエッジに接続される 2を見つけることである．ハブは複数のクラスタ間の橋渡しをす

つのノードの共通の隣接ノードを計算する必要がある．結果とるように繋がっているノードであり，バイラルマーケティング

して，SCAN の平均計算量は O(|E|2 /|V |) となり，最悪計算量等の分野で重要なデータである．一方で外れ値はクラスタとのは O(|E|1.5 ) となる．したがって，大規模グラフに対して膨大関係性が低いノードであり，一般的にノイズとして扱われる．

な計算時間を必要とするため，適用が難しいという問題がある．

1. 1 先行研究と課題

表 1: 記号の定義

SCAN を高速化するために，多くのクラスタリングアルゴ リ ズ ム が 提 案 さ れ て き た.

Lim ら に よって 提 案 さ れ た∗

LinkSCAN [13] はクラスタリングの高速化を行うためにエッジ
サンプリング手法を取り入れた近似的手法である. LinkSCAN∗
はエッジのサンプリングにより，構造的類似度計算が必要なエッジの数を削減している. しかしながら，得られるクラスタ
リング結果は近似解となり，SCAN と同等のクラスタリング結果が得られる保証はされていない.

Symbol
G
V
E
C
H
O
Γ(v)
Nϵ (v)
D(v)
C(v)
ϵ
µ
α, β
σ(u, v)Definition
与えられたグラフ．
G 中のノードの集合．
G 中のエッジの集合．
G から抽出されたクラスタの集合．
G からハブとして分類されたノードの集合．
G から外れ値として分類されたノードの集合．
ノード v の構造的隣接ノード集合．
ノード v の ϵ − neighborhood であるノードの集合．
ノード v から Direct structure reachability であるノードの集合．
ノード v と同じクラスタに属するノードの集合．
構造的類似度の閾値, 0 <=ϵ<= 1．
core となるために必要な構造的類似な隣接ノードの個数の閾値．
SCAN-XP で用いられる Block size のパラメータ．
u と v 間の構造的類似度．

SCAN と比較してクラスタリングの精度を落とすこと無く，計算速度を向上させる手法として，Shiokawa らによる

SCAN やその拡張手法は幅広いアプリケーションで利用され

SCAN++ [14] や Chang らによる pSCAN [15] がある．これているが，膨大な計算時間がボトルネックとなり大規模グラフ

らの手法は実世界のグラフに内包された構造特性の利用や計算に適応することは難しい．しかしながら，Intel Xeon Phi 上で結果が明示であるエッジへの計算回数の削減により，SCAN の大規模並列化を行うことにより，SCAN-XP はより広い範囲の高速化に成功している．しかし，どちらの手法も計算量は依然

アプリケーションの性能向上に貢献できる．

として O(|E|) を必要とする．ゆえに 1 億以上のエッジを持つ

本稿の構成は以下の通りである. まず，2. 節において前提知非常に大規模なグラフへの適用は未だ難しい．したがって，構識について説明する. 続いて 3. 節で本稿で提案する高速化手法

造的類似度に基づくグラフクラスタリングの更なる処理性能のについて述べ，その評価を 4. 節で行う. そして 5. 節では関連向上は依然として重要な課題となっている研究について示し，6. 節ではまとめと今後の課題を述べる．

1. 2 本研究の貢献
上記の課題を解決するために，本稿ではメニーコアプロセッサ

2. 前 提 知 識

である Intel Xeon Phi を用いて大規模グラフを高速に処理する

本節では，構造的類似度に基づくグラフクラスタリングの基

構造的類似度に基づくクラスタリング手法 SCAN-XP (Struc-

本的なアルゴリズムである SCAN および本研究で用いるメニー

tural Clustering Algorithm for Network over Xeon Phi) を提

コアプロセッサ Intel Xeon Phi について述べる．

案する．SCAN において構造的類似度の計算はエッジごとに独2. 1 従来手法 SCAN

立していることから，並列化による高速化が期待できる．特に本節では，従来手法 SCAN を基に構造的類似度に基づくク

近年では多くの演算コアを搭載したメニーコアプロセッサの発

ラスタリングの定義を述べる．SCAN では，与えられた無向重展がめざましく，高性能計算分野を中心に Intel Xeon Phi や

みなしグラフ G = {V, E} に対して，クラスタ集合 C ，ハブ集

GPU (Graphics Processing Unit) などを活用した並列化によ合 H ，外れ値集合 O を抽出する．

るデータ処理の高速化が注目されている．

SCAN はエッジで繋がれた 2 つのノード間に対して，自身とそこで SCAN-XP では Intel Xeon Phi を用いた高速かつス

その隣接ノードを含めたノードの集まりである定義 2.1 で示さケーラブルなグラフクラスタリング手法を開発する．具体的にれる構造的隣接ノード集合 Γ(v) の比較に基づき，定義 2.2 では，SCAN-XP は並列化におけるボトルネックとグラフの次数示される構造的類似度 σ(v, w) を計算する.

の偏りによる負荷分散の問題を解消するとともに，Intel Xeonv ∈ V が与えられたとPhi の持つ 512 ビット SIMD 演算を各構造的類似度計算に対し定義 2.1 (構造的隣接ノード集合)て適用し並列処理効率の向上を図る．

き ，ノ ー ド v の 構 造 的 隣 接 ノ ー ド 集 合 は Γ(v) と す る と ，

本研究の貢献は下記のとおりである．

•

高速性：SCAN-XP は従来手法 SCAN と比べ非常に高速にクラスタリングを行うことが出来る．SCAN-XP は 8.5 億のエッジを持つグラフを約 36 秒でクラスタリングする (4. 1 節)．

•

スケーラビリティ：SCAN-XP は従来手法 SCAN の持つ並列化ボトルネックを解消することにより，効率的な並列化を行う事ができる (4. 2 節)．

•

正確性：SCAN-XP は従来手法 SCAN と同じクラスタ

リング結果を得ることができる (3. 4 節)．
我々の知る限り，SCAN-XP は構造的類似度に基づくグラフ
クラスタリングに対して Intel Xeon Phi の高い演算性能を利用

Γ(v) = {v, w ∈ V |{v, w} ∈ E} ∪ {v}．
定義 2.2 (構造的類似度)

v, w ∈ V が 与 え ら れ た と き ，

構 造 的 類 似 度 は σ(v, w) と す る と ，σ(v, w) = |Γ(v) ∩√Γ(w)|/ |Γ(v)||Γ(w)|．
定義 2.2 に基づき計算されたノード v とその隣接ノード w の構造的類似度が与えられた閾値 ϵ 以上を示すとき，ノード v と
ノード w は構造的に類似であるとみなされる．ここであるノード v と構造的に類似な隣接ノードの集合を ϵ − N eighborhoodと呼び，Nϵ (v) と表す．そして，|Nϵ (v)| が閾値 µ 以上のとき v
は core となる．core は以下の定義 2.3 で示される．

した最初の手法である．我々の行った評価実験により，SCAN-

XP はグラフ中のクラスタ，ハブ，外れ値を従来手法 SCAN と比較して 100 倍以上高速に検出できることを確認した．

v ∈ V と ϵ ∈ R, µ ∈ N が与えられたとき，
v が core である必要十分条件は，|Nϵ (v)| >= µ である．

定義 2.3 (Core)SCAN では，定義 2.3 で示された core を検出し，core をク
ラスタの中心として Direct structure reachability なノードを同一クラスタとして検出していくことでクラスタリングを行う．

Direct structure reachability なノードとはある core ノード v
から見て Nϵ (v) に含まれるノードを指し，その集合を D(v) とする．SCAN は D(v) に含まれる全てのノード w ∈ D(v) を vと同じクラスタに割り当てる．更に，クラスタに割り当てられたノード w ∈ D(v) が core だった場合は D(w) に含まれるノードを同一クラスタとして割り当てることでクラスタを拡張する.
一方で，w ∈ D(v) が core ではない場合はクラスタはそれ以上拡張されない. SCAN は同一クラスタとして検出された全てのcore から Direct structure reachability なノードを同じクラス
タに割り当てるまで繰り返される．このようにある core v から Direct structure reachability を満たすノードを辿った先にあるノードを core v からの Structure reachability を満たすという．構造的類似度に基づいたグラフクラスタリングでは，ある core から Structure reachability を満たすノードを全て同一
クラスタとして検出する．構造的類似度に基づいたグラフクラスタリングのクラスタは次のように定義される．
定義 2.4 (クラスタ)

core v のクラ ス タを C(v) とす る と ，C(v) = {u ∈ D(w)|w ∈ C(v)}．ここで C(v) の初期状態はC(v) = {v} である．

Algorithm 1 Baseline method: SCAN [11]Input: G = {V, E}, ϵ ∈ R, and µ ∈ N
Output: C, H, and O
1: ∀v ∈ V are labeled as unclassified;2:
3: // Step 1: Core detection based on Definition 2.3
4: for each edge(v, w) ∈ E do
5:compute σ(v, w) by Definition 2.2;
6: end for
7:
8: // Step 2: Cluster construction based on Definition 2.4
9: for each unclassified node v ∈ V do10:
if Nϵ (v) >= µ then11:
generate new clusterID, and add v into C(v);12:
all w ∈ Nϵ (v) into queue Q;
13:
while Q =| ∅ do14:
u = Q.pop;
15:
for each w ∈ D(u) do
16:
if w is unclassified or non-member then17:
assign current clusterID to w, and add w into C(v);18:
end if19:
if w is unclassified then20:
insert w into Q;
21:
end if
22:
end for23:
end while24:
addC(v) into C;
25:
else
26:
v are labeled as non-member ;27:
end if
28: end for29:
30: // Step 3: Hubs/outliers detection based on Definition 2.5
31: for each non-member node v do
32:
if ∃u, w ∈ Γ(v) s.t. C(u) =| C(w) then33:label node v as hub, and H = H ∪ {v};
34:
else
35:
label node v as outlier, and O = O ∪ {v};36:
end if37: end for

定義 2.4 で示されたクラスタを全て検出した後，定義 2.5 に基づきクラスタに属していないノードを 2 つ以上のクラスタと2. 2 Intel Xeon Phi

隣接しているならばハブ，そうでない場合は外れ値に分類する．

Intel Xeon Phi [16] は Intel から提供されているメニーコア
プロセッサである．現在までに，KNC (KNights Corner) と定義 2.5 (ハブと外れ値)

グラフ中のノード u ∈/ C が与えら

KNL (KNights Landing) の 2 つが発売されている.

れたとき， その隣接ノードが 2 つ以上のクラスタに属してい

KNC は第 1 世代の Xeon Phi である．KNC は GPU と同じ

た場合 u はハブである．一方で，ハブの条件を満たさない場合

ようなカードの形でのみ提供され，PCIe によりホストと通信

は u は外れ値である．

する．内部では独立して Linux OS が動作しており，GPU と

SCAN のアルゴリズムを Algorithm 1 に示す．初期状態で全てのノードにラベルとして unclassified が与えられている．

SCAN アルゴリズムは Step 1 にて，グラフ中の全てのエッジに対して構造的類似度を計算する．そして，ϵ 以上の構造的類似度を持つエッジを µ 個持つノードを core として検出する．そして，Step 2 においては，検出した core を用いてクラスタの検出を行う．unclassified なノードに対して，それが core でない場合はラベルを non-menber に変更する．一方で core である場
合はそのノードをクラスタの核とする．そして，構造的類似度に基づくクラスタリングの定義に基づき，core から Structure

reachability を満たすノードを全て同一クラスタとして検出す
る．同一クラスタとして検出されたノードのラベルはクラスタ

ID に書き換えられる．これらの処理は unclassified なノードがなくなるまで繰り返す．最後に Step 3 において，non-memberとラベル付けされたノード，つまりクラスタに属していないノードに対して，ハブか外れ値かの判定を行う．それぞれクラ
スタ ID の異なる隣接ノードが存在する場合はハブ，そうでない場合は外れ値として判定する．

は異なり単体でのプログラムの実行も可能である．57 から 61の物理コアを搭載し，各コアは 512 ビットの SIMD 演算機を持
ち，1.10 GHz で動作する．また，6GB から 16GB のオンチッ
プメモリを持ち，各コアは高速にオンチップメモリに高速にアクセスすることが可能である．KNC は倍精度浮動小数点演算
で 1TFLOPS 以上の性能を発揮する．

KNL は第 2 世代の Xeon Phi であり，現在最も新しい機種である．KNL は KNC と同様のカードの形態だけでなく，単体で動作する CPU という 2 つの形で提供されている．KNL は最大72 個の物理コアを持つ．各コアは KNC と同様に 512 ビットの SIMD 演算機が搭載されており，1.3GHz から 1.5GHz で動作する．更に，KNL は 16GB のオンチップメモリ MCDRAMと最大 384GB の DDR4 メモリを利用できる．KNL は倍精度浮動小数点演算で 3TFLOPS 以上の性能を発揮する．
上記で述べた通り，Xeon Phi は非常に高い演算性能を持っているが，その性能を発揮するためにはプログラムを Xeon Phiに最適化することが必要である．なぜならば，各コア一つ一つの性能は CPU に大きく劣るからである．したがって，演算性

Algorithm 2 SCAN-XP
Input: G = {V, E}, ϵ ∈ R and µ ∈ N
Output: C, H, and O
1: ∀v ∈ V are labeled as unclassified;2:
3: // Step 1: Parallel core detection in Section 3. 2
4: for each edge (v, w) ∈ E do in parallel5:
run Algorithm 3;
6: end for
7:
8: // Step 2: Parallel cluster construction in Section 3. 3
9: for each core node v ∈ V do in parallel10:
for each w ∈ Nϵ (v) do
11:
if find(v) =| find(w) then12:
get C(v) ∪ C(w) by using union(v, w) and CAS instruction;
13:
node v and node w are labeled as cluster-member ;14:
end if15:
end for
16: end for
17:
18: // Step 3: Parallel hubs/outliers detection
19: for each node v that is not included in any clusters of C do in parallel20:
if ∃u, w ∈ Γ(v) s.t. C(u) =| C(w) then21:label node v as hub, and H = H ∪ {v};
22:
else
23:
label node v as outlier, and O = O ∪ {v};24:
end if
25: end forptr

0 2 5 7 8

to

1 2 0 2 3 0 1 1

2

3

1

Adjacent nodes of node 1

0

from

0 0 1 1 1 2 2 3

図 2: グラフを格納するデータ形式の例

性能を十分に発揮する実装が難しいという問題点がある．本手法で提案する Union-Find 木を用いた手法は並列化ボトルネッ
クを改善し，効率的なクラスタ検出を実現する．最後に Step 3のハブ・外れ値検出処理では，ノード単位でのスレッド並列化を行う．Step 3 については OpenMP を用いた単純な並列化であるため本稿では詳細な説明は割愛する．

3. 2 core 検出の並列化
core 検出処理では全てのエッジに対する構造的類似度計算が多くの計算時間を占めている．そこで，Xeon Phi を用いたス
レッド並列化と SIMD 演算を用いたデータ並列化による構造的能を十分に発揮するためには各コアを十分に利用した並列化と512 ビットの SIMD 演算を活用できるアルゴリズムを設計する

類似度計算の高速化を行う．

3. 2. 1 構造的類似度計算のスレッド並列化必要がある．また，メモリアクセスのレイテンシが大きいため

core 検出処理における構造的類似度の計算がグラフ中の各

キャッシュヒット率の高いデータ構造や明示的なプリフェッチ

エッジに対して独立していることに着目し，Xeon Phi の持つ命令の利用などメモリアクセスに伴うレイテンシの隠蔽を考慮

大量の物理コアを活用しスレッド並列化を行う．各構造的類似してプログラムを作成する必要がある．

度の計算は独立しているが，単純にノード単位でスレッド並列

3. 提案手法 SCAN-XP化をした場合，グラフの次数分布の偏りからスレッド間の負荷分散に偏りが生じるという問題がある．

本節では提案手法 SCAN-XP について概説する．SCAN-XP

上記の問題について，グラフ処理で一般的に使用されているのアルゴリズムを Algorithm 2 に示す．最初に SCAN-XP のデータレイアウト CRS (Compressed Row Storage) 形式 [1,17]

基本的なアイデアを 3.1 節で述べる．その後，各手法の詳細にを用いてより詳細に説明する．CRS 形式は ptr 配列と to 配列

ついて 3.2 節以降で説明する．

からなるデータレイアウトである．to 配列はノード 0 の隣接

3. 1 基本アイデア

ノードから順に各ノードの隣接ノードが連続して格納されてい前節で述べた通り，SCAN はグラフに含まれる全てのエッジ

る．ptr 配列は to 配列のどこにどのノードの隣接ノードが格納に対して構造的類似度を計算する必要がある．したがって，高されているかを示すポインタである．CRS 形式は連結リスト方速化のためには精度を落とすことなく，いかにして構造的類似

式などに比べて空間効率やキャッシュ効率の面で良いという利度を高速に計算するかが重要な課題となる．この課題を解決点があるため，Xeon Phi 上でグラフを処理する場合に非常にするために，Xeon Phi の高い並列計算性能用いた高速化手法有効である．しかしながら，CRS 形式を用いてスレッド並列化

SCAN-XP を提案する．SCAN-XP は Algorithm 1 で示したをする場合，to 配列からは元のノードを参照できないため，ptr(Step 1) core 検出処理，(Step 2) クラスタ検出処理，および配列の要素単位，すなわちノード単位での並列化を行う必要が(Step 3) ハブ・外れ値検出処理の 3 つのステップそれぞれをある．ところが，グラフは一般的にべき条則に従う次数分布を

Xeon Phi を用いて並列化および最適化する．

持つことが知られているため [18]，各ノードの持つ隣接ノード

Step 1 の core 検出処理では，構造的類似度計算がエッジご集合の大きさに偏りが生じる．結果として，スレッド間のタスとに独立であることに着目し，エッジ単位でのスレッド並列化

ク割当量に不均衡が生じ，並列化効率の低下を招くことになる．

を行う．更に，構造的類似度計算の内部での共通隣接ノード検

そこで本稿では，図 2 に示すように to 配列の要素と一対一

出処理は大きなボトルネックとなるため，SIMD 演算によるで対応した逆ポインタである from 配列を新たに導入する．ptr

データ並列化によりさらなる高速化を行う．Step 2 のクラスタ

配列および to 配列に加えて from 配列を持つことで，CRS 形

検出処理では，Union-Find 木と CAS (Compare And Swap)

式の持つ空間効率やキャッシュ効率を維持しつつ，エッジ単位

命令を用いた並列化可能なアルゴリズムを導入する．既存手法

でのスレッド並列化を行うことが可能となる．結果として各ス

SCAN では，core となったノードから探索的にクラスタを構成

レッドはエッジ 1 つ分の構造的類似度計算を担当することになするノードを見つける必要があったため，スレッド並列化が困る．ゆえに，前述したグラフの次数分布の偏りに関して影響を難であった．そのため Xeon Phi の各物理コアを活用し，演算受けることなく並列化が可能である．

STEP1

adjacent nodes of node v
3

4

10

3

SIMD register 1

13

3

20

4

…

end

3

3

4

13

43

3

4

4

…

3

2

2

2

3

2

3

0

1

3

tion
Input: v, w ∈ V ,Output: σ(v, w)
1: // Initialization
2: if |Γ(v)| >= 2|Γ(w)| (or 2|Γ(v)| <= |Γ(w)|) then3:
α = 1, β = 16 (or α = 16, β = 1);
4: else5:α = β = 4;
6: end if
7: get head pointers vp and wp from Γ(v) and Γ(w), respectively;
8: get tail pointers v end and w end from Γ(v) and Γ(w), respectively;

9:
10: while vp < v end && wp < w end do
11:// STEP 1 and STEP 2
12:load α and β nodes into SIMD register reg v and reg w from Γ(v) andΓ(w), respectively;
get the number of common nodes c between reg v and reg w by using
SIMD instructions;14:
vw common+ = c;
15:// STEP 3
16:
if vp+α == wp+β then17:
vp+ = α, wp+ = β;18:else if vp + α > wp + β then19:
wp+ = β;
20:
else
21:
vp+ = α;22:
end if
23: end while√
24: σ(v, w) = (vw common + 2)/ |Γ(v)||Γ(w)|;

13:

13

20

…

end

11

13

43

…

end

…

end

…

end

adjacent nodes of node v

0

0

4

10

13

20

advance pointer23

図 3: SIMD 演算による共通隣接ノード探索 (α = β = 2)

Algorithm 3 SIMD-based structural similarity computa-

10

adjacent nodes of node w

3

SIMD register 3
SIMD register 2

4

3

+1

end

3

compare (4>3)

SIMD register 2

2
11

STEP3
adjacent nodes of node v

Equalsadjacent nodes of node w
2

STEP2

SIMD register 1

11

13

43

adjacent nodes of node w

図 3 は 128 ビットの SIMD レジスタ上で α = β = 2 の場合の具体的なアルゴリズムの動作を示している．最初に Step 1 では構造的類似度を計算するノード v と w の隣接ノード配列からポインタで示された α(= 2) ， β(= 2) 個の要素をそれぞれ選択し，SIMD レジスタ 1 及び 2 上にロードする．次に Step 2にでは，SIMD レジスタ上にロードされたデータ同士の比較を

compare 命令を用いて行う．比較を行った結果，値が一致した
場合は，カウント用の SIMD レジスタ 3 の値が 1 加算される．
最後に Step 3 において，ポインタで示された要素の内，一番大きな要素同士を比較し，小さい方のポインタが α もしくは β
分だけ進められる．この処理をどちらかのポインタが配列を全て参照するまで繰り返し行われる．

3. 3 クラスタ検出処理のスレッド並列化
本節ではクラスタ検出処理の並列化について述べる．2 節で述べた SCAN のクラスタ検出処理は core からどこまでのノードがクラスタに入るのかは事前に明らかになっておらず，クラスタに含まれるノードを探索的に求める必要がある．その結果として，どのノードをどのスレッドで並列処理すれば良いのか決定できず，容易にスレッド並列化を行うことができない．

3. 2. 2 SIMD による共通ノード検出処理のデータ並列化

そこで本稿では，我々は Union-Find 木を用いた並列化アル

次に構造的類似度計算を SIMD によるデータ並列化することゴリズムを提案する．Union-Find 木は素集合に対して，集合同により高速化する．定義 2.2 で示したように，構造的類似度計

士の統合処理 (union) と要素が属する集合の特定 (find) を高速

算には隣接する 2 つのノードが持つ隣接ノード集合の積集合をに行うことが出来るデータ構造である．本稿では Union-Find

求める必要がある．この計算は，既存研究 [15] において，sort

木と CAS 命令を組み合わせることでクラスタ検出処理の効率

merge join が最も高速となることが示されている．そのため本的な並列化を行う．

研究では sort merge join による積集合計算を採用し，その処理を SIMD 演算を用いて実装する．

具体的な処理の詳細を Algorithm 2 を用いて説明する．Algo-rithm 2 の 12 行目の union(v, w) は，v の所属するクラスタとAlgorithm 3 と図 3 に SIMD による積集合計算の概要を示

w の所属するクラスタを統合する命令である．また，Algorithm

す．提案手法は，Inoue らにより提案されたブロックベースの2 の 11 行目の find(v) は v の所属するクラスタを検出する命令

積集合計算手法 [19] に基づき，ポインタで示された複数個のである．Algorithm 2 の 9 行目から 16 行目において，各スレッノードを SIMD レジスタ上にロードし，並列に比較を行うこと

ドは，core と判定されたノードをそれぞれ参照し，core とそのにより積集合計算を高速化する．

Nϵ で構成されるクラスタを検出する．このとき，各クラスタ間

ここで我々は各レジスタ上にロードされるノード数を表すパで格納されたノードに重複があった場合，それらのクラスタはラメータ α，β を導入する．積集合計算を行う配列のサイズ比

union 命令により統合する．この処理は全ての core が参照されに応じて，α，β の比率を変更することでグラフの次数の偏りるまで繰り返し実行する．また，union 命令による統合処理は，による SIMD 演算の効率の低下を抑制する．例えば，本研究でスレッド並列間の書き換えの衝突を検知できる CAS 命令を使対象とする Xeon Phi では SIMD レジスタが 512 ビットであ用して行われ，スレッド間のデータの整合性を保つようにする．

るため，32 ビットの integer で表現されたグラフを対象とする

3. 4 SCAN-XP の正確性場合，(α，
β)=(1,16)，(2,8)，(4,4) の 3 パターンが考えられる.

SCAN-XP 高速にクラスタリングを行う一方で，常に SCAN

基本的には比較する配列のサイズがほぼ同一の場合は α，β もと同じクラスタリング結果を保証する．本節では SCAN-XP の同一とし，サイズが異なるほど α，β も異なる値を選択する．

正確性について以下の定理 3.1 が成り立つことを示す．

表 3: 実験環境

定理 3.1 (SCAN-XP の正確性) SCAN-XP は常に SCANと同じクラスタリング結果を示す．
証明：SCAN-XP と SCAN は共に定義 2.5 に基づき，クラスタに属さないノードをハブと外れ値に分類する．したがっCPU
Main memory

Xeon E5 1620
16GB

Xeon Phi 3120A
6GB

Clock rate
# of Core/# of ThreadOS
SIMD

3.5 GHz
4/8
Cent OS 7
AVX2

1.10GHz
57/228Linux 3.10
IMCI

Xeon Phi 7250
MCDRAM 16GB
DDR4 96GB
1.4GHz68/272
Cent OS 7
AVX-512て，SCAN-XP が SCAN と同等のクラスタをグラフから抽出するなら，定理 3.1 は証明される．定義 2.4 により，SCAN と同じクラスタを抽出するために必要な十分条件は (1) SCAN-

XP が SCAN で検出する全ての core を検出することおよび(2) SCAN-XP がエッジで繋がった全ての core とその隣接ノードが同じクラスタに属するかどうかを判定することである．

Algorithm 2 により，SCAN-XP が上記の必要十分条件を満たすことが示される．Algorithm 2 の 3 行目から 6 行目において，SCAN-XP はグラフ G の全てのエッジ E に対して，構造的類似度計算を行う．これにより，グラフ G 中に含まれる core
ノードは全て検出される．したがって，必要十分条件 (1) は満たされる．同様に，Algorithm 2 の 3 行目から 6 行目において，SCAN-XP は全てのエッジの構造的類似度を計算する．したがって，エッジで繋がれた全ての core とその隣接ノードがDirect structure reachability であるかどうかを計算している．
□

よって，必要十分条件 (2) は満たされる．

4. 評 価 実 験とき α = 1，β = 8 とし，KNC 及び KNL では比較する配列のサイズの違いが 2 倍未満であるとき α = 4，β = 4，2 倍以上であるとき α = 1，β = 16 とするのが全体として良い傾向を示すことがわかっているため，本実験ではその値を設定する.

4. 1 実行時間の比較
CPU 上で 1 スレッドで実行した従来手法 SCAN と KNL 上
で 272 スレッドで実行した SCAN-XP の実行時間の比較を図4 に示す．SCAN-XP(KNL，272) は一貫して SCAN に対して100 倍以上の高速であることが示された．特に 1 億以上のエッ

本節では，実データに対して提案手法 SCAN-XP および既存手法 SCAN の実行時間を比較し，提案手法の有効性を検証する．実験に使用した計算機は Xeon E5-1620 (以下，CPU)，

Xeon Phi 3120A (以下，KNC)，Xeon Phi 7250 (以下，KNL)
である．KNC の MPSS は 3.7.2 を用い，KNL のメモリはフラットモードで使用した．また，コンパイラは icpc 17.0.0 を用い，最適化オプションとして-O3 を使用した．実験環境の詳
細は表 3 に示す．また，本実験において，測定に使用した 7 つの実データセットは以下の表 2 に示す．
Nodes
113489068523016328033997962
4846609
3072441115554441

Edges
2987624664947022301964
34681189
42851237
117185083
854809761

ジを持つ com-Orkut に対して，SCAN-XP (KNL，272) は 3.6秒でクラスタリングを行った．これは SCAN と比較して約 164
倍高速である．更に，8 億 5 千万エッジを持つ，webbase2001
に対して SCAN-XP はわずか約 36 秒でクラスタリングした．

4. 2 スケーラビリティの比較
SCAN-XP のスケーラビリティを評価するために，CPU，KNC，KNL 上でスレッド数を変化させて実験を行った．その結果を図 5 に示す．図から，SCAN-XP (CPU)，SCAN-

XP (KNC)，SCAN-XP (KNL) は一貫して SCAN より高速であることが示された．また，SCAN-XP (KNC) と SCAN-

表 2: データセットの詳細
Datasetcom-youtube
web-BerkStan
soc-Pokec
com-LiveJournal
soc-LiveJournal1
com-Orkut
webbase2001

図 4: 実データに対する実行時間

XP (KNL) はスレッド数の増加に対して実行速度も向上し，最Data source
SNAP [20]SNAP [20]SNAP [20]SNAP [20]SNAP [20]SNAP [20]LAW [21]

終的に一貫してそれぞれ約 50，100 倍以上 SCAN より高速となった．しかし，com-youtube 及び web-Berkstan では SCAN-

XP(CPU) と比較して，そこまでの高速化はされていない．これは，これら 2 つのグラフの大きさが小さいため Xeon Phi に搭載された多量の物理コアを十分に働かせることができなかっデータセットの内，webbase2001 は非常に大きなデータセッ
トであり，CPU 及び KNC ではメモリの容量が原因で実行が不可能であったため，KNL での実行結果のみを示す．また，たからだと考えられる．以上により，SCAN-XP は大規模なグラフに対して良いスケーラビリティを示すことがわかる．

4. 3 高速化手法の効果の検証

SCAN は逐次手法であるため CPU 上での逐次実行による測定

前述したように，SCAN-XP は core 検出処理とクラスタ検を行った．一方で，SCAN-XP は CPU，KNC，KNL 上でス

出処理に対して高速化手法を適用した．各処理に適用した高速

レッド数を変えて測定を行った．

化手法の評価を行うために，各処理の実行時間を測定した．

構造的類似度に基づくグラフクラスタリングにおけるユーザ

図 6 に，各アルゴリズムの core 検出処理の実行時間を示す．

定義の閾値 ϵ 及び µ について，SCAN と SCAN-XP はともに

図 5 と同様に SCAN-XP は com-youtube，web-Berkstan を覗

処理時間に対し影響を受けることはほぼ無かったため，本稿にいたグラフに対して，良いスケーラビリティを示している．更

おいては ϵ = 0.3，µ = 2 と定める. また，SCAN-XP におけるに SCAN-XP (KNL) は 272 スレッドでの実行時に 1 億エッジ

α，β は予備実験により，CPU ではでは比較する配列のサイズを持つ com-Orkut に対して 3.4 秒で core 検出処理を終える．

の違いが 2 倍未満であるとき α = 2，β = 4，2 倍以上である

これは従来手法 SCAN より 168 倍高速である．

10

1000
100
10
1

1

10000
1000
100
10

10000
1000
100
10

100
10

100000
10000
1000
100
10

1

100
10

100000
10000
1000
100
10

(d) com-LiveJournal

10

Faster than 1 ms
10
1

100
10
1

SCAN(CPU,1)

SCAN-XP(KNC,57)

SCAN-XP(KNL,68)

10000

SCAN-XP(CPU,1)

SCAN-XP(KNC,114)

SCAN-XP(KNL,136)

SCAN-XP(CPU,4)

SCAN-XP(KNC,171)

SCAN-XP(KNL,204)

SCAN-XP(CPU,8)

SCAN-XP(KNC,228)

SCAN-XP(KNL,272)

1000
100
10

100000
10000
1000
100
10

10000
1000
100

N/A

10

1000
100

(g) webbase2001

SCAN(CPU,1)

SCAN-XP(KNC,57)

SCAN-XP(KNL,68)

SCAN-XP(CPU,1)

SCAN-XP(KNC,114)

SCAN-XP(KNL,136)

SCAN-XP(CPU,4)

SCAN-XP(KNC,171)

SCAN-XP(KNL,204)

SCAN-XP(CPU,8)

SCAN-XP(KNC,228)

SCAN-XP(KNL,272)

10(c) soc-Pokec
Execution time (ms)

Execution time (ms)(d) com-LiveJournal

100000

1

10000

10000

1000
100
10

1000
100
10
1

1

1

(g) webbase2001

1

10000

10

N/A

10

100000(b) web-BerkStan

10000

100

100

1

10000

1000

(a) com-youtube

1000

1000

1

Execution time (ms)

100

10000

(c) soc-Pokec

10000

Execution time (ms)

Execution time (ms)100

100000(e) soc-LiveJournal1(f ) com-Orkut
図 6: コア検出処理の実行時間比較

10000

Execution time (ms)

1000

1

1

1000

SCAN-XP(KNL,272)

1

Execution time (ms)1000

SCAN-XP(KNL,204)

SCAN-XP(KNC,228)

10000(b) web-BerkStan
Execution time (ms)

Execution time (ms)(a) com-youtube

10000

SCAN-XP(KNC,171)

SCAN-XP(CPU,8)

10

1

100000

SCAN-XP(CPU,4)

100

1

Execution time (ms)1000

SCAN-XP(KNL,136)(e) soc-LiveJournal1(f ) com-Orkut
図 5: 全体の実行時間比較

Execution time (ms)

Execution time (ms)10000

SCAN-XP(KNL,68)

SCAN-XP(KNC,114)

100000100000(d) com-LiveJournal

SCAN-XP(KNC,57)

SCAN-XP(CPU,1)(c) soc-Pokec

1

1

1000001000

SCAN(CPU,1)

1

Execution time (ms)100000

10000(b) web-BerkStan
Execution time (ms)

Execution time (ms)(a) com-youtube

100000Execution time (ms)

100

10000

Execution time (ms)1000

100000(e) soc-LiveJournal1(f ) com-Orkut
図 7: クラスタ検出の実行時間比較

Execution time (ms)

10000

Execution time (ms)

Execution time (ms)

Execution time (ms)100000

1000
100

N/A

10
1

(g) webbase2001

次に図 7 にクラスタ検出処理の実行時間を示す．core 検出処

包されたクラスタ構造を捉えることが可能な構造的類似度に基理と同様に SCAN-XP (KNL) は他のアルゴリズムに対して良づく手法が考案され，幅広く利用されている. 本節では，主ないスケーラビリティを示す．対照的に，SCAN-XP (KNC) は構造的類似度に基づく手法について述べる.

SCAN-XP (CPU) より遅い．これは，Union-Find 木を用いた構造的類似度に基づく手法 [14, 15, 22–26] はグラフから高い

クラスタ検出アルゴリズムが SCAN のクラスタ検出処理と比較精度でクラスタを検出するだけでなく，ハブや外れ値といったして分岐予測ミスやキャッシュミスが起こりやすいこと，更にグラフ上で特別な役割を持つノードを検出することが可能なグ

KNC がアウトオブオーダー実行に対応していないため，そう

ラフクラスタリング手法である．

いったレイテンシの影響を受けてしまうからだと考えられる．

5. 関 連 研 究

Xu らにより提案された SCAN [11] は，最も代表的な構造的類似度に基づくグラフクラスタリング手法である. SCAN は
密度ベースのクラスタリング手法として有名な DBSCAN [12]グラフから隠されたクラスタ構造を抽出する手法は非常に重のグラフデータに対する拡張である. Xu らは SCAN は Mod-

要な技術であり，現在に至るまで様々なアルゴリズムが提案さ

ularity に基づく手法と比較してより正確なクラスタリング結

れてきている．min-max cut に基づく手法 [4,5] や Modularity

果が得られることを示している. しかし，2. 節で述べたようにに基づく手法 [9, 10] はグラフクラスタリングにおける代表的なSCAN は構造的類似度計算の計算量が原因となり，大規模グラ手法である. また，近年においては，より高精度にグラフに内フに対して計算時間が膨大となる問題がある.

SCAN の計算速度を向上させるために，最近になって幾つか[5]の手法 [13–15] が提案されている. Lim らによって提案された

LinkSCAN∗ はクラスタリングの速度を速めるためにエッジサ
ンプリング手法を取り入れ高速に近似解を求める手法である.
一方で，SCAN++ [14] と pSCAN [15] は，大規模グラフに対する高速かつ正確な構造的類似度に基づくグラフクラスタリン
グ手法である. この 2 つの手法は実世界に存在するグラフの頻

[6]

[7]
[8]

[9]

出構造に着目し，構造的類似度の計算回数を効率的に削減し，正確なクラスタリング結果を高速に求めることができる.

[10]

Zhao らによって提案された PSCAN [26] は MapReduce を利用した分散メモリ環境で SCAN を並列化した手法である.

PSCAN は，最初に map，reduce 処理により core を検出し，[11]

そして core でないノードをノイズとして排除する. 結果として，PSCAN で得られるクラスタリング結果は LinkSCAN∗ と[12]

同様の近似解である. MapReduce の特性上，中間結果をストレージに繰り返し読み書きする必要があるため，SCAN++やpSCAN より多くの計算時間を必要とする.

[13]

6. ま と め
Xeon Phi を用いて高速に構造的類似度に基づいたグラフク[14]

ラスタリングを行う SCAN-XP を提案した. SCAN-XP は従来手法である SCAN と比較し，KNC 上で一貫して 50 倍以上，

[15]

KNL 上で 100 倍以上の高速化を達成した．更に KNL 上で実行された SCAN-XP は 8 億 5 千万以上のエッジを持つグラフ[16]をたった 36 秒でクラスタリングした．
今後の課題として，512 ビット SIMD 演算を活かすことを含[17]

めた Xeon Phi への更なる最適化や，複数の Xeon Phi を用いた分散メモリ環境での並列化手法，更にメモリの限られた Xeon

[18]

Phi 上で更に大規模なグラフデータを処理する方法の検討を行う予定である．また，SCAN++や pSCAN で提案されている
計算回数削減アプローチの取り入れについて検討する．
[19]

謝

辞

本研究は，JSPS 科研費 JP26280037, JP16H07410，平成 28
年度筑波大学研究基盤支援プログラムならびに筑波大学計算科

[20]

[21]

学研究センター学際共同利用プロジェクト (COMA) の助成を受けたものである．
[22]

文
[1]

[2]

[3]

[4]

献

Junya Arai, Hiroaki Shiokawa, Takeshi Yamamuro, Makoto
Onizuka, and Sotetsu Iwamura. Rabbit Order: Just-in-Time
Parallel Reordering for Fast Graph Analysis. In Proceedingsof the IEEE International Parallel and Distributed Processing
Symposium (IPDPS), pages 22–31, 2016.
Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa,Takeshi Mishima, and Makoto Onizuka.
Eﬃcient Ad-hoc
Search for Personalized PageRank. In Proceedings of the ACM
SIGMOD International Conference on Management of Data
(SIGMOD), pages 445–456, 2013.
Pei Lee, Laks V. S. Lakshmanan, and Evangelos E. Milios. Incremental Cluster Evolution Tracking from Highly Dynamic Network Data. In Proceedings of the 30th IEEE International
Conference on Data Engineering (ICDE), pages 3–14, 2014.
Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, andHorst D. Simon. A Min-max Cut Algorithm for Graph Partitioning and Data Clustering. In Proceedings of the IEEE International Conference on Data Mining (ICDM), pages 107–114,
2001.

[23]

[24]

[25]

[26]

Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence, 22(8):888–905, August 2000.
M. E. J. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physical Review E,
69(2):026113, Feb 2004.
M. E. J. Newman. Fast Algorithm for Detecting Community
Structure in Networks. Physical Review, E 69(066133), 2004.
Aaron Clauset, M. E. J. Newman, , and Cristopher Moore. Finding Community Structure in Very Large Networks. PhysicalReview, E 70(066111), 2004.
V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E.L.J.S.
Mech. Fast Unfolding of Communities in Large Networks.
Journal of Statistical Mechanics: Theory and Experiment,
2008(10):P10008, 2008.
Hiroaki Shiokawa, Yasuhiro Fujiwara, and Makoto Onizuka.
Fast Algorithm for Modularity-based Graph Clustering. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), pages 1170–1176, 2013.
X. Xu, N. Yuruk, Z. Feng, and T. A. J. Schweiger. SCAN: A
Structural Clustering Algorithm for Networks. In Proceedings ofthe 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 824–833, New
York, NY, USA, 2007. ACM.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu.
A Density-Based Algorithm for Discovering Clusters in Large
Spatial Databases with Noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD), pages 226–231, 1996.
S. Lim, S. Ryu, S. Kwon, K. Jung, and J. G. Lee. LinkSCAN*:
Overlapping Community Detection Using the Link-space Transformation. In Proceedings of the IEEE 30th International Conference on Data Engineering (ICDE), pages 292–303, March2014.
Hiroaki Shiokawa, Yasuhiro Fujiwara, and Makoto Onizuka.
SCAN++: Eﬃcient Algorithm for Finding Clusters, Hubs andOutliers on Large-scale Graphs. Proceedings of the Very Learge
Data Bases (PVLDB), 8(11):1178–1189, August 2015.
L. Chang, W. Li, X. Lin, L. Qin, and W. Zhang. pSCAN:
Fast and Exact Structural Graph Clustering. In Proceedings ofthe IEEE 32nd International Conference on Data Engineering(ICDE), pages 253–264, May 2016.
James Jeﬀers and James Reinders. Intel Xeon Phi Coprocessor
High Performance Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2013.
James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der
Vorst. Templates for the Solution of Algebraic Eigenvalue
Problems: A Practical Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
Michalis Faloutsos, Petors Faloutsos, and Christos Faloutsos.
On Power-Law Relationships of the Internet Topology. In Proceedings of the ACM SIGCOMM 1999 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM 1999), pages 251–262, New
York, NY, USA, 1999. ACM.
Hiroshi Inoue, Moriyoshi Ohara, and Kenjiro Taura. FasterSet Intersection with SIMD instructions by Reducing Branch
Mispredictions. Proceedings of the Very Learge Data Bases(PVLDB), 8(3):293–304, August 2015.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford
Large Network Dataset Collection. http://snap.stanford.edu/
data, June 2014.
Paolo Boldi and Sebastiano Vigna. The WebGraph framework
I: Compression techniques. In Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), pages
595–601, Manhattan, USA, 2004. ACM Press.
T. R. Stovall, S. Kockara, and R. Avci. GPUSCAN: GPUBased Parallel Structural Clustering Algorithm for Networks.
IEEE Transactions on Parallel and Distributed Systems,
26(12):3381–3393, Dec 2015.
Dustin Bortner and Jiawei Han. Progressive Clustering of Networks Using Structure-Connected Order of Traversal. In Proceedings of the IEEE 26th International Conference on Data
Engineering (ICDE), pages 653–656, March 2010.
Heli Sun, Jianbin Huang, Jiawei Han, Hongbo Deng, Peixiang
Zhao, and Boqin Feng. gSkeletonClu: Density-Based Network
Clustering via Structure-Connected Tree Division or Agglomeration. In Proceedings of the 10th IEEE International Conference on Data Mining (ICDM), pages 481–490, 2010.
Nurcan Yuruk, Mutlu Mete, Xiaowei Xu, and Thomas A. J.
Schweiger. AHSCAN: Agglomerative Hierarchical Structural
Clustering Algorithm for Networks. In Proceedings of the International Conference on Advances in Social Network Analysis
and Mining (ASONAM), pages 72–77, 2009.
Weizhong Zhao, Venkata Swamy Martha, and Xiaowei Xu.
PSCAN: A Parallel Structural Clustering Algorithm for Big Networks in MapReduce. In Proceedings of the 27th IEEE International Conference on Advanced Information Networking andApplications (AINA), pages 862–869, 2013.