acceptodds
Under review as a conference paper at ICLR 2027

Can Subgraph Explanations Be Weaponized to Steal Graph Neural Networks?

Abstract

Graph Machine Learning as a Service (GMLaaS) platforms increasingly implement explainability interfaces to meet regulatory transparency requirements. However, this transparency creates exploitable vulnerabilities for model extraction attacks. We present the first model extraction attack specifically designed for graph classification under strict black-box constraints where the attacker observes only discrete class labels and binary explanation masks (no probability scores, gradients, or confidence values). Our method (1) uses model explanation outputs to guide Monte Carlo edge sensitivity estimation toward decision boundaries, with Hoeffding concentration guarantees on estimation accuracy and (2) exploits explanation subgraphs to efficiently narrow the boundary search space. Extensive experiments on benchmark graph datasets across multiple domains demonstrate our method's superiority over comparable baselines. These findings demonstrate that such explainability interfaces create exploitable attack surfaces, informing both defensive mechanisms and policy frameworks for explainable AI mandates. The implementation code is provided in https://anonymous.4open.science/r/GNN-MEA-288B/.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Model Explainability, Model Stealing

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_VvXfOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes XSTEAL, a model extraction attack on GNN graph classifiers in a strict black-box setting, where the attacker only sees predicted labels and binary explanation masks. The key idea is to find boundary pairs, that is, two graphs that differ by a few edges but receive different predictions, and use them to train a surrogate model. To find such pairs, the method estimates the effect of each edge by random sampling and uses the explanation to limit which edges are tested. Experiments on eight datasets, three GNN architectures, and two explainers show higher fidelity than adapted baselines.

Critical strengths

1.New and realistic setting. The paper studies stealing GNN graph classifiers using only predicted labels and binary explanation masks, a setting not covered by prior attacks and close to what providers may offer under transparency rules.

2.Reliable training data. Every boundary pair is confirmed by querying the victim, so even if the explanation is wrong, it only slows down the search without producing wrong labels.

3.Addresses a hard search problem. Finding boundary pairs on graphs is difficult because graphs are discrete and the attacker only sees labels, and the paper tackles this by estimating edge effects through random trials and using explanations to limit the search space.

Critical weaknesses

1.The role of explanations is not convincingly shown. The paper claims that explanations can be weaponized, but in Table 12, explanations improve fidelity over random edge selection on PTC_FM and Tox21 while barely changing it on NCI1, so their benefit is inconsistent.

2.Theory does not match the experiments. The theory requires more random samples than the five used in practice, as the authors admit, so it does not guarantee the reported results.

3.Missing a directly comparable baseline. Zhu et al. (2024), cited by the authors, also steals graph classifiers from predicted labels only and could run in this setting, but it is not compared, while the included baselines are weak.

4.Small-scale experiments. Several datasets use only tens of training graphs, such as 26 for MUTAG and 8 to 24 for Synthie, and very small test sets, so headline results like 100% fidelity on MUTAG may not be reliable.

5.The method is not always better. In some cases, Boundary is worse than simple random sampling, for example 71.4 versus 85.7 on PTC_FM with GAT in Table 9, and 77.6 versus 90.2 on NCI1 with GraphSAGE in Table 10.

Questions for authors

(1) How does XSTEAL compare with Zhu et al. (2024) under the same setting?

(2) Can you report the comparison between explanation guidance and random edge selection on all datasets with multiple seeds?

(3) Why does Boundary perform worse than random sampling in some GAT and GraphSAGE cases?

3 comments

We thank the reviewer for recognizing the realistic strict black-box setting, the reliability of victim-verified labels, and the difficulty of discrete graph boundary search. We appreciate the concerns on isolating explanation guidance, the finite-sample MC setting, stronger baselines, and small datasets.

W1/Q2: Isolating the role of explanations

We clarify that, the matched No-Exp control differs from Boundary only by sampling candidates uniformly rather than from the explanation subgraph; candidate count, training size, and query cost are matched. Guidance changes fidelity by +10.7 points on PTC_FM, +0.1 on NCI1, and +10.7 on Tox21_AhR. This is two substantial gains and one neutral case, not a harmful case.

NCI1 has the highest explanation-free Phase-1 deletion yield, leaving little work for Phase 2. PTC_FM/Tox21 yield fewer Phase-1 pairs, so explanation-guided Phase 2 contributes more and produces larger gains. Our multi-seed tests likewise show NCI1 convergence without meaningful Hybrid degradation. Thus, a neutral case where the component is rarely invoked does not negate its effectiveness on the two Phase-2-heavy datasets.

