A unified framework for strengthening topological node features and its application to subgraph isomorphism detection

This paper presents techniques to address the complexity problem of subgraph isomorphism detection on large graphs. To overcome the inherently high computational complexity, the problem is simplified through the calculation and strengthening of topological node features. These features can be utilised, in principle, by any subgraph isomorphism algorithm. The design and capabilities of the proposed unified strengthening framework are discussed in detail. Additionally, the concept of an n-neighbourhood is introduced, which facilitates the development of novel features and provides an additional platform for feature strengthening. Through experiments performed with state-of-the-art subgraph isomorphism algorithms, the theoretical and practical advantages of using these techniques become evident. © 2013 Springer-Verlag.