PaperlayerView exact revision on arXiv

Source-linked AI summary

Dagger: Decoupling-based Model Stealing Attack against Graph Neural Networks

Ying Song, Xiaowei Jia, Balaji Palanisamy

arXiv:2609.37972v1cs.CRcs.AIcs.LG

TL;DR

GNN stealing is difficult to assess under realistic black-box restrictions, where queries provide hard labels and limited local graph access. Dagger combines decoupled propagation and manifold mixup with imbalance-aware classifier tuning. Across four benchmark graphs and four victim backbones, it achieves higher fidelity than the strongest baseline with fewer queries.

  • Problem

    Under strict black-box access, hard labels, limited queries, and sparse local graphs leave the surrogate needing to generalize from constrained supervision.

    Source: §I · p. 1, B. Problem Statement · p. 4

  • Method

    Dagger pre-trains with decoupled propagation and manifold-level node mixup, then tunes the classifier using class-balanced sampling and logit adjustment.

    Source: §I · p. 2, 1) Class-balanced Sampling (C3) · p. 7, 2) Logit Adjustment (C3) · p. 7

  • Results

    With 12.23× fewer queries than the strongest baseline, Dagger achieves up to 18.16% higher fidelity across four benchmark graphs and four victim backbones.

    Source: §I · p. 2

  • Takeaways & Limitations

    Dagger’s evaluations show it bypasses query-monitoring and watermarking defenses, motivating defenses tailored to realistic GNN stealing threats.

    Source: §I · p. 2, §VI · p. 13

Abstract

from arXiv · show

As Graph Neural Networks (GNNs) are widely deployed as Machine Learning-as-a-Service (MLaaS) APIs, model stealing attacks have emerged as a critical security threat. By querying a victim model's black-box API, an adversary can construct a functionally equivalent surrogate model, compromising proprietary intellectual property and downstream security. Existing GNN stealing attacks, however, rely on overly permissive assumptions, such as soft-label outputs, large query budgets, full-graph query access, and prior knowledge of victim backbones that rarely hold in real-world deployments. In this work, we formalize a strictly constrained black-box, hard-label and backbone-agnostic threat model for GNN stealing attacks under a tight query budget. Given these realistic restrictions, we identify four fundamental challenges: sparse local structures and isolated nodes that degrade victim label quality, insufficient supervision signals, systematic imbalance with incomplete class coverage, and backbone mismatch. To address these interlocking barriers, we propose Dagger, a novel two-phase decoupling-based attack framework. Specifically, in Phase 1, Dagger pre-trains a surrogate using decoupled information propagation to preserve structural context over sparse local subgraphs while handling isolated nodes, combined with manifold-level node mixup to synthesize continuous supervision signals and smooth decision boundaries. In Phase 2, Dagger freezes the encoder and fine-tunes the classifier head via class-balanced sampling paired with logit adjustment to rectify severe query imbalance without requiring extra victim queries. Extensive experiments across four benchmark graphs and four GNN backbones demonstrate that Dagger consistently outperforms state-of-the-art GNN stealing attacks, achieving up to 18.16\% higher fidelity while only utilizing 12.23$\times$ fewer queries than the strongest baseline.

I. INTRODUCTION

Dagger targets GNN stealing under strict black-box, hard-label, backbone-agnostic access and a tight query budget. It pairs decoupled propagation and manifold-level mixup with imbalance-aware classifier tuning, and reports higher fidelity with fewer queries than the strongest baseline.

I. INTRODUCTION

  • GNN stealing can compromise proprietary intellectual property, and stolen models can support downstream attacks.The paper names backdoor injection, privacy inference, and other inference attacks as examples.Source: §I · p. 1
  • Dagger formalizes a strict black-box, hard-label, backbone-agnostic threat model with a tight query budget and queries restricted to local induced subgraphs.The paper identifies sparse structures and isolated nodes, insufficient supervision, class imbalance and incomplete coverage, and victim-backbone mismatch as challenges in this setting.Source: §I · pp. 1–2
  • Dagger uses decoupled propagation and manifold-level node mixup in pre-training, then tunes a frozen encoder’s classifier with class-balanced sampling and logit adjustment.The phases address sparse local structures and isolated nodes, hard-label supervision, and query-induced class imbalance without extra victim queries.Source: §I · p. 2
  • With 12.23× fewer queries than the strongest baseline, Dagger achieves up to 18.16% higher fidelity across four benchmark graphs and four victim backbones.With the same query budget, it outperforms the other baselines by up to 45.27% in fidelity, particularly on sparse and class-imbalanced graphs.Source: §I · p. 2

