Graph Neural Networks (GNNs) have shown remarkable results in graph-related tasks, yet interpreting their decision-making process remains challenging. Most existing methods for interpreting GNNs focus on finding a subgraph that preserves the model’s predictions. However, removing edges alters the original structure, making the optimization process heavily dependent on the loss function. In this paper, we propose FleX, a novel approach that transcends these limitations by using a distillation model to estimate prediction values after subgraph extraction. Our method combines implicit and explicit edge masking techniques to identify the most relevant subgraph. We introduce a flexible loss estimation strategy that allows for a more robust optimization process. Experimental results demonstrate that FleX outperforms most existing Graph XAI models across various benchmark datasets, achieving superior performance in interpreting GNNs. This approach enhances the interpretability of GNNs while maintaining high accuracy, contributing to more trustworthy and explainable graph-based machine learning models.