gSpan: graph-based substructure pattern mining
Xifeng Yan, Jiawei Han · Proceedings · 2003
We investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called gSpan (graph-based substructure pattern mining), which discovers frequent substructures without candidate generation. gSpan builds a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Our performance study shows that gSpan substantially outperforms previous algorithms, sometimes by an order of magnitude.
Cited by 2,013 works. doi:10.1109/icdm.2002.1184038
Authors
References
- Fast algorithms for mining association rules
- PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
- gSpan: graph-based substructure pattern mining
- Frequent subgraph discovery
- An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
- Efficiently mining frequent trees in a forest
- Introduction to Algorithms
- Efficient Substructure Discovery from Large Semi-structured Data
- Efficiently mining frequent trees in a forest
- Efficient Substructure Discovery from Large Semi-structed Data