Research map / Adversarial robustness and security / Attacks on text and graphs

Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks

ICLR 2025 · Adversarial robustness and security › Attacks on text and graphs · approach: Graph neural network robustness · 0 citations (OpenAlex)

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.

Proposes XGNNCert, a deterministic certified defense for graph-level explainable GNNs that uses hash-based hybrid subgraphs (graph plus complete-graph edges) with majority voting for classification and explanation, certifying explanation consistency under bounded edge perturbations.

Problem

Explainable GNNs (XGNNs) can have their edge explanations drastically altered by small graph structure perturbations, and existing defenses are empirical and breakable; certified robustness for explainers was unexplored.

Approach

Divide each graph via hash mapping into T subgraphs, combine each with complete-graph subgraphs to form hybrid subgraphs so that any M edge perturbations corrupt at most M hybrid subgraphs; then majority-vote the classifier predictions and explanation edge votes to derive a deterministic certified perturbation size.

Key results

• On SG+House with PGExplainer, XGNNCert guarantees at least 2 of 5 (sic, paper states k=5) groundtruth explanatory edges when on average 6.2 edges are arbitrarily perturbed.
• Under the adversarial XGNN attack of two non-explanatory edges, XGNNCert's fraction of different explanatory edges is 0.0% to 7.44% versus 48.39% to 83.82% for V-InfoR across datasets.
• XGNNCert's clean explanation accuracy is close to base explainers, e.g., 0.740 on SG+House versus 0.744 for GSAT original (per Table of explanation accuracy).

Measured effects reported in the paper

Surprising findings

• Certified perturbation size is zero when p=0, i.e., without complete-graph hybrid edges no provable defense is possible.
• Explanation accuracy without attack does not monotonically follow p; p=0 yields extremely poor explanation accuracy (about 0.05).

Limitations

• Node permutation variant voting classifier, so performance depends on node ordering (though empirically stable).
• Certified bound M* is not proven tight and is only guaranteed as a lower bound (M* <= M*_lambda).
• Extra computation and memory cost scale with T and |V|^2; only graph-level classification is covered, with node/edge-level extension left to future work.

Experimental setup

Datasets: SG-Motif (SG+House, SG+Diamond, SG+Wheel) Benzene Fluoride-Carbonyl (FC)

Benchmarks: SG+House SG+Diamond SG+Wheel Benzene FC

Metrics: classification accuracy explanation accuracy certified perturbation size M* at certified explanation accu fraction of different explanatory edges under attack

Baselines: V-InfoR PGExplainer ReFine GSAT

Builds on: PGExplainer ReFine GSAT randomized ablation majority-vote certified defenses

Closest papers by meaning

• Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations (CVPR 2025 · similarity 0.88)
• Graph Neural Network Explanations are Fragile (ICML 2024 · similarity 0.88)
• A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.88)
• Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.87)
• Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.87)
• Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs (ICLR 2025 · similarity 0.86)