Model Extraction Attacks on Graph Neural Networks: Taxonomy and Realization

1 INTRODUCTION

• The paper identifies GNN extraction as an unresolved threat: prior extraction work targets non-graph models, while GNNs are used in commercial and public-API settings.The introduction notes that trained models are costly to build and may be treated as owners’ intellectual property.Source: §1 · pp. 1–2
• GNN extraction must account for graph structure because node predictions depend on both node attributes and connections, unlike predictions for non-graph inputs.Attackers may lack some training-graph knowledge, making existing strategies that omit structure unsuitable for direct use.Source: §1 · p. 2
• The threat framework distinguishes seven attack types by access to node attributes, attack-node graph structure, and an auxiliary shadow subgraph.Adaptive strategies synthesize attributes when structure is known but attributes are missing, and generate surrogate structure when the known graph is fragmented.Source: §1 · p. 2
• More than 85% of duplicated-model predictions match the target across evaluations on three real-world datasets.Most duplicated models also achieve nearly equal accuracy to the target.Source: §1 · p. 2

2 RELATED WORK

• Prior model-extraction studies reconstruct conventional ML models from prediction queries, including linear models, decision trees, neural networks, and knockoff models.Examples include Tramèr et al.’s API-based reconstruction, Milli et al.’s gradient-based method [33], Pal et al.’s active learning [37], and Orekondy et al.’s knockoff model.Source: §2 · p. 2
• Output hiding or noise may be less effective against label-based extraction, while query-monitoring defenses do not account for GNN structure.The passage names output defenses [4] and monitoring approaches.Source: §2 · p. 2
• Most cited GNN attacks target integrity, while confidentiality studies infer graph membership or links rather than extracting the GNN model itself.The paper distinguishes its goal from membership inference and link stealing [20].Source: §2 · p. 3

3 PRELIMINARIES

• A node-classification model assigns labels to graph nodes using both their features and the graph structure.For a well-trained model, the predicted label is expected to match the corresponding ground-truth label.Source: §3 · p. 3
• The paper uses a two-layer GCN whose convolution layers aggregate attribute information from neighboring nodes.The GCN equation uses normalized adjacency; the adjacency is augmented with self-loops before normalization.Source: §3 · p. 3
• For extraction of the target GCN, the stated reconstruction goal is to recover its two layer-weight matrices.The matrices are denoted W^(0) and W^(1).Source: §3 · p. 3

4.1 Adversary’s Goal

• The attacker reconstructs a surrogate from query input-output pairs; success means target-like accuracy or predictions, not identical model parameters or structure.The formal goal is for surrogate predictions to approximate the target across graph nodes.Source: §4.1 · p. 3

4.2 Adversarial Knowledge

• The black-box threat model varies attacker knowledge of node attributes, target-graph connections, and a same-domain shadow graph.The attacker may know attributes only for compromised attack nodes; model parameters, labels, and output probabilities remain unknown.Source: §4.2 · pp. 3–4

4.3 Attack Taxonomy

• Seven attacks cover combinations of the three knowledge dimensions, including settings with attack-node attributes, connections, or a shadow graph.Attack-0 assumes partial attack-node attributes and neighbor connections but no shadow dataset; other settings vary which of these resources are available.Source: §4.3 · p. 4
• In Attack-0, query responses and two-hop neighbor connections support synthesizing attributes, and the resulting graph is used to train the duplicate model semi-supervisedly.The training data combine attack nodes with known attributes and labels and synthetic nodes with generated attributes.Source: Figure 2 · p. 5, §4.3 · p. 5
• Attack-5 combines attack-node attributes with a shadow graph, while Attack-6 combines connections with a shadow graph; the all-unknown setting is excluded.With no input graph or task domain and only final prediction labels exposed, the attacker cannot readily link inputs to outputs; the paper leaves this case open.Source: §4.3 · p. 5

5.1 Attack-0

• Attack-0 uses queried attack-node labels and known neighborhood connections, synthesizes inaccessible neighbors’ features from 1-hop and 2-hop neighbors, then trains semi-supervised because only attack nodes are labeled.An adjustment factor balances the 1-hop and 2-hop contributions.Source: §5.1 · pp. 5–6

5.2 Attack-1

• Attack-1 generates a substitute graph from known attack-node attributes using LDS, then trains the duplicated model with supervised learning.The generated graph approximates the target edge distribution so most nodes are not isolated.Source: §5.2 · p. 6, Figure 3 · p. 7

5.3 Attack-2

• Attack-2 uses the known full graph and query labels but replaces unavailable node attributes with index-based one-hot vectors for semi-supervised training.The resulting model can classify all nodes in the target graph.Source: §5.3 · pp. 6–7, Figure 4 · p. 7

5.4 Attack-3

