Marginalized Kernels Between Labeled Graphs

Hisashi Kashimahkashima@jp.ibm.com
IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, 242-8502 Kanagawa, Japan
Koji Tsudakoji.tsuda@tuebingen.mpg.de
Max Planck Institute for Biological Cybernetics, Spemannstr. 38, 72076 Tübingen, Germany; andAIST Computational Biology Research Center, 2-43 Aomi, Koto-ku, 135-0064 Tokyo, Japan
Akihiro Inokuchi
inokuchi@jp.ibm.com
IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, 242-8502 Kanagawa, Japan

Abstract
A new kernel function between two labeledgraphs is presented. Feature vectors are defined as the counts of label paths producedby random walks on graphs. The kernel computation finally boils down to obtaining thestationary state of a discrete-time linear system, thus is efficiently performed by solving simultaneous linear equations. Our kernel is based on an infinite dimensional feature space, so it is fundamentally different
from other string or tree kernels based on dynamic programming. We will present promising empirical results in classification of chemical compounds.1

1. Introduction
A large amount of the research in machine learning isconcerned with classification and regression for realvalued vectors (Vapnik, 1998). However, much of
the real world data is represented not as vectors, but
as graphs including sequences and trees, for example, biological sequences (Durbin et al., 1998), natural language texts (Manning & Schütze, 1999), semistructured data such as HTML and XML (Abiteboul
et al., 2000), and so on. Especially, in the pharmaceutical area, the chemical compounds are represented aslabeled graphs, and their automatic classification is of
crucial importance in the rationalization of drug discovery processes to predict the effectiveness or toxicity
1
An extended abstract of this research has been presented in IEEE ICDM International Workshop on Active
Mining at Maebashi, Japan (Kashima & Inokuchi, 2002).
But this full paper contains much richer theoretical analysises such as interpretation as marginalized kernels, convergence conditions, relationship to linear systems, and soon.

of drugs from their chemical structures (Kramer & De
Raedt, 2001; Inokuchi et al., 2000).
Kernel methods such as support vector machines are
becoming increasingly popular for their high performance (Schölkopf & Smola, 2002). In kernel methods, all computations are done via a kernel function,
which is the inner product of two vectors in a feature space. In order to apply kernel methods to graphclassification, we first need to define a kernel function between the graphs. However, defining a kernel function is not an easy task, because it must be
designed to be positive semidefinite2 . Following thepioneering work by Haussler (1999), a number of kernels were proposed for structured data, for example,
Watkins (2000), Jaakkola et al. (2000), Leslie et al.
(2003), Lodhi et al. (2002), and Tsuda et al. (2002)
for sequences, and Vishwanathan and Smola (2003),
Collins and Duffy (2001), and Kashima and Koyanagi(2002) for trees. Most of them are based on the idea ofan object decomposed into substructures (i.e. subsequences, subtrees or subgraphs) and a feature vector
is composed of the counts of the substructures. As
the dimensionality of feature vectors is typically very
high, they deliberately avoid explicit computations offeature values, and adopt efficient procedures such as
dynamic programming or suffix trees.
In this paper, we will construct a kernel function between two graphs, which is distinguished from the kernel between two vertices in a graph, e.g., diffusion kernels (Kondor & Lafferty, 2002; Kandola et al., 2003;
Lafferty & Lebanon, 2003) or the kernel between twopaths in a graph, e.g., path kernels (Takimoto & Warmuth, 2002). There has been almost no significant
works for designing kernels between two graphs except2
Ad hoc similarity functions are not always positive
semidefinite, e.g. Shimodaira et al. (2002) and Bahlmann
et al. (2002).

Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

for the work by Gärtner (2002). We will discuss about
his kernels in Appendix.
One existing way to describe a labeled graph as afeature vector is to count label paths appearing in
the graph. For example, the pattern discovery algorithm (Kramer & De Raedt, 2001; Inokuchi et al.,2000) explicitly constructs a feature vector from thecounts of frequently appearing label paths in a graph.
For the labeled graph shown in Figure 1, a label pathis produced by traversing the vertices, and looks like

