nips nips2001 nips2001-118 nips2001-118-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marcello Pelillo
Abstract: Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple replicator dynamics from evolutionary game theory. Experiments on hundreds of uniformly random trees are presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.
[1] D. H. Ballard and C. M. Brown. Computer Vision. Prentice-Hall, Englewood Cliffs, NJ, 1982.
[2] H. Blum and R. N. Nagel. Shape description using weighted symmetric axis features. Pattern Recognition, 10:167–180, 1978.
[3] I. M. Bomze. Evolution towards the maximum clique. J. Glob. Optim., 10:143–164, 1997.
[4] I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo. The maximum clique problem. In D.-Z. Du and P. M. Pardalos, editors, Handbook of Combinatorial Optimization (Suppl. Vol. A), pages 1–74. Kluwer, Boston, MA, 1999.
[5] I. M. Bomze, M. Pelillo, and V. Stix. Approximating the maximum weight clique using replicator dynamics. IEEE Trans. Neural Networks, 11(6):1228–1241, 2000. Figure 1: Results obtained over 100-node random trees with various levels of corruption, using the first-order dynamics (5). Top: Percentage of correct matches. Bottom: Average computational time taken by the replicator equations.
[6] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
[7] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman, San Francisco, CA, 1979.
[8] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Machine Intell. 18:377-388, 1996.
[9] J. Hofbauer. Imitation dynamics for games. Collegium Budapest, preprint, 1995.
[10] J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge, UK, 1998.
[11] T.-L. Liu, D. Geiger, and R. V. Kohn. Representation and self-similarity of shapes. In Proc. ICCV’98—6th Int. Conf. Computer Vision, pages 1129–1135, Bombay, India, 1998. 500 1000 1500 95 2500 100 2000 Percentage of correct matches Average CPU time (in secs) 3000
[12] T. S. Motzkin and E. G. Straus. Maxima for graphs and a new proof of a theorem of Tur´ n. a Canad. J. Math., 17:533–540, 1965. Figure 2: Results obtained over 100-node random trees with various levels of corruption, using the exponential dynamics (9) with . Top: Percentage of correct matches. Bottom: Average computational time taken by the replicator equations. ¤ ¡ ¥£ ¢ 100 200 95 100 300 Percentage of correct matches Average CPU time (in secs) 400
[13] M. Pelillo. Replicator equations, maximal cliques, and graph isomorphism. Neural Computation, 11(8):2023–2045, 1999.
[14] M. Pelillo and A. Jagota. Feasible and infeasible maxima in a quadratic program for maximum clique. J. Artif. Neural Networks, 2:411–420, 1995.
[15] M. Pelillo, K. Siddiqi, and S. W. Zucker. Matching hierarchical structures using association graphs. IEEE Trans. Pattern Anal. Machince Intell., 21(11):1105–1120, 1999.
[16] M. Pelillo, K. Siddiqi, and S. W. Zucker. Many-to-many matching of attributed trees using association graphs and game dynamics. In C. Arcelli, L. P. Cordella, and G. Sanniti di Baja, editors, Visual Form 2001, pages 583–593. Springer, Berlin, 2001.
[17] J. W. Weibull. Evolutionary Game Theory. MIT Press, Cambridge, MA, 1995.
[18] H. Wilf. The uniform selection of free trees. J. Algorithms, 2:204–207, 1981.
[19] S. C. Zhu and A. L. Yuille. FORMS: A flexible object recognition and modeling system. Int. J. Computer Vision, 20(3):187–212, 1996.