DEIM Forum 2019 F5-5

隣接性と構造類似性を考慮したグラフクラスタリング
小川

裕也†

前川

政司††

竹内

孝†††

佐々木勇和††

鬼塚真††† 大阪大学 〒 565–0871 大阪府吹田市山田丘 2–1†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5††† NTT コミュニケーション科学基礎研究所 京都府相良郡精華町光台 2–4
E-mail: †{ogawa.yuya,maekawa.seiji,ogawa.yuya,onizuka}@ist.osaka-u.ac.jp, ††takeuchi.kou@lab.ntt.co.jp
あらまし

様々な分野でグラフデータが扱われており，グラフのコミュニティを発見することができるグラフクラス

タリングは重要なタスクとなっている．本研究では隣接性と構造類似性を同時に考慮した新しいグラフクラスタリン
グ手法である GCAS(Graph Clustering that leverages Adjacency and Structural similarity) を提案する．提案手法
では隣接性または構造類似性だけを考慮することでは得られない，より正確なコミュニティを得ることが可能である．
実際に実グラフデータでクラスタリング結果の正確性評価実験を行い，隣接性と構造類似性を同時に考慮することでクラスタリングの正確性が向上することを示した．
キーワード グラフクラスタリング，構造類似度，行列分解
おいて，コミュニティ間のノードは隣接していることが多いが，

1 はじめにグラフデータは人物や物事をノード，それらのつながりをエッジで表現したデータであり，社会学，生物学，コンピュータ科
学などの様々な分野で幅広く用いられている [1]．代表的なグラ
フデータとしてソーシャルグラフが挙げられる．ソーシャルグ
ラフは人と人とのつながりをグラフで表現したものであり，例
えば Twitter 1 や Facebook 2 などの SNS 上でのつながりをグラフとして表現したものである．こういったグラフデータを解析できる技術のひとつにグラフクラスタリングがある．グラフク
ラスタリングは，グラフからコミュニティを抽出する目的で利用される．そして，グラフからコミュニティを発見することで，グラフの解析や様々なアプリケーションに利用が可能となる．
そのため，グラフデータを扱う社会学，生物学やコンピュータ
科学などの分野でグラフクラスタリングは重要な技術であり，需要が高まっている．実際に，生物学の分野ではタンパク質間相互作用ネットワークをクラスタリングすることでタンパク質の解析 [2] に用いている．また Sachan ら [3] によると，コミュ
ニティを発見することでウェブマーケットやユーザーに対する効率的なウェブ広告の表示の役に立つと述べている．これらの例のように，グラフクラスタリングはグラフからコミュニティを抽出するために様々なことに活用されている．よって，より正確なコミュニティを抽出するために Modularity に基づく手法 [4–6] や min-max cut に基づく手法 [7, 8] などの様々なグラ
フクラスタリング手法が提案されてきた．
グラフクラスタリングを行う際，重要な指標となるのは，ノード間の類似度である．そして，ノード間の類似度を考えるとき，重要な性質として隣接性と構造類似性がある．隣接性は，ノード同士が隣接しているかどうかを表す．実際のグラフデータにコミュニティ外のノードとは隣接していることが少ない．つまり，隣接しているノード同士は同じコミュニティに属している可能性が高い．このことを利用して，[4–8] ではコミュニティ
内ではエッジが多く，コミュニティ間ではエッジが少なくなる
ようなコミュニティを抽出する．一方，構造類似性は，ある 2
つのノードのそれぞれの隣接しているノード集合の類似性を表す．コミュニティ内のノード同士は共通して隣接しているノードが多く，構造類似性が強い．例えば，Structural Clustering

Algorithm for Networks (SCAN) [9] や graph-Skeleton based
Clustering (gSkeletonClu) [10] ではコミュニティ内で構造類似度が高くなるようなコミュニティを抽出する．このように既存手法では，隣接性と構造類似性が重要な性質であると認識されている．しかし，実際のグラフにおいてコミュニティ間でエッジが存在したり，コミュニティ内でエッジが十分に存在しないことが多く，隣接性もしくは構造類似性だけを考慮してクラス
タリングを行うとうまくコミュニティを得ることができない問
題がある．
そこで，本研究では隣接性と構造類似性を同時に考慮する新しいグラフクラスタリング手法 GCAS(Graph Clustering thatleverages Adjacency and Structural similarity) を提案する．
提案手法では隣接性を考慮するための隣接行列と構造類似性を考慮するための構造類似度行列の 2 つの行列を元に因子行列を得てクラスタリングを行う．これにより隣接性と構造類似度性を同時に考慮することを可能としている．また，構造類似性を考慮するにあたってノード間の構造類似度 3 に Adamic/Adar
類似度を用いている．この類似度は SCAN における構造類似度とは異なり，次数が低いノードとのつながりを重視することでより的確な類似度の計算が可能となる．実際に，実グラフデー

