FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Pattern-growth approach <s> We investigate new approaches for frequent graph-based pattern mining in graph datasets and propose a novel algorithm called gSpan (graph-based substructure pattern mining), which discovers frequent substructures without candidate generation. gSpan builds a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label. Based on this lexicographic order gSpan adopts the depth-first search strategy to mine frequent connected subgraphs efficiently. Our performance study shows that gSpan substantially outperforms previous algorithms, sometimes by an order of magnitude. <s> BIB001 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Pattern-growth approach <s> We present an algorithm to find fragments in a set of molecules that help to discriminate between different classes of for instance, activity in a drug discovery context. Instead of carrying out a brute-force search, our method generates fragments by embedding them in all appropriate molecules in parallel and prunes the search tree based on a local order of the atoms and bonds, which results in substantially faster search by eliminating the need for frequent, computationally expensive reembeddings and by suppressing redundant search. We prove the usefulness of our algorithm by demonstrating the discovery of activity-related groups of chemical compounds in the well-known National Cancer Institute's HIV-screening dataset. <s> BIB002 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Pattern-growth approach <s> A major challenge in frequent subgraph mining is the sheer size of its mining results. In many cases, allow minimum support may generate an explosive number of frequent subgraphs, which severely restricts the usage of frequent sub graph mining. In this paper, we study anew problem of mining frequent jump patterns from graph databases. Mining frequent jump patterns can dramatically reduce the number of output graph patterns, and still capture interesting graph patterns. By integrating the operation of checking jump patterns into the well-known DFS code tree enumeration framework, we present an efficient algorithm JPMiner for this new problem. We experimentally evaluate various aspects of Jupiter using both real and synthetic datasets. Experimental results demonstrate that the number of frequent jump patterns is much smaller than that of closed frequent graph patterns, and JPMiner is efficient and scalable in mining frequent jump patterns. <s> BIB003 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Pattern-growth approach <s> Most of existing frequent subgraph mining algorithms are used to deal with undirected unlabeled marked graph. A few of them aim at directed graph or labeled graph. But in the real world ,a lot of connections have direction and label,so directed labeled graph mining is more meaningful. Now we are analyzing a financial network which can be modeled by a directed weighted graph. We are interested in the patterns which are frequent.The graph pattern means a uniform expression of graphs which has different marked nodes but same structure. In our application we consider direction and weight as part of the pattern. It’s different from subgraph because subgraph mining consider the labels of nodes. This paper proposes a new algorithm mSpan for directed labeled graph frequent pattern mining. Based on FP-growth, the algorithm gets a minimum edge code and an abstract node code sequence to indentify a directed graph pattern uniquely through minimum extension. It can solve the graph pattern isomorphic problem and the redundant extension problem. The experiment shows that mSpan can mine all frequent directed, labeled graph patterns. <s> BIB004 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Pattern-growth approach <s> We investigate the problem of summarizing frequent subgraphs by a smaller set of representative patterns. We show that some special graph patterns, called δ-jump patterns in this paper, must be representative patterns. Based on the fact, we devise two algorithms, RP-FP and RP-GD, to mine a representative set that summarizes frequent subgraphs. RP-FP derives a representative set from frequent closed subgraphs, whereas RP-GD mines a representative set from graph databases directly. Three novel heuristic strategies, Last-Succeed-First-Check, Reverse-Path-Trace, and Nephew-Representative-Based-Cover, are proposed to further improve the efficiency of RP-GD. RP-FP can provide a tight ratio bound but has heavy computation cost. RP-GD cannot provide a ratio bound guarantee but is more efficient than RP-FP. We also make use of the similarity between sibling branches in the graph pattern space to devise another much more efficient algorithm, RP-Leap, for mining a representative set that can approximately summarize frequent subgraphs. Our extensive experiments on both real and synthetic data sets verify the summarization quality and efficiency of our algorithms. To further demonstrate the interestingness of representative patterns, we study an application of representative patterns to classification. We demonstrate that the classification accuracy achieved by representative pattern-based model is no less than that achieved by closed graph pattern-based model. <s> BIB005
In order to avoid the overhead of apriori algorithms, non-Apriority-based algorithms have been developed, most of which adopt the pattern-growth methodology, as discussed below. Patterngrowth-based graph pattern mining algorithms include gSpan by Yan A potential problem with the edge extension is that the same graph can be discovered many times. The gSpan BIB001 algorithm solves this problem by introducing a right-most extension technique, where the only extensions take place on the rightmost path. A right-most path is the straight path from the starting vertex v0 to the last vertex vn, according to a depth-first search on the graph. Typical pattern growth algorithms are discussed in the following paragraphs. Frequency counting process for Gaston is carried out with the help of embedding lists, where all the occurrences of a particular label are stored in the embedding lists. Borgelt and Berthold BIB002 in 2002 presented an algorithm Mofa to find fragments in a set of molecules that help to discriminate between different classes for instance, activity in a drug discovery context. Yan and Han BIB001 in 2002 investigated new approaches for frequent graphbased pattern mining in graph datasets and proposed a novel algorithm called gSpan. gSpan is a graph-based substructure pattern mining. This discovered frequent substructures without candidate generation. Yan and Han  in 2003 proposed to mine closed frequent graph patterns. A graph g is closed in a database if there exists no proper subgraph of g that has the same support as g. A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting looping methods. Their performance studies shown that CloseGraph not only dramatically reduces unnecessary subgraphs to be generated, but also substantially increases the efficiency of mining, especially in the presence of large graph patterns. Yong Liu, Jianzhong Li, Hong Gao BIB003 in 2009 studied the problem of mining frequent jump patterns from graph databases. They have showed that Mining frequent jump patterns can dramatically reduce the number of output graph patterns, and still capture interesting graph patterns. By integrating the operation of checking jump patterns into the well-known DFS code tree enumeration framework, they presented an efficient algorithm JPMiner for this new problem. Their experimental evaluation of JPMiner using both real and synthetic datasets, showed that the number of frequent jump patterns is much smaller than that of closed frequent graph patterns, and also JPMiner is efficient and scalable in mining frequent jump patterns. Most of existing frequent subgraph mining algorithms are used to deal with undirected unlabeled marked graph. A few of them aim at directed graph or labeled graph because it is very complex to consider that. But in the real world, a lot of connections have directions and labels, so directed labeled graph mining is more meaningful. Yuhua Li Quan Lin and DuanYanan BIB004 Bi in 2009 analyzed a financial network by modelling it as a directed weighted graph. They proposed a new algorithm mSpan for directed labeled graph frequent pattern mining. Based on FP-growth, the algorithm gets a minimum edge code and an abstract node code sequence to identify a directed graph pattern uniquely through minimum extension. It also solved the graph pattern isomorphic problem and the redundant extension problem. Their experiment showed that mSpan can mine all frequent directed, labeled graph patterns. Cheng-Te Li, Hsun-Ping Hsieh  proposed a novel algorithm, TSP-algorithm (Temporal Subgraph Patterns algorithm) to mine the patterns which contain temporal information and forms a connective subgraph. The proposed method recursively grows the patterns in a depth-first search manner. Since the TSP-algorithm only needs to scan the database once and does not generate unnecessary candidates, the experiment results showed that the TSP-algorithm outperforms the modified Apriori on time-efficiency and memory usage in both synthetic and real datasets. Jianzhong Li, Yong Liu, and Hong GaoWe BIB005 in 2011 investigated the problem of summarizing frequent subgraphs by a smaller set of representative patterns. They showed that some special graph patterns, called _-jump patterns , must be representative patterns. Based on the fact,they devised two algorithms, RP-FP and RP-GD, to mine a representative set that summarizes frequent subgraphs. RP-FP derives a representative set from frequent closed subgraphs, whereas RP-GD mines a representative set from graph databases directly. Three novel heuristic strategies, Last-Succeed-First-Check, Reverse-Path-Trace, and Nephew-RepresentativeBased-Cover, are proposed to further improve the efficiency of RP-GD. RP-FP can provide a tight ratio bound but has heavy computation cost. RP-GD cannot provide a ratio bound guarantee but is more efficient than RP-FP. They also made use of the similarity between sibling branches in the graph pattern space to devise another much more efficient algorithm, RP-Leap, for mining a representative set that can approximately summarize frequent subgraphs. Their extensive experiments on both real and synthetic data sets verify the summarization quality and efficiency of the algorithms. patterns to classification. They also demonstrated that the classification accuracy achieved by representative pattern graph pattern-based model.