A. Node Classification

  • GNNs aggregate information from a node’s local neighborhood to update its embedding, which is then fed to a classifier for node prediction.The paper describes this as the general node-classification pipeline for GNNs.Source: A. Node Classification · p. 2

B. Model Stealing Attacks against GNNs

Prior GNN stealing approaches often assume richer outputs, broader graph access, larger budgets, or knowledge of the victim backbone. This section contrasts those approaches with a constrained hard-label setting and defines the adversary’s goals and capabilities.

B. Model Stealing Attacks against GNNs

  • Prior attacks face limits including reliance on soft labels or extensive graph access, high query costs and detection risk, victim-backbone assumptions, and inconsistent evaluations.Some implementations query the full graph despite claiming restricted access; the paper argues this can inflate reported performance.Source: B. Model Stealing Attacks against GNNs · pp. 2–3

1) Attack Goals:

  • The adversary pursues theft by matching the victim’s task accuracy and reconnaissance by reproducing its predictions, measured with fidelity.For reconnaissance, the ideal surrogate agrees with the victim even when both predict incorrectly.Source: 1) Attack Goals · p. 3

2) Attacker’s Knowledge and Capabilities:

  • The threat model allows only black-box hard-label responses, without victim parameters, backbone knowledge, architecture, training procedures, or intermediate representations.Queries use target nodes and their induced subgraph rather than the full graph or complete multi-hop neighborhoods.Source: 2) Attacker’s Knowledge and Capabilities · p. 3
  • The query budget is limited to 5% of the victim training graph, and data synthesis to expand queries is prohibited.The paper states that queries use real training nodes, making them indistinguishable from legitimate usage.Source: 2) Attacker’s Knowledge and Capabilities · p. 3

3) Attack Scenarios:

The paper describes commercial model theft, low-footprint adversarial transfer, and intellectual-property auditing as attack scenarios. Its problem statement restricts the adversary to a small target-node set and asks the surrogate to generalize beyond queried nodes.

3) Attack Scenarios:

  • The proposed scenarios are commercial GNN API theft, extracting a surrogate before crafting transferable adversarial examples, and auditing model vulnerability or unauthorized IP infringement.The transfer scenario is framed as operating under a strict query budget to evade rate-limiting and anomaly defenses.Source: 3) Attack Scenarios · pp. 3–4

B. Problem Statement

  • The adversary’s access is limited to a target-node set, with graph access ratio β set to 5%, and queries use local subgraphs within the induced subgraph.The induced subgraph may be largely unconnected and contain many isolated nodes.Source: B. Problem Statement · p. 4
  • From query-response pairs, the adversary trains a surrogate to match ground-truth and victim-predicted labels on unseen nodes, despite sparse, small-scale query graphs and hard labels.The surrogate must generalize beyond the queried nodes using supervision from potentially sparse and small-scale induced subgraphs.Source: B. Problem Statement · p. 4

C. Empirical Studies

The studies show that restricted local queries can lower victim-label quality and produce severe class imbalance, creating unreliable and incomplete supervision for a surrogate.

1) Label Quality Degradation:

  • On sparse Cora and PubMed, expanding from isolated nodes to induced subgraphs does not consistently improve label accuracy; 2-hop labels can be worse than isolated-node labels.Noisy neighbors from different classes can distort victim predictions.Source: 1) Label Quality Degradation · p. 4, Figure 1 · p. 4
  • Sparse induced subgraphs and isolated nodes degrade standard GNN representations, while hard-label queries provide insufficient and noisy supervision for surrogate generalization.The resulting query-response pairs are informationally limited and can distort decision boundaries.Source: 1) Label Quality Degradation · pp. 4–5

2) Class Imbalance and Absence:

  • Victim predictions amplify class imbalance on Cora and Computer, reaching imbalance ratios of 45× and 70×, respectively, for GAT; APPNP on Cora omits class 6.PubMed remains relatively balanced, with victim imbalance ratios slightly below ground-truth baselines across backbones.Source: 2) Class Imbalance and Absence · p. 5

3) Backbone Disagreement:

Backbone predictions diverge more on sparse induced subgraphs, motivating Dagger’s backbone-agnostic, two-phase framework and topology-adaptive surrogate.

3) Backbone Disagreement:

  • Backbone prediction agreement falls on sparse induced subgraphs, reaching 0.51 for isolated nodes on Computer, and rises as topology expands toward the full graph.The study identifies topology as the primary driver of backbone divergence.Source: 3) Backbone Disagreement · p. 5, Figure 3 · p. 5

