DEIM Forum 2017 I7-3

属性付きグラフのための非線形関数を用いた
接合加重非負値行列分解
前川

政司†

竹内

孝††

佐々木勇和†

鬼塚真†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5†† NTT コミュニケーション科学基礎研究所 〒 619–0237 京都府相楽郡精華町光台 2–4
E-mail: †{maekawa.seiji,sasaki,onizuka}@ist.osaka-u.ac.jp, ††takeuchi.koh@lab.ntt.co.jp
あらましソーシャルグラフの発展に伴いノード間のリンク構造とノードの属性情報の両方を含むグラフデータが出現しており, 構造と属性の 2 つの情報を同時に利用する属性付きグラフクラスタリングに注目が集まっている. 本研究では, 構造と属性の非線形な関係性を利用したグラフクラスタリング手法である NJNMF を提案する. 提案手法は, 構
造と属性を 2 つの行列として扱い, これらを非線形関数を用いてモデル化し同時分解を行うことで, 従来の線形関数のみを用いたモデルよりも複雑な関係性を利用可能とする. クラスタリング結果の評価として 3 つの実データについて実験を行い, ノードと属性の間に複雑な関係があるとき NJNMF が既存の属性付きグラフクラスタリング手法を上回ることを示した.
キーワード グラフクラスタリング, 属性, 行列分解

1. は じ め に
近年, ソーシャルネットワークや Web2.0 の発展に伴って, 構

性情報からクラスタリングに有効な属性を自動で決定し利用する技術が重要である. Joint Weighted Nonnegative Matrix

Factorization(JWNMF) [4] は, これらの問題を解決するため

造とノードの属性の両方を持ったグラフデータが多く出現してに, 構造と属性から得られる 2 つの行列に, 非負値行列分解法

いる. 例えば, ウェブページをノードと考えると, ハイパーリ(Non-negative Matrix Factorization: NMF) を用いる手法でンクによってノード間の構造関係を与えることができ, ウェブ

ある. JWNMF は構造の評価指標であるモジュラリティ[16] とページのテキストはノードに付与された属性情報として扱うこ

属性の評価指標である平均エントロピー（注 1） において従来のグとができる. これらの情報からクラスタの抽出が実現されれば,ラフクラスタリング手法や属性付きグラフクラスタリング手法

ウェブページのコミュニティの自動発見が可能になる. 現在, 広よりも, 良いクラスタリング結果を得た. しかし, JWNMF でく用いられている手法であるグラフクラスタリング [5–7] では,

は構造と属性の間に線形の関係しか仮定しておらず、より複雑

グラフ構造で密に接続するノードを同一のクラスタに, 疎に結な非線形な関係が存在している場合にそれをクラスタリングに合するノードを別々のクラスタに分類することによってグラフ利用することができない. そこで本稿では, JWNMF の非線形からコミュニティを発見する. グラフクラスタリングはウェブ拡張である, Non-Linear Joint Weighted Nonnegative Matrix

データの解析のみならず, タンパク質の解析 [6] やソーシャル

Factorization(NJNMF) を提案する. 提案手法は, 属性情報にネットワークのコミュニティ推定 [7] などのデータ解析に応用

ついて非線形問題を解くために中間層を導入するとともに活性されており, データマイニングと機械学習の分野で注目を集め化関数を利用することで, JWNMF では発見不可能な複雑でよている. しかし, 既存のグラフクラスタリングでは構造の情報

り詳細な分析を可能にする. モデルの複雑化によって生じうるのみを用いており, 属性の情報を考慮することができない. 構

過学習の問題に対応するために深層学習の最適化技術であるド造に加え属性情報を考慮することが出来れば, 構造のみでは見ロップアウトを採用する. このモデルは反復更新によって自動つからない質の高い, すなわちノード同士が密に接続する上にで最適化を行うことができる. 実験は 3 つの実データについて似た属性を持つクラスタが発見できる可能性があるため, 構造行った. 最先端の既存手法に比べ, 高いクラスタリング結果をと属性の両方を利用する属性付きクラスタリングは重要な技術得られることを示した.

となってくると言える.

本稿の構成は以下の通りである. 2 章で属性付きグラフクラ

属性付きグラフクラスタリングでは構造に加え属性を同時スタリングの既存手法について述べ, 3 章では提案手法であるに考慮するために主に以下の 2 つの問題について取り組まれ

