DEIM Forum 2016 D2-1

Star 編集距離を用いたグラフ分類学習
塩月 英美†

猪口 明博†† 関西学院大学理工学部情報科学科 〒 669–1337 兵庫県三田市学園 2-1
E-mail: †{bkd96395,inokuchi}@kwansei.ac.jp
あらまし

グラフ編集距離を解く問題は NP 困難であるため，本稿ではグラフ編集距離を近似的に求めるグラフ

Mapping 距離を用いた，グラフ編集距離カーネルを提案する．グラフ Mapping 距離が同じであってもグラフの大きさによって類似度が異なることに着目したうえで，カーネル関数を提案する．一方，既存手法では，事前に設定したパターンに従って対象グラフをベクトル化し，ベクトルを用いて類似度が計算されるため，類似するパターンを含む
２つのグラフの類似度は必ずしも高くはならない．このため，提案手法は， 2 つのグラフの類似度をより正確に測ることができ，グラフ分類問題において高い分類精度になる．
キーワード

グラフマイニング，分類問題，Support Vector Machine，グラフカーネル，グラフ編集距離

1. は じ め に

ラフ同型問題は NP 完全 [2] であるため，この手法は効率的ではない．そこで，提案手法では，パターンを用いずに，グラフ

データマイニングとは，大量のデータを解析することで有用間類似度を測るグラフ編集距離に基づくカーネル関数を提案すな情報を発見することである．解析手法は頻出パターンマイニ

る．本研究の目的は，サポートベクターマシンとカーネル関数

ングやクラスタリングなど多数存在し，入力データの形式やを用いてクラス分類を行い，その分類精度を既存の手法よりも出力したい結果に応じて，適した解析手法が用いられる．解析向上させることである．また，2 種類のテストデータを用いてデータの形式は様々であり，グラフ構造で表現されているデー

提案手法の評価を行う．

タもその一つである．グラフで表現できるデータは多くあり，

本稿の構成は以下の通りである．2 節では，既存の 3 種類の

例えば，道路や鉄道のネットワークや化学分野の分子構造であ

グラフカーネルについての概要を述べる．3 節では，グラフ編

る．分子構造の場合は原子を頂点，結合を辺としてグラフ構造

集距離を近似的に求めたグラフ Mapping 距離の概要を示し，として捉えられる．このようなグラフ構造で表現されたデータ

グラフ編集距離カーネルを提案する．4 節では，カーネル関数

を解析することをグラフマイニングと言う．

の半正定値性について述べる．5 節では，既存手法との分類精グラフ構造は，頂点と，二つの頂点を結ぶ辺から成り立つ．
グラフには辺に方向がない無向グラフと辺に方向がある有向グ
ラフに区別できる．無向グラフは化合物や鉄道の路線図などを表現するときに用いられる．一方で，有向グラフは，インター度を比較することで提案手法の評価実験を行い，その結果と考察をまとめる．6 節で本研究の結論を述べる．

2. グラフカーネル

ネットの Web ページとそのページからのリンク先を表現でき

本研究では，グラフ分類問題を扱う．あるグラフ gi に対しる．Web ページの場合，リンクが双方向でなく，一方向のみでて，クラス yi ∈ {−1, +1} が定められている．各クラスラベルあるので，有向グラフで表現する必要がある．

からクラスを分類する関数を学習し，クラスラベルが未知であ

上記で示した例以外でもデータをグラフとして扱うことのでるデータに対してクラスラベルを予測する．グラフ分類問題をきる分野は他にもあり，グラフマイニングは幅広い分野で適応解くためには，Support Vector Machine (SVM) とグラフカー

されている．特に，化合物が持つ性質や化学的特徴は，化合物ネルを用いる．本節では，既存のグラフカーネルである，近傍の構造に依存すると知られている．化合物に含まれる原子の種

ハッシュカーネル [3]，Weisfeiler-Lehman 部分木カーネル [4]，類や，原子間を結ぶ結合の種類，およびそれらが構成する構造

縮約アダマール符号カーネル [5] の 3 種類のグラフカーネルに的な特徴を用いて化合物の類似度を測ることができれば，性質ついて述べる．

が既知の化合物データから傾向を学習し，性質が未知の化合物の性質を予測できるようになる．

本稿で扱うグラフとは，自己ループ，多重辺，辺ラベルを含まない無向グラフを指し，グラフを g = (V, E, Σ, l) で定義す

本研究では，グラフ表現されているデータの分類問題についる．ここで，V は頂点集合，E は E ⊂=V × V を満たす 辺集合，て検討する．文献 [1] では，あらかじめ決めておいたパターン

l は頂点ラベル集合を Σ としたとき，l : V → Σ なる頂点ラベに従って，対象グラフをベクトル化し，そのベクトル同士の比ルを定める関数である．3 つの既存カーネルは，任意の 2 つの較によってグラフの類似度を測る手法が述べられている．しかグラフ gi と gj の類似度を測り，それをグラフカーネルの戻り