W2: Theory and the five-sample MC setting

The concentration result describes improvement with sample size, not a worst-case guarantee at n=5. Against an n=100 reference on 12 NCI1 graphs, n=5 obtains Spearman/top-3 overlap 0.505/0.417; n=20 improves to 0.734/0.528. Yet more samples search fewer graphs. At Q=50k over three seeds:

MC samples/edgeFull fidelityPhase-2 pairs found
194.94±0.5311.67±2.52
594.35±0.583.67±3.06
1094.98±0.102.33±2.52
2095.01±0.592.00±2.00

Larger n improves ranking but reduces coverage. Full fidelity stays within 94.35–95.01% because Phase 1 dominates NCI1. Thus n=5 is a practical operating point, not a claimed finite-sample optimum. Here n=1 still uses stochastic perturbation (p_flip=.05), unlike deterministic No-MC (p_flip=0), so the sweep isolates sample count from stochastic perturbation.

W3/Q1: Zhu et al. (2024)

We clarify that Zhu et al. is not directly comparable under our data-access model. MSA-AU/AD/AUD requires an initial set of real examples from the target model's training dataset. In contrast, XSTEAL assumes no target-training example is available. Instead, the attacker has only an independent public shadow set and hard-label plus binary-mask API access. Providing Zhu et al. its required seed data would give it privileged information outside our setting, while removing that data would no longer faithfully implement the published method. We instead add the compatible random-perturbation and edit-path controls described in our reply to Reviewer RUvk, please kindly check it.

W4: Small datasets and the MUTAG headline

We agree that a single 100% value should be interpreted together with its sample size. We therefore run five complete MUTAG seeds. The victim-balanced test sets contain 14–36 graphs. At 5k queries, Boundary, No-Exp, Hybrid, balanced Shadow, and balanced random perturbation obtain 86.27±10.38, 89.92±9.25, 91.51±3.24, 90.44±9.53, and 89.39±12.03%, respectively. Hybrid has the highest mean and lowest variance among these methods, although individual runs naturally vary on such small tests. We will report the uncertainty rather than presenting 100% as a general guarantee.

W5/Q3: Cases where Boundary is below random sampling

This phenomenon reflects a coverage–locality trade-off, not a contradiction of boundary informativeness. Boundary concentrates samples near selected victim decision surfaces, while random sampling covers the overall input distribution more broadly. When the surrogate architecture differs substantially from the victim, broad coverage can be more helpful than highly localized victim-boundary data.

Our three-seed mismatch test supports this interpretation. Hybrid is strongest with GCN and GAT surrogates (96.34% and 94.42%), while with GraphSAGE balanced random perturbation reaches 91.89% versus 91.02% for Hybrid. Hybrid therefore mitigates the trade-off by combining boundary and distributional coverage, even though no strategy is expected to dominate every architecture/dataset pair.

In all, the additional analyses reinforce the empirical claim more precisely: explanations provide substantial gains when explanation-guided Phase 2 is needed, remain neutral rather than harmful when Phase 1 already saturates the available boundaries, and interact predictably with query coverage and architecture mismatch. We sincerely thank the reviewer for helping us clarify these regimes, and we will add important points in our revised verision.

Area_Chair_6RXiOpenReview ↗

Engaging with the authors

Dear reviewer,

the authors have posted a reply to your review. Please have a look and interact with the authors as needed.

Thank you, Your AC

Dear Authors,

Thank you for the detailed response and additional experiments. W2 and W5 are addressed.

However, my main concern remains: the evidence that explanations drive the improvement is still limited to three datasets with a single seed, and the new MUTAG results show Boundary below No-Exp.

I appreciate the authors’ effort, but I continue to lean toward rejection.

Best regards,

Reviewer

Reviewer_RUvkOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates a model extration attack against GNNs on graph classification tasks. In the threat model, the GNNs are served through an API and returns only a hard label and a binary explanation mask. The explanation mask is obtained by using GNNExplainer or PGExplainer. It first argues that boundary pairs are particularly better training data for training a surrogate model. Then, it proposes XSTEAL, a two-phase method to find the boundary pairs: Phase 1 tests single-edge deletions on each shadow graph and Phase 2 runs on graphs where Phase 1 fails. The authors run experiments on 8 TUDataset benchmarks, 3 victim architectures and 2 explainers.

Critical strengths
  1. Well-motivated threat model. The paper asks and explores whether the minimal explanation signal, i.e., hard labels plus binary subgraph masks, is enough to extract a GNN model.

  2. Comprehensive experiments. The evaluation is broad including 8 graph datasets, 3 victim architectures, and 2 explainers.

