Efficient subgraph matching using topological node feature constraints. Issue 2 (February 2015)

• Record Type: Journal Article
• Authors: Dahm, Nicholas; Bunke, Horst; Caelli, Terry; Gao, Yongsheng
• Is Part Of: Pattern recognition. Volume 48:Issue 2(2015:Feb.)
• Page Start: 317
• Page End: 330
• Publication Date: 2015-02
• Subjects: Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2014.05.018
• Languages: English
• ISSNs: 0031-3203

Abstract

<abstract abstract-type="author" id="ab0005"> <title id="sect0005">Abstract</title> <sec> <p id="sp0075">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 <italic>n</italic>-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.</p> </sec> </abstract>