ML Security PapersOn Stealing Graph Neural Network Models
Marcin Podhajski 1,2, Jan Dubiński 3,4, Franziska Boenisch 5, Adam Dziedzic 5, Agnieszka Pręgowska 1, Tomasz P. Michalak 6,7
3 Warsaw University of Technology
4 NASK National Research Institute
Published on arXiv
2511.07170
Model Theft
OWASP ML Top 10 — ML05
Key Finding
Achieves 91% accuracy stealing a SAGE model on the Physics dataset with only 100 queries, roughly 15x fewer than the prior state-of-the-art method requiring similar accuracy.
Current graph neural network (GNN) model-stealing methods rely heavily on queries to the victim model, assuming no hard query limits. However, in reality, the number of allowed queries can be severely limited. In this paper, we demonstrate how an adversary can extract a GNN with very limited interactions with the model. Our approach first enables the adversary to obtain the model backbone without making direct queries to the victim model and then to strategically utilize a fixed query limit to extract the most informative data. The experiments on eight real-world datasets demonstrate the effectiveness of the attack, even under a very restricted query limit and under defense against model extraction in place. Our findings underscore the need for robust defenses against GNN model extraction threats.
Key Contributions
- Demonstrates that GNN backbone (encoder) can be recovered locally without any direct queries to the victim model
- Proposes strategic query selection using extracted encoder representations to maximally exploit a fixed query budget for head extraction
- Achieves 91% accuracy on Physics/SAGE with only 100 queries vs ~5,000 queries and 15x higher cost for prior SOTA
🛡️ Threat Analysis
The paper's primary contribution is a two-stage model extraction attack that clones GNN functionality — first recovering the encoder backbone locally without querying the victim, then using selective queries to extract the model head. This is a direct model theft attack achieving high fidelity with drastically fewer queries than prior art.