Can Subgraph Explanations Be Weaponized to Steal Graph Neural Networks?
cs.LG
Submitted: 2026-05-28
Updated: 2026-08-28
Comments: 28 pages, 8 figures, 10 tables. Under review at NeurIPS 2026
Code: https://github.com/LabRAI/XSTEAL
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: Graph Machine Learning as a Service (GMLaaS) platforms increasingly implement explainability interfaces to meet regulatory transparency requirements.
Terminology
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://github.com/LabRAI/XSTEAL/.
Sources
- Adversarial Attack on Graph Structured Data
- Boundary Point Jailbreaking of Black-Box LLMs
- Benchmarking Graph Neural Networks
- Inductive Representation Learning on Large Graphs
- Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
- Semi-Supervised Classification with Graph Convolutional Networks
- Artificial Intelligence Index Report 2025
- Practical Black-Box Attacks against Machine Learning
- Efficient Model-Stealing Attacks Against Inductive Graph Neural Networks
- Model Stealing Attacks Against Inductive Graph Neural Networks
- Graph Attention Networks
- Model Extraction Attacks on Graph Neural Networks: Taxonomy and Realization
- GNNExplainer: Generating Explanations for Graph Neural Networks
- On Explainability of Graph Neural Networks via Subgraph Explorations
- A Survey on Model Extraction Attacks and Defenses for Large Language Models
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks