Academic
Publications
On Graph Kernels: Hardness Results and Efficient Alternatives

On Graph Kernels: Hardness Results and Efficient Alternatives,10.1007/978-3-540-45167-9_11,Thomas Gärtner,Peter A. Flach,Stefan Wrobel

On Graph Kernels: Hardness Results and Efficient Alternatives   (Citations: 152)
BibTex | RIS | RefWorks Download
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.
Conference: Computational Learning Theory - COLT , pp. 129-143, 2003
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Since Haussler [5] introduced the framework of the convolution kernel, kernel functions for various kind of discrete structures, for example, strings [22,23,24], trees [6,7,1,8,10,9], and graphs [25,26] have been proposed...

    Daisuke Kimuraet al. A Subpath Kernel for Rooted Unordered Trees

    • ...Gärtner (2003) provides a survey on some of the different approaches and some hardness results are established in Gärtner et al. (2003)...

    Ulrik Brandeset al. Network ensemble clustering using latent roles

    • ...The first is that the kernelized variant also allows us to reduce the dimensionality of non-vectorial structured data such as strings, trees, and graphs by employing kernel functions defined for such structured data (Lodhi et al. 2002; Duffy and Collins 2002; Kashima and Koyanagi 2002; Kondor and Lafferty 2002; Kashima et al. 2003; Gärtner et al. 2003; Gärtner 2003)...
    • ...We used the datasets in the Technion Repository of Text Categorization 8 (TechTC; Davidov et al. 2004)...

    Masashi Sugiyamaet al. Semi-supervised Local Fisher Discriminant Analysis for Dimensionality ...

    • ...SVM), and random walks in graphs [55] (RW-SVM), respectively...

    Xinbo Gaoet al. A survey of graph edit distance

    • ...(In Section 4 we demonstrate the comparative value for the discovery task.) Relative to existing graph kernels from the machine learning literature [6, 13], our approach allows us to represent object topology without requiring hard decisions on object names and idealized segmentations...

    Yong Jae Leeet al. Object-graphs for context-aware category discovery

Sort by: