DEIM Forum 2019 D7-5

コミュニティ構造を考慮した属性付きグラフ汎用生成機構
前川政司†

George H. L. Fletcher††鬼塚真†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5†† Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands
E-mail: †{maekawa.seiji,onizuka}@ist.osaka-u.ac.jp, ††g.h.l.fletcher@tue.nl
あらまし

多くの実世界のグラフでは, ノードは属性を持っている. そのため, トポロジーと属性の両方を利用して, グラフからコミュニティを推定する属性付きグラフクラスタリングの需要が増してきている. それらの手法を評価するために正解データ付きのグラフデータが必要であるが, 多種多様な属性付きグラフ
データを十分に収集することは困難である. 本稿では, コミュニティ構造を考慮したスケーラブルな属性付
きグラフ汎用生成機構を提案する. 本機構では, ノード次数, コミュニティサイズ, 属性の値に対して, 様々な分布を仮定した, 汎用なグラフ生成が可能である. スケーラビリティについて実験を行い, エッジ数および属性数に関して線形時間でグラフが生成できることを示した. 生成したグラフに対して, 既存のクラスタリング手法を適用し, アルゴリズムを定量的に評価できることを示した.
キーワード 属性付きグラフ, ベンチマーク, コミュニティ
やクラスタサイズ, 属性の値に対して, 様々な分布を指定

1 はじめにグラフはノードとそれらの関係を示すための基本的なデータ構造である. 多くの領域でグラフデータは現れており, 例えばソーシャルネットワーク [5], タンパク質の結合 [4], 交通計画 [7], コンピュータビジョン [9], そして遺伝子表現 [13] などが挙げられる. グラフ処理は研究者たちの注目を集めており, 特にグラフクラスタリングは機械学習およびデータマイニングで最も広く用いられている技術の 1 つである.
実世界のグラフデータでは多くの場合, ノードが属性を持っている. 実際に, グラフデータベースは属性付きグラフにも対応している [6], [23]. そして, 属性付きグラフのためのクラスタリング手法が注目されてきている [8], [24], [1], [21].
研究者たちは自身の設計したクラスタリング手法を評価するために, 大規模かつ多様なデータセットを必要としている. 一方で属性付きグラフについては, 正解クラスタが既知でかつ, 大規模なデータの収集は非常に困難である. 実際に, グラフデータのアーカイブとして広く知られている SNAP [16] において, ノードが属性を持ち, かつコ
ミュニティ構造の正解データが与えられているデータは公開されていない. また, 現在公開されている正解データが付属した属性付きグラフ 1 の大半は小規模なものである. そのため, グラフのサイズや特性を自由に設定できる
グラフ生成機構の必要性が高い. しかし, 属性付きグラフに対応した既存のグラフ生成機構 [2], [15] は, ノード次数

することができない. 例えば [15] では, クラスタサイズに関して確率分布を指定することができず, また属性の値に関しては正規分布のみを仮定している.
本稿では, コミュニティ構造を考慮した属性付きグラフ
汎用生成機構である acMark を提案する. acMark では,
ユーザが指定する任意の分布に従ってノード次数を決定
し, そのノード次数に基づいてエッジを生成する. そのため, ノード次数分布を制御することが可能である. また,
ユーザが指定した分布をディリクレ分布の入力ベクトルとして利用するため, コミュニティサイズに関してもユー
ザが分布を選択することができる. 属性の値については,同じクラスタ内のノードは似た属性値を持ち, かつユーザ指定可能な分布に従うように生成される. 属性ごとに分布を選択できるため, 多様な属性を持つグラフを生成可能である. 計算量に関して, 生成するグラフのエッジ数に対して線形時間で処理が終了するため, acMark は大規模グ
ラフの生成が可能である. そのため, 大規模でかつ, 様々な特性を持つ属性付きグラフを生成することができる.
実験では, まず実際に生成したグラフのプロパティが設定した分布に従っているかを確認した. スケーラビリ
ティの検証のために, 様々なエッジ数, 属性数で実験を行い, いずれのパラメータに対しても線形時間でグラフを生成できることを示した. またパラメータを調整することによって, クラスタ分離度を制御することが可能である
ことも示した. 最後に生成したグラフに対して, 既存のクラスタリング手法を適用し, それぞれの手法を定量的に評価できることを示した.
本稿の構成は以下の通りである. 2 章で事前準備, 3 章

1：https://linqs.soe.ucsc.edu/

で関連研究について述べる. 4 章では, 提案手法について述べ, 5 章で実験結果を示し, それについて考察する. 6 章
で結論を述べる.

2 事前準備属 性 付 き グ ラ フ は G = (V, E, A) と 表 す こ と が でき, ノ ー ド 集 合 V = {1, 2, . . . , n}, エッジ 集 合 E =表 1: 各手法のグラフプロパティ. 表中の PL はべき乗
分布, ND は正規分布を意味している. 提案手法 acMark
は, ノード次数とコミュニティサイズに関して, 本質的には任意の分布をサポートすることができる. × は該当するプロパティについて仮定がなされていないことを意味する. ∗ が付いている手法は, クラスタリング手法の逆演
算を想定した生成機構である.

