A graph matching algorithm based on concavely regularized convex relaxation

NEUROCOMPUTING

卷:134

Article

Liu, Zhi-Yong¹  Qiao, Hong¹  Jia, Li-Hao¹  Xu, Lei² 

[1] Chinese Acad Sci, Inst Automat, State Key Lab Management & Control Complex Syst, Beijing 100190, Peoples R China

[2] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China

关键词: Graph matching;    Concave-convex procedure;    Concave regularization;    Frank-Wolfe algorithm;    Convex relaxation;   

DOI  :  10.1016/j.neucom.2012.12.065

来源: Elsevier

【 摘 要 】

In this paper we propose a concavely regularized convex relaxation based graph matching algorithm. The graph matching problem is firstly formulated as a constrained convex quadratic program by relaxing the feasible set from the permutation matrices to doubly stochastic matrices. To gradually push the doubly stochastic matrix back to be a permutation one, an objective function is constructed by adding a simple weighted concave regularization to the convex relaxation. By gradually increasing the weight of the concave term, minimization of the objective function will gradually push the doubly stochastic matrix back to be a permutation one. A concave-convex procedure (CCCP) together with the Frank-Wolfe algorithm is adopted to minimize the objective function. The algorithm can be used on any types of graphs and exhibits a comparable performance as the PATH following algorithm, a state-of-the-art graph matching algorithm but applicable only on undirected graphs. (C) 2014 Elsevier B.V. All rights reserved.

【 授权许可】

Free