Towards Robust Heterogeneous Graph Explanations under Structural Perturbations

Explaining the decision-making process of Graph Neural Networks (GNNs) is essential for improving their transparency and reliability. However, real-world graphs are often heterogeneous and subject to structural noise, posing severe challenges to the robustness of existing explanation methods. To address these issues, we propose RoHeX, a Robust Heterogeneous GNN Explainer that enhances explanation quality under noisy conditions. RoHeX begins with a theoretical analysis revealing how different heterogeneous GNN architectures amplify structural perturbations through message passing. Building on this insight, we design a denoising variational inference framework that filters noisy structures and learns robust latent graph representations. Furthermore, we incorporate relation-aware heterogeneous semantics into the explanation generation process, formulating explanation as an optimization problem under the graph information bottleneck principle. This formulation enables RoHeX to balance fidelity and compactness, producing explanations that are both semantically meaningful and structurally stable. Comprehensive experiments on multiple real-world heterogeneous graphs demonstrate that RoHeX consistently surpasses state-of-the-art baselines in explanation fidelity, robustness to structural perturbations, and explainability.