Maximal Frequent Subgraph Mining

Abstract

The area of graph mining deals with mining frequent subgraph patterns, graph classification, graph newlineclustering, graph partitioning, graph indexing and so on. In this thesis, we focus only on the area of newlinefrequent subgraph mining and more precisely on maximal frequent subgraph mining. newlineThe exponential number of possible subgraphs makes the problem of frequent subgraph mining newlinea challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent newlinesubgraphs, providing ample scope for pruning. MARGIN is a maximal subgraph mining algorithm that newlinemoves among promising nodes of the search space along the border of the infrequent and frequent newlinesubgraphs. This drastically reduces the number of candidate patterns in the search space. Experimental newlineresults validate the efficiency and the utility of the technique proposed. MARGIN-d is the extension of newlinethe MARGIN algorithm which can be applied to finding disconnected maximal frequent subgraphs. A newlinetheoretical comparison with Apriori like algorithms and analysis are presented in this thesis. newlineFurther, sometimes frequent subgraph mining problems can find simpler solutions outside the area of newlinefrequent subgraph mining by applying itemset mining to graphs of unique edge labels. This can reduce newlinethe computational cost drastically. A solution to finding maximal frequent subgraphs for graphs with newlineunique edge labels using itemset mining is presented in the thesis. newline