Research map / Graph learning / GNN architectures
Graph Neural Network Explanations are Fragile
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that perturbation-based GNN explainers (GNNExplainer, PGExplainer, GSAT) can be drastically changed by a few structure perturbations that keep the GNN prediction correct and the graph statistically similar, via loss-based and deduction-based attacks.
Problem
GNN explainers may be fragile: an adversary with limited knowledge and a small budget can perturb graph structure so the GNN's prediction stays correct while the explanatory subgraph changes drastically.
Approach
Formulates an explanation-manipulation attack under a practical threat model (knows only explanation loss and explanatory edges, keeps explanatory edges, budgeted, power-law stealthy, prediction-preserving), relaxes the set-based objective to an l1 mask norm, and proposes a loss-based attack and a deduction-based attack that simulates the explainer's mask-learning dynamics via an integral approxim
Key results
- Deduction-based attack with a budget of 2 edges changes up to 64.80% of GNNExplainer's explanatory edges on Tree-Cycle (64.42%) and 64.80% on MUTAG, with PGExplainer changed by 47.93% on Tree-Cycle.
- Transferring perturbed graphs from perturbation-based explainers, the deduction-based attack changes up to 55.25% of explanatory edges for SA on Reddit-Binary and 53.50% on MUTAG.
- The attacks outperform Random and Kill-hot baselines across all three explainers and six datasets, while keeping GNN predictions correct in most intermediate graphs (failure fractions mostly under 10%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use deduction-based rather than loss-based attack | GNN explainers · Across BA House, BA Community, Tree Cycle, OGBN-Products, MUTAG, and Reddit-Binary | overlap ratio | Helped |
| Use loss-based or deduction-based graph perturbations rather than random or kill-hot perturbations | GNNExplainer, PGExplainer, and GSAT · Six evaluation datasets | overlap ratio | Helped |
| Use a larger perturbation budget (ablation) | Proposed attacks · Attack performance across datasets | overlap ratio | Helped |
| Use a smaller explanation size k (ablation) | Proposed attacks · MUTAG and Reddit-Binary | overlap ratio | Helped |
| Increase the number of deduction-attack samples N (ablation) | Deduction-based attack · Attack performance across datasets | overlap ratio: within 5% | Helped |
| Set γ and β to values neither too small nor too large (ablation) | Proposed attacks · Attack performance across datasets | overlap ratio | Helped |
| Replace the known explainer loss with a surrogate explanation loss (ablation) | Deduction-based attack · BA House, BA Community, Tree Cycle, OGBN-Products, MUTAG, and Reddit-Binary | overlap ratio | Hurt |
Surprising findings
- Loss-based and deduction-based attacks transfer to decomposition, gradient, surrogate, and generation-based explainers, with the deduction-based attack changing up to 55% of their explanation edges.
- A surrogate-loss black-box attack remains considerably stronger than random and kill-hot baselines, so only restricting explainer API access is not a sufficient defense.
Limitations
- Attacks are designed for perturbation-based explainers; attacks on other explainer types require redesigned objectives.
- Defenses tested (structure difference detection, API-only access) are ineffective; provably robust explainers remain open.
- Evaluation uses only 40-160 test cases per dataset and a limited set of attack budgets (2 to 10 edges).
Experimental setup
Datasets: BA-House BA-Community Tree-Cycle OGBN-Products MUTAG Reddit-Binary
Benchmarks: BA-House BA-Community Tree-Cycle OGBN-Products MUTAG Reddit-Binary
Metrics: explanation overlap ratio |E_S - E_S∩Ẽ_S|/|E_S| GNN prediction confidence change fraction of failed attacks
Baselines: Random attack Kill-hot attack GEAttack
Builds on: GNNExplainer PGExplainer GSAT
Closest papers by meaning
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.89)
- Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.89)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.88)
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.88)
- Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks (ICLR 2025 · similarity 0.88)
- Factorized Explainer for Graph Neural Networks (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.