期刊
PATTERN RECOGNITION
卷 47, 期 2, 页码 736-747出版社
ELSEVIER SCI LTD
DOI: 10.1016/j.patcog.2013.08.024
关键词
Graph matching; Nonnegative matrix factorization; Sparse model; Hungarian algorithm
资金
- National Natural Science Foundation of China [61073116, 61211130309, 61272152]
- Major Research Project of the Scientific Research Foundation of the Higher Education Institutions of Anhui Province, China [KJ2011ZD10]
Graph matching problem that incorporates pairwise constraints can be cast as an Integer Quadratic Programming (IQP). Since it is NP-hard, approximate methods are required. In this paper, a new approximate method based on nonnegative matrix factorization with sparse constraints is presented. Firstly, the graph matching is formulated as an optimization problem with nonnegative and sparse constraints, followed by an efficient algorithm to solve this constrained problem. Then, we show the strong relationship between the sparsity of the relaxation solution and its effectiveness for graph matching based on our model. A key benefit of our method is that the solution is sparse and thus can approximately impose the one-to-one mapping constraints in the optimization process naturally. Therefore, our method can approximate the original IQP problem more closely than other approximate methods. Extensive and comparative experimental results on both synthetic and real-world data demonstrate the effectiveness of our graph matching method. (C) 2013 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据