# Can Subgraph Explanations Be Weaponized to Steal Graph Neural Networks?

arXiv: https://arxiv.org/abs/2605.30470 · HTML: https://mlsanity.com/paper/2605.30470/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 44 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Model Reconstruction from Model Explanations](https://mlsanity.com/paper/1807.05185/) (2018)
- [I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defences](https://mlsanity.com/paper/2206.08451/) (2022)
- [Model Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2112.08331/) (2021)
- [MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable AI](https://mlsanity.com/paper/2107.08909/) (2021)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [A Survey on Model Extraction Attacks and Defenses for Large Language Models](https://mlsanity.com/paper/2506.22521/) (2025)
- [CEGA: A Cost-Effective Approach for Graph-Based Model Extraction and Acquisition](https://mlsanity.com/paper/2506.17709/) (2025)
- [AUTOLYCUS: Exploiting Explainable AI (XAI) for Model Extraction Attacks against Interpretable Models](https://mlsanity.com/paper/2302.02162/) (2023)
- [ATOM: A Framework of Detecting Query-Based Model Extraction Attacks for Graph Neural Networks](https://mlsanity.com/paper/2503.16693/) (2025)
- [Boundary Point Jailbreaking of Black-Box LLMs](https://mlsanity.com/paper/2602.15001/) (2026)
- [CREDIT: Certified Ownership Verification of Deep Neural Networks Against Model Extraction Attacks](https://mlsanity.com/paper/2602.20419/) (2026)
- [Efficient Model-Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2405.12295/) (2024)
- [Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defenses](https://mlsanity.com/paper/2508.19641/) (2025)
- [Efficient Model Extraction via Boundary Sampling](https://mlsanity.com/paper/2410.15429/) (2024)

## Abstract (arXiv)

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://github.com/LabRAI/XSTEAL/.