English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Shortest-path kernels on graphs

Borgwardt, K., & Kriegel, H.-P. (2005). Shortest-path kernels on graphs. In Fifth IEEE International Conference on Data Mining (ICDM'05) (pp. 74-81). Los Alamitos, CA, USA: IEEE Computer Society.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-D39F-C Version Permalink: http://hdl.handle.net/21.11116/0000-0004-DD0C-7
Genre: Conference Paper

Files

show Files

Locators

show
hide
Description:
-

Creators

show
hide
 Creators:
Borgwardt, KM1, Author              
Kriegel, H-P, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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 classification accuracy than walk-based kernels.

Details

show
hide
Language(s):
 Dates: 2005-11
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1109/ICDM.2005.132
BibTex Citekey: BorgwardtK2005
 Degree: -

Event

show
hide
Title: Fifth International Conference on Data Mining (ICDM 2005)
Place of Event: Houston, TX, USA
Start-/End Date: 2005-11-27 - 2005-11-30

Legal Case

show

Project information

show

Source 1

show
hide
Title: Fifth IEEE International Conference on Data Mining (ICDM'05)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Los Alamitos, CA, USA : IEEE Computer Society
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 74 - 81 Identifier: ISBN: 0-7695-2278-5