ComputingBioinformaticsData MiningData StructuresSequence AnalysisFrequent Pattern MiningGraph AlgorithmsGraph AnalyticsGraph MiningSequence MiningClosed Frequent Itemset MiningFrequent Closed Pattern MiningFrequent Itemset MiningGraph Pattern MiningPattern DiscoveryPattern MiningSubgraph Mining
Pattern discovery has evolved from frequent itemsets to structured patterns such as graphs, which model complex relations but pose challenges for mining due to an exponential number of frequent subgraphs. The study proposes mining closed frequent graph patterns instead of all subgraphs. CloseGraph defines a graph as closed when no proper supergraph shares its support, and uses several pruning methods to efficiently enumerate closed frequent graph patterns. Experiments demonstrate that CloseGraph dramatically reduces unnecessary subgraphs and substantially improves mining efficiency, particularly for large graph patterns.
Recent research on pattern discovery has progressed form mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. As a general data structure, graph can model complicated relations among data with wide applications in bioinformatics, Web exploration, and etc. However, mining large graph patterns in challenging due to the presence of an exponential number of frequent subgraphs. Instead of mining all the subgraphs, we propose to mine closed frequent graph patterns. A graph g is closed in a database if there exists no proper supergraph of g that has the same support as g. A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting pruning methods. Our performance study shows that CloseGraph not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.