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 115 articles )
Showing results 1 to 20 of 115.
Sorted by year (- Haraguchi, Kazuya; Nagamochi, Hiroshi: Enumeration of support-closed subsets in confluent systems (2022)
- Ingels, Florian; Azaïs, Romain: Enumeration of irredundant forests (2022)
- Yoshida, Tomoki; Takeuchi, Ichiro; Karasuyama, Masayuki: Distance metric learning for graph structured data (2021)
- Ferré, Sébastien; Cellier, Peggy: Graph-FCA: an extension of formal concept analysis to knowledge graphs (2020)
- Le, Ngoc-Thao; Vo, Bay; Nguyen, Lam B. Q.; Fujita, Hamido; Le, Bac: Mining weighted subgraphs in a single large graph (2020)
- Meng, Jinghan; Pitaksirianan, Napath; Tu, Yi-Cheng: Counting frequent patterns in large labeled graphs: a hypergraph-based approach (2020)
- Zhang, Richong; Mao, Yongyi; Zhao, Weihua: Knowledge graphs completion via probabilistic reasoning (2020)
- Haraguchi, Kazuya; Momoi, Yusuke; Shurbevski, Aleksandar; Nagamochi, Hiroshi: COOMA: a components overlaid mining algorithm for enumerating connected subgraphs with common itemsets (2019)
- Paramonov, Sergey; Stepanova, Daria; Miettinen, Pauli: Hybrid ASP-based approach to pattern mining (2019)
- van der Hallen, Matthias; Paramonov, Sergey; Janssens, Gerda; Denecker, Marc: Knowledge representation analysis of graph mining (2019)
- Ingalalli, Vijay; Ienco, Dino; Poncelet, Pascal: Mining frequent subgraphs in multigraphs (2018)
- 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)
- Strüber, D.; Rubin, J.; Arendt, T.; Chechik, M.; Taentzer, G.; Plöger, J.: Variability-based model transformation: formal foundation and application (2018)
- Costa, Fabrizio: Learning an efficient constructive sampler for graphs (2017)
- 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)
- Ahmed, Akiz Uddin; Ahmed, Chowdhury Farhan; Samiullah, Md.; Adnan, Nahim; Leung, Carson Kai-Sang: Mining interesting patterns from uncertain databases (2016)
- Bhuiyan, Mansurul; Hasan, Mohammad Al: Interactive knowledge discovery from hidden data through sampling of frequent patterns (2016)
- Strüber, Daniel; Rubin, Julia; Arendt, Thorsten; Chechik, Marsha; Taentzer, Gabriele; Plöger, Jennifer: \textitRuleMerger: automatic construction of variability-based model transformation rules (2016)
- Talukder, N.; Zaki, M. J.: A distributed approach for graph mining in massive networks (2016)
- Uno, Takeaki; Uno, Yushi: Mining preserving structures in a graph sequence (2016)