{(i, j)} ⊆ [n] × [n], およびノードを属性空間に射影

generator

node degreecommunity size

す る 関 数 A = {domA1 (v), domA2 (v), . . . , domAd (v)}

LFR

PL

PL

×

ANC

PL

×

R(ND)

PAICAN∗PL

×{0, 1}からなる. トポロジーに基づいたコミュニティ構造はC T ∈ {1, ..., k1 }n と表され, 属性に基づいたコミュニティ
構造は C A ∈ {1, ..., k2 }n と表される. 現在, 全ての既存のグラフ生成機構は C T ついてのみ考慮している.

2. 1 グラフプロパティ
次に生成したグラフが満たすべき, 実世界の属性付きグラフが持つプロパティについて述べる. 属性付きグラ

attribute

NAGC∗

×

×

{0, 1}

acMarkarbitrary

arbitrary

arbitrary

成するエッジ数だけの試行回数が必要になるため, O(m)となる. ここでの m はグラフが持つエッジ数を表す.

3. 2 ANC

フが満たすべきプロパティは, トポロジーについての構造

Largeron らによって提案された ANC [15] は, コミュニ

プロパティと属性についての属性プロパティに分けるこティ構造とノード属性の両方を持つグラフを生成する. 最とができる.

初にノードの属性を正規分布に基づいて生成し, それらの2. 1. 1 構造プロパティ

属性値からサンプリングした集合に対して k-medoids [12]

実世界のグラフは広く知られたプロパティ [20] を有しを適用し, クラスタコアを得る. そのため, 構造プロパており, 人工グラフもそれらのプロパティを持つべきであ

ティを考慮しないクラスタしか生成できない問題点がある. 例えば, ノード次数およびコミュニティサイズはそれる. 一方でノード次数に関しては, べき乗則に従うようにぞれべき乗則に従うことが多いことが知られている.

エッジが生成される.

2. 1. 2 属性プロパティ
属性の値は大きく 2 つのタイプに分けることができる.

3. 3 PAICAN

1 つ目はカテゴリー値 (e.g. 会議, 大学, 街など) であり,Bojchevski らによって提案された PAICAN [3] は, 属

2 つ目は数値 (e.g. 価格, タイムスタンプなど) である. カ

性付きグラフクラスタリング手法であり, 2 つの側面があ

テゴリー値に関しては, 1-hot vector によって, バイナリ

る. 1 つ目はベイジアンアプローチによって属性付きグラで表現することができる. 実世界の数値をとる属性のうフからクラスタを抽出することであり, 2 つ目は属性グラ

ちの多くは, べき乗則や正規分布に従うことが知られてフから部分的な異常値も含めた異常値検出を行うことでいる [18].

ある 2 . PAICAN は生成モデルでもあり, 目的関数の式から隣接行列および属性行列を構成するための計算式が3 関連研究定義されている. そのため, PAICAN の逆演算を考えた
とき, クラスタやノード次数などの必要な変数を用意す

本章では, 提案手法と関連の深い既存のグラフ生成機
構を説明する. ここでは, グラフクラスタリング手法から考えられるグラフ生成手順についても言及する. 各生成機構の特徴をまとめたものを表 1 に示す.

3. 1 LFR-benchmark
Lancichinetti らによって提案された LFR-benchmark[14] は, 人工グラフデータの生成に広く用いられている生成機構である. この生成機構はグラフ構造にのみ注目しれば, 隣接行列および属性行列を目的関数の式の計算から得ることができる可能性がある 3 . グラフを生成するときに, 隣接行列の要素全てに対して, エッジの生成確率を計算する必要があるため, PAICAN の逆演算の時間計算
量は O(n2 ) となる.

3. 4 NAGC
Maekawa らによって提案された NAGC [17] は属性付
きグラフのためのクラスタリング手法であり, グラフかており, ノード属性の生成は行わない. LFR-benchmarkの特徴はノード次数とコミュニティサイズの分布を考慮

2：我々の取り組みでは, 異常値について考慮していないので, 異常値がに入れることができる点である. 実行時間については, 各ない場合を考える.

ノードについてエッジを生成するペアを探すために, 生

3：実際には制約充足問題であり, 与えられた条件を可能な限り満たした
近似解を得ることしかできない.

らノードごとのクラスタ割合を抽出する. クラスタ割合

表 2: 変数の定義.

とは, ノードと各クラスタの関係の強さを表すものであ変数

説明る. この手法は行列分解手法に非線形関数および中間層

n×n
S ∈ R+

隣接行列の概念を導入することにより, 既存手法では捉えられな

n×d
X ∈ R+

属性行列

かった構造と属性の間の複雑な関係を考慮したクラスタ

