M2M: Subgraph Matching Based on Minimum Spanning Tree and Candidate Graph

Subgraph matching is one of the most basic and important problems in graphdata analysis due to its wide utilization in a variety of applications. It has alwaysbeen an open challenge due to that it is theoretically an NP-hard problem. Recentefforts have made good progress in most of the application scenarios. However,it is still full of potentialities to study more efficient algorithms to address thisproblem. Here, we propose a new algorithm, called M2M, for subgraph match-ing based on minimum spanning tree and candidate graph. The M2M algorithmfirst optimizes the matching order of the query nodes based on minimum span-ning tree to reduce the candidate space size. Then an efficient strategy basedon a minimum to minimum idea is proposed for generating the minimum can-didate graph of the query. Moreover, several optimization tricks are proposedsuch as indexing the candidate graph, calculating the size of the embeddings,enumerating the embeddings and so on. Finally, we carried out experiments onseveral real datasets and the results show that our algorithm M2M achieveshigher performance than state-of-the-art methods.