A Vertex-extension based Algorithm for Frequent Pattern Mining from Graph Databases

Authors

  • Md Tanvir Alam Department of Computer Science and Engineering, University of D haka, Bangladesh
  • Chowdhury Farhan Ahmed Department of Computer Science and Engineering, University of D haka, Bangladesh
  • Md Samiullah Department of Computer Science and Engineering, University of D haka, Bangladesh

DOI:

https://doi.org/10.3329/dujase.v7i1.62887

Keywords:

Graph mining, Knowledge graphs.

Abstract

Frequent pattern mining is a core problem in data mining. Algorithms for frequent pattern mining have been proposed for itemsets, sequences, and graphs. However, existing graph mining frameworks follow an edge-growth approach to building patterns which limits many applications. Motivated by real-life problems, in this work, we define a novel graph mining framework that incorporates vertex-based extensions along with the edge-growth approach. We also propose an efficient algorithm for mining frequent subgraphs. To deal with the exploding search space, we introduce a canonical labeling technique for isomorphic candidates as well as downward closure property-based search space pruning. We present an experimental analysis of our algorithm on real-life benchmark graph datasets to demonstrate the performance in terms of runtime.

DUJASE Vol. 7(1) 58-65, 2022 (January)

Abstract
63
PDF
61

Downloads

Published

2023-02-01

How to Cite

Alam, M. T. ., Ahmed, C. F., & Samiullah, M. (2023). A Vertex-extension based Algorithm for Frequent Pattern Mining from Graph Databases. Dhaka University Journal of Applied Science and Engineering, 7(1), 58–65. https://doi.org/10.3329/dujase.v7i1.62887

Issue

Section

Articles