Top-k Closed Sequential Graph Pattern Mining

Published Online July 2016 in MECS

Frequent graph patterns are substructures that appear in a graph data set to a frequency not less than a user-specified threshold [9]. Structural forms such as subtrees, subgraphs, sublattices are referred as substructures. A frequent structural pattern is a substructure that appears frequently in a graph database. Sequential pattern mining, the mining of frequently occurring sub-sequences as patterns, was introduced in [13] and has become an important problem in data mining. Sequential pattern mining discovers frequent subsequences as patterns. According to the GSP algorithm [14], sequential pattern mining is to find all sequences whose support is greater than the user-specified minimum support, such sequence is called a frequent sequence. In SPADE [8], the set of all frequent sequences is discovered by reducing database scans and it minimizes I/O costs. The GSP and SPADE follow candidate generation and test approach.

The PrefixSpan algorithm [5] is a pattern-growth approach to sequential pattern mining and it follows divide-and-conquer strategy. BIDE [6] is an algorithm used for mining frequent closed sequences without candidate generation. These algorithms [5,6] grow patterns by constructing projected databases to reduce the search space for a pattern. In this paper, we investigated the problem of mining sequential patterns in graph databases. Our approach finds sequential patterns occurring in graph databases.

Fig.1. Three graphs where each vertex represents a web page

In “Fig. 1” each node represents a web page. Let us consider that the edges of the given graphs represent the order of visiting the web pages. For example, Graph1 represents the sequence q,s,t. Similarly Graph2 represents the sequence q,r,t and Graph3 represents the sequence q,p,t. Observing the three given graphs, it is clear that page t is accessed after page q(not immediately after q). The resulting pattern is which is not a subgraph. Given the above three graphs as input, any existing subgraph mining algorithm will not generate as a pattern. Many graph mining algorithms exist to find the frequent subgraphs, maximal frequent subgraphs, closed frequent subgraphs, and constraint-based closed frequent subgraphs. The sequence is not considered as an output pattern by the existing graph mining algorithms. Though is not a subgraph, it represents a pattern showing a sequence q followed by t. In this paper, we proposed an algorithm to find sequential patterns from graph databases known as Sequential Graph-Pattern Mining.

We proposed SFG( S equential F requent G raph pattern mining) algorithm to mine frequent sequences in a graph database. As the number of edges in a graph increases, the number of sequential patterns also increases exponentially. This requires further analysis of frequent sequential graph patterns. To overcome this difficulty, we proposed TCSFG( T op-k C losed S equential F requent G raph pattern mining) algorithm to generate top-k closed sequential graph patterns.

The rest of the paper is organized as follows. Section ii describes the related work in subgraph mining. Section iii present problem definition and section iv describe SFG, TCSFG algorithms. Our experimental results and performance analysis are presented in section v and our work is concluded in section vi.

• II.    Related Work

Many algorithms exist in the literature for mining frequent graph patterns [1,7,9,16,18]. AGM [1] algorithm efficiently mines frequently appearing induced subgraphs from a graph data database. Experimental results in [1] show that AGM finds all frequent induced subgraphs containing 300 chemical compounds in 40 minutes to 8 days, as the minimum support threshold varied from 20% to 10%. FSG[9] algorithm uses a sparse graph representation which minimizes both storage and computation. The performance of FSG was worse where the number of vertex and edge labels was small. AGM [1] and FSG [9] are Apriori-based algorithms for mining frequent substructures from graph data. Apriori-based algorithms generate subgraph candidates from frequent subgraphs and prunes false positives. These algorithms [1,9] suffer from the problem of subgraph isomorphism test and candidate generation. Candidate generation and pruning false positives are costly.

The gSpan [18] was the first algorithm to discover all the frequent subgraphs without candidate generation and it prunes false positives. gSpan discovers frequent substructures without candidate generation. A new lexicographic ordering among graphs was built in [18] and it maps each with a unique minimum DFS code as its canonical label. gSpan finds both frequent subgraphs and frequent induced subgraphs. It [18] uses rightmost extension technique to minimize the generation of the same subgraphs and explores the depth-first search in frequent subgraph mining.

Frequent subgraph mining is a challenging issue due to the generation of an exponential number of frequent subgraphs. Closed graph pattern mining was introduced in [16] to mine only closed frequent graph patterns. A graph g is closed if there do not exist any proper super graph of g with the same support as g. CloseGraph [16] mines closed frequent graph patterns using the concepts of equivalent occurrence and early termination to prune the pattern search space. It [16] reduces unnecessary subgraphs and also increases the efficiency of the mining process in the presence of large graph patterns. TSP [12], TFP [4] and CloSpan [17] are the recent work for closed sequential pattern mining. CloSpan is the first algorithm to solve closed sequential pattern mining problem. It [17] mines frequent closed sequential patterns and produces significantly less number of discovered sequences. The CloSpan mines long frequent sequences with low minimum support and without any information loss.

