FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Apriori Based Approach <s> This paper proposes a novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set. A graph transaction is represented by an adjacency matrix, and the frequent patterns appearing in the matrices are mined through the extended algorithm of the basket analysis. Its performance has been evaluated for the artificial simulation data and the carcinogenesis data of Oxford University and NTP. Its high efficiency has been confirmed for the size of a real-world problem. <s> BIB001 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Apriori Based Approach <s> Several algorithms have already been implemented which combine association rules with first order logic formulas. Although this resulted in several usable algorithms, little attention was payed until recently to the efficiency of these algorithms. In this paper we present some new ideas to turn one important intermediate step in the process of discovering such rules, i.e. the discovery of frequent item sets, more efficient. Using an implementation that we coined FARMER, we show that indeed a speed-up is obtained and that, using these ideas, the performance is much more comparable to original association rule algorithms. <s> BIB002 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Apriori Based Approach <s> One fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of such patterns. In large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. In this paper, we propose a new algorithm that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. This may exponentially decrease the size of the output set in the best case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude.Our method first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. Using two chemical structure benchmarks and a set of synthetic graph data sets, we demonstrate that, in addition to decreasing the output size, our algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms. <s> BIB003 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Apriori Based Approach <s> 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. <s> BIB004
Apriori-based frequent substructure mining algorithms share similar characteristics with Aprioribased frequent itemset mining algorithms. The search for frequent graphs starts with graphs of small "size", and proceeds in a bottom-up manner. At each iteration, the size of newly discovered frequent substructures is increased by one. These new substructures are first generated by joining two similar but slightly different frequent subgraphs that were discovered already. The frequency of the newly formed graphs is then checked. The Apriori-based algorithms have considerable overhead when two size-k frequent substructures are joined to generate size-(k+1) graph candidates. Typical Apriori-based frequent substructure mining algorithms are discussed in the following paragraphs. The AGM BIB001 algorithm uses a vertex-based candidate generation method that increases the substructure size by one vertex at each iteration. Two size-k frequent graphs are joined only when the two graphs have the same size-(k − 1). ISG  represents graphs in an entirely different manner. It transforms the input set of graphs into item sets which are then represented using edge triplet. ISG uses a approach known as edge triplet extension in which a discovered item set is extended by adding one edge triplet in each iteration. ISG carries out frequent subgraph discovery by transforming graphs into itemsets followed by frequent itemset discovery, which is also apriori-based. The resultant frequent itemsets are transformed back to subgraphs. In pattern-growth approach, the subgraph generation is carried out by extending the previously discovered subgraph by one node or one edge. ISG use transaction identifier (TID) lists for frequency counting. Each frequent subgraph has a list of transaction identifiers which support it. For computing frequency of a k subgraph, the intersection of the TID lists of (k -1) subgraphs is computed. FARMER BIB002 uses trie for graph representation. In level-wise search, the algorithm finds a subgraph and then enumerates the instances of the subgraph by one adjacent edge in all possible ways. FARMER follow this mechanism for subgraph generation. FARMER, which has been developed as an enhancement to WARMR, an earlier developed algorithm which works on the basis of ILP approach, is based on a combination of a priori and ILP approaches. FARMER uses the trie data structure for frequency computation also. HSIGRAM [22] uses adjacency matrix representation of graph. HSIGRAM use iterative merging for subgraph generation. In case of HSIGRAM the aim is to find the maximal independentset of a graph which is constructed out of the embeddings of a frequent subgraph so as to evaluate its frequency. Huan, wang and Prince  in 2003 proposed a novel subgraph mining algorithm: FFSM, which employs a vertical search scheme within an algebraic graph framework.It uses a restricted join operation to generate candidates and stores embeddings to avoid explicit subgraph isomorphism testing. It uses a sub-optimal canonical adjacency matrix tree for counting the frequency. Their studies on synthetic and real datasets demonstrated that FFSM achieves a substantial performance gain over the start-of-the art subgraph mining algorithm gSpan. One fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of suchpatternsc. In large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. Jun Huan, Wei WangPrins, Jiong Yang, Jan BIB003 proposed a new algorithm, Spin that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. This may exponentially decrease the size of the output set in the best-case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude. It first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. SPIN offered very good scalability to large graph databases and at least an order of magnitude performance improvement in synthetic graph data sets. The efficiency of the algorithm is also confirmed by a benchmark chemical data set. This algorithm of compressing large number of frequent subgraphs to a much smaller set of maximal subgraphs.lt is used to investigate demanding applications such as finding structure patterns from proteins in the future. MichihiroKuramochi and George Karypis  in 2004 proposed a heuristic algorithm called GREW to overcome the limitations of existing complete or heuristic frequent subgraph discovery algorithms. GREW is designed to operate on a large graph and to find patterns corresponding to connected subgraphs that have a large number of vertex-disjoint embeddings. Their experimental evaluation showed that GREW is efficient, can scale to very large graphs, and find non-trivial patterns that cover large portions of the input graph and the lattice of frequent patterns. Karsten M. Borgwardt, Hans-Peter Kriegel, Peter Wackersreuther  investigated how pattern mining on static graphs can be extended to time series of graphs, ie. dynamic graphs. They proposed a framework into which Existingsubgraph mining algorithms can be easily integrated and handle dynamic graphs. Experimental results on real-world data confirm the practical feasibility of their approach. In particular, we are looking for subgraphs that are topologically frequent within a large graph and that show insertions and deletions of edges in the same temporal order. It might be used to study frequent motifs in protein-protein interaction dynamics, as well as in social or telecommunication networks. Lini T Thomas Satyanarayana R ValluriKamalakarKarlapalem BIB004 in 2006 proposed an algorithm MARGIN that mines maximal frequent subgraphs. MARGIN-Maximal frequent mining has triggered much interest since the size of the set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs. The set of candidate subgraphs which are likely to bemaximally frequent are the set of -edge frequent subgraphs that have a z-edge infrequent supergraph. The Margin algorithm computessuch a candidate set efficiently and finds the maximal subgraphs by a post-processing step. They have proved that the performance of the Margin algorithm is 20 times faster than gSpan for certain datasets. ZhaonianZou, Jianzhong Li, andShuo Zhang  in 2010 proposed an algorithm for Mining Frequent SubgraphPatternsfrom Uncertain Graph Data. In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graphdata. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. An approximate mining algorithm called MUSE (Mining Uncertain Sub graph pattErns), is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results showed that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. This is the first algorithm to investigate the problem of mining frequent sub graph patterns from uncertain graph data.