Efficient mining of frequent subgraphs in the presence of isomorphism

TLDR

Frequent subgraph mining is an active research topic in data mining, with graphs used to model data in domains such as cheminformatics and bioinformatics, but pattern mining is challenging due to the high time complexity of graph operations compared to itemsets, sequences, and trees. We propose a novel frequent subgraph mining algorithm, FFSM, to reduce redundant candidate generation. FFSM employs a vertical search scheme within an algebraic graph framework to achieve this. Our empirical study on synthetic and real datasets shows that FFSM achieves a substantial performance gain over the current state‑of‑the‑art subgraph mining algorithm gSpan.

Abstract

Frequent subgraph mining is an active research topic in the data mining community. A graph is a general model to represent data and has been used in many domains like cheminformatics and bioinformatics. Mining patterns from graph databases is challenging since graph related operations, such as subgraph testing, generally have higher time complexity than the corresponding operations on itemsets, sequences, and trees, which have been studied extensively. We propose a novel frequent subgraph mining algorithm: FFSM, which employs a vertical search scheme within an algebraic graph framework we have developed to reduce the number of redundant candidates proposed. Our empirical study on synthetic and real datasets demonstrates that FFSM achieves a substantial performance gain over the current start-of-the-art subgraph mining algorithm gSpan.