IV. ATTACK FRAMEWORK DESIGN

  • Dagger addresses the four identified challenges in two phases: decoupled propagation and manifold mixup in Phase 1, then balanced sampling and logit adjustment in Phase 2.The framework avoids assuming prior knowledge of the victim backbone.Source: §IV · pp. 5–6

1) Topology-adaptive Surrogate (C1):

  • The topology-adaptive surrogate first transforms node features independently of local topology, then propagates representations with PPR while retaining the original representation to limit over-smoothing.Explicit self-loops support stable propagation for isolated nodes.Source: 1) Topology-adaptive Surrogate (C1) · p. 6

3) Manifold

Manifold-level node mixup addresses sparse hard-label supervision by interpolating latent representations and pairing them with soft labels.

3) Manifold

  • Sparse query responses may omit classes, and hard labels discard inter-class relationships, while training on limited supervision can produce spurious decision boundaries.These boundaries hinder generalization to unseen nodes.Source: 3) Manifold · pp. 6–7
  • Manifold-level node mixup interpolates continuous latent representations to smooth decision boundaries without assigning semantic meaning to mixtures of sparse, discrete input features.The latent space carries structural context from PPR propagation.Source: 3) Manifold · p. 7
  • The method mixes representations from query nodes with different predicted labels using a uniformly sampled interpolation weight and trains them against paired soft labels.The soft labels are formed from the two classes’ one-hot vectors and complement relationships omitted by hard-label supervision.Source: 3) Manifold · p. 7

B. Phase 2: Imbalance-aware Classifier Tuning

Phase 2 addresses residual classifier bias after pretraining by freezing the encoder and tuning only the linear classifier head.

B. Phase 2: Imbalance-aware Classifier Tuning

1) Class-balanced Sampling (C3):

Dagger addresses skewed query labels by rebalancing classifier training and correcting the prior shift this creates. These Phase 2 components are designed to complement one another.

1) Class-balanced Sampling (C3):

  • Minority classes are oversampled with replacement until each class contributes as many nodes per epoch as the majority class.This counters majority-class dominance in the query-response pairs.Source: 1) Class-balanced Sampling (C3) · p. 7

2) Logit Adjustment (C3):

  • Logit adjustment calibrates classifier logits using victim-predicted class priors, without requiring additional victim queries.Class-balanced sampling equalizes per-class gradient contributions, while logit adjustment restores calibration at inference after rebalancing shifts the class prior.Source: 2) Logit Adjustment (C3) · p. 7

V. EXPERIMENTS

  • The experiments examine attack effectiveness, backbone adaptation, architecture mismatch, performance factors, component contributions, and defense bypass.These are the six research questions listed for the experimental section.Source: §V · pp. 7–8

A. Setups

Dagger is evaluated against stealing baselines under a shared access setting, with results on effectiveness, query use, and sensitivity to surrogate architecture and manifold coefficient.

A. Setups

  • The evaluation compares four GNN backbones and several stealing baselines, including synthetic-graph, active-learning, and induced-subgraph approaches.The baselines are evaluated with access to 5% of the victim training graph; some rely on higher query budgets or global information unavailable in practice.Source: A. Setups · p. 8

1) Effectiveness:

  • At similar query counts, Dagger improves accuracy by up to 43.17% and fidelity by up to 45.27% over state-of-the-art baselines.The table covers Cora and Computer; Dagger also surpasses or matches MEA despite MEA usually submitting 3.87–12.23× more queries.Source: Table II · p. 8, 1) Effectiveness · p. 8

2) Efficiency:

  • Dagger uses 5% of the graph’s nodes as queries, and its query count equals its accessible-node count; MEA typically uses 3.87–12.23× more queries.Lower query footprint reduces the risk of detection by query-monitoring defenses.Source: 1) Effectiveness · p. 8, 2) Efficiency · p. 9

1) GNN Architectures:

  • Across tested architectures, performance varies by about 1–4%; the default [2] [16] configuration is comparable to larger models.Increasing depth or hidden dimension provides little benefit under the 5% query budget.Source: 1) GNN Architectures · p. 9
  • Dagger is robust across manifold coefficients from 0.1 to 2.0, though sensitivity differs by dataset and victim backbone.Fluctuations are nearly flat on Physics and PubMed, while Cora and Computer show more variation; the authors tune the coefficient for each graph-backbone combination.Source: 1) GNN Architectures · p. 9