• Attack-3 trains a surrogate on a same-domain shadow graph and uses its weights as the extracted model, relying on matching attribute dimensions.The stated similar functionality depends on the target and shadow graphs being in the same domain.Source: §5.4 · p. 7

5.5 Attack-4

• Attack-4 combines an Attack-0 graph with a shadow graph as isolated components, training on their known structures, attributes, and labeled nodes without synthesizing cross-graph connections.The components are kept separate because the attack nodes are often not connected to the shadow graph.Source: §5.5 · p. 7

5.6 Attack-5

• Attack-5 combines an attribute-based generated graph for target attack nodes with a separate shadow graph, again leaving the two components unconnected.The first graph uses the Attack-1 strategy; the shadow graph supplies the second component.Source: §5.6 · p. 8

5.7 Attack-6

• Attack-6 trains Attack-2 and Attack-3 models separately, then feeds their posteriors to an MLP attack model trained on shadow-graph outputs to produce final labels.The one-hot attributes in Attack-2 have a dimension tied to node count, which does not match the original attributes.Source: §5.7 · p. 8

6.1 Experimental Setup

• The experiments use Cora, Citeseer, and Pubmed, with separate target and shadow graphs for Attacks 3–6 and a two-layer GCN target model.For Attacks 0–2, the target models are trained on the entire graph; for Attacks 3–6, target and shadow graphs are split from the network.Source: §6.1 · pp. 8–9

6.2 Attack Performance

• Most attacks achieve about 80% fidelity and accuracy nearly equal to the target model across the evaluated settings.Attack-0 has the highest fidelity; the overview uses about 25% attack nodes for Attacks 0–2 and a shadow graph nearly the target’s size plus about 10% attack nodes for Attacks 3–6.Source: §6.2 · p. 9, Table 4 · p. 9
• With attack nodes increasing from 5% to 25%, Cora accuracy reaches about 79.9% against the target’s 81.5%, and fidelity reaches about 90%.On Citeseer, accuracy rises from 59.9% to 67.0%; at about 25% attack nodes it is close to the 70.0% baseline and fidelity is 82.8%. Pubmed accuracy rises from 70% to 73%.Source: §6.2 · pp. 9–10, Figure 5 · p. 10
• Synthesising attack-node neighbours improves fidelity, but too many synthetic neighbours hurt performance; first-order synthesis most closely matches the target feature distribution.The distribution comparison contrasts first-order-only synthetic neighbours with first- and second-order neighbours.Source: §6.2 · p. 10, Figure 6 · p. 10, Table 5 · p. 11
• For Attack-0, increasing adjustment factor α raises performance on Cora and Citeseer, while its effect is mostly within ±5% and Pubmed performance fluctuates.Larger α weights synthetic attributes more toward one-hop neighbours.Source: §6.2 · p. 10, Figure 7 · p. 10
• For Attack-1, generating graph structure from node features improves fidelity over a feature-only DNN baseline, from 59.0% to 82.5%.On Cora, the extracted model’s accuracy is about 79.8% versus 57.7% for DNNs.Source: §6.2 · p. 11, Table 6 · p. 11
• Attack-2 performs worst among Attacks 0–2 because its synthetic node attributes are one-hot vectors unlike the target’s attributes; access to attribute knowledge could improve performance.Attacks 0–2 also gain accuracy and fidelity as the number of attack nodes increases.Source: §6.2 · p. 11
• With a larger shadow graph, Attack-3 accuracy increases while fidelity saturates; adding target-graph attack nodes improves Attack-4 over Attack-3, especially in fidelity on Citeseer and Pubmed.Attack-5 is slightly better than Attack-3 and nearly matches Attack-4, while Attack-6 outperforms Attack-2 and is comparable to Attacks 4 and 5; Attack-6’s performance changes little with more attack nodes because its ensemble relies more on the stronger Attack-3 component.Source: §6.2 · pp. 11–12, Figure 8 · p. 11, Figure 9 · p. 12

• The paper combines legitimate-looking queries and accessible structure knowledge to build surrogate GNNs across seven threat models, with experiments showing predictions similar to the targets.The authors identify defence against GNN extraction as future work, including extending query monitoring and filtering with structure analysis.Source: §7 · p. 12

• Using attack nodes with their one- or two-hop neighbours can significantly synthesise the target graph’s degree distribution, supporting neighbour-attribute synthesis when those attributes are inaccessible.Figure 10 compares the total target graph, attack nodes with one- or two-hop neighbours, and attack nodes alone.Source: §A.1 · p. 14, Figure 10 · p. 14

• Applying graph-structure generation makes the synthesised degree distribution more similar to the target, benefiting extraction attacks.Figure 11 compares the target graph, attack nodes with synthetic edges, and attack nodes alone.Source: §A.2 · p. 14, Figure 11 · p. 14