Current algorithms for Maximal Frequent Sub-graph (MFS) mining do not scale to large databases with more than 300k graphs. Frequency computation is commonly done using numerous sub graph isomorphism operations, which are computationally expensive. This paper explores a partition-based secondary memory algorithm, PMCS, that can make MFS mining for large databases viable. PMCS intelligently avoids redundant computations to perform frequency computation operations optimally. Its intermediate results are also small enough to fit in the main memory. Our results demonstrate that PM CS scales to databases of up to 1000k graphs with an average of 25–30 edges per graph.

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal subgraph mining algorithm that moves among promising nodes of the search space along the “border” of the infrequent and frequent subgraphs. This drastically reduces the number of candidate patterns in the search space. The proof of correctness of the algorithm is presented. Experimental results validate the efficiency and utility of the technique proposed.

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs, thus providing ample scope for pruning. MARGIN is a maximal subgraph mining algorithm that moves among promising nodes of the search space along the "border" of the infrequent and frequent subgraphs. This drastically reduces the number of candidate patterns considered in the search space. Experimental results validate the efficiency and utility of the technique proposed.