DEIM Forum 2013 E9-3

固有値を用いた階層グラフ検索のための行列表現の提案とその評価
笹原 健介†

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

グラフの部分構造を検索する問題は，化合物のデータベースを始めとした様々な分野への応用があり，これまで数多くの研究がなされてきた．しかし，ソーシャルネットワーク等に対する社会的関心の高まりに伴い，グラフというデータ構造そのものに対するニーズは年々複雑化している．単純なノード間の繋がりのみではなく，ノード集合によるコミュニティ間の繋がりや，それらが入れ子状にグループを形成しているような構造によって付加的な情報を持たせることが出来る．本稿では部分グラフ同型性判定問題を階層グラフを用いて行い，効率的なフィルタリン
グ手法の提案を行う．固有値に関する Interlace 定理をフィルタリングに用いた従来手法では，ある階層グラフを複数の行列の集合によって表現し，部分的な構造ごとの比較処理を行なっていた。本提案では，グラフの包含関係を含む階層グラフ全体を新たな行列で表現することを示し，ラベルによるグラフ分割と組み合わせることでフィルタリング精度の向上を目指す．実験結果より，クエリーグラフが密である場合及びラベル数が多い場合において高いフィルタリング精度を示した．
キーワード

部分グラフ同型性判定，階層グラフ，無閉路有向グラフ，Interlace 定理

Kensuke SASAHARA† and Kaoru KATAYAMA†† Graduate School of System Design,Tokyo Metropolitan University
Asahigaoka 6-6, Hino, Tokyo,191–0065 Japan
E-mail: †sasahara-kensuke@sd.tmu.ac.jp, ††kaoru@tmu.ac.jp

1. は じ め になどにおいて表れる．よって，近年データが複雑化している中で，階層部分グラフ同型性問題は部分グラフ同型性判定問題の近年グラフは複雑なデータ構造を持ち，グラフ同士が各々関拡張として，今後重要な課題になっていくと考えられる． 部連付いたデータとして表現されることが多い．タンパク質の相分グラフ同型性判定において，行列の固有値に関する Interlace互作用や SNS コミュニティに代表されるデータ構造は，単純定理 [6] を利用した数値的な手法が有効であることはこれまでなノードの横の広がりのみでは表現し得ず，一定のノード集合数多く示されてきた [7]．鈴木ら [8] の手法においては階層グラを意味のあるまとまりとして捉え，その集合間に何らかの関係フを個々のグラフ集合に分割し，隣接行列で表現する事で比較を持たせることで表現されている [1]．これらのデータ構造はグ処理を行っていた．しかし，どの頂点が別のグラフを含んでいラフの各頂点が他のグラフに関連付けられているような階層的るかという情報までは行列の中に含む事が出来ず，最終的な組な構造を利用することで表現されることがある．この階層的なみ合わせアルゴリズムでのみ確認していた．そこで本稿では階構造は，幅広い分野のデータ分析およびデータ監視の為に，グ層グラフの包含関係を含めた階層隣接行列を提案し，Interlace

ラフデータの視覚化に利用されている [2]．またテキスト処理に定理によって階層グラフにおけるグラフの包含関係を考慮した

おいては，テキストの持つ表面的な情報以外の意味を階層的なフィルタリング手法を提案する．

構造を用いることで持たせることができる [3]．このようなグラフは，階層型グラフデータ, 階層非循環有向グラフ等と表現さ

2. 関 連 研 究れる．これらを階層グラフと呼ぶこととし，通常のグラフの場部分グラフ同型性判定を行う為の研究はいくつもなされてい合と同様に階層部分グラフを定義する．一方のグラフがもう一る．それに関する研究として，Ullmann [9] の手法や VF2 [10]方のグラフに含まれるかどうかを判定する問題を部分グラフ同等がある．Ullmann の手法はバックトラックと呼ばれる手続き型性判定問題という．部分グラフ同型性判定問題は，画像におを用いて部分グラフ同型性判定を行う手法である．VF2 は 2 つける特徴量抽出 [4]，化合物のデータベース [5]，パターン認識のグラフの枝の間のマッピングの状態を更新していくことで 2

