A fast projected fixed-point algorithm for large graph matching

doi:10.1016/j.patcog.2016.07.015

CASIA OpenIR > 多模态人工智能系统全国重点实验室 > 模式分析与学习

	A fast projected fixed-point algorithm for large graph matching
	Lu, Yao; Huang, Kaizhu; Liu, Cheng-Lin
发表期刊	PATTERN RECOGNITION
	2016-12-01
卷号	60 页码:971-982
文章类型	Article
摘要	We propose a fast algorithm for approximate matching of large graphs. Previous graph matching algorithms suffer from high computational complexity and therefore do not have good scalability. By using a new doubly stochastic projection, for matching two weighted graphs of n nodes, our algorithm has time complexity only O (n(3)) per iteration and space complexity O (n(2)). We proved that our algorithm converges at a super-logarithmic rate. Experiments on large synthetic and real graphs (over 1000 nodes) were conducted to evaluate the performance of various algorithms. Results show that due to its fast convergence, our algorithm is more than an order of magnitude faster than the previous state-of-the-art algorithms, while maintaining comparable accuracy in large graph matching. (C) 2016 Elsevier Ltd. All rights reserved.
关键词	Graph Matching Projected Fixed-point Large Graph Algorithm Feature Correspondence Point Matching
WOS标题词	Science & Technology ; Technology
DOI	10.1016/j.patcog.2016.07.015
关键词[WOS]	RECOGNITION ; DECOMPOSITION ; ISOMORPHISM ; RELAXATION
收录类别	SCI
语种	英语
项目资助者	National Basic Research Program of China (973 Program)(2012CB316300) ; National Natural Science Foundation of China (NSFC)(61411136002 ; Strategic Priority Research Program of the Chinese Academy of Sciences(XDA06040102) ; 61473236)
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Engineering, Electrical & Electronic
WOS记录号	WOS:000383525600077
引用统计	被引频次：22[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/12633
专题	多模态人工智能系统全国重点实验室_模式分析与学习
作者单位	Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, 95 Zhongguancun East Rd, Beijing 100190, Peoples R China
第一作者单位	模式识别国家重点实验室
推荐引用方式 GB/T 7714	Lu, Yao,Huang, Kaizhu,Liu, Cheng-Lin. A fast projected fixed-point algorithm for large graph matching[J]. PATTERN RECOGNITION,2016,60:971-982.
APA	Lu, Yao,Huang, Kaizhu,&Liu, Cheng-Lin.(2016).A fast projected fixed-point algorithm for large graph matching.PATTERN RECOGNITION,60,971-982.
MLA	Lu, Yao,et al."A fast projected fixed-point algorithm for large graph matching".PATTERN RECOGNITION 60(2016):971-982.