2. Marginalized Kernels
A common way for constructing a kernel for structured data such as strings, trees, and graphs is to assume hidden variables and make use of the probability
distribution of visible and hidden variables (Haussler,
1999; Watkins, 2000; Tsuda et al., 2002). For example, Watkins (2000) proposed conditional symmetricindependence (CSI) kernels which are described as
K(x, x0 ) =Xh(A, e, A, d, D, a, B, c, D),
where the vertex labels A, B, C, D and the edge labelsa, b, c, d, e appear alternately. Numerous label paths
are produced by traversing the nodes in every possible way. Especially when the graph has a loop, thedimensionality of the count vector is infinite, because
traversing may never end. In order to explicitly construct the feature vector, we have to select features tokeep the dimensionality finite. The label paths may be
selected simply by limiting the path length or, more
intelligently, the pattern discovery algorithm identifies
the label paths which appear frequently in the training
set of graphs. In any case, there is an additional unwanted parameter (i.e. a threshold on path length orpath frequency) that has to be determined by a model
selection criterion (e.g. the cross validation error).
We will propose a kernel function based on the inner product between infinite dimensional path countvectors. A label path is produced by random walks ongraphs, and thus is regarded as a random variable. Our
kernel is defined as the inner product of the count vectors averaged over all possible label paths, which is regarded as a special case of marginalized kernels (Tsudaet al., 2002). The kernel computation boils down tofinding the stationary state of a discrete-time linear
system (Rugh, 1995), which can be done efficiently bysolving simultaneous linear equations with a sparse coefficient matrix. We especially notice that this computational trick is fundamentally different from the dynamic programming techniques adopted in other kernels (e.g. Watkins (2000), Lodhi et al. (2002), Collins
and Duffy (2001), Kashima and Koyanagi (2002)).
These kernels deal with very large but still finite dimensional feature spaces and have parameters to constrain the dimensionality (e.g. the maximum lengthof subsequences in Lodhi et al. (2002)). In order toinvestigate how our kernel performs well on the realdata, we will show promising results on predicting theproperties of chemical compounds.
This paper is organized as follows. In Section 2, we
review marginalized kernels as the theoretical foundation. Then, a new kernel between graphs is presented
in Section 3. In Section 4, we summarize the results ofour experiments on the classification of chemical compounds. Finally, we conclude with Section 5.

p(x|h)p(x0 |h)p(h),where h is a hidden variable, and x and x0 are visible
variables which correspond to structured data. Thiskernel requires p(x|h), which means that the generation process of x from h needs to be known. However,it may be the case that p(h|x) is known instead ofp(x|h). Then we can use a marginalized kernel (Tsudaet al., 2002) which is described as
K(x, x0 ) =XXhKz (z, z 0 )p(h|x)p(h0 |x0 ).

(1)

h0

where z = [x, h] and Kz (z, z 0 ) is the joint kernel depending on both visible and hidden variables. The
posterior probability p(h|x) can be interpreted as afeature extractor that extracts informative features forclassification from x. The marginalized kernel (1) isdefined as the expectation of the joint kernel over all
possible values of h and h0 . In the following, we
will construct a graph kernel in the context of themarginalized kernel. The hidden variable is a sequenceof vertex indices, which is generated by random walks
on the graph. Also the joint kernel Kz is defined as akernel between the sequences of vertex and edge labels
traversed in the random walk.

3. Graph Kernel
In this section, we introduce a new kernel between
graphs with vertex labels and edge labels. At the beginning, let us formally define a labeled graph. Denoteby G a labeled directed graph and by |G| the numberof vertices. Each vertex of the graph is uniquely indexed from 1 to |G|. Let vi ∈ Σv denote the labelof vertex i and eij ∈ ΣE denote the label of the edge
from i to j. Figure 1 shows an example of the graphsthat we handle in this paper. We assume that there
are no multiple edges between any vertices. Our task
is to construct a kernel function K(G, G0 ) between twolabeled graphs G and G0 .
3.1. Random Walks on Graphs
The hidden variable h = (h1 , . . . , h` ) associated withgraph G is a sequence of natural numbers from 1 to
|G|. Given a graph G, h is generated by a random walkas follows: At the first step, h1 is sampled from the    

would be a natural choice (Schölkopf & Smola, 2002).
The joint kernel is defined as the product of the label
kernels as follows:(` 6= `0 )

 0
Q`
0
0
0
K(vh1 , vh0 ) i=2 K(ehi−1 hi , eh0 h0 )×,Kz (z, z ) =
1
i−1 i


(` = `0 )K(vhi , vh0 0 )iwhere z = (G, h).
Figure 1. an example of graphs with labels

3.3. Efficient Computation
initial probability distribution ps (h). Subsequently, atthe i-th step, the next vertex hi is sampled subject tothe transition probability pt (hi |hi−1 ), but the random
walk may also end with probability pq (hi−1 ):K(G, G0 )
=

|G|

X

The marginalized kernel (1) is the expectation of Kz
over all possible h and h0 , which is described aspt (j|i) + pq (i) = 1.

(2)

∞ XX
X

ps (h1 )

h0

`=1 h

p(h|G) = ps (h1 )Ỳwhere ` is the length of h.
When we do not have any prior knowledge, we cab
set ps to be the uniform distribution, the transition
probability pt to be an uniform distribution over thevertices adjacent to the current vertex, and the termination probability pq to be a constant. Also gaps
(Lodhi et al., 2002) can be incorporated by setting thetransition probabilities appropriately.

j=20
k−1 ,hk

L→∞

Next we define the joint kernel Kz assuming that thehidden sequences h and h0 are given for two graphs G
and G0 , respectively. When the random walk is done
as described in h, the traversed labels are listed as)K(vhk , vh0 0 ),
k

