Fuzzy multilevel graph embedding. (English) Zbl 1251.68191

Luqman, Muhammad Muzzamil; Ramel, Jean-Yves; Lladós, Josep; Brouard, Thierry

Pattern Recognition 46, No. 2, 551-565 (2013).

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.

MSC:

68T10

Pattern recognition, speech recognition

Keywords:

pattern recognition; graphics recognition; graph clustering; graph classification; explicit graph embedding; fuzzy logic

Software:

clusfind

References:

[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)