A graph mining technique called Chunkingless Graph-Based Induction (Cl-GBI) can extract discriminative subgraphs from graph structured data by the operation called chunkingless pairwise expansion which constructs pseudo-nodes from selected pairs of nodes in the data. Because of the time and space complexities, it happens that Cl-GBI cannot extract good enough to describe characteristics of data. Thus, to improve its efficiency, we propose a pruning method based on the upper-bound of information gain. Information gain is used as a criterion of discriminativity in Cl-GBI and the upper-bound of information gain of a subgraph is the maximal one that its super graph can achieve. The proposed method allows Cl-GBI to exclude from its search space unfruitful subgraphs that cannot yield the most discriminative one, by comparing the upper-bound of information gain of each subgraph at hand with the best information gain at the moment. Furthermore, in this paper, we experimentally show the usefulness of the proposed pruning method by applying CI-GBI adopting it to both a real world dataset and an artificial datasets.