TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol. 12, No. 10, Octobe
r 20
14, pp. 7501
~ 750
8
DOI: 10.115
9
1
/telkomni
ka.
v
12i8.565
0
7501
Re
cei
v
ed
Jan
uary 19, 201
4
;
Revi
sed Au
gus
t 3, 201
4; Acce
pted Au
gust 25, 20
14
Graph Kernels and Applications in Protein
Classification
Jiang Qiangr
ong*, Xiong zhikan
g, Zha
i Can
Dep
a
rtment of Comp
uter Scie
nce, Beij
ing
U
n
iversit
y
of T
e
chnol
og
y, Beij
in
g, Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: jian
gqi
an
gron
g@gma
il.com
A
b
st
r
a
ct
Protein cl
assifi
cation is a w
e
ll esta
blis
he
d
res
earch fie
l
d concer
ne
d w
i
th the disco
very of
mo
lec
u
le
’
s
pro
perties thro
ug
h infor
m
a
t
ion
a
l
techniq
ues. Graph-
base
d
ke
rnels pr
ovid
e
a nice fra
m
ew
ork
combi
n
in
g mac
h
in
e lear
nin
g
techn
i
qu
es w
i
th graph the
o
ry. In this pap
er we introd
uce a n
o
vel gr
aph ker
n
e
l
meth
od f
o
r a
n
notatin
g functi
ona
l resi
du
es i
n
prote
i
n st
ruc
t
ures. A structure
is first mo
del
ed
as a
pro
t
ei
n
contact gra
ph,
w
here no
des
corres
pond to r
e
sid
ues a
nd e
dges c
onn
ect spatia
lly n
e
ig
h
bori
ng res
i
due
s. In
exper
iments
o
n
cl
assificati
on
of gr
ap
h
mo
dels
of
protei
ns, the
metho
d
b
a
se
d o
n
W
e
isfeiler-
Le
h
m
a
n
shortest path k
e
rne
l
w
i
th comple
ment gra
p
h
s
outperfor
m
e
d
other state-of-art meth
ods.
Ke
y
w
ords
:
pr
otein cl
assificat
i
on, mach
ine l
e
arni
ng, gra
ph k
e
rne
l
s, W
e
isfeil
er-Le
h
m
an
Co
p
y
rig
h
t
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Kernel
metho
d
s a
r
e
an im
portant m
e
th
od which is
widely u
s
e
d
i
n
statisti
cal l
earni
ng
theory [1]. Ke
rnel
s h
e
lp to
adapt
cla
ssifi
cation
re
gardl
ess ho
w
cla
s
sificatio
n
pe
rf
orm
s
. That i
s
to
say,
kernel
s act
li
ke an
int
e
rface betwe
en cla
ssi
fi
cati
on
tool
s and
data sets
via Suppo
rt
Ve
ctor
Machi
n
e
s
[2]. Early studies on
kernel
methods
d
e
a
lt almost e
x
clusively wit
h
vector-ba
s
ed
descri
p
tion
s
of input d
a
ta
. This
pro
c
e
dure,
th
oug
h
co
nvenient,
doe
s n
o
t al
ways effectiv
ely
captu
r
e top
o
l
ogical rel
a
tio
n
shi
p
s in
he
rent to
the d
a
ta; therefo
r
e, t
he power of the learn
i
n
g
pro
c
e
ss may
be insufficie
n
t. Haussle
r
[3] was the first to define a princi
pled way of designi
ng
kernel
s on structured
obje
c
ts,
the
so
-call
ed
R-co
nvolu
t
ion kernel. O
v
er recent ye
ars,
kern
els o
n
stru
ctured
ob
jects such a
s
strin
g
s an
d
trees
,
on
no
des in
gra
p
h
s
a
nd
on g
r
a
phs have
be
en
defined.
Gra
phs are nat
ural data
struct
ure
s
to
m
ode
l
su
ch structu
r
es, with nod
es rep
r
e
s
enti
n
g
obje
c
ts
and
edge
s th
e
re
lations bet
we
en the
m
. In
this
context, one
often
e
n
co
unters t
w
o
que
stion
s
: “How
similar
are two no
de
s
or ed
ge
s
in a
given graph
?” an
d “Ho
w
simila
r are two
grap
hs to ea
ch other?
”
For insta
n
ce, in protein cl
a
ssifi
cation, on
e mi
ght want to predi
ct wh
ether a given
protein
is a
n
e
n
zym
e
or not.
Com
putational
ap
proa
ch
es
infe
r p
r
otein
fun
c
tion by findi
n
g
p
r
otein
s
wit
h
simila
r se
que
nce,
stru
cture
,
or ch
emical
prop
ertie
s
. A very su
cces
sf
ul re
cent met
hod is to m
o
d
e
l
the protein a
s
a
gra
ph, a
nd a
ssi
gn
si
milar fun
c
tion
s to
simila
r g
r
aph
s [4]. Ge
nerally
spe
a
king,
grap
h kern
els are b
a
sed on
the com
pari
s
on of gr
aph
-substructu
re
s
via kernel
s. Several differe
nt
grap
h
kernel
s h
a
ve be
en
defined
in
machi
ne
l
earning
whi
c
h
can be
categ
o
rized i
n
to t
h
ree
cla
s
ses: g
r
ap
h ke
rnel
s ba
sed o
n
walks [5] and path
s
[6], graph
kernel
s b
a
sed
on limited-si
ze
sub
g
ra
ph
s [7,
8], and
gra
p
h
ke
rn
els
ba
sed on
subtre
e patterns [5, 9]. To defin
e
a g
r
aph
kern
el,
some
requi
re
ments are p
u
t
forwar
d: th
e
ke
rn
el
shoul
d be
me
asur
able
on th
e i
s
sue
of si
mil
a
rity
for gra
ph; se
con
d
, it shou
ld be comput
able in a
n
accepta
b
le time
; third, it sho
u
ld be p
o
sitiv
e
definite; fourth, it should b
e
appli
c
able
widely. Ho
we
ver, some of
the ker
nel
s cannot meet a
ll of
these
req
u
ire
m
ents. In thi
s
pape
r, we
prese
n
t a
ne
w
grap
h kernel
that mea
s
ure
simila
rity based
on Weisfeil
er-Leh
man
sh
o
r
test p
a
th in
undirect
e
d
g
r
aph
s, that are co
mputabl
e in polyn
om
ial
time, that are positive semi
definite.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
1
– 7508
7502
2. Basic Kno
w
l
e
d
g
e
2.1. Some Definitions on
Graph The
o
r
y
We define a
grap
h G as a
triplet
)
,
,
(
l
E
V
, where
V
is the set of vertices,
E
is the set
of undirecte
d
edge
s, an
d
V
l
:
is a fun
c
tion
that assign
s label
s from
an alp
habet
to
node
s in
the
grap
h. The
n
e
ighb
orh
ood
)
(
v
of a no
de
v
is the
set of
node
s to
whi
c
h
v
is
con
n
e
c
ted by an edge, that is
E
v
v
v
v
)
,
(
)
(
'
'
. We assume that e
v
ery graph h
a
s
n
node
s,
m
edge
s, and a maxi
mum deg
ree
of
d
.
The adja
c
e
n
cy matrix
A
of
G
is define
d
as f
o
llows:
,
0
,
)
,
(
1
otherwise
E
v
v
if
A
j
i
ij
Whe
r
e
i
v
and
j
v
are n
ode
s in
G
. Label
s can
be ad
ded o
n
node
s o
r
ed
g
e
s, the
s
e la
b
e
ls a
r
e
referred a
s
at
tributes.
A
wal
k
w
of l
ength
1
k
in
a grap
h
i
s
a seque
nce
of
node
s
k
v
v
v
,
,
,
2
1
whe
r
e
E
v
v
i
i
)
,
(
1
for
k
i
1
.
A
path
p
is a walk with
out sa
me node
s in the se
que
nce.
A
cycl
e
is a walk with
k
v
v
1
,a simple cycl
e do
es not have a
n
y repeate
d
node
s exce
pt
for
1
v
.
Suppo
se
)
,
(
E
V
G
is a graph
with vertex set
V
and
edge set
E
. Then, its co
mp
lement
)
,
(
E
V
G
is a grap
h wi
th the same
vertex set
V
, but with a different edg
e set
E
V
V
E
\
.
In other word
s, the
co
mpl
e
ment g
r
a
p
h
is
made
up
of all the
ed
ges missin
g f
r
om th
e o
r
igi
nal
grap
h.
2.2. Graph Is
omorphism
Grap
h
simila
rity or i
s
omo
r
p
h
ism
[10] i
s
t
he
m
o
st
esse
ntial proble
m
for le
arni
ng ta
sks li
ke
c
l
us
te
r
i
ng
and
c
l
a
s
s
i
fica
tion
o
n
gr
a
p
h
s
.
In
gr
a
p
h
th
e
o
ry, a
n
iso
m
or
ph
is
m o
f
gr
a
phs
G
and
H
is
a bijection b
e
twee
n the vertex sets of
G
and
H
:
)
(
)
(
:
H
V
G
V
f
, such that any two
ver
t
ic
es
u
and
v
of
G
are adj
a
c
ent in
G
if an
d only if
)
(
u
f
and
)
(
v
f
are adja
c
en
t in
H
.
Grap
h iso
m
orphism p
r
o
b
le
m is neithe
r
known to
be p
o
lynomial
-
co
mputable, no
r NP-ha
r
d [11]
.
3. The Weis
feiler-Lehma
n
Test o
f
Iso
m
orphism
Our meth
od
use
s
con
c
ept
s from the
Weisfeile
r-Leh
man test of i
s
omo
r
p
h
ism
[12, 13],
more
spe
c
ifically its 1
-
dim
e
nsio
nal va
ria
n
t. Assume
we are give
n t
w
o
gra
p
h
s
G
a
nd
H
and
we
woul
d like to
test whethe
r
they are
iso
m
orp
h
ic.
T
h
e
1-di
m Weisf
e
iler-Le
hman
test p
r
o
c
ee
d
s
in
iteration
s
, whi
c
h we index b
y
i
and which comp
ri
se the
step
s given in
Algorithm 1.
The key idea
of the algo
rithm is to a
u
g
m
ent the no
d
e
label
s by th
e so
rted
set
of node
label
s of
nei
ghbo
ring
no
d
e
s, a
nd
co
m
p
re
ss the
s
e
augme
n
ted l
abel
s into
ne
w, sho
r
t lab
e
l
s.
These step
s are
th
en re
p
eated until
th
e
no
de
la
bel sets
of
G
and
H
diffe
r
,
o
r
the
nu
mb
er
o
f
iteration
s
rea
c
he
s
n
. If the sets a
r
e i
denti
c
al
after
n
ite
r
ation
s
, it me
ans that eith
e
r
G
and
H
are i
s
om
orp
h
i
c, or the
alg
o
rithm h
a
s
n
o
t been
abl
e to
determi
ne that
they
are
not isom
orphi
c.
See Figure 1, for an illust
ration of these
steps.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Grap
h Kern
el
s and Appli
c
a
t
ions in Protei
n Cla
ssifi
cati
on (Ji
ang Qi
a
ngro
n
g
)
7503
Algorithm
1.
One iteratio
n of the 1-dim. Wei
s
feiler-L
e
h
man test of
grap
h iso
m
orphism
(19
68)
1. Multiset-la
bel determina
tion
a. For
,
s
e
t
)
(
)
(
0
v
l
v
M
i
.
b. For
0
i
, assign
a multiset-lab
el
to ea
ch n
o
de
v
in
G
and
H
w
h
ic
h
c
o
ns
is
ts
o
f
the multiset
)
(
)
(
1
u
u
u
l
i
.
2. Sorting ea
ch multiset
a.
Sort element
s in
)
(
v
M
i
in ascen
d
ing orde
r an
d con
c
ate
nat
e them into a string
)
(
v
s
i
.
b. Add
)
(
1
v
l
i
as a pre
f
ix to
)
(
v
s
i
and call
the resulting string
)
(
v
s
i
.
3. Label com
p
re
ssi
on
a.
Sort all of the string
s
)
(
v
s
i
for all
v
from
G
and
H
in ascen
d
ing
orde
r.
b. Map
e
a
ch
string
)
(
v
s
i
to a n
e
w
comp
re
sse
d
label,
usi
n
g a fun
c
tion
*
:
f
su
ch
that
))
(
(
))
(
(
w
s
f
v
s
f
i
i
iff
)
(
)
(
w
s
v
s
i
i
.
4. Relabeli
n
g
a. Set
))
(
(
)
(
v
s
f
v
l
i
i
for all nodes in
G
and
H
.
Figure 1.
Illustration of the 4 Steps of On
e Iteration of
the Com
putati
on of the Wei
s
feiler-L
ehma
n
Test of Isomo
r
phi
sm
4. The Weis
feiler-Lehma
n
Shortes
t
Path Kernel
In each ite
r
ati
on
i
of the Weisfeile
r-Leh
man algo
rith
m (se
e
Algori
t
hm 1), we g
e
t a new
labeling
)
(
v
l
i
for a
ll node
s
. Re
call th
at this labelin
g is co
nco
r
da
nt in
and
, meani
n
g
that if nod
es
in
and
H
hav
e identical
m
u
ltiset label
s, and
only i
n
this
case, they will
get
identical new
label
s. Therefore, we
can i
m
agine
o
ne iteration of We
isfeiler-L
ehm
an rela
belin
g as
a function
)
,
,
(
))
,
,
((
1
i
i
l
E
V
l
E
V
r
that transfo
rm
s all graph
s in
the same m
a
nner. Note that
r
depe
nd
s on the set of grap
hs that we
co
nsid
er.
0
i
T
h
e
i
m
a
g
e
p
a
r
t
w
i
t
h
r
e
l
a
t
i
o
n
sh
i
p
I
D
r
I
d
113 w
a
s n
o
t
f
o
u
n
d
i
n
t
h
e
f
i
l
e
.
v
G
H
G
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
1
– 7508
7504
4.1. Weisfeiler-Le
hman S
e
quen
ce Gra
phs
Define th
e Weisfeile
r-Leh
man g
r
aph
at height
i
of the grap
h
)
,
,
(
l
E
V
G
as the
grap
h
)
,
,
(
i
i
l
E
V
G
. We call the
seq
uen
ce of
Wei
s
feiler-L
e
h
man g
r
ap
hs,
)},
,
,
(
,
),
,
,
(
),
,
,
{(
}
,
,
,
{
1
0
1
0
h
h
l
E
V
l
E
V
l
E
V
G
G
G
Whe
r
e
G
G
0
, the
Wei
s
feiler-L
e
h
man sequ
e
n
ce u
p
to he
ight
h
of
G
.
0
G
is the original
grap
h,
)
(
0
1
G
r
G
is the grap
h re
sultin
g from the first relabelin
g, and so o
n
.
4.2. Weisfeiler-Lehman Kern
el w
i
t
h
Complement
Graphs
Let
be any
kernel for graphs, that we
will call the base
kernel. Then the
Wei
s
feiler-
Lehma
n
ke
rn
el with
h
iterations
with the base ke
rnel
k
is define
d
as:
).
,
(
)
,
(
)
,
(
)
,
(
1
1
0
0
h
h
h
WL
H
G
k
H
G
k
H
G
k
H
G
k
If we take the complem
e
nt graphs int
o
co
nsi
d
erati
on, we will
derive the
Weisfeiler-
Lehma
n
ke
rn
el with com
p
l
e
ment graph
s:
)
,
(
)
,
(
)
,
(
)
,
(
1
1
0
0
0
0
H
G
k
H
G
k
H
G
k
H
G
k
h
wl
),
,
(
)
,
(
)
,
(
1
1
h
h
h
h
H
G
k
H
G
k
H
G
k
Whe
r
e
)
,
,
,
(
),
,
,
,
(
1
0
1
0
h
h
H
H
H
G
G
G
a
r
e
compl
e
ment graph
s of
),
,
,
,
(
1
0
h
G
G
G
).
,
,
,
(
1
0
h
H
H
H
Let the base kernel
k
be any positi
v
e semidefin
ite kern
el on
graph
s. Th
en the
corre
s
p
ondin
g
Wei
s
feiler-L
ehman
ke
rnel
h
WL
k
is positive semidefinite.
4.3. Shortes
t
Path and Fl
o
y
d-Warshal
l
Algorithm
Given a
n
un
dire
cted
gra
p
h
)
,
(
E
V
G
the sh
ort
e
st p
a
th g
r
a
ph [14],
)
,
(
'
E
V
G
sp
,
whi
c
h contai
ns the same
set of vertice
s
as
and the
edge bet
we
en every pai
r of vertices is
labele
d
with
the
sho
r
test
di
stan
ce
betwe
en them
in
th
e ori
g
inal
gra
ph. The
tra
n
sformation
fro
m
to
can b
e
p
e
rform
ed by
any all-p
a
irs
sho
r
test
p
a
th
algorith
m
. Flo
y
d–Wa
r
shall
algorithm
(See Algorith
m
2) [15] is attractive an
d effect
ive beca
u
se it is straig
htforward and ha
s time
compl
e
xity of
. Then, a kernel fun
c
tion
wa
s
u
s
ed to
cal
c
ulate th
e
simila
rity betwee
n
two
sho
r
test
pat
h gra
p
h
s
a
c
cording to
the follo
wing
definition
s
, whi
c
h
were
first defin
ed
by
Borg
wardt an
d Krieg
e
l [6]. It is prove
d
to
be a
po
sitive semi
definite
kernel
and i
s
comp
utable
i
n
polynomial ti
me.
Algorithm
2.
Floyd–Warsh
all algorith
m
(Grap
h
with
node
s and a
d
j
a
ce
ncy matri
x
A
)
Floyd(
G
)
for
n
k
to
1
for
n
i
to
1
for
n
j
to
1
if(cost(
k
i
,
)+
co
st
(
j
k
,
)<
co
st
(
j
i
,
))
co
st
(
j
i
,
)=
co
st
(
k
i
,
)+c
o
st
(
j
k
,
)
endif
endfor
endfor
endfor
k
G
G
sp
G
)
(
3
n
O
G
n
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Grap
h Kern
el
s and Appli
c
a
t
ions in Protei
n Cla
ssifi
cati
on (Ji
ang Qi
a
ngro
n
g
)
7505
Let
1
e
be the edge co
nne
cti
ng vertice
s
1
v
and
1
w
on grap
h
G
, and
2
e
be the edge
con
n
e
c
ting n
ode
s
2
v
and
2
w
on graph
H
. A wal
k
on
an e
dge in
clu
d
e
s
the edg
e an
d
its two
adja
c
ent ve
rtice
s
. A walk
kernel
walk
k
is u
s
ed to
comp
are the walk
1
e
and
2
e
as:
,
)
,
(
*
)
,
(
*
)
,
(
)
,
(
2
1
2
1
2
1
2
1
w
w
k
e
e
k
v
v
k
e
e
k
node
edge
node
walk
whe
r
e
node
k
is
the
ke
rnel
functio
n
fo
r
comp
ari
ng two vertice
s
, and
edge
k
is
a k
e
rnel func
tion for
co
mpa
r
ing two
edg
es.
The
ke
rnel
fu
nction
for co
mpari
ng t
w
o
vertice
s
u
an
d
v
is a
Ga
ussia
n
kernel [1
6]
over
their re
sp
ecti
ve feature vectors,
.
2
)
(
)
(
exp
)
,
(
2
2
v
f
u
f
v
u
k
node
The kern
el fu
nction fo
r co
mpari
ng two
edge
s
e
and
f
is a Brownian
bridg
e
kern
el
that
assign
s the h
i
ghe
st value to edge
s
with
identical
wei
g
hts, and 0 to
all edge
s that
differ in wei
g
ht
more tha
n
a consta
nt
c
:
).
)
(
)
(
,
0
max(
)
,
(
f
length
e
length
c
f
e
k
edge
In this pape
r, we u
s
e
c
= 2.
4.4. Shortes
t
Path Ker
n
el
Given two
shorte
st p
a
th
grap
hs
)
,
(
1
1
E
V
G
and
the
sh
orte
st path
grap
h
kernel:
),
,
(
)
,
(
2
1
1
12
2
e
e
k
H
G
k
E
eE
e
walk
sp
Whe
r
e
walk
k
is a kernel fun
c
tion
for comp
arin
g two edg
e walks of length
1.
Floyd-tra
n
sfo
r
mation re
qui
res
time.
1
E
and
contai
n
)
(
2
n
O
edge
s. T
he
comp
utation
of the sho
r
test
-path graph
kernel requi
re
s
)
(
4
n
O
time.
4.5. Weisfeiler-Le
hman S
horte
st Pa
th Kernel
w
i
th Complement Graphs
With the a
b
o
v
e definition
s
, we a
r
e
rea
d
y to define
Wei
s
feiler-L
e
hman
sho
r
te
st path
kernel with
co
mpleme
nt gra
phs a
s
:
.
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
1
1
1
1
0
0
0
0
h
h
sp
h
h
sp
sp
sp
sp
sp
h
WL
H
G
k
H
G
k
H
G
k
H
G
k
H
G
k
H
G
k
H
G
sp
k
For
N
graphs, the runtim
e of WL shor
test
path kernel
will scal
e
as
.
5. Experiments
5.1. Experimental Setting
s
We compa
r
e
d
the perfo
rm
ance of the random
wa
l
k
grap
h ke
rn
el [17], the shortest path
kernel, the
WL Sho
r
test
Kernel with
out com
p
lem
ent gra
p
h
s
a
nd WL Sh
ort
e
st Kern
el with
compl
e
me
nt grap
hs i
n
terms of cla
s
sification
a
c
cu
ra
cy
of
t
he cla
ssi
fi
cation o
n
D&D [18] a
nd
ENZYMES dataset
s, whe
r
e accura
cy
shows the ov
erall pe
rcent
age
of co
rre
c
t cla
ssifi
cati
ons.
D&D i
s
a d
a
taset
of 691
enzyme
s
and
487
non
-e
n
z
ymes. E
a
ch
protei
n i
s
re
pre
s
ente
d
by
a
grap
h,
in whi
c
h
the nod
es are amino aci
d
s
a
nd
two n
ode
s a
r
e
con
necte
d by an
edge if they a
r
e
less than 6
Ångstroms
a
part. The ta
sk is to
cla
ssif
y
the protein
stru
ctures in
to enzyme
s
and
)
,
(
2
2
E
V
H
)
(
3
n
O
2
E
)
(
4
2
n
N
O
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
1
– 7508
7506
non-en
zyme
s. ENZYMES is a d
a
ta set
of protein
tert
iary structu
r
e
s
obtai
ned f
r
om Borgwa
rd
t e
t
al(20
0
5
)
, con
s
istin
g
of
60
0 en
zyme
s from th
e
BRE
NDA
en
zyme
datab
ase(S
c
hombu
rg
et al
.,
2004
). In thi
s
ca
se
the
task i
s
to
corre
c
tly assi
gn
ea
ch
en
zyme t
o
on
e
of the
6 EC top
-
lev
e
l
cla
s
ses.
Nod
e
s a
r
e lab
e
le
d in the data
s
et. In te
rm
s of D&D, we also a
nalyze
d the se
nsitiv
ity,
spe
c
ificity, a
nd Matthe
w
s co
rrel
a
tion
coefficient
(M
CC)[19] of th
e cla
s
sificatio
n
s in
ad
ditio
n
to
accuracy
(Ta
b
le 3
)
, where
se
nsitivity is t
he pe
rcent
age
of en
zymes th
at hav
e be
en
co
rre
ctly
cla
ssifie
d
as
enzyme
s
, specifi
c
ity indicate
s the pe
rce
n
tage of
non-
en
zyme
s that have bee
n
corre
c
tly cl
assified, a
nd
MCC sho
w
s
the overl
appi
ng b
e
twe
en t
he p
r
edi
ction
s
a
nd th
e a
c
tual
distrib
u
tion.
Suppo
se P repre
s
e
n
ts po
sitive instan
ces N
ne
gative instan
ce
s, TP
the numb
e
r of true
positive
s
, TN the numbe
r o
f
true negatives, FP t
he nu
mber of false positive
s
and
FN the num
b
e
r
of false
ne
gat
ives. Th
en th
e a
c
cura
cy,
sensitivit
y, spe
c
ificity an
d M
C
C can
be
calcul
ated
by the
following formulas
,
N
P
TN
TP
accuracy
,
FN
TP
TP
P
TP
y
sensitivit
,
TN
FP
TN
N
TN
y
specificit
,
.
)
)(
)(
)(
(
FN
TN
FP
TN
FN
TP
FP
TP
FN
FP
TN
TP
MCC
We perfo
rme
d
10
-fold cro
s
s-valid
ation o
f
C-
Su
ppo
rt V
e
ctor Ma
chi
n
e Cl
assification u
s
in
g
LIBSVM [20], using 9 folds for tr
aining and the rest one for testin
g. All parameters of the SVM
were optimi
z
ed on the training data
set
only. To ex
cl
ude rand
om effects of fold
assi
gnm
ents, we
repe
ated the
whole exp
e
r
iment 10 ti
mes. We sh
ow ave
r
age
cla
ssifi
cation
accuraci
es
and
stand
ard
dev
iations in T
a
ble 1. Table
2 sho
w
s
the
size of both
data set a
n
d
runtime of the
method
s co
m
puting on the
m
.
Table 1. The
Cla
ssifi
cation
Accu
ra
cy(%) and Standa
rd Deviation of
each Ke
rnel
on Protein
Da
ta
Sets
Method/Data set
D&D
ENZY
MES
Random Walk Kernel
70.26(±0.
86)
20.14(±0.
69)
Shortest Path Ke
rnel
78.19(±0.
26)
42.18(±0.
43)
WL Shortest Pat
h
Kernel
w
i
thout
complement gra
phs
81.27(±0.
70)
62.47(±0.
61)
WL Shortest Pat
h
Kernel
w
i
th co
mplement graph
s
83.64(±0.
92)
63.96(±0.
84)
Table 2. CP
U Runtime for
Kernel
Co
mp
utation on Protein Cla
s
sification
Data set
D&D
ENZY
MES
Class si
ze
2
6
Maximum nodes
5478
126
Average nodes
284.32
32.63
Number of
graph
s
1178
600
Random Walk Kernel
52da
y
s
39da
y
s
Shortest Path Ke
rnel
25h 17min22s
38s
WL Shortest Pat
h
Kernel
w
i
thout
complement gra
phs
64da
y
s
1min3s
WL Shortest Pat
h
Kernel
w
i
th co
mplement graph
s
71da
y
s
2min11s
Table 3. Co
m
pari
s
on of ou
r Method with
others usi
ng
D&D Data Se
t
Method
Sensitiv
ity
Specific
ity
MCC
Random Walk Kernel
65.28%
71.35%
0.523
Shortest Path Ke
rnel
71.32%
79.64%
0.736
WL Shortest Pat
h
Kernel
w
i
thout
complement gra
phs
78.24%
83.77%
0.821
WL Shortest Pat
h
Kernel
w
i
th co
mplement graph
s
81.05%
86.13%
0.836
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Grap
h Kern
el
s and Appli
c
a
t
ions in Protei
n Cla
ssifi
cati
on (Ji
ang Qi
a
ngro
n
g
)
7507
5.2. Results
In terms of runtime, The
sho
r
test path
ke
rn
el and t
he WL
sho
r
t
e
st path kern
el were
comp
etitive to the rand
om
walk kernel
on sm
all
e
r g
r
aph
s (ENZY
M
ES), but on D&D their ru
ntime
dege
nerated
to more th
an
25 ho
urs for the sh
orte
st
path kern
el, 64 day
s for t
he WL short
e
st
path kern
el
without
comp
lement g
r
aph
s an
d 71 d
a
y
s for the
WL sh
orte
st p
a
th ke
rnel
wi
th
compl
e
me
nt grap
hs. Usin
g a grap
h to model the
di
stribution of a
m
ino aci
d
re
sidue
s on the
3D
stru
cture, ou
r meth
od effi
ciently
captu
r
es
vario
u
s stru
ctural
det
ermin
ants
rel
a
ted to p
r
ot
ein
function. The
kern
els u
s
in
g WL metho
d
perform
ed
b
e
tter than oth
e
r ke
rn
el types. Furth
e
rm
ore,
the WL
sh
ort
e
st path
ke
rnel with
com
p
lement
g
r
a
p
h
s o
u
tperfo
rms the oth
e
r kernel
s with
an
accuracy of a
t
least 83.64
%, and it achieves im
p
r
ov
ements in a
c
curacy
mo
re
than 2% over th
e
WL
sho
r
te
st path kernel
without
com
p
lement g
r
ap
h
s
. Mea
n
while
, con
s
ide
r
in
g
sho
r
te
st pat
hs
inst
ea
d of
w
a
lk
s inc
r
e
a
s
e
s cl
as
sif
i
cat
i
o
n
ac
cu
ra
cy significa
ntly. For the rand
o
m
wal
k
kern
el,
c
l
as
s
i
fic
a
tion is
the worst as
with an inc
r
ea
sing
numbe
r of t
o
ttering
wal
k
s, cla
s
sificati
on
accuracy de
crea
se
s. Table
3 also sho
w
s that
our pro
p
o
se
d method
outperfo
rm
s other meth
od
s.
6. Conclusio
n
In this
pap
er, We
propo
se a
sim
p
le
yet effective and
efficie
n
t
gra
ph
cla
s
sificatio
n
approa
ch th
a
t
is
ba
sed
o
n
topol
ogical
and l
abel
gr
a
ph attrib
utes.
Our mai
n
id
ea i
s
that g
r
a
phs
from the
sa
me cla
s
s
sh
ould h
a
ve si
milar attr
ib
ute value
s
. O
n
the ba
si
s
of an exten
s
ive
comp
ari
s
o
n
with state
-
of-the-a
r
t gra
p
h
kernel
cl
assifiers, we sh
ow that ou
r
approa
ch yie
l
ds
comp
etitive or better
accuraci
es
and
has typi
cally much lo
wer computati
onal time
s. Our
con
c
lu
sio
n
is
that grap
h attribute
s
are ef
fective
in ca
p
t
uring di
scrim
i
nating st
ru
ctural info
rmati
on
from different
classe
s. Our new ke
rn
els
based
on We
isfeiler-L
ehm
an test of iso
m
orp
h
ism o
p
e
n
the doo
r to application
s
of graph
ke
rnel
s on la
rge
g
r
aph
s in bioinf
ormati
cs, for i
n
stan
ce, p
r
ot
ein
function
pre
d
i
c
tion via d
e
ta
iled graph
m
odel
s of prot
ein st
ructu
r
e
on the a
m
ino
acid l
e
vel, or on
gene n
e
two
r
ks fo
r ph
enot
ype pre
d
ictio
n
. A challe
ng
ing que
stion
for furthe
r st
udie
s
will b
e
to
con
s
id
er
ke
rn
els o
n
graph
s with
co
ntin
uou
s or
high
-dimen
sion
al
node l
abel
s a
nd their
effici
ent
comp
utation.
Ackn
o
w
l
e
dg
ements
This p
r
oje
c
t is su
ppo
rted
by Beijing Munici
pal Edu
c
ation Com
m
i
ssi
on. The a
u
thors are
grateful to the
Beijing Unive
r
sity of Tech
n
o
logy for fina
ncial
sup
port.
Referen
ces
[1]
Vapn
ik V.
T
he nature of statis
tical lear
nin
g
theor
y. Ne
w
Y
o
rk: Springer-V
e
r
lag. 19
95.
[2]
VN Vapnik, SE Golo
w
i
ch, AJ Smola.
Sup
por
t Vector Method for F
unc
tion Approx
i
m
atio
n, Regressi
o
n
Estimati
on a
n
d
Signa
l Proces
sion
.
Adv. Neu
r
al Informatio
n
Processi
on S
yst. 1996: 281-
2
87.
[3]
D Haussl
er. Co
nvluti
on kern
el
s on discrete structures.
T
e
chnic
a
l Re
port. 199
9.
[4]
KM Borg
w
a
rdt,
et al. Protein functio
n
predic
t
ion via gra
ph
kerne
l
s.
BIOIN
FORMATICS
. 200
5;
21(1):
i47-i
56.
[5]
J Ramon, T
Gärtner.
Expressivity versu
s
efficiency of
graph k
e
rne
l
s.
Proceedi
ng
s of the F
i
rst
Internatio
na
l W
o
rksho
p
on Mi
nin
g
Graphs, T
r
ees an
d Seq
u
ences. 20
03: 6
5
-74.
[6]
KM Borg
w
a
rdt
,
HP Kriegel.
Shortest-p
ath
kern
els on
grap
hs
. Proc
eedings
of the Fifth IEEE
Internatio
na
l C
onfere
n
ce o
n
Data Min
i
ng. 2
005: 74-
81.
[7]
V Vacic, M
L
I
a
kouc
hev
a, S
Lo
nard
i
, P
R
adiv
o
jac.
Graph
l
e
t Ke
rn
el
s fo
r Pred
i
c
ti
on
o
f
Fu
n
c
ti
on
al
Resid
ues i
n
Protein Structure
s
.
Journal of C
o
mputati
o
n
a
l B
i
olo
g
y
. 20
10; 1
7
(1): 55-7
2
.
[8]
N Shervashidze, et al.
Efficient graph
let ker
nels for lar
ge g
r
aph co
mparis
on
.
Internati
o
n
a
l Co
nferenc
e
on Artificia
l
Intelli
ge
nce a
nd
Statistics
. 2009
:
488-49
5.
[9]
P Mahé, JP Ve
rt.
Graph kerne
l
s base
d
on tre
e
patterns for
mo
lec
u
les.
Ma
chin
e Le
arni
ng
. 2009; 75(
1):
3-35.
[10]
DL Verti
gan,
GP W
h
ittle.
A 2-Isomorp
h
is
m T
h
e
o
re
m f
o
r Hyper
gra
p
h
s
.
Journa
l of Combi
nator
ial
T
heor
y
,
Series
B. 1997; 71(
2): 215–
23
0.
[11]
VN Z
e
ml
yach
e
n
ko, NM Korn
eenk
o, RI
T
y
s
h
kevic
h
.
Graph iso
m
or
phis
m
probl
e
m
.
Jour
nal of Sovi
et
Mathematics. 1
985; 29(
4):
142
6–1
48
1.
[12]
BJ W
e
isfeil
er,
AA Lema
n
.
A r
educti
on
of a
grap
h to
a ca
n
onic
a
l for
m
an
d al
ge
bra
arisi
ng d
u
ri
ng th
is
reducti
on.
Na
u
c
ho-T
e
chnich
e
skaja Infrormat
s
ia. 196
8; 9(2):
12-16.
[13] BJ
W
e
ifei
ler.
On constructi
o
n
a
n
d
id
entific
ation
of
gra
p
h
s
.
Ne
w
York: Springer-Lec
ture
Notes
in
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
1
– 7508
7508
Mathematics. 1
976.
[14] RW
F
l
o
y
d.
Algorithm
97: Shortest Path
. Communicati
ons
of the ACM.
1962.
[15]
BV Ch
erkassk
y, AV Go
ld
be
rg, T
Radzik.
Shortest pat
hs
al
gor
ith
m
s:
theory an
d exper
imenta
l
eval
uatio
n
. Mathematic
al pro
g
r
amming. 1
996
; 73(2): 129-1
7
4
.
[16]
J W
ang,
H L
u
, KN P
l
ata
n
i
o
tis.
Gaussi
an
kern
el
opti
m
i
z
a
t
i
o
n
for p
a
ttern cl
assific
a
ti
on.
Pattern
recog
n
itio
n. 20
09; 42(7): 1
237
-124
7.
[17]
H Kashim
a, K T
s
uda, A Inokuchi.
Marg
ina
l
i
z
e
d
kern
els b
e
t
w
een lab
e
le
d grap
hs.
Proce
edi
ngs of the
T
w
e
n
tieth Inter
natio
nal C
onfer
ence o
n
Mach
i
ne Le
arni
ng. 2
003: 32
1-3
28.
[18]
PD Dobs
on,
AJ Doig.
D
i
sti
ngu
ishi
ng En
zyme Structur
e
s
fr
om No
n-e
n
z
y
mes W
i
tho
u
t Align
m
ents.
Journ
a
l of Mol
e
cul
a
r Biol
og
y.
2003; 3
30(4):
771-
783.
[19] DMW
Po
w
e
rs.
Evalu
a
tion: F
r
o
m
Prec
isio
n, R
e
call
an
d F
-Measure to ROC,
Informedn
ess, Marked
nes
s
& Correlation
.
Journ
a
l of Mac
h
in
e Le
arni
ng
T
e
chnolog
ies.
201
1; 2(1): 37-
63.
[20]
CC Ch
an
g, CJ
Lin.
LIBSVM:
a libr
a
ry for su
pport vector
machi
nes.
ACM
T
r
ansactions
on Intel
lig
ent
S
y
stems a
nd T
e
chn
o
lo
g
y
. 201
1; 2(3): 27.
Evaluation Warning : The document was created with Spire.PDF for Python.