gSpan
gSpan: graph-based substructure pattern mining. 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.
Keywords for this software
References in zbMATH (referenced in 79 articles )
Showing results 1 to 20 of 79.
Sorted by year (- Uno, Takeaki; Uno, Yushi: Mining preserving structures in a graph sequence (2016)
- Khan, Kifayat Ullah; Nawaz, Waqas; Lee, Young-Koo: Set-based approximate approach for lossless graph summarization (2015)
- Shahrivari, Saeed; Jalili, Saeed: Distributed discovery of frequent subgraphs of a network using MapReduce (2015)
- Frasconi, Paolo; Costa, Fabrizio; De Raedt, Luc; De Grave, Kurt: kLog: a language for logical and relational learning with kernels (2014)
- Galbrun, Esther; Kimmig, Angelika: Finding relational redescriptions (2014)
- Morales-González, Annette; Acosta-Mendoza, Niusvel; Gago-Alonso, Andrés; García-Reyes, Edel B.; Medina-Pagola, José E.: A new proposal for graph-based image classification using frequent approximate subgraphs (2014)
- Negrevergne, Benjamin; Termier, Alexandre; Rousset, Marie-Christine; Méhaut, Jean-François: Para Miner: a generic pattern mining algorithm for multi-core architectures (2014)
- Ribeiro, Pedro; Silva, Fernando: G-Tries: a data structure for storing and finding subgraphs (2014)
- Shelokar, Prakash; Quirin, Arnaud; Cordón, Óscar: Three-objective subgraph mining using multiobjective evolutionary programming (2014)
- Spyropoulou, Eirini; De Bie, Tijl; Boley, Mario: Interesting pattern mining in multi-relational data (2014)
- Berlingerio, Michele; Pinelli, Fabio; Calabrese, Francesco: ABACUS: frequent pattern mining-based community discovery in multidimensional networks (2013)
- Garriga, Gemma C.: Formal methods for mining structured objects (2013)
- Garriga, Gemma C.; Khardon, Roni; De Raedt, Luc: Mining closed patterns in relational, graph and network data (2013)
- Kibriya, Ashraf M.; Ramon, Jan: Nearly exact mining of frequent trees in large networks (2013)
- Kuznetsov, Sergei O.: Fitting pattern structures to knowledge discovery in big data (2013)
- Livi, Lorenzo; Rizzi, Antonello: The graph matching problem (2013)
- Nettleton, David F.: Data mining of social networks represented as graphs (2013)
- Schietgat, Leander; Ramon, Jan; Bruynooghe, Maurice: A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics (2013)
- Shelokar, Prakash; Quirin, Arnaud; Cordón, Óscar: A multiobjective evolutionary programming framework for graph-based data mining (2013)
- Torti, Lionel; Gonzales, Christophe; Wuillemin, Pierre-Henri: Speeding-up structured probabilistic inference using pattern mining (2013)