し，この手法では，パターンが対象グラフに部分グラフとして値とする．ある頂点 v のラベル l(v) と，v に隣接する頂点に含まれているか否かの二値で判断しているため，パターンと少対する頂点ラベルの多重集合 L(N (v)) を引数として，頂点 v

しでも異なれば，含まれていないと判断される．また，部分グを新しいラベルに書き換える relabel という操作を複数回繰り返すことによって，頂点 v を特徴付け，グラフ間の類似度を測

ηϬϭϭ

ηϭϬϭ

る．relabel を r 回繰り返すと，頂点 v から r ステップで到達可能な頂点までを考慮して頂点 v のラベルを定めていることになる．つまり，頂点 v から r ステップで到達可能な頂点までの

ηϬϭϭ

ηϬϬϭ

ηϬϬϭ

ηϭϬϬ

部分グラフとして捉えることで，部分グラフ同士の類似度を計㼞㼑㼘㼍㼎㼑㼘

ηϭϬϭ

ηϭϬϬ

ηϭϬϬ

ηϬϬϭ

算し，それをグラフ全体に拡張させてグラフ間の類似度を求めている．この relabel の操作方法が各カーネルで異なっており，
以下で relabel の手法と各カーネルの特徴を述べる．

2. 1 近傍ハッシュカーネル
(a)

近傍ハッシュカーネル (Neighbourhood Hash Kernel: NHK)とは，グラフの各頂点ラベルを長さ L の固定長ビット列を用いて表現する．NHK の場合，頂点 v の relabel を r 回適用した

ηϬϭϭ; Ϳ(r)
ときのラベルを定める関数 lN (v) は，以下で定義される．


(r)

(r−1)

lN (v) = ROT (lN(v)) ⊕ 



⊕

(r−1)

lN

ZKd
ηϭϭϬ(u)

ηϬϭϭ; ͿηϬϬϭ; ͿηϬϬϭ; Ϳ
ηϬϭϭ

(1)

ηϭϭϬ
ηϬϭϭ
ηϭϬϭ

(b)

u∈N (v)

図 1 NHK の relabel の動作例

ここで，ROT は，ビット回転を意味する．ビット回転とは，ビット列の先頭ビットを一番最後に移動させる操作である．ま⊕た，⊕ は，ビット演算の排他的論理和であり， は，排他的論

2. 2 Weisfeiler-Lehman 部分木カーネル
Weisfeiler-Lehman 部 分 木 カ ー ネ ル (Weisfeiler-Lehman
Subtree Kernel: WLSK) は，Weisfeiler-Lehman アルゴリズ

理和の総和を表している．
実際の動作例を図 1 を用いて説明する．頂点数 |V | = 5，頂ム [6] に基づくグラフカーネルであり，グラフの各頂点ラベルの状態かを文字列で表現する．WLSK の場合，頂点 v の relabel を r 回

ら 1 回 relabel を行った場合の動作例を示している．また，図したときのラベルを定める関数 lW (v) は，以下の通り定義さ

1(b) は，v2 を例として，relabel を行う関数 lN の手順を表しれる．

点ラベルのビット列長 L = 3 とする．図 1(a) は，g(s)ている．まず，v2 の ROT を計算する．次に v2 に隣接する頂点 v1 , v3 , v5 のラベルの排他的論理和を取る．最後に 2 つの演
算結果の排他的論理和が v2 の新しい頂点ラベルとなる．
この手法の特徴として，relabel の演算で用いられる排他的

(r)



⊙



(r)
(r−1)
(r−1)
lW (v) = lW (v) · lW (u)
u∈N (v)(4)⊙
この式の · は文字列の連結を意味し， は，式の条件を満たす
頂点ラベルを全て連結させることを表している．

論理和は，交換法則が成立するので，ある頂点 vi に隣接する

上式に従って，relabel を行うと図 2 で示す動作をする．NHK

頂点の頂点ラベルをソートする必要がないことが挙げられる．

の場合と同様に，頂点数は 5 とする．relabel 前の状態が図の

また，演算の前後でビット数は変わらないので何回 relabel を

g (s) の場合，各頂点に隣接する頂点の頂点ラベル集合の要素を行っても頂点ラベルは L ビットである．しかし，relabel 前のソートする．それが表 1 の青い字で示されている．それをもと隣接頂点集合のラベルが異なっていても，relabel 後の頂点ラベのラベル (表の赤い字) と連結させ，各頂点の新しい頂点ラベル

ルが同一になってしまう場合がある．これをハッシュの衝突ととなる．NHK と異なる点は，隣接頂点の頂点ラベルの集合が呼び，NHK の欠点である．

