A Weight Regularized Relaxation Based Graph Matching Algorithm

详细信息    查看全文

• 作者：Zhi-Yong Liu (1) zhiyong.liu@ia.ac.cn
  Hong Qiao (1) hong.qiao@ia.ac.cn
  Lei Xu (2) lxu@cse.cuhk.edu.hk
• 关键词：graph matching – ; CCCP – ; Frank ; Wolfe algorithm – ; convex relaxation
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7202
• 期：1
• 页码：9-16
• 全文大小：190.9 KB
• 参考文献：1. Eshera, M.A., Fu, K.S.: An image understanding system using attributed symbolic representation and inexact graph-matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 8(5), 604–618 (1986)
  2. Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs (preliminary report). In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 172–184. ACM, New York (1974)
  3. 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(3), 265–298 (2004)
  4. Xu, L., Oja, E.: Improved Simulated Annealing, Boltzmann Machine and Attributed Graph Matching. In: Almeida, L.B., Wellekens, C.J. (eds.) EURASIP 1990. LNCS, vol. 412, pp. 151–160. Springer, Heidelberg (1990)
  5. Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 18(4), 377–388 (1996)
  6. Zaslavskiy, M., Bach, F., Vert, J.P.: A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence 31(12), 2227–2242 (2009)
  7. Kuhn, H.W.: The hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1-2), 83–97 (1955)
  8. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)
  9. Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence 10(5), 695–703 (1988)
  10. Liu, Z.Y., Qiao, H., Xu, L.: An extended path following algorithm for graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence (to appear, 2012)
  11. Liu, Z.Y.: Graph matching: a new concave relaxation fuction and algorithm. Automatica Sinica (to appear, 2012)
• 作者单位：1. State Key Laboratory of Management and Control for Complex Systems, Institute of Automation, Chinese Academy of Sciences, Beijing, 100190 China2. Department of Computer Science and Engineering, Chinese University of Hong Kong, Shatin, Hong Kong
• ISSN：1611-3349

文摘

In this paper we propose a regularized relaxation based graph matching algorithm. The graph matching problem is formulated as a constrained convex quadratic program, by relaxing the permutation matrix to a doubly stochastic one. To gradually push the doubly stochastic matrix back to a permutation one, a simple weighted concave regular term is added to the convex objective function. The concave regular function is not a concave relaxation of the original matching problem. However, it is shown that such a simple concave regular term has a comparative performance as the concave relaxation of the PATH following algorithm, which works only on undirected graphs. A concave-convex procedure (CCCP) together with the Frank-Wolfe algorithm is adopted to solve the matching problem, and some experimental results witness the state-of-art performance of the proposed algorithm.