CASIA OpenIR  > 模式识别国家重点实验室  > 模式分析与学习
A fast projected fixed-point algorithm for large graph matching
Lu, Yao; Huang, Kaizhu; Liu, Cheng-Lin
AbstractWe 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.
KeywordGraph Matching Projected Fixed-point Large Graph Algorithm Feature Correspondence Point Matching
WOS HeadingsScience & Technology ; Technology
Indexed BySCI
Funding OrganizationNational 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 Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Artificial Intelligence ; Engineering, Electrical & Electronic
WOS IDWOS:000383525600077
Citation statistics
Document Type期刊论文
AffiliationChinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, 95 Zhongguancun East Rd, Beijing 100190, Peoples R China
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Lu, Yao]'s Articles
[Huang, Kaizhu]'s Articles
[Liu, Cheng-Lin]'s Articles
Baidu academic
Similar articles in Baidu academic
[Lu, Yao]'s Articles
[Huang, Kaizhu]'s Articles
[Liu, Cheng-Lin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Lu, Yao]'s Articles
[Huang, Kaizhu]'s Articles
[Liu, Cheng-Lin]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.