FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Subgraph Enumeration <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> Subgraph Enumeration <s> As data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. An alternate way of modeling the objects in these data sets is to use graphs. Within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs.The authors present a computationally efficient algorithm for finding all frequent subgraphs in large graph databases. We evaluated the performance of the algorithm by experiments with synthetic datasets as well as a chemical compound dataset. The empirical results show that our algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though we have to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery. <s> BIB002
The current methods for enumerating all the subgraphs might be classified into two categories: one is the join operation adopted by FSG BIB002 and AGM BIB001 and another one is the extension operation . The major concerns for the join operation are that a single join might produce multiple candidates and that a candidate might be redundantly proposed by many join operations. The concern for the extension operation is to restrict the nodes that a newly introduced edge may attach to. Equivalence class based extension (Zaki 2002 (Zaki ,2005 ) is founded on a DFS-LS representation for trees. Basically, a (k + 1)-subtree is generated by joining two frequent ksubtrees. The two k subtrees must be in the same equivalence class . An equivalence class consists of the class prefix encoding, and a list of members. Each member of the class can be represented as a (l, p) pair, where l is the k-th vertex label and p is the depth-first position of the k-th vertex's parent. It is verified, in Zaki (2002), that all potential (k + 1)-subtrees with the prefix [C] of size (k − 1) can be generated by joining each pair of members of the same equivalent class [C] .Equivalence classes can be based on either prefix or suffix.