同じである v3 と v5 のみ，relabel 後も同じ頂点ラベルになって近傍ハッシュカーネルのカーネル関数では，Jaccard 係数が用いられる．これを任意の 2 つのグラフ gi と gj のカーネル関数に適応すると，連結を内部に含むところである．したがって，ここでは，あるc(gi , gj )|Vi | + |Vj | − c(gi , gj )(2)である．ただし，c(gi , gj ) は gi と gj の両方に共通している頂点ラベルの数を指す．s 回の relabel を行った i 番目のグラフを(s)とすると，relabel を r 回行ったときの近傍ハッシュカーネ(r)

ルのカーネル関数 KN HK (gi , gj ) は式 (3) となる．
(r)の頂点も異なっている．

WLSK と NHK の相違点は，交換法則が成立しない文字列のK(gi , gj ) =gi

いるが，他の点は隣接する頂点がそれぞれ違うので relabel 後

KN HK (gi , gj ) =

r
1∑

r s=0

頂点 vi の隣接する頂点の頂点ラベルの多重集合 L(N (vi )) を，
アルファベット順にソートして，ラベルの連結を行う．NHKの場合は，relabel を行うと，それまでのステップの情報を保持していなかったが，WLSK では，relabel を繰り返せば繰り返
すほど，頂点ラベルの文字列の長さは長くなり，また，ある頂点から r ステップ後にある頂点ラベルの情報を保持しているので表現力が高い．しかし，relabel を行う度に頂点ラベルの多重

(s)

(s)

K(gi , gj )(3)

集合 L(N (vi )) の要素をソートする必要があるため，計算量がNHK よりも多くなる．
relabel を r 回行ったときの Weisfeiler-Lehman 部分木カー







㼞㼑㼘㼍㼎㼑㼘

;Ϯ͕Ϯ͕Ϯ͕ϮͿ;ϭ͕ϭ͕ϭ͕ϭͿ







;ϭ͕ϭ͕ϭ͕ϭͿ

;ϭ͕Ͳϭ͕ϭ͕ͲϭͿ;ϰ͕Ϭ͕ϰ͕ϬͿ

;ϰ͕ͲϮ͕Ϯ͕ϬͿ㼞㼑㼘㼍㼎㼑㼘








;ϭ͕Ͳϭ͕ϭ͕ͲϭͿ

図 2 WLSK の relabel の動作例

;ϭ͕Ͳϭ͕Ͳϭ͕ϭͿ

;ϰ͕ͲϮ͕Ϯ͕ϬͿ(a)

表 1 WLSK の場合の relabel 前後の頂点ラベル

頂点に隣接するϰḟ䜴䜷䝹䝅䝳䞉䜰䝎䝬䞊䝹⾜ิ頂点 頂点ラベル 頂点集合の(s)lW

連結後の頂点ラベル(s+1)

ラベルをソートし，lWн

連結したもの

v1

A

A

AA

v2

A

ABB

AABB

v3

B

ABC

BABC

v4

C

BB

CBB

v5

B

ABC

BABC

;ϯ͕Ͳϯ͕ϭ͕ͲϭͿ;ϭ͕ ϭ͕ϭ͕ ϭͿ
;ϭ͕ ϭ͕ϭ͕ ϭͿ
;ϭ͕Ͳϭ͕ϭ͕ͲϭͿ
;ϭ͕Ͳϭ͕ϭ͕ͲϭͿ
;ϰ͕Ϭ͕ϰ͕ ϬͿ(b)
図 3 HCK の relabel の動作例

(r)

(r−1)

lH (v) = lH

∑

(v) +

(r−1)

lH

(u)

(8)

u∈N (v)

上式に従って，relabel を行うと HCK は図 3 で示す動作をす(r)
ネルのカーネル関数 KW LSK (gi , gj ) は，以下の式 (5) によってる．NHK，WLSK の場合と同様に，頂点数は 5 とする．ここ定義される．

では，4 次のウォルシュ・アダマール行列 H4 を用い，頂点ラベ(r)
KW LSK (gi , gj ) =

r
1∑

r s=0

ルは H4 の各行のベクトルのうちのいずれかとなっている．H4(s)(s)
K(gi , gj )(5)

は図 3(b) に示されている行列である．

HCK の場合の頂点ラベルの更新は，隣接する頂点ラベルと2. 3 アダマール符号カーネル

なっているベクトルとの和を取る．例えば v2 を例として説明

今まで述べた NHK や WLSK の短所である，ハッシュの衝突

すると，頂点 v2 の頂点ラベルと，その隣接する頂点 v1 , v3 , v5や計算量の多さを克服するために，考えられたのがアダマールの頂点ラベルのベクトルの和を求め，その結果が relabel 後の符号カーネル (Hadamard Code Kernel: HCK) である．HCK