1：http://www.twitter.com

3：本稿では構造類似度として狭義には SCAN における構造類似度を指す場合，

2：http://www.facebook.com

広義には一般的に 2 つのノードの隣接ノード集合の類似度を指す場合がある

タを用いクラスタリングの正確性評価実験を行い，主に以下ので可能となる．また，隣接行列ではなく構造類似度行列を入れ結果を確認した．

ることにより隣接性ではなく構造類似性からコミュニティを得•

隣接性と構造類似性を同時に考慮することでクラスタリ

ングの正確性が向上すること•提案手法において Adamic/Adar 類似度が SCAN における構造類似度に比べ，より適切に構造類似度を表現できる

ることも可能である．

2. 2 構造類似度
2. 2. 1 SCAN における構造類似度
Xu らによって提案された密度ベースのグラフクラスタリン

こと
本稿の構成は以下のようになっている．まず 2 章で事前準備にグ手法 SCAN [9] は，構造類似度に基づいてクラスタリングをついて述べる．ここでは本稿でのグラフの定義やクラスタリン

行う．SCAN では，2 つのノード x と y の構造類似度 σ を以下グの定義，そして提案手法で用いる既存研究について述べる．

の式 (2) のように定義している．

次に 3 章では提案手法について詳細に述べる．そして，4 章で評価実験及びその実験結果について述べる．5 章では関連研究について述べて，最後の 6 章にてまとめと今後の課題について述べる．

|Γ(x) ∩ Γ(y)|σ(x, y) = √|Γ(x)||Γ(y)|(2)

ただし，N (x) はノード x の隣接ノード集合であり，Γ(x) =N (x) ∪ {x} である．また，|Γ(x)| は集合 Γ(x) の要素数を表す．σ は 2 つのノードの共通隣接ノード集合の要素数を 2 つの2 事前準備ノードそれぞれの隣接集合の要素数で正規化したものである．