1
U ∈ Rn×k+
d×k2
V ∈ R+
H ∈ Rk+1 ×k2
θ ∈ Rn+χ ∈ Rk+1
C ∈ Nn

リングを可能にする. この手法では, 目的関数の式においてクラスタ割合と 隣接行列および属性行列の関係が明示的に定義されている. そのため, NAGC の逆演算を考えたとき, クラスタ割合などの必要な変数を用意し, 目的関数の式に基づいて, 隣接行列と属性行列を計算すること

M ∈ N∗

が可能である. NAGC の逆演算では, 隣接行列の全ての要素に対してエッジ生成確率を計算する必要があるため,
時間計算量は O(n2 ) となる.

構造のためのクラスタプロポーション
属性のためのクラスタプロポーション
クラスタ転移行列
ノード次数リスト
コミュニティサイズリスト
クラスタ割当リスト
エッジ生成のための候補ノードリスト

表 3: グラフ生成機構の入力とそれらの説明. ϕ, δ, σ の添字の意味を以下に示す: d はノード次数, c はコミュニ

3. 5 SBM

ティサイズ, V は属性のためのクラスタプロポーション,

SBM(Stochastic Block Models) [22] はエッジの重みをH は構造と属性のクラスタ間の転移行列をそれぞれ示す.

考慮しないグラフを表すために設計されており, 隣接行

入力

説明

列の各要素 Sij はベルヌーイ分布に従うことを仮定して

n∈N

ノード数

いる. Karrar らは SBM をマルチグラフに拡張した手

m∈N

エッジ数

d∈N

属性数

k1 ∈ N構造のためのクラスタ数

k2 ∈ N

属性のためのクラスタ数

θmin , θmax ∈ N

ノード次数の最小値と最大値

α∈R

クラスタ間と内でのエッジ数の法 [10] を提案した. マルチグラフとは, 同じノード対で複数のエッジの存在できるように, 通常のグラフを拡張したものである. ここでは, Sij はそれぞれ独立で, ポアソン
分布に従う. ポアソン分布は, 距離や量などの特定の間隔の中で起きるイベントの数を表すために用いられる分布である. スパース条件下では, ポアソンモデルは元のベル割合を調整するパラメータβ∈Rめのディリクレ分布のパラメータ

ヌーイモデル [22] と類似しているが, ポアソン分布は統γ∈R

計的に解析がより容易である.

属性クラスタプロポーションのたクラスタ転移行列のための
ディリクレ分布のパラメータ

4 提案手法私たちはコミュニティ構造を考慮した属性付きグラフ
汎用生成機構, acMark を提案する. acMark は, グラフ
プロパティおよび属性プロパティに対して, 多様な分布4を指定することを可能にするだけでなく, トポロジーと属性の間に, 非線形な関係を考慮することも可能である.

ϕd , ϕ c , ϕ V , ϕ H ∈ R

べき乗分布で用いるパラメータ

δd , δ c , δ V , δ H ∈ R

一様分布の値域

σd , σc , σV , σH ∈ R

正規分布の分散fS

隣接行列を構築するための関数fX

属性行列を構築するための関数r∈N

エッジ生成ステップの反復回数

attber ∈ R

離散値をとる属性の割合

attpow ∈ R

べき乗分布に従う属性の割合

表 2 に本章で用いる変数とその定義を示す. また提案すattuni ∈ R

一様分布に従う属性の割合

るグラフ生成機構の入力を表 3 にまとめる.

attnor ∈ R

正規分布に従う属性の割合

ϕatt min , ϕatt max ∈ R

属性値のためのべき乗分布の提案手法では, まずユーザがグラフのサイズや属性数,

パラメータ

クラスタ数および各グラフプロパティが従う分布とそのパラメータを入力として与える. それらの入力に基づいδatt ∈ R

属性値のための一様分布の値域て, 構造と属性のクラスタ割合 U , V およびクラスタ転移

σatt min , σatt max ∈ R

属性値のための正規分布の分散

行列 H を生成する. 構造のクラスタ割合 U はノードと構造クラスタの関係の強さを表す行列であり, 属性のク後それらの行列を用いて, 属性付きグラフを構成する隣ラスタ割合 V は属性クラスタと属性の関係の強さを表す

接行列 S および属性行列 X, そしてクラスタ割当 C を行列である. 転移行列 H とは, 構造クラスタ U と属性出力する. 提案手法の概要図を図 1 に示す.

クラスタ V をつなぐための行列であり, 構造と属性がそ

4. 1 acMark アルゴリズム

れぞれ異なったクラスタを持つことを可能にする. その提案手法のアルゴリズムの全体像を Algorithm 1 に示
4：実際には, いくつかの分布 (べき乗分布, ユニフォーム分布, 正規分布) が実装されている.

し, Algorithm 2,3 において, エッジ生成ステップと属性

Proposed Method, acMark❖
Information of distributions# of nodes, edges and attributes
Input
❖

U

H

fS

V
fX

Onizuka Lab

