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.


References in zbMATH (referenced in 100 articles )

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

1 2 3 4 5 next

  1. Ferré, Sébastien; Cellier, Peggy: Graph-FCA: an extension of formal concept analysis to knowledge graphs (2020)
  2. Haraguchi, Kazuya; Momoi, Yusuke; Shurbevski, Aleksandar; Nagamochi, Hiroshi: COOMA: a components overlaid mining algorithm for enumerating connected subgraphs with common itemsets (2019)
  3. van der Hallen, Matthias; Paramonov, Sergey; Janssens, Gerda; Denecker, Marc: Knowledge representation analysis of graph mining (2019)
  4. Ravkic, Irma; Žnidaršič, Martin; Ramon, Jan; Davis, Jesse: Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model (2018)
  5. Strüber, D.; Rubin, J.; Arendt, T.; Chechik, M.; Taentzer, G.; Plöger, J.: Variability-based model transformation: formal foundation and application (2018)
  6. Costa, Fabrizio: Learning an efficient constructive sampler for graphs (2017)
  7. Gkantouna, Vassiliki; Tzimas, Giannis: Mining domain-specific design patterns: a case study (2017)
  8. Hong, Jihye; Park, Kisung; Han, Yongkoo; Rasel, Mostofa Kamal; Vonvou, Dawanga; Lee, Young-Koo: Disk-based shortest path discovery using distance index over large dynamic graphs (2017)
  9. Ahmed, Akiz Uddin; Ahmed, Chowdhury Farhan; Samiullah, Md.; Adnan, Nahim; Leung, Carson Kai-Sang: Mining interesting patterns from uncertain databases (2016)
  10. Strüber, Daniel; Rubin, Julia; Arendt, Thorsten; Chechik, Marsha; Taentzer, Gabriele; Plöger, Jennifer: \textitRuleMerger: automatic construction of variability-based model transformation rules (2016)
  11. Talukder, N.; Zaki, M. J.: A distributed approach for graph mining in massive networks (2016)
  12. Uno, Takeaki; Uno, Yushi: Mining preserving structures in a graph sequence (2016)
  13. Dahm, Nicholas; Bunke, Horst; Caelli, Terry; Gao, Yongsheng: Efficient subgraph matching using topological node feature constraints (2015)
  14. Du, Lingxia; Li, Cuiping; Chen, Hong; Tan, Liwen; Zhang, Yinglong: Probabilistic SimRank computation over uncertain graphs (2015)
  15. Erciyes, K.: Distributed and sequential algorithms for bioinformatics (2015)
  16. Khan, Kifayat Ullah; Nawaz, Waqas; Lee, Young-Koo: Set-based approximate approach for lossless graph summarization (2015)
  17. Pan, Shirui; Wu, Jia; Zhu, Xingquan; Long, Guodong; Zhang, Chengqi: Finding the best not the most: regularized loss minimization subgraph selection for graph classification (2015)
  18. Shahrivari, Saeed; Jalili, Saeed: Distributed discovery of frequent subgraphs of a network using MapReduce (2015)
  19. Frasconi, Paolo; Costa, Fabrizio; De Raedt, Luc; De Grave, Kurt: kLog: a language for logical and relational learning with kernels (2014)
  20. Galbrun, Esther; Kimmig, Angelika: Finding relational redescriptions (2014)

1 2 3 4 5 next