On Stealing Graph Neural Network Models

AI summary

Overview

Research area: Security and privacy of graph neural networks (GNNs) — specifically model extraction, also called model stealing.

Technical level: Intermediate. The paper assumes familiarity with GNN architectures (GCN, GIN, SAGE, GAT), self-supervised learning, and black-box threat models, but the attack pipeline itself is described conceptually and is easy to follow.

Scope: The paper demonstrates that a GNN can be stolen under a strict query budget by acquiring the encoder locally without querying the victim and then spending a fixed query allowance on strategically selected nodes, evaluated on eight real-world datasets in both inductive and transductive settings.

What This Paper Is About

Existing GNN model-stealing methods assume the adversary can query the victim model essentially without limit, and they focus on improving accuracy as the budget grows. In practice, victim APIs can cap the number of allowed queries severely. This paper shows how an adversary can still extract a GNN under such a cap: first by obtaining the encoder backbone without contacting the victim at all, then by using the fixed query limit on the most informative nodes.

Key Contributions

1. The authors identify a threat previously overlooked in the literature: the ability to steal a GNN model even under a significant limit on access to the victim model.
2. They show that an adversary with access to query data but no direct model access can locally obtain a high-quality encoder at low computational cost.
3. They show that an adversary with restricted access to the victim can strategically select queries to train the model head, producing a stolen model with improved accuracy and fidelity.
4. They report that their approach is the only one in their comparison table covering both transductive and inductive settings while assuming limited data and limited victim queries, and using only the victim's final class predictions as output.

Main Findings

• Strict-query stealing is practical: Targeting a SAGE model trained on the Physics dataset, the authors report 91% accuracy with only 100 queries to the victim model — compared to approximately 5,000 queries, roughly 15× higher computational cost, and additional victim output (such as embeddings) needed by the current state-of-the-art method to reach similar accuracy.
• A randomly initialized encoder is a strong substitute in the inductive setting: In Table 3 (target SAGE, surrogate GCN, query limit 100, mean ± std. dev. over 3 runs), the "R-init + Select" variant reaches 82.5 ± 1.2 accuracy / 82.7 ± 1.2 fidelity on Reddit, 78.4 ± 2.1 / 79.2 ± 2.2 on CS, 91.2 ± 0.4 / 92.7 ± 0.5 on Physics, 86.8 ± 1.0 / 89.8 ± 0.9 on Photo, and 65.5 ± 1.8 / 73.6 ± 1.9 on WikiCS, against target accuracies of 94.8, 93.9, 96.0, 93.0, and 72.5 respectively.
• It beats prior inductive methods that assume a weaker threat model: Shen et al. (2022) and Podhajski et al. (2024), which both require access to victim embeddings (marked with * in the table), reach at most 79.9 and 90.6 accuracy on these datasets respectively, while Zhuang et al. (2024) — which assumes unlimited victim access — ranges from 13.6 to 55.5 accuracy.
• Self-supervised learning helps in the transductive setting: On Cora with a GCN surrogate and a query limit of 10, "SSL + Select" reaches 69.9 ± 1.2 / 72.5 ± 1.3, compared with 56.1 ± 2.7 / 56.8 ± 3.0 for "SSL + Random" and 47.5 ± 3.7 / 45.7 ± 1.0 for the E2E baseline of Wu et al. (2021); the target accuracy is 83.3.
• Query selection consistently helps: K-means–based selection from encoder embeddings improved accuracy and fidelity over random query selection in both settings, across all datasets and target models tested.
• Query selection beats alternatives: Comparing against farthest-first, K-center greedy, entropy sampling, coreset herding, and margin sampling (Table 10 in the appendix), the authors report K-means delivers the highest accuracy and fidelity across all datasets, though coreset herding also improves over random selection.
• Better class coverage at small budgets: Averaged over 100 runs on the CS dataset (Figure 8 in the appendix), the selection method covers a greater number of classes than random sampling under small budgets, with both converging to full class coverage as the query limit grows.
• The attack survives a hard-label defense: Under a defense that flips predictions with probability p = 10%, evaluated in both inductive and transductive settings (appendix Tables 12 and 13), the proposed method consistently achieves the highest performance.
• Statistical similarity to the victim: McNemar's test (appendix Tables 7 and 8) is used to compare classification errors of the stolen and original models; the authors report that their method produces a stolen model with a higher degree of similarity to the victim model.

Methodology in Plain English

The attack is split into three stages.

