A fast projected fixed-point algorithm for large graph matching
Lu, Yao; Huang, Kaizhu; Liu, Cheng-Lin
2016-12-01
发表期刊PATTERN RECOGNITION
卷号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
DOI10.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
引用统计
被引频次:6[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.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Lu, Yao]的文章
[Huang, Kaizhu]的文章
[Liu, Cheng-Lin]的文章
百度学术
百度学术中相似的文章
[Lu, Yao]的文章
[Huang, Kaizhu]的文章
[Liu, Cheng-Lin]的文章
必应学术
必应学术中相似的文章
[Lu, Yao]的文章
[Huang, Kaizhu]的文章
[Liu, Cheng-Lin]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。