3) Query Budget:

Query-budget tests show improved attack performance as more nodes are queried, while ablations indicate that manifold mixup and classifier tuning matter most in difficult, imbalanced settings.

3) Query Budget:

  • From 1% to 20% query budgets, Dagger’s performance consistently improves; gains diminish beyond 10% on most datasets.At 1%, Physics and PubMed already show competitive performance, while Cora and Computer improve more from 1% to 5%.Source: 3) Query Budget · p. 9, Figure 8 · p. 11

5) Ablation Studies:

  • Removing manifold mixup degrades performance most noticeably on Cora and Computer, while drops are less pronounced on PubMed and Physics.The latter graphs have larger, more balanced query sets, denser structure, and smaller class spaces, making mixup less critical.Source: 5) Ablation Studies · pp. 9, 11
  • Removing logit adjustment causes persistent drops, especially on imbalanced Cora and Computer; its contribution is smaller but measurable on PubMed and Physics.When query labels are balanced, applying logit adjustment may overfit and slightly reduce performance.Source: 5) Ablation Studies · p. 11
  • Omitting all classifier tuning substantially degrades performance on Cora and Computer and performs worse than removing logit adjustment alone under severe imbalance.The full model achieves the best or near-best performance in most graph-backbone combinations.Source: 5) Ablation Studies · pp. 9, 11

D. Defense (RQ6)

Dagger remains effective under the evaluated query-monitoring and watermarking defenses. The paper identifies near-zero minority-class coverage and further query reduction as open limitations and directions.

D. Defense (RQ6)

  • Against both PRADA and BackdoorWM, Dagger’s attack performance remains comparable to the undefended setting across datasets and victim backbones.PRADA initially treats queries as legitimate before later corrupting some labels; BackdoorWM’s fidelity drops to 76.75%–99.25%, yet it does not degrade surrogate functional quality.Source: D. Defense (RQ6) · p. 12
  • Near-zero-coverage minority classes remain a fundamental limitation; future work should allocate query budgets more effectively to address them.The authors also identify further query reduction, heterogeneous graphs, and robust defenses as future directions.Source: D. Defense (RQ6) · p. 12

VI. CONCLUSION

  • The conclusion reports that Dagger outperforms state-of-the-art baselines across diverse graph datasets and victim backbones, and resists query-monitoring and backdoor-watermarking defenses.The paper calls for more robust GNN defenses.Source: §VI · pp. 12–13

OPEN SCIENCE

  • The authors release code, implementation details, and an evaluation pipeline to reproduce experiments and conduct attacks.The datasets are downloadable from PyTorch Geometric, and processing scripts are provided.Source: OPEN SCIENCE · p. 13

ETHICAL CONSIDERATIONS

  • Experiments use public graph datasets on local devices and do not interact with third-party systems, collect personal data, or involve human subjects.The release excludes components intended to enable large-scale exploitation beyond the described experimental setup.Source: ETHICAL CONSIDERATIONS · p. 13

APPENDIX

The appendix specifies training and evaluation settings, reports benign victim performance, and examines how query balance relates to attack outcomes and data properties. It also includes ablations across datasets and backbones.

A. Implementation

  • Experiments use 80/10/10 splits, restrict node selection to training nodes, and report averages over three trials.Victim GNNs use a learning rate of 0.001, 16 hidden dimensions, and two layers; Adam is used for optimization.Source: A. Implementation · p. 14

B. Benign GNN Performance

D. Balance and Its Impact Factors

  • The balance study constructs four Cora query-set distributions, from very imbalanced to balanced, while keeping the total query budget fixed.Largest-remainder allocation distributes any remaining query nodes after integer class quotas are assigned.Source: D. Balance and Its Impact Factors · p. 14
  • Under high imbalance, class-balanced sampling with logit adjustment has its largest performance gap; the settings converge as query distributions become more uniform.At higher balance levels, rebalancing may provide only marginal benefit and can sometimes slightly degrade performance.Source: D. Balance and Its Impact Factors · p. 15
  • Label accuracy, isolated-node ratio, and average degree vary with balance in victim-specific, non-monotonic ways, so balance alone does not predict label quality or structural richness.Source: D. Balance and Its Impact Factors · p. 15

E. Ablation Studies

  • The appendix includes ablations across graph datasets and GNN backbones, alongside a figure on balance-level sensitivity and other factors.Source: Table VII · p. 15, Figure 9 · p. 16

Related papers

Loading 2609.37972v1…