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.

Citation

Y. Lu, P. Jiao, X. Guo, Z. Zou, Y. Wang, M. Gao , et al., "Towards Robust Heterogeneous Graph Explanations under Structural Perturbations," 2026, pp. 1262-1273.

Source

Proceedings of the ACM Web Conference 2026

Conference

ACM Web Conference 2026

Keywords

46 Information and Computing Sciences, 4603 Computer Vision and Multimedia Computation, 4611 Machine Learning

Source

ACM Web Conference 2026

Publisher

Association for Computing Machinery

DOI

10.1145/3774904.3792516

Additional links

https://dl.acm.org/doi/10.1145/3774904.3792516