Robust Surrogate Modeling for Explainable Graph Neural Networks
Organizations: Knight Foundation School of Computing and Information Sciences, Florida International University, Miami, USA · Department of Computer Science, University of Houston, Houston, USA
Abstract
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
| 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 |
| BA-2motifs | MUTAG | Fluoride-Car. | D&D | Graph-SST2 | ||
| 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 | |
| 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 |
| 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 |
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 |
| 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 |
| 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 |
| 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% |
GNN Explainability
Graph neural network explainability studies how to identify and communicate the features, nodes, edges, and subgraphs behind graph-model predictions.
See all 88 papers