Abstract
Recently, an emerging trend of representing objects by graphs can be observed. In fact, graphs offer a powerful alternative to feature vectors in pattern recognition, machine learning, and related fields. However, the domain of graphs contains very little mathematical structure, and consequently, there is only a limited amount of classification algorithms available. In this paper we survey recent work on graph embedding using dissimilarity representations. Once a population of graphs has been mapped to a vector space by means of this embedding procedure, all classification methods developed in statistical pattern recognition become directly available. In an experimental evaluation we show that the proposedmethodology of first embedding graphs in vector spaces and then applying a statistical classifier has significant potential to outperform classifiers that directly operate in the graph domain. Additionally, the proposed framework can be considered a contribution towards unifying the domains of structural and statistical pattern recognition.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Duda, R., Hart, P., Stork, D.: Pattern Classification, 2nd edn. Wiley-Interscience, Hoboken (2000)
Pekalska, E., Duin, R.: The Dissimilarity Representation for Pattern Recognition: Foundations and Applications. World Scientific, Singapore (2005)
Spillmann, B., Neuhaus, M., Bunke, H., Pekalska, E., Duin, R.: Transforming strings to vector spaces using prototype selection. In: Yeung, D.-Y., Kwok, J.T., Fred, A., Roli, F., de Ridder, D. (eds.) SSPR 2006 and SPR 2006. LNCS, vol. 4109, pp. 287–296. Springer, Heidelberg (2006)
Riesen, K., Neuhaus, M., Bunke, H.: Graph embedding in vector spaces by means of prototype selection. In: Escolano, F., Vento, M. (eds.) GbRPR 2007. LNCS, vol. 4538, pp. 383–393. Springer, Heidelberg (2007)
Riesen, K., Bunke, H.: Classifier ensembles for vector space embedding of graphs. In: Haindl, M., Kittler, J., Roli, F. (eds.) MCS 2007. LNCS, vol. 4472, pp. 220–230. Springer, Heidelberg (2007)
Riesen, K., Bunke, H.: Reducing the dimensionality of dissimilarity space embedding graph kernels. Engineering Applications of Artificial Intelligence Engineering Applications of Artificial Intelligence (accepted, 2008)
Riesen, K., Bunke, H.: Non-linear transformations of vector space embedded graphs. In: 8th International Workshop on Pattern Recognition in Information Systems (accepted, 2008)
Riesen, K., Bunke, H.: On Lipschitz embeddings of graphs. In: 12th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems (accepted, 2008)
Riesen, K., Bunke, H.: Dissimilarity based vector space embedding of graphs using prototype reduction schemes (submitted)
Bunke, H., Dickinson, P., Kraetzl, M.: Theoretical and algorithmic framework for hypergraph matching. In: Roli, F., Vitulano, S. (eds.) ICIAP 2005. LNCS, vol. 3617, pp. 463–470. Springer, Heidelberg (2005)
Luo, B., Wilson, R., Hancock, E.: Spectral embedding of graphs. Pattern Recognition 36(10), 2213–2223 (2003)
Wilson, R., Hancock, E., Luo, B.: Pattern vectors from algebraic graph theory. IEEE Trans. on Pattern Analysis ans Machine Intelligence 27(7), 1112–1124 (2005)
Robles-Kelly, A., Hancock, E.: A Riemannian approach to graph embedding. Pattern Recognition 40, 1024–1056 (2007)
Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recognition Letters 1, 245–253 (1983)
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing (accepted, 2008)
Gärtner, T., Lloyd, J., Flach, P.: Kernels and distances for structured data. Machine Learning 57(3), 205–232 (2004)
Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)
Bezdek, J., Kuncheva, L.: Nearest prototype classifier designs: An experimental study. Int. Journal of Intelligent Systems 16(12), 1445–1473 (2001)
Kim, S., Oommen, B.: A brief taxonomy and ranking of creative prototype reduction schemes. Pattern Analysis and Applications 6, 232–244 (2003)
Schölkopf, B., Smola, A., Müller, K.R.: Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation 10, 1299–1319 (1998)
Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert spaces. Israel Journal of Mathematics 52(1-2), 46–52 (1985)
Hjaltason, G., Samet, H.: Properties of embedding methods for similarity searching in metric spaces. IEEE Trans. on Pattern Analysis ans Machine Intelligence 25(5), 530–549 (2003)
Kuncheva, L.: Combining Pattern Classifiers: Methods and Algorithms. John Wiley, Chichester (2004)
Breiman, L.: Bagging predictors. Machine Learning 24, 123–140 (1996)
Freund, Y., Shapire, R.: A decision theoretic generalization of online learning and application to boosting. Journal of Computer and Systems Sciences 55, 119–139 (1997)
Watson, C., Wilson, C.: NIST Special Database 4, Fingerprint Database. National Institute of Standards and Technology (1992)
DTP, AIDS antiviral screen (2004), http://dtp.nci.nih.gov/docs/aids/aids_data.html
Schenker, A., Bunke, H., Last, M., Kandel, A.: Graph-Theoretic Techniques for Web Content Mining. World Scientific, Singapore (2005)
Neuhaus, M., Bunke, H.: Bridging the Gap Between Graph Edit Distance and Kernel Machines. World Scientific, Singapore (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bunke, H., Riesen, K. (2008). Graph Classification Based on Dissimilarity Space Embedding. In: da Vitoria Lobo, N., et al. Structural, Syntactic, and Statistical Pattern Recognition. SSPR /SPR 2008. Lecture Notes in Computer Science, vol 5342. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89689-0_103
Download citation
DOI: https://doi.org/10.1007/978-3-540-89689-0_103
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89688-3
Online ISBN: 978-3-540-89689-0
eBook Packages: Computer ScienceComputer Science (R0)