Cookies Policy

This site uses cookies. By continuing to browse the site you are agreeing to our use of cookies.

I accept this policy

Find out more here

Novel kernels for error-tolerant graph classification

No metrics data to plot.
The attempt to load metrics for this article has failed.
The attempt to plot a graph for these metrics has failed.
The full text of this article is not currently available.

Brill’s MyBook program is exclusively available on BrillOnline Books and Journals. Students and scholars affiliated with an institution that has purchased a Brill E-Book on the BrillOnline platform automatically have access to the MyBook option for the title(s) acquired by the Library. Brill MyBook is a print-on-demand paperback copy which is sold at a favorably uniform low price.

Access this article

+ Tax (if applicable)
Add to Favorites
You must be logged in to use this functionality

image of Spatial Vision
For more content, see Multisensory Research and Seeing and Perceiving.

One of the major difficulties in graph classification is the lack of mathematical structure in the space of graphs. The use of kernel machines allows us to overcome this fundamental limitation in an elegant manner by addressing the pattern recognition problem in an implicitly existing feature vector space instead of the original space of graphs. In this paper we propose three novel error-tolerant graph kernels — a diffusion kernel, a convolution kernel, and a random walk kernel. The kernels are closely related to one of the most flexible graph matching methods, graph edit distance. Consequently, our kernels are applicable to virtually any kind of graph. They also show a high degree of robustness against various types of distortion. In an experimental evaluation involving the classification of line drawings, images, diatoms, fingerprints, and molecules, we demonstrate the superior performance of the proposed kernels in conjunction with support vector machines over a standard nearest-neighbor reference method and several other graph kernels including a standard random walk kernel.

Affiliations: 1: Institute of Computer Science, University of Bern, Neubrückstrasse 10, CH-3012 Bern, Switzerland; 2: Institute of Computer Science, University of Bern, Neubrückstrasse 10, CH-3012 Bern, Switzerland.


Full text loading...


Data & Media loading...

Article metrics loading...



Can't access your account?
  • Tools

  • Add to Favorites
  • Printable version
  • Email this page
  • Subscribe to ToC alert
  • Get permissions
  • Recommend to your library

    You must fill out fields marked with: *

    Librarian details
    Your details
    Why are you recommending this title?
    Select reason:
    Spatial Vision — Recommend this title to your library
  • Export citations
  • Key

  • Full access
  • Open Access
  • Partial/No accessInformation