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. Recently, 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 and novel 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.