L X
X

s(h1 , h01 ) ×(5)`=1 h1 ,h01

X

h2 ,h02t(h2 , h02 , h1 , h01 ) Xt(h3 , h03 , h2 , h02 )×h3 ,h03

· · · X

Assume that two kernel functions, K(v, v 0 ) andK(e, e0 ), are readily defined between vertex labels andedge labels, respectively. We constrain both kernels
K(v, v 0 ), K(e, e0 ) ≥ 0 to be nonnegative3 . An exampleof the vertex label kernels is
K(v, v 0 ) = δ(v = v 0 ),wheres(h1 , h01 ) :=2

K(v, v ) = exp(− k v − v k /2σ )ps (h1 )p0s (h01 )K(vh1 , vh0 01 )t(hi , h0i , hi−1 , h0i−1 ):= pt (hi |hi−1 )p0t (h0i |h0i−1 ) ×K(vhi , vh0 0i )K(ehi−1 hi , eh0i−1 h0i )(3)where δ is a function that returns 1 if its argument
holds, 0 otherwise. If the labels are defined in R, theGaussian kernelq(h` , h0` ):= pq (h` )p0q (h0` )Let us further simplify (5) as(4)This constraint will play an important role in proving
the convergence of the marginalized kernel in Section 3.4.

t(h` , h0` , h`−1 , h0`−1 )q(h` , h0` ) · · · h` ,h0`vh1 eh1 h2 vh2 eh2 h3 vh3 · · ·3K(ehk−1 hk , e0h0

K(G, G0 ) = lim


2

Ỳ

P
P|G|
P|G|
where h := h1 =1 · · · h` =1 . The straightforward
enumeration is obviously impossible, because ` spansfrom 1 to infinity. Nevertheless we have an efficient
way to compute this kernel as shown below. By rearranging the terms, the kernel has the following nested
structure.

3.2. Joint Kernel0p0t (h0j |h0j−1 )p0q (h0` ) ×

k=2

i=2

0

Ỳ