NJNMF をついて述べる. 4 章で実験結果を示し, それについている. 1 つ目は構造と属性の関係性の効果的なモデル化であて考察し, 5 章で関連する既存技術について述べる. 6 章で結論る. 多くの既存手法はクラスタを発見するために線形関数しかを述べる.

用いていないため, 複雑な関係を考慮することができない. 2
つ目の問題は, 膨大な属性情報のすべてがグラフクラスタリン
グに効果的とは限らないことである. そのため与えられた属（注 1）：https://en.wikipedia.org/wiki/Entropy (information theory)

際に用いる潜在変数の数を表す. V はノードについての構造と

2. 事 前 準 備

属性の情報を考慮した表現である. 式 3 に JWNMF の目的関

属性付きグラフは G = (V, E, A) として定義され, ここでは

V = {v1 , v2 , . . . , vn } はノード集合, E = {(vi , vj ), 1 <= i, j <=n} はエッジ集合, A = [A1 , A2 , . . . , Am ] はノードの属性集合を表す. ここでは, 集合はレギュラーの大文字, 行列はボールド体の大文字, スカラーは小文字, 行列 X の i, j 要素は Xij とする. 属性付きグラフ G では V 中の各ノード vi が属性ベクトル(ai1 , ai2 , . . . , aim ) と関連付けられている. ここでのベクトルの各
要素は各属性での vi の属性の値である.
属性付きグラフクラスタリングと従来のグラフクラスタリン
グとの違いはノードの属性を考慮に入れる必要があるかどうかである. 理想的なクラスタリング結果として以下の 2 つのような特性が得られるべきである. (1) 同じクラスタに属するノードは密に接続し, 異なるクラスタに属するノードは疎な接続を持つ. (2) 同じクラスタに属するノードは似た属性の値を持ち,異なるクラスタに属するノードは多様な属性の値を持つ.

数を示す.

min

1

V,U ,Λ>=0 2(∥S − V V T ∥2F + λ∥AΛ − V U T ∥2F )(3)

λ > 0 は構造と属性を統合する重みである. V, U, Λ それぞれについて目的関数を偏微分し, その勾配に基づいて更新して最適化を行う. 求めた V に k-means を適用し, 最終的なクラス
タリング結果を得る. JWNMF では, 各属性の重みを自動で最適化する行列を導入することによって, 属性に含まれるノイズへの頑健性を得た. しかし, この手法では行列分解の線形性か
ら線形分離可能な属性の寄与しか考慮することができない.

JWNMF は構造については SymNMF と同様に 1 つの行列を用いてオートエンコーダで表現し, 属性ついては 2 つの行列を用いてエンコードしていると考えることができる.

2. 3 ドロップアウト
本節では, 深層学習で用いられる技術であるドロップアウ

2. 1 SymNMF
まず Kuang らによって提案されたグラフクラスタリング法
である SymNMF [2, 3] について述べる. SymNMF はグラフク
ラスタリングのための NMF に特殊な制約を科したものである.
通常の NMF はある非負の観測行列 X を近似する低ランクの因子行列 C と G を推定する技術であり, 次の最適化問題として定式化される.

ト [12] について述べる. ドロップアウトでは, ニューラルネッ
トワークの学習を行う際に, 層の中のノードを事前に決定した割合だけ無効にする. 次の更新では無効にするノードを選び直し, 学習を行う. これによって学習時のネットワークの自由度を抑え, 汎化性能を向上させることが知られている. 隠れ層において, 一般的に 50% 程度のノードを無効にすると良いと言われている. [12] によると全結合層だけでなく, 畳み込み層などに適用

min ∥X − CGT ∥2F

C,G>
=0

(1)

した場合においても同様に性能を向上させることが確かめられている. ドロップアウトが高性能を実現する理由として, アン

ここでの X ∈ Rm×n
, C ∈ Rm×k , G ∈ Rn×k
, R+ は非負の実++

サンブル学習の近似であることが挙げられる. すなわち, ドロッ

数集合, ∥ · ∥ はフロベニウスノルムを表す. 次に SymNMF の

プアウトはモデルサイズを増大させることなくアンサンブル学

目的関数を式 2 に示す.

習の近似を行い, モデルの汎化性能を向上している. 学習ごと

min ∥S − HH T ∥2F

H>=0に無効にしているノードがあることから学習速度が遅く, 同じ(2)

