情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences
2009 (IBIS2009)

近傍ハッシュを用いた高速なグラフカーネル

A Fast Graph Kernel Using Neighborhood Hash
比戸将平∗
Shohei Hido

鹿島久嗣†
Hisashi Kashima

Abstract: We propose a novel graph kernel based on the structural characteristics of labeled graphs.
The idea is to convert node labels to binary arrays and to compare the nodes by logical operations
on the set of the adjacent node labels. The proposed kernel can be computed in linear time with thenumber of nodes times the average degree of the nodes. Experimental results show that our graphkernel is efficient and it performs better than a state-of-the-art graph kernel for benchmark data sets.
Keywords: graph kernel, hash, logical operation

1

はじめに
グラフ構造を持つデータからの学習やデータマイニン

グは重要な研究分野である．グラフは文字列や木などに比べて複雑な構造や関係を表現できる．例えば，計算機
化学において化学物質のグラフ構造解析は必要不可欠である [10]．化学物質の性質はその構成原子の構造に強く依存するため，計算機上で分子構造をモデル化することで，大量の化学物質に対して高コストな手作業による実験を行わずに毒性などの性質を調べることができる．同様に，グラフはバイオインフォマティクスにおいて遺伝子ネットワークやタンパク質間相互作用ネットワーク，

RNA の 2 次構造などとして現れる．さらに，ソーシャ
ルネットワーク解析や Web マイニングなどの問題においても，ある種のグラフデータが主要な役割を果たしている．
グラフは自由度と表現力が高いため，一般に固定長のベクトルへ変換することは難しい．ところが，従来の機械学習アルゴリズムにおいてはデータが固定長のベク
トルで表現されていると仮定されている．一方，サポー
トベクターマシン（SVM）に代表されるカーネル法においては，グラフ同士の特徴空間での内積の計算手法を与えることにより，グラフをベクトルへ変換することなく学習問題を解くことが可能である．よって Haussler
が R-convolution カーネルを発表して以来 10 年，グラフ∗ IBM 東京基礎研究所, 〒 242-8501 神奈川県大和市下鶴間 1623-14,

e-mail hido@jp.ibm.com,
IBM Research - Tokyo, 1623-14 Shimo-tsuruma, Yamato-shi, Kanagawa,242-8501 Japan† 東京大学大学院情報理工学系研究科数理情報学専攻, 〒 113-8656
東京都文京区本郷 7-3-1, e-mail kashima@mist.i.u-tokyo.ac.jp,
Department of Mathemacical Informatics, the University of Tokyo, 7-3-1
Hongo, Bunkyo-ku, Tokyo, 113-8656 Japan

カーネルを用いたグラフからの学習は大きな研究課題である [1, 5]．多くのグラフカーネルが提案されてきたが，それらは常にスケーラビリティと性能とのトレード
オフに直面してきた．最も成功したグラフカーネルであるランダムウォークカーネルは，n をグラフ中のノード数として O(n3 ) の計算時間が必要である [4, 8, 11]．実際のところ，3 乗の計算量は依然として大きな負荷であり，ランダムウォークカーネルが適用可能なグラフのサイズは数百以下である．それゆえ，既存のグラフカーネ
ルの応用範囲はこれまで主に小さな化学構造などのグラ
フデータに限られていた．
我々は本論文でラベル付きグラフに対し，近傍ハッシュカーネル（Neighborhood Hash Kernel）と呼ぶ新しいグ
ラフカーネルを提案する．その鍵となるのは，ビット列として表現されたノードラベルと，それらの論理演算である．そのためにまず，変換関数によって各離散ノード
ラベルを固定長ビット列に変換する．例えば，ノードラ
ベル A を 4 ビットのビットラベル #1000 と表す．重要なポイントは，ビットラベル集合は，適用順序に依存しない論理演算で扱えることである．あるノードに近接するノード集合のビットラベルに対する排他的論理和演算（XOR）は，そのノードに新しいラベルとしての固有のハッシュ値を与える．ノードラベルをそれら XOR 演算の値で更新することで，近接ノード集合の構造の情報を新しいラベルに集約することができる．更新ラベルを接続されたノード間で交換するために，この操作はグラフ
中の全てのノードに対して数回適用され，それによって高次構造の特徴がグラフ中に伝播していく．そして最後に，更新ラベル集合同士が一致する割合によって，グラフ間のカーネル関数の値を計算する．近傍ハッシュカー

ネルの大きな優位性は計算がグラフサイズに対して線形用され，成功を収めてきた．多くの学習問題は，カーネ

時間と非常に高速に行えるスケーラビリティを備えるとル法によって，最適解が反復法で効率的に求められる 2

同時に，ノードの順列問題を回避しながら大きなグラフ

次計画問題として解ける．グラフデータを扱う学習問題の高度な構造を扱えることである．

も同様にカーネル法の恩恵を受けられるはずだが，多く本論文は以下のように構成されている．最初に 2 節でのカーネルは個々のデータが固定長の実数値ベクトルでラベル付きグラフを定義する．次に 3 節でグラフカー