Critical weaknesses

The central claim, i.e., boundary pair contributes to the training of surrogate model, is not isolated from other possible factors, and the observed gains may come from elsewhere.

  1. Class imbalance is confounded with boundary status. Boundary training sets are exactly class-balanced by construction, whereas Shadow, Non-boundary, and EGSteal-BB inherit the shadow set's class imbalance. Surrogate models are trained without reweighting but evaluated on a balanced test set. Shadow and Non-boundary achieve only 50.0% on Tox21 (Tables 3 and 10), suggesting majority-class collapse. Since label-stratified sampling or loss reweighting is feasible under the stated threat model, a class-balanced Shadow baseline is necessary.

  2. Methods are matched by training-set size, not query budget. Phase 2 requires 1+2ne∣C∣1 + 2n_e|C| queries per iteration. On Tox21, Table 12 reports ~609k victim queries to obtain ntrain=100n_{\text{train}}=100, whereas Shadow-Only requires only O(ntrain)O(n_{\text{train}}) queries. Query count, not training-set size, is the relevant attack cost. The evaluation should include a baseline that labels randomly perturbed shadow graphs under the same query budget.

The baselines are weak.

EGSteal-BB drops EGSteal's alignment loss on the grounds that it "requires continuous scores." But a binary mask can supervise surrogate saliency through a BCE or set-overlap loss. The remaining style augmentation generates interior, label-preserving samples by design. Appendix F.6 attributes EGSteal-BB's failure to label noise, yet Table 14 reports 93-100% label faithfulness (100% on PTC_FM, where the gap is largest). Several applicable hard-label baselines are absent:

  1. Zhu et al. Model stealing attack against graph classification with authenticity, uncertainty and diversity (2024);

  2. Mu et al. A hard label black-box adversarial attack against graph neural networks (2021), adapted to collect boundary pairs;

  3. the edit-path binary search implied by Lemma C.1. Walking the edit path between any two differently labelled shadow graphs finds a single-edge boundary pair, with no explanations needed.

Questions for authors
  1. What is the total number of victim queries (and explainer calls) for every method in Tables 1, 9 and 10? How does XSTEAL compare with a random-perturbation augmentation baseline at equal query count?

  2. Can the No-Exp control be extended to all datasets, both explainers and all three architectures, with multiple seeds? Without this, the marginal contribution of the explanation channel, which is the paper's title claim, is unclear.

  3. How does fidelity change when the surrogate architecture differs from the victim's? Does the advantage of Boundary over the baselines persist when the attacker does not know the victim's architecture?

  4. How about the robustness of XSTEAL against defences, e.g., explanation randomization/coarsening, near-duplicate query detection (ATOM), or OOD filtering?

  5. How about the performance of XTEAL on other graph tasks, e.g., node-classification tasks, link-prediction tasks?

3 comments

We thank the reviewer for recognizing our strict hard-label plus binary-mask setting and broad evaluation. We address the concerns with additional multi-seed controls.

W1/W2/Q1: Class balance and total queries

The original matched-training-size comparison isolates sample informativeness. For end-to-end cost, our ledger additionally counts every initial label, Phase-1 probe, MC probe, failed search, and verification call. We also balance every method and add balanced Shadow and random 1–3-edge perturbation controls.

NCI1 total queriesBoundaryNo-ExpHybridBal. ShadowBal. random perturb.
10k92.72±2.0593.70±1.8095.23±2.9694.22±2.0495.09±0.44
50k94.80±0.6794.84±0.7895.68±1.2194.18±2.0095.58±0.32
203,15095.31±0.4495.43±0.5095.22±0.9594.22±2.0491.36±5.92

At NCI1/50k, Boundary, No-Exp, Hybrid, balanced Shadow, and balanced random perturbation obtain 94.80, 94.84, 95.68, 94.18, and 95.58%. Hybrid remains the highest mean. At 10k, Hybrid is also highest (95.23%), supporting its limited-query effectiveness; at larger budgets, methods naturally converge as coverage saturates. On PTC_FM/24,184, Boundary exceeds No-Exp (84.19 vs. 78.49), while small balanced tests (18–26 graphs) cause high variance. Thus, both class balance and targeted information matter, and our accounting includes the full pipeline cost.

W3: Stronger compatible hard-label baselines

Thanks for bringing the work Zhu et al., however, it requires initial real examples from the target training dataset, whereas in XSTEAL we assume no target-training example is available. Providing that data grants privileged information outside our threat model; removing it no longer faithfully implements MSA-AU/AD/AUD.

