A-RAFF: A Ranked Frequent Pattern-growth Subgraph Pattern Discovery Approach

Abstract

Graph mining is one of the arms of Data Mining in which voluminous complex data are represented in the form of graphs and mining is done to infer useful knowledge from them. Frequent subgraph mining (FSM) is an active research field and is considered as the essence of graph mining. FSM is defined as finding all the subgraph patterns that occur frequently over the entire set of graphs. FSM is extensively used in graph clustering, classification and building indices in the databases. In literature, different FSM algorithms have been proposed such as AGM, FSG, SPIN, SUBDUE, gSpan, FFSM, CloseGraph, FSG, GREW. Most of these FSM techniques perform very well for small to medium size graph datasets, but the computational cost of FSM becomes very critical when the graph size is increased. In accession to this, the number of frequent subgraphs patterns grows exponentially with the increasing size of graph datasets. Consequently, in this research work, a novel FSM approach A RAnked Frequent pattern-growth Framework (A-RAFF) is proposed. This work is a preliminary work to study on how to make A-RAFF both computational effective and avoid the generation of the huge number of useless frequent subgraph patterns. A-RAFF has achieved efficiency by embedding the ranking of discovering FSGs during the mining process. The experiments on the three different real benchmark graph datasets demonstrated that the mining results of A-RAFF are very promising as compared to the existing FSM techniques.