つのグラフの間の同型写像を作成する手法である．これらの研究は大規模なグラフへの適応はできるが，単純なグラフにしか適応できない．しかし，近年のデータは単純なグラフだけでは十分な表現力を持たない為，複雑な構造を持ったグラフを利用した研究がなされている．データ分析およびデータ監視の為に，階層的な構造を持つのグラフデータの視覚化トレースツールの開発 [2] や，力学モデルを用いるグラフデータの画面配置手法を階層型のグラフへ拡張 [11] するなどのデータ解析の為の視覚化を目的とした研究がある．他にも，階層的な構造を与える事で，テキストマイニングの性能を向上させる研究 [3] や，複雑な構造を持ったグラフとして，ある頂点にアイテム集合が付与されているグラフであるアイテム集合付きグラフの解析 [12] などがある．これらのように，複雑な構造を持ったグラフに関する研究は各々の限定的な分野ではあるが，徐々になされるようになってきている．対象物のシルエットに基づく形状認識の分野では，Shokoufandeh ら [13] が階層構造を持つ shock graphを対象としたグラフマッチングのためのインデクス手法を提案している．本提案ではより一般的なモデルを用いて，マッチングにおけるフィルタリングを行うことを目的としている．

3. 準

隣接行列は対称行列であり，行列の次数はグラフの頂点数に等しい．以降，隣接行列とは上記の頂点ラベルを用いたものを指すこととする．
［定義 2］ 隣 接 行 列 は n 個 の 頂 点 V g = {v1 , v2 , · · · , vn }と，E g = {(vi , vj )|vi , vj ∈ V g , i =| j} の枝を持つグラフ

g = (V g , E g , Lg , µg ) を n × n 行列 Ag を用いて以下のように表現する．対角成分には頂点のラベル，非対角成分には枝のラベルを使用する．agij を 行列 Ag の (i, j) 要素とし，これより行列の要素を同様に小文字のアルファベットで表すこととする．
g
(i = j) µ (vi )agij :=備3. 1 Interlace 定理と部分グラフ
次の 2 つの実数列: α1 <= α2 <= ... <= αn ,θ1 <= θ2 <= ... <= θm(m <= n) において，以下を満たすとき，2 つの実数列は Interlaceするという．

(i =| j, (vi , vj ) ∈ E g )µg (vi , vj ) 0(otherwise)［例 1］ 図 1 にグラフの例として g l を示す．また，その誘導部分グラフを g1s ，部分グラフを g2s に示す．
lss

［例 2］ 図 1 のグラフを，それぞれ隣接行列 Ag , Ag1 ,Ag2 を用いて以下のように表現することができる．

αi <= θi <= αi+(n−m) (i = 1, . . . , m)(1)⊤

［定理 1］ (Interlace 定理) S を S S = I を満たす n×m の実行列とし，A を固有値 α1 <= α2 <= ... <= αn を持つ n × n 対称行列とする．また，B = S ⊤ AS を定義し，B は θ1 <= θ2 <= ... <= θm(m <= n) の固有値を持つとする．このとき,B の固有値と A の固有値は Interlace する．
A

図 1 グラフ g l , 誘導部分グラフ g1s , 部分グラフ g2s の例

グラフ g , gBは対称行列 A, B で表せるものとすると，行列A,B の固有値が Interlace しなければ，グラフ B はグラフ Aの部分グラフではないといえる．本稿では，固有値が Interlacesしないことによって，一方のグラフ g が，もう一方のグラフl11302 1 2 1 0 0 
Ag =  3 1 5 2 0  , 0 0 2 4 1 
2 0 0 1 3

1 11 1 3
 gs 
s,A 2 =  1 2
Ag1 = 121

0 1
3 1 5l(2)01 

5

対称行列から同じ番号の行と列を削除した行列を主部分行列

g の部分グラフではないことを検出する処理をフィルタリング（Principal Submatrix) という．図 1 の例において，誘導部分と呼ぶ．

グラフではない部分グラフの場合，グラフ g2s の隣接行列 Ag2sl

3. 2 グラフと行列表現はグラフ g l の隣接行列 Ag の主部分行列とならない．Interlace

階層グラフでない通常のグラフに関しては，重み付き無向グ定理を部分グラフであるかどうかの判定に用いるとき，誘導ラフに対して議論を進める．

部分グラフではない部分グラフに対しては隣接行列で表現す［定義 1］ グラフ g は以下のように定義される 4 つの要素ることができない．これは S ⊤ S = I , Ag2 = S ⊤ Ag S となる(V g , E g , Lg , µg ) から成り立つ．

n × m 行列 S が一般には存在しない為である．このような場•

V g は頂点の集合 {vi |i = 1, . . . n}

•E は枝の集合 {(vi , vj )|vi , vj ∈ V , i =| j}gsl