ここでの S ∈ Rn×n
はノード同士の類似度の情報を持った行+
列, H ∈ Rn×k
であり, 分解後の行列が 1 つであることから H+を用いてクラスタリング結果を得るので解釈が自然であり, 容易である.

SymNMF は S を低ランク行列 H に圧縮する手法として考えることでき, これは主成分分析の特殊例と言える. また主成
分分析は深層学習のオートエンコーダの 1 層で線形演算のみで構築されたものとみなすことができる.

2. 2 JWNMF
本節で, Huang らに提案された最先端の属性付きグラフクラスタリング手法である JWNMF [4] について述べる. ここでは構造の情報を持つ隣接行列を S ∈ Rn×n
, 属性の情報を持つ行+
列を A ∈ Rn×m
で表すものとする. A の行はノードを表し, 列+は属性を表している. 加えて, 各属性のための重みを割り当てる対角行列 Λ ∈ Rm×mを提案している. グラフクラスタリン+
グで高い性能を示すことで知られている SymNMF [2] を参考に, S ≈ V V

Tう. ここでの Vと AΛ ≈ V U

Tのように 2 つの行列分解を行∈ Rn×k, U ∈ Rm×k
であり, k は行列分解の++サイズの通常モデルの学習に比べて多くの反復が必要になる.

3. 提 案 手 法
本稿では, 属性付きグラフを行列分解を用いてクラスタリン
グする際に, 構造と属性の両方の情報を利用するとともに属性に関して非線形関数を導入することによってより詳細な分析を可能にした NJNMF を提案する. 前章と同様に, S を隣接行列,

A を属性行列, Λ を各属性の重み決める対角行列とする. 構造については SymNMF に影響を受け, S ≈ V V T のように分解する. 属性については従来の手法より詳細な分析を行うために中間層 Θ および活性化関数 f (·) を導入し, AΛ ≈ f (V Θ)U Tのように分解する. このモデルを 2 つの連結した 3 部グラフとして考えたときの構造を図 1 に示す.
またこれら 2 つの行列分解を統合した目的関数を式 4 に示す.
式 4 の第一項は構造に関する誤差を表し, 第二項は属性に関する誤差を表している.

min

1

V,U,Λ,Θ>=0 2(∥S−V V T ∥2F +λ∥AΛ−f (V Θ)U T ∥2F ) (4)n×n
ここでは S ∈ R+
, A ∈ Rn×m
, V ∈ Rn×k
, U ∈ Rm×h
,Θ ∈
+
+
+

∂L
= −λΛAT f (V Θ) + λU f (V Θ)T f (V Θ) + β (9)
∂U
∂L
(10)
= −λAT f (V Θ)U T + λAT AΛ + γ∂Λ∂L= −λV T ((AΛU ) ◦ (f ′ (V Θ)))∂Θ(11)
+ λV T ((f ′ (V Θ) ◦ f (V Θ))U T U ) + δ
ここでは, ◦ はアダマール積を表している. Karush-Kuhn-

Tucker (KKT) 条件から αp,r Vp,r = 0, βp,r Up,r = 0, γq,q Λq,q =∂L∂L∂L
0 および δp,r Θp,r = 0 とすると, ∂V= 0, ∂U= 0, ∂Λ=∂L0, ∂Θ
= 0 である. これらの条件に基づいて導出した更新式を式 12, 式 13, 式 14 および式 15 に示す.

V ← V ◦ (SV + S T V + λ((AΛU ) ◦ (f ′ (V Θ))ΘT ))