p0s (h01 )K(vh1 , vh0 01 )pt (hi |hi−1 )pq (h` ),pt (hi |hi−1 )pq (hl ) ×

i=2

j=1

The posterior probability for the label path h is described asỲ

K(G, G0 ) = lim

L→∞

L X
X
`=1 h1 ,h01s(h1 , h01 )r` (h1 , h01 ),where for ` ≥ 2,r` (h1 , h01 )


X
X
:= 
t(h2 , h02 , h1 , h01 ) t(h3 , h03 , h2 , h02 )×

h2 ,h02h3 ,h03

· · · Xt(h` , h0` , h`−1 , h0`−1 )q(h` , h0` ) · · ·  ,h` ,h0`and r1 (h1 , h01 ) := q(h1 , h01 ). Replacing the order ofsummation, we have the following:
K(G, G0 ) =Xs(h1 , h01 ) lim

L→∞h1 ,h01=Xs(h1 , h01 )h1 ,h01LXr` (h1 , h01 )`=1

lim RL (h1 , h01 ), (6)L→∞

Computing the kernel requires solving a linear equation with a |G||G0 | × |G||G0 | coefficient matrix. However, the matrix is actually sparse because the numberof non-zero elements is less than c2 |G||G0 | where c is
the maximum degree. Therefore, we can employ various kinds of efficient numerical algorithms that exploit
sparsity (Barrett et al., 1994). In our implementation,
we employed a simple iterative method that updates
current solutions by using (8) until convergence starting from R1 (h1 , h01 ) = r1 (h1 , h01 ).
3.4. Convergence Condition
The convergence condition needed to justify (9) is described as follows:
Theorem
1.
The
infinitesequence∈
limL→∞ RL (h1 , h01 ) converges for any h1{1, · · · , |G|} and h01 ∈ {1, · · · , |G0 |}, if the following inequality holds for i0 ∈ {1, · · · , |G|} andj0 ∈ {1, · · · , |G0 |},
0where
RL (h1 , h01 ) :=|G| |G |X
X

LXr` (h1 , h01 ).

t(i, j, i0 , j0 )q(i, j) < q(i0 , j0 ).

(10)

i=1 j=1`=1

Thus we need to compute R∞ (h1 , h01 ) to obtain
K(G, G0 ).
Now let us restate this problem in terms of linear system theory (Rugh, 1995). The following recursive relationship holds between rk and rk−1 (k ≥ 2):X
rk (h1 , h01 ) =t(i, j, h1 , h01 )rk−1 (i, j).
(7)i,jRL (h1 , h01 ) = r1 (h1 , h01 ) +

T
X

X̀ X

q(h1 , h01 ) +t(h2 , h02 , h1 , h01 ) 

i=2 h2 ,h02

X

h3 ,h03

· · · Xt(h3 , h03 , h2 , h02 )×

t(hi , h0i , hi−1 , h0i−1 )q(hi , h0i ) · · · T XXt(i, j, h1 , h01 )rk−1 (i, j)

k=2 i,jX:= q(h1 , h01 ) +X̀ui (h1 , h01 ),i=2

rk (h1 , h01 )k=2= r1 (h1 , h01 ) +R` (h1 , h01 ) =hi ,h0i

Using (7), the recursive relationship for RL also holds
as follows:= r1 (h1 , h01 ) +(proof) R` (h1 , h01 ) can also be described ast(i, j, h1 , h01 )RL−1 (i, j). (8)where ui (i ≥ 2) denotes the i-th term of the series. According to the ratio test, this series converges if lim supi→∞ |ui (h1 , h01 )|/|ui−1 (h1 , h01 )| < 1.
Since K(v, v 0 ) and K(e, e0 ) are nonnegative as previously defined, ui (h1 , h01 ) ≥ 0, and thus what we needto prove is lim supi→∞ ui (h1 , h01 )/ui−1 (h1 , h01 ) < 1. For
this purpose, it is sufficient to showi,jThus RL is perceived as a discrete-time linear system (Rugh, 1995) evolving as the time L increases.
Assuming that RL converges, (see Sec. 3.4 for the convergence condition), we have the following equilibrium
equation:X
R∞ (h1 , h01 ) = r1 (h1 , h01 ) +t(i, j, h1 , h01 )R∞ (i, j)ui (h1 , h01 )<1
ui−1 (h1 , h01 )for all i. The two terms in (11) are written asXai−1 (hi−1 , h0i−1 , h1 , h01 ) ×
ui (h1 , h01 ) =(12)

hi−1 ,h0i−1Xt(hi , h0i , hi−1 , h0i−1 )q(hi , h0i ),

hi ,h0ii,j(9)Therefore, the computation of the marginalized kernel finally comes down to solving linear simultaneous
equations (9) and substituting the solutions into (6).

(11)

ui−1 (h1 , h01 ) =Xai−1 (hi−1 , h0i−1 , h1 , h01 )q(hi−1 , h0i−1 ),hi−1 ,h0i−1(13)whereai−1 (hi−1 , h0i−1 , h1 , h01 ) :=X
h2 ,h02t(h2 , h02 , h1 , h01 ) t(h3 , h03 , h2 , h02 )×h3 ,h03

· · · XXt(hi−2 , h0i−2 , hi−3 , h0i−3 )×hi−2 ,h0i−2!

t(hi−1 , h0i−1 , hi−2 , h0i−2 )

!
··· .

Notice that ai−1 (hi−1 , h0i−1 , h1 , h01 ) ≥ 0 as well. Substituting (12) and (13) into (11), we haveXai−1 (hi−1 , h0i−1 , h1 , h01 ) ×
hi−1 ,h0i−1X

hi ,h0i<t(hi , h0i , hi−1 , h0i−1 )q(hi , h0i )X     

ai−1 (hi−1 , h0i−1 , h1 , h01 )q(hi−1 , h0i−1 ).

hi−1 ,h0i−1

Both sides of this inequality are the linear combinations of ai−1 (hi−1 , h0i−1 , h1 , h01 ) with nonnegative coefficients. In order to prove the inequality, it is sufficient
to prove the following inequalities for coefficients:Xt(i, j, i0 , j0 )q(i, j) < q(i0 , j0 ), ∀i0 , j0 ,i,jwhich we have assumed to hold in (10).
The condition (10) seems rather complicated, but we
can have a simpler condition, if the termination probabilities are constant over all vertices.
Lemma 1. If pq (i) = p0q (j) = γ for any i and j, theinfinite sequence limL→∞ RL (h1 , h01 ) converges if
K(v, v 0 )K(e, e0 ) <1.
(1 − γ)2(14)2(proof) Due to the assumption,
P q(i, j) = q(i0 , j0 ) = γ .
Thus it is sufficient to prove i,j t(i, j, i0 , j0 ) < 1, thatis,X
pt (i|i0 )p0t (j|j0 )K(vi , vj )K(ei0 i , ej0 j ) < 1. (15)Figure 2. A chemical compound is conventionally represented as an undirected graph (left). Atom types andbond types correspond to vertex labels and edge labels,
respectively. The edge labels ’s’ and ’d’ denote single anddouble bonds, respectively. As our kernel assumes a directed graph, undirected edges are replaced by directededges (right).

4. Experiments
We applied our kernel to prediction of the propertiesof chemical compounds. A chemical compound cannaturally be represented as an undirected graph byconsidering the atom types as the vertex labels, e.g.
C, Cl and H, and the bond types as the edge labels,
e.g. s (single bond) and d (double bond). For ourgraph kernel, we replaced an undirected edge by two
directed edges (Figure 2) since the kernel assumes directed graphs.
4.1. Pattern Discovery Algorithm
We compare our graph kernel with the patterndiscovery (PD) method by Kramer and De Raedt(2001) that is one of the best state-of-the-art methods in predictive toxicology. As in our graph kernel,
each feature is constructed as the count that a particular label path appears in the graph4 . There are othermethods which count more complicated substructures
such as subgraphs (Inokuchi et al., 2000), but we focus on Kramer and De Raedt (2001) whose featuresare similar to ours.
Assume that we have n graphs G1 , . . . , Gn . Also let
us define #(h, G) as the number of appearances of alabel path h in G. The PD method identifies a set of
all label paths H which appear in more than m graphs:
H = {h |i,jnXδ (# (h, Gi ) > 0) ≥ m},i=1

Due to Relation (2), we observe thatX
X
X
pt (i|i0 )p0t (j|j0 ) =pt (i|i0 )
p0t (j|j0 ) = (1−γ)2 .
i,j        ijThus (15) holds if all the coefficients satisfy
K(vi , vj )K(ei0 i , ej0 j ) < 1/(1 − γ)2 .
Apparently, the above lemma holds for λ > 0 if
K(·, ·) ≤ 1. Standard label kernels such as (3) and(4) satistfy this condition.

where the parameter m is called the minimum support
parameter. Furthermore, it is possible to add extra
conditions, e.g., selecting only the paths frequent in acertain class, and scarce in the other classes. Then thefeature vector of G based on the identified label paths
4

Notice that the definition of label paths is different
from ours in several points, e.g. a vertex will not be visited
twice in a path. See Kramer and De Raedt (2001) for
details.

is built as
G → (#(h1 , G), . . . , #(h|H| , G)),

(16)

whose dimensionality is the cardinality of H. The
PD method is useful for extracting comprehensive features. However, as the minimum support parametergets smaller, the dimensionality of feature vectors becomes so huge that a prohibitive amount of computation is required. Therefore, the user has to control theminimum support parameter m, such that the feature
space does not lose necessary information and, at thesame time, computation stays feasible.
The PD method contrasts markedly with our method.
Our kernel method puts emphasis on dealing with infinite, but less interpretable features, while the PD
method trys to extract a relatively small number of
meaningful features. Looking at the algorithms, ourmethod is so simple that it is described by just one
equation (9), while the PD method’s algorithm israther complicated (De Raedt & Kramer, 2001).
4.2. Datasets
We used two datasets, the PTC dataset (Helma et al.,2001) and the Mutag dataset (Srinivasan et al., 1996).
The PTC dataset is the results of the following pharmaceutical experiments. Each of 417 compounds is
given to four types of test animals: Male Mouse (MM),Female Mouse (FM), Male Rat (MR) and Female
Rat (FR). According to their carcinogenicity, eachcompound is assigned one of the following labels:{EE, IS, E, CE, SE, P, NE, N} where CE, SE and P indicate ”relatively active”, and NE and N indicate ”relatively inactive”, and EE, IS and E indicate ”can not
be decided”. In order to simplify the problem, we relabeled CE, SE and P as “positive”, and NE and N
as “negative”. The task is to predict whether a given
compound is positive or negative for each type of test
animals. Thus we eventually had four two-class problems.
In the Mutag dataset, the task is defined to be a twoclass classification problem to predict whether each of
the 188 compounds has mutagenicity or not.
Each statistics of the datasets are summarized in Table
1.
4.3. Experimental Settings and Results
Assuming no prior knowledge, we defined the probability distributions for random walks as follows. The
initial probabilities were simply uniform, i.e. ps (h) =1/|G|, ∀h. The termination probabilities were determined as a constant γ over all vertices. The transition
probabilities pt (h|h0 ) were set as uniform over adjacentvertices. We used Equation (3) as the label kernels.
In solving the simultanous equations, we employed asimple iterative method (8). In our observation, 20-30

Table 1. Several statistics of the datasets such as numbers of positive examples (#positive) and negative examples (#negative), maximum degree (max. degree), maximum size of graphs (max. |G|), average size of graphs (avg.
|G|), and numbers of vertex labels (|Σ|v ) and edge labels (|Σ|e ).

#positive#negative
max. |G|
avg. |G|
max. degree
|Σ|v
|Σ|e

MM

FM

MR

FR

Mutag

129
207
109
25.0
4
21
4

143
206
109
25.2
4
19
4

152
192
109
25.6
4
19
4

121
230
109
26.1
4
20
4

125
63
40
31.4
4
8
4

Table 2. Classification accuracies (%) of the pattern discovery method. ’MinSup’ shows the ratio of the minimum
support parameter to the number of compounds m/n.
MinSup

MM

FM

MR

FR

Mutag

0.5%
1%
3%
5%
10 %
20%

60.1
61.0
58.3
60.7
58.9
61.0

57.6
61.0
55.9
55.6
58.7
55.3

61.3
62.8
60.2
57.3
57.8
56.1

66.7
63.2
63.2
63.0
60.1
61.3

88.3
87.8
89.9
86.2
84.6
83.5

iterations were enough for convergence in all cases. For
the classification algorithm, we used the voted kernel
perceptron (Freund & Shapire, 1999), whose the performance is known to be comparable to SVMs. In thepattern discovery method, the minimum support parameter was determined as 0.5, 1, 3, 5, 10, 20% of thenumber of compounds, and the simple dot productin the feature space (16) was used as a kernel. In
our graph kernel, the termination probability γ waschanged from 0.1 to 0.9.
Table 2 and Table 3 show the classification accuracies
in the five two-class problems measured by leave-oneout cross validation. No general tendencies were foundto conclude which method is better (the PD was better in MR, FR and Mutag, but our method was betterin MM and FM). Thus it would be fair to say thatthe performances were comparable in this small setof experiments. Even though we could not show that
our method is constantly better, this result is still appealing, because the advantage of our method lies in
its simplicity both in concepts and in computational
procedures.

Table 3. Classification accuracies (%) of our graph kernel.
The parameter γ is the termination probability of random
walks, which controls the effect of the length of label paths.

where the feature matrix is defined as
Ma1 ,a2 (G) =∞ X
Xp(h1 , h` )δ(vh1 = σa1 )δ(vh` = σa2 ),`=1 h1 ,h`

γ

MM

FM

MR

FR

Mutag

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9

62.2
62.2
64.0
64.3
64.0
62.8
63.1
63.4
62.8

59.3
61.0
61.3
61.9
61.3
61.9
62.5
63.4
61.6

57.0
57.0
56.7
56.1
56.1
54.4
54.1
54.9
58.4

62.1
62.4
62.1
63.0
64.4
65.8
63.2
64.1
66.1

84.3
83.5
85.1
85.1
83.5
83.0
81.9
79.8
78.7

(17)
and Σv = {σ1 , σ2 , . . . , σ|Σv | }.
Notice that the probability p(h1 , h` ) is denoted asp(h1 , h` ) =ps (h1 )pq (h` ) ×XX···
pt (h2 |h1 ) · · · pt (h` |h`−1 ).
h2