合，定義 3 の接続行列を利用した表現方法 [14] を用いることでgInterlace 定理を部分グラフへも利用することができる．しか•L は頂点と枝のラベルの集合

し，Interlace 定理の判定精度は行列表現やそれに伴う行列サイ•µg : V g ∪ E g → Lg は各頂点と各枝にラベルを割り当てズなどによって変化するため，同様の判定結果が得られるわける関数ではない．

g

誘導部分グラフの場合，式 (2) のように隣接行列の対角要素［定義 3］ 拡張接続行列 (Extended incidence matrix) とは，に頂点ラベルを挿入した行列を用いて表現することができる．

グラフ g = (V g , E g , Lg , µg ) を通常の接続行列 N を用いた以下の行列を示す．

(M g :=PN

⊤N

v1H)

Qv 2H

N は，グラフ g の接続行列，⊤N は N の転置，P, Q はそれぞ

v5H

v 4H

v8H

れ以下の pij , qij を要素とする対角行列である．

1nij :=0((vi , vk ) = ej ∈ E )［例 3］

図 2 階層グラフ H の構造を示す例

g1(i = j, vi ∈ V )g(otherwise)µg (ei )(i = j, ei ∈ E g )

0

g2
2v

lsv

l

M g の主部分行列となっていることが確認できる．

1


 0


 0

 0


 0
l
g
M :=  1

 0


 1


 0


 0
1

0000

10

100

2000

1

10000

50001

1

1000

40

000

1

1000

300001

1000

100001

1000

1000010000

3000110000201001

10000

10001000002

1
 0
sg2
M :=  0 1
0001201050101

1100g5g41vv

g44g51vv 4g 5v 2g 4v 3g 4v 2g 5v 3g 5v 4g 3v 3g 3g6g7v

v 4g 6v1g 7v 2g 6v 3g 6v 3g 7v 2g 7g8g9v1g 8v 4g 8v1g 9v 2g 8v 3g 8v 3g 9v 2g 9

図 3 図 2 の階層グラフ H の拡大図

•GH はグラフ集合 {gi |i = 1, . . . , n}•

LH は枝ラベルの集合．枝ラベルはグラフ gi 内の頂点ID を示している•µH : V H ∪ E H → LH は各頂点と各枝にラベルを割り当てる関数•ϕH : V H → GH は各頂点が含んでいるグラフを示す•

φH : E H → V (GH ) × GH は，GH のグラフである関数

g1 が含んでいる頂点 v と，GH のグラフである g2 を，枝 (v1H , v2H ) ∈ E H の v1H と v2H に割り当てる関数であ




1 

1 
0 

1v 3g1g4v 2g 3g230 0 0 
1 0 
0 0 0 
0 

v 2g1

g61s

グラフ g l ,g2s の行列表現を以下の M g , M g2 に示し，M g2 は

v 4g1

v 5g 3v1g 3

v1g 2(otherwise)

v1g1

g3

g2

図.1 において，グラフ g2s は g l の部分グラフである．

v9H(otherwise)µg (vi )pij :=
0qij :=

v 7H

v 6H

v3Hgる．各元の対応としては， φH : (v1H , v2H ) 7→ (v, g2 ) とも表現できる
ssssss［定義 5］ H s = (V H , E H , GH , LH , ϕH , φH ) と，H l =llllll(V H , E H , GH , LH , ϕH , φH ) を階層グラフとする．部分グsl

ラフの条件である単射を f : V g → V g とする. ここで，以3. 3 階層グラフと階層部分グラフ下の条件を全て満たすとき H s は H l の階層部分グラフとし，

図 2 の左側に示すのは本稿で定義する階層グラフの構造であlH s⊂=H と記述する．
ssss

り，ある一つの頂点が別のグラフを包含することで入れ子構造 （ 1 ） 任意の枝 (viH , vjH ) について，(f ′ (viH ), f ′ (viH )) ∈ E Hsllを成している．しかし，この表現では階層数の増加につれてそとなる全単射 f ′ : V g → V g が存在する．これは，H l のの内部構造の把握が困難になる．そのため，図 2 の右側に示す構造 V H , E H 内に， H s の構造 V H , E H と同型の構ような非循環有向グラフを用いて階層ごとに整理し，頂点とグラフの包含関係を有向辺によって表現する．
［定義 4］ 階 層 グ ラ フ H は 以 下 に 定 義 さ れ る 6 つ の 要 素HHHHH

