Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks

Explainable Graph Neural Networks (XGNNs) have garnered increasing attention for enhancing the transparency of Graph Neural Networks (GNNs), which are the leading methods for learning from graph-structured data. While existing XGNNs primarily focus on improving explanation quality, their robustness under adversarial attacks remains largely unexplored. Recent studies have shown that even minor perturbations to graph structure can significantly alter the explanation outcomes of XGNNs, posing serious risks in safety-critical applications such as drug discovery. In this paper, we take the first step toward addressing this challenge by introducing XGNNCert, the first provably robust XGNN. XGNNCert offers formal guarantees that the explanation results will remain consistent, even under worst-case graph perturbation attacks, as long as the number of altered edges is within a bounded limit. Importantly, this robustness is achieved without compromising the original GNN's predictive performance. Evaluation results on multiple graph datasets and GNN explainers show the effectiveness of XGNNCert. Source code is available at https://github.com/JetRichardLee/XGNNCert .