Abstract
Graphs are the most powerful, expressive and convenient data structures but there is a lack of efficient computational tools and algorithms for processing them. The embedding of graphs into numeric vector spaces permits them to access the state-of-the-art computational efficient statistical models and tools. In this paper we take forward our work on explicit graph embedding and present an improvement to our earlier proposed method, named “fuzzy multilevel graph embedding - FMGE”, through feature selection technique. FMGE achieves the embedding of attributed graphs into low dimensional vector spaces by performing a multilevel analysis of graphs and extracting a set of global, structural and elementary level features. Feature selection permits FMGE to select the subset of most discriminating features and to discard the confusing ones for underlying graph dataset. Experimental results for graph classification experimentation on IAM letter, GREC and fingerprint graph databases, show improvement in the performance of FMGE.
Chapter PDF
References
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence 18(3), 265–298 (2004)
Bunke, H., Irniger, C., Neuhaus, M.: Graph Matching – Challenges and Potential Solutions. In: Roli, F., Vitulano, S. (eds.) ICIAP 2005. LNCS, vol. 3617, pp. 1–10. Springer, Heidelberg (2005)
Bunke, H., Gunter, S., Jiang, X.: Towards Bridging the Gap between Statistical and Structural Pattern Recognition: Two New Concepts in Graph Matching. In: Singh, S., Murshed, N., Kropatsch, W.G. (eds.) ICAPR 2001. LNCS, vol. 2013, pp. 1–11. Springer, Heidelberg (2001)
Roth, V., Laub, J., Kawanabe, M., Buhmann, J.: Optimal cluster preserving embedding of nonmetric proximity data. IEEE Transactions on Pattern Analysis and Machine Intelligence 25(12), 1540–1551 (2003)
Chen, T., Yang, Q., Tang, X.: Directed graph embedding. In: International Joint Conference on Artificial Intelligence, pp. 2707–2712 (2007)
Shaw, B., Jebara, T.: Structure preserving embedding. In: International Conference on Machine Learning, pp. 1–8 (2009)
Foggia, P., Vento, M.: Graph Embedding for Pattern Recognition. In: Ünay, D., Çataltepe, Z., Aksoy, S. (eds.) ICPR 2010. LNCS, vol. 6388, pp. 75–82. Springer, Heidelberg (2010)
Lee, G., Madabhushi, A.: Semi-Supervised Graph Embedding Scheme with Active Learning (SSGEAL): Classifying High Dimensional Biomedical Data. In: Dijkstra, T.M.H., Tsivtsivadze, E., Marchiori, E., Heskes, T. (eds.) PRIB 2010. LNCS, vol. 6282, pp. 207–218. Springer, Heidelberg (2010)
Riesen, K., Bunke, H.: Graph Classification and Clustering Based on Vector Space Embedding. World Scientific (2010)
Riesen, K., Bunke, H.: Graph Classification And Clustering Based On Vector Space Embedding. World Scientific Publishing Co., Inc. (2010)
Bunke, H., Riesen, K.: Recent advances in graph-based pattern recognition with applications in document analysis. Pattern Recognition 44(5), 1057–1067 (2011)
Wilson, R.C., Hancock, E.R., Luo, B.: Pattern vectors from algebraic graph theory. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(7), 1112–1124 (2005)
Bunke, H., Riesen, K.: Improving vector space embedding of graphs through feature selection algorithms. Pattern Recognition 44(9), 1928–1940 (2011)
Gibert, J., Valveny, E., Bunke, H.: Feature selection on node statistics based embedding of graphs. Pattern Recognition Letters (April 2012)
Gibert, J., Valveny, E., Bunke, H.: Dimensionality Reduction for Graph of Words Embedding. In: Jiang, X., Ferrer, M., Torsello, A. (eds.) GbRPR 2011. LNCS, vol. 6658, pp. 22–31. Springer, Heidelberg (2011)
Gibert, J., Valveny, E., Terrades, O.: Multiple classifiers for graph of words embedding. Multiple Classifier Systems, 1–10 (2011)
Luqman, M.M., Lladós, J., Ramel, J.Y., Brouard, T.: A Fuzzy-Interval Based Approach for Explicit Graph Embedding. In: Ünay, D., Çataltepe, Z., Aksoy, S. (eds.) ICPR 2010. LNCS, vol. 6388, pp. 93–98. Springer, Heidelberg (2010)
Luqman, M.M., Ramel, J.Y., Lladós, J., Brouard, T.: Fuzzy Multilevel Graph Embedding. Pattern Recognition (accepted, 2012), http://dx.doi.org/10.1016/j.patcog.2012.07.029
Luqman, M.M., Lladós, J., Ramel, J.Y., Brouard, T.: Dimensionality Reduction for Fuzzy-Interval Based Explicit Graph Embedding. In: GREC, pp. 117–120 (2011)
Kira, K., Rendell, L.A.: The feature selection problem: traditional methods and a new algorithm. In: Proceedings of the Tenth National Conference on Artificial Intelligence, AAAI 1992, pp. 129–134. AAAI Press (1992)
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.) S+SSPR 2008. LNCS, vol. 5342, pp. 287–297. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Luqman, M.M., Ramel, J.Y., Lladós, J. (2012). Improving Fuzzy Multilevel Graph Embedding through Feature Selection Technique. In: Gimel’farb, G., et al. Structural, Syntactic, and Statistical Pattern Recognition. SSPR /SPR 2012. Lecture Notes in Computer Science, vol 7626. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34166-3_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-34166-3_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34165-6
Online ISBN: 978-3-642-34166-3
eBook Packages: Computer ScienceComputer Science (R0)