Knowledge Commons of Institute of Automation,CAS
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 |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | 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. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论