閾値の変化に対する高速なグラフ研磨の再計算手法

人工知能学会研究会資料
SIG-FPAI-B502-18
閾値の変化に対する高速なグラフ研磨の再計算手法
An Eﬃcient Algorithm to Recalculate Graph Polishing for the
Change of Threshold
西村翔一 1 ∗
Shoichi Nishimura1
吉仲亮 1
Ryo Yoshinaka1
山本章博 1
Akihiro Yamamoto1
1
1
京都大学大学院情報学研究科
Graduate School of Informatics Kyoto University
Abstract: Graph polishing is a preprocessing method for Micro-clustering, which is a cliqueenumeration-based clustering method. In this paper, we propose an algorithm to recalculate graph
polishing on a diﬀerent threshold parameter. In the algorithm, we holds the values of the number
of common neighbors for all vertex pairs and the sets of pairs grouped by the value to update
the polished graph. It is more eﬃcient than recalculating graph polishing without the information
of previous polishing naı̈vely because the time complexity of the algorithm is linear in the size of
added or removed edges on all polishing stages.
1
はじめに
グラフ研磨は宇野らによって提案されたマイクロク
ラスタリングにおける前処理手法である [1]．マイクロ
クラスタリングは入力データから小規模のクラスタを
抽出するためのグラフ構造に基づくクラスタリング手
法である．マイクロクラスタリングのためのアルゴリ
ズムは次の三つの処理によって構成されている．すな
わち，入力データからの類似グラフの生成，類似グラ
フに対するグラフ研磨の適用，研磨されたグラフから
の極大クリークの列挙である．
グラフ研磨は極大クリークの列挙のための前処理手
法として重要な役割を果たしている．一般にクリーク
列挙に基づくクラスタリングは，列挙するクリークの
個数がグラフによって膨大になってしまうことがある
ため，困難なタスクとされている．すべての極大クリー
クを列挙する効率的なアルゴリズムはいくつか提案さ
れてきたが [2, 3]，それにもかかわらず，現実のグラ
フに対してはしばしば列挙が困難になる場合があった．
グラフ研磨はそのような困難を解決するために提案さ
れている．
グラフ研磨の手法はグラフの局所的グループや構造
を明確にするように，元のグラフを変形する．その変
形は「二つの頂点が一定以上のサイズの密な部分グラ
フに含まれているならば，それらの共通の隣接頂点の
個数は大きい」という仮定に基づいて行われる．具体
∗ 連絡先：京都大学大学院情報学研究科知能情報学専攻山本・Cuturi
研究室
〒 606-8501 京都市左京区吉田本町 36-1
E-mail:[email protected]
的な変形の処理は，次の二つである．一つは，与えら
れた閾値以上の個数の共通隣接頂点を持つ任意の頂点
ペアに対して，それらの間に辺がなければ辺を追加す
るという処理である．もう一つは，与えられた閾値未
満の個数しか共通隣接頂点を持たない任意の頂点ペア
に対して，それらの間に辺があればそれを削除すると
いう処理である．グラフ研磨は，これらの処理を繰り
返しグラフに適用していく．
マイクロクラスタリングにおいて，グラフ研磨は研
磨グラフのクリーク列挙よりもしばしば多くの時間を
必要とすることが経験的に知られている．これは，グ
ラフ研磨によってクリークの個数が削減されることで，
クリーク列挙に必要な時間は十分少なくなるためであ
る．また，グラフ研磨を行う際，通常は理想的な閾値
が不明なため，複数のパラメータの結果を比較するた
めに複数回グラフ研磨を行う必要がある．これらの理
由から，複数のパラメータのグラフ研磨を効率的に行
うアルゴリズムは，マイクロクラスタリングの計算時
間を削減するために有効であると考えられる．
本論文では，ある閾値パラメータのグラフ研磨の結
果をもとに，新しい閾値のグラフ研磨の結果を効率的
に計算するアルゴリズムを提案する．このアルゴリズ
ムでは，グラフ研磨の結果得られるグラフのほかに，任
意の頂点ペアに対する共通隣接頂点数と，共通隣接頂
点数ごとに分割された頂点ペアの集合を持つことで，効
率的な更新を行う．このアルゴリズムは，研磨結果の
グラフの増減する辺の個数に比例した計算量となるた
め，単純にグラフ研磨を繰り返す手法よりも効率的で
あると考えられる．
− 69 −
本論文は以下のように構成されている．まず第 2 節
で本研究の背景について説明を行う．次に第 3 節で提
案手法について説明を行い，計算量や正当性について
解析を行う．さらに第 4 節では提案手法の有効性を確
認するために幾つかの実験を行い，その結果について
検討する．最後に第 5 節で本論文のまとめを行い，今
後の課題について検討する．
背景
2
2.1
グラフ
2
グラフとは E ⊂ [V ] を満たす二つの集合のペア
G = (V, E) である．V の要素をグラフ G の頂点とい
い，E の要素を辺という．
二つの頂点 u, v について (u, v) ∈ E のとき u と v
は隣接しているという．N (v) を v に隣接している頂
点の集合とし，また N [v] を N (v) ∪ {v} とする．頂
点 w が二つの頂点 u と v とともに隣接しているとき，
w は u と v の共通隣接頂点とよぶ．頂点 v の次数を
v に隣接している頂点の個数 |N (v)| とし，また ∆ を
すべての頂点に関する次数の最大値とする．
頂点集合 C ⊂ V について，C の任意の二頂点が隣
接しているとき，C はクリークであるという．また，C
がクリークであり，C を除く任意のクリークが C を包
含しないとき，C は極大クリークであるという．
2.2
マイクロクラスタリング
マイクロクラスタリングは入力データから小規模の
クラスタを抽出するためのグラフアルゴリズムに基づ
くクラスタリングである．マイクロクラスタリングの
アルゴリズムは以下の 3 つの処理で構成されている．
1. 類似グラフの構築
辺集合は {(u, v) | sim(u, v) ≥ θs } である．類似グラ
フを構築する際は，すべてのオブジェクトのペアに対
して類似度尺度に基づいて類似度を計算し，θs を上回
るときに辺を貼るという処理を行う．
2.2.2
グラフ研磨
Algorithm 1 Graph polishing
1: for i = 0 to τ do
2:
G′ ← (V, ∅)
3:
for u ∈ V do
4:
intersection[u] ← 0
5:
end for
6:
for u ∈ V do
7:
L←∅
8:
for w ∈ N [u] do
9:
for v ∈ N [v] such that v < u do
10:
if intersection[v] = 0 then
11:
L ← L ∪ {v}
12:
intersection[v] ← intersection[v]+1
13:
end if
14:
end for
15:
end for
16:
for v ∈ L do
17:
if intersection[v] ≥ θ then
18:
insert (u, v) into G′
19:
end if
20:
intersection[v] ← 0
21:
end for
22:
end for
23:
if G′ = G then
24:
break
25:
end if
26:
G ← G′
27: end for
2. 類似グラフに対するグラフ研磨の適用
3. 極大クリークの列挙
本節ではマイクロクラスタリングのアルゴリズムの各
処理について詳しく説明する．
次に，構築された類似グラフに対してグラフ研磨を適
用する．グラフ研磨では，グラフ Gi = (V, Ei ) から閾
値 θp に対して以下の定義に基づいて Gi+1 = (V, Ei+1 )
に変形するということを繰り返す．
Ei+1 = {(u, v) | |Ni [u] ∩ Ni [v]| ≥ θp }
2.2.1
類似グラフの構築
まず，マイクロクラスタリングでは，入力データから
類似グラフを構築する．類似グラフとはデータ内の各
オブジェクトの類似関係を表現するグラフである．類
似グラフは類似度尺度 sim と辺を張るための類似度
の閾値 θs を用いて定義される．類似グラフの頂点集合
は，入力データに含まれるオブジェクトの集合であり，
変形の処理は入力グラフ G0 = G から繰り返し，繰
り返し回数が τ に到達するかグラフの変形が収束した
ときに処理を停止する．この処理によって最終的に得
られたグラフを研磨グラフとよぶ．
Algorithm 1 はグラフ研磨を効率的に計算するアル
ゴリズムである．このアルゴリズムでは，二つの頂点
− 70 −
の共通隣接頂点の個数の計算を，収束するか繰り返し
回数が τ に到達するまで繰り返し行う．
この手法は入力グラフのクラスタ構造を変化させる
ことなくクリークの個数を削減するために提案された
手法である．その処理は「二つの頂点が一定のサイズ
の密な部分グラフに含まれているならば，それらの共
通の隣接頂点の個数は大きい」という仮定に基づいて
行われる．
2.2.3
極大クリーク列挙
最後に，クラスタとして研磨グラフの極大クリーク
を列挙することを行う．
すべての極大クリークを列挙するための効率的な手
法はいくつか提案されている牧野の手法 [2] は O(∆4 )
時間遅延ですべての極大クリークを列挙する．富田の
手法 [3] は O(3n/3 ) 時間ですべての極大クリークを列
挙する．この計算量は頂点数 n について最善である．
クリークの個数の上限は頂点数に対して指数オーダー
ではあるが，実際のグラフはグラフ研磨によって極大
クリークの個数は十分に削減されているため，これら
のアルゴリズムによって高速にすべての極大クリーク
を列挙することができる．
3
提案手法
本節では，異なる閾値に対して効率的にグラフ研磨
を再計算するための提案手法について詳しく説明する．
まず，閾値の変化を二つの場合に分けて説明する．す
なわち，変化前の閾値 θ1 と変化後の閾値 θ2 の大小で
ある．θ1 と θ2 の大小によって以下の変化が生じる．
1. θ2 < θ1 のとき元のグラフに対して，新しい辺の
増加のみが生じる．
2. θ2 > θ1 のとき元のグラフに対して，元の辺の削
除のみが生じる．
どちらの変化に対しても，共通して以下の値を閾値
の変化ごとに記録するという方針を取る．
3.1
辺を追加するアルゴリズム: θ2 < θ1
Algorithm 2 Updating polished graph (θ2 < θ1 )
1: for i = 0 to τ do
2:
Q←∅
∪
3:
N Q ← θ2 ≤c≤θ1 −1 Si,c
4:
for all (u, v) such that (u, v) ∈ Q do
5:
for all w such that w is a neighbor of u in a
graph Gi do
6:
c ← Xi,v,w
7:
Xi,v,w ← c + 1
8:
move (v, w) from Si,c to Si,c+1
9:
if c + 1 = θ2 then
10:
insert (v, w) into N Q
11:
end if
12:
end for
13:
for all w such that w is a neighbor of v in a
graph Gi do
14:
c ← Xi,u,w
15:
Xi,u,w ← c + 1
16:
move (u, w) from Si,c to Si,c+1
17:
if c + 1 = θ2 then
18:
insert (u, w) into N Q
19:
end if
20:
end for
21:
add an edge (u, v) to a graph Gi
22:
end for
23:
Q ← NQ
24: end for
Algorithm 2 は新しい閾値が古い閾値よりも小さい
ときに研磨グラフを更新するためのアルゴリズムであ
る．このアルゴリズムは新しく増加する辺を Gi に挿
入しつつ Si , Xi を更新するという処理を行う．更新作
業は，S0 からグラフ G1 に挿入する辺を計算し，それ
らの辺を挿入しつつ G2 に挿入する辺を計算するとい
うように，順々にグラフを更新していく．
さて，次にこのアルゴリズムの時間計算量について
解析する．時間計算量について以下の定理が成立する．
1. グラフ Gi のすべての頂点のペア (u, v) に対して
共通隣接頂点の個数 Xi,u,v を記録する．
Theorem 1. Algorithm 2 の時間計算量は
∑
O( (|Ei′ | − |Ei |)∆′i ) である．
2. 整数 i, c (0 ≤ i ≤ τ ) (1 ≤ c ≤ |V |) に対して
Xi,u,v = c となるような頂点のペア (u, v) の集
合 Si,c を記録する．
Proof. アルゴリズム内における i が k のときに保持さ
れている Q を Qk とする．Qk に辺を挿入するための
時間は，θ2 ≤ c < θ をみたす Sk,c の中のすべての辺
を挿入するだけなので，O(|Qk |) である．
また Xk and Sk を更新するために必要な時間は
O(|Qk |∆′k ) である．更新のためには，挿入された辺の
端点のすべての隣接頂点をたどる．そのような隣接頂
提案手法では，これらの値を記録し，閾値の変化に対
してグラフとともにこれらの値を更新するという方法
を取る．次に，それぞれの閾値の変化の仕方に対して，
これら二種類の値の更新の方法を説明する．
− 71 −
点の個数は，各辺に対して高々 2∆′k であり，それぞれ
の隣接頂点について Xk , Sk を更新するための時間は
定数である．したがって，処理全体では O(|Qk |∆′k ) と
なる．
このアルゴリズムでは，Qk は Ei′ −Ei に等しい．した
∑
がって Algorithm 2 の時間計算量は O( (|Ei′ | − |Ei |)∆′i )
である．
次に，本アルゴリズムの正当性について解析する．
Lemma 1. 任意のグラフ G = (V, E) と頂点のペア
(u, v) ∈
/ E と (x, y) に対して，以下が成り立つ
′
′
′
′
|N [x] ∩ N [y]| = |N [x] ∩ N [y]| + 2 ⇐⇒
(x, y) = (u, v)
|N [x] ∩ N [y]| = |N [x] ∩ N [y]| + 1 ⇐⇒
((x, y) = (u, w) ∧ w ∈ N (u))∨
((x, y) = (v, w) ∧ w ∈ N (v))
ただし N (u) はグラフ G における u の隣接頂点の集
合であり，N ′ (u) はグラフ G′ = (V, E ∪ {(u, v)}) に
おける u の隣接頂点の集合である．
Proof. 新しい隣接頂点の集合について，N ′ [u] = N [u]∪
{v} and N ′ [v] = N [v] ∪ {u} であり，残りの隣接頂点
の集合は変化しない．
したがって，|N ′ [u] ∩ N ′ [v]| = |N [u] ∩ N [v]| + 2 が成
り立つ．また任意の頂点 w (w ̸= u and w ̸= v) に対し
て v ∈ N [w] ならば |N ′ [u]∩N ′ [w]| = |N [u]∩N [w]|+1
であり，u ∈ N [w] ならば |N ′ [v] ∩ N ′ [w]| = |N [v] ∩
N [w]| + 1 である．
Lemma 2. 各ループの 3 行目の実行直前において，以
下が成り立つ
1. Q は Ei′ − Ei である．
2. Gj は G′j と等しい．
3. Xj,u,v = |Nj′ [u] ∩ Nj′ [v]| が成り立つ．
4. Cj,c は |Nj′ [u] ∩ Nj′ [v]| = c をみたすような頂点
のペア (u, v) の集合である．
Proof. i = 0 のときは明らかに成り立つ．i = k − 1 の
とき成り立つと仮定すると，Q is Ek′ − Ek であり，そ
の後の処理で Q をすべて Gk に挿入するため，Gk は
G′k と等しい．また，Lemma 1 より Xj,u,v と Sj,c は
上記のように更新される．したがって Lemma 2 は成
立する．
Lemma 2 より，アルゴリズムの終了時点では新しい
グラフ G′0 , . . . , G′τ と二種類の値 X, C を更新できるこ
とが示される．
3.2
辺を削除するアルゴリズム: θ2 > θ1
Algorithm 2 は新しい閾値が古い閾値よりも大きい
ときに研磨グラフを更新するためのアルゴリズムであ
る．このアルゴリズムは，algorithm 2 とほぼ同様であ
り，異なる箇所は Xi,u,w の値の増減および辺の挿入削
除の違いのみである．
このアルゴリズムの時間計算量および正当性は algorithm 2 と同様に証明することができる．時間計算量
∑
は O( (|Ei | − |Ei′ |)∆i ) である．
Algorithm 3 Updating polished graph (θ2 > θ1 )
1: Q ← ∅
2: for i = 0 to τ do
3:
Q←∅
∪
4:
N Q ← θ1 ≤c≤θ2 −1 Si,c
5:
for all (u, v) such that (u, v) ∈ Q do
6:
remove an edge (u, v) to a graph Gi in a graph
Gi
7:
for all w such that w is a neighbor of u do
8:
c ← Xi,v,w
9:
Xi,v,w ← c − 1
10:
move (v, w) from Si,c to Si,c−1
11:
if c = θ2 then
12:
insert (v, w) into N Q
13:
end if
14:
end for
15:
for all w such that w is a neighbor of v in a
graph Gi do
16:
c ← Xi,u,w
17:
Xi,u,w ← c − 1
18:
move (u, w) from Si,c to Si,c−1
19:
if c = θ2 then
20:
insert (u, w) into N Q
21:
end if
22:
end for
23:
end for
24:
Q ← NQ
25: end for
4
実験
本手法の効率性を解析するために計算機を用いた
実験を行った．実験には，Amazon Web Services の
c4.xlarge (CPU: Intel Xeon E5-2666, Memory: 7.5GB)
を用いた．この実験では，複数のデータに対して θ =
3, 4, . . . , 50 のすべてのパラメータでグラフ研磨を行う
時間を計測した．実験に用いる手法は，θ = 50 から始
めて，θ を 1 つずつ減らしながら本手法を用いて再計
− 72 −
4.1
t=1d=5
120
100
Time [ms]
60
40
20
60
20
0
100
150
200
250
# of vertex
300
350
0
100
400
図 1: τ = 1 d = 5
t = 1 d = 15
150
200
250
# of vertex
300
350
400
図 2: τ = 5 d = 5
t = 5 d = 15
50000
naive method
our method
800
naive method
our method
40000
700
500
Time [ms]
Time [ms]
600
400
30000
20000
300
200
10000
100
0
100
150
200
250
# of vertex
300
350
0
100
400
図 3: τ = 1 d = 15
t = 1 d = 30
6000
200
250
# of vertex
300
350
400
図 4: τ = 5 d = 15
t = 5 d = 30
naive method
our method
100000
80000
Time [ms]
4000
Time [ms]
150
120000
naive method
our method
5000
3000
2000
60000
40000
1000
20000
0
100
150
200
250
# of vertex
300
350
400
0
100
150
200
250
# of vertex
300
350
400
Relaxed caveman graph
図 5: τ = 1 d = 30
Caveman graph は l 個の k-クリークに対してそれ
ぞれ一つの辺を取り除き隣接するクリークに接続させ
ると得られるグラフである．Relaxed caveman graph
は caveman graph の各辺について独立に p の確率で
ランダムなところに辺を張り替えることで得られるグ
ラフである．
この実験では各パラメータ (p, k) についてクラスタ
の個数を変化させたときの実行時間の変化を調べた．な
お，繰り返しの回数については，すべてのパラメータ
設定で τ = 1 としている．Figure 7–12 は各パラメー
タにおける実験結果を示す図である．
実験結果の考察
まず，Binomial graph の結果についてだが，今回の
実験では，比較的小さい d については，比較手法より
も高速に動作したが，d が大きくなると比較手法より
も遅くなるという結果になった．これは，d が小さいグ
ラフについては，閾値が小さくなってもグラフが密に
ならず，変化する辺の数はそれほど多くないが，d が
大きいときは，閾値が小さくなると研磨グラフがほと
図 6: τ = 5 d = 30
んど一つの完全グラフになってしまい変化する辺の数
が大きくなることが原因と考えられる．
一方，Relaxed caveman graph については，ほとん
どのグラフについて，本手法のほうが比較手法よりも高
速に動作するという結果が得られた．これは，Relaxed
caveman graph がほとんどクリークの集合に近いグラ
フであるため，閾値が小さくなっても変化する辺の数
が大きくならないためと考えられる．
5
4.3
80
40
Binomial graph
Binomial graph は頂点の間にランダムに辺を張るこ
とで構築されるグラフである．具体的には，任意の頂
点ペアに対してそれぞれ独立に p の確率で辺を張るこ
とで構築される．
この実験では，他のパラメータ d を導入してそれに
もとづいて p = d/|V | と設定することで p の値を決定
した．パラメータ d を導入する目的は，異なるグラフ
のサイズに対して平均の頂点の次数を一定に設定する
ことである．
実験では，さまざまなパラメータ (d, τ ) に対してグ
ラフの大きさを変化させながら実行時間を計測した．
Figure 1–6 は各パラメータで得られた実行時間を示す
図である．青い線は提案手法の実行時間であり，赤い
線はグラフ研磨をそのまま適用した結果を示している．
naive method
our method
120
80
900
4.2
t=5d=5
140
naive method
our method
100
Time [ms]
算するという手法である．また，比較する手法は，グ
ラフ研磨を各パラメータに対して前の情報を用いずに
そのまま行うという手法である．
実験で用いるグラフには二種類のランダムグラフ Binomial graph と Relaxed Caveman graph を用意した．
以降では，それぞれのグラフについて実験結果を述べ
たあと，二つの結果について考察を行う．
まとめ・今後の課題
本論文では，異なる閾値に対してグラフ研磨の再計
算をするためのアルゴリズムを提案した．このアルゴ
リズムは，すべての頂点ペアについて共通隣接頂点の
個数を記録し，順番にその個数を更新していくことで
新しいグラフ研磨の結果を求める．時間計算量は，す
べてのグラフに追加または削除される辺の個数に線形
となっている．実験により，変化する辺の数が大きく
ならないようなグラフについては，そのままグラフ研
磨を行うよりも高速に動作することが確認された．
− 73 −
t = 1 p = 0.01 k =16
900
800
50000
700
[2] Makino, Kazuhisa, and Takeaki Uno. “New algorithms for enumerating all maximal cliques.” Algorithm Theory-SWAT 2004. Springer Berlin Heidelberg (2004). 260–272.
naive method
our method
40000
500
Time [ms]
Time [ms]
600
400
300
30000
20000
200
[3] Tomita, Etsuji, Akira Tanaka, and Haruhisa Takahashi. “The worst-case time complexity for generating all maximal cliques and computational experiments.” Theoretical Computer Science 363.1
(2006). 28–42.
10000
100
0
0
t = 1 p = 0.01 k =64
60000
naive method
our method
10
20
30
40
# of clusters
50
60
0
0
70
図 7: p = 0.01 k = 16
t = 1 p = 0.1 k =16
1200
1000
10
20
30
40
# of clusters
50
60
70
図 8: p = 0.01 k = 64
t = 1 p = 0.1 k =64
80000
naive method
our method
70000
naive method
our method
[4] Karp, Richard M. “Reducibility among combinatorial problems” springer US, (1972).
60000
50000
Time [ms]
Time [ms]
800
600
40000
30000
400
20000
200
0
0
10000
10
20
30
40
# of clusters
50
60
0
0
70
図 9: p = 0.1 k = 16
t = 1 p = 0.2 k =16
1600
1400
10
20
30
40
# of clusters
50
60
70
図 10: p = 0.1 k = 64
t = 1 p = 0.2 k =64
100000
naive method
our method
naive method
our method
80000
1200
Time [ms]
Time [ms]
1000
800
60000
40000
600
20000
400
200
0
0
0
0
10
20
30
40
# of clusters
50
60
70
図 11: p = 0.2 k = 16
10
20
30
40
# of clusters
50
60
70
図 12: τ = 1 p = 0.2 k =
64
今後の課題は，提案手法を他の類似尺度を用いたグ
ラフ研磨に対しても適用できるように拡張することで
ある．提案手法は，類似尺度を共通隣接頂点の個数と
したときのみ利用できる手法であるが，マイクロクラ
スタリングでは Jaccard 類似度や PIM などを用いてグ
ラフ研磨を行うことがあるため，これらのグラフ研磨
に対しても利用できるようにすることが今後の課題で
ある．
謝辞
本研究は，JST，CREST の支援を受けたものである．
参考文献
[1] Uno, Takeaki, et al. “Micro-clustering: Finding
small clusters in large diversity.” arXiv preprint
arXiv:1507.03067 (2015).
− 74 −

Download Report