In recent years, the problem of mining association rules over frequent itemsets in transactional data has been frequently studied and yielded several algorithms that can find association rules within a limited amount of time. Also more complex patterns have been considered such as ordered trees, unordered trees, or labeled graphs. Although some approaches can efficiently derive all frequent subgraphs from a massive dataset of graphs, a subgraph or subtree that is mathematically defined is not necessarily a better knowledge representation. In this paper, we propose an efficient approach to discover significant rules to classify positive and negative graph examples by estimating a tight upper bound on the statistical metric. This approach abandons unimportant rules earlier in the computations, and thereby accelerates the overall performance. The performance has been evaluated using real world datasets, and the efficiency and effect of our approach has been confirmed with respect to the amount of data and the computation time.