H(V , E , G , L , ϕ , φ ) から成り立つ．

llss

造部分が存在するという意味である．
（ 2 ） 全 て の 頂 点 vHHϕl′(f (vsHss∈ VHsssに お い て ，ϕH (v H )∈)) となる．
s（ 3 ） 枝 (v1H , v2H ) ∈ E Hsは ，φHsssに よって ，(v1H , v2H )ssl•V H は頂点の集合 {viH |i = 1, . . . n}

7→ (v s , g s ) と な る ．枝 φ(f ′ (v1H ), f ′ (v2H )) は φH に•

E H は頂点の順序対を表す枝の集合 {(viH , vjH )|viH , vjH ∈よって，(f ′ (v1H ), f ′ (v2H )) 7→ (v l , g l ) となる．このとき，V H, i =| j}lf (v s ) = v l , g s ⊂=g を満たす．

ss

ls

以下の D H , DH のように表せる．
lていた．階層グラフ H のある一つの頂点 viH を始点とする枝のDH =1 0 0 1
 0 0
 1 1
 0 1

 0 0

 0 0
 0 0
= 0 0

 0 0

 0 1

 0 1


 0 1

 0 1
 0 1


数，および階層数の比較によるフィルタリングは，候補の削減

0

図 4 階層グラフ H l とその階層部分グラフ H s

4. 提 案 手 法
階層部分グラフ同型性判定において，鈴木ら [4] の従来手法
では階層構造の比較によって候補となり得ない階層グラフを事前にフィルタリングし，行列の固有値を用いた数値的手法は階層グラフ H の各頂点 viH が含むグラフ gi に対してのみ行なっには非常に有効であるが処理手順が非常に複雑になるということ，グラフの包含関係に関するチェックが行えないこと等が問題であった．本提案ではグラフの包含関係を含む階層グラフの情報全てを新たな階層接続行列という行列で表現し，Interlace定理によるフィルタリングを可能にする．しかし，行列のサイズはフィルタリング精度に大きな影響を与え，サイズが大きくなるに連れて候補になり得ないグラフを検出しずらくなる事が既に知られている．そのため，本提案ではラベルによるグラフ分割を前処理として行い，行列サイズの縮小を図る．なお，以101000000000000110000011111301333330000002000000000001020000000000300300100000030001011000003000010100000300110200000030001103000000

0

000

0001

00100

000

00000101

1

000

00

00000101

000

0

00001

10

2000

0000

0001

10

2

00

000000

1

0

1

00

100

1

00

00

1

01

100

0

301

3

31

0

20001

1

0

2

000

3

001

00

3

000

1

0

30011


 0

 0

 1s
H
D=
 0

 0
 00
0 
3 

0 
0 

1 
1 
3

4. 2 ラベルによる階層グラフ分割手法

行列を用いた表現により部分グラフにおいても同様の議論が行

大規模な行列の固有値計算には多大な時間を要し，また In-terlace 定理の判定精度も著しく低下してしまうことがこれまで

4. 1 階層接続行列にわかっている．そこで，Katayama ら [14] のグラフ分割手法［定義 6］ 階層接続行列を階層グラフにも同様に応用することで階層隣接行列の行列サ階層グラフ H の全体を表す階層接続行列を拡張接続行列 M gi

イズを縮小し，フィルタリング精度の向上を図る．頂点ラベルと，グラフ gi 及びグラフ gj の包含関係を示す行列であるによる分割階層グラフは，ある階層グラフ H の中である頂点

C gi gj (|V gi + E gi | × |V gj + E gj |) を用いて以下のように定義

ラベル liv のみを持つ頂点集合 Vi からなり，H の階層部分グラする．ここで GH = {g1 , g2 , ..., gn } とする．

フとなる．同様に枝ラベルによる分割階層グラフは，ある階層

グラフ H の中である枝ラベル lie のみを持つ枝集合 Ei からなDH := M g1..
.
⊤

C gn g1···..
.
···

C g1 gn
..

.

M gn

り，H の階層部分グラフとなる．階層グラフ H[lie ][ljv ] は階層
グラフ H をまず枝ラベル lie で分割し，その後頂点ラベル ljv で分割した階層グラフを意味する．
［例 5］ 図 4 の階層グラフ H l , H s の分割階層グラフをそれぞg gcsti j :=µgi (vs )0

れ図 5, 図 6 に示す．

(ϕ(vsgi ) = gj )同じラベルで分割した階層グラフ対が Interlace しない場合，(otherwise)

