FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Graph Representations <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> BIB001 </s> FREQUENT SUBGRAPH MINING ALGORITHMS- A SURVEY AND FRAMEWORK FOR CLASSIFICATION <s> Graph Representations <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> BIB002
The simplest mechanism whereby a graph structure can be represented is by employing an adjacency matrix or adjacency list. Using an adjacency matrix the rows and columns represent vertexes, and the intersection of row i and column j represents a potential edge connecting the vertexes vi and vj . The value held at intersection < i, j > typically indicates the number of links from vi to vj . However, the use of adjacency matrices, although straightforward, does not lend itself to isomorphism detection, because a graph can be represented in many different ways depending on how the vertexes (and edges) are enumerated (Washio&Motoda 2003) . With respect to isomorphism testing it is therefore desirable to adopt a consistent labeling strategy that ensures that any two identical graphs are labeled in the same way regardless of the order in which vertexes and edges are presented (i.e. a canonical labeling strategy). A canonical labeling strategy defines a unique code for a given graph. Canonical labeling facilitates isomorphism checking because it ensures that if a pair of graphs are isomorphic, then their canonical labeling will be identical BIB001 (Kuramochi&Karypis 2001). One simple way of generating a canonical labeling is to flatten the associated adjacency matrix by concatenating rows or columns to produce a code comprising a list of integers with a minimum (or maximum) lexicographical ordering imposed. To further reduce the computation resulting from the permutations of the matrix, canonical labeling are usually compressed, using what is known as a vertex invariant scheme (Read &Corneil 1977) , that allows the content of an adjacency matrix to be partitioned according to the vertex labels. Various canonical labeling schemes have been proposed, some of the more significant are described in this subsection. Minimum DFS Code (M-DFSC): There are a number of variants of DFS encodings, but essentially each vertex is given a unique identifier generated from a DFS traversal of a graph (DFS subscripting). Each constituent edge of the graph in the DFS code is then represented by a 5-tuple: (i, j, li, le, lj), where i and j are the vertex identifiers, li and lj are the labels for the corresponding vertexes, and le is the label for the edge connecting the vertexes. Based on the DFS lexicographic order, the M-DFSC of a graph g can be defined as the canonical labeling of g BIB002 ( 