Efficient and exact multi-graph matching search

A multigraph is modeled as a bag of graphs. Exact multigraph matching search aims to find all multigraphs that are the same as the query multigraphs from the data multigraph datasets. To the best of our knowledge, works regarding exact multigraph matching search have not been reported although they have a very wide range of application scenarios. In this article, we propose an efficient algorithm to solve the problem of exact multigraph matching search. We first propose a definition of exact multigraph matching and its Basic Method (BM), called BM, which has a considerable amount of graph isomorphism detection calculations and, thus, has very high computational complexity. Obviously, it is impractical to compare the query multigraph to each data multigraph in the multigraph datasets. To reduce the search space, multiple filtering conditions are proposed to obtain a candidate result set containing all the final results, including the cardinality filter, the vertex filter, the edge filter, the size filter, and the star filter. Then, each multigraph in the candidate result set is verified with the Improved BM (IBM) algorithm. Moreover, an offline and Multilayer Inverted Index (MII), named MII, is proposed to further accelerate the search process. Finally, we propose an Exact Multigraph Matching Search (EMMS) algorithm, based on the abovementioned technologies. We also analyze its time complexity. Extensive experiments on real datasets demonstrate the effectiveness and efficiency of the proposed algorithms.