Abstract
In recent years graph embedding has emerged as a promising solution for enabling the expressive, convenient, powerful but computational expensive graph based representations to benefit from mature, less expensive and efficient state of the art machine learning models of statistical pattern recognition. In this paper we present a comparison of two implicit and three explicit state of the art graph embedding methodologies. Our preliminary experimentation on different chemoinformatics datasets illustrates that the two implicit and three explicit graph embedding approaches obtain competitive performance for the problem of graph classification.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brun, L., Conte, D., Foggia, P., Vento, M.: A graph-kernel method for re-identification. In: Kamel, M., Campilho, A. (eds.) ICIAR 2011, Part I. LNCS, vol. 6753, pp. 173–182. Springer, Heidelberg (2011)
Bunke, H., Riesen, K.: Recent advances in graph-based pattern recognition with applications in document analysis. Pattern Recognition 44(5), 1057–1067 (2011)
Chung, F.R.K.: Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society (February 1997)
Gaüzère, B., Brun, L., Villemin, D.: Graph kernels based on relevant patterns and cycle information for chemoinformatics. In: Proceedings of ICPR 2012. IAPR, pp. 1775–1778. IEEE (November 2012)
Gaüzére, B., Brun, L., Villemin, D.: Two new graphs kernels in chemoinformatics. Pattern Recognition Letters 33(15), 2038–2047 (2012)
Gaüzère, B., Hasegawa, M., Brun, L., Tabbone, S.: Implicit and explicit graph embedding: Comparison of both approaches on chemoinformatics applications. In: Gimel’farb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M., Omachi, S., Windeatt, T., Yamada, K. (eds.) SSPR&SPR 2012. LNCS, vol. 7626, pp. 510–518. Springer, Heidelberg (2012)
Gibert, J., Valveny, E., Bunke, H.: Graph embedding in vector spaces by node attribute statistics. Pattern Recognition 45(9), 3072–3083 (2012)
Gibert, J., Valveny, E., Bunke, H., Fornés, A.: On the correlation of graph edit distance and l 1 distance in the attribute statistics embedding space. In: Gimel’farb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M., Omachi, S., Windeatt, T., Yamada, K. (eds.) SSPR&SPR 2012. LNCS, vol. 7626, pp. 135–143. Springer, Heidelberg (2012)
Jaromczyk, J., Toussaint, G.: Relative neighborhood graphs and their relatives. In: Proceedings of the IEEE (1992)
Jouili, S., Tabbone, S.: Graph embedding using constant shift embedding. In: Ünay, D., Çataltepe, Z., Aksoy, S. (eds.) ICPR 2010. LNCS, vol. 6388, pp. 83–92. Springer, Heidelberg (2010)
Luqman, M.M., Ramel, J.Y., Lladós, J.: Improving Fuzzy Multilevel Graph Embedding through Feature Selection Technique. In: Gimel’farb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M., Omachi, S., Windeatt, T., Yamada, K. (eds.) SSPR & SPR 2012. LNCS, vol. 7626, pp. 243–253. Springer, Heidelberg (2012)
Luqman, M.M., Ramel, J.Y., Lladós, J., Brouard, T.: Fuzzy multilevel graph embedding. Pattern Recognition 46(2), 551–565 (2013)
Neuhaus, M., Bunke, H.: Bridging the Gap Between Graph Edit Distance and Kernel Machines. World Scientific Publishing Co., Inc., River Edge (2007)
Riesen, K., Bunke, H.: Iam graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) SSPR & SPR 2008. LNCS, vol. 5342, pp. 287–297. Springer, Heidelberg (2008)
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Computing 27(7), 950–959 (2009)
Riesen, K., Bunke, H.: Graph classification based on vector space embedding. IJPRAI 23(6), 1053–1081 (2009)
Sidere, N., Héroux, P., Ramel, J.Y.: Vector representation of graphs: Application to the classification of symbols and letters. In: ICDAR, pp. 681–685. IEEE Computer Society (2009)
Smola, A.J., Kondor, R.I.: Kernels and regularization on graphs. In: XV Annual Conference on Learning Theory, pp. 144–158 (2003)
Steinke, F., Schlkopf, B.: Kernels, regularization and differential equations. Pattern Recognition 41(11), 3271–3286 (2008)
Toivonen, H., Srinivasan, A., King, R., Kramer, S., Helma, C.: Statistical evaluation of the predictive toxicology challenge 2000–2001. Bioinformatics 19(10), 1183–1193 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Conte, D. et al. (2013). A Comparison of Explicit and Implicit Graph Embedding Methods for Pattern Recognition. In: Kropatsch, W.G., Artner, N.M., Haxhimusa, Y., Jiang, X. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2013. Lecture Notes in Computer Science, vol 7877. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38221-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-38221-5_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38220-8
Online ISBN: 978-3-642-38221-5
eBook Packages: Computer ScienceComputer Science (R0)