We instead implement the suggested edit-path control using exactly our shadow-data/API access:

Edit-path variantQueriesTraining samplesFidelity
All elementary edits2,400±1756095.66±1.21
One-edge ending, within 20 edits of a real graph2,400±1734194.48±1.05

Unrestricted paths are efficient but traverse mixed node-label/structure states; the comparable local edge-only constraint lowers fidelity. XSTEAL instead searches locally around each queried graph. Mu et al. is an adversarial, not extraction, method; changing its objective/accounting would not be a faithful comparison, so we avoid presenting an approximate reproduction.

Q2: No-Exp across datasets, explainers, and architectures

The paper provides the broad dataset × explainer × victim-architecture study; our added three-seed total-query test covers representative GCN settings. On PTC_FM, where explanation-guided Phase 2 does more work, Boundary exceeds No-Exp by 5.70 points. On NCI1, high Phase-1 yield leaves little work for Phase 2, so they remain close. This explains when guidance is most useful.

Q3: Unknown surrogate architecture

Against GCN victims at Q=50k, Hybrid obtains 96.34, 94.42, and 91.02% with GCN, GAT, and GraphSAGE surrogates. The strongest controls obtain 94.81, 93.54, and 91.89%. Thus Hybrid leads for GCN/GAT and remains competitive for GraphSAGE, showing effectiveness without exact architecture knowledge; the final near-tie also reveals a coverage–locality trade-off under stronger mismatch.

Q4: Defensive randomization and filtering

Replacing 0/50/100% of mask nodes at equal query cost gives NCI1 fidelity 94.35/94.27/94.76% and PTC_FM 81.62/85.47/84.76%. Hence simple mask randomization does not reliably suppress extraction. Duplicate/OOD filters are threshold-dependent and also reject benign users; their proper evaluation must measure both attack suppression and clean-user rejection.

Q5: Node classification and link prediction

These are important future works, while in this paper we focus on graph classification, where each query is an independent graph. Node/link tasks are transductive, share topology across queries, and require new query units and theory. Therefore they are outside the present scope.

W4: EGSteal-BB adaptation

Our strict interface prevents EGSteal's continuous rank alignment. Binary BCE or set-overlap is a possible new adaptation, but is not its published objective. EGSteal-BB therefore retains the applicable style-invariance component. The balanced random and edit-path controls provide stronger native hard-label tests.

In all, binary explanations expose an exploitable signal, Hybrid remains effective under limited queries and architecture mismatch, and gains depend on coverage and Phase-2 usage. We thank the reviewer for these valuable questions, and will add necessary clarifications on these points in our revised version

Area_Chair_6RXiOpenReview ↗

Engaging with the authors

Dear reviewer,

the authors have posted a reply to your review. Please have a look and interact with the authors as needed.

Thank you, Your AC

Thank you for the clarifications and additional experiments. However, I find them reinforce rather than resolve my main concerns.

Specifically, on NCI1, Boundary is statistically indistinguishable from the other baselines, suggesting that the original gains largely rely on class balance. In the experiment to W3, the explanation-free edit-path control also achieves comparable fidelity with about 2.4k queries vs. 50k-203k for XSTEAL. Moreover, replacing all mask nodes with random nodes leaves fidelity unchanged on NCI1 and even increases it on PTC_FM, suggesting the attack does not rely on the explanation signal, which is however the paper's central claim.

Given these resutls, my main concerns remain, and I would retain my current score for now.

Reviewer_DjTtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies model extraction from graph classification services that return only discrete labels and binary explanation subgraphs. XSTEAL first searches for boundary pairs through single-edge deletion. When these are insufficient, it uses explanation subgraphs to select candidate edges and Monte Carlo estimates of edge sensitivity to search for graphs with changed predictions. The resulting boundary pairs are used to train a surrogate model. The paper analyzes estimation error and evaluates the method across eight datasets, three victim architectures, and two explainers, with additional ablation studies.

Critical strengths
  1. The paper demonstrates model extraction using discrete prediction labels and binary explanations, without access to prediction probabilities or victim gradients. Each boundary pair retained for training is verified against the victim’s predictions, preventing explanation errors from directly introducing incorrect training labels.
  2. The evaluation covers different victim architectures and explainers. Appendix F.4 also includes a query-matched comparison with a no-explanation control, providing initial evidence that explanation guidance contributes beyond the search budget alone.
