Abstract
Association graph techniques represent a classical approach to tackle the graph matching problem and recently the idea has been generalized to the case of hypergraphs. In this paper, we explore the potential of this approach in conjunction with a class of dynamical systems derived from the Baum-Eagon inequality. In particular, we focus on the pure isomorphism case and show, with extensive experiments on a large synthetic dataset, that despite its simplicity the Baum-Eagon dynamics does an excellent job at finding globally optimal solutions.
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
Barrow, H.G., Burstall, R.M.: Subgraph isomorphism, matching relational structures and maximal cliques. Inf. Process. Lett. 4(4), 83–84 (1976)
Baum, L.E., Eagon, J.A.: An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Am. Math. Soc. 73(3), 360–363 (1967)
Baum, L.E., Petrie, T., Soules, G., Weiss, N.: A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Stat. 41(1), 164–171 (1970)
Blakley, G.R.: Homogeneous nonnegative symmetric quadratic transformations. Bull. Am. Math. Soc. 70(5), 712–715 (1964)
Duchenne, O., Bach, F., Kweon, I., Ponce, J.: A tensor-based algorithm for high-order graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 33(12), 2383–2395 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. WH Freeman, New York (2002)
Hou, J., Pelillo, M.: A game-theoretic hyper-graph matching algorithm. In: 24th International Conference on Pattern Recognition (ICPR) (2018)
Kozen, D.: A clique problem equivalent to graph isomorphism. ACM SIGACT News 10(2), 50–52 (1978)
Lee, J., Cho, M., Lee, K.M.: Hyper-graph matching via reweighted random walks. CVPR 2011, 1633–1640 (2011)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math. 17, 533–540 (1965)
Pelillo, M.: The dynamics of nonlinear relaxation labeling processes. J. Math. Imaging Vis. 7(4), 309–323 (1997)
Pelillo, M.: A unifying framework for relational structure matching. In: Proceedings of 14th International Conference on Pattern Recognition, (ICPR), pp. 1316–1319 (1998)
Pelillo, M.: Replicator equations, maximal cliques, and graph isomorphism. Neural Comput. 11(8), 1933–1955 (1999)
Rota Bulò, S., Pelillo, M.: A generalization of the Motzkin-Straus theorem to hypergraphs. Optim. Lett. 3(2), 287–295 (2009)
Rota Bulò, S., Pelillo, M.: A game-theoretic approach to hypergraph clustering. IEEE Trans. Pattern Anal. Mach. Intell. 35(6), 1312–1327 (2013)
Yan, J., Zhang, C., Zha, H., Liu, W., Yang, X., Chu, S.M.: Discrete hyper-graph matching. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1520–1528 (2015)
Zhang, H., Ren, P.: Game theoretic hypergraph matching for multi-source image correspondences. Pattern Recogn. Lett. 87, 87–95 (2017)
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
Sandi, G., Vascon, S., Pelillo, M. (2018). On Association Graph Techniques for Hypergraph Matching. 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_46
Download citation
DOI: https://doi.org/10.1007/978-3-319-97785-0_46
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)