Mining top-k frequent closed patterns without minimum support was introduced in [4]. Top-down and bottom-up combined Fp-tree mining strategy was developed in [4] to raise the support and to discover closed frequent patterns. TSP algorithm mines top-k frequent closed sequential patterns of length no less than min_len, the minimum length of each pattern. It [12] doesn’t require the minimum support threshold, it makes use of the length constraint and outperforms the closed sequential pattern mining algorithm that make use of minimum support threshold.

Several algorithms were proposed previously ranging from mining graph patterns with constraints [2,11,19] and without constraints [6,18] for mining closed graph patterns [16]. Frequent graph-pattern mining may result in a large number of patterns. To make the mining more effective, constraints are often used to confine the pattern search. In gPrune algorithm[2] the frequent graph patterns are generated based on the constraints such as density and diameter. The Density of a graph is defined as the ratio of the edge set to vertex set. The diameter of a graph is the maximum length of the shortest path over all pairs of vertices. The problem of incorporating structural constraints in mining frequent graph patterns was solved in gPrune.

Finding closed frequent graphs with connectivity constraints in relational graphs was introduced in [19]. Two approaches, namely CLOSECUT and SPLAT were proposed to speed up the mining process. The former was pattern growth approach and it has better performance on patterns with high support and low connectivity, later approach was pattern reduction approach and it achieves better performance for the high connectivity constraints. These [19] algorithms mines closed frequent graphs with connectivity constraints in relational graphs. DS-search algorithm [11] mines frequent subgraphs of limited diameter and symmetry. It [11] employs the tree decomposition structure of database graphs during the mining process and generates more structurally interesting patterns in the database.

Recently two sequential techniques[3,10] were developed to solve the problem of graph-coloring. Graphcoloring concept [10 ] was used in processor allocation to represent the busy processor and the busy processors are mapped in the graph using different colors. The authors in [3] investigated the problem of Star coloring and they used DNA sequence to construct a solution space for the star coloring problem

Two algorithms RP-FP and RP-GD were proposed in

• [7] . These algorithms mine a representative set that summarizes frequent subgraphs. In these algorithms [7] a representative set RS is mined such that any frequent subgraph is covered by a representative in RS, and the value of |RS| is minimized. RP-FP and RP-GD algorithms have been proposed to summarize graph patterns efficiently using the concept of δ-cover and generates δ-jump patterns for a user specified δ. Even though there exist many subgraph mining algorithms, the problem of sequential pattern mining of graphs has not been investigated in the literature.

In this paper, we proposed a new algorithm SFG to mine sequential patterns from a graph database using pattern growth approach. We also extended our algorithm to mine top-k closed sequential patterns. We demonstrate that generating top-k closed frequent sequences reduce the number of output graphs without losing much information.

• III.    Problem Definition

In this section, we define sequential graph pattern and frequent sequential graph pattern mining problem.

A Labeled directed Multigraph can be represented as a tuple, G= (V,E,L,F) where V denotes a set of vertices, E denotes a set of edges, L denotes a set of labels and F is a labeling function that assigns labels to the vertices and edges. Every edge is a 4 tuple , where s is the source vertex, d is destination vertex, Gid is Graph id and lb is an edge label. A sample Graph data set is shown in “Fig. 2”.

Fig.2. A sample graph data set

Definition 1 (Graph Sequence)

An ordered collection of edges in a graph is called a graph sequence. Every edge is assigned a time constant (time of the creation of the relationship between the vertices) as a label. A Graph Sequence can be represented as,

GS=<(v a ,v b ),(v b ,v c ),….(v l ,v m ),(v m ,v n )> where v a , v n are the source and destination of the Graph sequence and each (v_i,v j ) represents an edge from v_i to v j . Compact representation of Graph sequence is given as

GS=a,vb,vc,….vn>.

Definition 2 (Length of the Graph Sequence).

Given a Graph Sequence GS =a,vb,vc,….vn> Where each vi represents a vertex. Length of the Graph sequence is the number of edges in the sequence.

Definition 3 (Support of Graph sequence)

Support of Graph Sequence GS is the total number of graphs containing the sequence GS as a subsequence.

Fig.3. A sample graph

Graph sequence for the graph in “Fig. 3” is

<(p-q),(q-r),(r-p),(p-s)> where t1,t2,t3,t4 are edge labels such that t 1 2 3 4. Its compact representation is . Length of the sequence is 4.

