K. Borgwardt, and H. Kriegel. Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM 2005), page 74--81. Washington, DC, USA, IEEE Computer Society, (2005)
Abstract
Data mining algorithms are facing the challenge to deal with an increasing number of complex objects. For graph data, a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs. Graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. As a general problem, these kernels are either computationally expensive or limited in their expressiveness. We try to overcome this problem by defining expressive graph kernels which are based on paths. As the computation of all paths and longest paths in a graph is NP-hard, we propose graph kernels based on shortest paths. These kernels are computable in polynomial time, retain expressivity and are still positive definite. In experiments on classification of graph models of proteins, our shortest-path kernels show significantly higher classificationaccuracy than walk-based kernels.
%0 Conference Paper
%1 paper:borgwardt:2005
%A Borgwardt, Karsten M.
%A Kriegel, Hans-Peter
%B Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM 2005)
%C Washington, DC, USA
%D 2005
%I IEEE Computer Society
%K 2005 graph kernel path short to-read
%P 74--81
%T Shortest-Path Kernels on Graphs
%U http://dx.doi.org/10.1109/ICDM.2005.132
%X Data mining algorithms are facing the challenge to deal with an increasing number of complex objects. For graph data, a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs. Graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. As a general problem, these kernels are either computationally expensive or limited in their expressiveness. We try to overcome this problem by defining expressive graph kernels which are based on paths. As the computation of all paths and longest paths in a graph is NP-hard, we propose graph kernels based on shortest paths. These kernels are computable in polynomial time, retain expressivity and are still positive definite. In experiments on classification of graph models of proteins, our shortest-path kernels show significantly higher classificationaccuracy than walk-based kernels.
@inproceedings{paper:borgwardt:2005,
abstract = {Data mining algorithms are facing the challenge to deal with an increasing number of complex objects. For graph data, a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs. Graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. As a general problem, these kernels are either computationally expensive or limited in their expressiveness. We try to overcome this problem by defining expressive graph kernels which are based on paths. As the computation of all paths and longest paths in a graph is NP-hard, we propose graph kernels based on shortest paths. These kernels are computable in polynomial time, retain expressivity and are still positive definite. In experiments on classification of graph models of proteins, our shortest-path kernels show significantly higher classificationaccuracy than walk-based kernels.},
added-at = {2008-06-02T15:39:47.000+0200},
address = {Washington, DC, USA},
author = {Borgwardt, Karsten M. and Kriegel, Hans-Peter},
biburl = {https://www.bibsonomy.org/bibtex/2275778901efecbb122cb8b9ca8ad9311/mschuber},
booktitle = {Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM 2005)},
interhash = {c5c45ca832e89c6f1bcff594a5e5efdc},
intrahash = {275778901efecbb122cb8b9ca8ad9311},
keywords = {2005 graph kernel path short to-read},
pages = {74--81},
publisher = {IEEE Computer Society},
timestamp = {2008-09-09T12:56:40.000+0200},
title = {Shortest-Path Kernels on Graphs},
url = {http://dx.doi.org/10.1109/ICDM.2005.132},
year = 2005
}