Efficient Supergraph Search Using Graph Coding

Shun IMAI  Akihiro INOKUCHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.1   pp.130-141
Publication Date: 2020/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7011
Type of Manuscript: PAPER
Category: Data Engineering, Web Information Systems
supergraph search,  indexing,  graph coding,  canonical form,  subgraph isomorphism,  

Full Text: PDF(1.2MB)>>
Buy this Article

This paper proposes a method for searching for graphs in the database which are contained as subgraphs by a given query. In the proposed method, the search index does not require any knowledge of the query set or the frequent subgraph patterns. In conventional techniques, enumerating and selecting frequent subgraph patterns is computationally expensive, and the distribution of the query set must be known in advance. Subsequent changes to the query set require the frequent patterns to be selected again and the index to be reconstructed. The proposed method overcomes these difficulties through graph coding, using a tree structured index that contains infrequent subgraph patterns in the shallow part of the tree. By traversing this code tree, we are able to rapidly determine whether multiple graphs in the database contain subgraphs that match the query, producing a powerful pruning or filtering effect. Furthermore, the filtering and verification steps of the graph search can be conducted concurrently, rather than requiring separate algorithms. As the proposed method does not require the frequent subgraph patterns and the query set, it is significantly faster than previous techniques; this independence from the query set also means that there is no need to reconstruct the search index when the query set changes. A series of experiments using a real-world dataset demonstrate the efficiency of the proposed method, achieving a search speed several orders of magnitude faster than the previous best.