Fuzzy multilevel graph embedding. (English) Zbl 1251.68191

Summary: Structural pattern recognition approaches offer the most expressive, convenient, powerful but computational expensive representations of underlying relational information. To benefit from mature, less expensive and efficient state-of-the-art machine learning models of statistical pattern recognition they must be mapped to a low-dimensional vector space. Our method of explicit graph embedding bridges the gap between structural and statistical pattern recognition. We extract the topological, structural and attribute information from a graph and encode numeric details by fuzzy histograms and symbolic details by crisp histograms. The histograms are concatenated to achieve a simple and straightforward embedding of graph into a low-dimensional numeric feature vector. Experimentation on standard public graph datasets shows that our method outperforms the state-of-the-art methods of graph embedding for richly attributed graphs.


68T10 Pattern recognition, speech recognition


Full Text: DOI


[1] De Sa, J., Pattern RecognitionConcepts, Methods, and Applications (2001), Springer Verlag
[2] Friedman, M.; Kandel, A., Introduction to Pattern Recognition (1999), World Scientific
[4] Bunke, H.; Riesen, K., Recent advances in graph-based pattern recognition with applications in document analysis, Pattern Recognition, 44, 5, 1057-1067 (2011) · Zbl 1209.68443
[5] Riesen, K.; Bunke, H., Graph classification based on vector space embedding, International Journal of Pattern Recognition and Artificial Intelligence, 23, 6, 1053-1081 (2009)
[7] 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)
[8] Shokoufandeh, A.; Macrini, D.; Dickinson, S.; Siddiqi, K.; Zucker, S., Indexing hierarchical structures using graph spectra, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 7, 1125-1140 (2005)
[9] Ferrer, M.; Valveny, E.; Serratosa, F.; Riesen, K.; Bunke, H., Generalized median graph computation by means of graph embedding in vector spaces, Pattern Recognition, 43, 4, 1642-1655 (2010) · Zbl 1191.68569
[10] Duda, R.; Hart, P.; Stork, D., Pattern Classification, vol. 2 (2000), Wiley Interscience
[11] 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)
[13] Nathan Linial, E. L.; Rabinovich, Y., The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245 (1995) · Zbl 0827.05021
[17] Riesen, K.; Bunke, H., Graph Classification and Clustering Based on Vector Space Embedding (2010), World Scientific Publishing Co., Inc. · Zbl 1231.68233
[18] 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)
[23] Luo, B., Spectral embedding of graphs, Pattern Recognition, 36, 10, 2213-2230 (2003) · Zbl 1054.68105
[25] Torsello, a.; Hancock, E., Graph embedding using tree edit-union, Pattern Recognition, 40, 5, 1393-1405 (2007) · Zbl 1112.68114
[28] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Learning, 22, 8, 888-905 (2002)
[29] Ren, P.; Wilson, R.; Hancock, E., Graph Characterization via Ihara coefficients, IEEE Transactions on Neural Networks, 22, 233-245 (2011)
[33] Delalandre, M.; Valveny, E.; Pridmore, T.; Karatzas, D., Generation of synthetic documents for performance evaluation of symbol recognition & spotting systems, International Journal on Document Analysis and Recognition, 1-21 (2010)
[37] Kaufman, L.; Rousseeuw, P. J., Finding Groups in DataAn Introduction to Cluster Analysis (1990), John Wiley & Sons, Ltd.
[41] Morgan, H. L., The generation of a unique machine description for chemical structures - a technique developed at chemical abstracts service, Journal of Chemical Documentation, 5, 2, 107-113 (1965)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.