a general generator for
Algorithm 2 Edge construction step
attributedgraphs with
1: # Edge construction
community structure

2: θ ← (power law(ϕd ), unif orm(δd ), normal(σd ))3: for i = 1 to n do

U, H, V are derived from4:
counter ← 0
dirichlet
distributions∑
5:
counter < r and nl Sil < θi dobased onwhile
the inputs
6:# Candidate selection

7:

M ← {}

10:

end for

図 1: 提案法の概要図. U の行は各ノードのクラスタプロ

11:

M ← unique(M )ポーションを表し, H は構造と属性のクラスタを繋ぐ配12:# Edge Generation

13:

for j ∈ M do

C

S

OutputX

S = fS(U,H,V),e.g.
Poisson(UUT)
8:
for j = 1 to θi do
T∪
X = fX(U,H,V),e.g.
9:
Mnormal(UHV← M Randint)(1, n)分を表す. また V の行は各属性のクラスタプロポーショ
ンを表す. C はクラスタ割当, S は隣接行列, X は属性

if Sij == 0 and

14:

12

∑n

l Sil < θi and∑nh Shj < θjthen

行列をそれぞれ表す. fS は S を生成するための関数を表15:Sij ← fS (U ) (e.g. P oisson(< Ui , Uj >))し, fX は X を生成するための関数を表す.

16:

Sji ← Sij

生成ステップをそれぞれ示す.

17:

end if18:

end for

19:

Algorithm 1 Graph generation steps of our method
Require: n, (m or (θmin and θmax )), d, k1 , k2 , α, β, γ,20:counter ← counter + 1
end while

21: end for(ϕd , δd or σd ), (ϕc , δc or σc ), fS , fX , r, (ϕV , δV or σV ),(ϕH , δH or σH ), attber , attpow , attuni , attnor ,ϕatt min , ϕatt max , δatt , σatt min , σatt max
Ensure: S, X, C
2: χ ← (power law(ϕc ), unif orm(δc ), normal(σc ))∑1: # Attribute generation
2: X ← fX (U , H, V ) (e.g. (power law, unif orm,

1: # Cluster assignment
3: ξ ← Dirichlet(αχ/Algorithm 3 Attribute generation step

normal)(U HV ⊤ ) for numerical values,and Bernoulli(U HV ⊤ ) for categorical values)χ)

4: for i = 1 to n do
5:Ui ← mutinomial(ξ)

目). ここでの α はクラスタ間と内のエッジの割合を調整

6:

Ci ← arg max(Uij )するパラメータであり, α が小さいとき, グラフはクラス

j

7: end for

タ内エッジを持つ割合が大きい. この多項分布はノード

8: # Edge constructionのクラスタ割合 U を表し, クラスタ割当 C は U から得

9: Edge construction() # Algorithm2
10: # Attribute generation
11: π ← (power law(ϕV ), unif orm(δV ), normal(σV ))12: ω ← Dirichlet(βπ/∑π)

Va ← multinomial(ω)

15: end for∑τ)

18: for b = 1 to k1 do
19:

ロセスはエッジの生成確率を計算する候補集合をランダムに生成する Candidate selection と, 実際にエッジの生

