グラフスペクトルを用いた高効率・高精度なグラフ同型性判定方法の検討

グラフスペクトルを用いた高効率・高精度な

グラフ同型性判定方法の検討

An Efficient and Accurate Graph Isomorphism Test using Graph

Spectra

大原 剛三

1∗

鷲尾 隆

1

Kouzou Ohara

1

and Takashi Washio

1

1

_{大阪大学産業科学研究所}

1

_{The Institute of Scientific and Industrial Research, Osaka University}

Abstract: Graph isomorphism test is an important and essential task for all methodologies

dealing with graphs such as graph mining, graph query, and etc. However, it is a computationally hard problem, and has been a bottleneck of various applications using graphs. In most cases, it needs the cost of O(n!). In this paper, we propose a method to check graph isomorphism using graph spectra and the other graph invariants. A graph spectrum of a graph is ordered eigenvalues of a symmetric matrix representing the graph, and is known to be invariant over any representations of an identical graph. Our method approximately checks graph isomorphism of two graphs by comparing their graph spectra as well as the other graph invariants. This approach could be more efficient compared with existing test because the computational cost of graph spectrum for an n×n symmetric matrix is O(n2_{). Through experimental evaluations, we will show the graph spectra of}

the signless Laplacian matrix of a given graph and that of the line graph of the original graph are mutually complementary, and the use of both the spectra could achieve an approximate but highly accurate and highly efficient graph isomorphism test.

1

はじめに

近年，化学や遺伝子工学，コンピュータネットワーク など様々な分野において，構造をもつデータをグラフ で表現し，計算機上で処理することへの要求が高まっ ている．それに伴い，単一，もしくは複数のグラフか ら頻出する部分グラフを網羅的に枚挙するグラフマイ ニングや，大量のグラフから目的とするグラフを高速 に検索するグラフ検索などが盛んに研究され，多くの アルゴリズムが提案されている [5, 6, 7, 8]．しかしな がら，それらのアルゴリズムを用いても，大規模なグ ラフを現実的な時間内で処理するには限界がある． その主要な原因の 1 つに，2 つのグラフが同型である か否かを判定するグラフ同型判定問題（graph isomor-phism problem）がある．多頻度グラフマイニングや グラフ検索など，グラフを用いたおおよそ全てのアプ リケーションにおいて，グラフ同型判定は必須課題と いえる．たとえば，多頻度グラフマイニングアルゴリ ズムの多くは，枚挙する多頻度部分グラフの重複を避 ∗_{連絡先：大阪大学産業科学研究所}     〒 567-0047 大阪府茨木市美穂ヶ丘 8-1      E-mail: [email protected] けるために，Canonical label と呼ばれるグラフ不変量 （graph invariant）を計算し，新たに枚挙した部分グラ フと，それまでに発見した部分グラフの同型性を判定 し，重複する候補を棄却する．しかしながら，現在ま でにグラフ同型問題を多項式時間で解くアルゴリズム は知られておらず，Canonical label の計算には，通常， n個の頂点をもつ部分グラフに対して O(n!) の計算コ ストがかかる． 以上のような背景から，本稿では，グラフ同型判定 を近似的にではあるが，高精度，かつ高効率に行う手 法について検討する．そのために，グラフ不変量の 1 つ であるグラフスペクトルに着目する [1, 3]．グラフスペ クトルは，グラフを表現する対称行列の固有値により 構成されるベクトルである．その計算コストは，n× n

の対称行列に対して O(n2) であり，Canonical label を 用いたグラフ同型判定よりも大幅に低い．実際には，同 型でない 2 つのグラフが同一のグラフスペクトルをも つ場合もあるが，複数種類のグラフスペクトルを組合 わせることで，より高精度にグラフの同型性を判定す ることが期待できる．そのため，本稿では，複数種類 のグラフスペクトル，および他のグラフ不変量を組合 人工知能学会研究会資料 SIG-DMSM-A703-07 (2/29)

わせた，より判定精度が高く，かつ高効率なグラフ同 型判定手法を検討する．具体的には，多頻度グラフマ イニングシステムに，複数種類のグラフスペクトルを 用いたグラフ同型判定手法を実装し，どのようなグラ フスペクトルの組合せが，より高精度に，かつより高 効率にグラフの同型性を判定できるかを実験的に示し， その理論背景を考察する．

2

グラフスペクトル

2.1 グラフ構造データ

