GTRACE: Mining Frequent Subsequences from Graph Sequences

Akihiro INOKUCHI  Takashi WASHIO 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E93-D  No.10  pp.2792-2804
Publication Date: 2010/10/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
frequent pattern mining,  graph sequence,  union graph, 

Full Text: PDF(646.3KB)

Summary: 
In recent years, the mining of a complete set of frequent subgraphs from labeled graph data has been studied extensively. However, to the best of our knowledge, no method has been proposed for finding frequent subsequences of graphs from a set of graph sequences. In this paper, we define a novel class of graph subsequences by introducing axiomatic rules for graph transformations, their admissibility constraints, and a union graph. Then we propose an efficient approach named "GTRACE" for enumerating frequent transformation subsequences (FTSs) of graphs from a given set of graph sequences. The fundamental performance of the proposed method is evaluated using artificial datasets, and its practicality is confirmed by experiments using real-world datasets.