16: τ ← (power law(ϕH ), unif orm(δH ), normal(σH ))17: ψ ← Dirichlet(γτ /次に Algorithm 2 に示すエッジ生成ステップについて述べる. ユーザが指定した分布からノード次数が決定される. エッジはノード次数に基づいて生成され, このプ

13: for a = 1 to d do
14:

られる 5 .

Hb ← multinomial(ψ)

20: end for
21: Attribute generation() # Algorithm3

成確率を計算し, それに基づいてエッジを生成する Edge

generation に分けることができる. Candidate selection
では, 全てのノードからランダムにエッジを接続する先のノード候補の集合 M が選ばれる (7–11 行目). Edge

generation では, ノード i とノード j のエッジの生成確率を対応するクラスタ割合の内積 < Ui , Uj > で表し, そまず, ノードをクラスタに割り当てるクラスタ割当ス
テップが Algorithm 1 の 1–7 行目で行われる. コミュニ
ティサイズのリスト χ はユーザ指定可能な分布によって導出される (2 行目). その後, 各ノードについて αχ に基づいたディリクレ分布から, 多項分布が導かれる (3 行の値に対してポアソン分布を適用することによってエッジを生成する (13–17 行目). この手続きは全てのノード次数を適切に満たせない場合があるので, ノード次数の5：本研究では, 各ノードは U の対応する行の最大値を持つ列, すなわちクラスタに割り当てられる.

みの制約では反復が終わらない可能性がある. そのため,れ考える. Cluster assignment では, クラスタ割合とクラr 回のループを終了したときに, ループから抜けるように

スタ割当がノードごとに行われ, このステップは O(nk1 )設計されている (18–21 行目).

を必要とする. 次に, Edge construction は Candidate

属性クラスタ割合 V およびクラスタ転移行列 H は,selection と Edge Generation に分けられる. Candidate

ユーザが指定した分布およびクラスタの純度を調整する

selection では, ノード次数の長さを持つ候補リストが生β, γ を入力ベクトルとしたディリクレ分布によって, それ成される. そして, Edge Generation では, エッジは候補

ぞれ生成される (Algorithm 1 の 11–20 行目). そして, 属

リストの中のノードとのクラスタポーションに基づいて

性行列 X は行列 U , V , H から計算される. Algorithm 3生成される. これらの 2 つのステップが各ノードに対しての例では, H は U と V の間の転移行列であるため, X実行されるので, Edge construction は O(nk1 rθAvg ) と⊤で表現されるものを挙げているが, NAGC となる. さらに, c を定数として r = c × k1 と m = nθAvg

同様に関数 f を導入して, U と V の間に非線形な関係をであることから, 時間計算量は O(mk12 ) となる. 最後に仮定することも可能である.

Attribute generation では, V と H は各属性と各クラス

は U HV

4. 2 属 性 生 成

タ割当に対してそれぞれ生成される. 属性行列 X のための計算量は, k = min(k1 , k2 ) としたとき O(ndk) であ提案手法では, 属性の値のため複数の分布を選択する

る. それゆえ, 合計の時間計算量は O(mk12 + ndk) であことができ, 連続値と離散値の両方を属性の値に用いる

る. 通常は m ≫ k1 であることから, 計算時間はエッジことができる. 実世界では, 多くの現象がべき乗則や正規数に対して線形に決定される.

分布に従うことがよく知られている [18].

attber , attpow , attuni , attnor によって, 複数の分布に従5 実

験

う属性の数を調整することができる. 離散値をとる属性数
は d×attber で表すことができ, これらの属性に関して, X

本実験では, 4 つの目標がある. 最初の目標は, ノードの対応する列にポアソン分布を適用する. 連続値をとる属次数, コミュニティサイズおよび属性の値に対して, 異性についても同様に, attpow , attuni , attnor を用いて表さなる分布を指定したときに得られる人工データを可視化れる属性数に対応する X の列に, べき乗則, 一様分布, 正することで, 指定通りにグラフが生成されているかを確

規分布を適用する. またクラスタの情報から独立した属性

認することである. 2 つ目の目標は, 多様なエッジ数, 属を生成するために, 1 − (attber + attpow + attuni + attnor )性数, クラスタ数に対してグラフを生成し, acMark のスの割合の属性はランダムに生成される. この場合, 複

ケーラビリティを明らかにすることである. 3 つ目の目標数の分布の中からランダムに従う分布が選択される.

として, パラメータを調整することによって, クラスタのϕatt min , ϕatt max , δatt , σatt min , σatt max はランダム生

分離度を変更できることを示す. 最後に, acMark にクラ成のときの分布のパラメータである. 各属性は最小値が 0

スタリング手法を適用し, 既存のクラスタリング手法のとなり, 最大値が 1 となるように正規化される.

特性を明らかにする. また本実験では, fS および fX は

Algorithm2,3 で例に示すものを利用した.
4. 3 計 算 量
ここでは, 提案したグラフ生成機構の空間計算量と時

5. 1 多様なグラフプロパティでの可視化

間計算量の両方について議論する. グラフに関する研究

ここでは, acMark で n = 1000, m = 4000, k1 = 5 との多くの場面で, 我々が検討するのはスパースグラフ [20]

してパラメータを設定して, グラフを生成した. ノード次であり, m は n2 に比べて非常に小さいと考えることがで数に関して, べき乗則, 一様分布, 正規分布をそれぞれ適きる.

用した 3 つのグラフのノード次数のヒストグラムを図 2a ) 空間計算量に示す. これらの図からノード次数が指定した分布に従提案手法の中で, 最もサイズの大きい行列は隣接行列

うようにグラフが生成されていることがわかる. 次に, コ

S であり, そのサイズは n × n である. スパース条件下でミュニティサイズに関して, べき乗則, 一様分布, 正規分

は, 隣接行列のほとんどの要素が 0 であるため, メモリの布をそれぞれ適用した 3 つのグラフを図 3 に示す. この

ほとんどはそれらの 0 を保持するために使われる. この図から, 指定した分布に従ってコミュニティが生成されて状態を避けるために, 隣接リストを用いた他の表現方法がいることがわかる.

あり, その方法ではエッジ数だけ要素を保持すれば良い.

5. 2 スケーラビリティ

他の行列サイズは表 2 に示す通りであるため, 空間計算
量は O(m + nd) となる.

b ) 時間計算量
Algorithm 1,2,3 に示す 3 つのステップについてそれぞ

ここでは, 多様なパラメータの値に対してグラフを生成し, 実行時間とメモリ消費の変化を示す. 特に記述がなければ, 各パラメータは以下に示す値に設定す増加することがわかる. これはディリクレ分布の特徴の

0.10
0.05

0.05

count

0.00 0

count

count

0.2

20
degree(a) べき乗則に従ってノード次数を生成(ϕd = 3).

0.00

0.0
5

10 15
degree(b) 一様分布に従ってノード次数を生成.

1 つであり, α をより小さくすれば, 各クラスタが他のク
510
degreeラスタより分離する. β と γ についても同様に実験を行う. 図 7 が, これらのパラメータが属性のクラスタ分離度(c) 正規分布に従っを調整することができることを示す. β と γ が大きいとてノード次数を生成

き, クラスタがより重なり合っていることがわかる. ディ(σd = 0.1).

リクレ分布の特徴から, 0.1 などの小さな値に β を設定し

図 2: 提案手法が生成したノード次数に関して 3 つの分たとき, 各構造に関するクラスタは非常に少ない数の属

布に従うグラフのノード次数分布のヒストグラム.

性に関するクラスタとのみ関係を持つ.

5. 4 クラスタリング手法の適用
本節では, acMark が生成する人工グラフデータによって, クラスタリング手法の特性を明らかにできることを示す. まず, acMark によってグラフデータを生成し, そ(a) コミュニティサイ
ズはべき乗則に従う(ϕc = 2).

(b) コミュニティサイ
ズは一様分布に従う.

(c) コミュニティサイ

れらのデータに対して, 属性付きグラフクラスタリング

ズは正規分布に従う手法である NAGC, グラフクラスタリング手法である(σc = 0.1).

METIS [11], 属性に関するクラスタリング手法である

図 3: 提案手法が生成したコミュニティサイズに関し

k-means をそれぞれ適用し, その結果を示す. グラフ生成て 3 つの分布に従うグラフの可視化. ノードの色のはは確率分布に基づくため, 同じパラメータで 5 つのグラ

そのノードのクラスタ割当先を示す. これら実験では,

フを作成する. また, 初期値依存がある手法を用いている

n = 1000, m = 4000 としている. ノード次数はべき乗則

ため, それぞれ 5 回実行する. そのため, 合計 25 回実行に従う (ϕd = 3).

し, その平均と標準偏差を結果として示すものとする.

5. 4. 1 データセット
る: n = 10000, m = 100000, d = 100, k1 = 10, k2 =実験に用いる人工グラフの詳細を表 4 に示す. acMark1

10, α = 1/k1 , ϕ = 3, ψ = 2, σd = 0.1, σc = 0.1, r =では, 属性のうちの 9 割が正規分布に従う. acMark2 で10 ∗ k1 , attpoi = 0.0, attpow = 0.4, attuni = 0.1, attnor =は, 属性はべき乗則, 一様分布, 正規分布に 1 割ずつ従い,

0.4.

残りの 7 割はクラスタとは独立してランダムに生成され5. 2. 1 エッジ 数

る. acMark3 は属性の従う分布について, acMark2 と同エッジ数 m は {104 , 105 , 106 , 107 } の中から選ばれ, ス

じ条件を持つ一方で, α が小さいためクラスタの分離度がパース条件下を維持するために n = m/10 とする. 図 4a高いグラフである.

が示すように, 実行時間はエッジ数に関して線形に増加し5. 4. 2 クラスタリング性能ている. また図 4b に注目すると, 実際に生成されたエッここでは 4 つの指標を用いて評価する. クラスタリング

ジが m に対して小さいことがわかる. これはエッジ生成

結果と正解データとの比較のために, Normalized Mutual

アルゴリズムが, 確率分布から決定したノード次数を完Information (NMI) と ARI [25] を用いた. また構造の評

全に満たすことができないことから生じている. r をよ価にモジュラリティ [19] を用い, 属性の評価に情報エント

り大きな値に設定したとき, 実際のエッジ数は m に近づ

ロピーを用いた. モジュラリティは, クラスタ内でエッジ

く. S のサイズがエッジ数に対して, 線形に増加していくが密であり, クラスタ間でエッジが疎であれば, 値が高くことが図 4c からわかる. これらの実験から時間および空なる指標である.

間計算量の両方がエッジ数に関して線形にスケールする
ことが示された.

生成したデータにクラスタリング手法を適用した結果を表 5 に示す. まず, クラスタリング性能を示す NMI と5. 2. 2 属 性 数

ARI について議論する. acMark1 は, その属性の 9 割が属性数 d は {102 , 103 , 104 } の中から選ばれる. 図 5 に

正規分布に従うため, 属性と正解クラスタの関係が強い

おいて, 属性に関する提案手法のスケーラビリティを示

データと言える. クラスタリング結果を見ると, NAGC

す. 図 5a は, 実行時間が属性数に対して線形に増加してと k-means が良い性能を示していることから, これらのいることを示している. また図 5b において属性行列のサ手法は属性の情報をクラスタリング結果に組み込めていイズが線形に増加することを示している.

ることがわかる. 次に acMark2 では, acMark1 に比べ5. 3 クラスタ分離度て属性と正解クラスタの関係が弱くなっている. そのた

