Graph Mining with
Dirichlet Process Mixture Models

Kenichi Kurihara (Google)
joint work withKoji Tsuda (Max Plank)
第11回情報論的学習理論ワークショップ(IBIS2008)

グ

概要
枝刈り
動的な素性選択によるクラスタリング

グラフのクラスタリング
生成モデル

生成モデル

Dirichlet process mixtureによるクラスタリング

枝刈り

動的な素性選択+ Dirichlet process mixtureによるグラフのクラスタリング

2 /40 IBIS2008: ノンパラメトリックベイズ

クラスタリング3 /40 IBIS2008: ノンパラメトリックベイズ

クラスタリング4 /40 IBIS2008: ノンパラメトリックベイズ

グ

概要
枝刈り
動的な素性選択によるクラスタリング

グラフのクラスタリング
生成モデル

生成モデル

Dirichlet process mixtureによるクラスタリング

枝刈り

動的な素性選択+ Dirichlet process mixtureによるグラフのクラスタリング

5 /40 IBIS2008: ノンパラメトリックベイズ

深さ優先探索によるグラフマイニング枝刈り:

AA

B

A

AAAA

B
B

6 /40 IBIS2008: ノンパラメトリックベイズ

Aminimumsupport

グ

概要
枝刈り
動的な素性選択によるクラスタリング

グラフのクラスタリング
生成モデル

生成モデル

Dirichlet process mixtureによるクラスタリング

枝刈り

動的な素性選択+ Dirichlet process mixtureによるグラフのクラスタリング

7 /40 IBIS2008: ノンパラメトリックベイズ

クラスタリング• 二つの混合正規分布 (データの生成モデル)

8 /40 IBIS2008: ノンパラメトリックベイズ

p(k|X)→DPM

2 4 6 8 10 12 14K↓ k-means

グ

概要
枝刈り
動的な素性選択によるクラスタリング

グラフのクラスタリング

生成モデル

生成モデル

(+共役事前分布)(+共役事前分布)

Dirichlet process mixtureによるクラスタリング

枝刈り

動的な素性選択+ Dirichlet process mixtureによるグラフのクラスタリング

10/40 IBIS2008: ノンパラメトリックベイズ

グラフのクラスタリング

11/40 IBIS2008: ノンパラメトリックベイズ

グラフのクラスタリング
特徴的なパターン

クラスタリングされたグラフ

Pattern
Pattern

クラスタ1

Pattern

クラスタ2

クラスタ3
Figure 5: Obtained clusters from the RNA dataset (m = 1000). Each row corresponds to a cluster. Characteristic
patterns
shown clusters
in the leftmost
and their
are drawn
in green. to a cluster. Characteristic
Figure 5: areObtained
from thecolumn
RNA dataset(mprojections= 1000). Eachrow corresponds
patterns are shown in the leftmost column and their projections are drawn in green.
Figure 5: Obtained clusters from the RNA dataset (m = 1000). Each row corresponds to a cluster. Characteristic
patterns are shown in the leftmost column and their projections are drawn in green.

12/40 IBIS2008: ノンパラメトリックベイズ

部分グラフがFeatureAA
B

B

A

xi = (0,...,0,1,0,...,0,1,0,...)
A

A

A
B

13/40 IBIS2008: ノンパラメトリックベイズ

Aグラフの生成モデルの例
AA
B

B

A

xi = (0,...,0,1,0,...,0,1,0,...)
A

A

A
B

A

p(xi|θ) = Πj Bernoulli(xij|θj)
14/40 IBIS2008: ノンパラメトリックベイズ

部分グラフの数
AA
B

B

A

xi = (0,...,0,1,0,...,0,1,0,...)AAA

BAAABBB

15/40 IBIS2008: ノンパラメトリックベイズ

A

A

A A

A

部分グラフの数
A
B

A
A

A

AA
B

B

B

A Aグラフマイニング• Inokuchi et al. (2000)• Yan & Han (2002)+clustering
16/40 IBIS2008: ノンパラメトリックベイズ

AA

A

A

AA
B

B

B

A A

A
B

A

