A survey of frequent subgraph mining algorithms

If a graph is frequent, then all of its subgraphs will also be frequent.

A simple graph is an unweighted and undirected graph with no loops and no multiple links between any two distinct nodes (Gibbons, 1985; West, 2000).

The length of a path is equivalent to the number of edges in the path.

A labelled ordered tree, in graph theory, is also called a rooted plane tree (West, 2000).

A pre-order traversal is where a sequence of operations are performed recursively as follows: visit the root first, and then do a pre-order traversal of each of the subtrees of the root one-by-one in the order given (Preiss, 1998).

k refers to the expansion unit for growing the candidate subtrees, which can be expressed in terms of vertexes, edges.

In Zaki (2002), two k-subtrees T₁, T₂ are in the same ‘prefix’ equivalence class if and only if they share the same encoding up to the (k − 1)-th vertex.

The left-most leaf of the tree is the first leaf vertex in the DFS traversal of that tree (Hido & Kawano, 2005).

IP multicast: a method for building multicast trees at the Internet Protocol layer so as to send packets to multiple receivers in a single transmission (Paul, 1998).

The level of embedding is defined as ‘the length of path between two vertexes that form an ancestor–descendant relationship’ (Tan et al., 2006).

The prüfer sequence (Prüfer, 1918) of a labelled tree on n vertexes is a unique (n − 2) length sequence that can be formed by an iterative algorithm (Tatikonda et al., 2006).

The path from the root to the left-most leaf is the left-most path (Tatikonda et al., 2006).

Two embeddings in a graph G are vertex-disjoint, if they do not share any vertexes in G.

Automorphism is a graph isomorphism to itself via a non-identity mapping.

In the candidate generation phase, a core is a common (k − 1) subgraph shared by two frequent k subgraphs. Two frequent k subgraphs are eligible for joining only if they contain the same core (Kuramochi & Karypis, 2001).

An edge-angle list is a multi-set where each element represents the angle formed by two distinct edges sharing the same end points.

An overlap graph for a given pattern with a set of all embeddings (occurrences) is a constructed graph where each vertex represents a non-identical embedding of the pattern; two vertexes are connected if the corresponding embeddings overlap (Kuramochi & Karypis, 2005).

Network Motifs are defined as ‘patterns of interconnections occurring in complex networks at numbers that are significantly higher than those in randomized networks’ (Milo et al., 2002).

The minimum degree of a pattern g is the minimum of the degree of v, for all v ∈ V(g) (Yan et al., 2005a).

A canonical spanning tree of a graph is defined as the lexicographically maximal spanning tree of the graph (Huan et al., 2004).

A cut between two nodes in the lattice is defined as an ordered pair (p, c), where node p represents the parent of node c and p is infrequent while c is frequent (Thomas et al., 2006).

Let V(g) denote the set of vertexes in a graph g, a subset s ⊆V(g) is a clique if the subgraph induced on s is a complete graph.

A γ-quasi-clique(0 ⩽ γ ⩽ 1) is a k subgraph (k ⩾ 1), g, where ∀v ∈ V(g), $$\[--><$> degree{\rm{(}}v{\rm{)}}\,{\geqslant}\,{\lceil}\gamma {\rm{(}}k\,{\rm{ - }}\,{\rm{1)}}{\rceil} <$><!--$$ (Zeng et al., 2006).