グラフは頂点と頂点間を結ぶ辺により表現される．本 稿では，各頂点と辺がラベルをもつラベル付きグラフ を対象にする．いま，V を頂点 v の集合としたとき， ラベル付きグラフ G を G = (V, E, L, ϕ) と表す．ここ で，E⊆ V × V であり，E を辺集合，e ∈ E を辺と呼

ぶ．L はラベルの集合であり，ϕ は任意の v∈ V もし くは e∈ E に対して 1 つのラベルを割り付ける写像で ある．辺に向きのないグラフを無向グラフと呼び，そ の辺を{vi, vj} と書く．一方，辺に向きのあるグラフを 有向グラフと呼び，その辺を (vi, vj) と書く．グラフ G が同一の頂点ペア間に 2 つ以上の辺をもたず，かつ辺 の端点が同一頂点である自己閉路をもたない場合，G を単純グラフ（simple graph）と呼ぶ．以降では，す べてのグラフは，単純グラフであるとする． 次に，グラフの同型性を定義する．2 つの無向グラ フ，G = (V, E, L, ϕ)，G = (V, E, L, ϕ) について， {δ(vi), δ(vj)} ∈ Eであり，ϕ(vi) = ϕ(δ(vi))，ϕ(vj) = ϕ(δ(vj)) であるとき，かつそのときに限り{vi, vj} ∈ E であるような全単射 δ が存在する場合，G と G は同 型（isomorphic）であるという．有向グラフの同型性 も同様に定義できる．たとえば，図 1 中の無向グラフ G1と G2は同型であるが，G2と G3は同型ではない． これは，グラフの頂点を，グラフの ID（gid）と頂点 の ID（vid）の組 gid : vid で表現した場合，G1と G2

間には， G1: 1→ G2 : 1 G1: 2→ G2: 3 G1: 3→ G2 : 2 G1: 4→ G2: 4 という同型性の条件を満足する全単射が存在するが， G2と G3 間には，そのような全単射は存在しない為で ある．

2.2 グラフの行列表現とグラフスペクトル

グラフスペクトルは，グラフを表現する対称行列の スペクトル，すなわちその対称行列の固有値を大きさ の順に並べたベクトルとして定義される．グラフスペ 1 3 4 2 a b c d A B D C 1 2 3 4 a c b d A B C D 1 2 3 4 a c b d A B D C 1 G G2 G3 同型 同型でない A, B, C, D: 頂点ラベル a, b, c, d: 辺ラベル 1, 2, 3, 4: 頂点のID 図 1: グラフの同型性の例 クトルの計算に用いられる代表的なグラフの行列表現 としては，隣接行列（adjacency matrix）と Laplacian 行列がある [1]．グラフ G の隣接行列 A(G) とは，第 i 行（第 i 列）が頂点 viに対応し，頂点 vi と vjの間に

辺が存在する場合，その (i, j) 要素 A(G)i,jが 1，辺が

存在しない場合には 0 となる行列である．G が無向グ ラフの場合，A(G)i,jと A(G)j,iは同じ値をもつ．すな

わち，A(G) は対称行列となる．たとえば，図 1 のグラ フ G1の隣接行列 A(G1) は，以下のようになる． A(G1) = ⎛ ⎜ ⎜ ⎜ ⎝ 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 ⎞ ⎟ ⎟ ⎟ ⎠ (1) このとき，G2の隣接行列 A(G2) は， A(G2) = ⎛ ⎜ ⎜ ⎜ ⎝ 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 ⎞ ⎟ ⎟ ⎟ ⎠ (2) となり，A(G1) とは異なるが，両者は (2.00, 0.00, 0.00,−2.00) という共通のグラフスペクトルをもつ． なお，G が有向グラフの場合，viから vj への辺が

A(G)i,j成分に対応し，vjから viへの辺が A(G)j,i成

分に対応するため，A(G) は非対称行列となる．ただ し，この場合でも，  0 A(G) A(G)T ₀ という行列を考えれば，G が無向グラフの場合と同様 に G の頂点間の隣接関係を表した対称行列を得ること ができる．ここで，A(G)T _{は A(G) の転置行列を表す．} 以下では，議論を簡単化するため，一般性を失うこと なく無向グラフの場合についてのみ議論する． 一方，Laplacian 行列は，頂点数 n のグラフ G に対し て，次数行列（degree matrix）D(G)，および A(G) が

与えられた場合に，その差，D(G)− A(G) として定義 される．ここで，次数行列 D(G) は，対角成分 D(G)i,i に G 中の頂点 viの次数（degree）d(vi)，すなわち vi に接続する辺の数をもち，その他の成分はすべて 0 で あるような対角対称行列である．Laplacian 行列につい ては，その値を正規化したものなど，幾つかの種類が 提案されているが，本研究では，その中でもグラフの識 別精度が比較的高いという結果が報告 [1, 9] されている 符号なし Laplacian 行列（signless Laplacian matrix） を用いる．グラフ G に対する符号なし Laplacian 行列 S(G) は，S(G) = D(G) + A(G) と定義される．たとえ ば，図 1 の G1に対する符号なし Laplacian 行列 S(G1) は，以下のようになる． S(G1) = ⎛ ⎜ ⎜ ⎜ ⎝ 2 1 0 1 1 2 1 0 0 1 2 1 1 0 1 2 ⎞ ⎟ ⎟ ⎟ ⎠ (3) 以下では，符号なし Laplacian 行列を SLLAP と表す．

2.3 グラフスペクトルの共有性

グラフスペクトルはグラフ不変量であり，同型であ る 2 つのグラフは必ず同じグラフスペクトルをもつ．こ れは，グラフを表現する行列において，各行（列）に 対応する頂点の並びが変化しても，対称行列の性質上， その固有値が変化しないためである．しかしながら，そ の逆は成り立たない．つまり，同型でない 2 つのグラ フが同一のグラフスペクトルをもつ場合が知られてい る．グラフスペクトルだけで，どれだけ正確にグラフ の同型性を判定できるか，言い換えるなら，どれだけ の同型でないグラフが同一のグラフスペクトルを共有 するかについては，グラフ理論において半世紀にもお よぶ研究がなされており，今なお探求の対象となって いる [1, 3]． Haemers らは，頂点数 11 までのラベルなし無向グ ラフをすべて列挙し，そのグラフスペクトルを実際に 計算，比較することで，どのようなグラフスペクトル がどの程度共有されるかを調べている [1]．その結果に よると，頂点数 4 以下のグラフに関しては，隣接行列 のスペクトルによって同型性は完全に判定可能である． また，頂点数 11 のグラフであっても，GM switching と呼ばれる手法を SLLAP に適用した場合には，同型 でないの他のグラフとグラフスペクトルを共有するグ ラフの割合は，全グラフ数に対して 0.1%程度である． しかしながら，頂点数 11 のグラフの総数は約 10 億に 上り，その 0.1%は実に約 100 万個に相当することが報 告されている． これらの結果はラベルなしグラフに対するものであ ることから，実際のアプリケーションで多用されるラ ベル付きグラフの場合，頂点や辺に付されたラベルを 考慮することで，よりグラフ同型判定の精度を向上で きると考えられる．しかしながら，同時に上記の結果 は，単独のグラフスペクトルのみを用いて高精度なグ ラフ同型判定を実現するには限界があることも示唆し ている．

3

グラフスペクトルを用いたグラフ

同型判定

本節では，グラフスペクトルを用いたグラフ同型判 定について議論する．前述の通り，同型ではないが同 一のグラフスペクトルをもつ複数のグラフが存在し得 ることから，グラフ G，Gが特定の行列に対して同一 のグラフスペクトルをもつことは，両者が同型である ための必要条件に過ぎない．従って，単一のグラフス ペクトルだけを用いて正確なグラフ同型判定を実現す ることは困難である．そこで，本研究では，(1) グラフ 中の頂点・辺に付されたラベルの情報もグラフを表現 する行列に反映する，(2) 複数のグラフスペクトルの組 合せを用いる，(3) グラフスペクトル以外のグラフ不変 量も利用する，というアプローチを取る．以下，それ ぞれについて述べる．

3.1 ラベル情報の利用

本研究では，ラベル付きグラフを対象としていること から，以下では，隣接行列，および次数行列をラベルの 情報も反映できるように再定義する．そのために，写像 σV，σEを用いてグラフの頂点・辺ラベルそれぞれに，重 複なく正整数を割り当てるものとする．このとき，隣接 行列に関しては，単純に (i, j) 要素を σE(ϕ({vi, vj})) と するのではなく，辺{vi, vj} に接続する頂点 vi, vjの情 報も加味し，以下のような行列 A(G) として定義する． A_(G) i,j= σE(ϕ({vi, vj})) {vi, vj} ∈ E +σV(ϕ(vi)) +σV(ϕ(vj)) 0 otherwise (4) たとえば，図 1 中のグラフ G1に対して，σV，σEがそ れぞれ頂点ラベル A, B, C, D，および辺ラベル a, b, c, d に対して正整数 1,2,3,4 を割り当てる場合，A(G1) は 以下のようになる． A(G1) = ⎛ ⎜ ⎜ ⎜ ⎝ 0 4 0 9 4 0 7 0 0 7 0 10 9 0 10 0 ⎞ ⎟ ⎟ ⎟ ⎠ (5)