グラフは G = (V, E) として定義され，V = {v0 , v1 , ..., vN −1 }SCAN では，core と呼ばれるノードを中心に構造類似度 σ が高| j} はエッジ
はノード集合，E = {(vi , vj )|0 <= i, j <= N − 1, i =集合を表す．グラフクラスタリングはグラフ G が与えられたとき

いノード同士は同じコミュニティであると考えることで，次々グラフの構造情報からコミュニティ集合 C = {c0 , c1 , ..., cK−1 }る．また，SCAN ではコミュニティに属さないノードをハブやを見つけ出す技術である．ただし，コミュニティck はノード集

外れ値として抽出する．

合である．また，それぞれのノードはただ一つのコミュニティに属すものとする．つまり，ci ∩ cj = ∅(i =| j) である．以下提とコミュニティを拡大していき最終的なコミュニティ集合を得

2. 2. 2 Adamic/Adar 類似度
2 つのノードを x と y ，そしてそれらの隣接集合を N (x)，N (y) としたとき，x と y の構造類似度 AAsim は以下のように案手法で用いている既存技術について述べる．

表される．

2. 1 SymNMF
ここでは，提案手法のベースとなっている Kuang らによって

AAsim(x, y) =∑u∈N (x)∩N (y)提案されたグラフクラスタリング手法である SymNMF [11, 12]1
log(|N (u)|)(3)

について述べる．ノード Vi がコミュニティCk に対しどれだけ

ノード u は，ノード x とノード y の共通隣接集合 N (x) ∩ N (y)×K
属しているかを表す行列 V = {V ik } ∈ RNを考える．N+に含まれるノードであり，|N (u)| はノード u の隣接ノード集

はノードの数，K はコミュニティの数である．このとき行列合の数を表す．この Adamic/Adar 類似度は，2 つのノードのA = V V T は行列 X から期待されるノード間類似度行列であ

共通隣接ノード集合が多いほど高くなるという点において，上ると考えることができる．つまり，逆にノード間類似度行列 A

で述べた SCAN で定義された構造類似度と同じである．しかが与えられたとき A ≃ V V

Tのように行列 V で近似すること

し，Adamic/Adar 類似度では共通隣接ノードの内，次数が高でノード Vi がコミュニティCk に対しどれだけ属しているかをいノードより次数が低いノードの方により大きな重みが与えら表す行列 V を得ることが可能である．SymNMF では以下の式れる．論文引用関係を表すグラフを例に挙げると，他の論文か(1) を最適化することでノード間類似度行列 A から行列 V をらも引用が多い論文を共通して引用していても似ているか判断得る．

しにくいが，比較的他の論文からも引用が少ない論文を共通して引用していると似ていると判断しやすいことを表す．この考

min ||A − V V T ||2F
V>
=0

(1)

×N
×K
上式において A ∈ RN
，V ∈ RN，R+ は非負の実数集++

合，|| · ||F はフロベニウスノルムを表す．
最適化することで得た行列 V の各要素 V ik は，ノード Vi がえ方は自然な考え方であり, すべてのノードを同じ重みで扱うよりも現実に即した類似度であると考えられる．

3 提案手法コミュニティCk に対しどれだけ属しているかを表すと考えるこ

本稿では，隣接性と構造類似性を同時に考慮した新しいグとができる．よって，一番強く属しているコミュニティCj に属

ラフクラスタリング手法である GCAS(Graph Clustering that

するものとする．ただし，j = arg max V ik である．SymNMF

leverages Adjacency and Structural similarity) を提案する．

1<
=K
=k <

ではグラフの隣接行列 S が与えられたときこれをノード間類似度行列の一種であると考えノード間類似度行列 A の代わりに
隣接行列 S を用いることで隣接性からコミュニティを得ること

隣接性と構造類似性という 2 つの観点を組み合わせてコミュニティを得ることで，どちらか一方だけでは得ることができない
より正確なコミュニティを抽出することが可能になる．例えば，

隣接はしているが構造類似度は高くないノードや，構造類似度

3. 2 GCAS アルゴリズム

は高いが隣接はしていないノードについて，隣接性と構造類似提案手法のアルゴリズムを Algorithm 1 で示す．GCAS では性を同時に考慮することで互いに情報を補完してコミュニティ

入力を隣接行列 S と構造類似度行列 W として，コミュニティを得ることができる．また，提案手法では構造類似性を考慮す

集合 C を出力する．初めに，行列 V を初期化し (詳しい手順るにあたって，2 章で述べた理由によりノード間の構造類似度は後で述べる)，反復規則に従って行列 V を反復更新する．更として SCAN における構造類似度ではなく Adamic/Adar 類

新を終えると，SymNMF と同様に行列 V からコミュニティ集

似度を用いることで，より正確なコミュニティを抽出すること合 C を得る．また，行列 V の初期化の手順を以下に示す．なが可能である．

お，kmeans 法 [13] ではなく kmeans++法 [14] を用いたのは一提案手法では，隣接性と構造類似性を同時に考慮するために般に kmeans++法の方がクラスタリング性能が高いからである.

隣接行列 S と構造類似度行列 W の 2 つの行列を用いて以下の（ 1 ） 隣接行列を入力として k-means++法 でコミュニティ

式 (4) で表す目的関数を最適化することで，因子行列 V を得集合 C={c0 , c1 , ..., cK } を得る

る．式 (4) において第一項で SymNMF と同様に隣接性から因（ 2 ） 行列 V の要素のすべてを 0 とする

子行列 V を得て，第二項で構造類似性によって因子行列 V の（ 3 ） ノード vi がコミュニティck に属しているなら行列 V

行ベクトル vi に制約を加えて，構造類似度が高いノード同士にの要素 vik を 1 とする

対応する行ベクトルの距離を近づけている．素子て，最適化す（ 4 ） 3 の手順をすべてのノードについて行う

ることで得た行列 V の各要素 V ik は，ノード Vi がコミュニ

例えば，隣接行列を入力に k-means ++法 でクラスタリングすティCk に対しどれだけ属しているかを表すと考えることができることで図 1 のようなコミュニティ集合 C が得られたなら，まるため，一番強く属しているコミュニティCj に属するものとす

ず行列 V の要素すべてを 0 とした後，ノード v0 がコミュニる．ただし，j = arg max V ik である．以下に，提案手法におティc0 に属しているため行列 V の要素 v00 を 1 とする．そし

1<
=k <
=K

てノード v1 がコミュニティc0 に属しているため行列 V の要素

ける目的関数を示す．

min ||S − V V T ||2F + λ
V>
=0

∑

v10 を 1 とする．以下同様の操作を繰り返すと行列 V は以下のWij ||vi − vj ||2

(4)

ij

×N
×K
×N
ただし，S ∈ RN
，V ∈ RN，W ∈ RN，R+ は非負の+++実数集合，|| · ||F はフロベニウスノルム，λ >= 0 はハイパーパ
ラメータであり，隣接性と構造類似性による制約を統合する重みを表す．また，N はノードの数,K はコミュニティの数を表す．隣接行列 S は，その要素 sij がノード vi と vj にエッジがように初期化される．4



1


 1


V = 0

 0

0

0
0
1
1
0

0




0 


0 

0 

1

(9)

あれば 1 なければ 0 となる行列であり，構造類似度行列 W は，
その要素 wij が wij = AAsim(vi , vj ) となる行列である．

3. 1 更 新 規 則
ここでは，提案手法の更新規則について述べる. まず，式 (4)の目的関数を損失関数として書き換えると以下の式 (5) となる．

L = ||S − V V T ||2F + 2λT r(V T LV ) + T r(αT V )(5)

ここで，α は V >= 0 の制約のためのラグランジュ未定乗数行列∑である．また ij Wij ||vi − vj ||2 = 2T r(V T LV ) であることを∑用いた．ただし L = D − W であり，行列 D は Dii = j Wij
である対角行列である．損失関数 L を V について偏微分すると以下のようになる．

3. 3 計 算 量
この章では，提案手法の計算量について述べる．提案手法に∂L= −4SV + 4V V T V + 4λLV + α∂V(6)

L = D − W であるから

おいて行列 V の更新において N × N の行列と N × K の行列の積演算が行われる．この計算量は O(N 2 K) となる．そしてこの行列の積演算が提案手法の計算量において支配的な項となる∂L= −4SV + 4V V T V + 4λDV − 4λW V + α∂V∂L
ここで，KKT 条件を考慮すると αij Vij = 0, ∂V

図 1 コミュニティ集合 C(7)

ため，提案手法の計算量は O(N 2 Kt) となる．ここで N はノー
ドの数，K はコミュニティの数，t は学習の反復回数である．

= 0 である．

よって，以下の式 (8) の更新式を得る．

Vijnew = Vij(SV + λW V )ij(V V T V + λDV )ij(8)

4：実際には，行列の要素が 0 になると更新できなくなることがあるため，行列の各要素に ϵ ≪ 1 であるような非常に小さい数 ϵ を足している．

Algorithm 1 GCAS アルゴリズム

さ優先による探索の影響度を制御することが可能である．広義

Input: S, Wに，隣接性と構造類似性を考慮している．

Output: clustering result C

4. 1 データセット

1: Initialize V
2:set(V ) ← 0

3:

C ← k-means++(S)4:set(V ) ← C

データセットとして以下の表 1 に示すようなグラフデータを用いる．
表 1 データセット

5: Learn V

エッジ数

クラスタ数

Parliament

451

5823

7

Cora

2708

5278

7

9: Assign nodes to community

BlogCatalog

5196

171743

6

C ← max entry(V )LFR1000

1000

8261

8

6:

for counter=1 to max iteration do

7:
8:
10:

データセット名 ノード数

V

(t+1)

← update(V(t))

end do3. 4 GCAS における構造類似度提案手法では構造類似度に Adamic/Adar 類似度を用いているが，Adamic/Adar 類似度の代わりに SCAN で用いられている構造類似度などの異なる類似度を用いることで Adamic/Adar
類似度を用いる場合と違ったクラスタリング結果が得られる．
本稿では Adamic/Adar 類似度の代わりに SCAN で用いられている構造類似度を用いた GCAS を GCAS∗ と呼ぶこととする．

4 評価実験

•Parliament [17] : フランス国会の議員の関係を表したグラフである．ノードは議員を表し，エッジは議案に連署したことを表す．正解コミュニティは各政党となっている．

•

Cora 7 : 機械学習に関する論文の引用関係を表したグラフである．ノードは論文を表し，エッジは引用関係を表す．正解
コミュニティは，論文が属する以下の 7 つの機械学習のサブカテゴリになっている．Case Based, Genetic Algorithms, Neural

Networks, Probabilistic Methods, Reinforcement Learning,
Rule Learning, Theory．
•

BlogCatalog [18] : ソーシャルブログである BlogCata-

この章では提案手法のクラスタリング正確性の評価を行う．

log 上での，ユーザーの関係を表したグラフである．ノードはまた，パラメータのクラスタリング正確性への影響についてもユーザーで，エッジは BlogCatalog 上で友達関係であることを述べる．また，比較手法として以下の手法を用いた．5表す．正解コミュニティは，BlogCatalog 上で登録する際にあ•∗GCAS : Adamic/Adar 類似度が構造類似度に適しているか確認するために，提案手法において Adamic/Adar 類似
度ではなく SCAN における構造類似度を採用した手法．

•

8

らかじめ決めるカテゴリとなっている．

•

LFR1000 : LFRbenchmark [19] によって生成された人口グラフである．パラメータは [19] で使用されている値を

SymNMF : 隣接性と構造類似性を同時に考慮すること参考に用いた．値は以下の通りである．n=1000, tau1=3.0,

でクラスタリング結果の正確性が向上するか確認するために，

tau2=2.0, mu=0.5, average degree=15,min community=50.

隣接性もしくは構造類似性のうち一つだけを考慮する手法．入その他のパラメータはあらかじめ設定されている値を用いた．

力によって以下のような表記を行う．

グラフと同時に出力されるコミュニティを正解コミュニティと– SymNMF A : 入力を隣接行列とした SymNMF．隣接性のみを考慮する．

– SymNMF S : 入力を Adamic/Adar 類似度を用いた構

した．

4. 2 評 価 指 標

造類似度行列とした SymNMF．構造類似性のみを考慮する．

クラスタリング結果の正確性の評価指標として，クラスタ– SymNMF S∗ : 入力を SCAN における構造類似度を用リングの評価指標として広く用いられている Adjusted Rand

いた構造類似度行列とした SymNMF．構造類似性のみを考慮

Index (ARI) 及び Normalized Mutual Information (NMI) をする．

用いる．以下にこの 2 つの評価指標の詳細を述べる．

•

k-means++法 6 : 広く用いられているクラスタリング手•

ARI [20] : 正解コミュニティと得られたコミュニティの法．提案手法及び SymNMF における因子行列の初期化に利用一致度を測る指標であり，0 から 1 の値をとる．ARI が 1 に近している．本実験では入力を隣接行列としているため，隣接性

いほど正解コミュニティと得られたコミュニティの一致度が高のみ考慮する．

いことを示す．つまり ARI が高いほどクラスタリング結果の•node2vec [15] : ネットワークエンベディング手法．Deep-

正確性が高いことを表す．ARI は以下のように定義される．

Walk [16] の拡張手法であり，パラメータによって幅優先と深集合 X = {X1 , X2 , ..., Xr } と集合 Y = {Y1 , Y2 , ..., Ys } を考

5：SCAN ではコミュニティの数を決めることができず，コミュニティに属さな

え，集合 Xi と Yj の共通集合 Xi ∩ Yj の要素数を nij とする．
∑∑
そして ai = j nij , bj = i nij であるとすると，ARI は以

いノードも出力されるため本稿では比較を行わない．

6：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.

7：https://linqs.soe.ucsc.edu/data

KMeans.html

8：http://www.blogcatalog.com

下のように計算される．

表 3 NMI の平均値．括弧内の数字は標準偏差を表す．*は構造類似度∑ (nij )− EI
ARI = 1 ∑ (a ) ∑ (b )
，EI =
j
i
[
+
i 2
j 2 ] − EI2ij2

∑ (ai ) ∑ (bj )
i

2

(n)

j

2

2

(10)
ただし

•

(n)
k

= n Ck である．

NMI : ARI と同様正解コミュニティと得られたコミュニ

ティの一致度を測る指標であり．0 から 1 の値をとる．1 に近いほど正解コミュニティと得られたコミュニティの一致度が高に σ を利用したことを表す．また太字はそれぞれのグラフデー
タに対して最も値が高いことを表す．
手法

Parliament

GCAS

0.875(0.039) 0.400(0.018) 0.231(0.010) 0.336(0.012)

Cora

BlogCatalog

LFR1000

GCAS∗

0.845(0.028)

0.400(0.013) 0.231(0.022)

0.287(0.013)

SymNMF A

0.700(0.027)

0.345(0.018)

0.220(0.020)

0.256(0.017)

SymNMF S

0.679(0.006)

0.308(0.016)

0.012(0.001)

0.193(0.024)

SymNMF S∗

0.673(0.023)

0.354(0.026)

0.212(0.026)

0.200(0.025)

k-means++

0.512(0.027)

0.136(0.057)

0.127(0.016)

0.100(0.029)

node2vec

0.027(0.000)

0.261(0.007)

0.001(0.000)

0.016(0.003)

いことを示す．正解コミュニティ集合を C ，クラスタリングによって得られたコミュニティ集合 C ′ とすると NMI は [21] を参考にすると以下のように定義される．

表 2，3 においてすべてのグラフデータにおいて隣接性と構造∑
NMI(C, C ′ ) =p(ci ,c′j )′ci ∈C,c′ ∈C ′ p(ci , cj ) log2 p(ci )p(c′ )j4. 3. 1 クラスタリング結果の正確性評価√
H(C)H(C ′ )j

類似性を同時に考慮する提案手法 GCAS が最も良いクラスタ(11)

リング結果を示していることが確認できる．このことから，隣接性と構造類似性を同時に考慮することでクラスタリング結果

上の式において ci , c′i はそれぞれ正解コミュニティの内のひとが向上することがわかる．また GCAS が GCAS∗ と同程度以

つ，クラスタリングによって得られたコミュニティ内のひとつ

上のクラスタリング性能を示していることから，すべてのノーを表す．p(ci ) と p(c′j ) は，ランダムに選ばれたノードがそれぞ

ドを同じ重みで扱う SCAN の構造類似度よりも Adamic/Adar

れ ci ，c′j に属する確率を表す．また H(C)，H(C ′ ) はそれぞれ類似度の方が構造類似度として適していることがわかる．よっコミュニティ集合 C ，C ′ のエントロピーを表す. NMI も ARIて，本稿で用いた 3 つのグラフデータについて，次数が高いと同様に高いほどクラスタリング結果の正確性が高いことをノードよりも次数が低いノードと共通して隣接しているほうが示す．

より類似度が高いという Adamic/Adar 類似度における仮定が4. 3 実 験 設 定

正しいことがわかる．

Adamic/Adar 類似度の計算において，[22] では自然対数を4. 4 因子行列の初期化のクラスタリング結果への影響用いているが，本稿ではより次数が低いノードを重視するため提案手法において得られるコミュニティは因子行列 V の初

常用対数を用いて構造類似度の計算を行った. SymNMF の行

期値に依存する．そこで，提案手法において因子行列 V を

列 V の初期化は，提案手法と同様に行った．node2vec は，[15]k-means++によって得られるコミュニティによって初期化してを参考にして，得られたノードの表現ベクトルを入力としているが，ランダムな値で初期化した場合クラスタリング結果のk-means++によってクラスタリングを行った．node2vec のハイ

正確性がどう変化するのか確かめる．そのため k-means++法にパーパラメータは p=1, q=0.5 として他の値はあらかじめ決め

よって因子行列を初期化した場合とランダムな値で初期化したられている値を用いた 9 ．そして提案手法のハイパーパラメー

場合の提案手法のクラスタリング結果の正確性を比較する．ラタ λ は { 0.01, 0.02,..., 0.09, 0.1 , ..., 0.9} の中から各データにンダムな値で初期化した提案手法を GCASran と表すこととす

対し最適なもので実験を行った．また ARI 及び NMI の値はする．以下表 4, 5 に結果を示す．

べての手法において実験を 10 回行いその平均値をその手法で得られた結果とした．括弧内の数字は標準偏差を表す．表 2，3

表 4 ARI の平均値．括弧内の数字は標準偏差を表す．また太字はそれぞれのグラフデータに対して最も値が高いことを表す．

に結果を示す．

表 2 ARI の平均値．括弧内の数字は標準偏差を表す．*は構造類似度に σ を利用したことを表す．また太字はそれぞれのグラフデー

手法

Parliament

GCAS

0.902(0.081) 0.339(0.027) 0.140(0.012) 0.199(0.014)

GCASran

0.886(0.054)

Cora
0.313(0.031)

BlogCatalog
0.136(0.007)

LFR1000
0.194(0.025)

タに対して最も値が高いことを表す．
手法

Parliament

GCAS

0.902(0.081) 0.339(0.027) 0.140(0.012) 0.199(0.014)

Cora

BlogCatalog

LFR1000

GCAS∗

0.866(0.052)

0.322(0.022)

0.136(0.013)

0.197(0.008)

SymNMF A

0.584(0.058)

0.263(0.016)

0.132(0.023)

0.150(0.015)

SymNMF S

0.582(0.010)

0.206(0.023)

0.000(0.000)

0.139(0.016)

SymNMF S∗

0.496(0.032)

0.245(0.040)

0.123(0.030)

0.129(0.025)

k-means++0.279(0.049)

0.014(0.015)

0.021(0.004)

0.055(0.026)

node2vec

0.000(0.000)

0.223(0.004)

0.000(0.000)

0.000(0.000)

表 5 NMI の平均値．括弧内の数字は標準偏差を表す．また太字はそれぞれのグラフデータに対して最も値が高いことを表す．
手法

Parliament

GCAS

0.875(0.039) 0.400(0.018) 0.231(0.010) 0.336(0.012)

GCASran0.858(0.028)

Cora
0.387(0.016)

BlogCatalog
0.216(0.008)

LFR1000
0.328(0.020)

表 4, 5 からランダムな値で初期化するよりも k-means++によって初期化を行う方がクラスタリング結果が良いことがわか
9：https://github.com/aditya-grover/node2vec

図 2 Parliament ARI

図 3 Cora ARI

図 4 Parliament NMI

図 5 Cora NMIる．つまり，全くランダムな値から学習を進めるよりも，事前

ドの数，M は属性の数，K はコミュニティの数を表す．行列学習をしてから学習した方が良いクラスタリング結果が得ら

W は以下のように定義されている．

1 if Vi ∈ Np (Vj ) or
Wi,j =
0 otherwise

れる．

4. 5 バランスパラメータのクラスタリング正確性への影響

Vj ∈ Np (Vi )(13)

図 2 と図 3 に各グラフデータにおいてのバランスパラメータ

λ と ARI の関係を示す．また図 4 と図 5 に各グラフデータに

Np (Vi ) はノード Vi の p 近傍ノード集合である．目的関数第 1

おいてのバランスパラメータ λ と NMI の関係を示す．図 3 の項においてデータ行列から特徴を抽出する．そして，目的関数

結果からバランスパラメータ λ の値を大きくすると提案手法が第 2 項においてノード間の距離が近いと制約をかけることで，

SymNMF A よりもクラスタリング性能が悪くなることがある

因子行列の行ベクトルの距離を近づける．

ことがわかる．これはバランスパラメータ λ を大きすぎると，制約項による制約が強くなりうまくコミュニティが得ることができなくなるためであると考えられる．よって，本稿ではバランスパラメータ λ の値を大きくしすぎるとクラスタリング結果の正確性が下がる可能性を考慮して λ の値は 0.05 以下で使用することを推奨する．

5. 2 node2vec
node2vec [15] は，ネットワークエンベディング手法である．
グラフデータから，ノードの表現ベクトルを得ることを目的に使用される．単語をベクトルに変換する技術である Word2vecをグラフに応用するために，ランダムウォークを用いてサンプ
リングを行う．DeepWalk [16] の拡張手法であり，パラメータによって幅優先と深さ優先による探索の影響度を制御すること

5 関連研究が可能である．node2vec では，得られたベクトルを元にして，主にリンク予測やマルチラベリングが行われる．DeepWalk や

5. 1 GNMF
Graph regularized NMF(GNMF) [23, 24] は NMF を改良しnode2vec などのネットワークエンベディング手法におけるノーてグラフ制約を課した行列分解手法であり，その目的関数は提ドの表現ベクトルは，提案手法において因子行列の行ベクトル

案手法と関連が深い．各ノードに対する各特徴量を表現したに対応する．つまり，ノードの表現ベクトルを得るという点でデータ行列 X から，ノードのクラスタリングを行うために利は，関連が深い技術である．

用される．以下式 (12) に目的関数を示す．

min ||X − U V T ||2F + λ
V>
=0

∑

Wij ||vi − vj ||2

6 おわりに
(12)

ij

×N
×K
×K
式 (12) において X ∈ RM
，U ∈ RM，V ∈ RN，+++×N
W ∈ RN，λ はハイパーパラメータである．また N はノー+

本稿では隣接性に加え，Adamic/Adar 類似度を用いた構造類似性を考慮した新しいグラフクラスタリング手法を提案した．
提案手法では隣接性と構造類似性を同時に考慮することで一方だけでは得ることができないより正確なコミュニティを得るこ

とを可能とした．
今後の課題としては，ノードの属性を利用できるように拡張，ノードの表現ベクトルが得られることを利用してクラシフィ[17]

ケーションタスクでの応用などが挙げられる．
文

献[1] Santo Fortunato. Community detection in graphs. Physics
reports, Vol. 486, No. 3-5, pp. 75–174, 2010.
[2] Sylvain Brohee and Jacques Van Helden. Evaluation of clustering algorithms for protein-protein interaction networks.
BMC bioinformatics, Vol. 7, No. 1, p. 488, 2006.
[3] Mrinmaya Sachan, Danish Contractor, Tanveer A.
Faruquie, and L. Venkata Subramaniam. Using content
and interactions for discovering communities in social networks. In Proceedings of the 21st International Conferenceon World Wide Web, WWW ’12, pp. 331–340. ACM, 2012.
[4] Mark EJ Newman. Fast algorithm for detecting community
structure in networks. Physical review E, Vol. 69, No. 6, p.
066133, 2004.
[5] Aaron Clauset, Mark EJ Newman, and Cristopher Moore.
Finding community structure in very large networks. Physical review E, Vol. 70, No. 6, p. 066111, 2004.
[6] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities
in large networks. Journal of statistical mechanics: theory
and experiment, Vol. 2008, No. 10, p. P10008, 2008.
[7] Chris HQ Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, andHorst D Simon. A min-max cut algorithm for graph partitioning and data clustering. In Data Mining, 2001. ICDM
2001, Proceedings IEEE International Conference on, pp.
107–114. IEEE, 2001.
[8] Jianbo Shi and Jitendra Malik. Normalized cuts and image
segmentation. IEEE Transactions on pattern analysis andmachine intelligence, Vol. 22, No. 8, pp. 888–905, 2000.
[9] Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas AJ
Schweiger. Scan: a structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining,
pp. 824–833. ACM, 2007.
[10] 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 Data Mining (ICDM), 2010 IEEE 10th
International Conference on, pp. 481–490. IEEE, 2010.
[11] Da Kuang, Chris Ding, and Haesun Park. Symmetric nonnegative matrix factorization for graph clustering. In Proceedings of the 2012 SIAM international conference on data
mining, pp. 106–117. SIAM, 2012.
[12] Da Kuang, Sangwoon Yun, and Haesun Park. Symnmf:
nonnegative low-rank approximation of a similarity matrix for graph clustering. Journal of Global Optimization,
Vol. 62, No. 3, pp. 545–574, 2015.
[13] Pankaj K Agarwal and Nabil H Mustafa. K-means projective clustering. In Proceedings of the twenty-third ACM
SIGMOD-SIGACT-SIGART symposium on Principles of
database systems, pp. 155–165. ACM, 2004.
[14] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth
annual ACM-SIAM symposium on Discrete algorithms, pp.
1027–1035. Society for Industrial and Applied Mathematics,
2007.
[15] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM
SIGKDD international conference on Knowledge discovery
and data mining, pp. 855–864. ACM, 2016.
[16] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceed-

[18]

[19]

[20]
[21]

[22]
[23]

[24]

ings of the 20th ACM SIGKDD international conference on
Knowledge discovery and data mining, pp. 701–710. ACM,
2014.
Aleksandar Bojchevski and Stephan Günnemann. Bayesianrobust attributed graph clustering: Joint learning of partial anomalies and group structure. In Thirty-Second AAAI
Conference on Artificial Intelligence, 2018.
Xiao Huang, Jundong Li, and Xia Hu. Accelerated attributed network embedding. In SIAM International Conference on Data Mining, pp. 633–641, 2017.
Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection
algorithms. Physical review E, Vol. 78, No. 4, p. 046110,
2008.
Lawrence Hubert and Phipps Arabie. Comparing partitions.
Journal of classification, Vol. 2, No. 1, pp. 193–218, 1985.
Shudong Huang, Zenglin Xu, and Fei Wang. Nonnegative
matrix factorization with adaptive neighbors. In Neural
Networks (IJCNN), 2017 International Joint Conferenceon, pp. 486–493. IEEE, 2017.
Lada A Adamic and Eytan Adar. Friends and neighbors on
the web. Social networks, Vol. 25, No. 3, pp. 211–230, 2003.
Deng Cai, Xiaofei He, Xiaoyun Wu, and Jiawei Han. Nonnegative matrix factorization on manifold. In Data Mining,2008. ICDM’08. Eighth IEEE International Conference on,
pp. 63–72. IEEE, 2008.
Deng Cai, Xiaofei He, Jiawei Han, and Thomas S Huang.
Graph regularized nonnegative matrix factorization for data
representation. IEEE Transactions on Pattern Analysis
and Machine Intelligence, Vol. 33, No. 8, pp. 1548–1560,
2011.