Efficient subgraph matching using topological node feature constraints
Efficient subgraph matching using topological node feature constraints
复制标题
DOI：
10.1016/j.patcog.2014.05.018
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
N. Dahm;H. Bunke;T. Caelli;Yongsheng Gao
中科院分区：
文献类型：
--
作者：
N. Dahm;H. Bunke;T. Caelli;Yongsheng Gao
本文提出了技术，旨在尽量减少在子图同构检测探索的状态的数量。一组先进的拓扑节点功能，计算从n-邻域图，并显示优于现有的功能。此外，通过引入加强技术，新的和现有的拓扑节点功能的修剪效果显着提高。除了拓扑节点的功能，这些加强技术也可以用来增强特定于应用程序的节点标签，使用现有的修剪算法提出了一种新的扩展。通过这些技术的组合，探索的搜索状态的数量可以减少到接近最佳的水平。
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 fromn-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.