Robust Surrogate Modeling for Explainable Graph Neural Networks
Authors: Zhuomin Chen, Jingchao Ni, Hojat Allah Salehi, Xu Zheng, Dongsheng Luo
Organizations: Knight Foundation School of Computing and Information Sciences, Florida International University, Miami, USA · Department of Computer Science, University of Houston, Houston, USA
Graph Neural Networks (GNNs) have achieved remarkable performance in a wide range of graph-related learning tasks. However, explaining their predictions remains a challenging problem, especially due to the mismatch between the graphs used during training and those encountered during explanation. Most existing methods optimize soft edge masks on weighted graphs to highlight important substructures, but these graphs differ from the unweighted graphs on which GNNs are trained. This distributional shift leads to unreliable gradients and degraded explanation quality, especially when generating small, sparse subgraphs. To address this issue, we propose explaining a robust surrogate whose explanations provide a faithful proxy for those of the original model. Specifically, we train this surrogate model through an iterative re-weighting strategy that alternates between identifying explanation subgraphs and adapting the model to the resulting weighted graph distribution, supporting stable explanation refinement while preserving the validity of the soft-mask relaxation. We evaluate our method on multiple benchmark datasets using different GNN backbones and explanation methods. Experimental results show that our method consistently improves explanation quality and can be flexibly integrated with different architectures.
Figures & tables
Figure 1: (a) Classification accuracy of a GCN trained on unweighted graphs, evaluated on weighted graphs from the BA-2motif dataset with varying edge weights for motif and BA-graph edges. High accuracy is maintained only in the “in-distribution” region (both edge types near weight 1.0), but degrades significantly under distributional shift. (b) The original unweighted graph (example ①) is correctly classified, but reweighting motif edges to 0.9 and BA-graph edges to 0.3 (example ②) causes misclassification.
Figure 2: Overview of the vanilla explainer and STORE. (a) Vanilla explainer. (b) STORE first inputs the original graph into a GNN to obtain node and edge embeddings. Then we use an explainer to generate a weighted explanation subgraph. Based on this explanation, we apply a Gaussian-based sampling strategy to assign edge weights and construct a weighted graph. This graph is used to retrain a surrogate GNN to improve explanation accuracy.
Explainer Method
BA-2motifs
MUTAG
Benzene
Alkane-Car.
Fluoride-Car.
GNNExplainer
0.515 ±0.107
0.707 ±0.086
0.604 ±0.029
0.650 ±0.042
0.640 ±0.018
+ STORE
0.528 ±0.108
0.720 ±0.057
0.595 ±0.026
0.686 ±0.026
0.647 ±0.019
PGExplainer
0.672 ±0.326
0.533 ±0.272
0.541 ±0.204
0.778 ±0.237
0.784 ±0.031
+ STORE
0.758 ±0.232
0.774 ±0.189
0.662 ±0.152
0.801 ±0.227
0.802 ±0.020
Refine
0.522 ±0.078
0.502 ±0.193
0.723 ±0.166
0.623 ±0.268
0.633 ±0.051
+ STORE
0.546 ±0.095
0.529 ±0.197
0.747 ±0.178
0.752 ±0.153
0.648 ±0.043
Table 1: Performance comparison of different explanation methods using GCN as the backbone
BA-2motifs
MUTAG
Fluoride-Car.
D&D
Graph-SST2
Fidα1,+↑
PGExplainer
0.038 ±0.029
0.042 ±0.008
0.055 ±0.012
0.010 ±0.011
0.008 ±0.002
+ STORE
0.074 ±0.023
0.060 ±0.002
0.064 ±0.010
0.022 ±0.008
0.011 ±0.001
Fidα2,−↓
PGExplainer
0.037 ±0.023
0.063 ±0.044
0.018 ±0.007
0.003 ±0.005
0.005 ±0.002
+ STORE
0.035 ±0.022
0.041 ±0.022
0.016 ±0.008
0.001 ±0.004
0.003 ±0.002
Table 2: Fidelity evaluation
Figure 3: AUC-ROC performance with different numbers of iterations.
Figure 4: Average training time. GCN and Explainer jointly represent the standard pipeline.
BA-2motifs
MUTAG
Fluoride-Car.
Random
0.631 ±0.282
0.513 ±0.264
0.763 ±0.035
Uniform
0.678 ±0.241
0.757 ±0.154
0.795 ±0.022
Gaussian
0.758 ±0.232
0.774 ±0.189
0.802 ±0.020
Table 3: Performance comparison with different sampling methods
Figure 5: AUC-ROC performance with different Δμ for PGExplainer.
Figure 6: Heat maps of classification accuracy under different edge weights.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Domain
#Graphs
Avg.#nodes
Avg.#edges
#Feature
BA-2motifs
Synthetic
1,000
25
51
10
MUTAG
Biochemical molecules
4,337
30.32
30.77
14
Benzene
Biochemical molecules
12,000
20.58
43.65
14
Alkane-Car.
Biochemical molecules
4,326
21.13
44.95
14
Fluoride-Car.
Biochemical molecules
8,671
21.36
45.37
14
D&D
Bioinformatics
1,178
284.32
715.66
89
Appendix
Table 4: Statistics of datasets used for graph classification task
Explainer Method
BA-2motifs
MUTAG
Benzene
Alkane-Car.
Fluoride-Car.
GNNExplainer
0.511 ±0.005
0.553 ±0.127
0.469 ±0.079
0.502 ±0.126
0.501 ±0.029
+ STORE
0.544 ±0.053
0.589 ±0.114
0.514 ±0.018
0.552 ±0.071
0.513 ±0.005
PGExplainer
0.756 ±0.315
0.489 ±0.246
0.617 ±0.260
0.495 ±0.259
0.678 ±0.088
+ STORE
0.791 ±0.176
0.657 ±0.209
0.797 ±0.108
0.631 ±0.258
0.730 ±0.118
Refine
0.518 ±0.066
0.535 ±0.225
0.499 ±0.127
0.603 ±0.190
0.551 ±0.074
+ STORE
0.584 ±0.066
0.537 ±0.150
0.638 ±0.158
0.650 ±0.117
0.597 ±0.054
Appendix
Table 5: Performance comparison of different explanation methods using GIN as the backbone.
BA-2motifs
MUTAG
Fluoride-Carbonyl
Train Acc
Original
0.923 ±0.061
0.787 ±0.026
0.764 ±0.036
Surrogate
0.915 ±0.057
0.802 ±0.010
0.757 ±0.038
Val Acc
Original
0.942 ±0.050
0.785 ±0.025
0.773 ±0.044
Surrogate
0.933 ±0.062
0.791 ±0.011
0.766 ±0.033
Test Acc
Original
0.934 ±0.049
0.771 ±0.026
0.750 ±0.053
Surrogate
0.926 ±0.062
0.786 ±0.014
0.752 ±0.040
Appendix
Table 6: Graph classification performance of the original GCN model and the final robust surrogate GCN model.
Metric
BA-2motifs
MUTAG
Fluoride-Carbonyl
Indep. baseline
87.0%
65.5%
62.6%
Pred. agreement
93.5%
80.3%
82.8%
Correct-set IoU
92.6%
78.1%
79.5%
Exp. overlap
89.7%
76.8%
84.4%
Exp. IoU
81.9%
72.6%
76.3%
Appendix
Table 7: Prediction and explanation agreement between the original GCN and the final robust surrogate GCN.
Figure 7: The explanation visualization comparison between original and the robust surrogate GCNs
Figure 8: Sampled edge weight distributions for explanatory and non-explanatory edges.
Figure 9: Visual comparison of explanation results.
Graph Neural Networks (GNNs) have demonstrated remarkable performance across a range of applications involving graph-structured data, particularly in high-stakes domains. However, the opaque nature of their decision-making processes limits their trustworthiness and broader adoption. Existing post-hoc explanation methods aim to improve explainability by identifying subgraphs that influence GNN predictions and adopt mixup strategies to alleviate the out-of-distribution (OOD) issue caused by using subgraphs for prediction. Yet, these approaches typically rely on soft masks, which are inherently unable to fully eliminate label-irrelevant information, allowing redundant structures to leak into the mixup process and hindering the resolution of the OOD problem, thereby degrading explanation fidelity. In this work, we propose HPME, a Hard-Perturbation Mixup Explanation framework grounded in a generalized Graph Information Bottleneck, which leverages graph pooling to extract discrete explanatory subgraphs and to yield an information-capacity bound to thoroughly compress label-irrelevant components. Furthermore, we introduce a novel mixup strategy built upon structure-level replacement, generating in-distribution explanations to effectively mitigate the distribution shift. Extensive experiments on diverse tasks demonstrate that HPME achieves state-of-the-art performance in generating robust and interpretable explanations across both synthetic and real-world datasets.
Jialiang Yin, Zheng Zhao, Linsey Pang +3
Xi’an Jiaotong University · Xi’an, China · PayPal +2
Instance-level explanations aim to reveal the rationale behind a model's decisions for a specific graph. Previous methods explain graph neural networks (GNNs) by selecting important edges to induce subgraphs, where edge importance is assessed by perturbing each edge and observing changes in the model predictions. However, they often neglect the synergistic effects among edges, which are crucial for accurately characterizing edge importance. To address this issue, we propose SeeExplainer, a parameter-free explainer to interpret GNNs. Specifically, we first introduce a granular-ball graph refinement mechanism that decomposes a graph into several disjoint granular-balls with no fixed size, and utilize them as nodes to construct a structural graph. This process can better capture the synergistic effects among edges. Then, we perturb nodes and edges in the structural graph to generate explanatory subgraphs based on their respective contributions. Experiments on several graph classification datasets of different networks show that SeeExplainer outperforms state-of-the-art baselines.
Jiancu Chen, Shuyin Xia, Guan Wang +2
Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, China · School of Computer Science and Engineering, Chongqing Three Gorges University, Chongqing, China
Explainable Artificial Intelligence aims to make black-box models more trustworthy by presenting, in a human-understandable manner, the elements that lead to the model's output. This involves both (i) identifying components and connections with genuine causal influence on outputs and (ii) translating such structures into an interpretable representation. For the former, we introduce CIExplainer, a novel perturbation-based method grounded in causal inference for explaining Graph Neural Networks (GNNs). CIExplainer identifies the subgraph with the highest causal effects on GNN predictions using the Potential Outcome Framework. We evaluate and compare CIExplainer on various GNN architectures (GCN, GraphSAGE, GAT, GIN) and datasets. To bridge subgraph explanations with human interpretability, we further propose G2TeXplainer, a method that transforms causal subgraphs into natural language explanations that capture both feature-level and relational information.
Francisco Caldas, Sahil Satish Kumar, Ruben Belo +1
NOVA LINCS, NOVA School of Science and Technology, Lisbon, Portugal