中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 自动化研究所
  3. 中国科学院自动化研究所
  4. 多模态人工智能系统全国重点实验室
  5. 模式分析与学习团队
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
关键词Graph Matching Projected Fixed-point Large Graph Algorithm Feature Correspondence Point Matching
DOI10.1016/j.patcog.2016.07.015
文献子类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.
WOS关键词RECOGNITION ; DECOMPOSITION ; ISOMORPHISM ; RELAXATION
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:000383525600077
资助机构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)
源URL[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.

入库方式： OAI收割

来源：自动化研究所

浏览0
下载0
收藏0
其他版本

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