Back
GRAPH CLASSIFICATION BASED ON VECTOR SPACE EMBEDDING
Journal article

GRAPH CLASSIFICATION BASED ON VECTOR SPACE EMBEDDING

  • RIESEN, KASPAR Institute of Computer Science and Applied Mathematics, University of Bern, Neubrückstrasse 10, CH-3012 Bern, Switzerland
  • BUNKE, HORST Institute of Computer Science and Applied Mathematics, University of Bern, Neubrückstrasse 10, CH-3012 Bern, Switzerland
  • 2011-11-21
Published in:
  • International Journal of Pattern Recognition and Artificial Intelligence. - World Scientific Pub Co Pte Lt. - 2009, vol. 23, no. 06, p. 1053-1081
English Graphs provide us with a powerful and flexible representation formalism for pattern classification. Many classification algorithms have been proposed in the literature. However, the vast majority of these algorithms rely on vectorial data descriptions and cannot directly be applied to graphs. Recently, a growing interest in graph kernel methods can be observed. Graph kernels aim at bridging the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. In the present paper, we propose an approach transforming graphs into n-dimensional real vectors by means of prototype selection and graph edit distance computation. This approach allows one to build graph kernels in a straightforward way. It is not only applicable to graphs, but also to other kind of symbolic data in conjunction with any kind of dissimilarity measure. Thus it is characterized by a high degree of flexibility. With several experimental results, we prove the robustness and flexibility of our new method and show that our approach outperforms other graph classification methods on several graph data sets of diverse nature.
Language
  • English
Open access status
closed
Identifiers
Persistent URL
https://sonar.ch/global/documents/206197
Statistics
Document views: 39 File downloads: