Frequent Subgraph Mining And Its Application In Compound Property Prediction

Frequent subgraph mining is the most basic and most important research content of graph mining, it has wide application field. In practical application, frequent subgraph mining algorithm has a high requirement on the efficiency, but the complexity of the graph structure data makes frequent subgraph mining face many challenges, especially the graph isomorphism and subgraph isomorphism problem. At present, there is no polynomial time algorithm to solve the subgraph isomorphism problem, and the subgraph isomorphism problem has been determined to be a NP-complete problem. In order to research the high-efficiency algorithm for mining frequent subgraph, how to deal with these problems effectively has become the attention focus of researchers.In order to calculate the support of candidate subgraph, the current major algorithms for frequent subgraph mining mostly involve a lot of subgraph isomorphism testing, that affect the efficiency of the algorithms itself. To this end, some algorithms convert the subgraph isomorphism problem into a graph isomorphism problem or encode graph into the unique form, but these can not solve the problem fundamentally, because graph isomorphism testing or encode graph into the unique form still need to consume a lot of time. Considering these problems, the frequent subgraph mining algorithm based on the automorphism mapping is proposed in this paper. In order to generate candidate subgraph, it record the isomorphism mapping relationship between subgraph, then build automorphism mapping table and extend edge from subgraph according to it. The algorithm do not need to test subgraph isomorphism or graph isomorphism for calculating the support of candidate subgraph, thus the efficiency of the algorithm is improved, the time complexity of the algorithm achieve0(2"·n). The experimental result also show that the algorithm can mining frequent subgraph effectively.In addition, on the basis of research on frequent subgraph mining algorithm, it is applied to the compound property prediction in this paper, and good result is obtained.