v2 の頂点ラベルとなる．WLSK と同様，隣接頂点の頂点ラベの場合の relabel の動作の説明の前に，アダマール符号についルの集合が同じである v3 と v5 のみ，relabel 後も同じ頂点ラて述べる．

ベルになっているが他の点は隣接する頂点がそれぞれ違うのでアダマール符号は，ウォルシュ・アダマール行列の各行ベク

relabel 後の頂点も異なっている．

トルのことである．ウォルシュ・アダマール行列とは行列内の

この図 3 では頂点ラベルがベクトルで表記されているが実際全ての要素が 1 もしくは −1 であり，任意の 2 行のベクトルのには 2 進数でメモリに格納される．NHK を用いた場合よりも内積が 0 になる正方行列である．例えば，2 次のウォルシュ・

HCK を用いた方が，頂点ラベルのビット数が多くなってしまkアダマール行列は式 (6) で，s 次のウォルシュ・アダマール行う．そこで HCK の場合と同等の記憶量で頂点ラベルを割り当て

列は式 (7) で定義される．
(
1
H2 =
1

られるように考えられたものが，縮約アダマール符号カーネル

(
H2k =

1

)

(Shortened Hadamard Code Kernel: SHCK) である．SHCK(6)−1の概念を説明する．ウォルシュ・アダマール行列 H の特徴として，第 1 列目以外の全ての要素は，−1 と 1 が同じ数ずつある．

H2k−1

H2k−1

H2k−1

−H2k−1)

従って，各頂点ラベルの出現確率が同じであるとすると，各頂(7)点ラベルの 2 番目以降の要素は −1 もしくは 1 が確率 21 の二項分布に従う．つまり，H の第 1 列目以外の要素の平均は 0 とな

ここから HCK の場合の relabel の動作の概要を述べる．グ⌈log |Σ|⌉

ラフの各頂点ラベルの集合を Σ としたとき，2る．よって，ラベル l の 2 番目以降の要素に対して大きな記憶次のウォ量を与える必要はなく，その部分を縮約する．縮約する各要素

ルシュ・アダマール行列を H を用いる．そしてグラフの各頂を ρ ビットの 2 進数表記に置き換え，全体として，NHK の場

点の初期ラベルを |H| 次のアダマール符号とする．頂点 v の合の頂点ラベルのビット数 L と同等にすることが可能である．

(r)relabel を r 回したときのラベルを定める関数 lH (v) は以下で

なお，SHCK の relabel 演算は HCK の場合と同様である．

求められる．

縮約アダマール符号カーネルのカーネル関数は，任意の 2 つのグラフを gi と gj とし，NHK のカーネル関数と同様，Jac-

 vϮ

 vϮ

card 係数を用いる．式 (2) から K(gi , gj ) を求め，relabel を r回行ったときの縮約アダマール符号カーネルのカーネル関数
(r)

(r)

KSHCK (gi , gj ) =

r
1∑

r s=0

(s)

(s)

K(gi , gj )




 vϭ

KSHCK (gi , gj ) は，

vϯ

(9)

近似的に求めるグラフ Mapping 距離の概要を示し，グラフ編
集距離カーネルを提案する．
グラフ gi と gj のグラフ編集距離 λ(gi , gj ) を，以下に定義

vϯ

vϰ 

 vϱ

3. グラフ編集距離カーネル
本節では，グラフ編集距離 [7] の概要と，グラフ編集距離を

 vϭ

vϰ 

図4

定義 2 (Star 編集距離)

グラフ編集距離の例

Star Structure si と sj の Star 編集

距離 λ(si , sj ) は，λ(si , sj ) = T (ri , rj ) + d(Li , Lj ) + M (Li , Lj )

(10)

する．
定義 1 (グラフ編集距離) グラフ編集距離は 2 つのグラフ giと gj において，グラフ gi を gj に書き換える場合に必要となる最少の編集操作の数で定義される．ここで，グラフにおける編集操作とは，以下の 3 つの操作を指す．