• Tsuda and Kudo (2006)

グラフマイニング
data
A

113

B

81

A

A

62

...
A
30 ≧ minimum support
B

17/40 IBIS2008: ノンパラメトリックベイズ

A深さ優先探索によるグラフマイニング
枝刈り:

A
A

B

A

A

A

A
A

B
B

18/40 IBIS2008: ノンパラメトリックベイズAminimumsupport

部分グラフの数
A
B

A
A

A

AA
B

B

B

A A

グラフマイニング• Inokuchi et al. (2000)• Yan & Han (2002)+clustering
19/40 IBIS2008: ノンパラメトリックベイズ

AA

AAAAB

B

B

A AA
BA

• Tsuda and Kudo (2006)

Tsuda and Kudo (2006) のモデル
AA
B

B

A

xi = (0,...,0,1,0,...,0,1,0,...)
AA

A
B

A

p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)
20/40 IBIS2008: ノンパラメトリックベイズ

Tsuda and Kudo (2006) のアルゴリズム

xi = (0,...,0,1,0,...,0,1,0,...)
p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)
グラフマイニング
AEMアルゴリズム
θcj の推定B

AAAAAB

B

B
21/40 IBIS2008: ノンパラメトリックベイズ

AA AA
B

A

深さ優先探索によるグラフマイニング
枝刈り:

AA

B

A

A

AA
A

B
B

22/40 IBIS2008: ノンパラメトリックベイズ

AL1regularization

Tsuda and Kudo (2006) のアルゴリズム

xi = (0,...,0,1,0,...,0,1,0,...)
p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)p(θcj) 〜 exp(-λ|θcj - θ0j|)
A

EMアルゴリズムθcj の推定B

AAAA
B

B

B
23/40 IBIS2008: ノンパラメトリックベイズ

AAA A

A
BA

Tsuda and Kudo (2006) のアルゴリズム

xi = (0,...,0,1,0,...,0,1,0,...)
p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)p(θcj) 〜 exp(-λ|θcj - θ0j|)y Weighted Substructure Miningr!i =(7)hoodAlgorithm 1 Pseudo-code of the EM algorithm forclustering graphs.
Set initial partition r!i randomly.
repeat
Set the weight parameter w!iCall the mining algorithm to obtain F
Estimate θ!k and θ0k only for k ∈ F (M-step)
Update the posterior r!i (E-step)
until the convergence of (21)

(8)

θcj

θ

usterto its

212λ

θ0j

0
−1

−2
com0
0.2
0.4
0.6
er allη
24/40 IBIS2008: ノンパラメトリックベイズ
this0.81Tsuda and Kudo (2006) のアルゴリズム

p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)p(θcj) 〜 exp(-λ|θcj - θ0j|)
jABA

θ1j, ..., θKj
25/40 IBIS2008: ノンパラメトリックベイズ

j’AB
A

θ0j

深さ優先探索によるグラフマイニング
枝刈り:

AA

BAA

AAA

B
B

26/40 IBIS2008: ノンパラメトリックベイズAθcj = θ0jグ概要
枝刈り
動的な素性選択によるクラスタリング

グラフのクラスタリング

生成モデル

生成モデル

(+共役事前分布)(+共役事前分布)

Dirichlet process mixtureによるクラスタリング

枝刈り

動的な素性選択+ Dirichlet process mixtureによるグラフのクラスタリング

27/40 IBIS2008: ノンパラメトリックベイズ

p(k|X)→DPM

2 4 6 8 10 12 14K↓ k-means

Tsuda and Kudo (2006) のモデル

xi = (0,...,0,1,0,...,0,1,0,...)
p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)p(θcj) 〜 exp(-λ|θcj - θ0j|)

29/40 IBIS2008: ノンパラメトリックベイズ

Tsuda and Kudo + 共役事前分布

xi = (0,...,0,1,0,...,0,1,0,...)
p(xi|θ) = Σc p(c) Πj Bernoulli(xij|θcj)p(θcj) = Beta(θcj|a,b)
事後分布p(θcj|X) = Beta(θcj|acj,bcj)
30/40 IBIS2008: ノンパラメトリックベイズ

