Defending against Model Extraction for GNNs with Model Reprogramming

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 propose GraphRP (Graph Reprogramming Protection), a proactive defense framework that repurposes Model Reprogramming for 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.

The paper addresses the central research question: 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? The 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 of learnable, layer-wise perturbations that act as a structural firewall. Crucially, the Structure-Aware Gating Mechanism dynamically modulates these perturbations based on the topological signature of the input graph. By learning benign structural prototypes, the method ensures that defensive noise is only activated when the query distribution deviates from the benign distribution (OOD), thereby preserving utility for benign users.

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

The methodology introduces two key components into the standard message-passing backbone: (1) Layer-Wise Reprogramming, which injects learnable, task-specific perturbations into the latent node embeddings, allowing manipulation of the model's output distribution without retraining the original weights; and (2) Structure-Aware Gating, a dynamic control module that assesses the structural legitimacy of an input graph by computing a gating factor alpha ∈ [0, 1] to modulate the reprogramming intensity. The pipeline operates in two modes: Benign Mode (alpha → 0) where reprogramming noise is suppressed for inputs matching the training distribution, preserving high utility; and Defense Mode (alpha → 1) where the gating mechanism activates the reprogramming layers for suspicious OOD inputs, subtly distorting outputs to maximize divergence from the true decision boundary, effectively poisoning the attacker's surrogate training data.

The Layer-Wise Reprogramming uses a Universal Reprogramming Prototype delta(l) ∈ Rdl for each layer, broadcasted to all nodes. The reprogrammed layer output is formulated as H̃(l) = H(l) + lambda · Tanh(delta(l)), where Tanh ensures the perturbation remains bounded. The Structure-Aware Prototype Gating maps the input graph to a permutation-invariant structural embedding zG using a lightweight Readout function Φ(·) that aggregates node degrees, clustering coefficients, and spectral features (top-k Laplacian eigenvalues). A set of K centroids ck initialized via K-Means on Did represents the structural clusters of the private in-distribution data. The gating factor is calculated as alpha(Gq) = Sigmoid(gamma · (dmin − tau)), where dmin is the distance to the nearest benign prototype and tau is a learnable distance threshold. The final reprogramming equation becomes H̃(l) = H(l) + alpha(G) · lambda · Tanh(delta(l)), ensuring defensive noise is strictly conditional on the structural foreignness of the query.

The defensive optimization uses a total objective function L that is a weighted combination of three terms: (1) Utility Preservation (Ltask) minimizing standard Cross-Entropy loss on the private training set Did; (2) Extraction Defense (Ldefense) maximizing the KL divergence between the reprogrammed model's output and the original model's output for OOD queries, using a hinge loss formulation with margin mu; and (3) Structural Compactness (Lstruct) minimizing the distance between ID samples and their nearest prototype to create tighter clusters for benign data. The final optimization problem is Θ∗rep = arg min (Ltask + beta1 · Ldefense + beta2 · Lstruct), where beta1 and beta2 are hyperparameters controlling defense strength and structural clustering. The original model parameters thetaT are frozen to ensure parameter efficiency.

The theoretical analysis provides a Structural Defense Bound (Theorem 5.1): Let C∗ be the optimal clone model trained on OOD queries reprogrammed by GraphRP. Under the cross-entropy loss, the performance gap between the clone and the victim on benign tasks is lower-bounded by: Q(C∗,T) ≥ EG∼Good [1/2 · alpha(G)2 · delta˜⊤ Ih(G) delta˜] − 2M · TV(Gid, Good), where alpha(G) is the structure-aware gating factor, delta˜ = lambda·Tanh(delta) is the effective bounded perturbation, and Ih(G) is the Fisher Information Matrix of the victim GNN with respect to the latent representation h. The term delta˜⊤ Ih(G) delta˜ captures the structural sensitivity of the GNN, which is largest when the reprogramming noise aligns with high-curvature directions of the model.

Experiments evaluate on diverse graph classification benchmarks including MUTAG, ENZYMES, PROTEINS, NCI1, OGB-MolHIV, and COLLAB. Baselines include RandP (Random Perturbation), P-Poison, GRAD (Gradient Redirection), AM (Adaptive Misinformation), and MeCo (contrastive defense). The attack configuration employs KnockoffNet as the query strategy, with surrogate models including GraphSAGE, Graph Isomorphism U-Net (GIUNET), and Gaussian-Induced Convolution (GIC), using either soft-label or hard-label supervision.