このとき，A(G1) = A(G3) であったのに対し，A(G1)= A(G3) となり，両者は行列 A(G) に対して，異なるグ

これに対し，次数行列に関しては，前述のように定 めた A(G) の各要素の値を G 中の各辺への重みと考 え，単に G 中の各頂点 v に接続する辺の総数を対角成 分とするのではなく，v に接続する辺の重みの総和を 対角成分とする行列 D(G) として，以下のように定義 する． D(G)i,j = n p=1A(G)i,p if i = j 0 otherwise (6) このとき，S(G) = D(G) + A(G) とする．A(G)，お よび S(G) は，厳密には隣接行列，SLLAP とは異な るが，本稿では，便宜上，それぞれをラベルつき無向 グラフ G に対する隣接行列，SLLAP と呼ぶ．

3.2 グラフスペクトルの組合せ

次に，グラフスペクトルの組み合わせについて考え る．符号なし Laplacian 行列，SLLAP に対して，通常の Laplacian 行列や，正規化 Laplacian 行列（normalized Laplacian）などを組合わせても，基となる隣接行列， 次数行列が同一である以上，同型性判定の精度が向上 することはあまり期待できない．そのため，本稿では， 行列としては隣接行列，および SLLAP のみを用いる 一方，対象となるグラフ G から他の種類のグラフを導 き，そのグラフに対するグラフスペクトルを利用する ことを考える．具体的には，予備実験による個別種類の グラフ，および他の種類のグラフとの組合せによるグ ラフ同型性判定の精度の高さの評価結果から，与えら れたグラフ G に対する接続グラフ（Incidence graph） [2]，および線グラフ（Line graph）[2] を用いることと した． グラフ G の接続グラフ I(G) とは，G = (V, E, L, ϕ) であるとき，以下のような頂点 VI と辺 EIをもつグラ フ (VI, EI, LI, ϕI) である． VI = V ∪ E EI = {{vi,{vi, vj}}|vi, vj∈ V, {vi, vj} ∈ E} 本研究では，EI中の辺{vi,{vi, vj}} のラベルは未定義

のままとする．このとき，A(I(G))i,jは，先の定義よ