Definition 4 (Projected database of a sequence S)

Let S be a sequential pattern in a Graph database GD. The S projected database is the collection of subgraph sequences in GD with S as the first occurring sequence.

Definition 5 (Projected database of a vertex)

Given a Graph Database GD = {G 1 , G 2 ,… Gn}, The projected database of a vertex V is the set of subgraphs in which the sequence of the subgraph starts with V.

PDv = { SGi / i ɛ 1,2,..n and v is the starting vertex in each SGi}.For example, in the given graph database, the sequence that starts with vertex p as the source forms projected database of p. In “Fig. 2” edge 1 of Graph 1, edge 3 of Graph 2, edge 2 of Graph 3, edge 1 of Graph 4 and edge 2 of Graph 5 forms the sequence starting with p. Instead of storing the projected database separately for every vertex, considering the space constraints, we store only the pairs. Hence p-projected database is <(1,1),(2,3),(3,2),(4,1), (5,2)>

Definition 6 ( Support of a vertex)

Support of a vertex V is the number of sequences that start with V. A graph may contain multiple subsequences starting with V, but the count is only 1 for every graph.

Definition 7 (Canonical form)

Given a multigraph G i with n vertices, m edges and a graph sequence GS 1,v_2,…..v_n>, Canonical form of G_i is denoted as (v 1 ,v 2 ,i,1),(v 2 ,v 3 ,i,2),….(v n-1 ,v n ,i,m)

Definition 8 (Sequential Graph Pattern)

Given a graph sequence, a Sequential Graph Pattern is all possible subsequences.

For the Graph given in “Fig. 3” Graph Sequence is

, the possible sequential graph patterns are

,,,,,,,< pqrs>,,,,,,,,,,,,,

Definition 9 (Frequent Sequential Graph Pattern Mining)

Given a Graph database and minimum support, Frequent Sequential Graph-Pattern Mining is to find all the frequent sequences from the graph database.

Table 1. Canonical representation of Graph database

Graph-Id	Graph Sequence (Ordered Edges)	Canonical form
1	p→q, q→r,r→p,p→q,q→s,s→r	(p,q,1,1),(q,r,1,2),(r,p,1,3), (p,q,1,4),(q,s,1,5),(s,r,1,6)
2	q→r, r→p, p→q, q→s,s→r	(q,r,2,1),(r,p,2,2),(p,q,2,3), (q,s,2,4),(s,r,2,5)
3	r→p, p→s	(r,p,3,1),(p,s,3,2)
4	p→q, q→r, r→t, t→q, q→r	(p,q,4,1),(q,r,4,2),(r,t,4,3), (t,q,4,4),(q,r,4,5)
5	r→p, p→s, s→r, r→t, t→r, r→t	(r,p,5,1),(p,s,5,2),(s,r,5,3), (r,t,5,4),(t,r,5,5), (r,t,5,6)
6	q→s, s→t	(q,s,6,1),(s,t,6,2)

Table 2. Projected database of vertices

Vertex v	Projected Database	Support (v)	Nodes visited from v	Frequent Sequential Length-1 patterns
P	{(1,1),(2,3),(3,2) ,(4,1),(5,2)}	5	<7>7>
			<6 p:2="">6>
			<4 q:3="">4>
			<4>4>
			<2>2>

•    

•    

•    

’’

•    

•    

•    ɛ

•    

•    

•      ɛ

•        

• ←

•       

•      

•    

•    ʹ

←ʹ

•     

ʹ

•     ʹ

•    ʹʹ

•    ←ʹʹ

•     ʹ’

ʹ

ʹʹ……

ʹ

•    ←Φ

•    

•       

•     ←ᴜ

•    

•    

•    

•    <7 q:5="" s:4="" t:3=""><7>7>7>

•    <5><5><4><4><2>2>4>4>5>5>

•              

<7> 7>

•    

•    

•  

•  

•    

•    

•    

<3 q:2="" s:1=""> <3> <2>2> 3> 3>

“”

р

•    

•    

•    

•    

 

•    

•    

•    ʹ

←ʹ

•      

ʹ

•     ʹ

•       ʹʹ

ʹʹ

ʹʹ ʹ

←ʹ

•      ʹ’

ʹʹʹ

•    <7><6><5><4><4><4><4><3><3><3><3><3><2><2>2>2>3>3>3>3>3>4>4>4>4>5>6>7>

•    <7><3><2><2><2>2>2>2>3>7>

•    <6>6> <3> <2> <2> <2>2> 2> 2> 3>

<2> <2> <2> <2> <3> <7>“”7> 3> 2> 2> 2> 2>

“”

•    

“”

“”“”

“”“”

•