表されていることを前提としている．実際のところ，グネルとその性質を説明する．そして 4 節で近傍ハッシュラフをその構造的な情報の欠損無しに固定長ベクトルへ

カーネルを提案する．まず 4.1 節でビットラベルと，そ変換することは一般に困難である．しかしながら，グラ

れに対する論理演算を導入する．4.2 節では近傍ハッシュフカーネルの登場によって，グラフを高次元ベクトルとの計算方法を詳しく述べる．カーネル行列を求めるアル

して陽に表現せずとも，SVM を含むカーネル法ベース

ゴリズムは 4.3 節で説明する．5 節では計算量についての学習アルゴリズムをグラフデータに適用する道が開け考察する．最後に 6 節において既存カーネルとの比較にた．グラフを含む構造を持つデータに対しては，Haussler

よってスケーラビリティと性能の評価実験を行う．

が最初に全ての部分構造ペアを比較する R-convolution
カーネルを考案した [5]．同じフレームワークを使って，

2

ラベル付きグラフ
本論文で，我々はノードが離散ラベルで表現される属性を持ち，枝が無向であるグラフに重点を置く．ラベル

特定の種類の部分構造，例えば経路や木，もしくは部分グラフを用いるグラフカーネルがいくつも提案されている [1]．

付き無向グラフは，G = {V, E, `(·)} のように形式的に

次に，カーネルに関して，カーネル関数とカーネル行

定義される．ここで，V はノード集合，E = V × V は枝列，及びいくつかの重要な性質を説明する．2 つのグラ集合を表す．各要素 v ∈ {v1 , . . . , vn } = V はグラフ中の1 つのノードを表す．ノードの数 n = |V | をもって，グラ
フのサイズと定義する（|G| = n），ラベリング関数 `(·)
はノードから離散ラベルの全集合であるアルファベット

フ G と G0 の間のカーネル関数を k(G, G0 ) とする．G とG0 が同一のグラフであることは，k(G, G0 ) = 1 を満たす必要十分条件である．そうでなければ，カーネル関数の値は 0 以上 1 未満となる．グラフ集合 {G1 , . . . , Gh }

Σ へのマッピングを表す．各ノード vi（1 ≤ i ≤ n）はラとカーネル関数 k(·, ·) に対し，カーネル行列 K の各要

ベル `(vi ) ∈ Σ を持つ．各枝 eij は 2 つのノード vi と vj

素は以下のように計算される．

の間の無向枝である．ここで，枝が無向であるため，eji

Kij = Kji = k(Gi , Gj ) (1 ≤ i, j ≤ h).

も必ず E に属する．枝集合 E は大きさ n × n の隣接行列

A としても表現できる．隣接行列の要素は，eij ∈ E な
らば Aij = Aji = 1，そうでなければ 0 である．Vadj (vi )

半正定値性を満たすカーネルは Mercer カーネルと呼ばは，vi に近接する（枝を共有する）ノードの集合を表し，の鍵となる．よって，カーネル行列は任意の複素数列

そのサイズは |Vci ∈ C(1 ≤ i ≤ h) に対して以下の不等式を一般に満たす．
h∑ci c¯j Kij ≥ 0.

adj(vi )| = di とする．同様に， r-近接
r
ノード集合 Vadj (vi ) は最大 r 個の枝からなる経路で viに繋がるノードの集合とする．現実のグラフデータの多くが離散ラベル付き無向グラフで表現できるため，ほとんどの既存のグラフカーネルと同様，我々も離散ラベル付き無向グラフを扱う新たなカーネルを提案する．

3

グラフカーネル

れ、SVM を含むカーネル法の凸最適化問題を解くため

i,j=1

カーネル行列の半正定値性は固有値が全て非負であるか否かで確かめることができる．また，カーネル関数は加法性を持つので 2 つのカーネル k(·, ·) と k 0 (·, ·) に対して，その線形和本節で，カーネル法について簡単に紹介すると共に，

k 00 (·, ·) = αk(·, ·) + (1 − α)k 0 (·, ·)どのようなグラフカーネルが実世界の応用において新たな可能性を見出せるかについて議論する．
サポートベクターマシン（SVM）が教師付き学習における強力なアプローチとして現れて以来，カーネル法に基づくアルゴリズムは深く研究されており，機械学習とデータマイニングにおけるおよそ全ての問題に対して適(1)もまたカーネルとなる．ここで，α は 0 以上 1 以下の実数である．この性質により，複数のカーネルの組み合わせによって，別のカーネルを定義できる．
次に，グラフカーネルの望ましい性質について説明する．

スケーラビリティ．最も重要なポイントはカーネルのすのは，まさにそのようなカーネルである．

計算に必要な時間とメモリ量である．グラフは複雑な構造であるため，2 つのグラフを比較してその類似度や差近傍ハッシュカーネル

4

分を何らかの値として求めることは困難かつ漠然とした本節で，グラフカーネルとして良い性質を備えた近傍タスクである．実際，単に 2 つのグラフが同一かどうか

ハッシュカーネルを提案する．鍵となるのは，ノードラをチェックするグラフ同型性問題（graph isomorphism）

ベルを固定長のビット列（ビットラベル）として表現し，においてすら，多項式時間アルゴリズムは知られていな

近接するノード集合のビットラベル間の論理演算によっい．グラフ同型性問題を困難にしている大きな理由の 1て各ノードを特徴付けることである．まず，どのようにつは，ノード順列である．あるノードが別のグラフに出ビットラベル付きノードを扱うかを説明し，次にカーネ現しているか知るためには，近接ノード集合の埋め込み

ルの計算アルゴリズムを導入する．

を，その順序に依らず調べなければならない．そのためにはさらに各近接ノードに近接する全ノード集合の埋め込みも考える必要がある．計算機上でノード間の接続
は隣接行列の形で保持されているだけなので，これら埋

4.1

ビットラベルと論理演算

以下のように，D 個のビット（0 もしくは 1）から成るビット列をビットラベルと呼ぶ．

め込みのチェックは数十ノードの小さなグラフに対して

s = {b1 , b2 , · · · , bD }.

すら膨大な計算コストがかかる．実際，ランダムウォー(2)

3

クを基にしたカーネルでも O(n ) の計算時間を要する．
よって，サイズが 1, 000 を超えるグラフの詳細な比較は非現実的であり，既存のグラフカーネルでは扱うことができなかった．
表現力．グラフカーネルはまた，可能な限りグラフ構
造に潜む隠れた重要な差異を扱う表現力を持たねばならない．単純に実行可能なグラフ比較方法は，ノードラベ
ルの種類やヒストグラム，ノード次数の分布などの統計的性質を比べることである．しかし，そのようなナイー
ブな方法ではグラフの構造における特徴を考慮できない
ため，その応用範囲は限定的となってしまう．例えば，
薬剤試験において，化学物質の毒性を予測するにはノードや枝レベルの統計的性質だけでなく，原子間の接続関係における微妙な差異を考慮する必要がある．一方，構造の性質を考慮しながらグラフを比較する単純な手法
は，部分グラフ集合間のマッチングを行い類似度を計算する手法である．しかしながら，部分グラフの数はグラフサイズに対し指数的に増大するため，大きなグラフにおいて全部分グラフを列挙するのは非現実的である．
ここで，良いグラフカーネルに求められる性質をまとめる．

• 小さな計算コスト（O(n3 ) 未満）．
• 部分グラフ構造に対する高い表現力．

ここで，定数 D は 2D − 1 À |Σ| を満たすようにする．
ビットラベルは最大 2D − 1 までの大きさの非負整数を表すことができる．ラベル付きグラフに対して，ノード
ラベル全集合 Σ は離散値の有限集合であり，グラフデー
タにおいて通常その種類数は千通り以下である．たとえば，化学物質の中には 118 の異なる原子のみが存在す
る．それゆえ，全てのノードラベルは対応するランダムに選ばれた D ビット列集合に一般性を失うことなく変換できる．実験においては，元のラベル集合とランダムな 16 ビット列への 1 対 1 のマッピング関数によって，全てのラベルを 16 ビットラベルで置き換えるとする．
次に，ビットラベルを扱ってハッシュ値を計算するた
めに，符号理論で一般的によく用いられるビット演算を導入する．排他的論理和（Exclusive OR, XOR）は，2ビット間の 2 値関数として定義される．ビット bi とビット bj の間の XOR は，bi 6= bj の場合は 1，それでなけ
れば 0 を返す．
ここで，XOR(si , sj ) = si ⊕ sj は 2 つのビットラベル

si と sj の間の XOR 演算とし，その出力である新たなビット列は各桁が si と sj の各桁の XOR 操作の結果を表すとする．この操作はビット毎に行われるため，si ⊕ sjの計算は最大でも D に線形の時間で実行可能である1 ．

XOR 操作の特徴を表 1 にまとめた．表 1(a) 中の szero
は空のビット列（{0, 0, · · · , 0}Di=1 ）を表す．任意の 3 つ

様々なグラフに対して多様なカーネルが提案されてきたのビット列 s，s0 ，s00 に対して，表 1(a-e) の性質が成りが，それらは常にスケーラビリティと表現力の間の同じ立つ．

トレードオフに直面しており，その応用可能範囲は未だ限定的である．我々の知る限り，一般のラベル付きグラフに対して両方の性質を兼ね備えた効率よく性能の良い
グラフカーネルはこれまで存在しなかった．我々が目指

1 一般的な CPU は，ビット長 D がプロセッサのビットサイズ（主に 32 か 64）を超えない場合，このようなビット毎の論理演算を 1 ク
ロック（単位時間）で実行できる [7]．MATLAB においても，16 ビッ
ト列に対するビット毎の XOR 操作は 32 ビット列と同じ計算時間となる．

し，近傍ハッシュを以下の通り計算する．
表 1: ビット毎 XOR 演算の性質
(a)
(b)
(c)
(d)
(e)

NH(v) = ROT1 (`(v)) ⊕ (`(v1adj ) ⊕ · · · , ⊕`(vdadj )).