り正整数 σV(ϕ(vi)) + σE(ϕ({vi, vj})) となる．I(G) は 直感的には，G の辺と頂点の接続関係をグラフ化した ものと考えることができ，実際には，V と E を基準に した二部グラフとなる．例として，図 2(a) に，図 1 の グラフ G1 に対する接続グラフを示す． 一方，グラフ G の線グラフ L(G) とは，以下のような 頂点 VLと辺 ELをもつグラフ (VL, EL, L, ϕL) である． VL = E EL = {{{vi, vj}, {vj, vk}}| vi, vj, vk∈ V, {vi, vj}, {vj, vk} ∈ E} a A 1 5 b B 2 6 c C 3 7 d D 4 8 1 2 3 4 B D C A a b c d (a) 接続グラフ (b) 線グラフ 図 2: G1の接続グラフと線グラフ 本研究では，EL中の辺{{{vi, vj}, {vj, vk}} のラベル に，G 中の 2 つの辺 {vi, vj}，{vj, vk} が共有する頂 点 vjのラベル ϕ(vj) を用いる．たとえば，図 2(b) は， 図 1 のグラフ G1 に対する線グラフである． これら接続グラフ，線グラフそれぞれに対しても， 元のグラフ G と同様に隣接行列，SLLAP を定義でき ることから，本研究では，A(G)，S(G)，A(I(G))，

S(I(G))，A(L(G))，S(L(G)) から得られる 6 種類の グラフスペクトルの組合せを検討する．

3.3 グラフスペクトル以外のグラフ不変量

行列固有値の計算には一定のコストを要するため，高 効率にグラフの同型性を判定するために余りにも多く のグラフスペクトルを組合わせることは好ましくない． したがって，グラフスペクトルを用いる場合の計算時 間上の利得を確保するために，本稿では，予備実験の 結果に基づき，組合わせるグラフスペクトル数の上限 を 2 個とする． 更に，2 つのグラフ G，および Gの同型性を判定す る場合，両者の頂点数が異なればこれら 2 つのグラフ は明らかに同型ではない．この場合，わざわざグラフ スペクトルを計算するまでも無く，容易に同型性を判 定可能である．同様に，グラフスペクトルを求めるよ りも容易に計算可能なグラフ不変量の値が一致しない グラフ同士に関しては，グラフスペクトルの比較をす る必要はない． 以上の事から，本稿では，より高効率なグラフ同型 性判定のために，比較的容易に計算可能である以下の 5 つのグラフ不変量について，グラフ G，Gがそれら すべてに関して同一の値をもつことを，両者のグラフ スペクトルを比較するための必要条件として用いる． • 頂点数 • 辺の数 • 頂点ラベルの最大頻度 • 頂点ラベルの平均頻度 • 頂点ラベルを表す正整数と次数の積の総和 n i=1σV(ϕ(vi))· d(vi)

これらのグラフ不変量は，対象グラフの入力と同時に 容易に計算可能なものである．最後の 1 つは，頂点を 特徴づけるグラフ不変量の線形結合である．

4

評価実験に基づく考察

4.1 実験方法

前節までに述べたグラフスペクトル，およびグラフ 不変量の比較によるグラフ同型判定法を，多頻度部分 グラフマイニングアルゴリズムに実装し，用いるグラ フスペクトルの違いによる，判定精度と実行時間の違 いを比較，評価した．具体的には，公開されているグ ラフ分類ツール gboost のパッケージ1_{に含まれる，多} 頻度部分グラフマイニングシステム gSpan[7] の C++ コードを用い，その中に提案手法を 1 つの関数として 実装した．なお，gboost は MATLAB を使うことを前 提としているが，本実験では，MATLAB は用いずに， gSpan の C++のコードのみを用いた． gSpan では，同一の多頻度部分グラフを重複して抽出 することを避けるために，DFS コードと呼ばれるコー ドをすべての部分グラフに割り当て，DFS コードが最 小である多頻度部分グラフだけを抽出する．DFS コー ドは，対象となる部分グラフをどういう手順で単一の頂 点から構成したかによって決定され，同型でない 2 つの グラフが同一の DFS コードをもつことはないが，同型 のグラフであっても異なる DFS コードをもつ場合があ る．そのため，gSpan では最小の DFS コードをグラフ に対する Canonical label とし，多頻度部分グラフの候 補を枚挙するたびに，その部分グラフの DFS コードが 最小であるか否かの判定をする．この DFS コードの最 小性判定は，新たに枚挙した部分グラフと，DFS コー ドが最小である部分グラフの同型性を判定しているこ とに等しい．DFS コードは起点となる頂点からラベル を辞書式順序を基準に深さ優先で辿ることで決められ るため，頂点数 n の部分グラフの最小 DFS コードを求 める計算の複雑さは，平均次数を d とすると O(n· dnd) となる． 一方，グラフスペクトルを用いたグラフ同型判定に より多頻度部分グラフの重複抽出を回避するためには， すでに発見した多頻度部分グラフの中に，新たに枚挙 した多頻度部分グラフの候補と同型なものが存在する か否かを判定する探索問題を解く必要がある．そのた めに本実験における実装では，gSpan において列挙さ れる多頻度部分グラフ候補を，はじめに計算コストの 低いグラフスペクトル以外のグラフ不変量で分類し，そ れらが過去に発見された多頻度部分グラフの当該不変 量と完全に一致した場合にのみ，更にグラフスペクト 1_{http://www.kyb.mpg.de/bs/people/nowozin/gboost/} 頂点数に対する ハッシュテーブル 辺の数に対する ハッシュテーブル 頂点ラベルに対する 正整数と次数の積の 総和に対するハッシュ テーブル 1種類目のグラフ スペクトルに対する 平衡二分木 2種類目のグラフ スペクトルに対する 平衡二分木 図 3: 発見済み多頻度部分グラフ分類のデータ構造 ルについても一致するか判定を行った．発見済みの多 頻度部分グラフを，そのグラフスペクトル以外の各グ ラフ不変量（スカラー値）に基づく階層的ハッシュテー ブルに格納し，その分類末端に，更にグラフスペクト ル中の各固有値の大小によって場合分けを行なう平衡 二分木を接続して分類を行なう．その概念図を図 3 に 示す． 評価実験では，gSpan の多頻度部分グラフ候補列挙 の重複判定に，頂点数が k までの多頻度部分グラフ候補 に対しては，gSpan 本来の DFS コード最小性判定関数 （以下，DFS 判定と呼ぶ）を適用し，頂点数が k +1 以上 の多頻度部分グラフ候補に対しては，上述のグラフスペ クトルによるグラフ同型判定関数（以下，GS（Graph Spectra）判定と呼ぶ）を適用した．k は 0 から 20 ま で変化させ，k の各値について，発見された多頻度部 分グラフの総数 N ，および実行時間 T を計測し，それ らの値から，以下に示す抽出率，および時間短縮率を 算出し，比較検討に用いた． （抽出率）= N N0 × 100 (%) (7) （時間短縮率）= T0− T T0 × 100 (%) (8) ここで，N0は，GS 判定を用いずに DFS 判定のみを用 いた場合に発見された多頻度部分グラフの総数であり， T0はその場合の実行時間である．N0がグラフ同型判定 が完全に正しい場合の多頻度部分グラフの総数である のに対し，N はグラフスペクトルを用いて近似的に求 めた多頻度部分グラフ数である．グラフスペクトルを 用いてグラフの同型性を判定した場合，同型ではない 2 つのグラフを同型であると判定する可能性がある．その 場合，多頻度部分グラフマイニングでは，本来，新たに 発見されるべき多頻度部分グラフが既出と判断される ため，その抽出数が正解の数よりも減少する．したがっ

92.00% 94.00% 96.00% 98.00% 100.00% 0.00% 10.00% 20.00% 30.00% 40.00% 50.00% 時間短縮率 抽出 率 A'(G) S'(G) A'(G)+S'(G) (a) 元のグラフ G を用いた比較 99.60% 99.70% 99.80% 99.90% 100.00% 0.00% 5.00% 10.00% 15.00% 20.00% 25.00% 時間短縮率 抽出 率 A'(IG)) S'(I(G)) A'(I(G))+S'(I(G)) (b) 接続グラフ I(G) を用いた比較 50.00% 60.00% 70.00% 80.00% 90.00% 100.00% 0.00% 20.00% 40.00% 60.00% 80.00% 時間短縮率 抽出 率 A'(L(G)) S'(L(G)) A'(L(G))+S'(L(G)) (c) 線グラフ L(G) を用いた比較 図 4: 隣接行列，SLLAP 及びその組合せの比較 て，必ず N ≤ N0となり，上記の抽出率は，100 に近い ほど，グラフスペクトルによるグラフ同型判定が高精度 であることを意味する．一方，時間短縮率に関しては， その値が 100 に近いほど，高効率であることを意味す る．なお，実験データとしては，National Toxicology Program の Web ページから取得できる 208 個の化合 物データを，ラベル付き無向グラフのデータに変換し て用いた [4]．

4.2 実験結果と考察

隣接行列，SLLAP 及びその組合せの比較 まず，隣接 行列と SLLAP の性能を比較するために，元のグラフ G，接続グラフ I(G)，線グラフ L(G) それぞれについ て，隣接行列，SLLAP 及びその組合せを用いた場合の 抽出率と時間短縮率を比較した．gSpan の最小支持度 を 4 とした場合の結果を，図 4 に示す．これから，グ ラフ種類に拠らず隣接行列，SLLAP いずれを用いても 50.00% 60.00% 70.00% 80.00% 90.00% 100.00% 0.00% 20.00% 40.00% 60.00% 80.00% 時間短縮率 抽出率 S'(G) S'(I(G)) S'(L(G)) 図 5: グラフ種類間の比較 その性能に大差はないか，若干，SLLAP を用いた方が 性能が良いことがわかる．また，両者を組合わせても 判定精度はほとんど向上せず，返って計算時間を要す ることから，これら 2 つの行列が相補的ではないこと がわかる．これは，SLLAP が隣接行列を基礎としてい るため，内包する情報に大きな差がない為であると考 えられる．これらの結果から，以降では，若干，性能 がよい SLLAP のみを対象に検討を進める． グラフ種類の比較 次に，元のグラフ G，接続グラフ I(G)，線グラフ L(G) それぞれを表す SLLAP を個別 に用いた場合の抽出率と時間短縮率を対比した．gSpan の最小支持度を 4 とした場合の結果を図 5 に示す．こ れから，S(G)，および S(I(G)) による結果と比較し て，S(L(G)) による結果が全体的に悪いことがわかる． これは，化合物データにおける辺ラベルの種類が少 ないことに起因すると考えられる．線グラフ L(G) の SLLAP S(L(G)) における非対角要素の値は，G 中の ある頂点 v と，v を挟んで隣接する 2 つの辺のラベルに より決定される．したがって，隣接する辺の特徴がよ り強く反映されると考えられるが，今回用いた化合物 データの辺ラベルは，原子間の結合タイプであるため， 基本的に単結合，二重結合の 2 つのタイプしかなく，そ の結果，S(L(G)) の要素がそれほど特徴的ではないも のと考えられる．これに対して，頂点ラベルは 23 種類 の元素記号を含むことから，非対角要素が 2 つの頂点 ラベルと 1 つの辺ラベルにより決まる S(G) や，1 つ の頂点ラベルと 1 つの辺ラベルによる決まる S(I(G)) からは，S(L(G)) よりも判別精度の高いグラフスペク トルが得られたものと考えられる． 特に，S(L(G)) の最低の抽出率は他の 2 つと比べて かなり低い値となっている．抽出率が最低となるのは， は，k = 0 の場合，すなわち DFS 判定を 1 度も使わず GS 判定のみを使う場合であることに注意されたい．す なわち，図 5 において，右下の領域が k の値が小さい 場合に対応し，左上の領域が k の値が大きい場合に対 応する．k の値が小さい場合，小さな部分グラフから GS 判定を適用する．したがって，小さい k に対して抽 出率が低い線グラフ L(G) は，小さな部分グラフに対 する同型性判定の精度が極めて低いことになる．これ

96.00% 97.00% 98.00% 99.00% 100.00% 0.00% 10.00% 20.00% 30.00% 40.00% 時間短縮率 抽出率 S'(G) S'(I(G)) S'(L(G)) S'(G) + S'(I(G)) S'(G) + S'(L(G)) S'(I(G)) + S'(L(G)) 図 6: SLLAP の組合わせの比較 は，頂点数，辺の数がともに少ない小さな部分グラフ に関しては，その線グラフが単純な形状になり，元の グラフの形状，ラベルの違いを十分に反映できないた めであると考えられる．なお，k の値が大きい場合に も，S(G) と同程度の抽出率を達成するには，より多 くの時間を要している．これは，線グラフを用いた場 合のグラフ同型判定精度が高くないために，同程度の 抽出率を得るためには，k の値を大きくし，より計算 時間のかかる DFS 判定の適用回数を増やさなければな らないためである． 一方，元のグラフ G と接続グラフ I(G) を比較した 場合，I(G) のほうが最低抽出率は高いが，時間短縮率 に関しては G のほうが高い．これは，頂点と辺それぞ れに対応する行と列をもつ I(G) のほうが，グラフの特 徴をより多く反映する反面，行列のサイズが G と比較 するとほぼ倍になるため，固有値計算のコストが増大 し，時間短縮率を悪化させているものと考えられる． SLLAP の組合せの比較 最後に，各種グラフに対す る SLLAP よるグラフスペクトルを組合せて用いた場 合の抽出率と時間短縮率を，gSpan の最小支持度を 4 とした場合に比較した結果を図 6 に示す．これからわ かるように，元のグラフ G に対する SLLAP（S(G)） によるグラフスペクトルと，G の線グラフ L(G) に対 する SLLAP （S(L(G))）によるグラフスペクトルの 組合せ（S(G) + S(L(G))）が，極めて高精度，かつ高 効率にグラフの同型性を判定できることがわかる．実 際には，最低抽出率は 99.90%であり，そのときの時間 短縮率は 33.01%であった．一方，S(G)，S(L(G)) そ れぞれを単独で用いた場合の抽出率，時間短縮率はそ れほど高くなく，特に S(L(G)) に関しては，前述の通 りその結果は極めて悪い． 以上のことから，これら 2 種類のグラフスペクトルの 相補性は非常に高いと言える．この理由は，S(L(G)) と S(G) の非対角要素の違いであると考えられる．S(L(G)) の非対角要素は，前述のように G 中の頂点 v と，v によ り接続される 2 つの辺のラベルにより決まる．S(L(G)) を単独で用いると，前述のように辺ラベルの種類の少 なさから判定精度は悪くなると考えられるが，2 つの 辺の接続情報は S(G) 中には内包されていないため， S(G) と組合わせることで，相補的に極めて高い判定 精度を達成するものと考えられる．これは，S(I(G)) のグラフスペクトルと S(L(G)) のグラフスペクトル の組合せ（S(I(G)) + S(L(G))）に関しても，同様に 高精度にグラフの同型性を判定できていることからも 推察される．S(I(G)) も同様に，2 つの辺の接続情報 を内包していない．なお，S(I(G)) + S(L(G)) の場合 の最低抽出率は，99.97%であり，S(G) + S(L(G)) の それよりも高いが，時間短縮率は最高でも 22.84%と， S(G) + S(L(G)) の場合よりもかなり低くい．これは， 前述のように，接続グラフに対する行列のサイズが元 のグラフと比較して大きく，固有値計算コストが高い ためである． また，S(G) によるグラフスペクトルと，S(I(G)) によるグラフスペクトルの組合せは，S(I(G)) 単独の 場合と比較して抽出率の向上は見られず，時間短縮率 のみが悪化している．これは，これら 2 種類のグラフ スペクトル間の相補性が低く，2 種類のグラフスペクト ルの固有値計算コストだけが増大した為である．S(G) と S(I(G)) のいずれもが，G 中の辺とそれに接続する 1 つ，もしくは 2 つの頂点の情報という類似した特徴 を反映するため，相補性が低いと考えられる． 以上の実験結果から，少なくとも GS 判定を gSpan に組み込み National Toxicology Program に適用した 限りでは，線グラフ L(G) の SLLAP によるグラフス ペクトルは，元のグラフ G の SLLAP，および G の接 続グラフ I(G) の SLLAP から得られるグラフスペクト ルそれぞれと相補的であり，特に G の SLLAP による グラフスペクトルと組合わせることにより，グラフの 同型性を高精度，かつ高効率に判定できることが明ら かとなった．

5

おわりに

本稿では，グラフスペクトルを用いた高効率，高精 度なグラフ同型判定について検討した．グラフスペク トルは他のグラフ不変量に比べ，グラフの形状情報を より多く反映しているため，複数種類のグラフスペク トルを組合わせて使うことで，完全ではないが，高精 度にグラフの同型性を判定できる．本稿では，ラベル 付き無向グラフを対象に，元のグラフ，およびその接 続グラフ，線グラフそれぞれに対する隣接行列，符号 なし Laplacian 行列を用い，元のグラフと線グラフの 符号なし Laplacian 行列によるグラフスペクトルの相 補性が極めて高く，高効率，高精度にグラフの同型性 が判定可能であることを実験的に示し，その要因につ いて考察した． 今後の課題としては，今回得られた実験結果の理論 的分析，および幅広いデータでの検証が必要である．ま

た，他のグラフ同型判定手法との比較実験も，今後，進 める予定である．

謝辞

本稿における実験では，ドイツ Max Planck Institute for Biological Cybernetics の Koji Tsuda，Sebastian Nowozin 両氏により公開されている gboost パッケー ジに含まれる，Taku Kudo 氏（Google Japan）による gSpan の C++のソースコードを利用させていただい た．ここに，感謝する．

また，本研究の一部は文部科学省科学研究費補助金 による．

参考文献

[1] E. R. van Dam and W. H. Haemers: “Which graphs are determined by their spectrum?”, Linear Algebra and its Applications, Vol.373, pp.241–272 (2003). [2] C. Godsil and G. Royle: Algebraic Graph Theory,

Springer(2001).

[3] L. Hogben: “Spectral Graph Theory and the Inverse Eigenvalue Problem of a Graph”, Electronic Journal of Linear Algebra, Vol.14, pp.12-31 (2005).

[4] A. Inokuchi, T. Washio, and H. Motoda: “An Apriori-Based Algorithm for Mining Frequent Sub-structures from Graph Data”, Proc. of PKDD 2000, pp.13–23 (2000).

[5] T. Washio and H. Motoda: ”State of the art of graph-based data mining”, SIGKDD Explorations Vol.5, No.1, pp.59–68 (2003).

[6] T. Washio, L. De Raedt, J. N. Kok: “Advances in Mining Graphs, Trees and Sequences”, Fundam. In-form. Vol.66, No.1-2 (2005).

[7] X. Yan and J. Han: “gSpan: Graph-based substruc-ture pattern mining”, Proc. of ICDM, pp.721–724 (2002).

[8] X. Yan, P. S. Yu, and J. Han: “Substructure Sim-ilarity Search in Graph Databases”, Proc. of 2005 ACM-SIGMOD, pp.766–777 (2005).

[9] P. Zhu and R. C. Wilson: “A Study of Graph Spectra for Comparing Graphs”, Electronic Proc. of British Machine Vision Conference 2005, http://cms.brookes.ac.uk/staff/PhilipTorr/ BMVC2005/papers/162/bmvc2005b.pdf (2005).