DEIM Forum 2013 E8-5

符号なしラプラス行列を用いた部分グラフ検索の効率化
木村 達郎†

片山薫†† 首都大学東京システムデザイン研究科 〒 191-0065 東京都日野市旭が丘 6-6
E-mail: †ttro.kimura@gmail.com, ††kaoru@tmu.ac.jp
あらまし

近年, グラフはコンピュータビジョン, 類似検索, 化合物の表現などに利用されており, 重要なデータモデルとなっている. あるグラフに他のグラフが含まれているかどうかを判定する問題は部分グラフ同型判定問題と呼ばれ,部分グラフ同型判定問題において，組み合わせ的手法によって問題を効率よく解く VF2 や Ullmann の手法などが研究されてきた．しかし，グラフのサイズが大きくなると，調べなければならない組み合わせの量が急激に増加し, 膨大な計算時間がかかる． グラフを行列で表現し, 行列の固有値に関する定理である Interlace 定理の条件式を用いることで, 部分グラフではないことを数値比較によって判定することができる. この判定は部分グラフでないことを判定できるだけであるので, 組み合わせ的な手法の前処理として使う. 本研究ではグラフを符号なしラプラス行列で表現した時の性質を利用し, 固有値を用いた部分グラフ同型判定の効率的な手法を提案する.
キーワード

符号なしラプラス行列, 固有値, 部分グラフ同型判定, Interlace 定理

Tatsuro KIMURA† and Kaoru KATAYAMA†† Graduate School of System Design, Tokyo Metropolitan University
Asahigaoka 6-6, Hino-shi, Tokyo, 191–0065 Japan
E-mail: †ttro.kimura@gmail.com, ††kaoru@tmu.ac.jp

1. は じ め にラフでないことを判定できるだけであるので, 組み合わせ的手法の前処理として使う. しかし, 一般部分グラフを扱う場合, グ

近年，グラフはより重要なデータモデルとなってきており，ラフを表現した行列のサイズは枝数に依存しており, 固有値のコンピュータビジョン，類似検索などの情報学だけでなく様々計算時間が多くなっていた. そこで我々は, 接続行列を用いたグな分野で利用されている．情報学の分野においては画像や回路ラフの行列表現と符号なしラプラス行列の 0 以外の固有値は等図，ネットワークフローなどがグラフで表現されていて，近年しくなるという性質を利用し, 固有値の計算時間が枝数に依存幅広く利用されている XML データもグラフで表現することしない, 固有値を用いた部分グラフ同型判定の効率的な手法をができる．コンピュータビジョンの分野では，文体や風景を識提案する.

別するための複雑な関係がグラフで表現されている．また，パターン識別ではグラフデータの効率的な検索が重要な課題となっている．化学，生物分野において，たんぱく質や化合物やDNA などのデータがグラフで表現されている．

2. 準

備

2. 1 グ ラ フ
本稿では, ラベル付き無向グラフ G = (V, E, LV , LE , µ, ν)あるグラフ Gl に他のグラフ Gs が含まれている時,Gs は Gl のを 対 象 と す る.V = {v1 , v2 , . . . , v|V | } を 頂 点 の 集 合,E =部分グラフである. 部分グラフかどうかを判定する問題は部分{e1 , e2 , . . . , e|E| } = {vi vj |vi , vj ∈ V, i ̸= j} を枝の集合,Lv

グラフ同型判定問題と呼ばれ, 部分グラフ同型判定問題においを頂点ラベルの集合,LE を枝のラベルの集合とする.µ, ν をラて，組み合わせ的手法によって問題を効率よく解く VF2 [1] やベルを与えるための関数とする.µ : V → LV , ν : E → LE は,Nauty [2] や Ullmann [3] の手法などが研究されてきた．しか個々の頂点と枝にラベルを割り当てる関数である.

し，グラフのサイズが大きくなると，調べなければならない組み合わせの量が急激に増加し, 膨大な計算時間がかかる．

2. 2 Interlace 定理
α1 <= α2 <= ··· <
= α n とβ 1 <= β2 <= ··· <= βm（m < n）の 2 つグラフを行列で表現し, 行列の固有値に関する定理である Inter-の数列が以下の式を満たすとき,{βi } は {αi } を Interlace するlace 定理 [4] の条件式を用いることで, 部分グラフではないことと言う.