それらの分割前の階層グラフ対は階層部分グラフ同型となら

なお，GH が全て部分グラフでないとする (=誘導部分グラフのみを対象とする) のであれば，DH内の接続行列を隣接行列表現に換えることで，より小さいサイズの行列で Interlace 定ないことがわかる．したがって，ラベルによる分割によってInterlace 定理の判定に用いる行列サイズの縮小だけでなく，全体の処理時間の軽減も期待できる．

4. 3 提案アルゴリズム

理を利用することが出来る．
ls［例 4］ 定義 8 の表現を用いると図 4 の階層グラフ H , H は

本稿では，一方が他方に含まれないことを示すフィルタリン

1 
0 
0 

0 
0 
0 
0 
0 
0 
1 

0 
1 
0 

0 2

下より紙面の都合上誘導部分グラフについてのみ扱うが，接続える．

0

Algorithm 1 Check Hiersubgraph
Inputs: H s：クエリ，H l：問い合わせ先，N ：ラベル数
Outputs: true or false
1: for i ← 1 to N do
2:H s ，H l を枝ラベル i で分割し H s [i], H l [i] を生成；

3:for j ← 1 to N do
H s [i], H l [i] を頂点ラベル j で分割した H s [i][j], H l [i][j]4:を生成；
図 5 階層グラフ H l , H s を枝ラベル 2 で分割したグラフ

5:end for

6: end for
7: for i ← 1 to N do
8:for j ← 1 to N dosl

H s [i][j], H l [i][j] を階層接続 (隣接) 行列 DH [i][j] , DH [i][j]9:で表現する；sl

10:

DH [i][j] , DH [i][j] の固有値 θ(= {θ1 , ..., θm })，11:

θ と α を Interlace 定理で比較する；

12:

if Interlace 定理を満たさない thenα(= {α1 , ..., αn }) を計算する；

図6

階層グラフ H l [2], H s [2] を頂点ラベル 1 で分割したグラフ

13:

H s は H l の階層部分グラフでない；

14:

return false;

グ精度の評価が目的であるため，予め階層部分グラフになり得

15:

end ifないクエリーとデータセットの組み合わせのみを入力すること

16:

end forを想定している．そのため，階層グラフの行列への変換の際に17: end forは階層隣接行列を用いるが，階層グラフの各頂点に含まれるグ18: H

ラフである各グラフ gi (= ϕ(vi )) が誘導部分グラフではない一般の部分グラフである場合，階層接続行列を用いた表現によって同様に対処出来る．と H l を組み合わせアルゴリズムに通す；

19: if H
20:lに H s と同型な部分がない thenreturn false；

21: else
22:

5. 評 価 実 験sreturn true；

23: end if

ここでは本稿で提案したフィルタリング手法のパフォーマンス評価のための実験を行う．全ての実験は CPU：プロセッ
TMR
サ：Intel⃝Core
i7 CPU 870 @ 2.93GHz 2.93GHz，メモリ：16.0GB，OS：Microsoft Windows 7 Professional Service Pack
1 の環境下で行い，MATLAB R2012b を用いて実装を行った．

変化させる．以上の条件のもと，階層グラフ H l 10 個と階層グ
ラフ H s 10 個に対して，計 100 回の階層部分グラフ同型性判定を行う．

5. 2 実 験 結 果
実験結果を表 1 に示す．全体として，ラベル数及び g s の枝

5. 1 実 験 条 件
入力データをランダムで生成してしまうと，互いの階層数や数の増加につれてフィルタリング精度が高い傾向を示した．特使用されているラベルの種類などの比較によって，候補となりに g s の枝数もしくはラベル数が最大のときには他方の条件に得ないことが容易に確認できてしまう．そのため対象とする階関わらず 8 割以上の精度でフィルタリングされた．

層グラフは，一定の制限のもとでのランダムデータに制限して実験を行う．入力データとして，50 個 (i = 50) のデータセット
ssssss

His = (V Hi , E Hi , GHi , LHi , ϕHi , φHi ) 及び，50 個 (j = 50)
llllllのクエリー Hjl = (V Hj , E Hj , GHj , LHj , ϕHj , φHj ) を用意すls

る．階層構造の頂点数 |V Hi | は 8 個，頂点数 |V Hj | は 13 個で，グラフ集合がそれぞれ G

