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.

References in zbMATH (referenced in 87 articles )

Showing results 1 to 20 of 87.
Sorted by year (citations)

1 2 3 4 5 next

  1. Strüber, D.; Rubin, J.; Arendt, T.; Chechik, M.; Taentzer, G.; Plöger, J.: Variability-based model transformation: formal foundation and application (2018)
  2. Costa, Fabrizio: Learning an efficient constructive sampler for graphs (2017)
  3. Strüber, Daniel; Rubin, Julia; Arendt, Thorsten; Chechik, Marsha; Taentzer, Gabriele; Plöger, Jennifer: \itRuleMerger: automatic construction of variability-based model transformation rules (2016)
  4. Uno, Takeaki; Uno, Yushi: Mining preserving structures in a graph sequence (2016)
  5. Dahm, Nicholas; Bunke, Horst; Caelli, Terry; Gao, Yongsheng: Efficient subgraph matching using topological node feature constraints (2015)
  6. Du, Lingxia; Li, Cuiping; Chen, Hong; Tan, Liwen; Zhang, Yinglong: Probabilistic SimRank computation over uncertain graphs (2015)
  7. Khan, Kifayat Ullah; Nawaz, Waqas; Lee, Young-Koo: Set-based approximate approach for lossless graph summarization (2015)
  8. Shahrivari, Saeed; Jalili, Saeed: Distributed discovery of frequent subgraphs of a network using MapReduce (2015)
  9. Frasconi, Paolo; Costa, Fabrizio; De Raedt, Luc; De Grave, Kurt: kLog: a language for logical and relational learning with kernels (2014)
  10. Galbrun, Esther; Kimmig, Angelika: Finding relational redescriptions (2014)
  11. 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) ioport
  12. Negrevergne, Benjamin; Termier, Alexandre; Rousset, Marie-Christine; Méhaut, Jean-François: Para Miner: a generic pattern mining algorithm for multi-core architectures (2014)
  13. Ribeiro, Pedro; Silva, Fernando: G-Tries: a data structure for storing and finding subgraphs (2014)
  14. Shelokar, Prakash; Quirin, Arnaud; Cordón, Óscar: Three-objective subgraph mining using multiobjective evolutionary programming (2014)
  15. Spyropoulou, Eirini; De Bie, Tijl; Boley, Mario: Interesting pattern mining in multi-relational data (2014)
  16. Berlingerio, Michele; Pinelli, Fabio; Calabrese, Francesco: ABACUS: frequent pattern mining-based community discovery in multidimensional networks (2013)
  17. Garriga, Gemma C.: Formal methods for mining structured objects (2013)
  18. Garriga, Gemma C.; Khardon, Roni; De Raedt, Luc: Mining closed patterns in relational, graph and network data (2013)
  19. Kibriya, Ashraf M.; Ramon, Jan: Nearly exact mining of frequent trees in large networks (2013)
  20. Kuznetsov, Sergei O.: Fitting pattern structures to knowledge discovery in big data (2013)

1 2 3 4 5 next