Optimizing Frequent Subgraph Mining for Single Large Graph

Frequent subgraph mining (FSM) is defined as finding all the subgraphs in a given graph that appear more number of times than a given value. It consists of two steps broadly, first is generating a candidate subgraph and second is calculating support of that subgraph. When the input to FSM algorithm is a single graph, calculating support of subgraph needs identifying its isomorphisms in the input graph. Identifying subgraph isomorphisms is NP-Complete problem. Evidently, fewer the number of candidates, fewer the support computations needed. In this paper we present a filtration technique that reduces the number of candidate subgraphs thereby reducing the overall time complexity by 7 to 18% experimentally.