を数値比較によって判定することができる. この判定は部分グ

αi <= βi <= αi+（n−m）(1)［定理 1］（Interlace 定理） S を S T S = I を満たす n×m の実行列とし, P をα1 <= α2 <= ... <= αn の固有値を持つ n × n の対称行列とする.Q = S T P S を定義し, Q はβ1 <= β2 <= ··· <= βm（m < n）の固有値を持つとする.このとき, Q の固有値は P の110100 1 0 0 0 1 1
Ng = 
 0 1 1 0 0 0
 0 0 1 1 1 0

固有値をInterlace する.

00000100 1 0 1

2. 3 符号なしラプラス行列
グラフ G の頂点 {v1 , v2 , . . . , v|V | } の次数を {d1 , d2 , . . . , d|V | }と す る. 次 数 と は 頂 点 に 接 続 し て い る 枝 の 本 数 で あ る.

3. 従 来 手 法{d1 , d2 , . . . , d|V | } を対角成分に持つ対角行列を D, グラフ G

3. 1 頂点ラベルによるグラフ分割手法の隣接行列を W とすると D + W はグラフ G の符号なしラプ

頂点ラベルを利用してグラフを分割する. 同じ頂点ラベルを持つ頂点全てを元とする頂点集合を作成し, その頂点集合で枝ラス行列である.
ここでを持つもの全てについて枝を張り, 分割グラフを作成する. 頂点{W = (wij ) =1(i ̸= j, (vi vj ) ∈ E)

0

(それ以外)

ラベルに基づいた分割グラフ gi は, あるグラフ g の同じラベル(2)

そしてグラフ G の接続行列を N とすると D + W と N N Tは同じ行列を表す.

を持つ頂点を全て集めた頂点集合 Vi を持つグラフで,g の部分グラフである.

3. 2 枝ラベルによるグラフ分割手法
枝ラベルを利用してグラフを分割する. 同じ枝ラベルを持つ枝全てを元とする枝集合を作成し, その枝集合が結んでいる頂

D + W = NNT(3)

点全てを頂点集合として, 分割グラフを作成する. 枝ラベルに基づいた分割グラフ gi は, あるグラフ g の同じラベルを持つ枝を

ここで{N = (nij ) =1(vi vk = ej ∈ E)

0(それ以外)全て集めた枝集合 Ei を持つグラフで,g の部分グラフである.

(4)

3. 3 Interlace 定理の条件を満たすグラフの行列表現
グラフを下記の行列 B または C で表現した時, その固有値

図 1 のグラフ g を D, W, N で表現した行列 Dg , Wg , Ng を下記に示す. 図 1 の数字はそれぞれ頂点と枝の ID を表してる.

が Interlace しなければ, 部分グラフではない. ラベルで分割することによってラベルを考慮しなくてよくなり, 下記の行列表現が有効になる.

B = NT N

11[26C=4255343
図17(5)]
0NNT0(6)行列 B, C は対称行列で, サイズはそれぞれ |E| × |E|, (|V | +|E|) × (|V | + |E|) である.

グ ラ フ g

3. 4 ラベル分割を用いた固有値による部分グラフ同型性



以下にラベル分割を用いた固有値による部分グラフ同型性判判定

30000

 0 3 0 0 0 
Dg = 
 0 0 2 0 0 
 0 0 0 4 0 0000201110

 1 0
Wg = 
 1 0
 1 10110

固有値による部分グラフ同型性判定の実行手順
入力：グラフデータ Gl , Gs

1: Gl と Gs を頂点ラベルによって分割する
0 1 1 
0 1 0 
1 0 1 0定の実行手順を示す.

2: 1 で分割したグラフを枝ラベルによって分割する
3: 分割したグラフの頂点数と枝数に矛盾があれば部分グラフでないと判定

4: 2 で分割したグラフを行列に変換する
5: 4 の行列の固有値を計算する
6: 5 の固有値が Interlace しないなら部分グラフでないと判定

グラフを頂点ラベルで分割することによって異なる頂点間の情報は失うことになるが, 固有値による部分グラフ同型性判定の1

性能は良くなることが知られている [5]. グラフの行列表現とし

12てサイズ |E| × |E| 以上の行列で表現しており, 固有値の計算時間は枝数に依存していた.

424. 提 案 手 法

34. 1 行列の性質

図2

グ ラ フ g′

210

1

1

112

43

Interlace 定理によって一般部分グラフでないものを判別する
時, グラフを 行列 B や C で表現しており, サイズは |E| × |E|以上になり, 固有値の計算に多くの計算コストを必要としていた. そこで, 符号なしラプラス行列と行列 B の 0 以外の固有値は等しくなる [6] という性質を利用する. 以降, 符号なしラプラス行列を A とする.

A = D + W = NNT(7)

行列 A のサイズは |V | × |V |, 行列 B のサイズは |E| × |E|
で, 固有値の個数はそれぞれ |V | 個, |E| 個である. つまり頂点数と枝数の情報があれば 行列 B の固有値を計算せずに, 行列 A の固有値を計算することによって, 行列 B の固有値がわかるということである.

 1 2 1 1  0 1 2 1 Bg′ = NgT′ Ng′ = 4. 2 提案手法の手順
今回提案するのは, 頂点ラベル, 枝ラベルで分割したグラフを行列 A で表現し, その固有値を計算すると, 行列 B の固有値を得ることができるので, 行列 B の固有値が Interlace するか判定するというものである.
頂点, 枝ラベルにより分割したグラフは, 頂点, 枝それぞれにおいてラベルが１種類となり, 今回の行列表現が有効なものとな（例）図 1 のグラフ g を A, B で表現した行列 Ag , Bg と Ag , Bg のる. 以下に提案手法の実行手順を示す.

固有値Θ(Ag ), Θ(Bg ) を下記に示す.固有値Θ(Ag ), Θ(Bg ) の 0 以外の値は等しくなる.
図 2 のグラフ g ′ はグラフ g の部分グラフであり, g ′ を B で表現

提案手法の実行手順
入力：グラフデータ Gl , Gs

した行列 Bg′ は行列 Bg の 主小行列になり Interlace 定理の条件

1: Gl と Gs を頂点ラベルによって分割するを満たす.

2: 1 で分割したグラフを枝ラベルによって分割する
3: 分割したグラフの頂点数と枝数に矛盾があれば部分グラフでないと判定31


 1 3T
Ag = Ng Ng = 
 1 0
 1 101

110

4: 2 で分割したグラフを行列 A に変換する



5: 行列 A の固有値を計算し, 行列 B の固有値を得る

0 1 1 

2 1 0 

1 4 1 0

1

6: 行列 B の固有値が Interlace しないなら部分グラフでないと判定

25. 実験と評価



2


 1

 0

TBg = Ng Ng =  1

 1
 10

101

11021

100

121101121001

121000120 

1 1 1 1 

011112

実験データとして頂点数, 枝数, ラベル数を設定した人工グ
ラフデータをランダムに生成し, 使用する. データベースのグラフと問い合わせグラフをそれぞれ 100 個に設定する. 実験環
境は Windows Vista Bisiness Service Pack 2(64bit), Intel(R)Xeon(R) 2.33GHz, メモリ 8GB である.
5. 1 行列表現の比較
グラフを行列 A, B, C で表現した時の固有値による部分グラ
フ同型性判定の処理時間と発見された部分グラフでない数を比Θ(Ag ) = {1.00, 1.24, 2.64, 3.00, 6.12}

較する. 図 3 にデータベースのグラフを頂点数 200, ラベル数

Θ(Bg ) = {0.00, 0.00, 1.00, 1.24, 2.64, 3.00, 6.12}

3, 平均枝数 10000, 問い合わせグラフを頂点数 100, ラベル数 3,1400

表 1 にその時に発見された部分グラフではないグラフ数を示す.

1200

図 3 と表 1 より Ａ, Ｂ, Ｃ で発見された部分グラフでないグラ

1000

フの数は等しくて問い合わせグラフの枝数が多いほど多くなり,処理時間は ＡがＢより少なく, ＢがＣ より少ないことが確認できる.

処理時間（秒）平均枝数を 2000 から 4000 に変化させた時の処理時間を示す.

800
A
600
B400
C

図 4 にデータベースのグラフを頂点数 200, 平均枝数 10000, 問200い合わせグラフを頂点数 100, 平均枝数を 3000 に固定し, ラベ034

ル数をそれぞれ 3 から 6 に変化させた時の処理時間を示す. 表

56ラベル数2 にその時に発見された部分グラフではないグラフ数を示す. 図
図 4 ラベル数と処理時間の関係

4 と表 2 より Ａ, Ｂ, Ｃで発見された部分グラフでないグラフの数はほぼ等しくてラベル数が多いほど多くなり, 処理時間はＡ1400がＢより少なく, ＢがＣより少ないことが確認できる.

1200

枝密度を 50%, 問い合わせグラフをラベル数 3, 平均枝密度を50%, 頂点数を 110 から 150 に変化させた時の処理時間を示す.
表 3 にその時に発見された部分グラフではないグラフ数を示す.

処理時間（秒）

図 5 にデータベースのグラフを頂点数 200, ラベル数 3, 平均1000
800
A600
B400C

図 5 と表 3 より Ａ, Ｂ, Ｃで発見された部分グラフでないグラ

200

フの数は等しくて問い合わせグラフの頂点数が多いほど多くな

0110

り, 処理時間はＡがＢより少なく, ＢがＣより少ないことが確認

120

130140150

頂点数できる.
図 5 頂点数と処理時間の関係
1400

枝数

処理時間（秒）

1200
1000
800
A600
B

表3110 120 130 140 150

A03141542B

03141542C03141542

発見された部分グラフでないグラフの数

400C2005. 2 前処理としての効果

02000

2500

3000

3500

4000

枝数

組み合わせ的手法の一つである VF2 を使った実験を行う. 提案手法の, 行列 A を用いた部分グラフ同型性判定を前処理として行い, 部分グラフでないと判定できなかったグラフに対して

図 3 枝数と処理時間の関係

VF2 による判定を行うものと, 前処理を行わないものを比較する. 以降, この前処理によって部分グラフでないと判別すること

枝数 2000 2500

A

表103000 3500 4000

041344をフィルタリングと呼ぶ.
図 6 にデータベースのグラフを頂点数 400, ラベル数 3, 平均B

0041344

枝密度を 50%, 問い合わせグラフをラベル数 3, 平均枝密度をC

004134450%, 頂点数を 260 から 340 に変化させた時の処理時間を示す.

発見された部分グラフでないグラフの数

表 4 にその時にフィルタリングされたグラフ数と処理時間を示す. 図 6 と表 4 より問い合わせグラフの頂点数が多くなるほど,フィルタリングされたグラフ数が増え, 提案手法の処理時間がラベル数 3

表2456

A

4 19 71 96

B

4 19 71 96

C

4 19 71 95発見された部分グラフでないグラフの数

VF2 のみに比べ少なくなるが頂点数が少なくなるほどフィルタリングされるグラフ数が少なくなり, 提案手法の処理時間がVF2 のみに比べ差が少なくなっていくことが確認できる. また
頂点数 260 以下はフィルタリングされるグラフ数が 0 だと予想されるので提案手法の処理時間は VF2 のみに比べフィルタリングの処理時間が余計にかかると予想される．つまりデータベースのグラフと問い合わせグラフの頂点数の差が少ないほど提案手法は効果的であり, 頂点数の差が多いほど効果的ではな

いと考えられる.
9000

図 7 にデータベースのグラフを頂点数 400, 平均枝密度を 50%,

8000

問い合わせグラフを頂点数 320, 平均枝密度を 50% に固定し,表 5 にその時にフィルタリングされたグラフ数と処理時間を示す. 図 7 と表 5 よりラベル数が多いほどフィルタリングされる処理時間（秒）

ラベル数をそれぞれ 3 から 6 に変化させた時の処理時間を示す.

7000
6000
5000
4000

提案手法

3000

VF22000

グラフ数は多くなるが VF2 のみの処理時間が大幅に少なくな

1000り, 提案手法と VF2 の差が少なくなることが確認できる. つま

034り, ラベル数が少ないほど提案手法が効果的であると考えられ

56ラベル数る.
図 7 ラベル数と処理時間の関係

図 8 にデータベースのグラフを頂点数 400, ラベル数 3, 平均枝密度を 50%, 問い合わせグラフを頂点数 320, ラベル数 3, 枝密度を変化させた時の処理時間を示す. 表 6 にその時にフィルタラベル数

3リングされたグラフ数と処理時間を示す. 図 8 と表 6 より問い

グラフ数36 69 95 100

4

処理時間 (秒) 163 98

合わせグラフの枝密度が上がるほどフィルタリングされるグラ

560636表 5 フィルタリングされたグラフの数と処理時間フ数は多くなるが提案手法と VF2 のみの処理時間の差が小さくなり, 枝密度が小さくなるほどフィルタリングされるグラフ

12000

フと問い合わせグラフの枝密度の差が小さいほど提案手法が効10000

果的であると考えられる. つまり, データベースのグラフと問い合わせグラフの枝密度の差が少ないほど提案手法が VF2 のみに比べ処理時間が少なくなり, 提案手法が効果的になると考処理時間（秒）数が少なくなりことが確認できる. つまり, データベースのグラえられる.

8000
6000

提案手法

4000

VF22000

図 9 にデータベースのグラフを頂点数 400, ラベル数 3, 問い合040

わせグラフを頂点数 320, ラベル数 3 に固定し, 枝密度をそれぞ45505560

枝密度（%）枝密度（ ）れ変化させた時の処理時間を示す. 表 7 にその時にフィルタリングされたグラフ数と処理時間を示す. 図 9 と表 7 より枝密度

図 8 問い合わせグラフの枝密度と処理時間の関係の変化によってフィルタリングされたグラフ数は大きく変化せず, 提案手法の処理時間が VF2 のみに比べ安定して少ないことが確認できる. つまり, データベースのグラフと問い合わせグラフの頂点数が一定で枝密度が等しいなら, 提案手法によって安枝密度 (%)

40455055

グラフ数693671 100

処理時間 (秒) 192 185

定した効果を得ることができると考えられる.

163 1336082

表 6 フィルタリングされたグラフの数と処理時間

25000
8000
20000

6000
5000

提案手法

4000

VF2

処理時間（秒）

処理時間（秒）

7000

15000
提案手法
10000
VF23000
5000
2000
260

280

300

320

340

0

頂点数

3040506070

枝密度（%）枝密度（ ）

図 6 頂点数と処理時間の関係
図 9 枝密度と処理時間の関係
頂点数
グラフ数
処理時間 (秒)260 280 300 320 340
06123660

172 187 182 163 142

表 4 フィルタリングされたグラフの数と処理時間

枝密度3040506070

グラフ数2830362526

処理時間 (秒) 156 157

163 198 218

表 7 フィルタリングされたグラフの数と処理時間

6. ま と め
本稿では符号なしラプラス行列の固有値の性質を利用し, 固有値を用いた部分グラフでないグラフを発見する処理を効率化し、処理時間を短縮できることを示した. 実験の結果から提案
手法がより有効な場合はラベル数が少なく, データベースと問い合わせのグラフの頂点数の差が小さく, 枝密度の差が小さい場合であることがわかった.

文

献[1] L. P. Cordella, P. Foggia, C. Sansone and M. Vento. An improved algorithm for matching large graphs. Proc. of the 3rdIAPR TC-15 Workshop on Graph-based Representations in
Pattern Recognition, Ischia, Italy, pp. 149-159 (2001).
[2] B.D.Mckay. Practical Graph Isomorphism. Congressus
Numeranitum,vol.30,pp.45-87,1981.
[3] J. R. Ullmann. An algorithm for subgraph isomorphism. J.
Assoc. Comput. Mach, Vol. 23, pp. 31-42, 1976.
[4] W. H.Haemers. Interlacing eigenvalues and graphs. LinearAlgebra and its Applications, 226-228, pp. 593-616 (1995).
[5] K.Katayama et al., Detecting Non-subgraphs Eﬃciently byComparing Eigenvalues of Decomposed Graphs, Vol.E95-D,No.11, pp.-, Nov. 2012.
[6] A.E.Brouwer,Willem H.Haemers.Spectra of graph.springer,Feb.2011