zbMATH — the first resource for mathematics

Heuristics for the generalized median graph problem. (English) Zbl 1346.90790
Summary: Structural approaches for pattern recognition frequently make use of graphs to represent objects. The concept of object similarity is of great importance in pattern recognition. The graph edit distance is often used to measure the similarity between two graphs. It basically consists in the amount of distortion needed to transform one graph into the other. The median graph of a set \(S\) of graphs is a graph of \(S\) that minimizes the sum of its distances to all other graphs in \(S\). The generalized median graph of \(S\) is a graph that minimizes the sum of the distances to all graphs in \(S\). It is the graph that best captures the information contained in \(S\) and may be regarded as the best representative of the set. Exact methods for solving the generalized median graph problem are capable to handle only a few small graphs. We propose two new heuristics for solving the generalized median graph problem: a greedy adaptive algorithm and a GRASP heuristic. Numerical results indicate that both heuristics can be used to obtain good approximate solutions for the generalized median graph problem, significantly improving the initial solutions and the median graphs. Therefore, the generalized median graph can be effectively computed and used as a better representation than the median graph in a number of relevant pattern recognition applications. This conclusion is supported by experiments with a classification problem and comparisons with algorithm \(k\)-NN.
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Aiex, R. M.; Resende, M. G.C.; Ribeiro, C. C., Probability distribution of solution time in GRASP: an experimental investigation, Journal of Heuristics, 8, 343-373, (2002) · Zbl 1012.68795
[2] Aiex, R. M.; Resende, M. G.C.; Ribeiro, C. C., TTTPLOTS: A perl program to create time-to-target plots, Optimization Letters, 1, 355-366, (2007) · Zbl 1220.90102
[3] Allahyari, S.; Salari, M.; Vigo, D., A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem, European Journal of Operational Research, 242, 756-768, (2015) · Zbl 1341.90011
[4] Alpaydin, E., Introduction to machine learning, (2010), The MIT Press · Zbl 1191.68485
[5] Balas, E.; Yu, C. S., Finding a maximum clique in an arbitrary graph, SIAM Journal on Computing, 15, 1054-1068, (1986) · Zbl 0604.05024
[6] Berretti, S.; Bimbo, A. D.; Vicario, E., Efficient matching and indexing of graph models in content-based retrieval, IEEE Transactions Pattern Analysis Machine Intelligence, 23, 1089-1105, (2001)
[7] Bunke, H., On a relation between graph edit distance and maximum common subgraph, Pattern Recognition Letters, 18, 689-694, (1997)
[8] Bunke, H. (2011). Graph representation for intelligent information processing - Fundamentals and algorithms for classification and clustering. Available online at: http://cvpr-ss-2010.cecs.anu.edu.au/pdfs/HorstBunke.pdf. Accessed 02.02.15.
[9] Bunke, H.; Foggia, P.; Guidobaldi, C.; Sansone, C.; Vento, M., A comparison of algorithms for maximum common subgraph on randomly connected graphs, Lecture Notes in Computer Science, 2396, 123-132, (2002) · Zbl 1073.68700
[10] Bunke, H.; Jiang, X.; Kandel, A., On the minimum common supergraph of two graphs, Computing, 65, 13-25, (2000) · Zbl 0963.05127
[11] 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, 265-298, (2004)
[12] Conte, D.; Foggia, P.; Vento, M., Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs, Journal of Graph Algorithms and Applications, 11, 99-143, (2007) · Zbl 1161.68846
[13] de la Higuera, C.; Casacuberta, F., Topology of strings: Median string is NP-complete., Theoretical Computer Science, 230, 39-48, (2000) · Zbl 0940.68116
[14] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern classification, (2000), Wiley New York
[15] Durand, P.; Pasari, R.; Baker, J. W.; Tsai, C.-C., An efficient algorithm for similarity analysis of molecules, Internet Journal of Chemistry, 2, 17, (1999)
[16] Fan, K. C.; Liu, C. W.; Wang, Y. K., A fuzzy bipartite weighted graph matching approach to fingerprint verification, Proceedings of the 1998 IEEE international conference on systems, man, and cybernetics, Vol. 5, 4363-4368, (1998), IEEE San Diego
[17] Feo, T.; Resende, M., A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8, 67-71, (1989) · Zbl 0675.90073
[18] Feo, T.; Resende, M., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 109-133, (1995) · Zbl 0822.90110
[19] Ferrer, M., Theory and algorithms on the median graph - Application to graph-based classification and clustering, (2008), Universitat Autonoma de Barcelona Belaterra, (Ph.D. thesis)
[20] Ferrer, M.; Valveny, E.; Serratosa, F., Median graph: A new exact algorithm using a distance based on the maximum common subgraph, Pattern Recognition Letters, 30, 579-588, (2009)
[21] Ferrer, M.; Valveny, E.; Serratosa, F., Median graphs: A genetic approach based on new theoretical properties, Pattern Recognition, 42, 2003-2012, (2009) · Zbl 1192.68571
[22] Ferrer, M.; Valveny, E.; Serratosa, F.; Riesen, K.; Bunke, H., An approximate algorithm for Median graph computation using graph embedding, Proceedings of the 19th international conference on pattern recognition, Tampa, Vol. 2, 1-4, (2008)
[23] 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, 1642-1655, (2010) · Zbl 1191.68569
[24] Festa, P.; Resende, M., GRASP: an annotated bibliography, (Ribeiro, C.; Hansen, P., Essays and surveys in metaheuristics, (2002), Kluwer), 325-367 · Zbl 1017.90001
[25] Festa, P.; Resende, M., An annotated bibliography of GRASP, part I: algorithms, International Transactions in Operational Research, 16, 1-24, (2009) · Zbl 1153.90553
[26] Festa, P.; Resende, M., An annotated bibliography of GRASP, part II: applications, International Transactions in Operational Research, 16, 131-172, (2009) · Zbl 1168.90582
[27] Fischer, S.; Gilomen, K.; Bunke, H., Identification of diatoms by grid graph matching, Proceedings of the joint IAPR international workshop on structural, syntactic, and statistical pattern recognition, 94-103, (2002), Springer London · Zbl 1073.68742
[28] Foggia, P.; Percannella, G.; Vento, M., Graph matching and learning in pattern recognition in the last 10 years, International Journal of Pattern Recognition and Artificial Intelligence, 28, 1450001-1-1450001-40, (2014)
[29] Fukunaga, K., Introduction to statistical pattern recognition, (1990), Academic Press San Diego · Zbl 0711.62052
[30] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), W. H. Freeman & Co. New York · Zbl 0411.68039
[31] Hlaoui, A.; Wang, S., A new Median graph algorithm, Lecture Notes in Computer Science, 2726, 225-234, (2003) · Zbl 1040.68552
[32] Hong, P.; Wang, R.; Huang, T., Learning patterns from images by combining soft decisions and hard decisions, Proceedings of the conference on computer vision and pattern recognition, Vol. 1, 79-83, (2000), IEEE Computer Society Hilton Head
[33] Jiang, X.; Munger, A.; Bunke, H., On Median graphs: properties, algorithms, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 1144-1151, (2001)
[34] Lades, M.; Vorbruggen, J. C.; Buhmann, J.; Lange, J.; von der Malsburg, C.; Wurz, P. R., Distortion invariant object recognition in the dynamic link architecture, IEEE Transactions on Computers, 42, 300-311, (1993)
[35] McGregor, J. J., Backtrack search algorithms and the maximal common subgraph problem, Software Practice and Experience, 12, 23-34, (1982) · Zbl 0466.68053
[36] Montgomery, D. C.; Runger, G. C., Applied statistics and probability for engineers, (2003), John Wiley and Sons
[37] Mukherjee, L.; Singh, V.; Peng, J.; Xu, J.; Zeitz, M.; Berezney, R., Generalized Median graphs: theory and applications, Proceedings of the IEEE 11th international conference on computer vision, (2007), IEEE Rio de Janeiro
[38] Mukherjee, L.; Singh, V.; Peng, J.; Xu, J.; Zeitz, M. J.; Berezney, R., Generalized Median graphs and applications, Journal of Combinatorial Optimization, 17, 21-44, (2009) · Zbl 1172.90497
[39] Musmanno, L., Approximate algorithms for the generalized median graph problem (in Portuguese), (2013), Universidade Federal Fluminense Niterói, (Master’s thesis)
[40] Nguyen, V.-P.; Prins, C.; Prodhon, C., Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking, European Journal of Operational Research, 216, 113-126, (2012) · Zbl 1237.90047
[41] Rebagliati, N.; Solé-Ribalta, A.; Pelillo, M.; Serratosa, F., On the relation between the common labelling and the Median graph, Proceedings of the 2012 joint IAPR international conference on structural, syntactic, and statistical pattern recognition, 107-115, (2012), Springer
[42] Research Group on Computer Vision and Artificial Intelligence (2011). IAM graph database repository. Available online at: http://www.iam.unibe.ch/fki/databases/iam-graph-database. Accessed 02.02.15.
[43] Resende, M.; Ribeiro, C., Greedy randomized adaptive search procedures, (Glover, F.; Kochenberger, G., Handbook of metaheuristics, (2002), Kluwer), 219-249 · Zbl 1102.90384
[44] Resende, M.; Ribeiro, C., GRASP with path-relinking: recent advances and applications, (Ibaraki, T.; Nonobe, K.; Yagiura, M., Metaheuristics: Progress as real problem solvers, (2005), Springer), 29-63
[45] Resende, M.; Ribeiro, C., Greedy randomized adaptive search procedures: advances, hybridizations, and applications, (Gendreau, M.; Potvin, J.-Y., Handbook of metaheuristics, (2010), Springer), 283-319
[46] Resende, M.; Ribeiro, C., GRASP: greedy randomized adaptive search procedures, (Burke, E.; Kendall, G., Search methodologies, (2014), Springer), 285-310
[47] Serratosa, F.; Cortés, X.; Solé-Ribalta, A., Component retrieval based on a database of graphs for hand-written electronic-scheme digitalisation, Expert Systems with Applications, 40, 2493-2502, (2013)
[48] Shearer, K.; Bunke, H.; Venkatesh, S., Video indexing and similarity retrieval by largest common subgraph detection using decision trees, Pattern Recognition, 34, 1075-1091, (2001) · Zbl 1006.68857
[49] Suganthan, P. N.; Yan, H., Recognition of handprinted Chinese characters by constrained graph matching, Image and Vision Computing, 16, 191-201, (1998)
[50] Torsello, A.; Hancock, E. R., Computing approximate tree edit-distance using relaxation labeling, Pattern Recognition Letters, 24, 1089-1097, (2003) · Zbl 1028.68150
[51] Vento, M., A long trip in the charming world of graphs for pattern recognition, Pattern Recognition, 48, 291-301, (2015) · Zbl 1373.68356
[52] Voigt, K., Semi-automatic matching of heterogeneous model-based specifications, Lecture Notes in Informatics, P-160, 537-542, (2010)
[53] Zeng, Z.; Tung, A. K.H.; Wang, J.; Feng, J.; Zhou, L., Comparing stars: on approximating graph edit distance, Proceedings of the VLDB Endowment, 2, 25-36, (2009)
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.