Results show GraphRP consistently achieves the lowest clone accuracy across all scenarios. For instance, on MUTAG under soft-label attack, the method reduces clone accuracy from 76.5% (Undefended) to 60.3%, significantly outperforming the best baseline (MeCo at 71.2%). GraphRP achieves the strongest defense while incurring less than 2% utility loss, whereas baseline methods suffer a substantially larger utility-defense trade-off. The Structure-Aware Gating mechanism effectively distinguishes benign from adversarial queries (AUROC > 0.91, FPR < 0.06). The additional latency is marginal (≈ 7%) compared to heavy matrix multiplications in the GNN backbone.

Robustness analysis shows GraphRP remains effective even against adaptive attackers using a Structural Generator (based on GraphGAN) trained to mimic benign topological statistics, limiting clone accuracy to 61.5% (soft-label) and 58.8% (hard-label) on MUTAG. When the attacker gains access to 10% ID data, clone accuracy increases by only 3.2% (vs. 5.2% for Undefended). On large-scale benchmarks (OGB-MolHIV and COLLAB), GraphRP achieves the lowest clone accuracy while maintaining high benign utility. Under unlimited query budgets, GraphRP saturates at a low level (≈ 55% on NCI1), indicating that reprogramming noise fundamentally poisons the decision boundary. Ablation studies confirm that Spectral Features are the most critical component for OOD detection: removing them increases clone accuracy from 0.603 to 0.685, while removing degree statistics has only minor impact.

Improvements to AI Systems:

1. Structural Firewall for GNN-Based MLaaS APIs

The improved AI system can actively defend against model extraction attacks by injecting learnable, layer-wise perturbations into latent node embeddings, gated by a Structure-Aware Gating Mechanism. It distinguishes benign queries (on-manifold) from adversarial OOD queries (off-manifold) using topological prototypes (spectral features, degrees, clustering coefficients), preserving >98% benign utility while degrading clone accuracy by up to 17%—without retraining the victim model.

2. Dynamic Conditional Perturbation via Topological Prototype Gating

The system can compute a gating factor α ∈ [0,1] based on the distance of an input graph to learned benign structural centroids. For benign queries, α→0 (no noise, full fidelity); for adversarial queries, α→1 (maximal reprogramming). This enables real-time, query-specific defense with only 7% added latency, unlike static noise injection that harms all users.

3. Fisher Information-Guided Defense Optimization

The system can maximize the attacker’s estimation error by aligning reprogramming noise with high-curvature directions of the victim GNN’s loss landscape (via Fisher Information Matrix). This theoretically guarantees a lower bound on clone model performance degradation, making the defense robust even against adaptive attackers that mimic benign graph statistics (e.g., GraphGAN-based generators).

4. Utility-Preserving OOD Detection for Graphs

The system can serve as a built-in OOD detector for graph-structured data, achieving AUROC >0.91 and FPR <0.06 on distinguishing extraction queries from benign ones. This capability can be repurposed for anomaly detection, fraud detection, or out-of-distribution sample rejection in production GNN pipelines.

5. Parameter-Efficient, Retraining-Free Security Layer

The system can be deployed as a plug-and-play module on top of any frozen GNN backbone (e.g., GraphSAGE, GIN, GIC), requiring only training of the reprogramming prototypes and gating centroids. This avoids costly full-model retraining, making it suitable for rapid deployment in MLaaS environments with limited compute budgets.

6. Scalable Defense for Large-Scale Graph Benchmarks

The improved system can maintain defense effectiveness on large graphs (e.g., OGB-MolHIV, COLLAB) with thousands of nodes, showing saturated clone accuracy (55%) even under unlimited query budgets. This ensures long-term protection against persistent attackers who attempt to exhaust the API.

7. Adaptive Robustness Against Data Leakage

The system can limit the impact of partial training data leakage (e.g., attacker obtains 10% of ID data), increasing clone accuracy by only 3.2% (vs. 5.2% for undefended models). This makes it resilient to insider threats or accidental data exposure.

8. Interpretable Defense via Structural Compactness

The system can learn tighter clusters for benign data (via L struct loss), providing an interpretable measure of “graph normality.” This allows operators to audit which structural features (e.g., spectral eigenvalues) are most critical for defense, enabling feature-level insights into attack vectors.

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 propose GraphRP (Graph Reprogramming Protection), a proactive defense framework that repurposes Model Reprogramming for 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.