深さ優先探索によるグラフマイニング
枝刈り:

AABAAAAABB

31/40 IBIS2008: ノンパラメトリックベイズ

AL1
regularization

Tsuda and Kudo + 共役事前分布p(xi|θ) = Σc p(c) Πj∈A Bernoulli(xij|θcj)× Πj∉A Bernoulli(xij|θ0j)p(θcj) = Beta(θcj|a,b) if j ∈ Ap(θ0j) = Beta(θ0j|a0,b0) if j ∉ A

A
変分ベイズ
32/40 IBIS2008: ノンパラメトリックベイズ

AB
A
A

AA

AA
B

B

B

A AA
B

A

Tsuda and Kudo + 共役事前分布p(xi|θ) = Σc p(c) Πj∈A Bernoulli(xij|θcj)× Πj∉A Bernoulli(xij|θ0j)p(θcj) = Beta(θcj|a,b) if j ∈ Ap(θ0j) = Beta(θ0j|a0,b0) if j ∉ AAĀjABA

θ1j, ..., θKj
33/40 IBIS2008: ノンパラメトリックベイズ

j’ABAθ0jk ∈ A. The computational complexity of updating qy interms of features is O(m) although that without feature
selection is O(d).

深さ優先探索によるグラフマイニング

3.2 Criterion for Feature Selection The feature
set A is optimized fixing qy . Ignoring the terms notdepending on A, the free energy is described as!

(3.19)

F =T!!

D[qθlk (θlk ), pθlk (θlk )]k∈A l=1

枝刈り:gamma function andAAAA(2.11)d!
sil ={xik Ψ(alk ) + (1 − xik )Ψ(blk ) − Ψ(alk + blk )}Bk=1!

Adding new variables,{θ0k}dk=1, the(θ0k), pvariational+D[qθ0k (θ0k )] distriθ0kbution becomes
k∈A
/
$# L
$n! #""(y(x(3.13) q(y, v,−q(vlv)].
)
Θ, Θ0 )E=q [logqp
yiAi ) i , yi |Θ,共役事前分布
ii=1

# d L
""

l=1

$# d
$"
l−1!
q(θsimplifies
Substituting
the optimal qθ and qvq(θ, itlk )further0k ) .
{Ψ(γj2 ) − Ψ(γj1 +γj2 )}.
+ Ψ(γl1 ) − Ψ(γl1 + γl2 ) +A+変分ベイズ(3.20)
asj=1

k=1 l=1

k=1

The free energy becomesTo minimize the free energy, qy and {qθ , qv } are alter(3.14)
nately updated.

