Graph Neural Networks (GNNs) have shown excellent performance in graph-related tasks. Despite significant advancements in GNN technology, these models are often perceived as opaque ‘black boxes’ that lack intuitive and human-understandable interpretations. To address this challenge, various explainability techniques have been developed to enhance the interpretability of GNNs, thereby facilitating more transparent decision-making processes and generating more interpretable outputs. Although recent advancements have enabled the interpretation of subgraphs with performance on par with the original graphs—marking a significant step towards demystifying the ‘black box’ of GNNs existing research often overlooks the associated time costs of this process. This oversight is a critical factor in the practical application of these models. In this paper, we propose a novel explanatory framework for GNNs, aimed at reducing time overhead by introducing an auxiliary dataset combined with an optimized Ullmann algorithm. Our framework applies to a wide range of explanation methods for graph classification. Experimental results demonstrate that our framework not only maintains performance comparable to traditional methods but also significantly reduces time overhead relative to existing solutions.