Frequent subgraph mining based on the automorphism mapping

摘要

Frequent subgraph mining is an important research subject of graph mining. At present, there are many effective frequent subgraph mining algorithms, such as gSpan and FFSM. But these algorithms spend a lot of time solving the subgraph isomorphism or graph isomorphism problem, which affects the efficiency of the algorithm itself. According to the problem, we propose a novel frequent subgraph mining algorithm: FSMA, based on the automorphism mapping. The algorithm generate candidate subgraph through extending edges, and the extension location is determined by the automorphism mapping of subgraph. FSMA does not need to test the subgraph isomorphism or graph isomorphism throughout the process of mining frequent subgraph, so it achieves the time complexity of 0(n-2")(n is the number of frequent edges in graph dataset).