s ⊕ s = szeros ⊕ szero = ss ⊕ s0 = s0 ⊕ s(s ⊕ s0 ) ⊕ s00 = s ⊕ (s0 ⊕ s00 )s0 ⊕ s0 ⊕ s = s

ここで，出力 NH(v) もまた D ビット列である．図 1(b) のステップ (1)-(4) は 3 つのビットラベルに対する XOR 演
算を表している．v 自身のビットラベルだけが 1 ビット回

さらにもう 1 つのビット演算，ビット回転 (ROT)

転（ROT1 (`(v))）によって近接ノードのビットラベルと=は区別されている．その後，ハッシュ値 NH(v) = #0011{b1 , b2 , · · · , bD } に対し，後半の D − o ビットを o ビッ
ト左に移動させ，前半の o ビットをその後ろに移動させる．その結果は，次のようになる．

を得て，v の新たなビットラベルと見なす．この値 NH(v)を 導 入 す る ．ビット 回 転 ROTo は ビット 列 s

は v 周辺のノードラベルの分布（ヒストグラム）を一意に表現する．この 1 ノードに対するハッシュ演算は，d を

v の近接ノード数とした時，O(Dd) で実行可能である．
ROTo (s) = {bo+1 , bo+2 , · · · , bD , b1 , · · · , bo }.

(3)

ROT 演算もビットラベルを同じ長さの新たなビット列に変換する．さらに，ROTo 操作も，o の値に関わらず，
D に線形の時間で実行可能性である2 ．

4.2

近傍ハッシュは（あるノードとその近接ノード集合の）ビットラベル集合から，同じ長さの新しいビット列へのハッシュ関数となっている．ここで，2 つのノード vi とvj は同じノードラベルを持つとする（`(vi ) = `(vj )）．もし vi と vj の近接ノード集合のラベル集合も同一であった場合は，2 つのノードに対する近傍ハッシュのハッシュ

近傍ハッシュ

ビットラベル付きグラフに対して，論理演算 XOR とROT を用いて近傍ハッシュを計算する．
あるノード v に対して，まず近接ノード集合 Vadj (v)を得る．図 1 に，あるノードについて近接するノードとそのラベルが与えられた時の，近傍ハッシュ計算の例を示す．簡単のため，ここではノードラベルを 4 ビット列で表している．図 1(a) にあるように，ノード v の元のラベルと対応するビットラベルはそれぞれ A と #1000
である．このノードは 2 つの近接ノード {v1adj , v2adj } を持ち，それらの元のラベルとビットラベルはそれぞれ B（#1110）と C（#1100）である．図 1(b) に計算方法を示した単純な近傍ハッシュは次の通り定義する．

値は同じになる．そうでなければ，ハッシュ衝突の場合を除いて，ハッシュ値は違うものとなる3 ．近傍ハッシュにとって重要なのは，XOR 演算の性質（表 1(c)）によって，近接ノード集合のノードラベルが処理される順序にハッシュ値が依存しないことである．これにより，我々は vi と vj に対して，近接ノードのラベル集合の共通部
分のマッチング無しに，近傍ラベル集合が同一か否かを判断できる．これが計算量の面において，我々のグラフ
カーネルにとって主要な優位性となる．
ここまでで，我々はノード v のノードラベルを近傍
ハッシュ値 NH(v) に置き換えるられるようになった．このラベル更新は各ノードの近接ノードの情報を統合したことになる．近傍ハッシュをグラフ G の全てのノー

Definition 1 Simple Neighborhood Hash: ノード v とそドに適用してノードラベルを更新すると，新しいグラフ(node) = {v1adj , · · · , vdadj } に対G1 = {V, E, `1 (·)} が得られる．そこでは `1 (v) = NH(v)が全ての v ∈ V について成り立つ．この操作を，グラフへの近傍ハッシュ関数（G1 = NH(G)）とする．更新の近接ノード集合 V

adj

#1110
+
#1100

#1110
B = #1110 v2adj
v1adj
C = #1100

A = #1000#1100v
NH:#0011#0010 + #0001 = #0011(1)Neighbors(3)XOR(2)XOR(a)(5)Hash label

されたグラフ G1 において，各ノードラベル `1 (v) は元のグラフ G において直接繋がっているノードのラベル(4)Self node