1. Get the encoder without querying the victim. In the inductive setting, the adversary simply uses a randomly initialized GCN encoder and freezes it. This is motivated by prior self-supervised learning results, summarized in Table 2, showing that a random encoder plus a trained MLP head performs close to an SSL-trained encoder — for example, 93.3 vs. 94.0 on Reddit and 62.6 vs. 63.8 on PPI (DGI), and 86.5 vs. 90.3 on Computer, 92.0 vs. 93.1 on Photo, 91.6 vs. 93.3 on CS, 93.7 vs. 95.7 on Physics, 78.9 vs. 79.9 on WikiCS (BGRL). In the transductive setting, the random encoder performs worse (69.3 vs. 82.3 on Cora, 61.9 vs. 71.8 on Citeseer, 69.6 vs. 76.8 on Pubmed), so the adversary trains an encoder locally with self-supervised learning; the authors use LaGraph, and note the method is compatible with any SSL framework producing useful representations. Transductive graphs are typically small, keeping this local training cheap.

2. Choose which nodes to query. The adversary runs K-means on the encoder's node embeddings, with the number of clusters set equal to the query limit. From each cluster the node whose embedding is closest to the centroid is selected, forming the query set. The idea is to cover the embedding space and maximize the information obtained per query.

3. Train the head. An MLP head is trained with cross-entropy loss on the selected nodes' embeddings and the class labels returned by the victim API. The final surrogate is the encoder plus this head — the only victim outputs used are hard class labels.

Experimental scope. Eight real-world datasets. Inductive: Physics, CS, Photo, Reddit, WikiCS (split 40% train / 10% validation / 50% test; Reddit uses the PyTorch Geometric public split). Transductive: Cora, Citeseer, Pubmed (public split protocol of Yang et al. 2016). Inductive targets: a 5-layer SAGE with hidden size 512, ReLU, dropout 0.5; and a 5-layer GAT with hidden size 128, 4 heads, ReLU, dropout 0.5 (embedding size 512). Inductive surrogate: a 5-layer GCN with hidden size 512, batch normalization, and PReLU. Transductive targets include a 2-layer GCN with hidden size 256, dropout 0.5, and ReLU; GAT is also mentioned as a target architecture, though the full description of the second transductive target model is cut off in the supplied text. Transductive surrogates are GIN, SAGE, and GCN. Query limits tested: 10, 25, 50, 100, and 500 nodes in the inductive setting, and 5, 10, 20, or 50 nodes in the transductive setting. For comparison, the authors note Zhuang et al. (2024) uses 100 queries for graphs of size 250, totaling 25,000 query nodes.

Why This Matters

Impact on research. Prior GNN stealing work (Zhuang et al., Wu et al., Podhajski et al., Shen et al.) assumes unlimited victim queries; this paper shows the threat is more severe and more resource-efficient than previously understood, and that limiting queries is not by itself an adequate defense. The authors argue this underscores the need for robust defenses against GNN model extraction.

Real-world applications — the paper frames GNNs as widely deployed for graph-structured data. Application contexts implied by the paper's scope include:

• Node classification services exposed behind public APIs.
• Recommendation systems built on graph-structured interaction data.
• Link prediction systems.
• Graph and subgraph classification services.

The paper's stated threat model requires only a publicly accessible API returning class labels, which is the most common real-world API output the authors consider.

Industry relevance. Model extraction violates intellectual property in the victim model, and a high-fidelity stolen model can serve as a tool for subsequent attacks such as crafting adversarial examples without querying the original model. Because the attack needs no access to victim parameters, architecture, or the training graph, and because the inductive variant uses a frozen randomly initialized encoder requiring only an MLP layer to be trained, the barriers to mounting this attack are low.

Future Directions

• Developing defenses that remain effective in the hard-label, limited-query setting; the authors observe that the flip-prediction defense costs model accuracy, and that defending is difficult even under such mechanisms.
• Extending the evaluation beyond node-level tasks, since the paper explicitly restricts itself to node-level query responses.
• Testing compatibility with other self-supervised learning frameworks — the authors state their approach is compatible with any SSL framework producing meaningful representations but only evaluate with LaGraph.
• Investigating whether other encoder or query-selection strategies further improve extraction, building on the comparison of K-means against farthest-first, K-center greedy, entropy sampling, coreset herding, and margin sampling.

Target Audience

Researchers and practitioners in machine learning security and privacy, particularly those working on model extraction and intellectual property protection for graph neural networks. It is also relevant to engineers deploying GNNs behind public inference APIs, and to readers already familiar with GNN architectures and self-supervised learning who want to understand how query limits affect the practical severity of model-stealing attacks.

Authors’ abstract

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.