Positive definite kernels between labeled graphs have recently been proposed. They enable the application of kernel methods, such as support vector machines, to the analysis and classification of graphs, for example, chemical compounds. These graph kernels are obtained by marginalizing a kernel between paths with respect to a random walk model on the graph vertices along the edges. We propose two extensions of these graph kernels, with the double goal to reduce their computation time and increase their relevance as measure of similarity between graphs. First, we propose to modify the label of each vertex by automatically adding information about its environment with the use of the Morgan algorithm. Second, we suggest a modification of the random walk model to prevent the walk from coming back to a vertex that was just visited. These extensions are then tested on benchmark experiments of chemical compounds classification, with promising results.
%0 Conference Paper
%1 mahe2004
%A Mahé, Pierre
%A Ueda, Nobuhisa
%A Akutsu, Tatsuya
%A Perret, Jean-Luc
%A Vert, Jean-Philippe
%B Proceedings of the twenty-first international conference on Machine learning
%C New York, NY, USA
%D 2004
%I ACM
%K graph-kernel
%P 70--77
%R 10.1145/1015330.1015446
%T Extensions of marginalized graph kernels
%U http://doi.acm.org/10.1145/1015330.1015446
%X Positive definite kernels between labeled graphs have recently been proposed. They enable the application of kernel methods, such as support vector machines, to the analysis and classification of graphs, for example, chemical compounds. These graph kernels are obtained by marginalizing a kernel between paths with respect to a random walk model on the graph vertices along the edges. We propose two extensions of these graph kernels, with the double goal to reduce their computation time and increase their relevance as measure of similarity between graphs. First, we propose to modify the label of each vertex by automatically adding information about its environment with the use of the Morgan algorithm. Second, we suggest a modification of the random walk model to prevent the walk from coming back to a vertex that was just visited. These extensions are then tested on benchmark experiments of chemical compounds classification, with promising results.
%@ 1-58113-838-5
@inproceedings{mahe2004,
abstract = {Positive definite kernels between labeled graphs have recently been proposed. They enable the application of kernel methods, such as support vector machines, to the analysis and classification of graphs, for example, chemical compounds. These graph kernels are obtained by marginalizing a kernel between paths with respect to a random walk model on the graph vertices along the edges. We propose two extensions of these graph kernels, with the double goal to reduce their computation time and increase their relevance as measure of similarity between graphs. First, we propose to modify the label of each vertex by automatically adding information about its environment with the use of the Morgan algorithm. Second, we suggest a modification of the random walk model to prevent the walk from coming back to a vertex that was just visited. These extensions are then tested on benchmark experiments of chemical compounds classification, with promising results.},
acmid = {1015446},
added-at = {2011-04-29T12:25:04.000+0200},
address = {New York, NY, USA},
author = {Mah\'{e}, Pierre and Ueda, Nobuhisa and Akutsu, Tatsuya and Perret, Jean-Luc and Vert, Jean-Philippe},
biburl = {https://www.bibsonomy.org/bibtex/2df6e4caa92af781bfd85efdae65b2fc6/utahell},
booktitle = {Proceedings of the twenty-first international conference on Machine learning},
description = {Extensions of marginalized graph kernels},
doi = {10.1145/1015330.1015446},
interhash = {8910e0a15c6c65eeb0df5f37b3825ebe},
intrahash = {df6e4caa92af781bfd85efdae65b2fc6},
isbn = {1-58113-838-5},
keywords = {graph-kernel},
location = {Banff, Alberta, Canada},
pages = {70--77},
publisher = {ACM},
series = {ICML '04},
timestamp = {2011-04-29T13:38:30.000+0200},
title = {Extensions of marginalized graph kernels},
url = {http://doi.acm.org/10.1145/1015330.1015446},
year = 2004
}