Abstract
Graph matching is the task of computing the similarity between two graphs. Error-tolerant graph matching is a type of graph matching, in which a similarity between two graphs is computed based on some tolerance value whereas within exact graph matching a strict one-to-one correspondence is required between two graphs. In this paper, we present an approach to error-tolerant graph similarity using geometric graphs. We define the vertex distance (dissimilarity) and edge distance between two graphs and combine them to compute graph distance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Armiti, A., Gertz, M.: Geometric graph matching and similarity: a probabilistic approach. In: SSDBM (2014)
Bunke, H.: Error-tolerant graph matching: a formal framework and algorithms. In: Amin, A., Dori, D., Pudil, P., Freeman, H. (eds.) SSPR/SPR 1998. LNCS, vol. 1451, pp. 1–14. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0033223
Bunke, H., Allerman, G.: Inexact graph matching for structural pattern recognition. Pattern Recogn. Lett. 1, 245–253 (1983)
Caelli, T., Kosinov, S.: Inexact graph matching using eigen-subspace projection clustering. Int. J. Pattern Recogn. Artif. Intell. 18(3), 329–355 (2004)
Cheong, O., Gudmundsson, J., Kim, H.-S., Schymura, D., Stehn, F.: Measuring the similarity of geometric graphs. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 101–112. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02011-7_11
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18(3), 265–298 (2004)
Dwivedi, S.P., Singh, R.S.: Error-tolerant graph matching using homeomorphism. In: International Conference on Advances in Computing, Communication and Informatics (ICACCI), pp. 1762–1766 (2017)
Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. Int. J. Pattern Recogn. Artif. Intell. 88, 1450001.1–1450001.40 (2014)
Gartner, T.: Kernels for Structured Data. World Scientific, Singapore (2008)
Hart, P.E., Nilson, N.J., Raphael, B.: A formal basis for heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 100–107 (1968)
Haussler, D.: Convolution kernels on discrete structures. Technical report, UCSC-CRL-99-10, University of California, Sant Cruz (1999)
Kuramochi, M., Karypis, G.: Discovering frequent geometric subgraphs. Inf. Syst. 32, 1101–1120 (2007)
Lafferty, J., Lebanon, G.: Diffusion kernels on statistical manifolds. J. Mach. Learn. Res. 6, 129–163 (2005)
Neuhaus, M., Riesen, K., Bunke, H.: Fast suboptimal algorithms for the computation of graph edit distance. In: Yeung, D.-Y., Kwok, J.T., Fred, A., Roli, F., de Ridder, D. (eds.) SSPR /SPR 2006. LNCS, vol. 4109, pp. 163–172. Springer, Heidelberg (2006). https://doi.org/10.1007/11815921_17
Neuhaus, M., Bunke, H.: Bridging the Gap Between Graph Edit Distance and Kernel Machines. World Scientific, Singapore (2007)
Pinheiro, M.A., Kybic, J., Fua, P.: Geometric graph matching using Monte Carlo tree search. IEEE Trans. Pattern Anal. Mach. Intell. 39(11), 2171–2185 (2017)
Robles-Kelly, A., Hancock, E.R.: Graph edit distance from spectral seriation. IEEE Trans. Pattern Anal. Mach. Intell. 27, 365–378 (2005)
Riesen, K., Bunke, H.: IAM graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo, N., et al. (eds.) SSPR /SPR 2008. LNCS, vol. 5342, pp. 287–297. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-89689-0_33
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(4), 950–959 (2009)
Riesen, K., Bunke, H.: Improving bipartite graph edit distance approximation using various search strategies. Pattern Recogn. 48(4), 1349–1363 (2015)
Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. 13(3), 353–363 (1983)
Schieber, T.A., Carpi, L., Diaz-Guilera, A., Pardalos, P.M., Masoller, C., Ravetti, M.G.: Quantification of network structural dissimilarities. Nature Commun. 8(13928), 1–10 (2017)
Shimada, Y., Hirata, Y., Ikeguchi, T., Aihara, K.: Graph distance for complex networks. Sci. Rep. 6(34944), 1–6 (2016)
Shokoufandeh, A., Macrini, D., Dickinson, S., Siddiqi, K., Zucker, S.: Indexing hierarchical structures using graph spectra. IEEE Trans. Pattern Anal. Mach. Intell. 27(3), 365–378 (2005)
Sorlin, S., Solnon, C.: Reactive tabu search for measuring graph similarity. In: Brun, L., Vento, M. (eds.) GbRPR 2005. LNCS, vol. 3434, pp. 172–182. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31988-7_16
Tsai, W.H., Fu, K.S.: Error-correcting isomorphisms of attributed relational graphs for pattern analysis. IEEE Trans. Syst. Man Cybern. 9, 757–768 (1979)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Dwivedi, S.P., Singh, R.S. (2018). Error-Tolerant Geometric Graph Similarity. In: Bai, X., Hancock, E., Ho, T., Wilson, R., Biggio, B., Robles-Kelly, A. (eds) Structural, Syntactic, and Statistical Pattern Recognition. S+SSPR 2018. Lecture Notes in Computer Science(), vol 11004. Springer, Cham. https://doi.org/10.1007/978-3-319-97785-0_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-97785-0_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97784-3
Online ISBN: 978-3-319-97785-0
eBook Packages: Computer ScienceComputer Science (R0)