集合に対応している．ここで，G1 を保持するのに必要(b)

なメモリ量は G と同じである．
近傍ハッシュによって，離れたノード間の高次構造

図 1: 単純な近傍ハッシュの例．(a) ノード v は 2 つのがどのように扱うかを説明する．Gr+1 = NH(Gr ) の近接ノードを持つ．(b)XOR と ROT を用いた v の近傍

ように，近傍ハッシュは繰り返し適用できる．ここで，ハッシュの計算手法．

`r+1 (v) = NH(v r ) である．グラフ Gr における，更新
されたノードラベル `r (v) は r-近傍ノード集合のラベル

2 ROT 演算は MATLAB でサポートされている bitshift 操作を用いて実装する．

3 D ビット列に対してハッシュ衝突が起こる確率はわずか 2−D である（D = 16 ならば 10−5 以下である）．

D = #0101
C = #1100
D = #0101

A = #1000

v3adj

v

v2adj

#0101

#0101

#1100

#0101

#0101

#1100

} #0111

#1101

#1101
+

#1011

#1011

x2
#1101
x1

NH:#1101

v1adj

#0110

+

#0001 =

#0111

CS-NH:#0111(a)
C = #1100
v1’adj(1)Neighborsv’(9)Hash label(2)Radix sort

NH:#1101(4)Add(3)Counting

