A Method for Efficiently Deriving Connected Frequent Subgraphs from Graph Structured Data
Original Publication Date: 2002-Nov-26
Included in the Prior Art Database: 2002-Nov-26
Graph structured data mining to derive frequent subgraphs from a graph dataset is difficult because the search for subgraphs is combinatorially explosive, and includes subgraph isomorphism matching.The past research on this issue has not show the sufficient performance for practical use. In this paper, we propose a new approach called AcGM which achieves the complete search of frequent connected (induced) subgraphs in a massive labeled graph dataset within highly practical time.The power of AcGM comes from the algebraic representation of graphs, its associated operations and well-organized constraints to limit the search space efficiently. Its performance has been evaluated through some artificial simulation data and real world data. The high scalability of AcGM has been confirmed for the amount of data, the complexity of graphs and the computation time.