となる．このとき，T (ri , rj ) と d(Li , Lj ) と M (Li , Lj ) は以下の式から求められる．
{0 l(ri ) = l(rj ) のとき
T (ri , rj ) =1 上記以外のとき(11)(1) 頂点や辺の追加

d(Li , Lj ) = |Li | − |Lj |(12)(2) 頂点や辺の削除

M (Li , Lj ) = max{|ΨLi |, |ΨLj |} − |ΨLi ∩ ΨLj |(13)(3) 頂点ラベルの変更■

また，編集操作の系列をアライメントと呼ぶ．ただし，頂点の削除は，削除の対象である頂点から辺が出ていない場合のみ削除可能とする．■λ(si , sj ) は，si の根と sj の根が対応するときの si と sj の編集距離である．T (ri , rj ) では，根 ri と rj のラベルが異なるとこの 3 つの操作に必要となるコストはすべて等しいものとする．

きに 1 を，それ以外のときに 0 を頂点ラベルの変更のための編

また，ε を仮想の頂点とするとき，頂点の削除は，σ ∈ Σ から集距離として加算する．また，d(Li , Lj ) では根 ri に隣接する

ε への頂点ラベルの変更と等価であるとする．同様に，頂点の辺数と根 rj に隣接する辺数との差を辺の追加，あるいは削除

追加は，ε から σ への頂点ラベルの変更と等価である．グラフのための編集距離として加算する．さらに，M (Li , Lj ) では根

編集距離の値が小さいほど，その二つのグラフは類似している

ri に隣接する頂点ラベル集合 ΨLi と根 rj に隣接する頂点ラベことを意味する．図 4 を用いて gi と gj のグラフ編集距離を求

ル集合 ΨLj を比べ，この異なりの程度を頂点ラベルの変更のめる．gi から gj に書き換える場合，少なくとも頂点 v4 のラベ

ための編集距離として加算する．Star 編集距離はこれらの編集

ルの変更，頂点 v3 と v5 を結ぶ辺の削除，頂点 v5 の削除の 3

距離の和で定義される．

つの操作が必要なので，グラフ編集距離 λ(gi , gj ) = 3 となる．

次に，2 つのグラフ gi と gj における，それぞれの Star Struc-

しかし，グラフ編集距離を求める問題は NP 困難である．そこ

ture 集合 S(gi ) と S(gj ) の距離 ζ(S(gi ), S(gj )) を Star 編集距

で，グラフ編集距離を近似的に求めたものが，グラフ Mapping

離を用いて定義する．そして，その定義を用いて，グラフ間の距離である．

距離であるグラフ Mapping 距離 µ(gi , gj ) について述べる．

グラフ Mapping 距離を求めるためには，Star Structure と呼Star Structure 集合 S(gi ) と S(gj ) において，各集合の要素

ばれる，対象グラフの部分グラフが用いられる．Star Structure数が等しくない場合は，仮想の頂点 ε を追加して要素数が同一はある頂点 v と v に隣接する頂点集合のみで構成され，Starになるようにする．2 つの集合間に P : S(gi ) → S(gj ) なる全Structure を s = (r, L, l) で定義する．r は根となる頂点，L は単射が存在するとき，Star Structure 集合間の距離を Mapping

葉となる r に隣接する頂点集合，l は頂点ラベルを定める関数

距離と言い，Mapping 距離 ζ(S(gi ), S(gj )) は，式 (14) で定義である．L に含まれる頂点間には辺を含まない．グラフ g のされる．

全ての頂点 v に対して Star Structure を構成することができ，頂点数が n のグラフから n 個の Star Structure を生成可能である．グラフの i 番目の頂点 vi を根とすると，Star Structureは si = (vi , Li , l) となり，グラフ g から生成される全ての Star

Structure の集合を S(g) と表記する．
Star 編集距離とは，2 つの Star Structure 間の編集距離のことであり以下で定義される．

ζ(S(gi ), S(gj )) = minP∑λ(sk , P (sk ))(14)

sk ∈S(gi )S(gi ) に 含 ま れ る Star Structure と S(gj ) に 含 ま れ る Star
Structure に対し，Star Structure 集合間全体としての重みが最小となるようにマッチングを行い，その最小重みを Star

Structure 集合間の距離 (Mapping 距離) としている．ここでの重みとは，マッチングした 2 つの Star Structure 間の編集距離

 vϭ

vϮ 

 vϭ

vϮ 

 vϭ

 vϯ

vϰ 

 vϯ

vϰ 

 vϯ

vϮ 

 vϭ

vϮ 

 vϯ

(a)
 vϱ

vϱ

 vϭ

vϮ 

 vϭ

vϮ 

 vϯ

vϰ 

 vϯ

vϰ 

 vϱ

vϲ 

 vϱ

vϲ 

(a)












vϯ

vϭ

vϮ

vϯ

vϭ

vϮ













vϭ

vϮ

vϰ

vϭ

vϮ

vϰ









vϭ

vϯ

vϰ

 vϮ


vϭ


vϯ

vϰ













(b)

vϯ

vϰ

vϮ

vϯ

vϰ

vϮ

図 6 類似度の違いの例





vϯ

vϱ
^;

vϱ
^;

Ϳ

g2 ，(b) に示した g3 と g4 はどちらも 1 箇所の頂点ラベルのみ

Ϳが異なっているので µ(g1 , g2 ) と µ(g3 , g4 ) の値は等しい．しか(b)
図5

し，グラフ全体の頂点数を比較すると，g3 と g4 の方が g1 と g2グラフ間の Star Structure マッチング

よりも多いため，類似度は g3 と g4 の方が高いと言える．このである．図 5 のように，このマッチング問題は，二部グラフにような場合に，g3 と g4 の方がより類似していることを値に反おけるマッチング問題と同じである．この図 5(a) の g1 と g2 は映させた，式 (16) をグラフ編集距離カーネルとして提案する．

グラフの頂点数が違うため，g2 に ε を追加して頂点数を同じにしている．そして g1 と g2 の各頂点を根とした Star Structure

KGEDK (gi , gj ) = 1 −を図 5(b) に示す．各 Star Structure 同士の組み合わせは黒の点線で示した 25 通りあり，Star Structure 間のマッチングは

5! 通り存在する．そのうち編集距離の総和が最小となるときのマッチングは赤い矢印で示した組み合わせとなり，このときのµ(gi , gj )|Vi | + |Vj | + |Ei | + |Ej |(16)

グラフ間類似度 µ(gi , gj ) は，2 つのグラフが類似している場合には 0 に近い値を返すのに対し，SVM に適応するグラフカー
ネルには，2 つのグラフが類似している場合にはより大きい値を与えなければならない．そのために，式 (16) では µ(gi , gj )編集距離の総和が ζ(S(g1 ), S(g2 )) である．
この二部グラフのマッチング問題は，S(g1 ) に含まれる i 番目の Star Structure と S(g2 ) に含まれる j 番目の Star Structureを正規化し，1 から引いている．

4. カーネル関数の半正定値性についての編集距離を引数として，Hungarian アルゴリズムを用いて解かれる．このアルゴリズムは Star Structure 集合の要素数が nなければならない．カーネル関数が半正定値性を満たすことは，のとき，O(n3 ) で計算可能である．

Star Structure 間の最小重みを用いて，グラフ間の類似度をグ ラ フ gi と gj の グ ラ フ

Mapping 距離 µ(gi , gj ) は，µ(gi , gj ) = ζ(S(gi ), S(gj ))カーネル行列の固有値が全て非負であることと等価である．
グラフ編集距離カーネル KGEDK (gi , gj ) で構成したカーネ測るグラフ Mapping 距離は以下の式で定義される．
定義 3 (グラフ Mapping 距離)

一般的に SVM に用いるカーネル関数は半正定値性を満たさ

ル行列の半正定値性について検証してみると，固有値に負の数を含むことから，KGEDK (gi , gj ) は半正定値性を満たしていな
い．しかし，文献 [8] によると，カーネル関数を SVM に適応する場合など，例外的に半正定値性を満たさないことがあると(15)■

SVM を用いて対象データをクラスに分類するために，式 (15)で定義されるグラフ Mapping 距離をグラフカーネルに適応す
る．そのとき，グラフの大きさに着目した．グラフ間類似度µ(gi , gj ) の値が同じでも，比べるグラフによって，より類似度が高い場合と低い場合がある．例えば図 6 の (a) に示した g1 と知られている．カーネル行列における負の固有値の数が多い場
合は，データの学習が困難となり分類精度が伴わないことがあるが，SVM を利用する場合，負の固有値の数が少なければ適切に判別される．

,
,

,


༢⤖ྜ䜢ďϭ
஧㔜⤖ྜ䜢ďϮ





,

,

,
ďϮ



r · · · 原子，結合

ďϭ

ďϭ

,

,

図7

表 2 MUTAG を用いた分類精度 (%)

ďϭ

ďϭ

GK

90.96

93.62

92.55

93.62

88.30

90.96

90.96

93.62

La = 1r · · · 原子，結合

辺ラベルの除去GEDK

La = 2r · · · 原子
La = 1r · · · 原子
La = 2᰿ƌ

表 3 ENZYMES を用いた分類精度 (%)

r · · · 原子，結合

図 8 各 La に対する L の変化

GEDK

GK

52.00

61.66

46.33

65.33

39.00

46.83

50.17

62.67

La = 1r · · · 原子，結合5. 評 価 実 験La = 2

5. 1 実 験 設 定

r · · · 原子

3 節で提案したグラフ編集距離カーネル (GEDK) の分類精La = 1

度を評価するために 2 種類のデータセットを用いる．1 つは

r · · · 原子

MUTAG [9] というデータセットで，188 個の化合物サンプル

La = 2に対して変異原性の有無の情報が含まれている．このデータセットに含まれる化合物の原子数や結合の種類は様々である．

MUTAG は，辺にラベルを持つが，グラフ Mapping 距離を求めるアルゴリズムでは，グラフの辺にラベルがないものを対象としているので，図 7 に従って辺ラベルを除去し，結合の種類ごとに頂点ラベルを割り当て，辺にラベルがないグラフとして評価実験を行う [3]．また，3 つ以上のグループに分類される化
合物データとして，酵素番号が記されたタンパク質の三次構造のデータ ENZYMES [10] を利用する．600 個のタンパク質に対し，1 から 6 までの 6 種類の酵素番号がクラスとして割り当
てられている．
評価実験では，まず，GEDK と，代表的なカーネル関数であるガウシアンカーネル (Gaussian Kernel: GK) を用いた場合を比較する．ただし，ガウシアンカーネルは式 (17) で定義される．GK は式 (17) における ||xi − xj ||2 をグラフ Mapping
距離 µ(gi , gj ) とした以下の式 (18) で定義される．

K(xi , xj ) = exp −||xi − xj ||2σ2KG (gi , gj ) = exp −σ2



集合を L とした．図 8 に La を変化させたときの具体例を示す．

5. 2 実 験 結 果
表 2 にデータセットとして MUTAG を用いた場合の精度の結果，表 3 にデータセットとして ENZYMES を用いた場合の精度の結果を示す．ただし，これらの GK の値は，パラメー
ター σ を 1 から 30 まで 1 刻みで変化させ，最も高い分類精度が得られたときのものである．
次に，3 節で述べた既存手法である，NHK と WLSK とSHCK の 3 種のグラフカーネルと，提案手法の GEDK の分類
精度の比較を行った．MUTAG を用いた場合の結果を表 4 に，

ENZYMES を用いた場合の結果を表 5 に示す．SHCK のパラ
メーター ρ を 1 から 4 まで変化させた．また，図 9 と図 10 は，

GEDK は既存手法の GK にグラフ編集距離の近似値を用い(17)た場合, 条件によっては同等の精度が得られた．MUTAG で評価した場合，根 r は原子と結合，La = 2 としたときが最も精µ(gi , gj )プでたどり着ける，r に隣接する頂点とその更に隣りの頂点のそれぞれの結果をグラフで表したものである．



点のみの集合を L とした．La = 2 の場合は，r から 2 ステッ

度が高く，GK の精度とほぼ同じである．ENZYMES で評価(18)

した場合は，GK に比べて少し精度は劣るが，r は原子と結合部分の両方，La = 1 のときに，比較的高い精度が得られた．ままた，GEDK と GK の分類精度を比較するだけでなく，グラフ Mapping 距離を計算するときに Star Structure として扱

た，MUTAG の結果からは，Star Structure として与える範囲

La が大きい方が高い精度が得られやすく，根 r に原子と結合う範囲を変化させて比較した．変更した点は，Star Structure

部分の両方が設定されている場合の方が精度は高い．しかし，の根 r で扱う頂点の種類と，r に隣接する頂点集合 L の範囲 LaENZYMES を用いた場合はそのような傾向は見られなかった．

の 2 点である．r に設定する頂点を化合物の原子のみの場合と，原子と結合部分の両方の場合の，2 つに分けた．また，La = 1の場合は，r から 1 ステップでたどり着ける，r に隣接する頂3 種の既存手法 (NHK，WLSK，SHCK) と GEDK の精度を比べると，MUTAG で，いずれの既存手法よりも，GEDK表 4 MUTAG を用いた場合のϵϰ͘ϬϬ

NHK, WLSK, SHCK と GEDK の分類精度 (%)

2

NHK

83.51

82.45

WLSK

82.45

80.85

1

82.98

85.11

2

82.98

82.98

3

82.45

80.85

4

82.45

80.85

原子 90.96

92.55

ϵϬ͘ϵϲ

ϵϬ͘ϵϲ

ϵϬ͘ϬϬ

ステップ数 (La )

1

ϵϮ͘ϱϱ

ϵϮ͘ϬϬ

ϴϴ͘ϯϬ

ϴϴ͘ϬϬ
Ϳ ϴϲ͘ϬϬ
;й

ϴϱ͘ϭϭ

ᗘ
ϴϯ͘ϱϭ
ϴϰ͘ϬϬ
ϴϮ͘ϵϴ
⢭
ϴϮ͘ϰϱ ϴϮ͘ϰϱ
㢮
ϴϮ͘ϬϬ
ศ
ϴϬ͘ϴϱ

ϴϮ͘ϵϴ
ϴϮ͘ϵϴ

ϴϮ͘ϰϱ

ϴϮ͘ϰϱ

ϴϬ͘ϴϱ

ϴϬ͘ϴϱ

ϯ

ϰ

>Ăсϭ
>ĂсϮ

ϴϬ͘ϬϬ
ϳϴ͘ϬϬ
ϳϲ͘ϬϬ

SHCK ρ

ϳϰ͘ϬϬ

ϭ

E,<

t>^<

図9

GEDK r 結合

ϲϬ͘ϬϬ

原子 88.30

Ϯ

^,<

'<

分類精度結果の比較 (MUTAG)

ϰϯ͘ϲϳ

ϱϬ͘ϬϬ

ϯϴ͘ϴϯ

表 5 ENZYMES を用いた場合の

ϰϬ͘ϬϬ

1

2

NHK

38.83

38.83

WLSK

52.33

53.17

1

31.17

35.00

2

38.50

43.00

3

43.50

43.67

4

50.00

47.00

原子 52.00

46.33

SHCK ρGEDK r 結合[4]

これらの結果から，GEDK は対象となるグラフを部分グラ[5]グラフをベクトル化せずに類似度を計算しているため，既存手[6]

よりも La = 2 の場合の方が，高い精度が得られたのは，根 rである頂点から，より広い範囲に対して Star 編集距離を求め[7]が得られる可能性がある．

6. ま と め[8]

本稿では，グラフ間類似度を求めるためにグラフ Mapping
距離を用い，グラフ分類問題を解くグラフカーネルとしてグラ[9]

フ編集距離カーネルを提案した．評価実験では SVM を用いて既存手法と提案手法の分類精度を比較し，提案手法の性能を評価した．その結果から，提案手法は既存手法と比べて，同等またはそれ以上の分類精度を得ることができた．
[10]

文

献

[1] T. Kudo, E. Maeda, and Y. Matsumoto. An Application of

>ĂсϮ

ϭ

t>^<

Ϯ

ϯ

ϰ

ཎᏊ䠈⤖ྜ

ཎᏊ

ʌ

ƌ

^,<

'<

図 10 分類精度結果の比較 (ENZYMES)度が得られた．

ているからである．更に数ステップ増やすことでより高い精度

ϯϵ͘ϬϬ

ϯϴ͘ϱϬ

>Ăсϭ

E,<

の方が高い分類精度が得られた．ENZYMES の場合は，条件法より高い精度が得られた．また，MUTAG において La = 1

ϱϬ͘ϭϳ

ϰϲ͘ϯϯ

ϯϱ͘ϬϬ
ϯϭ͘ϭϳ

Ϭ͘ϬϬ

[3]

フに分割し，その部分グラフ同士の編集距離を求めることで，

ϱϮ͘ϬϬ

ϭϬ͘ϬϬ

50.17

によっては既存手法で最も精度が高かった WLSK と同等の精

ϱϬ͘ϬϬ
ϰϳ͘ϬϬ

ϮϬ͘ϬϬ

[2]

原子 39.00

ϯϴ͘ϴϯ

ᗘ
ϯϬ͘ϬϬ
⢭
㢮
ศ

ステップ数 (La )

ϰϯ͘ϱϬ

ϰϯ͘ϬϬ

Ϳ
й
;

NHK, WLSK, SHCK と GEDK の分類精度 (%)

ཎᏊ
ƌ

ϱϯ͘ϭϳ
ϱϮ͘ϯϯ

90.96

ཎᏊ䠈⤖ྜ

ʌ

Boosting to Graph Classification. Advances in Neural Information Processing Systems (NIPS), pp.729–736, (2004)
G. R. Michael and J. S. David. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H.
Freeman and Company, (2003)
S. Hido and H. Kashima. A Linear-Time Graph Kernel.
Proc. of International Conference on Data Mining (ICDM),
pp. 179–188, (2009)
N. Shervashidze, P. Schweitzer, E. J. Leeuwen, K. Mehlhorn,
and K. M. Borgwardt. Weisfeiler-lehman Graph Kernels.
Journal of Machine Learning Research (JMLR), pp. 2539–
2561, (2011)
片岡哲也，猪口明博. アダマール符号を用いたグラフ類似度計
算，データ指向構成マイニングとシミュレーション研究会，研究会資料，9(1), pp. 1–7, (2015)
B. Weisfeiler and A. A. Lehman. A Reduction of a Graph
to a Canonical Form and an Algebra Arising During thisReduction. Nauchno-Technicheskaya Informatsia, Ser. 2, 9,(1968)
Z. Zeng, A. K. H. Tung, J. Wang, J. Feng, and L. Zhou.
Comparing Stars: On Approximating Graph Edit Distance.
Proc. of 35th International Conference on Very Large Data
Bases (PVLDB), 2(1), pp. 25–36, (2009)
M. Neuhaus and H. Bunke. Bridging the Gap Between
Graph Edit Distance and Kernel Macines, World Scientific,(2007)A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A.
J. Shusterman, and C. Hansch. Structure-activity Relationship of Mutagenic Aromatic and Heteroaromatic Nitrocompounds. Correlation with Molecular Orbital Energies andHydrophobicity. Journal of Medicinal Chemistry, 34. pp.
786–797, (1991)
I. Schomburg, A. Chang, C. Ebeling, M. Gremse, C. Heldt,
G. Huhn, and D. Schomburg. Updates and Major New
Developments. Nucleic Acids Research, 32D, pp. 431–433,(2004)