A = #1000 CS-NH:#1010(b)(6)XOR(5)Bit rotation(7)XOR(8)Self node(c)

図 2: カウント考慮型近傍ハッシュの例．(a) ノード v とその近接ノード．(b) ノード v 0 は v と同じ近傍ハッシュ値を持つ．(c)v のカウント考慮型近傍ハッシュの計算手法．

分布を表している．それゆえ，近傍ハッシュが r 回適用

ここでは，o との XOR 演算の後に o ビット回転が適用

された 2 つのグラフ中の 2 つのノード vi と vj は，そのされる．これらの処理により，ラベルの出現回数によっr-近傍ノード集合のラベルとその構造が等しい場合にのみ，同じノードラベルを持つ．

て異なる近傍ハッシュ値が得られる．こうしてカウント

rr`r+1 (vi ) = `r+1 (vj ) ⇒ Vadj(vi ) = Vadj
(vj ).

考慮型近傍ハッシュを次のように定義する．

Definition 2 Count-sensitive Neighborhood Hash: ノー0

そうでなければ，異なるノードラベルとなる（ハッシュド v とその重複無し近接ノード集合 V adj (v), に対し，衝突を除く）．近傍ハッシュは近接ノード集合内の順序

カウント考慮型近傍ハッシュを以下の通り計算する．

に依存しないため，複雑なマッチング無しに，vi と vj

CSNH(v) = ROT1 (`(v)) ⊕ (`0 (v1adj )⊕, · · · , ⊕`0 (vdadj
0 )).

の周辺ノード構造の一致を効率よく比較できる．
次に，ハッシュ衝突を削減するために，単純な近傍ハッ

この拡張された近傍ハッシュはハッシュ衝突を引き起シュの拡張を行う．実際，偶然によるハッシュ衝突でなこしていた図 2(a)(b) の v と v 0 に正しく異なる値を与えくとも，2 つのノードに対する近傍ハッシュが同じ値とる（CSNH(v) 6= CSNH(v 0 )）．図 2(a) の v に対するカウなってしまう可能性がわずかながら存在する．例えば，ント考慮型近傍ハッシュの計算の様子を図 2(c) に示す．

図 2(a)(b) にあるように，ノード v と v 0 が同じノード

入力ノードとラベル集合は単純な近傍ハッシュの場合と

ラベル A（#1000）を持ち，近接ノードがラベル集合そ同じである．最初に近接ノードのラベル集合がステップ

れぞれ｛ D，C，D｝と｛ C ｝だとする．この場合，2(1) でソートされる．ラベルの出現回数を順にカウントすることにより，2 種類のラベルが存在し，#0101 の出

0

つの近傍ハッシュ値は同一になる（NH(v) = NH(v ) =#1101）．何故なら，図 2(a) に偶数個存在するノードラベ
ル D（#0101）は XOR 演算において表 1 (e) の性質により打ち消されてしまうためである．このような都合の悪

現が 2 回，#1100 の出現が 1 回であることがステップ(2)-(3) で分かる．そこでラベルの出現回数に応じ，ステップ (4)-(5) で XOR と ROT を適用して，#1101 といハッシュ衝突は，近傍ハッシュを利用したカーネルの#1011 を求める．最後に，ステップ (6)-(9) においてもう半正定値性とその性能に悪影響を与える可能性がある．

一度 XOR を元のノード v との間で計算して，#0111 を

この問題に対処するため，ラベルカウントを用いた結果として得る．一方で，v 0 に対し，カウント考慮型近近傍ハッシュの拡張を行う．まず近接ノードのビットラ

傍ハッシュは図 2(b) の通り異なるハッシュ値 #0011 をベル集合に対しソートを適用する．これは，基数ソート

与える．カウント考慮型近傍ハッシュの計算量は，依然（radix sort）等の比較無しソートアルゴリズムを用いるとして近接ノードの数 d（d0 ≤ d）に比例している．こことで，O(Dd) で実行可能である．次に，含まれる全

こで，偶然のハッシュ衝突に対しては，十分に長いビッラベルとその出現回数を線形時間で数え，重複無し近接トラベルを用いることによって，その確率を低減できる．

0

ラベル集合 V adj (v) とその大きさ d0 を得る．各ラベル

我々の実装においては，16 ビットのビットラベルを用`(v adj ) に対し，その出現回数 o（D ビット列で表現する）を用いて新しいラベルを次のように計算する．

いる．

`0 (v adj ) = ROTo (`(v adj ) ⊕ o).

