@inproceedings{2000555,
author={Thomas Gaertner and Peter Flach and Stefan Wrobel},
title={On Graph Kernels: Hardness Results and Efficient Alternatives},
booktitle={Proceedings of the 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop},
ISBN={3-540-40720-0 },
publisher={Springer-Verlag},
pages={129--143},
month={August},
year={2003},
abstract={As most `real-world' data is structured, research in kernel
methods has begun investigating kernels for various kinds of structured
data. One of the most widely used tools for modeling structured data
are graphs. An interesting and important challenge is thus to investigate
kernels on instances that are represented by graphs. So far, only very
specific graphs such as trees and strings have been considered.
This paper investigates kernels on labeled directed graphs with general
structure. It is shown that computing a strictly positive definite graph
kernel is at least as hard as solving the graph isomorphism problem.
It is also shown that computing an inner product in a feature space
indexed by all possible graphs, where each feature counts the number
of subgraphs isomorphic to that graph, is NP-hard. On the other hand,
inner products in an alternative feature space, based on walks in the
graph, can be computed in polynomial time. Such kernels are defined in
this paper. },
abstract-url={http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2000555},
url={http://www.cs.bris.ac.uk/Publications/Papers/2000555.pdf},
keyword={Machine Learning},
pubtype={102}
}