図 1 NJNMF のモデル図./(2V V T V + λ((f (V Θ)U T U ) ◦ (f ′ (V Θ))ΘT ))Rk×h, f (·) : R+ → R+ , R+ は非負の実数集合を表し, n はノー+∑
ド数, m は属性の種類を表す. 対角行列 Λ は m
i=1 Λi,i = 1 を満たし, λ > 0 は構造と属性を統合する重みである. k は抽出するクラスタ数を表し, h は中間層のユニット数を表す. 活性化関数 f (·) はステップ, シグモイド, ReLU, ソフトマックス, 恒等関数など多くの種類が考えられる. 線形関数を用いた場合, 同(12)U ← U ◦ (ΛAT f (V Θ))./(U f (V Θ)T f (V Θ))(13)Λ ← Λ ◦ (AT f (V Θ)U T )./(AT AΛ)(14)Θ ← Θ ◦ (V T ((AΛU ) ◦ (f ′ (V Θ)))(15)

様の振る舞いを行う 2 層のモデルが存在するので本手法では非./(V T ((f ′ (V Θ) ◦ f (V Θ))U T U )線形関数であり微分が容易であるシグモイド関数を採用する.

ここでは, ./ は要素ごとの除算を表している. Λ の重みを正規式 5 にシグモイド関数を示す.

空間へ割り当てるために, 式 16 に示すように Λ を正規化する.

f (x) =

1
1 + e−x(5)ΛΛ = ∑mi=1 Λi,i(16)

構造と属性の情報のうちどちらか一方だけの影響が強くなり過NJNMF は構造について 1 つの行列を用いてオートエンコー

ぎないようにするため式 4 の最適化を行う前に, S と A につダで表現し, ノードと属性の間を多層で表現するため深層学習

いて式 6 に示す正規化を行う.

の一種として考えることができる. このモデルの複雑さによっS = ∑nS∑ni=1

j=1 Si,j, A = ∑ni=1A∑m

j=1 Ai,jて起こりうる過学習に対応するために以下の 2 つの方法をそれ(6)

ぞれ適用する. 1 つ目は, 深層学習で用いられるドロップアウ
ト [12] と同様に中間層にあたる Θ と U の間の層のユニットを

3. 1 更 新 規 則
次に V, U, Λ および Θ の更新規則について述べる. α, β, γ

学習ごとに 0 < p <= 1 の割合だけ残して実行する方法である. 2
つ目は, Θ はノードと属性に直接接続しておらず, 学習の際の自および δ をそれぞれ V >= 0, U >= 0, Λ >= 0 および Θ >= 0 の制由度が高くなることが考えられることから, 深層学習の正規化の約のためのラグランジェの未定乗数行列とする. ラグランジェために提案されたドロップコネクト [13] のように Θ の要素のうの方程式を用いて, 式 4 で得た目的関数を損失関数として書き

ち0<q<= 1 の割合だけ更新を行う方法である. 次に上記の更換えると式 7 が得られる.

L=

新規則の収束性と計算時間について分析する. 収束性については [14] で示されている補助関数を用いて証明することができる.

1(∥S − V V T ∥2F + λ∥AΛ − f (V Θ)U T ∥2F )2

加えて目的関数の定常点を求める KKT 条件もまた更新規則の+ T r(αT V ) + T r(β T U ) + T r(γ T Λ) + T r(δ T Θ)

収束性を示している. 学習の反復回数を t とすると, NJNMF の(7)

全体の計算量は O(((n2 + nm + nh)k + (m2 + nm)h)t) である.

この損失関数を V, U, Λ, Θ それぞれについて偏微分を行い, 得た勾配を式 8, 式 9, 式 10 および式 11 に示す.

3. 2 Non-Linear Joint Weighted NMF アルゴリズム
NJNMF アルゴリズムを Algorithm1 で説明する. 1 行目で隣接行列 S と属性行列 A に前処理を行い, 2 行目で行列 V, U

∂L
= −(SV + S T V + λ((AΛU ) ◦ (f ′ (V Θ))ΘT ))∂V+ (2V V T V + λ((f (V Θ)U T U ) ◦ (f ′ (V Θ))ΘT )+ α)および Θ をランダム値, 対角行列 Λ の値を 1/m で初期化する.

3–8 行目までで行列 V, U, Λ および Θ を収束するまで繰り返し更新する. 最後に 9 行目で分解結果である V からクラスタ
リング結果を得る. V からクラスタリング結果を導出する手続(8)

きとして, ノードごとに V の対応する行で最大の値を持つクラスタに割り当てる最大エントリ法もしくは k 平均法を用いる.

をそれぞれ式 17, および式 18 に示す.

Algorithm 1 NJNMF アルゴリズム
Input: S, A

Q=

Output: clustering result Ck∑(ei,i − c2i )

(17)

i=1

1: Preprocess: S, A
2: Initialize: V , U , Λ, Θ

Avg entropy =3: while not(converge) do

m ∑
k
∑
|Cj |
t=1 j=1

nm

entropy(at , Cj )

(18)

4:

V (t+1) ← update(V (t) )5:

U (t+1) ← update(U (t) )ここでの eij はクラスタ i に含まれるノードを始点として, クラ

6:

Λ(t+1) ← update(Λ(t) )スタ j に含まれるノードを終点とするエッジの割合である. ci

7:

Θ(t+1) ← update(Θ(t) )はクラスタ i に含まれるノードに接続するエッジの終点の割合

8: end whileを示している. entropy(at , Cj ) はクラスタ Cj の中での属性 at

9: C ←max entry(V ) or kmeans(V )の情報エントロピーである. 本実験で用いるデータセットは連続地である属性を含むため, 直接情報エントロピーを適用することができない. そのため, 以下の 2 つの指標を用いた. 1 つ目

4. 評 価 実 験は微分エントロピー [17] であり, 同じクラスタに含まれたノー

この章では, まずクラスタリング結果の導出のために最大エドが持つ属性値の分散を用いて算出する. 2 つ目は値域を r 等

ントリを用いる場合と k 平均法で割り当てる場合を比較する.

分し, 離散化してから情報エントロピーを用いる. 最も簡単な

その後, ドロップアウトを適用したものを含む 3 つの提案手法

離散化である {0, 1} に置き換えた場合より連続値の情報を残すの性能実験を行い, 属性付きグラフクラスタリング手法である一例として r = 10 とした.

JWNMF と構造の情報のみに着目したモジュラリティクラスタ

4. 3 実 験 設 定

リング [15] および属性のみに着目した k 平均法と比較する.

ドロップアウトを適用したものを NJNMF-out と呼び, ドロップコネクトを適用したものを NJNMF-con と呼ぶことす

4. 1 データセット
およびる. 本実験では, ドロップアウトのパラメータである p は [12]はアマゾンの商品データのネットワークであで中間層に適用する場合に経験的に良いとされる p = 0.5 とり, Enron(注 3 を参照) はメールアドレスのネットワークであし, ドロップコネクトのパラメータである q についても [13]（注 2）

本実験では 3 つの実データを用いる. Disney（注 3）

Amazon Failる. 上記 3 つのグラフの属性はいずれも離散値と連続値の両方

で経験的に良いとされる q = 0.5 とした. 学習の反復回数を含む. 用いたデータセットの詳細な情報を表 1 に示す.

は実験的に十分収束した 100 回に固定し, モデルに初期値依存性があるため評価は異なる初期値で行なった 5 回の実

表 1 データセット
データセットノード数 エッジ数 属性数

験の平均値とした. 構造と属性を統合するための重み λ を{10−10 , 10−8 , 10−7 , 10−6 , 10−5 , 10−4 , 10−3 , 100.5 } の集合の中

Disney

124

335

25

Amazon Fail

418

3695

21

からデータごとに最適なものを実験で決定した. また NJNMF

13533

17698718で設定が必要な中間層のユニット数 h を {5, 8, 10, 15, 20} の集

Enron合の中からデータごとに最適なものを実験で決定した. k 平均

4. 2 評 価 指 標
属性付きグラフクラスタリングの目標は構造と属性の両方の情報から類似するデータを抽出することなので, 2 つの観点で結果を評価する. 構造の観点からクラスタリング結果を評価するためにモジュラリティ[16] を用いて, 属性の観点から評価するために平均エントロピー (注 1 を参照) を用いる. モジュラリ
ティはグラフ分割の基準として広く用いられている. 平均エントロピーは属性を用いたクラスタリング結果の評価に用いられる指標である. モジュラリティが高いほどクラスタ内のノード間での接続が密であり, 異なるクラスタに含まれるノード間での接続が疎であることを示している. 平均エントロピーが低いほどクラスタ内のノードが似た属性値を持ち, 異なるクラスタに含まれるノードは異なる属性値を持っている.

C = (C1 , C2 , . . . , Ck ) が属性付きグラフの k 個の分割を表すとすると, モジュラリティQ と平均エントロピー Avg entropy

法は属性行列を利用した属性 kmeans と属性ごとにその最大値が 1 になるように正規化したものを利用した kmeans-reg をそれぞれ実験した. k 平均法は本実験で用いた他の手法に比べモ
ジュラリティが非常に低かったためモジュラリティを比較した
グラフには表示しない.

4. 4 クラスタ割当方法の比較
本節では, 反復更新によって学習した V からクラスタリング
結果を得るために用いる最大エントリと k 平均法を比較する.
図 2, 3 では, JWNMF および NJNMF は最大エントリ法を用いたものであり, JWNMF-kmeans および NJNMF-kmeans は

k 平均法によってクラスタリング結果を得たものである. これらの図から最大エントリを用いた場合, k 平均法を用いた場合に比べほとんどの地点で, 高いモジュラリティと低い平均エントロピーを実現している. k 平均法を用いた場合, 次数の小さいノードが集まってクラスタを構築する可能性がある. 一方で, 最大エントリ法を用いた場合ではノードごとに最も関連の強い V（注 2）：http://www.perozzi.net/projects/focused-clustering/.

の列に属するので, 次数の小さなノードも最も関連が強いクラ（注 3）：http://www.ipd.kit.edu/˜muellere/consub/.

スタに属することになるため高い性能が得られたと考えられる.

図 2 Disney データでの最大エントリと k 平均法の比較

図 3 Amazon データでの最大エントリと k 平均法の比較

4. 5 他のクラスタリング手法との比較

ラスタの中で属性に関して 2 つ以上の密集したグループが存

前節の実験結果より, 以下の実験では最大エントリからクラ在していることが考えられる. このような複雑な条件下では,スタリング結果を得る方法を用いて, 他の手法と比較実験を行NJNMF は属性について既存手法より詳細な分析が可能になるう. Disney データに対してクラスタ数を変えながらモジュラリ

ことがわかる. 特に NJNMF-out が 10 分割エントロピーの観ティ, 微分エントロピーおよび 10 分割エントロピーの変化をプ

点では, 実験した全てのクラスタ数で良い性能を示した. これはロットしたグラフを図 4 に示す. Disney データでは, NJNMF

NJNMF-out が提案手法の中で最も良い汎化性能を持ち, ノーが既存手法の JWNMF をモジュラリティの観点で上回っている

ドと属性の間の非線形な関係をうまく捉えることができたためことがわかる. エントロピーについては, NJNMF は JWNMFであると考えられる. Enron データに対し k 平均法を適用し,と同等の性能を示し, 構造のみを考慮してクラスタリングを行

属性の正規化を行ったものと行っていないものとで比較した結う modularity-based より良いエントロピーを実現している. 属

果を図 7 に示す. 属性 kmeans と kmeans-reg の性能に差があ性 kmeans と kmeans-reg の間でエントロピーに大きな開きがることから, disney データと同様に属性間で値域に差があるこ

ある原因として, 属性間で値域に差があることが挙げられる. 属とが考えられる.

性 kmeans は大きい値をとる属性から大きな影響を受けるため,全ての属性を平等に扱う平均エントロピーが大きくなったと考えられる.

5. 関 連 研 究
近年, 属性付きグラフマイニングのためにいくつかの手法がAmazon データに対してクラスタ数を変えながらモジュラリ

提案されてきている. それらは主に距離ベース [8, 9] とモデル

ティ, 微分エントロピーおよび 10 分割エントロピーの変化をプ

ベース [10, 11] の 2 つに分類することができる. 距離ベースのロットしたグラフを図 5 に示す. modularity-based の手法がモ

手法は構造と属性の両者から定義される距離基準を考えること

ジュラリティの面で高い性能を示し, エントロピーに関してはで, k 平均法やスペクトラルクラスタリングといった既存手法

属性を考慮した NJNMF や JWNMF と同等の性能を示していを属性付きグラフクラスタリングへ拡張している. モデルベーることから, Amazon データではモジュラリティを高めるようスの手法ではクラスタリングのために結合モデルを構築するたにクラスタリングを行えば, エントロピーも良い結果が得られめにエッジとノードの属性の相互関係を活用する.

ることがわかる. また属性 kmeans と kmeans-reg はともにエ5. 1 距離ベースの手法

ントロピーの観点で良い結果が得られていることから正規化を

Zhou らが距離ベースの手法である SA-Cluster [8] を提案行う前から, 属性値に大きな偏りがないことがわかる.

し, それを効率化した Inc-Cluster [9] 提案した. これら 2 つEnron データでは NJNMF が JWNMF をモジュラリティおの手法は属性を新しいノードとして元のグラフに追加して新しよびエントロピーを実験した全てのクラスタ数で上回る性能をいグラフを構築する. そのとき, 属性の値が 0 でないノードに示した. 属性 kmeans に着目すると, 微分エントロピーでは他リンクを設ける. ランダムウォークを用いて拡張されたグラフの手法に比べて高い性能を示している一方で, 10 分割エントの距離を設計し, k-medoids によってグラフを分割する. グラ

ロピーでは他の手法に比べ低い性能を示している. この結果か

フを拡張するステップにおいてグラフのサイズを大きくするこら Enron のデータに対して k 平均法を実行したとき, 1 つのクとから, 大規模グラフで実行することは困難である.

図 4 Disney データでのクラスタリング性能

図 5 Amazon データでのクラスタリング性能

図 6 Enron データでのクラスタリング性能

図 7 Enron データでの k 平均法の比較

5. 2 モデルベースの手法
Xu らがモデルベースのアプローチである BAGC [10] を提6. お わ り に案した. この手法はクラスタが各属性の多項分布とノードの結本稿では, 非線形関数を組み込んだモデルベースの属性付き合のベルヌーイ分布を持っていると仮定することによってベイグラフクラスタリングである NJMNF を提案し, その概要につジアン確率モデルを構築する. 結果として属性付きグラフクラ

いて示した. 提案手法では, グラフの構造的な情報とノードのスタリング問題は標準的な確率推定の問題へと変形させること持つ属性を統合して行列分解を行う. 属性についての行列を 3ができる. この手法の問題点としては重み付きの属性付きグラつに分解し, 中間層に活性化関数を導入することによって既存

フを扱うことができないことが挙げられる. この問題を解決すのモデルベースの手法に比べて詳細な分析を可能にした. またるために Xu らは後に BAGC を拡張し, GBAGC [11] を提案

モデルの複雑さから生じる過学習に対応するために提案モデル

した. これらの手法では多重グラフを扱うことができないといへのドロップアウトの適用も考案した. 実データを用いて実験う欠点が挙げられる.

を行い, ノードと属性の関係が複雑な場合に NJNMF が高いク
ラスタリング性能であることを示した. 過学習を抑えるためにドロップアウトとドロップコネクトを適用して実験を行い, 深層学習で広く用いられているドロップアウトを用いたとき, 良い結果が得られることを示した.

文

献[1] Lee D.D. : Algorithms for non-negative matrix factorization. Adv. Neural Inf. Process. Syst. (2001)[2] Kuang D., Ding C., Park H.: Symmetric nonnegative matrix factorization for graph clustering. SIAM (2012)[3] Kuang D., Yun S., Park H.: SymNMF: nonnegative lowrank approximation of a similarity matrix for graph clustering. J. Glob. Optim. (2015)[4] Z. Huang, Y. Ye, X. Li, F. Liu, and H. Chen: Joint Weighted
Nonnegative Matrix Factorization for Mining Attributed
Graphs. PAKDD (2017)[5] X. Xu, N. Yuruk, Z. Feng, and T. A. J. Schweiger: Scan: astructural clustering algorithm for networks. KDD (2007)[6] S. Brohee, J. V. Helden: Evaluation of clustering algorithms for protein–protein interaction networks. BMC
Bioinf. (2006)[7] S. Fortunato: Community detection in graphs. Phys. Rep.
486(3), 75–174 (2010)[8] Zhou Y., Cheng H., Yu J.X.: Graph clustering based on
structural/attribute similarities. Proc. VLDB (2009)[9] Zhou Y., Cheng H., Yu J.X.: Clustering large attributedgraphs: an eﬃcient incremental approach. ICDM (2010)[10] Xu Z., Ke Y., Wang Y., Cheng H., Cheng J.: A model-based
approach to attributed graph clustering. SIGMOD (2012)[11] Xu Z., Ke Y., Wang Y., Cheng H., Cheng J.: GBAGC: ageneral bayesian frame- work for attributed graph clustering. TKDD (2014)[12] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, R.
Salakhutdinov: Dropout: A Simple Way to Prevent Neural
Networks from Overfitting. JMLR (2014)[13] L. Wan, M. Zeiler, S. Zhang, Y. LeCun, R. Fergus: Regularization of Neural Networks using DropConnect. ICML
(2013)[14] Lee, D.D.: Algorithms for non-negative matrix factorization. Adv. Neural Inf. Process. Syst. (2001)[15] 藤森 俊匡, 塩川 浩昭, 鬼塚 真: 効率的な分散グラフ処理のためのグラフ分割. DEIM (2017)[16] M. E. J. Newman: Modularity and community structure in
networks. Proc. Natl Acad. Sci. (2006)[17] C. M. Bishop: Pattern recognition and machine learning.
New York, NY: Springer Verlag (2006)