Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Directed Graph
Feature Space
Graph Isomorphism
Indexation
Inner Product
Kernel Method
Polynomial Time
Positive Definite
Structured Data
Related Publications
(20)
Marginalized Kernels Between Labeled Graphs
Kernels for Graphs
Protein function prediction via graph kernels
Di usion kernels on graphs and other discrete structures
Fast Computation of Graph Kernels
Subscribe
Academic
Publications
On Graph Kernels: Hardness Results and Efficient Alternatives
On Graph Kernels: Hardness Results and Efficient Alternatives,10.1007/9783540451679_11,Thomas Gärtner,Peter A. Flach,Stefan Wrobel
Edit
On Graph Kernels: Hardness Results and Efficient Alternatives
(
Citations: 152
)
BibTex

RIS

RefWorks
Download
Thomas Gärtner
,
Peter A. Flach
,
Stefan Wrobel
As most 'realworld' 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 NPhard. 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. 129143, 2003
DOI:
10.1007/9783540451679_11
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.
(
www.springerlink.com
)
(
www.cs.bris.ac.uk
)
(
www.informatik.unitrier.de
)
(
springerlink.metapress.com
)
More »
Citation Context
(89)
...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 Kimura
,
et 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 Brandes
,
et al.
Network ensemble clustering using latent roles
...The first is that the kernelized variant also allows us to reduce the dimensionality of nonvectorial 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 Sugiyama
,
et al.
Semisupervised Local Fisher Discriminant Analysis for Dimensionality ...
...SVM), and random walks in graphs [
55
] (RWSVM), respectively...
Xinbo Gao
,
et 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 Lee
,
et al.
Objectgraphs for contextaware category discovery
References
(18)
Fault Detection of Combinational Circuits Based on Supply Current
(
Citations: 31
)
Masaki Hashizume
,
Takeomi Tamesada
,
Kazuhiro Yamada
,
Masaaki Kawakami
Conference:
International Test Conference  ITC
, pp. 374380, 1988
Graph Kernels and Gaussian Processes for Relational Reinforcement Learning
(
Citations: 41
)
Thomas Gärtner
,
Kurt Driessens
,
Jan Ramon
Conference:
International Workshop on Inductive Logic Programming  ILP
, pp. 146163, 2003
Marginalized Kernels Between Labeled Graphs
(
Citations: 205
)
Hisashi Kashima
,
Koji Tsuda
,
Akihiro Inokuchi
Conference:
International Conference on Machine Learning  ICML
, pp. 321328, 2003
Product Graphs: Structure and Recognition
(
Citations: 291
)
W. Imrich
,
S. Klavzar
Published in 2000.
A training algorithm for optimal margin classifiers
(
Citations: 2045
)
Bernhard E. Boser
,
Isabelle M. Guyon
,
Vladimir N. Vapnik
Conference:
Computational Learning Theory  COLT
, pp. 144152, 1992
Sort by:
Citations
(152)
A Subpath Kernel for Rooted Unordered Trees
Daisuke Kimura
,
Tetsuji Kuboyama
,
Tetsuo Shibuya
,
Hisashi Kashima
Journal:
Transactions of The Japanese Society for Artificial Intelligence
, vol. 26, pp. 473482, 2011
Network ensemble clustering using latent roles
Ulrik Brandes
,
Jürgen Lerner
,
Uwe Nagel
Journal:
Advanced Data Analysis and Classification
, vol. 5, no. 2, pp. 8194, 2011
LTS: Discriminative subgraph mining by learning from search history
Ning Jin
,
Wei Wang
Conference:
International Conference on Data Engineering  ICDE
, pp. 207218, 2011
Semisupervised Local Fisher Discriminant Analysis for Dimensionality Reduction
(
Citations: 9
)
Masashi Sugiyama
,
T. Id'e
,
Shinichi Nakajima
,
Jun Sese
Journal:
Machine Learning  ML
, vol. 78, no. 1, pp. 3561, 2010
A survey of graph edit distance
(
Citations: 10
)
Xinbo Gao
,
Bing Xiao
,
Dacheng Tao
,
Xuelong Li
Journal:
Pattern Analysis and Applications  PAA
, vol. 13, no. 1, pp. 113129, 2010