On Graph Kernels: Hardness Results and Efficient Alternatives

Gaertner Thomas, Peter Flach, Wrobel Stefan

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

431 Citations (Scopus)

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.
Translated title of the contributionOn Graph Kernels: Hardness Results and Efficient Alternatives
Original languageEnglish
Title of host publicationProceedings of the 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop
Pages129-143
Publication statusPublished - 2003

Bibliographical note

ISBN: 3540407200
Publisher: Springer-Verlag
Name and Venue of Conference: Proceedings of the 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop
Other identifier: 2000555

Fingerprint Dive into the research topics of 'On Graph Kernels: Hardness Results and Efficient Alternatives'. Together they form a unique fingerprint.

Cite this