簡単に言えば，近傍ハッシュは各ノードラベルに，近接ノードのラベル集合という，より多くの情報量を含ませる操作である．近傍ハッシュを r 回適用されたグラフと計算する．ラベルマッチング関数 Compare Labels のは，間に r − 1 個のエッジを持つノード間の高次

内容と，どのように K r がカーネル行列になるかは後述の関係性も考慮した情報を持つ．また，更新されたグラする．上記処理を R 回繰り返した後，カーネルの加法

フ集合を保持するのに必要なメモリ量は，元のグラフに性（式 1）に基づいて，最終的なカーネル行列 K は全比例した量でしかない．

部分カーネル行列 {K r }R
r=1 の平均として求める．

r+1

G

4.3

ラベルマッチング関数 Compare Labels の仮想コー

アルゴリズムドを Algorithm 2 に示す．2 つのグラフ Ga と Gb につ

近傍ハッシュを用いて更新されたグラフ集合を用い

いて，入力を 1-3 行目にまとめた．入力されたグラフて，元のグラフ間の近傍ハッシュカーネル（Neighborhoodのノードラベルリストはソート済みと仮定する．8 行目

Hash Kernel, NHK）を構築する．本節では，近傍ハッシュ

で，ノードリスト Vasort の i 番目の要素を選択し，もうを用いてカーネル行列を計算するアルゴリズムを示す．

一方のノードリスト Vbsort 中のマッチングを順に数え

Algorithm 1 はグラフ集合を与えられてカーネル行列を計算する関数 Calculate Similarity Matrix の仮想コードでる．共通して存在するラベルのマッチング数を数えなある．近傍ハッシュを繰り返し適用し，グラフ間の高次る．実際，7-19 行目の while ループは最大 na + nb 回

構造を段階的に比較する．1-3 行目は，必要な入力であの繰り返しで終了するため，このカウント処理は計算量る．各ステップ r（1 ≤ r ≤ R）において，5-13 行目の操行列として初期化する．6-9 行目において，Γ の全グラフ

O(D(na + nb )) で完了する．20 行目で，最終的なマッ
チング数 c を正規化し，カーネル行列の要素 (κ) として出力する．この式は離散集合間の類似度尺度としてよくに近傍ハッシュを適用する．7 行目では，単純な近傍ハッ用いられる Jaccard-Tanimoto 係数と同等のものである．

シュとカウント考慮型近傍ハッシュのどちらでも選択可

これらのアルゴリズムによって，近傍ハッシュを用いr

作を繰り返す．5 行目で，部分カーネル行列 K を単位能である．同時に，各ノード集合のラベルを 8 行目でソートする．ノードラベルは固定長ビット列なので，基数ソート（radix sort）を用いることで D に比例する時間でソート可能である．古いグラフ Gr は以後使われない
ので，10 行目でそのデータをメモリ上から消去してもよい．11-13 行目で，全グラフペアに対して，ラベル集合間rのマッチングによって行列の各要素を Kij= k(Gi , Gj )Algorithm 1 Calculate Similarity M atrix
Require: カーネル行列を計算するグラフ集合

1: Γ = {G01 , . . . , G0h } : グラフ集合

がら，インデックス i と j はそれぞれ na と nb に達す

たカーネル行列は効率よく計算できる．
Algorithm 2 Compare Labels
Require: 比較する 2 つのグラフ
1: Vasort , Vbsort :両グラフのソート済みノードリスト
2: na = |Vasort |, nb = |Vbsort |: 両グラフのノード数
3: `a , `b :両グラフのラベリング関数

Ensure: 0 ≤ κ ≤ 1
4: c ← 0
5: i ← 1
6: j ← 1

2: h = |Γ| : グラフ数

7: while i ≤ na andj ≤ nb do

3: R: 近傍ハッシュの最大適用数

8:

Ensure: K 半正定カーネル行列
4: for r = 1 to R do
5:
6:
7:
8:
9:
10:
11:

10:

K r ← I {:h x h 単位行列 }for i = 1 to h do

11:

