CloseGraph
Xifeng Yan, Jiawei Han · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · 2003
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.
Cited by 635 works. doi:10.1145/956750.956784
Authors
References
- Introduction to Algorithms
- Fast Algorithms for Mining Association Rules in Large Databases
- Mining frequent patterns without candidate generation
- Mining frequent patterns without candidate generation
- Introduction to algorithms [2nd ed.]
- Discovering Frequent Closed Itemsets for Association Rules
- Frequent subgraph discovery
- An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
- CLOSET : An Efficient Algorithm for Mining Frequent Closed Itemsets
- CHARM: An Efficient Algorithm for Closed Itemset Mining