図 6 が示すように, α が小さいときクラスタ内エッジがめ, このデータの正解クラスタを抽出するには構造と属性をうまく組み合わせる必要があると言える. NAGC

1
0
0.0
0.5
1.0
m (number of edges(ideal)) [M](a) 実行時間.

0.75
0.50
0.25
0.00
0.0
0.5
1.0
m (number of edges(ideal)) [M]size of S [MB]number ofedges(actual) [M]runtime [K sec]

2

75
50
25
0
0.00 0.25 0.50 0.75
m (number of edges(ideal)) [M](b) 実際に生成されたエッジ数と m の比較.

(c) S のサイズ.

図 4: エッジ数に関するスケーラビリティの実験. その他のパラメータは以下のように設定する: n = m/10, d = 100,

k1 = 10, k2 = 10.
表 4: 生成したデータセット
ID

n

m

d

k1

k2

α

β

γ

attpow

attuni

attnoracMark1

1000

4000

10

5

5

0.2

10

1

0.0

0.0

0.9

acMark2

1000

4000

10

5

5

0.2

10

1

0.1

0.1

0.1

acMark3

1000

4000

10

5

5

0.1

10

1

0.1

0.1

0.1

表 5: クラスタリング性能. Oracle は正解データをクラスタリング結果として評価したものである. 括弧内は標準偏差を意味する.
データセット手法

acMark1

OracleacMark2

NMI

ARI

モジュラリティ

エントロピー

1.000(±0.000)

1.000(±0.000)

0.571(±0.030)−0.787(±0.045)

NAGC

Topology, Attribute

0.751(±0.000)

0.805(±0.002)

0.579(±0.000)−0.622(±0.000)

METIS

Topology

0.553(±0.043)

0.512(±0.060)

0.534(±0.033)−0.588(±0.068)

k-means

Attribute

0.620(±0.028)

0.547(±0.041)

0.348(±0.048)−0.768(±0.062)

1.000(±0.000)

1.000(±0.000)

0.495(±0.094)−0.450(±0.147)

Oracle
NAGC

Topology, Attribute

0.662(±0.008)

0.741(±0.001)

0.524(±0.002)−0.320(±0.006)

METIS

Topology

0.475(±0.080)

0.393(±0.135)

0.497(±0.046)−0.268(±0.085)

k-means

Attribute

0.321(±0.063)

0.209(±0.056)

0.167(±0.026)−0.394(±0.047)

1.000(±0.000)

1.000(±0.000)

0.653(±0.021)−0.412(±0.048)

Oracle
NAGC

Topology, Attribute

0.834(±0.014)

0.890(±0.010)

0.599(±0.005)−0.321(±0.008)

METIS

Topology

0.669(±0.044)

0.606(±0.053)

0.611(±0.030)−0.290(±0.046)

k-means

Attribute

0.406(±0.099)

0.278(±0.088)

0.182(±0.052)−0.346(±0.063)

size of X [MB]runtime [K sec]

acMark3

入力タイプ

1.0
0.5
0
5
10
d (number of attributes) [K](a) 実行時間.

750
500
250
0

0
5
10
d (number of attributes) [K](b) X のサイズ

図 5: 属性数に関しての実行時間とメモリ消費の変化. その他のパラメータは以下のように設定する:n = 10000,

m = 10000, k1 = 10, k2 = 10.
が最も良いクラスタリング精度を示していることから,(a) α = 1.0.

(b) α = 0.1

図 6: 構造に関するクラスタ分離度. これらの実験では,

n = 1000, m = 4000, k1 = 5 とし, ノードの色はそのノードのクラスタ割当先を表す.

NAGC が構造と属性の両方を考慮できていることがわかる. acMark3 では, α の変化によって, クラスタの分離度

エントロピーの評価が悪化していることがわかる. またが高まっている. そのため, いずれの手法でもクラスタリ

acMark2 と acMark3 との差異から, クラスタの分離度がング精度が acMark2 に比べ高くなっている. Oracle のモ

上がると, エントロピーが良くなっていることがわかる.

ジュラリティに注目すると, acMark3 でのスコアは他のいずれの結果もデータ生成時のパラメータから推察でき

2 つのデータより高くなっており, 構造に関してクラスタる特性と一致している. このことから, 様々なデータでクの分離度が高くなっていることがわかる. 次にエントロ

ラスタリング手法を実験することによって, それらの手法

ピーに注目すると, Oracle の acMark1 と acMark2 でのの特性を明らかにできることを示した.

結果の差異から, ランダムに生成される属性が増えると,

1.0

attribute2

attribute2

1.0
0.5

0.5
0.0

0.0

0.5
attribute1

0.0

1.0

(a) β = 100, γ = 100.

0.0

0.5
attribute1

1.0(b) β = 1, γ = 1