Critical weaknesses
  1. The main experiments match training-set sizes without establishing equal total query costs. The limited query-matched evaluation leaves it unclear whether the reported gains hold under comparable query budgets.
  2. Victim configurations are selected by test accuracy, compromising the independence of the final evaluation. Selection on a separate validation set is needed to assess whether the reported conclusions remain stable.
Questions for authors
  1. How is the query budget enforced across the full pipeline, including initial labeling, Phase 1 search, Monte Carlo probes, and unsuccessful attempts? Please provide comparisons with Shadow-Only and No-Exp at matched total query counts in representative settings, with repeated runs to assess variability.
  2. Were the test examples used to select victim configurations also used for the final extraction evaluation? If so, please provide a representative comparison using validation-based model selection and an untouched test set, and clarify what the reported error bars capture.
3 comments

We sincerely thank the reviewer for recognizing our strict black-box setting, the reliability of victim-verified boundary pairs, and our initial matched-query No-Exp analysis. We also appreciate the questions on full query accounting and victim-model selection, which help us clarify the purpose and robustness of our evaluation.

Q1: Full query accounting and matched-query comparison

We first clarify that the original matched-training-size evaluation is intentional: by fixing the number of surrogate-training samples and all training hyperparameters, it directly measures the informativeness of different types of retained data. As the reviewer asks a complementary question on end-to-end efficiency when every victim prediction call is counted, we further evaluate with three complete seeds.

Our query ledger includes initial graph labeling, all Phase-1 deletion probes, all paired MC probes, unsuccessful Phase-2 attempts, and verification calls. We stop every method at identical total-query checkpoints and add balanced Shadow and random-perturbation controls:

NCI1 total queriesBoundaryNo-ExpHybridBal. ShadowBal. random perturb.
10k92.72±2.0593.70±1.8095.23±2.9694.22±2.0495.09±0.44
50k94.80±0.6794.84±0.7895.68±1.2194.18±2.0095.58±0.32
203,15095.31±0.4495.43±0.5095.22±0.9594.22±2.0491.36±5.92

The trajectory shows XSTEAL's practical strength most clearly in the limited-query regime: at 10k, Hybrid reaches the highest mean fidelity. At 50k, all strong methods begin to converge, while Hybrid remains the highest mean and does not lose performance. This reduced gap is expected: with sufficiently many victim-labeled graphs, untargeted sampling increasingly covers the relevant distribution, leaving less room for targeted selection to improve upon it.

Therefore, the two evaluations are consistent and answer different questions: matched training size measures information quality per retained sample, while matched total queries measures operational efficiency. We thank the reviewer for prompting this distinction and will make it explicit in our discussion.

Q2: Victim selection and untouched evaluation

In the original setup, we select a well-performing victim checkpoint to keep victim quality comparable across the broad dataset/architecture grid; the evaluation graphs are never available to the extraction attack or surrogate training. We agree that a separate validation set gives an even stricter independence check, so we additionally use a four-way split for each seed: 48% victim training, 12% validation, 20% attacker shadow data, and 20% untouched testing. Hyperparameters are selected only on validation, and the victim is then refit on the combined 60% victim portion.

The main NCI1 behavior remains stable under this alternative protocol, supporting that our conclusions are not an artifact of checkpoint choice. The main difference appears on very small datasets, as expected from split variance. For example, five MUTAG seeds have only 14–36 victim-balanced test graphs; at 5k queries, Hybrid achieves 91.51±3.24%, with some seeds still reaching 100%. We therefore report the split sizes and uncertainty rather than relying on a single headline value.All matched-query results reported in Q1 are obtained using these validation-selected victims and untouched test sets; we will also report the victim validation/test accuracy, split sizes, and extraction results under this protocol in the revised manuscript.

In all, the additional total-query and validation-selected tests further support the robustness of the main finding while clarifying the low-budget regime where XSTEAL is most useful. We thank the reviewer again for these constructive questions.

Area_Chair_6RXiOpenReview ↗

Engaging with the authors

Dear reviewer,

the authors have posted a reply to your review. Please have a look and interact with the authors as needed.

Thank you, Your AC

Thank you for the clarifications and additional experiments. The validation-based selection protocol alleviates my concern about test-set independence in the new experiments. However, excluding test graphs from attack and surrogate training does not address the original use of test accuracy for victim-model selection. Under matched query budgets, Hybrid performs similarly to balanced random perturbation on NCI1, while the reported gain on PTC_FM lacks uncertainty estimates. The evidence therefore remains insufficient to establish a consistent advantage, and I retain my current rating for now.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.