Let T be a |G| × |G| matrix where Tij = pt (j|i).
Also, let S and Q be |G| × |Σv | matrices where Sij =ps (i)δ(vi = σj ) and Qij = pq (i)δ(vi = σj ), respectively. By means of these matrices, the feature matrix
is rewritten as

5. Conclusion
In this paper, we introduced a new kernel between
graphs with vertex labels and edge labels in the framework of the marginalized kernel. We defined the kernel by using random walks on graphs, and reduced
the computation of the kernel to solving a system of
linear simulataneous equations. As contrasted withthe pattern-discovery method, our kernel takes into
account all possible label paths without computing feature values explicitly. The structure we dealt with in
this paper is fairly general, as it includes sequences,
trees, DAGs and so on. Thus, applications of thiskernel are by no means limited to chemical compounds. Promising targets would be DNA and RNA
sequences with remote correlations, HTML and XML
documents, distance graphs of 3-D protein structures,and so on. Recently, we found that our kernel canalso be interpreted as an instance of the rational kernels (Cortes et al., 2003) over probability semiring. In
this interpretation, the probability distributions over agraph are considered as a weighted automaton. In furure works, we would like to explore how to deal with
infinite dimensions when another semiring is adopted.

Appendix: Relation to Exponential andGeometric Kernels for Labeled Graphs
Here we review the exponential and geometric kernels
between graphs proposed by Gärtner (2002) and describe the relation to our kernel. Although his kernels
are defined in a quite different formulation from ours,
we relate them by using the same notations.
His kernels are defined as the inner product of two|Σv | × |Σv | feature matrices M (G) and M (G0 ),h`

M (G) =∞X

S > T `−1 Q.

