Mining generalized substructures from a set of labeled graphs

The problem of mining frequent itemsets in transactional data has been studied frequently and has yielded several algorithms that can find the itemsets within a limited amount of time. Some of them can derive "generalized" frequent itemsets consisting of items at any level of a taxonomy (Srikant and Agrawal, 1995). Several approaches have been proposed to mine frequent substructures (patterns) from a set of labeled graphs. The graph mining approaches are easily extended to mine generalized patterns where some vertices and/or edges have labels at any level of a taxonomy of the labels by extending the definition of "subgraph". However, the extended method outputs a massive set of the patterns most of which are over-generalized, which causes computation explosion. In this paper, an efficient method is proposed to discover all frequent patterns which are not over-generalized from labeled graphs, when taxonomies on vertex and edge labels are available.