His= {g1s , . . . , g8s }，GHjls= {g1l , . . . , g13}と与えられている．各グラフは g1s がルートのグラフ，g2s , g3s ,g4s が 2 階層目，g5s , g6s , g7s ,g8s が 3 階層目となっている．g1l がルートのグラフ, g2l , g3l , g4l が 2 階層目，g5l , g6l , g7l ,g8l が 3 階層
llll目，g9l , g10, g11, g12, g13が 4 階層目となっている．枝・頂点ラベルの種類は {1,2,3} から {1,2,3,4,5} まで変化させ，g l , g s の頂点数をそれぞれ 100 頂点，80 頂点で固定する．また，g l の枝数は 1700 で固定させ，g s の枝数のみを 200 から 1500 まで

表 1 提案手法によるフィルタリング数及び処理時間

6. 結び

本稿では，階層グラフの行列表現を新たに提案し，グラフ分割を用いた行列サイズ縮小を図ることで，階層部分グラフ同型生判定のフィルタリング手法を示した．実験より，グラフのラベル数が多いとき，及びクエリーグラフの枝密度が大きい場合の有効性を確認した．構造の比較処理によって検索範囲を縮小する鈴木ら [8] の手法と異なり，階層グラフ全体を１つの検索対象として捉えるため，細かな組み合わせを確認せずにより簡潔なステップでフィルタリングを行うことが出来る．しかし，必然的に大規模な行列を扱わなくてはならなく，Interlace 定理の判定精度を考慮するとより小さなサイズの行列操作によって比較処理を行うことが必要になってくる．今後の課題としては，行列表現の改善や，クエリーの構造に合わせた部分構造の列挙を効率的に行う方法等が挙げられる．
文献[1] Masuda, N., Kawamura, Y. Kori, H. Impact ofhierarchical modular structure on ranking of individual nodes indirected networks. New Journal Of Physics 11, 113002 2009.
[2] 坂本和弥, 山内雅弘. 階層型グラフに対応したグラフアルゴリズ
ムの視覚的トレースツールの開発. 電子情報通信学会技術研究
報告. CST, コンカレント工学, Vol. 106, No. 368, pp. 13-18,2006-11-14.
[3] 鈴木潤, 佐々木裕, 前田英作. 階層非循環有向グラフカーネル (情報論的学習理論論文). 電子情報通信学会論文誌. D-II, 情報・システム, II-パターン処理, Vol. 88, No. 2, pp.230-240, 2005.
[4] 諏訪美佐子, 藤本克仁. グラフ表現を利用した手書き数字列のセグメンテーション方式. Technical report of IEICE. PRMU,Vol. 107, No. 491, pp. 161-166, February 2008.
[5] 和田貴久, 大野博之, 稲積宏誠. 部分構造に基づく構造類似性を用いた特徴抽出システムとその応用. The Databese Society ofJapan, Vol. 7, No. 1, pp. 187-192, June 2008.
[6] William H. haemers. Interlacing eigenvalues and graphs.
Linear Algebra and its Applications, Vol. 226-228, pp. 593616, 1995.
[7] 長屋未来, 片山薫. 部分グラフ同型判定のための 2 分法を利用した固有値比較手法. 第 19 回データ工学ワークショップ DEWS
2008, 2008.
[8] 鈴木純, 片山薫. 階層グラフ発見手法の効率化とテキスト検索への応用. DEIM Forum March 2012.
[9] J.R.Ullmann. An algorithm for subgraph isomorphism.
ACM, Vol. 23, No. 1, pp. 31-42, January 1976.
[10] L.P.Cordella, P.Foggia. An improved algorithm for matching large graphs. the 3rd IAPR TC-15 Workshop on Graphbased Representations in Pattern Recognition, pp. 149-159,
May 2001.
[11] 土井淳, 伊藤貴之. 力学モデルを用いた階層型グラフデータ画面
配置手法の改良手法とウェブサイト視覚化への応用. 芸術科学会
論文誌, Vol. 3, No. 4, pp. 250-263, 2004.
[12] Jun Sese, Mio Seki, and Mutsumi Fukuzaki. Mining networks with shared items. In Proceedings of the 19th ACM
international conference on Information and knowledge
management, CIKM ’10, pp. 1681-1684, NY, USA, 2010.
[13] Ali Shokoufandeh, Diego Macrini. Indexing HierarchicalStructures Using Graph Spectra. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No.7, July
2005.
[14] K.Katayama et al., Detecting Non-subgraphs Eﬃciently byComparing Eigenvalues of Decomposed Graphs, Vol.E95-D,No.11,pp.-, Nov. 2012.