Abstract
The Graph Edit Distance is the most used distance between Attributed Graphs and it is composed of three main costs on nodes and arcs: Insertion, Deletion and Substitution. We present a method to learn the Insertion and Deletion costs of nodes and edges defined in the Graph Edit Distance, whereas, we define the Edit Cost Substitution data dependent and without parameters (for instance the Euclidean distance). In some applications, the ground truth of the correspondence between some pairs of graphs is available or can be easily deducted. The aim of the method we present is the learning process depends on these few available ground truth correspondences and not to the classification set that in some applications is not available. To learn these costs, the optimisation algorithm tends to minimise the Hamming distance between the ground truth correspondences and the automatically extracted node correspondences. We believe that minimising the Hamming distance makes the matching algorithm to find a good correspondence and so, to increase the recognition ratio of the classification algorithm in a pattern recognition application.
This research is supported by Spanish projects DPI2013-42458-P & TIN2013-47245-C2-2-R.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Jouili, S., Tabbone, S.: Hypergraph-based image retrieval for graph-based representation. Pattern Recognition 45(11), 4054–4068 (2012)
Neuhaus, M., Bunke, H.: A graph matching based approach to fingerprint classification using directional variance. In: Kanade, T., Jain, A., Ratha, N.K. (eds.) AVBPA 2005. LNCS, vol. 3546, pp. 191–200. Springer, Heidelberg (2005)
Serratosa, F., Cortés, X., Solé-Ribalta, A.: Component retrieval based on a database of graphs for Hand-Written Electronic-Scheme Digitalisation. Expert Syst. Appl. 40(7), 2493–2502 (2013)
Mahé, P., Vert, J.-P.: Graph kernels based on tree patterns for molecules. Machine Learning 75(1), 3–35 (2009)
Fan, W.: Graph pattern matching revised for social network analysis. In: ICDT 2012, pp. 8–21
Qi, X., Wu, Q., Zhang, Y., Fuller, E., Zhang, C.-Q.: A novel model for DNA sequence similarity analysis based on graph theory. Evolutionary Bioinformatics 7, 149–154 (2011)
Sanfeliu, A., Fu, K.S.: A Distance measure between attributed relational graphs for pattern recognition. IEEE Trans. on Systems, Man, and Cybernetics 13(3), 353–362 (1983)
Gao, X., et al.: A survey of graph edit distance. Pattern Analysis and Applications 13(1), 113–129 (2010)
Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recognition Letters 1(4), 245–253 (1983)
Solé, A., Serratosa, F., Sanfeliu, A.: On the Graph Edit Distance cost: Properties and Applications. Intern. Journal Pattern Recognition & Artificial Intelligence 26(5) (2012)
Neuhaus, M., Bunke, H.: Self-organizing maps for learning the edit costs in graph matching. IEEE Trans. on Sys., Man, and Cybernetics, Part B 35(3), 503–514 (2005)
Neuhaus, M., Bunke, H.: Automatic learning of cost functions for graph edit distance. Information Sciences 177(1), 239–247 (2007)
Leordeanu, M., Sukthankar, R., Hebert, M.: Unsupervised Learning for Graph Matching. International Journal of Computer Vision 96(1), 28–45 (2012)
Caetano, T., et al.: Learning Graph Matching. Transaction on Pattern Analysis and Machine Intelligence 31(6), 1048–1058 (2009)
Serratosa, F., Solé-Ribalta, A., Cortés, X.: Automatic learning of edit costs based on interactive and adaptive graph recognition. In: Jiang, X., Ferrer, M., Torsello, A. (eds.) GbRPR 2011. LNCS, vol. 6658, pp. 152–163. Springer, Heidelberg (2011)
Moreno, C., Serratosa, F.: Consensus of Two Sets of Correspondences through Optimisation Functions, Pattern Analysis and Applications (2015)
Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. The MIT Press (2012). ISBN: 9780262018258
Cortés, X., Serratosa, F.: Learning Graph-Matching Edit-Costs based on the Optimality of the Oracle’s Node Correspondences. Pattern Recognition Letters 56, 22–29 (2015)
Lladós, J., Martí, E., Villanueva, J.J.: Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1137–1143 (2001)
Gold, S., Rangarajan, A.: A Graduated Assignment Algorithm for Graph Matching. IEEE TPAMI 18(4), 377–388 (1996)
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Computing 27(7), 950–959 (2009)
Serratosa, F.: Fast Computation of Bipartite Graph Matching. Pattern Recognition Letters 45, 244–250 (2014)
Serratosa, F.: Speeding up Fast Bipartite Graph Matching trough a new cost matrix. International Journal of Pattern Recognition and Artificial Intelligence 29(2) (2015)
Cortés, X., Moreno, C., Serratosa, F.: Improving the correspondence establishment based on interactive homography estimation. In: Wilson, R., Hancock, E., Bors, A., Smith, W. (eds.) CAIP 2013, Part II. LNCS, vol. 8048, pp. 457–465. Springer, Heidelberg (2013)
Serratosa, F., Cortés, X.: Interactive Graph-Matching using Active Query Strategies. Pattern Recognition 48, 1360–1369 (2015)
Cortés, X., Serratosa, F.: An Interactive Method for the Image Alignment problem based on Partially Supervised Correspondence. Expert Systems with Applications 42(1), 179–192 (2015)
Bay, H., Ess, A., Tuytelaars, T., Van Gool, L.: SURF: Speeded Up Robust Features. Comp. Vision and Image Unders. 110(3), 346–359 (2008)
Delaunay, B.: Sur la sphère vide. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk 7, 793–800 (1934)
Nelder, J.A., Mead, R.: Computer Journal 7, 308–313 (1965)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Cortés, X., Serratosa, F., Moreno-García, C.F. (2015). Ground Truth Correspondence Between Nodes to Learn Graph-Matching Edit-Costs. In: Azzopardi, G., Petkov, N. (eds) Computer Analysis of Images and Patterns. CAIP 2015. Lecture Notes in Computer Science(), vol 9256. Springer, Cham. https://doi.org/10.1007/978-3-319-23192-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-23192-1_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23191-4
Online ISBN: 978-3-319-23192-1
eBook Packages: Computer ScienceComputer Science (R0)