Defending against Model Extraction for GNNs with Model Reprogramming

# Defending against Model Extraction for GNNs with Model Reprogramming
Source: [https://arxiv.org/html/2608.11495](https://arxiv.org/html/2608.11495)
## Defending against Model Extraction for GNNs with Model ReprogrammingConference:Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2; August 09–13, 2026; Jeju Island, Republic of KoreaProceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2 \(KDD ’26\), August 09–13, 2026, Jeju Island, Republic of KoreaDOI:[10\.1145/3770855\.3817983](https://doi.org/10.1145/3770855.3817983)ISBN:979\-8\-4007\-2259\-2/2026/08CCS:Security and privacy Software and application securityCCS:Computing methodologies Machine learning

Yan WenOrcID:[0009\-0002\-6425\-5056](https://orcid.org/0009-0002-6425-5056)Affiliation:University of Maryland, College Park,Department of Computer Science,College Park,MD,USAemail:[ywen1@umd\.edu](mailto:[email protected])Zhenyi WangOrcID:[0000\-0002\-2780\-9446](https://orcid.org/0000-0002-2780-9446)Affiliation:University of Central Florida,Department of Computer Science and Institute of Artificial Intelligence,Orlando,FL,USAemail:[zhenyi\.wang@ucf\.edu](mailto:[email protected])andHeng HuangOrcID:[0000\-0002\-3483\-8333](https://orcid.org/0000-0002-3483-8333)Affiliation:University of Maryland, College Park,Department of Computer Science,College Park,MD,USAemail:[heng@umd\.edu](mailto:[email protected])

2026; © cc

###### Abstract\.

Graph Neural Networks \(GNNs\) serve as the backbone for high\-stakes applications in Machine\-Learning\-as\-a\-Service \(MLaaS\)\. Still, their black\-box deployment exposes them to Model Extraction \(ME\) attacks, in which adversaries steal intellectual property by querying APIs\. Existing defenses suffer from a critical “Euclidean bias”: they transfer image\-based strategies \(e\.g\., random noise\) to graphs, ignoring the complex topological dependencies between nodes, which often results in severe utility degradation\. Passive methods like watermarking also fail to prevent theft in real time\. To bridge this gap, we proposeGraphRP\(GraphReprogrammingProtection\), a proactive defense framework that repurposesModel Reprogrammingfor security\. Unlike static perturbations, GraphRP introduces a Structure\-Aware Gating Mechanism driven by learnable topological prototypes\. This creates a dynamic “structural firewall” that selectively modulates the model’s decision boundary: it preserves fidelity for benign queries residing on the training manifold, while maximizing the Fisher Information along the perturbation direction for adversarial queries\. Under standard assumptions \(bounded loss, optimal attacker, and local second\-order approximation\), we prove a lower bound on the attacker’s estimation error that increases with the structural sensitivity of the reprogramming noise\. Extensive experiments on both hard\-label and soft\-label ME attacks demonstrate that GraphRP significantly degrades attack effectiveness while preserving benign utility\.

###### Keywords:

Model Extraction; Graph Neural Networks; Model Reprogramming; Adversarial Defense; Trustworthy AI

††cc\-license:by## 1\.Introduction

Graph Neural Networks \(GNNs\)\([21](https://arxiv.org/html/2608.11495#bib.bib1);[12](https://arxiv.org/html/2608.11495#bib.bib2);[39](https://arxiv.org/html/2608.11495#bib.bib3)\)have emerged as the de facto standard for modeling non\-Euclidean data, serving as the backbone for high\-stakes applications in recommendation systems\([46](https://arxiv.org/html/2608.11495#bib.bib4)\), financial fraud detection\([23](https://arxiv.org/html/2608.11495#bib.bib5)\), and social network analysis\([22](https://arxiv.org/html/2608.11495#bib.bib6)\)\. Given the high costs associated with data collection and model training, these proprietary models are increasingly deployed as cloud\-based API services, a paradigm known asMachine\-Learning\-as\-a\-Service\(MLaaS\)\([24](https://arxiv.org/html/2608.11495#bib.bib7);[25](https://arxiv.org/html/2608.11495#bib.bib8)\)\. However, this black\-box access exposes them toModel Extraction \(ME\) attacks, where an adversary systematically queries the API to train a surrogate model that replicates the victim’s functionality\([35](https://arxiv.org/html/2608.11495#bib.bib9);[45](https://arxiv.org/html/2608.11495#bib.bib10);[50](https://arxiv.org/html/2608.11495#bib.bib11)\)\. Unlike attacks on independent and identically distributed \(i\.i\.d\.\) image data, ME attacks on GNNs exploit the complex topological dependencies between nodes, allowing attackers to infer global graph properties from limited queries\. This renders GNNs uniquely vulnerable to intellectual property \(IP\) theft and subsequent adversarial exploitation\([7](https://arxiv.org/html/2608.11495#bib.bib12)\)\.

While prior work has made progress in defending against model extraction, existing solutions have critical limitations when applied to GNNs\. First,passive defenses, such as watermarking\([9](https://arxiv.org/html/2608.11495#bib.bib13);[15](https://arxiv.org/html/2608.11495#bib.bib14)\), focus on ownership verification rather than prevention\. These methods can only identify a stolen modelafterthe theft has occurred, by which time the intellectual property is already compromised\. Second,active defensestransferred from the image domain fail to account for the specific properties of graph data\. Most existing active methods attempt to confuse attackers by adding random noise or performing complex calculations during inference\([32](https://arxiv.org/html/2608.11495#bib.bib15);[20](https://arxiv.org/html/2608.11495#bib.bib16);[27](https://arxiv.org/html/2608.11495#bib.bib17);[43](https://arxiv.org/html/2608.11495#bib.bib18)\)\. However, these approaches face two major problems with graphs: \(1\)Utility Degradation: Unlike pixels in an image, nodes in a graph are connected\. Adding indiscriminate noise to a single node propagates errors to its neighbors during message passing, severely harming the model’s accuracy for benign users\. \(2\)High Latency: Many defense methods require expensive optimization steps for every query\. For real\-world web applications like recommendation systems, this extra delay is unacceptable\.

These challenges lead us to the central research question of this work:RQ:How can we design an active defense for GNNs that effectively prevents model extraction without hurting the accuracy for benign users, while keeping inference fast?

To address this, we proposeGraphRP\(GraphReprogrammingProtection\), a novel active defense mechanism based onModel Reprogramming\([3](https://arxiv.org/html/2608.11495#bib.bib19);[17](https://arxiv.org/html/2608.11495#bib.bib20)\)\. While reprogramming is traditionally used to adapt pre\-trained models to new tasks, we repurpose it for security\. Our key insight is to treat defense as a "conditional task": the model should behave normally for benign queries but essentially "malfunction" for adversarial ones\. Unlike random noise injection, GraphRP optimizes a set oflearnable, layer\-wise perturbationsthat act as a "structural firewall\." Crucially, we introduce aStructure\-Aware Gating Mechanismthat dynamically modulates these perturbations based on the topological signature of the input graph\. By learning "benign structural prototypes," our method ensures that defensive noise is only activated when the query distribution deviates from the benign distribution \(OOD\), thereby preserving utility for benign users\.

In summary, our main contributions are fourfold:

- •Framework:We propose GraphRP, the first defense framework that leverages model reprogramming to protect GNNs against model extraction, avoiding the need for full model retraining\.
- •Structure\-Awareness:We introduce a prototype\-based gating mechanism that exploits graph topological invariants \(e\.g\., spectral features\) to distinguish benign queries from extraction attacks, solving the utility\-defense trade\-off\.
- •Theoretical Guarantee:Under standard assumptions \(bounded loss, an optimal attacker, and a local second\-order approximation\), we show that our method maximizes a lower bound on the attacker’s estimation error by exploiting the Fisher Information of the target GNN\.
- •Empirical Effectiveness:Extensive experiments on diverse benchmarks demonstrate that GraphRP reduces clone model accuracy by up to17%17\\%compared to state\-of\-the\-art baselines while maintaining high utility and low inference latency\.

## 2\.Related Work

### 2\.1\.Model Extraction

Model Extraction \(ME\), also referred to asmodel stealing, denotes the adversarial process of replicating the functionality of a target model by extracting its parameters or approximating its decision boundary\([31](https://arxiv.org/html/2608.11495#bib.bib21);[33](https://arxiv.org/html/2608.11495#bib.bib22);[38](https://arxiv.org/html/2608.11495#bib.bib23);[30](https://arxiv.org/html/2608.11495#bib.bib24)\)\. Attackers may target exact parameters\([34](https://arxiv.org/html/2608.11495#bib.bib25)\), hyperparameters\([41](https://arxiv.org/html/2608.11495#bib.bib26)\), or neural architectures\([29](https://arxiv.org/html/2608.11495#bib.bib27)\); this work, however, focuses onbehavioral cloning—training a surrogate that mimics the target’s outputs without accessing its internals\([7](https://arxiv.org/html/2608.11495#bib.bib12)\)\.

ME attacks are conventionally categorized based on the data available to the adversary\.Data\-Based Model Extraction \(DBME\)\([18](https://arxiv.org/html/2608.11495#bib.bib28);[5](https://arxiv.org/html/2608.11495#bib.bib29);[33](https://arxiv.org/html/2608.11495#bib.bib22)\)assumes the attacker possesses a dataset distributionally similar to the victim’s training data\. By querying the target model with these inputs, the attacker collects labeled pairs to train the surrogate in a supervised manner\. Conversely,Data\-Free Model Extraction \(DFME\)\([18](https://arxiv.org/html/2608.11495#bib.bib28);[38](https://arxiv.org/html/2608.11495#bib.bib23)\)represents a more sophisticated threat where no real data is available\. In this scenario, the attacker must generate synthetic queries to simultaneously explore the high\-dimensional input space and learn the model’s behavior, often utilizing generative models to maximize query efficiency\.

The difficulty of extraction is further dictated by the granularity of the API’s output\. Insoft\-label attacks, the victim returns a full probability distribution \(logits\), providing rich information about the decision boundary\([13](https://arxiv.org/html/2608.11495#bib.bib30)\)\. In contrast,hard\-label attacksreturn only the top\-1 class prediction\. This setting significantly restricts the information gain per query, forcing attackers to rely on label\-only learning techniques that are typically less sample\-efficient and harder to optimize\.

Recent research has demonstrated that GNNs are uniquely vulnerable to these attacks due to the leakage of structural information\([7](https://arxiv.org/html/2608.11495#bib.bib12);[45](https://arxiv.org/html/2608.11495#bib.bib10);[35](https://arxiv.org/html/2608.11495#bib.bib9);[50](https://arxiv.org/html/2608.11495#bib.bib11)\)\. Unlike image models, GNN extraction reconstructs not only node labels but also the underlying graph topology\.[45](https://arxiv.org/html/2608.11495#bib.bib10)proposed using discrete graph structure learning to infer a substitute graph from node attributes, while[35](https://arxiv.org/html/2608.11495#bib.bib9)utilized k\-Nearest Neighbors \(kNN\) to initialize surrogate structures\. More recently,[50](https://arxiv.org/html/2608.11495#bib.bib11)proposed StealGNN, a data\-free extraction attack for GNNs that leverages a generative model to synthesize queries without access to any real graph data, demonstrating that structural information leaks even under strict black\-box constraints\. Furthermore, as the field moves toward large\-scale pre\-training,[47](https://arxiv.org/html/2608.11495#bib.bib31)have shown that even Graph Foundation Models are susceptible to extraction, emphasizing the urgent need for robust defense mechanisms in the graph domain\.

### 2\.2\.Model Extraction Defense

Existing defenses against model extraction can be broadly categorized into passive and active strategies, depending on whether they attempt to detect the attack or prevent it entirely\.

Passive Defensesfocus on monitoring and detecting extraction attempts without modifying the model’s inference behavior\([15](https://arxiv.org/html/2608.11495#bib.bib14);[37](https://arxiv.org/html/2608.11495#bib.bib32);[26](https://arxiv.org/html/2608.11495#bib.bib33)\)\. These methods typically analyze query patterns, distribution shifts, and timing to identify suspicious activities distinct from normal user behavior\. Standard techniques involve sophisticated logging and anomaly detection pipelines\. In the specific context of GNNs, recent approaches, such as those by[9](https://arxiv.org/html/2608.11495#bib.bib13), have proposed embedding watermarks directly into GNN explanations to verify ownership\. While they provide evidence for legal recourse after the fact, they fail to prevent intellectual property theft in the first place\.

Active Defenses, in contrast, aim to prevent model extraction \(ME\) attacks by proactively modifying the model’s responses or access mechanisms\([32](https://arxiv.org/html/2608.11495#bib.bib15);[20](https://arxiv.org/html/2608.11495#bib.bib16);[19](https://arxiv.org/html/2608.11495#bib.bib34);[27](https://arxiv.org/html/2608.11495#bib.bib17);[43](https://arxiv.org/html/2608.11495#bib.bib18)\)\. Primary strategies includePrediction Obfuscation\([32](https://arxiv.org/html/2608.11495#bib.bib15)\), which alters output logits to reduce the information gain per query, andPerturbation Techniques\([20](https://arxiv.org/html/2608.11495#bib.bib16);[19](https://arxiv.org/html/2608.11495#bib.bib34);[43](https://arxiv.org/html/2608.11495#bib.bib18)\), which introduce stochastic noise to degrade the fidelity of the extracted surrogate\. Other approaches, such asQuery Limitation\([27](https://arxiv.org/html/2608.11495#bib.bib17)\), restrict the rate of queries or dynamically adjust responses based on behavior analysis\([43](https://arxiv.org/html/2608.11495#bib.bib18);[50](https://arxiv.org/html/2608.11495#bib.bib11)\)\.

Despite these advancements, designing defenses for GNNs presents unique challenges that existing methods fail to address\. We term this failure mode theEuclidean bias\. Graph data is non\-Euclidean, containing complex dependencies between node features and topological structures\. Most existing active defenses are designed for independent and identically distributed \(i\.i\.d\.\) image data; when applied to graphs, they often disrupt the message\-passing mechanism, leading to severe utility degradation for benign users\. A recent work, ADAGE\([48](https://arxiv.org/html/2608.11495#bib.bib35)\), takes a step toward GNN\-specific active defense by monitoring the diversity of incoming queries across sessions and reactively blocking requests that exhibit extraction\-like patterns\. However, ADAGE operates in astatefulmanner, requiring persistent query\-log monitoring across multiple API calls, which introduces significant infrastructure overhead and makes it inapplicable in truly stateless black\-box deployments\. Furthermore, its reactive blocking strategy depends on accumulating sufficient query history before a defense is triggered, leaving an exploitable window for early\-stage attacks\. In contrast, GraphRP is entirelystateless: it requires no query logging or cross\-session state, and proactively poisons every OOD query at inference time based solely on the structural signature of the current input\. These fundamental architectural differences make direct experimental comparison between ADAGE and GraphRP infeasible, as they operate under incompatible deployment assumptions\.

Our work bridges this gap by proposing a novel defense pipeline that emphasizes graph\-structure sensitivity\. We introduce adaptive, layer\-wise perturbations that exploit the unique construction of graph\-based models\. Unlike prior works, we leverageModel Reprogrammingas an active defense mechanism\. To the best of our knowledge, this is the first study to explore Model Reprogramming specifically to defend against GNN model extraction, offering a proactive solution that reduces surrogate fidelity while preserving benign utility\.

### 2\.3\.Model Reprogramming

Model Reprogramming \(MR\)is a parameter\-efficient learning paradigm that repurposes pre\-trained machine learning models for target tasks in different domains without modifying the original model weights\([3](https://arxiv.org/html/2608.11495#bib.bib19)\)\. Initially introduced in the context of adversarial machine learning\([11](https://arxiv.org/html/2608.11495#bib.bib36)\), MR demonstrates that a fixed model can be "steered" to perform a new function simply by learning a transformation function \(or perturbation mask\) applied to the input data\. This approach has since evolved into a powerful tool for cross\-domain adaptation, offering a resource\-efficient alternative to traditional transfer learning, where full model fine\-tuning is computationally prohibitive\.

In the graph domain, MR has gained significant traction under the umbrella of "Graph Prompting" and "Deep Graph Reprogramming\."[17](https://arxiv.org/html/2608.11495#bib.bib20)proposedDeep Graph Reprogramming, which aligns pre\-trained GNNs with novel downstream tasks by optimizing a set of learnable structural perturbations\. Similarly,[36](https://arxiv.org/html/2608.11495#bib.bib37)demonstrated that reprogramming\-based prompting can unify multi\-task learning on graphs by modifying the input graph topology and features rather than the model architecture\.

Our work introduces a paradigm shift in the application of MR\. While prior works\([17](https://arxiv.org/html/2608.11495#bib.bib20);[36](https://arxiv.org/html/2608.11495#bib.bib37)\)introduce reprogramming to enhance model utility for new tasks, we leverage it as a defensive mechanism\. We reprogram the victim GNN to maintain utility for the original task \(benign users\) while simultaneously degrading utility for the specific task of "model extraction" \(adversaries\), effectively turning the model’s plasticity into a security feature\.

Distinction from Watermarking\.It is crucial to distinguish GraphRP from watermarking techniques\([15](https://arxiv.org/html/2608.11495#bib.bib14)\)\. Watermarking is apassive, post\-hocmechanism that embeds a signature into the model to verify ownershipaftertheft has occurred\. It does not prevent the attacker from using the stolen model\. In contrast, GraphRP is anactive, real\-timedefense\. It fundamentally degrades the quality of the extracted model, rendering the stolen copy useless\. While watermarking seeks legal recourse, GraphRP seeks to render the surrogate functionally obsolete\.

Benign Query\(x,y\)∼𝒟i​d\(x,y\)\\sim\\mathcal\{D\}\_\{id\}StandardGNNAttack Query\(x,y\)∼𝒟o​o​d\(x,y\)\\sim\\mathcal\{D\}\_\{ood\}StandardGNNHighConfidence\!Benign QueryStruct\.Check\(x,y\)∼𝒟i​d\(x,y\)\\sim\\mathcal\{D\}\_\{id\}α≈0\\alpha\{\\approx\}0ReprogramLayerNoise×0\\times 0Attack Query\(x,y\)∼𝒟o​o​d\(x,y\)\\sim\\mathcal\{D\}\_\{ood\}Struct\.Checkα≈1\\alpha\{\\approx\}1ReprogramLayerUniformDist\.Noise×1\\times 1
Figure 1\.Overview of the Proposed Defense Framework\.Comparison between a standard GNN pipeline and our approach\. While the standard GNN pipeline \(left\) leaks high\-confidence information for both benign and attack queries, GraphRP \(right\) dynamically modulates the output based on structural legitimacy\. The top row shows utility preservation for benign users \(orange bars\), while the bottom row demonstrates defense activation for OOD attackers \(grey/flat bars\)\.

## 3\.Preliminaries

### 3\.1\.Notations and Problem Setup

Graph Notation\.LetG=\(V,E\)G=\(V,E\)denote a graph, whereVVis the set ofnnnodes \(vertices\) andEEis the set of edges\. A graph sample can be represented as a tuplex=\(A,X\)x=\(A,X\), whereA∈\{0,1\}n×nA\\in\\\{0,1\\\}^\{n\\times n\}is the adjacency matrix representing the graph structure, andX∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}is the node feature matrix, withdddenoting the feature dimension\.

Data Distributions\.We consider a graph classification task where data is sampled from a ground\-truth distribution𝒟\\mathcal\{D\}\. A dataset is denoted asD=\{\(xi,yi\)\}i=1ND=\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{N\}, whereyi∈Yy\_\{i\}\\in Yis the label\. Crucially for Model Extraction \(ME\) defense, we distinguish between two data regimes:

- •In\-Distribution \(ID\):The private distribution𝒟i​d\\mathcal\{D\}\_\{id\}on which the victim model is trained and expected to perform well\. The defender possesses a private datasetDt​r​a​i​n∼𝒟i​dD\_\{train\}\\sim\\mathcal\{D\}\_\{id\}\.
- •Out\-of\-Distribution \(OOD\):The public or synthetic distribution𝒟o​o​d\\mathcal\{D\}\_\{ood\}used by the attacker to query the model\. This includes surrogate datasets \(in Data\-Based ME\) or synthetic graphs generated by a generator \(in Data\-Free ME\)\.

In our setting, we assume the query dataxqx\_\{q\}comes from𝒟o​o​d\\mathcal\{D\}\_\{ood\}, such that𝒟i​d∩𝒟o​o​d=∅\\mathcal\{D\}\_\{id\}\\cap\\mathcal\{D\}\_\{ood\}=\\emptysetin terms of exact samples, though they may share feature semantics\.

### 3\.2\.Model Framework

Victim Model \(Target\)\.The defender deploys a pre\-trained Graph Neural Network, denoted asT:𝒢→𝒴T:\\mathcal\{G\}\\to\\mathcal\{Y\}, parameterized byθT\\theta\_\{T\}\. This model maps an input graphx∈𝒢x\\in\\mathcal\{G\}to a probability distribution over classesYY\. We assumeTTis well\-trained on the private distribution𝒟i​d\\mathcal\{D\}\_\{id\}and serves as an oracle𝒪\\mathcal\{O\}accessible via an API\.

Surrogate Model \(Clone\)\.The attacker aims to train a surrogate modelC:𝒢→𝒴C:\\mathcal\{G\}\\to\\mathcal\{Y\}, parameterized byθC\\theta\_\{C\}\. The architecture ofCCis generally unknown to the defender and may differ significantly fromTT\. The attacker’s objective is to estimateθC\\theta\_\{C\}such thatC⁡\(x\)≈T⁡\(x\)C\(x\)\\approx T\(x\)for allxxin the domain of interest with similar functionality\.

Query Generator\.In the Data\-Free Model Extraction \(DFME\) setting, the attacker utilizes a generatorfg​e​n:𝒵→𝒢o​o​df\_\{gen\}:\\mathcal\{Z\}\\to\\mathcal\{G\}\_\{ood\}to synthesize query graphs\. Here,𝒵\\mathcal\{Z\}represents a latent space \(e\.g\., Gaussian noise\), andfg​e​nf\_\{gen\}constructs node features and adjacency matrices that are structurally valid but distributionally distinct from the private data𝒟i​d\\mathcal\{D\}\_\{id\}\.

### 3\.3\.Attacker’s Goal and Knowledge

Attacker’s Knowledge\.We assume a black\-box setting where the attacker has no access to the victim model’s parametersθT\\theta\_\{T\}, gradients, or the private training data𝒟i​d\\mathcal\{D\}\_\{id\}\. The attacker can only query the API with inputsxq∼𝒟o​o​dx\_\{q\}\\sim\\mathcal\{D\}\_\{ood\}and observe the outputyqy\_\{q\}, as illustrated in Figure[1](https://arxiv.org/html/2608.11495#S2.F1)\. In thesoft\-labelsetting,yqy\_\{q\}is a full probability vector; in thehard\-labelsetting,yqy\_\{q\}is the top\-1 predicted class\.

Optimization Objective\.The attacker aims to train a surrogate modelC⁡\(⋅,θC\)C\(\\cdot;\\theta\_\{C\}\)that mimics the behavior of the target modelTT\. Since the attacker lacks access to𝒟i​d\\mathcal\{D\}\_\{id\}, they minimize the divergence between the two models over the available query distribution𝒟o​o​d\\mathcal\{D\}\_\{ood\}\. Formally, the attacker minimizes the Kullback\-Leibler \(KL\) divergence:

\(1\)minθC𝔼x∼𝒟o​o​d\[DKL\(T\(x;θT\)∥C\(x;θC\)\)\],\\displaystyle\\min\_\{\\theta\_\{C\}\}\\ \\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\_\{ood\}\}\\left\[D\_\{\\text\{KL\}\}\\left\(T\(x;\\theta\_\{T\}\)\\parallel C\(x;\\theta\_\{C\}\)\\right\)\\right\],whereT⁡\(x,θT\)T\(x;\\theta\_\{T\}\)represents the soft labels returned by the victim \(or approximated from hard labels\)\. By minimizing this loss, the surrogate learns to replicate the decision boundary of the victim on the query set\.

Ultimate Goal\.While the optimization occurs on𝒟o​o​d\\mathcal\{D\}\_\{ood\}, the attacker’s ultimate goal is to obtain a model that generalizes well to the private task\. That is, the surrogateCCshould achieve high accuracy on the private test setDi​dt​e​s​tD\_\{id\}^\{test\}\.

### 3\.4\.Defender’s Goal and Knowledge

Defender’s Knowledge\.The defender has full white\-box access to the target modelTTand the private training setDi​dD\_\{id\}\. Crucially, we assume the defender knows that attack queries are likely to be out\-of\-distribution \(OOD\) relative to the private data\([44](https://arxiv.org/html/2608.11495#bib.bib38);[43](https://arxiv.org/html/2608.11495#bib.bib18)\)\. This assumption allows the defender to leverage an auxiliary OOD dataset𝒟o​o​dd​e​f\\mathcal\{D\}\_\{ood\}^\{def\}\(different from the attacker’s queries\) to calibrate the defense\.

Defense Objectives\.The defender has three competing objectives:

1. \(1\)Utility Preservation:The target model must maintain high accuracy for benign users \(ID queries\), therefore, \(2\)𝔼\(x,y\)∼𝒟i​d​\[𝕀⁡\(arg⁡max⁡T⁡\(x\)=y\)\]​is maximized\.\\displaystyle\\mathbb\{E\}\_\{\(x,y\)\\sim\\mathcal\{D\}\_\{id\}\}\\left\[\\mathbb\{I\}\(\\arg\\max T\(x\)=y\)\\right\]\\text\{ is maximized\.\}
2. \(2\)Extraction Prevention:The target model should provide uninformative outputs for attack queries \(OOD\) to prevent the surrogate from learning the true decision boundary\.
3. \(3\)Efficiency:The defense mechanism must be computationally lightweight, avoiding expensive test\-time optimization that would increase latency for real\-time services\.

Input GraphG=\(A,X\)G=\(A,X\)Structure ExtractorΦ⁡\(G\)\\Phi\(G\)Eig​\(𝐋\),deg​\(v\),clus​\(v\)\\text\{Eig\}\(\\mathbf\{L\}\),\\text\{deg\}\(v\),\\text\{clus\}\(v\)Prototype Matchingd=mink⁡‖𝐳−𝐜k‖2d=\\min\_\{k\}\\\|\\mathbf\{z\}\-\\mathbf\{c\}\_\{k\}\\\|^\{2\}𝐜k\\mathbf\{c\}\_\{k\}𝐳\\mathbf\{z\}α\\alphaSim\.GNN Layerll𝐇\(l\)=σ⁡\(A^​𝐇\(l−1\)​W\)\\mathbf\{H\}^\{\(l\)\}=\\sigma\(\\hat\{A\}\\mathbf\{H\}^\{\(l\-1\)\}W\)\+\+ReprogrammedOutput𝐇~\(l\)\\tilde\{\\mathbf\{H\}\}^\{\(l\)\}×\\timesLearnable Perturbation𝜹\(l\)∈ℝd\\bm\{\\delta\}^\{\(l\)\}\\in\\mathbb\{R\}^\{d\}Task Lossmin⁡ℒC​E\\min\\mathcal\{L\}\_\{CE\}Defense Lossmax⁡DK​L\\max D\_\{KL\}Module 1: Structure\-Aware GatingModule 2: Reprogramming BackboneFigure 2\.Architecture of the GraphRP Framework\.The system operates via two coupled pathways\. TheStructure Branch\(Top\) computes a gating factorα\\alphaby matching the input graph against learned benign prototypes\. TheReprogramming Branch\(Bottom\) performs standard message passing but injects an effective bounded perturbation𝜹~\(l\)\\tilde\{\\bm\{\\delta\}\}^\{\(l\)\}at each layer\. The injection is modulated byα\\alpha, effectively switching the defenseONforOOD queriesandOFFforbenign queries\.

## 4\.Methodology

We proposeGraphRP\(GraphReprogrammingProtection\), a proactive defense framework that leverages model reprogramming to secure GNNs against ME attacks\. The core intuition is to embed a dormant "security protocol" within the model’s layers that activates only when it detects suspicious, OOD query patterns characteristic of extraction attempts\.

### 4\.1\.Overview of Pipeline

The overall architecture of GraphRP is illustrated in Figure[2](https://arxiv.org/html/2608.11495#S3.F2)\. Standard GNNs \(left\) process all inputs identically, making them vulnerable to attackers who query the model with synthetic or OOD graphs to approximate the decision boundary\. In contrast, GraphRP \(right\) introduces two key components into the standard message\-passing backbone:

1. \(1\)Layer\-Wise Reprogramming \(Sec\.[4\.2](https://arxiv.org/html/2608.11495#S4.SS2)\):A mechanism to inject learnable, task\-specific perturbations into the latent node embeddings\. This allows us to manipulate the model’s output distribution without retraining the original weights\.
2. \(2\)Structure\-Aware Gating \(Sec\.[4\.3](https://arxiv.org/html/2608.11495#S4.SS3)\):A dynamic control module that assesses the structural legitimacy of an input graph\. It computes a gating factorα∈\[0,1\]\\alpha\\in\[0,1\]to modulate the reprogramming intensity\.

The pipeline operates in two modes:

- •Benign Mode \(α→0\\alpha\\to 0\):For inputs matching the training distribution \(ID\), the reprogramming noise is suppressed\. The model functions as a standard GNN, preserving high utility\.
- •Defense Mode \(α→1\\alpha\\to 1\):For suspicious inputs \(OOD\), the gating mechanism activates the reprogramming layers\. The model outputs are subtly distorted to maximize the divergence from the true decision boundary, effectively poisoning the attacker’s surrogate training data\.

### 4\.2\.Layer\-Wise Reprogramming

The first challenge is to alter the behavior of a GNN without degrading its original performance\. We adopt aModel Reprogrammingapproach\([3](https://arxiv.org/html/2608.11495#bib.bib19)\), treating the defense as a secondary task learned alongside the primary classification task\. Consider a standard GNN layerlldefined by the message passing operation:

\(3\)𝐇\(l\)=σ⁡\(𝐀^​𝐇\(l−1\)​𝐖\(l\)\),\\displaystyle\\mathbf\{H\}^\{\(l\)\}=\\sigma\\left\(\\hat\{\\mathbf\{A\}\}\\mathbf\{H\}^\{\(l\-1\)\}\\mathbf\{W\}^\{\(l\)\}\\right\),where𝐇\(l\)∈ℝn×dl\\mathbf\{H\}^\{\(l\)\}\\in\\mathbb\{R\}^\{n\\times d\_\{l\}\}are the node embeddings and𝐀^\\hat\{\\mathbf\{A\}\}is the normalized adjacency matrix\. A learnable perturbation𝐏\(l\)\\mathbf\{P\}^\{\(l\)\}is injected into the latent space for defensive flexibility\. However, applying a static noise matrix is insufficient as graph sizes vary\. Instead, we define aUniversal Reprogramming Prototype𝜹\(l\)∈ℝdl\\bm\{\\delta\}^\{\(l\)\}\\in\\mathbb\{R\}^\{d\_\{l\}\}for each layer, which is broadcasted to all nodes\.

The reprogrammed layer output𝐇~\(l\)\\tilde\{\\mathbf\{H\}\}^\{\(l\)\}is formulated as:

\(4\)𝐇~\(l\)=𝐇\(l\)\+λ⋅Tanh⁡\(𝜹\(l\)\)⏟Bounded Perturbation,\\displaystyle\\tilde\{\\mathbf\{H\}\}^\{\(l\)\}=\\mathbf\{H\}^\{\(l\)\}\+\\underbrace\{\\lambda\\cdot\\operatorname\{Tanh\}\(\\bm\{\\delta\}^\{\(l\)\}\)\}\_\{\\text\{Bounded Perturbation\}\},where𝜹\(l\)\\bm\{\\delta\}^\{\(l\)\}are the learnable parameters of the defense\. TheTanh⁡\(⋅\)\\operatorname\{Tanh\}\(\\cdot\)function ensures the perturbation remains bounded, preventing numerical instability\. Crucially,𝜹\(l\)\\bm\{\\delta\}^\{\(l\)\}captures thedirectionin the latent space that is most disruptive to an attacker’s learning process\. If we optimized𝜹\(l\)\\bm\{\\delta\}^\{\(l\)\}solely to maximize prediction error, it would destroy utility\. Thus, the magnitude of this perturbation must be controlled by the graph structure, which we detail next\.

### 4\.3\.Structure\-Aware Prototype Gating

A naive application of the perturbation in Eq\. \([4](https://arxiv.org/html/2608.11495#S4.E4)\) treats benign and malicious queries equally\. To distinguish them, we propose aStructure\-Aware Prototype Gatingmechanism\. Instead of relying on simple heuristics \(like average degree\), we learn a set of "Benign Structural Prototypes" in the embedding space\.

1\. Structural Projection\.We first map the input graphGGto a permutation\-invariant structural embedding𝐳G\\mathbf\{z\}\_\{G\}\. We utilize a lightweightReadoutfunctionΦ⁡\(⋅\)\\Phi\(\\cdot\)that aggregates node degrees, clustering coefficients, and spectral features \(top\-kkLaplacian eigenvalues\):

\(5\)𝐳G=Φ\(G\)=\[MLP\(∑v∈V\[deg\(v\)∥C\(v\)\]\);Eig\(𝐋\)\]\.\\displaystyle\\mathbf\{z\}\_\{G\}=\\Phi\(G\)=\\left\[\\text\{MLP\}\\left\(\\sum\_\{v\\in V\}\\left\[\\text\{deg\}\(v\)\\parallel C\(v\)\\right\]\\right\);\\text\{Eig\}\(\\mathbf\{L\}\)\\right\]\.Here,C⁡\(v\)C\(v\)denotes the local clustering coefficient of nodevv,∥\\parallelrepresents feature concatenation,\[⋅;⋅\]\[\\cdot\\,;\\,\\cdot\]denotes vector concatenation, andEig​\(𝐋\)\\text\{Eig\}\(\\mathbf\{L\}\)extracts the top\-kkeigenvalues of the normalized Laplacian\([4](https://arxiv.org/html/2608.11495#bib.bib39);[8](https://arxiv.org/html/2608.11495#bib.bib40)\)\. This projection captures the topological "signature" of the graph\.

2\. Benign Prototypes\.During training, we maintain a set ofKKcentroids\{𝐜k\}k=1K\\\{\\mathbf\{c\}\_\{k\}\\\}\_\{k=1\}^\{K\}initialized via K\-Means on𝒟i​d\\mathcal\{D\}\_\{id\}to represent the structural clusters of the private in\-distribution data\. The prototypes are refined in a dedicated structural update step \(independently ofΘr​e​p\\Theta\_\{rep\}\) and are explicitly excluded from the reprogramming gradient updates in Step 4 of Algorithm[1](https://arxiv.org/html/2608.11495#alg1)\.

3\. Gating Factor Calculation\.For a new queryGqG\_\{q\}, we calculate its distance to the nearest benign prototype\. The gating factorα⁡\(Gq\)\\alpha\(G\_\{q\}\)is derived using a soft\-thresholding function:

\(6\)dm​i​n\\displaystyle d\_\{min\}=mink⁡‖𝐳Gq−𝐜k‖22,\\displaystyle=\\min\_\{k\}\\\|\\mathbf\{z\}\_\{G\_\{q\}\}\-\\mathbf\{c\}\_\{k\}\\\|\_\{2\}^\{2\},\(7\)α⁡\(Gq\)\\displaystyle\\alpha\(G\_\{q\}\)=Sigmoid⁡\(γ⋅\(dm​i​n−τ\)\),\\displaystyle=\\operatorname\{Sigmoid\}\\left\(\\gamma\\cdot\(d\_\{min\}\-\\tau\)\\right\),whereτ\\tauis a learnable distance threshold andγ\\gammais a sharpness parameter\. Ifdm​i​n<τd\_\{min\}<\\tau\(structurally similar to private data\), thenα→0\\alpha\\to 0\. Ifdm​i​n\>τd\_\{min\}\>\\tau\(structurally anomalous/OOD\), thenα→1\\alpha\\to 1\.

Final Reprogramming Equation\.Combining Eq\. \([4](https://arxiv.org/html/2608.11495#S4.E4)\) and the gating factor, the final operation at layerllbecomes:

\(8\)𝐇~\(l\)=𝐇\(l\)\+α⁡\(G\)⋅λ⋅Tanh⁡\(𝜹\(l\)\)\.\\displaystyle\\tilde\{\\mathbf\{H\}\}^\{\(l\)\}=\\mathbf\{H\}^\{\(l\)\}\+\\alpha\(G\)\\cdot\\lambda\\cdot\\operatorname\{Tanh\}\(\\bm\{\\delta\}^\{\(l\)\}\)\.This ensures that the defensive noise is strictly conditional on the structural "foreignness" of the query, effectively creating a graph\-structure\-sensitive firewall\.

Robustness against Structural Spoofing\.A natural question may arise:Can an adaptive attacker forge graph queries to bypass this gating mechanism?Unlike adding Gaussian noise to images, generating synthetic graphs that match the complex topological signature \(e\.g\., Laplacian spectrum and clustering coefficients\) of a private distribution is a non\-trivial inverse problem\([49](https://arxiv.org/html/2608.11495#bib.bib41)\)\. Without access to the benign training set, the attacker cannot easily estimate the centroid prototypes𝐜k\\mathbf\{c\}\_\{k\}\. Thus, our spectral gating effectively acts as a “structural firewall,” forcing the attacker to query OOD samples that trigger the defense\.

### 4\.4\.Defensive Optimization and Algorithm

Having defined the structure\-aware reprogramming mechanism, we now formulate the defensive training as an optimization problem\. The defender’s goal is to learn the optimal reprogramming parametersΘr​e​p=\{𝜹\(l\),τ\}l\\Theta\_\{rep\}=\\\{\\bm\{\\delta\}^\{\(l\)\},\\tau\\\}\_\{l\}that selectively degrade the fidelity of the attacker’s surrogate model without compromising benign accuracy\. Note that the prototypes\{𝐜k\}\\\{\\mathbf\{c\}\_\{k\}\\\}are maintained separately and excluded fromΘr​e​p\\Theta\_\{rep\}\.

#### 4\.4\.1\.Loss Function Formulation

The total objective functionℒ\\mathcal\{L\}is a weighted combination of three terms: the utility preservation loss, the extraction defense loss, and a structural compactness loss\.

1\. Utility Preservation \(ℒtask\\mathcal\{L\}\_\{\\text\{task\}\}\)\.For in\-distribution \(ID\) data, the reprogramming layer should have minimal impact\. We minimize the standard Cross\-Entropy loss on the private training set𝒟i​d\\mathcal\{D\}\_\{id\}:

\(9\)ℒtask=𝔼\(x,y\)∼𝒟i​d​\[lCE​\(T⁡\(x,θT,Θr​e​p\),y\)\]\.\\displaystyle\\mathcal\{L\}\_\{\\text\{task\}\}=\\mathbb\{E\}\_\{\(x,y\)\\sim\\mathcal\{D\}\_\{id\}\}\\left\[l\_\{\\text\{CE\}\}\(T\(x;\\theta\_\{T\},\\Theta\_\{rep\}\),y\)\\right\]\.Since the gating factorα⁡\(x\)→0\\alpha\(x\)\\to 0for ID data, this term ensures the perturbations remain dormant for benign users\.

2\. Extraction Defense \(ℒdefense\\mathcal\{L\}\_\{\\text\{defense\}\}\)\.For out\-of\-distribution \(OOD\) queries—which act as a proxy for attack queries—we explicitly maximize the divergence between the reprogrammed model’s output and the original model’s output\. This "poisons" the information retrieved by the attacker\. We utilize the Kullback\-Leibler divergence:

\(10\)ℒdefense=𝔼x∼𝒟o​o​d\[max\(0,μ−DKL\(T\(x;θT\)∥T\(x;θT,Θr​e​p\)\)\)\]\.\\displaystyle\\mathcal\{L\}\_\{\\text\{defense\}\}=\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\_\{ood\}\}\\left\[\\max\(0,\\mu\-D\_\{\\text\{KL\}\}\(T\(x;\\theta\_\{T\}\)\\parallel T\(x;\\theta\_\{T\},\\Theta\_\{rep\}\)\)\)\\right\]\.Here, we employ a hinge loss formulation with marginμ\\mu\. This encourages the reprogrammed output to deviate from the original prediction by at least marginμ\\mu, effectively obfuscating the true decision boundary for OOD inputs\.

By minimizing this hinge loss, the optimization encourages a large KL divergence between the target and reprogrammed distributions, which serves a dual purpose\. Beyond simple output distortion, it implicitly maximizes theFisher Information \(FI\)distance along the direction of the perturbation𝜹\\bm\{\\delta\}\. As we will prove in Theorem[5\.1](https://arxiv.org/html/2608.11495#S5.Thmtheorem1), maximizing this term forces the attacker’s surrogate model to optimize in the region of highest curvature in the loss landscape, thereby maximizing the estimation error for the stolen model parameters\.

3\. Structural Compactness \(ℒstruct\\mathcal\{L\}\_\{\\text\{struct\}\}\)\.To ensure the "Benign Prototypes"𝐜k\\mathbf\{c\}\_\{k\}accurately represent the ID distribution, we add a regularization term that minimizes the distance between ID samples and their nearest prototype:

\(11\)ℒstruct=𝔼x∼𝒟i​d​\[mink⁡‖Φ⁡\(x\)−𝐜k‖22\]\.\\displaystyle\\mathcal\{L\}\_\{\\text\{struct\}\}=\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\_\{id\}\}\\left\[\\min\_\{k\}\\\|\\Phi\(x\)\-\\mathbf\{c\}\_\{k\}\\\|\_\{2\}^\{2\}\\right\]\.This creates tighter clusters for the benign data, improving the sensitivity of the gating mechanismα⁡\(x\)\\alpha\(x\)\.

The final optimization problem is to findΘr​e​p∗\\Theta\_\{rep\}^\{\*\}such that:

\(12\)Θr​e​p∗=arg⁡minΘr​e​p⁡\(ℒtask\+β1⋅ℒdefense\+β2⋅ℒstruct\),\\displaystyle\\Theta\_\{rep\}^\{\*\}=\\arg\\min\_\{\\Theta\_\{rep\}\}\\left\(\\mathcal\{L\}\_\{\\text\{task\}\}\+\\beta\_\{1\}\\cdot\\mathcal\{L\}\_\{\\text\{defense\}\}\+\\beta\_\{2\}\\cdot\\mathcal\{L\}\_\{\\text\{struct\}\}\\right\),whereβ1\\beta\_\{1\}andβ2\\beta\_\{2\}are hyperparameters controlling the defense strength and structural clustering, respectively\. Note that we freeze the original model parametersθT\\theta\_\{T\}to ensure parameter efficiency\.

#### 4\.4\.2\.Training Algorithm

The complete training procedure for GraphRP is summarized in Algorithm[1](https://arxiv.org/html/2608.11495#alg1)\. We use an alternating update strategy: first minimizing the structural loss to refine the gating boundary, and then optimizing the reprogramming noise to enforce the defense\.

1:Input:Pre\-trained Victim Model

T⁡\(⋅,θT\)T\(\\cdot;\\theta\_\{T\}\), Private Data

𝒟i​d\\mathcal\{D\}\_\{id\}, Auxiliary OOD Data

𝒟o​o​dd​e​f\\mathcal\{D\}\_\{ood\}^\{def\}\.

2:Hyperparameters:Margins

μ\\mu, weights

β1,β2\\beta\_\{1\},\\beta\_\{2\}, learning rate

η\\eta\.

3:Initialize:Reprogramming noise

𝜹\(l\)∼𝒩⁡\(0,ϵ\)\\bm\{\\delta\}^\{\(l\)\}\\sim\\mathcal\{N\}\(0,\\epsilon\), Prototypes

\{𝐜k\}\\\{\\mathbf\{c\}\_\{k\}\\\}via K\-Means on

𝒟i​d\\mathcal\{D\}\_\{id\}\(updated in Step 2 only; excluded fromΘr​e​p\\Theta\_\{rep\}gradient updates\), Distance threshold

τ\\tau\.

4:whilenot convergeddo

5:Step 1: Data Sampling

6:Sample benign batch

ℬi​d=\{\(x,y\)\}∼𝒟i​d\\mathcal\{B\}\_\{id\}=\\\{\(x,y\)\\\}\\sim\\mathcal\{D\}\_\{id\}\.

7:Sample OOD batch

ℬo​o​d=\{x′\}∼𝒟o​o​dd​e​f\\mathcal\{B\}\_\{ood\}=\\\{x^\{\\prime\}\\\}\\sim\\mathcal\{D\}\_\{ood\}^\{def\}\.

8:Step 2: Structural Update

9:Compute embeddings

Z=Φ⁡\(ℬi​d\)Z=\\Phi\(\\mathcal\{B\}\_\{id\}\)\.

10:Update

\{𝐜k\}\\\{\\mathbf\{c\}\_\{k\}\\\}to minimize

ℒstruct\\mathcal\{L\}\_\{\\text\{struct\}\}with Eq\. \([11](https://arxiv.org/html/2608.11495#S4.E11)\)\(independent ofΘr​e​p\\Theta\_\{rep\}gradient\)\.

11:Step 3: Gating & Forward Pass

12:Calculate gates

α⁡\(x\)\\alpha\(x\)for

x∈ℬi​d∪ℬo​o​dx\\in\\mathcal\{B\}\_\{id\}\\cup\\mathcal\{B\}\_\{ood\}with Eq\. \([7](https://arxiv.org/html/2608.11495#S4.E7)\)\.

13:Compute reprogrammed outputs

y~=T⁡\(x,θT,Θr​e​p\)\\tilde\{y\}=T\(x;\\theta\_\{T\},\\Theta\_\{rep\}\)\.

14:Compute original outputs

yo​r​i​g=T⁡\(x,θT\)y\_\{orig\}=T\(x;\\theta\_\{T\}\)\(for KL\)\.

15:Step 4: Reprogramming Update

16:Calculate

ℒtask\\mathcal\{L\}\_\{\\text\{task\}\}on

ℬi​d\\mathcal\{B\}\_\{id\}with Eq\. \([9](https://arxiv.org/html/2608.11495#S4.E9)\)\.

17:Calculate

ℒdefense\\mathcal\{L\}\_\{\\text\{defense\}\}on

ℬo​o​d\\mathcal\{B\}\_\{ood\}with Eq\. \([10](https://arxiv.org/html/2608.11495#S4.E10)\)\.

18:Compute Total Loss

ℒ\\mathcal\{L\}with Eq\. \([12](https://arxiv.org/html/2608.11495#S4.E12)\)\.

19:Update

Θr​e​p←Θr​e​p−η​∇Θr​e​pℒ\\Theta\_\{rep\}\\leftarrow\\Theta\_\{rep\}\-\\eta\\nabla\_\{\\Theta\_\{rep\}\}\\mathcal\{L\}\.

20:endwhile

21:Return:Protected Model

Tp​r​o​t​e​c​t​e​d​\(⋅\)=T⁡\(⋅,θT,Θr​e​p∗\)T\_\{protected\}\(\\cdot\)=T\(\\cdot;\\theta\_\{T\},\\Theta\_\{rep\}^\{\*\}\)\.

Algorithm 1Defensive Training forGraphRP\.Complexity Analysis\.The proposed defense is highly efficient\. The structural extractionΦ⁡\(x\)\\Phi\(x\)relies on simple statistics \(degree, eigenvalues\) computable inO⁡\(\|E\|\+n3\)O\(\|E\|\+n^\{3\}\)or approximated in linear time\. The reprogramming layer involves only element\-wise addition, adding negligible cost to theO⁡\(\|E\|​d\)O\(\|E\|d\)GNN inference\. Importantly, sinceθT\\theta\_\{T\}is frozen, the number of trainable parameters is extremely small \(\|Θr​e​p\|≪\|θT\|\|\\Theta\_\{rep\}\|\\ll\|\\theta\_\{T\}\|\), ensuring rapid convergence\.

## 5\.Theoretical Analysis

In this section, we provide a theoretical analysis for the effectiveness of GraphRP\. We consider the worst\-case scenario where the attacker has infinite query budget and capacity, aiming to learn a cloneCCthat properly mimics the reprogrammed victimTRT^\{R\}\. We measure the defense success by theLoss DisparityQ⁡\(C∗,T\)≜ℒi​d​\(C∗\)−ℒi​d​\(T\)Q\(C^\{\*\},T\)\\triangleq\\mathcal\{L\}\_\{id\}\(C^\{\*\}\)\-\\mathcal\{L\}\_\{id\}\(T\)on the benign distribution𝒢i​d\\mathcal\{G\}\_\{id\}\. Here𝒢i​d\\mathcal\{G\}\_\{id\}and𝒢o​o​d\\mathcal\{G\}\_\{ood\}denote the graph distributions induced by𝒟i​d\\mathcal\{D\}\_\{id\}and𝒟o​o​d\\mathcal\{D\}\_\{ood\}, respectively\.

Let𝜹~\(l\):=λ⋅Tanh⁡\(𝜹\(l\)\)\\tilde\{\\bm\{\\delta\}\}^\{\(l\)\}:=\\lambda\\cdot\\operatorname\{Tanh\}\(\\bm\{\\delta\}^\{\(l\)\}\)denote the effective bounded perturbation at layerll, which satisfies‖𝜹~\(l\)‖≤λ\\\|\\tilde\{\\bm\{\\delta\}\}^\{\(l\)\}\\\|\\leq\\lambdaby construction\. Our analysis assumes: \(A1\) the lossℓ\\ellis bounded by constantMM; \(A2\) the attacker is optimal, i\.e\.,C∗C^\{\*\}perfectly mimicsTRT^\{R\}on𝒢o​o​d\\mathcal\{G\}\_\{ood\}; and \(A3\) the KL divergence admits a local second\-order \(Fisher Information\) approximation in the bounded perturbation regime, where‖α⁡\(G\)⋅𝜹~‖≤λ⋅α⁡\(G\)≤λ\\\|\\alpha\(G\)\\cdot\\tilde\{\\bm\{\\delta\}\}\\\|\\leq\\lambda\\cdot\\alpha\(G\)\\leq\\lambdaby construction\.

###### Theorem 5\.1 \(Structural Defense Bound\)\.

LetC∗C^\{\*\}be the optimal clone model trained on OOD queriesG∼𝒢o​o​dG\\sim\\mathcal\{G\}\_\{ood\}reprogrammed by GraphRP\. Under the cross\-entropy loss, the performance gap between the clone and the victim on benign tasks is lower\-bounded by:

\(13\)Q⁡\(C∗,T\)≥𝔼G∼𝒢o​o​d​\[12​α​\(G\)2⋅𝜹~⊤​𝐈𝐡​\(G\)​𝜹~\]⏟Structural Sensitivity Term−2​M⋅𝕋​𝕍​\(𝒢i​d,𝒢o​o​d\)⏟Distribution Shift Term,\\displaystyle Q\(C^\{\*\},T\)\\geq\\underbrace\{\\mathbb\{E\}\_\{G\\sim\\mathcal\{G\}\_\{ood\}\}\\left\[\\frac\{1\}\{2\}\\alpha\(G\)^\{2\}\\cdot\\tilde\{\\bm\{\\delta\}\}^\{\\top\}\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)\\tilde\{\\bm\{\\delta\}\}\\right\]\}\_\{\\text\{Structural Sensitivity Term\}\}\-\\underbrace\{2M\\cdot\\mathbb\{TV\}\(\\mathcal\{G\}\_\{id\},\\mathcal\{G\}\_\{ood\}\)\}\_\{\\text\{Distribution Shift Term\}\},whereα⁡\(G\)\\alpha\(G\)is the structure\-aware gating factor,𝛅~=λ⋅Tanh⁡\(𝛅\)\\tilde\{\\bm\{\\delta\}\}=\\lambda\\cdot\\operatorname\{Tanh\}\(\\bm\{\\delta\}\)is the effective bounded perturbation, and𝐈𝐡​\(G\)\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)is the Fisher Information Matrix of the victim GNN with respect to the latent representation𝐡\\mathbf\{h\}\.

Remark\.The term𝜹~⊤​𝐈𝐡​\(G\)​𝜹~\\tilde\{\\bm\{\\delta\}\}^\{\\top\}\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)\\tilde\{\\bm\{\\delta\}\}captures thestructural sensitivityof the GNN, which is largest when the reprogramming noise aligns with high\-curvature directions of the model\. Because𝜹~\\tilde\{\\bm\{\\delta\}\}is bounded, the analysis remains in the local regime where the second\-order approximation in \(A3\) applies\. For attack queries withα⁡\(G\)≈1\\alpha\(G\)\\approx 1, GraphRP drives the learned surrogate boundary away from the benign boundary in proportion to this sensitivity\. The full proof is given in Appendix[A](https://arxiv.org/html/2608.11495#A1); the bound holds under assumptions \(A1\)–\(A3\) and should not be interpreted as unconditional\.

Table 1\.Main Defense Performance\.Clone model accuracy \(lower is better\) under Model Extraction attacks\. GraphRP consistently outperforms state\-of\-the\-art baselines across diverse datasets\.Table 2\.Target model utility \(test accuracy\) andℓ1\\ell\_\{1\}norm of the output difference\.
## 6\.Experiments

In this section, we empirically validate GraphRP\. We aim to answer three key questions:

\(1\)Defense Effectiveness:Does GraphRP significantly degrade the performance of surrogate models compared to state\-of\-the\-art baselines? \(2\)Utility Preservation:Does the defensive reprogramming maintain the utility of the target model for benign users? \(3\)Scalability & Robustness:Is the method effective on large\-scale graph benchmarks and robust against adaptive attackers?

### 6\.1\.Experimental Setup

Datasets\.We evaluate on a diverse set of graph classification benchmarks\([28](https://arxiv.org/html/2608.11495#bib.bib42)\), ranging from biochemical molecules to social networks\. To demonstrate scalability, we includeNCI1\([40](https://arxiv.org/html/2608.11495#bib.bib43)\)\(4k\+ graphs\) andOGB\-MolHIV\([14](https://arxiv.org/html/2608.11495#bib.bib44)\)\(41k\+ graphs\), alongside standard baselinesMUTAG\([6](https://arxiv.org/html/2608.11495#bib.bib45)\),ENZYMES\([2](https://arxiv.org/html/2608.11495#bib.bib46)\), andPROTEINS\([2](https://arxiv.org/html/2608.11495#bib.bib46)\)\. Note that this work focuses ongraph\-level classification, the dominant MLaaS deployment setting for GNNs\.

Baselines\.We compare GraphRP against five defense strategies: \(1\)RandP\(Random Perturbation\)\([32](https://arxiv.org/html/2608.11495#bib.bib15)\), \(2\)P\-Poison\([32](https://arxiv.org/html/2608.11495#bib.bib15)\), \(3\)GRAD\(Gradient Redirection\)\([27](https://arxiv.org/html/2608.11495#bib.bib17)\), \(4\)AM\(Adaptive Misinformation\)\([20](https://arxiv.org/html/2608.11495#bib.bib16)\), and \(5\)MeCo\([43](https://arxiv.org/html/2608.11495#bib.bib18)\), a recent contrastive defense\. These baselines represent the full spectrum of active defense strategies: output obfuscation \(RandP, P\-Poison\), gradient redirection \(GRAD\), adaptive misinformation \(AM\), and contrastive learning \(MeCo\), all applicable to the black\-box graph classification setting\.

Attack Configuration\.We employKnockoffNet\([31](https://arxiv.org/html/2608.11495#bib.bib21)\)as the query strategy\. The attacker trains surrogate models \(GraphSAGE\([12](https://arxiv.org/html/2608.11495#bib.bib2)\), Graph Isomorphism U\-Net \(GIUNET\)\([1](https://arxiv.org/html/2608.11495#bib.bib47)\), Gaussian\-Induced Convolution \(GIC\)\([16](https://arxiv.org/html/2608.11495#bib.bib48)\)\) using eithersoft\-label\(probability vector\) orhard\-label\(top\-1\) supervision from the victim\. Our evaluation collectively covers soft\-label attacks, hard\-label attacks, adaptive gray\-box attacks \(Section[6\.3](https://arxiv.org/html/2608.11495#S6.SS3)\), data leakage scenarios, and varying query budgets, providing comprehensive coverage of realistic ME threat models\. Detailed hyperparameters and architecture settings are provided in Appendix[C](https://arxiv.org/html/2608.11495#A3)\.

### 6\.2\.Defense Performance \(RQ1 & RQ2\)

#### 6\.2\.1\.Reducing Clone Model Accuracy

The primary goal of the defender is to maximize the error of the attacker’s clone model\. The detailed numbers are shown in Table[1](https://arxiv.org/html/2608.11495#S5.T1), Table[A1](https://arxiv.org/html/2608.11495#A1.T1)\(MUTAG & ENZYMES\) and Table[A2](https://arxiv.org/html/2608.11495#A1.T2)\(NCI1 & PROTEINS\)\.

Figure[3](https://arxiv.org/html/2608.11495#S6.F3)summarizes the performance on MUTAG and ENZYMES\. We can observe that GraphRP consistently achieves the lowest clone accuracy across all scenarios\. For instance, on MUTAG under soft\-label attack, our method reduces the clone accuracy from76\.5%76\.5\\%\(Undefended\) to60\.3%60\.3\\%, significantly outperforming the best baseline \(MeCo at71\.2%71\.2\\%\)\.

MUTAG\-SoftMUTAG\-HardENZ\-SoftENZ\-Hard0\.40\.40\.60\.60\.80\.8110\.770\.770\.740\.740\.560\.560\.490\.490\.710\.710\.610\.610\.480\.480\.430\.430\.60\.60\.570\.570\.360\.360\.340\.34Clone Accuracy \(↓\\downarrow\)No DefenseMeCoGraphRP \(Ours\)Figure 3\.Attack Success Rate comparison\.Clone model accuracy \(lower is better\) on MUTAG and ENZYMES\. GraphRP outperforms the best baseline \(MeCo\) and the undefended setting, reducing clone accuracy by up to∼15%\\sim 15\\%compared to the undefended model\.
#### 6\.2\.2\.Utility\-Defense Trade\-off

A robust defense must not degrade the experience for benign users, as shown in Table[2](https://arxiv.org/html/2608.11495#S5.T2)\.

We analyze the trade\-off betweenUtility LossandDefense Success\. As shown in Figure[4](https://arxiv.org/html/2608.11495#S6.F4), GraphRP achieves the strongest defense while incurring less than2%2\\%utility loss, whereas baseline methods suffer a substantially larger utility\-defense trade\-off\. This advantage stems from theStructure\-Aware Gatingmechanism, which effectively distinguishes benign from adversarial queries \(AUROC\>0\.91\>0\.91, FPR<0\.06<0\.06\), enabling selective activation of the defense\.

Computational Efficiency\.A potential concern with spectral methods is the cost of eigendecomposition\. However, GraphRP mitigates this by computing only the top\-kkeigenvalues \(wherek≪nk\\ll n\) using efficient iterative methods like the Lanczos algorithm\. Furthermore, feature extraction is performed at thegraph level, not the node level, meaning the overhead scales linearly with the batch size rather than the number of nodes\. As shown in Table[A4](https://arxiv.org/html/2608.11495#A3.T4), the additional latency is marginal \(≈7%\\approx 7\\%\) compared to the heavy matrix multiplications in the GNN backbone, ensuring GraphRP remains suitable for real\-time MLaaS latency constraints\.

### 6\.3\.Robustness and Scalability Analysis \(RQ3\)

To validate the resilience of GraphRP in hostile environments, we conducted two stress tests \(detailed results in Appendix[D](https://arxiv.org/html/2608.11495#A4)\)\.

Defending against Adaptive Attackers\.We simulated a sophisticated "gray\-box" attacker who is aware of the GraphRP defense mechanism\. This adaptive adversary employs aStructural Generator\(based on GraphGAN\([42](https://arxiv.org/html/2608.11495#bib.bib49)\)\) explicitly trained to generate queries that mimic the topological statistics of the benign dataset, attempting to bypass our Structure\-Aware Gating\.

As shown in Table[3](https://arxiv.org/html/2608.11495#S6.T3), GraphRP largely remains effective even against this adaptive strategy, confirming that spectral eigenvalues serve as a “structural fingerprint” that is mathematically difficult to spoof without access to the private training manifold\. Furthermore, GraphRP outperforms simpler OOD\-based strategies—query rejection \(OOD\-Reject\) and uniform\-confidence return \(Low\-Conf\)—achieving strictly lower clone accuracy and higher benign accuracy simultaneously, while returning outputs in a confidence range similar to genuine predictions\.

Finally, Table[4](https://arxiv.org/html/2608.11495#S6.T4)shows that GraphRP maintains robustness even when the attacker gains access to a portion of the private training data: with10%10\\%ID data leaked, clone accuracy increases by only3\.2%3\.2\\%\(vs\.5\.2%5\.2\\%for Undefended\), confirming resilience to partial distribution shift\.

00112233440010102020RandPMeCoGraphRP↑\\uparrowDefense←\\leftarrowUtilityUtility Drop on Benign Data \(%\\%, Lower is better\)Clone Accuracy Reduction \(%\\%, Higher is better\)Figure 4\.Utility vs\. Defense Trade\-off on NCI1\.The y\-axis represents the reduction in attacker accuracy \(Benefit\), and the x\-axis represents the drop in benign accuracy \(Cost\)\. GraphRP provides the best protection\-to\-cost ratio\.0\.5x1x2x3x4x5x0\.50\.50\.60\.60\.70\.70\.80\.80\.90\.9Attacker Query Budget \(×\\timesSize of\|Dt​r​a​i​n\|\|D\_\{train\}\|\)Clone Model AccuracyUndefendedRandPGraphRPFigure 5\.Effect of Query Budget on Attack Success \(NCI1\)\.As the attacker increases the query budget, the clone accuracy of the undefended model rises steadily\. In contrast, GraphRP effectively saturates the attacker’s learning, keeping accuracy low \(≈55%\\approx 55\\%\) regardless of the budget\.Table 3\.Adaptive Defense Robustness \(MUTAG\)\.Clone accuracy under Standard & Adaptive attacks\. GraphRP remains effective even when attacker mimics benign graph structure\.Table 4\.Robustness against Data Leakage \(MUTAG\)\.Clone accuracy when attacker mixes10%10\\%private ID data into queries\. GraphRP remains robust under partial distribution shift\.Scalability \(Large\-Scale Graphs\)\.Table[5](https://arxiv.org/html/2608.11495#S6.T5)reports defense performance on two large\-scale benchmarks:OGB\-MolHIV\(41k molecular graphs\) andCOLLAB\(dense social network\)\. GraphRP achieves the lowest clone accuracy on both datasets while maintaining high benign utility, demonstrating that our spectral structural prototypes generalize effectively to large and topologically diverse graph manifolds\.

Table 5\.Large\-Scale Defense Performance\.Clone accuracy \(↓\\downarrow\) and test accuracy \(↑\\uparrow\) on OGB\-MolHIV and COLLAB\.Impact of Query Budget\.Standard active defenses often fail under unlimited query budgets, as noise eventually averages out\. As shown in Figure[5](https://arxiv.org/html/2608.11495#S6.F5), while the Undefended model’s clone accuracy increases steadily with budget \(0\.5×0\.5\\times–5×5\\times\), GraphRP saturates at a low level \(≈55%\\approx 55\\%on NCI1\), indicating that reprogramming noise fundamentally poisons the decision boundary, rendering additional queries uninformative\.

Defense Transferability against Complex Surrogates\.A realistic risk is that an attacker employs a more powerful architecture than the victim to extract the model\. We tested the following scenario: the victim uses the standard G\-Inception target, while the attacker uses a powerful Graph Transformer\([10](https://arxiv.org/html/2608.11495#bib.bib50)\)\. As detailed in Appendix[D\.2](https://arxiv.org/html/2608.11495#A4.SS2), GraphRP successfully degrades the Graph Transformer’s performance from82\.4%82\.4\\%to64\.1%64\.1\\%\. This confirms that GraphRP’s layer\-wise reprogramming distorts the underlying data manifold itself, making the poisoned labels effective regardless of the attacker’s model capacity\.

Ablation\.To understand which features drive our Gating Mechanism, we ablate Node Degrees, Clustering Coefficients, and Spectral Eigenvalues\. As shown in Figure[6](https://arxiv.org/html/2608.11495#S6.F6),Spectral Featuresare the most critical: removing them increases clone accuracy from 0\.603 to 0\.685, indicating a substantially weaker defense, while removing degree statistics has only a minor impact, validating that global spectral properties are the hardest for attackers to mimic\.

Full Methodw/o Degreew/o Clusteringw/o Spectral0\.40\.40\.50\.50\.60\.60\.70\.70\.80\.80\.60\.60\.620\.620\.640\.640\.690\.69Clone Accuracy \(Lower is Better\)Figure 6\.Feature Importance Ablation \(MUTAG\)\.Removing spectral features causes the sharpest accuracy rise, confirming they are the most critical component for OOD detection\.

## 7\.Conclusion

In this work, we presentedGraphRP, a dynamic defense against GNN model extraction\. GraphRP combines model reprogramming with structure\-aware gating to selectively poison surrogate training while preserving benign utility\. Under the stated assumptions, our analysis provides a lower bound on the attacker’s estimation error, and experiments show that GraphRP scales effectively to large graph datasets\.

##### Future Directions\.

Future work will extend GraphRP to node\-level tasks through localized ego\-graph prototypes and adapt it to heterogeneous and dynamic graphs, where evolving topology requires continuous prototype calibration\.

###### Acknowledgements\.

This work was partially supported by NSF IIS\-2347592, IIS\-2348169, DBI\-2405416, CCF\-2348306, CNS\-2347617, and RISE\-2536663\.

## References

- Amouzadet al\.\(2024\)A\. Amouzad, Z\. Dehghanian, S\. Saravani, M\. Amirmazlaghani, and B\. RoshanfekrGraph isomorphism u\-net\.Expert Systems with Applications236,pp\. 121280\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p3.1)\.
- Borgwardtet al\.\(2005\)K\. M\. Borgwardt, C\. S\. Ong, S\. Schönauer, S\. Vishwanathan, A\. J\. Smola, and H\. KriegelProtein function prediction via graph kernels\.Bioinformatics21\(suppl\_1\),pp\. i47–i56\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p1.1)\.
- Chen \(2024\)P\. ChenModel reprogramming: resource\-efficient cross\-domain machine learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 22584–22591\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p4.1),[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p1.1),[§4\.2](https://arxiv.org/html/2608.11495#S4.SS2.p1.1)\.
- Chung \(1997\)F\. R\. ChungSpectral graph theory\.Vol\.92,American Mathematical Soc\.\.Cited by:[§4\.3](https://arxiv.org/html/2608.11495#S4.SS3.p2.2)\.
- Correia\-Silvaet al\.\(2018\)J\. R\. Correia\-Silva, R\. F\. Berriel, C\. Badue, A\. F\. De Souza, and T\. Oliveira\-SantosCopycat cnn: stealing knowledge by persuading confession with random non\-labeled data\.In2018 International joint conference on neural networks \(IJCNN\),pp\. 1–8\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p2.1)\.
- Debnathet al\.\(1991\)A\. K\. Debnath, R\. L\. Lopez de Compadre, G\. Debnath, A\. J\. Shusterman, and C\. HanschStructure\-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds\. correlation with molecular orbital energies and hydrophobicity\.Journal of medicinal chemistry34\(2\),pp\. 786–797\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p1.1)\.
- DeFazio and Ramesh \(2019\)D\. DeFazio and A\. RameshAdversarial model extraction on graph neural networks\.arXiv preprint arXiv:1912\.07721\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p4.1)\.
- Defferrardet al\.\(2016\)M\. Defferrard, X\. Bresson, and P\. VandergheynstConvolutional neural networks on graphs with fast localized spectral filtering\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.29,pp\. 3844–3852\.Cited by:[§4\.3](https://arxiv.org/html/2608.11495#S4.SS3.p2.2)\.
- Downeret al\.\(2025\)J\. Downer, R\. Wang, and B\. WangWatermarking graph neural networks via explanations for ownership protection\.arXiv preprint arXiv:2501\.05614\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p2.1)\.
- Dwivedi and Bresson \(2020\)V\. P\. Dwivedi and X\. BressonA generalization of transformer networks to graphs\.arXiv preprint arXiv:2012\.09699\.Cited by:[§D\.2](https://arxiv.org/html/2608.11495#A4.SS2.p1.1),[§6\.3](https://arxiv.org/html/2608.11495#S6.SS3.p7.1)\.
- Elsayedet al\.\(2018\)G\. F\. Elsayed, I\. Goodfellow, and J\. Sohl\-DicksteinAdversarial reprogramming of neural networks\.arXiv preprint arXiv:1806\.11146\.Cited by:[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p1.1)\.
- Hamiltonet al\.\(2017\)W\. Hamilton, Z\. Ying, and J\. LeskovecInductive representation learning on large graphs\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1),[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p3.1)\.
- Hintonet al\.\(2015\)G\. Hinton, O\. Vinyals, and J\. DeanDistilling the knowledge in a neural network\.arXiv preprint arXiv:1503\.02531\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p3.1)\.
- Huet al\.\(2020\)W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. LeskovecOpen graph benchmark: datasets for machine learning on graphs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.33,pp\. 22118–22133\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p1.1)\.
- Jiaet al\.\(2021\)H\. Jia, C\. A\. Choquette\-Choo, V\. Chandrasekaran, and N\. PapernotEntangled watermarks as a defense against model extraction\.In30th USENIX security symposium \(USENIX Security 21\),pp\. 1937–1954\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p2.1),[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p4.1)\.
- Jianget al\.\(2019\)J\. Jiang, Z\. Cui, C\. Xu, and J\. YangGaussian\-induced convolution for graphs\.InProceedings of the AAAI conference on artificial intelligence,Vol\.33,pp\. 4007–4014\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p3.1)\.
- Jinget al\.\(2023\)Y\. Jing, C\. Yuan, L\. Ju, Y\. Yang, X\. Wang, and D\. TaoDeep graph reprogramming\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 24345–24354\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p4.1),[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p2.1),[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p3.1)\.
- Kariyappaet al\.\(2021a\)S\. Kariyappa, A\. Prakash, and M\. K\. QureshiMaze: data\-free model stealing attack using zeroth\-order gradient estimation\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 13814–13823\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p2.1)\.
- Kariyappaet al\.\(2021b\)S\. Kariyappa, A\. Prakash, and M\. K\. QureshiProtecting dnns from theft using an ensemble of diverse models\.InInternational Conference on Learning Representations,Cited by:[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p3.1)\.
- Kariyappa and Qureshi \(2020\)S\. Kariyappa and M\. K\. QureshiDefending against model stealing attacks with adaptive misinformation\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 770–778\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p3.1),[Table 1](https://arxiv.org/html/2608.11495#S5.T1.6.7.1.1),[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p2.1)\.
- Kipf and Welling \(2017\)T\. N\. Kipf and M\. WellingSemi\-supervised classification with graph convolutional networks\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Liet al\.\(2023\)X\. Li, L\. Sun, M\. Ling, and Y\. PengA survey of graph neural network based recommendation in social networks\.Neurocomputing549,pp\. 126441\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Liuet al\.\(2021\)Y\. Liu, X\. Ao, Z\. Qin, J\. Chi, J\. Feng, H\. Yang, and Q\. HePick and choose: a gnn\-based imbalanced learning approach for fraud detection\.InProceedings of the web conference 2021,pp\. 3168–3177\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Liuet al\.\(2023\)Y\. Liu, C\. Fan, P\. Zhou, and L\. SunUnlearnable graph: protecting graphs from unauthorized exploitation\.arXiv preprint arXiv:2303\.02568\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Longet al\.\(2022\)Y\. Long, M\. Wu, Y\. Liu, Y\. Fang, C\. K\. Kwoh, J\. Chen, J\. Luo, and X\. LiPre\-training graph neural networks for link prediction in biomedical networks\.Bioinformatics38\(8\),pp\. 2254–2262\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Mainiet al\.\(2021\)P\. Maini, M\. Yaghini, and N\. PapernotDataset inference: ownership resolution in machine learning\.arXiv preprint arXiv:2104\.10706\.Cited by:[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p2.1)\.
- Mazeikaet al\.\(2022\)M\. Mazeika, B\. Li, and D\. ForsythHow to steer your adversary: targeted and efficient model stealing defenses with gradient redirection\.InInternational Conference on Machine Learning,pp\. 15241–15254\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p3.1),[Table 1](https://arxiv.org/html/2608.11495#S5.T1.6.6.1.1),[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p2.1)\.
- Morriset al\.\(2020\)C\. Morris, N\. M\. Kriege, F\. Bause, K\. Kersting, P\. Mutzel, and M\. NeumannTudataset: a collection of benchmark datasets for learning with graphs\.arXiv preprint arXiv:2007\.08663\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p1.1)\.
- Ohet al\.\(2019\)S\. J\. Oh, B\. Schiele, and M\. FritzTowards reverse\-engineering black\-box neural networks\.Explainable AI: interpreting, explaining and visualizing deep learning,pp\. 121–144\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1)\.
- Oliynyket al\.\(2023\)D\. Oliynyk, R\. Mayer, and A\. RauberI know what you trained last summer: a survey on stealing machine learning models and defences\.ACM Computing Surveys55\(14s\),pp\. 1–41\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1)\.
- Orekondyet al\.\(2019\)T\. Orekondy, B\. Schiele, and M\. FritzKnockoff nets: stealing functionality of black\-box models\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 4954–4963\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1),[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p3.1)\.
- Orekondyet al\.\(2020\)T\. Orekondy, B\. Schiele, and M\. FritzPrediction poisoning: towards defenses against DNN model stealing attacks\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p3.1),[Table 1](https://arxiv.org/html/2608.11495#S5.T1.6.4.1.1),[Table 1](https://arxiv.org/html/2608.11495#S5.T1.6.5.1.1),[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p2.1)\.
- Papernotet al\.\(2017\)N\. Papernot, P\. McDaniel, I\. Goodfellow, S\. Jha, Z\. B\. Celik, and A\. SwamiPractical black\-box attacks against machine learning\.InProceedings of the 2017 ACM on Asia conference on computer and communications security,pp\. 506–519\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p2.1)\.
- Reithet al\.\(2019\)R\. N\. Reith, T\. Schneider, and O\. TkachenkoEfficiently stealing your machine learning models\.InProceedings of the 18th ACM Workshop on Privacy in the Electronic Society,pp\. 198–210\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1)\.
- Shenet al\.\(2022\)Y\. Shen, X\. He, Y\. Han, and Y\. ZhangModel stealing attacks against inductive graph neural networks\.In2022 IEEE Symposium on Security and Privacy \(SP\),pp\. 1175–1192\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p4.1)\.
- Sunet al\.\(2023\)X\. Sunet al\.All in one: multi\-task prompting for graph neural networks\.InProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 2120–2131\.Cited by:[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p2.1),[§2\.3](https://arxiv.org/html/2608.11495#S2.SS3.p3.1)\.
- Szylleret al\.\(2021\)S\. Szyller, B\. G\. Atli, S\. Marchal, and N\. AsokanDawn: dynamic adversarial watermarking of neural networks\.InProceedings of the 29th ACM International Conference on Multimedia,pp\. 4417–4425\.Cited by:[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p2.1)\.
- Truonget al\.\(2021\)J\. Truong, P\. Maini, R\. J\. Walls, and N\. PapernotData\-free model extraction\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 4771–4780\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p2.1)\.
- Veličkovićet al\.\(2018\)P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. BengioGraph attention networks\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Waleet al\.\(2008\)N\. Wale, I\. A\. Watson, and G\. KarypisComparison of descriptor spaces for chemical compound retrieval and classification\.Knowledge and Information Systems14,pp\. 347–375\.Cited by:[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p1.1)\.
- Wang and Gong \(2018\)B\. Wang and N\. Z\. GongStealing hyperparameters in machine learning\.In2018 IEEE symposium on security and privacy \(SP\),pp\. 36–52\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p1.1)\.
- Wanget al\.\(2018\)H\. Wang, J\. Wang, J\. Wang, M\. Zhao, W\. Zhang, F\. Zhang, X\. Xie, and M\. GuoGraphgan: graph representation learning with generative adversarial nets\.InProceedings of the AAAI conference on artificial intelligence,Vol\.32\.Cited by:[§D\.1](https://arxiv.org/html/2608.11495#A4.SS1.p1.1),[§6\.3](https://arxiv.org/html/2608.11495#S6.SS3.p2.1)\.
- Wanget al\.\(2023\)Z\. Wang, L\. Shen, T\. Liu, T\. Duan, Y\. Zhu, D\. Zhan, D\. Doermann, and M\. GaoDefending against data\-free model extraction by distributionally robust defensive training\.Advances in Neural Information Processing Systems36\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p3.1),[§3\.4](https://arxiv.org/html/2608.11495#S3.SS4.p1.1),[Table 1](https://arxiv.org/html/2608.11495#S5.T1.6.8.1.1),[§6\.1](https://arxiv.org/html/2608.11495#S6.SS1.p2.1)\.
- Wang \(2021\)Z\. WangZero\-shot knowledge distillation from a decision\-based black\-box model\.InInternational conference on machine learning,pp\. 10675–10685\.Cited by:[§3\.4](https://arxiv.org/html/2608.11495#S3.SS4.p1.1)\.
- Wuet al\.\(2022a\)B\. Wu, X\. Yang, S\. Pan, and X\. YuanModel extraction attacks on graph neural networks: taxonomy and realisation\.InProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security,pp\. 337–350\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p4.1)\.
- Wuet al\.\(2022b\)S\. Wu, F\. Sun, W\. Zhang, X\. Xie, and B\. CuiGraph neural networks in recommender systems: a survey\.ACM Computing Surveys55\(5\),pp\. 1–37\.Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1)\.
- Xuet al\.\(2025a\)H\. Xu, R\. Qian, J\. Li, Y\. Dong, M\. Lin, H\. Yan, Z\. Yao, Q\. Liu, J\. Dong, R\. Huang,et al\.A systematic study of model extraction attacks on graph foundation models\.arXiv preprint arXiv:2511\.11912\.Cited by:[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p4.1)\.
- Xuet al\.\(2025b\)J\. Xu, F\. Boenisch, and A\. DziedzicADAGE: active defenses against gnn extraction\.arXiv preprint arXiv:2503\.00065\.Cited by:[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p4.1)\.
- Yinget al\.\(2018\)Z\. Ying, J\. You, C\. Morris, X\. Ren, W\. L\. Hamilton, and J\. LeskovecHierarchical graph representation learning with differentiable pooling\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.31\.Cited by:[§4\.3](https://arxiv.org/html/2608.11495#S4.SS3.p6.1)\.
- Zhuanget al\.\(2024\)Y\. Zhuang, C\. Shi, M\. Zhang, J\. Chen, L\. Lyu, P\. Zhou, and L\. SunUnveiling the secrets without data: can graph neural networks be exploited through data\-free model extraction attacks?\.In33rd USENIX Security Symposium \(USENIX Security 24\),Cited by:[§1](https://arxiv.org/html/2608.11495#S1.p1.1),[§2\.1](https://arxiv.org/html/2608.11495#S2.SS1.p4.1),[§2\.2](https://arxiv.org/html/2608.11495#S2.SS2.p3.1)\.

## Appendix ADetails of Theoretical Analysis

Here, we provide the rigorous derivation of Theorem[5\.1](https://arxiv.org/html/2608.11495#S5.Thmtheorem1)\.

### A\.1\.Preliminaries

Let𝒢i​d\\mathcal\{G\}\_\{id\}and𝒢o​o​d\\mathcal\{G\}\_\{ood\}denote the benign and adversarial graph distributions\. Let𝜹~\(l\):=λ⋅Tanh⁡\(𝜹\(l\)\)\\tilde\{\\bm\{\\delta\}\}^\{\(l\)\}:=\\lambda\\cdot\\operatorname\{Tanh\}\(\\bm\{\\delta\}^\{\(l\)\}\)denote the effective bounded perturbation at layerll, satisfying‖𝜹~\(l\)‖≤λ\\\|\\tilde\{\\bm\{\\delta\}\}^\{\(l\)\}\\\|\\leq\\lambdaby construction\. The victim model output isT⁡\(G\)T\(G\), and the reprogrammed victim isTR​\(G\)=T⁡\(𝐇\(l\)\+α⁡\(G\)​𝜹~\)T^\{R\}\(G\)=T\(\\mathbf\{H\}^\{\(l\)\}\+\\alpha\(G\)\\tilde\{\\bm\{\\delta\}\}\)for thell\-th layer\. The attacker minimizes the expected risk on the query distribution:ℒo​o​d​\(C\)=𝔼G∼𝒢o​o​d​\[ℓ⁡\(C⁡\(G\),TR​\(G\)\)\]\\mathcal\{L\}\_\{ood\}\(C\)=\\mathbb\{E\}\_\{G\\sim\\mathcal\{G\}\_\{ood\}\}\[\\ell\(C\(G\),T^\{R\}\(G\)\)\]\. We assume the loss functionℓ\\ellis bounded by constantMM\.

### A\.2\.Proof of Theorem[5\.1](https://arxiv.org/html/2608.11495#S5.Thmtheorem1)

###### Proof\.

Step 1: Relating ID and OOD Performance\.We aim to lower\-boundQ⁡\(C∗,T\)=ℒi​d​\(C∗\)−ℒi​d​\(T\)Q\(C^\{\*\},T\)=\\mathcal\{L\}\_\{id\}\(C^\{\*\}\)\-\\mathcal\{L\}\_\{id\}\(T\)\. For any bounded functionffwith boundMM, the difference in expected loss across distributions satisfies\|𝔼P​\[f\]−𝔼Q​\[f\]\|≤M⋅‖P−Q‖1\|\\mathbb\{E\}\_\{P\}\[f\]\-\\mathbb\{E\}\_\{Q\}\[f\]\|\\leq M\\cdot\\\|P\-Q\\\|\_\{1\}, which gives:

\(14\)\|ℒi​d​\(C∗\)−ℒo​o​d​\(C∗\)\|≤2​M⋅𝕋​𝕍​\(𝒢i​d,𝒢o​o​d\)\.\|\\mathcal\{L\}\_\{id\}\(C^\{\*\}\)\-\\mathcal\{L\}\_\{ood\}\(C^\{\*\}\)\|\\leq 2M\\cdot\\mathbb\{TV\}\(\\mathcal\{G\}\_\{id\},\\mathcal\{G\}\_\{ood\}\)\.Since the victimTTis well\-trained on𝒟i​d\\mathcal\{D\}\_\{id\}\(i\.e\.,ℒi​d​\(T\)≈0\\mathcal\{L\}\_\{id\}\(T\)\\approx 0\):

\(15\)Q⁡\(C∗,T\)≥ℒo​o​d​\(C∗\)−2​M⋅𝕋​𝕍​\(𝒢i​d,𝒢o​o​d\)\.Q\(C^\{\*\},T\)\\geq\\mathcal\{L\}\_\{ood\}\(C^\{\*\}\)\-2M\\cdot\\mathbb\{TV\}\(\\mathcal\{G\}\_\{id\},\\mathcal\{G\}\_\{ood\}\)\.
Step 2: Optimal Attacker Assumption\.Assume the attacker trains the cloneC∗C^\{\*\}to minimize the divergence from the observed query responsesTR​\(G\)T^\{R\}\(G\)\. Under the optimal attacker assumption, the clone perfectly learns the reprogrammed distribution, i\.e\.,C∗​\(G\)≈TR​\(G\)C^\{\*\}\(G\)\\approx T^\{R\}\(G\)\. We evaluate the clone’s errorℒo​o​d\\mathcal\{L\}\_\{ood\}against theoriginalvictimTTusing Cross\-Entropy\. By decomposing Cross\-Entropy into Entropy \(HH\) and KL\-Divergence \(DKLD\_\{\\text\{KL\}\}\), and noting thatH⁡\(T⁡\(G\)\)≥0H\(T\(G\)\)\\geq 0, we obtain the lower bound:

ℒo​o​d​\(C∗\)\\displaystyle\\mathcal\{L\}\_\{ood\}\(C^\{\*\}\)=𝔼G∼𝒢o​o​d\[H\(T\(G\)\)\+DKL\(T\(G\)∥C∗\(G\)\)\]\\displaystyle=\\mathbb\{E\}\_\{G\\sim\\mathcal\{G\}\_\{ood\}\}\[H\(T\(G\)\)\+D\_\{\\text\{KL\}\}\(T\(G\)\\parallel C^\{\*\}\(G\)\)\]\(16\)≥𝔼G∼𝒢o​o​d\[DKL\(T\(G\)∥TR\(G\)\)\]\.\\displaystyle\\geq\\mathbb\{E\}\_\{G\\sim\\mathcal\{G\}\_\{ood\}\}\[D\_\{\\text\{KL\}\}\(T\(G\)\\parallel T^\{R\}\(G\)\)\]\.
Step 3: Taylor Expansion via Fisher Information\.LetP⁡\(Y\|𝐡\)P\(Y\|\\mathbf\{h\}\)be the victim’s output distribution parameterized by graph embedding𝐡\\mathbf\{h\}, soTR​\(G\)T^\{R\}\(G\)corresponds toP⁡\(Y\|𝐡\+ϵ\)P\(Y\|\\mathbf\{h\}\+\\epsilon\)withϵ=α⁡\(G\)⋅𝜹~\\epsilon=\\alpha\(G\)\\cdot\\tilde\{\\bm\{\\delta\}\}\. Since𝜹~=λ⋅Tanh⁡\(𝜹\)\\tilde\{\\bm\{\\delta\}\}=\\lambda\\cdot\\operatorname\{Tanh\}\(\\bm\{\\delta\}\), the effective perturbation satisfies‖ϵ‖≤λ⋅α⁡\(G\)≤λ\\\|\\epsilon\\\|\\leq\\lambda\\cdot\\alpha\(G\)\\leq\\lambda, which ensures the perturbation remains in the local regime where the following Taylor expansion is applicable\. SinceDKL\(P∥P\)=0D\_\{\\text\{KL\}\}\(P\\\|P\)=0and the first\-order term vanishes, a second\-order Taylor expansion gives:

\(17\)DKL\(P\(Y\|𝐡\)∥P\(Y\|𝐡\+ϵ\)\)≈12ϵ⊤𝐈𝐡\(G\)ϵ\+O\(∥ϵ∥3\),D\_\{\\text\{KL\}\}\(P\(Y\|\\mathbf\{h\}\)\\parallel P\(Y\|\\mathbf\{h\}\+\\epsilon\)\)\\approx\\tfrac\{1\}\{2\}\\epsilon^\{\\top\}\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)\\epsilon\+O\(\\\|\\epsilon\\\|^\{3\}\),where𝐈𝐡​\(G\)=𝔼y∼P⁡\(Y\|𝐡\)​\[∇𝐡​log​P​\(y\|𝐡\)​∇𝐡​log⁡P​\(y\|𝐡\)⊤\]\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)=\\mathbb\{E\}\_\{y\\sim P\(Y\|\\mathbf\{h\}\)\}\\left\[\\nabla\_\{\\mathbf\{h\}\}\\log P\(y\|\\mathbf\{h\}\)\\nabla\_\{\\mathbf\{h\}\}\\log P\(y\|\\mathbf\{h\}\)^\{\\top\}\\right\]is the Fisher Information Matrix \(FIM\)\.

Step 4: Combining Terms\.Substitutingϵ=α⁡\(G\)⋅𝜹~\\epsilon=\\alpha\(G\)\\cdot\\tilde\{\\bm\{\\delta\}\}:

\(18\)DKL\(T\(G\)∥TR\(G\)\)≈12α\(G\)2𝜹~⊤𝐈𝐡\(G\)𝜹~\.D\_\{\\text\{KL\}\}\(T\(G\)\\parallel T^\{R\}\(G\)\)\\approx\\frac\{1\}\{2\}\\alpha\(G\)^\{2\}\\tilde\{\\bm\{\\delta\}\}^\{\\top\}\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)\\tilde\{\\bm\{\\delta\}\}\.Substituting this back into the bounds from Steps 1 and 2 yields the final bound:

\(19\)Q⁡\(C∗,T\)≥𝔼G∼𝒢o​o​d​\[12​α​\(G\)2​𝜹~⊤​𝐈𝐡​\(G\)​𝜹~\]−2​M⋅𝕋​𝕍​\(𝒢i​d,𝒢o​o​d\)\.Q\(C^\{\*\},T\)\\geq\\mathbb\{E\}\_\{G\\sim\\mathcal\{G\}\_\{ood\}\}\\left\[\\frac\{1\}\{2\}\\alpha\(G\)^\{2\}\\tilde\{\\bm\{\\delta\}\}^\{\\top\}\\mathbf\{I\}\_\{\\mathbf\{h\}\}\(G\)\\tilde\{\\bm\{\\delta\}\}\\right\]\-2M\\cdot\\mathbb\{TV\}\(\\mathcal\{G\}\_\{id\},\\mathcal\{G\}\_\{ood\}\)\.∎

Table A1\.Hard\-label defense performance on MUTAG & ENZYMES\.Soft\-label results are in Table[1](https://arxiv.org/html/2608.11495#S5.T1)\.Table A2\.Hard\-label defense performance on NCI1 & PROTEINS\.Soft\-label results are in Table[1](https://arxiv.org/html/2608.11495#S5.T1)\.Table A3\.Clone model accuracy after applyingadaptive attackon MUTAG withG\_Inceptionas target model\.

## Appendix BImplementation Details of GraphRP

### B\.1\.Structure ExtractorΦ⁡\(G\)\\Phi\(G\)

The structural embedding𝐳G=Φ⁡\(G\)\\mathbf\{z\}\_\{G\}=\\Phi\(G\)concatenates three permutation\-invariant feature groups: \(1\)Spectral Features— top\-kksorted eigenvalues of the normalized Laplacian𝐋=𝐈−𝐃−1/2𝐀𝐃−1/2\\mathbf\{L\}=\\mathbf\{I\}\-\\mathbf\{D\}^\{\-1/2\}\\mathbf\{A\}\\mathbf\{D\}^\{\-1/2\}, with zero\-padding for small graphs \(n<50n<50\) and truncation for large ones \(k=8k=8for molecular datasets\); \(2\)Degree Statistics— a 4\-dimensional vector of\[min,max,mean,std\]\[\\min,\\max,\\text\{mean\},\\text\{std\}\]of node degrees; \(3\)Global Properties— graph diameter, average clustering coefficient, and density\. The final vector isℓ2\\ell\_\{2\}\-normalized:𝐳G←𝐳G/‖𝐳G‖2\\mathbf\{z\}\_\{G\}\\leftarrow\\mathbf\{z\}\_\{G\}/\\\|\\mathbf\{z\}\_\{G\}\\\|\_\{2\}\.

### B\.2\.Prototype Learning

Prototypes\{𝐜k\}k=1K\\\{\\mathbf\{c\}\_\{k\}\\\}\_\{k=1\}^\{K\}are initialized via K\-Means \(K=5K=5\) on𝒟i​dt​r​a​i​n\\mathcal\{D\}\_\{id\}^\{train\}and updated exclusively viaℒstruct\\mathcal\{L\}\_\{\\text\{struct\}\}in Step 2 of Algorithm[1](https://arxiv.org/html/2608.11495#alg1), independently ofΘr​e​p\\Theta\_\{rep\}\. The gating factor is:

\(20\)α⁡\(G\)=Sigmoid⁡\(γ⋅\(mink⁡‖Φ⁡\(G\)−𝐜k‖22−τ\)\),\\alpha\(G\)=\\operatorname\{Sigmoid\}\\left\(\\gamma\\cdot\\left\(\\min\_\{k\}\\\|\\Phi\(G\)\-\\mathbf\{c\}\_\{k\}\\\|\_\{2\}^\{2\}\-\\tau\\right\)\\right\),whereγ=10\\gamma=10andτ\\tauis a trainable threshold initialized at the95th95^\{\\text\{th\}\}percentile of benign distances\.

## Appendix CExtended Experimental Settings

### C\.1\.Hardware and Hyperparameters

All models are implemented in PyTorch≥\\geq1\.12 with PyTorch Geometric\. Experiments were conducted on a cluster with NVIDIA RTX A5000 \(24GB VRAM\) and RTX 6000 Ada \(48GB\) GPUs\.

We use G\-Inception \(3 layers, 128 dimensional hidden layers\) as the target model for biochemical datasets and GraphSAGE \(3 layers\) for social datasets\. All models are optimized using Adam, with the reprogramming noise𝜹\\bm\{\\delta\}trained at learning rate1×10−31\\times 10^\{\-3\}and weight decay5×10−45\\times 10^\{\-4\}\. The query budget is set to20×20\\timesthe size of the benign training set for hard\-label attacks and10×10\\timesfor soft\-label attacks\.

Table A4\.Inference Time Comparison\.
### C\.2\.Inference Latency Analysis

A critical requirement for MLaaS defense is low latency\. As shown in Table[A4](https://arxiv.org/html/2608.11495#A3.T4), GraphRP incurs a marginal overhead of only≈7\.9%\\approx 7\.9\\%compared to the Undefended model \(56\.42s vs\. 52\.31s\)\. This slight increase is primarily due to the spectral decomposition inΦ⁡\(G\)\\Phi\(G\), which is computed once per graph\. In contrast, optimization\-based methods likeP\-Poisonare computationally prohibitive, requiring iterative gradient steps at test time that make them over8×8\\timesslower \(432\.17s\) than the baseline\. GraphRP’s efficient forward\-pass design ensures it remains compatible with real\-time applications\.

## Appendix DExtended Robustness and Transferability

### D\.1\.Adaptive Attack and Data Leakage

Defending against Adaptive Attackers\.As shown in Tables[3](https://arxiv.org/html/2608.11495#S6.T3)and[A3](https://arxiv.org/html/2608.11495#A1.T3), GraphRP remains robust against a gray\-box attacker \(using GraphGAN to mimic benign topology\([42](https://arxiv.org/html/2608.11495#bib.bib49)\)\), limiting clone accuracy to61\.5%61\.5\\%\(soft\-label\) and58\.8%58\.8\\%\(hard\-label\)—a negligible increase \(<1\.5%<1\.5\\%\) over the standard attack\. Notably, even when the attacker knows the defended architecture, clone accuracy stays below65%65\\%\.

### D\.2\.Cross\-Architecture Transferability

As shown in Table[A5](https://arxiv.org/html/2608.11495#A4.T5), GraphRP is architecture\-agnostic: layer\-wise reprogramming distorts the data manifold regardless of surrogate capacity, reducing extraction accuracy by over18%18\\%even against a powerful Graph Transformer\([10](https://arxiv.org/html/2608.11495#bib.bib50)\)\.

Table A5\.Defense Transferability \(MUTAG\)\.Clone accuracy across attacker architectures\. GraphRP’s poisoning effect holds even against Graph Transformers\.