図 7: 属性に関するクラスタの分離度. これらの実験では, n = 1000, k1 = 5 とし, ノードの色はそのノードのク
ラスタ割当先を表す.

6 おわりにコミュニティ構造を考慮した属性付きグラフ汎用生成機構である acMark を提案した. acMark は生成するグラ
フのノード次数, コミュニティサイズ, 属性の値それぞれに任意の分布を仮定することが可能であり, 既存手法に比べ多様なグラフを生成することができる. また時間計算
量および空間計算量ともに, エッジ数と属性数に関して線形であるため, 効率的なグラフ生成を実現した. acMarkによって生成した属性付きグラフに対し, 実際にクラスタリング手法を適用することによって, それらのグラフが期待した特徴を保持して生成されることを示した.
文

献[1] Leman Akoglu, Hanghang Tong, Brendan Meeder,and Christos Faloutsos. PICS: Parameter-free identification of cohesive subgroups in large attributedgraphs. In Proceedings of SIAM SDM, 2012.
[2] Oualid Benyahia, Christine Largeron, Baptiste Jeudy,and Osmar R Zaı̈ane. Dancer: Dynamic attributed
network with community structure generator. In
ECML PKDD. Springer, 2016.
[3] Aleksandar Bojchevski and Stephan Günnemann.
Bayesian Robust Attributed Graph Clustering: Joint
Learning of Partial Anomalies and Group Structure.
In AAAI, 2018.
[4] Sylvain Brohee and Jacques Van Helden. Evaluationof clustering algorithms for protein-protein interaction networks. BMC bioinformatics, 2006.
[5] Santo Fortunato. Community detection in graphs.
Physics reports, 2010.
[6] Nadime Francis, Alastair Green, Paolo Guagliardo,
Leonid Libkin, Tobias Lindaaker, Victor Marsault,
Stefan Plantikow, Mats Rydberg, Petra Selmer, andAndrés Taylor. Cypher: An Evolving Query Language for Property Graphs. In Proceedings of SIGMOD, 2018.
[7] Betsy George, Sangho Kim, and Shashi Shekhar.
Spatio-temporal network databases and routing algorithms: A summary of results. In International Symposium on Spatial and Temporal Databases, 2007.
[8] Zhichao Huang, Yunming Ye, Xutao Li, Feng Liu,and Huajie Chen. Joint weighted nonnegative matrix
factorization for mining attributed graphs. In Proceedings of PAKDD, 2017.
[9] Ashesh Jain, Amir R Zamir, Silvio Savarese, andAshutosh Saxena. Structural-RNN: Deep learningon spatio-temporal graphs. In Proceedings of CVPR,

2016.
[10] Brian Karrer and Mark EJ Newman. Stochastic
blockmodels and community structure in networks.
Physical review E, 2011.
[11] George Karypis and Vipin Kumar. Multilevelk-way
partitioning scheme for irregular graphs. Journal of
Parallel and Distributed computing, 1998.
[12] Leonard Kaufmann and Peter Rousseeuw. Clustering by means of medoids. Data Analysis based on the
L1-Norm and Related Methods, pp. 405–416, 01 1987.
[13] Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney. Semi-supervised graph clustering: akernel approach. Machine learning, 2009.
[14] Andrea Lancichinetti, Santo Fortunato, and Filippo
Radicchi. Benchmark graphs for testing community
detection algorithms. Physical review E, 2008.
[15] Christine Largeron, Pierre-Nicolas Mougel, Reihaneh
Rabbany, and Osmar R Zaı̈ane. Generating attributed networks with communities. PloS one, 2015.
[16] Jure Leskovec and Andrej Krevl. SNAP Datasets:
Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
[17] Seiji Maekawa, Koh Takeuch, and Makoto Onizuka.
Non-linear Attributed Graph Clustering by Symmetric NMF with PU Learning. arXiv preprint
arXiv:1810.00946, 2018.
[18] Mark EJ Newman. Power laws, pareto distributions
and zipf’s law. Contemporary physics, 2005.
[19] Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academyof sciences, 2006.
[20] Mark EJ Newman. Networks: An Introduction. Oxford University Press, 2010.
[21] M. Parimala and D. Lopez.
Graph clustering
based on Structural Attribute Neighborhood Similarity (SANS). In Proceedings of IEEE ICECCT, 2015.
[22] Patrick O Perry and Patrick J Wolfe. Null models for
network data. arXiv preprint arXiv:1201.5871, 2012.
[23] Martin Sevenich, Sungpack Hong, Oskar van Rest,
Zhe Wu, Jayanta Banerjee, and Hassan Chafi. Using Domain-specific Languages for Analytic Graph
Databases. PVLDB, 2016.
[24] Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, andJames Cheng. A model-based approach to attributedgraph clustering. In SIGMOD. ACM, 2012.
[25] Ka Yee Yeung and Walter L Ruzzo. Details of theadjusted rand index and clustering algorithms, supplement to the paper an empirical study on principal component analysis for clustering gene expression
data. Bioinformatics, 2001.