Efficient subgraph matching using topological node feature constraints

PATTERN RECOGNITION

卷:48

Article; Proceedings Paper

Dahm, Nicholas¹  Bunke, Horst²  Caelli, Terry³  Gao, Yongsheng¹ 

[1] Griffith Univ, Sch Engn, Brisbane, Qld 4111, Australia

[2] Univ Bern, Inst Comp Sci & Appl Math, CH-3012 Bern, Switzerland

[3] Univ Melbourne, Melbourne, Vic 3010, Australia

关键词: Graph matching;    Subgraph isomorphism;    Topological node features;   

DOI  :  10.1016/j.patcog.2014.05.018

来源: Elsevier

【 摘 要 】

This paper presents techniques designed to minimise the number of states which are explored during subgraph isomorphism detection. A set of advanced topological node features, calculated from n-neighbourhood graphs, is presented and shown to outperform existing features. Further, the pruning effectiveness of both the new and existing topological node features is significantly improved through the introduction of strengthening techniques. In addition to topological node features, these strengthening techniques can also be used to enhance application-specific node labels using a proposed novel extension to existing pruning algorithms. Through the combination of these techniques, the number of explored search states can be reduced to near-optimal levels. (C) 2014 Elsevier Ltd. All rights reserved.

【 授权许可】

Free