Gri ← NH(Gr−1) {:単純かカウント考慮型 }irGi ← {Radix Sort(Vi , `r (·)), E, `r (·)}
end for13:

r−1

remove G
for each pair (Gri , Grj ) ∈ Γ × Γ do

r
r
Kij
= Kij
← Compare Labels(Ga , Gb )13:
end for
14: end for∑R1r
15: K ← R
r=1 K {:繰り返しに対する正規化 }16: return K {:カーネル行列 }

12:

9:

12:

14:
15:
16:
17:
18:

vi ← Vasort [i]vj ← Vbsort [j]if `a (vi ) = `b (vj ) then
c←c+1
i←i+1
j ←j+1else if `a (vi ) < `b (vj ) then
i←i+1
else
j ←j+1
end if

19: end whilec
20: κ = n +n−ca

21: return κb10Elapsed time (sec)1010

表 2: 各データセットに関する性質．計算時間は RW（λ =RW(0.4)RW(0.9)
NHK
CSNHK

3

0.4）と，NHK，CSNHK（共に R = 5）， 全て Morgan
インデックスを適用済みの値である.

2

データ

1

MUTAG
PTC MR
10#Graph188344Max. size
28
109

計算時間（秒）RW
NHK CSNHK
145.2
38.9
41.3
896.3 133.7
137.6

0

型近傍ハッシュカーネル（CSNHK）の両方を MATLABで実装した．ビットラベルの長さは 16 に固定し，近傍
100

200

500
1000
2000
The number of nodes in graph

5000

10000

ハッシュの最大回数は 1 から 5 まで変化させる．比較のため，定点反復法を用いる効率的なランダムウォー
クカーネル（RW）も実装した [11]．ランダムウォーク

図 3: 各アルゴリズムの計算時間．近傍ハッシュカーネ
ルはグラフサイズに対して線形の増加である.

5

考察

5.1

計算量

近傍ハッシュカーネルのスケーラビリティを考察する．

カーネルの対角要素は 1 ではないため，正規化を行って√
0
Kij= Kij / Kii · Kjj としたカーネル行列 K 0 を計算する．ランダムウォークカーネルの停止確率 λ は {0.4, 0.9}のいずれかとし，収束チェックの閾値は 10−10 とした．
R 3.16GHz，メインメモリ
全ての実験は Intel Xeon°

12GB を搭載した Windows サーバ上で実行した．

まず単純な近傍ハッシュとカウント考慮型近傍ハッシュ（NH と CSNH）の計算について考える．

4.2 節で示したように，あるノードに対する近傍ハッシュでは d 個の近接ノードを扱い，d + 1 個のビットラ
ベルに対して XOR や ROT の論理演算を適用する．4.1

6.1

人工グラフデータ

まず人工グラフを用いて近傍ハッシュカーネルのス
ケーラビリティを評価する．生成する人工グラフは 100
から 10, 000 までのサイズで，平均ノード次数 d¯ = 5，ア

節で説明した通り，全ての論理演算は固定ビット長 D

ルファベットの大きさ |Σ| = 100 とした．2 つの人工グに比例する時間で計算できる．図 2(c) のステップ (2) にラフに対して，カーネル行列（2 × 2 の大きさ）の計算

あるように，CSNH の中のソートも，基数ソートを用いに要した時間を CPU 時間で計測した．各パラメータ設ることにより，高々ノード次数 d に線形の時間で計算

定について 10 回ずつ計測を行った後，その平均時間を可能である（O(Dd)）．ラベル種類数のカウントやカウ示す．図 3 は NHK，CSNHK，RW に対してグラフの大ントの追加など，図 2 のステップ (2-3) にあるその他のきさを変化させた時の計算時間の増加を示した両対数プ

操作もまた O(Dd) で実行できる．よって，グラフ G 中

ロットである．

の全てのノードに対して操作を行うと，近傍ハッシュの¯ となる．
計算量は NH と CSNH の両方に対して O(Ddn)

である．特に，サイズ 10, 000 のグラフに対しても NHK

ここで，d¯ は平均ノード次数（近接ノード数）である．

が要する時間はわずか 5 秒以下である．この結果は，近Algorithm 1 の 8 行目のソートもまたノード数に線形で計算できる．Algorithm 2 において 2 つのグラフを比較

傍ハッシュカーネルを用いた学習が数千ノードを含むグする時間も，2 つのグラフの最大サイズで抑えられる．

方，ランダムウォークカーネルはパラメータ λ の値にそれゆえ，近傍ハッシュカーネルの計算全体の計算量も¯ となる．また，計算に必要なメモリ用も最大O(DRdn)

寄らず，グラフサイズに 2 乗の計算時間の増大が起きて全体として，NHK と CSNHK は RW よりも一桁高速

ラフデータセットに対しても適用であることを示す．一いる．

グラフサイズとグラフ数の積に線形となる．

6.2

6

実験
本節で，近傍ハッシュカーネルの性能とスケーラビリ

ティを評価する．
単純な近傍ハッシュカーネル（NHK）とカウント考慮

ベンチマークデータ

グラフカーネルの性能評価に広く用いられている化学構造グラフの 2 値分類データセット，MUTAG と PTC

Mice and Rats（MR）を用いて実験を行った [3, 6]．各
データセットのグラフ数（#Graph）と最大グラフサイズ（Max. size）を表 2 に示した．また，元のデータセット表 3: MUTAG と PTC MR における予測精度．2 行目の値は RW のパラメータ λ，NHK と CSNHK のパラメータ R．
データ

MUTAG
PTC MR

Morgan
Off
On
Off
On

RW
0.4
0.9
74.94 74.50
82.43 76.05
59.87 58.11
55.86 52.33

1
81.84
84.53
60.77
59.03

2
79.15
84.01
59.61
59.61

NHK
3
78.74
82.37
59.59
59.29

4
80.85
82.89
59.00
60.17

5
81.90
82.92
57.84
58.71

1
81.84
84.53
60.77
59.03

2
81.37
84.56
62.21
61.01

CSNHK
3
86.17
84.50
61.05
58.72

4
87.75
84.53
60.48
59.29

5
87.75
85.06
60.77
59.29

に対して，Morgan インデックス [9] を付与した．構築しある．実験において，近傍ハッシュカーネルは数千ノーたカーネル行列を用いて予測モデルを学習するために，

ドのグラフに適用可能であることが示され，ベンチマー

LIBSVM [2] の中の C-SVM を用いた．データセットをクにおいて既存カーネルよりも良い性能を示した．

10 個の部分セットに分割し，各評価セットに対して残りの 9 個の部分セットにおいて 10 段階交差検定を行い，参考文献

パラメータ c を {10 , 10 , · · · , 10 } から選択した．その
0

1

7

後，選択された最適な c を用いて 9 個の部分セットにおいて学習を行い，評価セットにおける予測精度を求めた．

10 セットの平均精度を表 3 に示した. 太字の数字は各設定（行）において最良の結果を表す．全体として，NHK と CSNHK は RW に比べて良い性能を発揮した．
パラメータ R の影響は NHK については明らかではないが，R = 5 の CSNHK が Morgan インデックスの有無に関わらず最良の結果を残した．これはカウント考慮型近傍ハッシュが MUTAG データにおいて高次構造を正しく考慮することに成功したことを示している．MUTAG
データの化学構造には数種類の原子しか含まれないため，Morgan インデックスは全てのアルゴリズムについて有効に働いている．PTC MR データセットにおいては，正しい予測が極めて難しいことが知られている．その中で，CSNHK は RW と NHK よりも高い性能を示した．最大ハッシュ回数 R の影響は不明だが，R = 2 の時の CSNHK が最良だった．これは，近傍ハッシュカー
ネルにおいて，最適な R の選択がデータセットに依存することを示している．ただし，計算時間は R に対して高々線形である．また，Morgan インデックスは PTC

MR データセットにおいては上手く機能しない．
表 2 にアルゴリズム毎の最大計算時間を示した．実際，NHK と CSNHK はこれらの最大グラフサイズ 100程度の比較的小さなグラフから成るデータセットに対しても 3 倍以上高速に動作した．

7

むすび
本論文において，高速な近傍ハッシュカーネルを提案した．その鍵は，ラベルをビット列で表現し，近接ノード集合のラベル分布を論理演算で比較することである．
¯ で
その結果，カーネル関数の計算量はわずか O(Ddn)[1] K. M. Borgwardt. Graph Kernels. PhD thesis, Computer
Science, Ludwig-Maximilians-University Munich, 2007.
[2] C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/∼cjlin/libsvm.
[3] A. Debnath, R. Lopez de Compadre, G. Debnath, A. Shusterman, and C. Hansch. Structure-activity relationship ofmutagenic aromatic and heteroaromatic nitro compounds.
correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34:786–797, 1991.
[4] T. Gärtner, J. W. Lloyd, and P. A. Flach. Kernels and distances for structured data. Machine Learning, 57(3):205–
232, 2004.
[5] D. Haussler. Convolution kernels on discrete structures.
Technical report, 1999.
[6] C. Helma and S. Kramer. A survey of the predictive toxicology challenge 2000-2001. Bioinformatics, 19(10):1179–
1182, 2003.
[7] Intel Corporation. Intel 64 and IA-32 Architectures Software
Developer’s Manual Volume 2B: Instruction Set Reference,
N-Z, March 2009.
[8] H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th
International Conference on Machine Learning (ICML),
2003.
[9] P. Mahe and T. Akutsu. Extensions of marginalized graphkernels. In In Proceedings of the 21st International Conference on Machine Learning (ICML), pages 552–559. ACM
Press, 2004.
[10] L. Ralaivola, S. J. Swamidass, H. Saigo, and P. Baldi.
Graph kernels for chemical informatics. Neural Networks,
18(8):1093–1110, 2005.
[11] S. Vishwanathan, K. M. Borgwardt, and N. N. Schraudolph.
Fast computation of graph kernels. In B. Schölkopf, J. Platt,and T. Hoffman, editors, Advances in Neural Information
Processing Systems 19, pages 1449–1456. MIT Press, Cambridge, MA, 2007.