`=1In his settings, the parameters ps , pt and pq do nothave stochastic constraints, i.e. ps (i) = 1 and pq (i) =1 for any vertex i. Therefore, S = Q := L, where
Lij = δ(vi = j).
Thevector of geometric kernel, M (G) =P∞ feature>``=1 L (βE) L, is obtained by setting T = βE,
where E is the adjacency matrix of G and β is a constant to assure convergence.
In the case
P∞of exponential kernel, M is defined as
M (G) = `=1 (L> (βE)`−1 L)/(` − 1)!, which still results in a similar form.
As seen in (17), the primary difference from our approach is that they only take the vertex labels at bothends (h1 , h` ) into account. Although this simplification allows to keep the size of the matrices small, it
might be harmful when contiguous labels are essential as in chemical compounds. Another difference isthat they do not use an infinite dimensional feature
space. Although they also compute the infinite sum inEquation (17), the infinite sum is for obtaining |Σv |2
dimensional feature vectors.

References
Abiteboul, S., Buneman, P., & Suciu, D. (2000). Dataon the Web: from relations to semistructured data
and XML. Morgan Kaufmann.
Bahlmann, C., Haasdonk, B., & Burkhardt, H. (2002).
On-line handwriting recognition with support vector
machines – a kernel approach. Proc. of the 8th Int.
Workshop on Frontiers in Handwriting Recognition(IWFHR) (pp. 49–54).

|Σv | |Σv |K(G, G0 ) =X X

a1 =1 a2 =1

Ma1 ,a2 (G)m0a1 ,a2 (G0 ),Barrett, R., Berry, M., Chan, T. F., Demmel, J.,
Donato, J., Dongarra, J., Eijkhout, V., Pozo, R.,Romine, C., & der Vorst, H. V. (1994). Templates
for the solution of linear systems: Building blocks
for iterative methods, 2nd edition. Philadelphia, PA:
SIAM.

Kondor, R. I., & Lafferty, J. (2002). Diffusion kernels
on graphs and other discrete input spaces. Proc. of
the 19th ICML (pp. 315–322).

Collins, M., & Duffy, N. (2001). Convolution kernel
for natural language. Proc. of the 14th NIPS.

Kramer, S., & De Raedt, L. (2001). Feature construction with version spaces for biochemical application.
Proc. of the 18th ICML (pp. 258–265).

Cortes, C., Haffner, P., & Mohri, M. (2003). Rational
kernels. Advances in Neural Information Processing
Systems 15. MIT Press. In press.

Lafferty, J., & Lebanon, G. (2003). Information diffusion kernels. Advances in Neural Information Processing Systems 15. MIT Press. In press.

De Raedt, L., & Kramer, S. (2001). The levelwise version space algorithm and its application to molecular fragment finding. Proceedings of the 17th International Joint Conference on Artificial Intelligence(pp. 853–862). Morgan Kaufmann.

Leslie, C., Eskin, E., Weston, J., & Noble, W. (2003).
Mismatch string kernels for svm protein classification. Advances in Neural Information Processing
Systems 15. MIT Press. In press.

Durbin, R., Eddy, S., Krogh, A., & Mitchison, G.
(1998). Biological sequence analysis: Probabilistic
models of proteins and nucleic acids. Cambridge
University Press.
Freund, Y., & Shapire, R. (1999). Large margin classification using the perceptron algorithm. Machine
Learning, 37, 277–296.
Gärtner, T. (2002). Exponential and geometric kernels for graphs. NIPS*02 Workshop on Unreal Data:
Principles of Modeling Nonvectorial Data. Available
from http://mlg.anu.edu.au/unrealdata/.
Haussler, D. (1999). Convolution kernels on discrete structures (Technical Report UCSC-CRL-9910). University of Calfornia in Santa Cruz.
Helma, C., King, R., Kramer, S., & Srinivasan, A.
(2001). The Predictive Toxicology Challenge 20002001. Bioinformatics, 17, 107–108.
Inokuchi, A., Washio, T., & Motoda, H. (2000). An
Apriori-based algorithm for mining frequent substructures from graph data. Proc. of the 4th PKDD
(pp. 13–23).
Jaakkola, T., Diekhans, M., & Haussler, D. (2000). A
discriminative framework for detecting remote protein homologies. Journal of Computational Biology,
7, 95–114.
Kandola, J., Shawe-Taylor, J., & Cristianini, N.
(2003). Learning semantic similarity. Advances in
Neural Information Processing Systems 15. MIT
Press. In press.
Kashima, H., & Inokuchi, A. (2002). Kernels for graphclassification. IEEE ICDM Workshop on Active
Mining. Maebashi, Japan.
Kashima, H., & Koyanagi, T. (2002). Kernels for semistructured data. Proc. of the 19th ICML (pp. 291–
298).

Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., & Watkins, C. (2002). Text classification
using string kernels. Journal of Machine Learning
Research, 2, 419–444.
Manning, C. D., & Schütze, H. (1999). Foundations ofstatistical natural language processing. Cambridge,
Massachusetts: The MIT Press.
Rugh, W. (1995). Linear system theory. Prentice Hall.
Schölkopf, B., & Smola, A. J. (2002). Learning withkernels. Cambridge, MA: MIT Press.
Shimodaira, H., Noma, K.-I., Nakai, M., & Sagayama,
S. (2002). Dynamic time-alignment kernel in support vector machine. Advances in Neural Information Processing Systems 14 (pp. 921–928). Cambridge, MA: MIT Press.
Srinivasan, A., Muggleton, S., King, R. D., & Sternberg, M. (1996). Theories for mutagenicity: a studyof first-order and feature based induction. Artificial
Intelligence, 85, 277–299.
Takimoto, E., & Warmuth, M. K. (2002). Path kernels
and multiplicative updates. Proc. of the 15th Annual
Conference on Computational Learning Theory (pp.
74–89).
Tsuda, K., Kin, T., & Asai, K. (2002). Marginalized
kernels for biological sequences. Bioinformatics, 18,
S268–S275.
Vapnik, V. (1998). Statistical learning theory. New
York: Wiley.
Vishwanathan, S., & Smola, A. (2003). Fast kernels
for string and tree matching. Advances in Neural
Information Processing Systems 15. MIT Press. In
press.
Watkins, C. (2000). Dynamic alignment kernels. In
A. Smola, P. Bartlett, B. Schölkopf and D. Schuurmans (Eds.), Advances in large margin classifiers,
39–50. MIT Press.