Graph Matching: a New Concave Relaxation Function and Algorithm
-
摘要: 将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向. 它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲, 相对于离散优化,连续优化问题的近似求解将更为容易. 但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵. 最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵, 并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数. 本文提出一种针对于有向无自环图匹配问题的凹松弛函数, 并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.
-
关键词:
- 图模型匹配 /
- Frank-Wolfe算法 /
- 凹松弛函数 /
- 凸松弛函数
Abstract: Recently, approximate graph matching based on relaxing the permutation matrix to a doubly stochastic matrix has become an important and popular topic. The key point lies in which approximation over a continuous set is usually easier to implement than that over a discrete one. However, a consequent trouble related to such a relaxation is how to properly map the doubly stochastic matrix back to a permutation one. In the literature, a concave relaxation function for matching problem between the undirected graphs without self-loops was recently proposed, such that the doubly stochastic matrix can converge to a permutation one in a smooth way, and got a state-of-art performance on matching accuracy. Unfortunately, except for the undirected graphs without self-loops, there are no concave relaxation proposed for any other types of graph models. In this paper, we propose a concave relaxation for the directed graphs without self-loops, based on which a graph matching algorithm is then presented. Extensive experimental comparisons witness the validity of the proposed methods.-
Key words:
- Graph matching /
- Frank-Wolfe algorithm /
- concave relaxation /
- convex relaxation
-
[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, 1986, 8(5): 604-618[2] Duchenne O, Bach F, Kweon I S, Ponce J. A tensor-based algorithm for high-order graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(12): 2383-2395[3] Singh R, Xu J B, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(35): 12763-12768[4] Sambhoos K, Nagi R, Sudit M, Stotz A. Enhancements to high level data fusion using graph matching and state space search. Information Fusion, 2010, 11(4): 351-364[5] Wu H, Ling T W, Dobbie G, Bao Z, Xu L. Reducing graph matching to tree matching for XML queries with ID references. Lecture Notes in Computer Science. Berlin: Springer, 2010. 391-406[6] Fernandez M L, Valiente G. A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters, 2001, 22(6-7): 753-758[7] Umeyama S. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(5): 695-703[8] Luo B, Hancock R. Structural graph matching using the EM algorithm and singular value decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(10): 1120-1136[9] Zheng Kai-Jie, Gao Yu-Tao, Peng Ji-Gen. A new relaxation model for weighted graph matching. Acta Automatica Sinica, 2010, 36(8): 1200-1203(郑开杰, 高玉涛, 彭济根. 赋权图匹配问题的一种新的松弛模型. 自动化学报, 2010, 36(8): 1200-1203 )[10] Gold S, Rangarajan A. A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(4): 377-388[11] Zaslavskiy M, Bach F, Vert J P. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2227-2242[12] Blake A, Zisserman A. Visual Reconstruction. Cambridge: The MIT Press, 1987[13] Kuhn H W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 1955, 2(1-2): 83- 97[14] Li J S. Kronecker products of positive semidefinite matrices. Journal of Mathematical Research and Exposition, 1997, 17(3): 327-334[15] Zhan X Z. Extremal eigenvalues of real symmetric matrices with entries in an interval. SIAM Journal on Matrix Analysis and Applications, 2006, 27(3): 851-860[16] Frank M, Wolfe P. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 1956, 3(1-2): 95-110[17] Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004
点击查看大图
计量
- 文章访问数: 2076
- HTML全文浏览量: 57
- PDF下载量: 1308
- 被引次数: 0