&T %
Td !
!!
!
!
D[q(vp(v, lb)]lk+) − D[q(θlogp(θlk0k)] , b0k )F! = − F =log
B(al ), lklk ),B(a3 Feature Selection
k=1k∈A l=1
l=1k∈A/In substructure representation (Figure 1), the number ofd!
dimensionality d is intractably large. In this section, we + const,+D[q(θ0k ), p(θ0k )]propose a feature selection method to obtain a reduced
k=1
feature set A of prespecified size |A| = m. In Bayesiannwhere B is the beta
function. For the detail from (3.19)!
inference, the new variable A can be inferred either+E− Eminimizeyi |Θ,v)]. theq [log qB.
yi (yi )]q [log pA (xi , F
to (3.20), see Appendix
Tounderas a latent variable [7] or as a hyperparameter [13].
i=1constraint= m, it is sufficient to sort the features
As an example of the former approach, Kim etal. [7] We |A|
need to minimize F jointly over qv , qθ , qy and A.
accordingto thegainqv function
proposed to introduce new Bernoulli latent variables
to Amongthem,
is solved as in the previous section,indicate selected features, and the posterior distribution and qθ is analytically solved asTis inferred by Gibbs sampling. However, this approach!
'Beta(θ; a , blk )B(a(k ∈ ,A)
is not amenable to our problems, because one(3.21)
has to (3.15)
gk =qθlk (θlog
B(alk , blklk) −lklog
0k b0k ))=lk
Beta(θ;a,b)(k ∈/ A),lk
sample from the whole feature set. In the following,
l=1'
we regard A as a hyperparameter, and estimate it byBeta(θ0k ; a0k , b0k ) (k ∈/ A)(3.16) qθ0k (θ0k ) =minimizing the free energy.
Beta(θ
;a,b)(k∈A). The
in descendingorder and takethefirstmfeatures.
0k
Our algorithm incorporated with a feature selection
algorithm
describedin this section is summarized inwhere(nalk , blk are defined(asn (2.9) and (2.10) and a0k =updates q and A alternately to minimize the free energy.
a +1. i=1 xik , b0k = b + i=1 (1 − xik ).
Algorithm
We first derive q with fixed A. We also propose a feature
Plugging the solutions into F , the remaining variselection with fixed q later.
ables are qy and A, which are updated alternately. We
4 Finding
Optimal Patterns
optimize qyi (yi ) fixing A. The solution is obtained as3.1 Posteriors with Selected Features Before weq i (yi ) algorithm∝ exp(sil ) whereTo apply
to graph data, we have to findgo to the detail of feature selection, we modify
the your34/40 IBIS2008: ノンパラメトリックベイズ

AA

BB

A

アルゴリズムA• do until convergence‒ 変分ベイズ‒ グラフマイニング

AB

AA

AA
A

B
B

p(xi|θ) = Σc p(c) Πj∈A Bernoulli(xij|θcj)× Πj∉A Bernoulli(xij|θ0j)p(θcj) = Beta(θcj|a,b) if j ∈ Ap(θ0j) = Beta(θ0j|a0,b0) if j ∉ A
35/40 IBIS2008: ノンパラメトリックベイズ

A補足: MCMC の場合• 動的なグラフマイニングが困難
MCMC
MCMC

A AABAA

AA
B

B

B

36/40 IBIS2008: ノンパラメトリックベイズ

AA AABA

実験Figure 5: Obtained clusters from the RNA dataset (m = 1000). Each row corresponds to a cluster. Characteristpatterns are shown in the leftmost column and their projections are drawn in green.

• proposed : 動的な素性選択• baseline : 静的な素性選択
53

50

2.5

Proposed
Baseline!50
Free Energy

Hold!out LogLikelihood

0x 10!100!150!200

2
1.5
1!250!300!350

0.5

Proposed
Baseline
210310
Number of Features

4100

210310
Number of Features

410Figure 6: (Left) Average log-likelihood per test example in the CPDB dataset. (Right) Free energy for trainin
data. The lower is the better for the free energy.
37/40 IBIS2008: ノンパラメトリックベイズ

実験ng resultsin the RNA dataset(α =データ1). For other choices of α, refer to the supple• ラベル付きRNA

50
100 500 1000 5000
Number of Features
Proposed#clusters
677
1111purity
92.5 96.2 93.8 93.8 90.0
Frequent Mining #clusters
357912f the DFS code tree and computational time. The time is evaluated on a standarpurity
73.8 73.8 93.8 93.8 88.8
memory.

50
100500
Number of Features
TreeSizemap [10] and8317 (a)
8440
8947
True classspace byRNA
the kernel
PCA(seconds)
14.9
15.9
20.1
aussian mixture Time[8]. We
have applied
CPDB
Tree
Sizedataset. The
23569 26765 35838
ph kernels[5] to theRNA
Time(seconds)
80.4
128.4
bability of random
walking
was set59.9
tohe best performing paramater in [12].
atrix is shown in Figure 7. In the DP
38/40 IBIS2008: ノンパラメトリックベイズ

1000
9066
27.2
39731
159.7

5000
10236
(b) Graph64.355790
526.9

グ

まとめ枝刈り動的な素性選択によるクラスタリング

グラフのクラスタリング

生成モデル

生成モデル

(+共役事前分布)(+共役事前分布)

Dirichlet process mixtureによるクラスタリング

枝刈り

動的な素性選択+ Dirichlet process mixtureによるグラフのクラスタリング

39/40 IBIS2008: ノンパラメトリックベイズ