- 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
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
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:
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.