PaperlayerView exact revision on arXiv

Source-linked AI summary

Stealing Links from Graph Neural Networks

Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, Yang Zhang

arXiv:2005.02131v2cs.CRcs.LG

TL;DR

Graphs can contain costly intellectual property and sensitive relationships, yet the privacy and security implications of training GNNs on them are largely unexplored. The paper proposes black-box link stealing attacks organized by three adversary-knowledge dimensions, and evaluates them across real-world datasets, finding effective link inference. Its results indicate that GNN outputs reveal rich information about training-graph structure.

  • Problem

    Graphs may be costly to collect or contain sensitive relationships, while the security and privacy implications of training GNNs on graphs remain largely unexplored.

  • Method

    The paper proposes black-box link stealing attacks, a three-dimensional threat model, and 8 attack methods using target attributes, partial graphs, or shadow datasets.

  • Results

    The attacks effectively steal links across 8 real-world datasets; Attack-6 achieves average AUC scores over 0.95 on 7 of 8 datasets.

  • Takeaways & Limitations

    GNN posteriors reveal rich information about the structure of the graph used to train the model.

  • Takeaways & Limitations

    The paper identifies differential privacy and adversarial-example defenses as future work to mitigate the attacks.

Abstract

from arXiv · show

Graph data, such as chemical networks and social networks, may be deemed confidential/private because the data owner often spends lots of resources collecting the data or the data contains sensitive information, e.g., social relationships. Recently, neural networks were extended to graph data, which are known as graph neural networks (GNNs). Due to their superior performance, GNNs have many applications, such as healthcare analytics, recommender systems, and fraud detection. In this work, we propose the first attacks to steal a graph from the outputs of a GNN model that is trained on the graph. Specifically, given a black-box access to a GNN model, our attacks can infer whether there exists a link between any pair of nodes in the graph used to train the model. We call our attacks link stealing attacks. We propose a threat model to systematically characterize an adversary's background knowledge along three dimensions which in total leads to a comprehensive taxonomy of 8 different link stealing attacks. We propose multiple novel methods to realize these 8 attacks. Extensive experiments on 8 real-world datasets show that our attacks are effective at stealing links, e.g., AUC (area under the ROC curve) is above 0.95 in multiple cases. Our results indicate that the outputs of a GNN model reveal rich information about the structure of the graph used to train the model.

1 Introduction

Graphs can encode valuable intellectual property and sensitive relationships, while GNNs increasingly analyze them in applications including healthcare, recommender systems, and fraud detection. This paper introduces link stealing attacks, a threat model spanning three knowledge dimensions, and evaluation showing that links can be effectively inferred from black-box GNN outputs.

  • Motivation: Graphs may be costly to collect and can contain sensitive relationships, making their structure confidential or private.Examples include experimentally collected chemical networks and private social relationships.
  • Background: GNNs analyze graphs for node classification and have growing applications in healthcare analytics, recommender systems, and fraud detection.The security and privacy implications of training GNNs on graphs remain largely unexplored.
  • Contributions: The paper proposes the first link stealing attacks, which use black-box GNN access to predict whether pairs of training-graph nodes are linked.The attacks raise concerns about graph intellectual property, confidentiality, and privacy.
  • Threat model: The threat model varies adversary knowledge across three dimensions and yields 8 link stealing attacks.The dimensions concern node attributes, a partial target graph, and an auxiliary shadow dataset.
  • Evaluation: 8 real-world datasets are used to evaluate the attacks, which the experiments show can steal links effectively.The evaluation is described as extensive across the attack set and datasets.

2 Graph Neural Networks

A GNN combines graph structure and node attributes to update node representations and predict labels. In particular, GCN layers use normalized adjacency-based neighbor aggregation, and the resulting node posteriors can reveal graph structure.

  • Background: Graphs represent complex relationships in domains such as social, knowledge, and chemical networks, motivating GNN-based analysis.GNNs have been proposed for exploiting graph data and show superior performance across tasks.
  • GNN formulation: A target dataset is D = (A,F), where A is the graph adjacency matrix and F contains node attributes.An adjacency entry A_uv indicates whether an edge exists between nodes u and v.
  • GNN formulation: GNNs iteratively update node features by aggregating neighboring features through neural-network layers whose final layer predicts node labels.Different GNN methods use different aggregation rules.
  • GCN: GCN propagation uses the adjacency matrix with self-connections, symmetric normalization, trainable layer weights, and an activation function.Here, ˜A = A + I, and σ introduces non-linearity such as ReLU.
  • GCN: For a two-layer GCN, node attributes are transformed through two normalized propagation layers to produce predictions.The paper focuses mainly on two-layer GCNs but later considers GraphSAGE and GAT.
  • Prediction: A trained GNN returns a posterior distribution for a queried node, and these posteriors reveal information about graph structure.The attack methodology uses properties of node posteriors, including their distances and entropies.

3 Problem Formulation

The paper formulates link stealing as inferring whether two nodes are connected using black-box access to a GNN and specified adversarial background knowledge. Three binary knowledge dimensions produce 8 attack settings.

  • 3 Problem Formulation: This section introduces the threat model and formally defines the link stealing attack.The attack is subsequently constructed under different background-knowledge configurations.
  • 3.1 Threat Model: The adversary seeks to infer whether a given node pair is connected in the target dataset.Such links may expose sensitive social relationships or confidential graph intellectual property.
  • 3.1 Threat Model: The adversary is assumed to have black-box access and can obtain only node posteriors by querying the target GNN.This is characterized as the most difficult setting for the adversary.
  • 3.1 Threat Model: Background knowledge is characterized along node attributes, a partial target graph, and a shadow dataset.These dimensions are denoted F, A*, and D′, respectively.
  • 3.1 Threat Model: Known node attributes include labels for a small subset of nodes, while a partial graph supplies known links that can train the attack model.The partial graph provides ground-truth edges for supervised attack training.
  • 3.1 Threat Model: A shadow dataset contains its own attributes and graph and supports training a shadow target model for transferring attacks.It need not come from the same domain, although same-domain data performs better in Section 5.
  • 3.1 Threat Model: The adversary’s background knowledge is represented as K = (F,A*,D′).Each of the three knowledge items is available or unavailable as a binary choice.
  • 3.2 Link Stealing Attack: The resulting 8 knowledge configurations define 8 link stealing attacks against pairs of nodes in the target dataset.The formal definition assumes black-box GNN access, a target node pair, and background knowledge K.

4 Attack Taxonomy

The paper organizes link-stealing attacks by adversary knowledge and develops attack features from node posteriors, entropies, attributes, partial graphs, and shadow datasets. The taxonomy addresses order invariance and dimension mismatch across attack settings.

  • Attack Methodologies: Symmetric distance metrics and pairwise operations make predictions invariant to whether an undirected node pair is ordered as (u,v) or (v,u).The attacks use eight symmetric distance metrics and pairwise vector operations to address node pair order.
  • Attack Methodologies: The unsupervised posterior-distance attack predicts links from d(f(u), f(v)), relying on closer posteriors for linked nodes.A threshold is needed for concrete predictions, while AUC evaluates performance across thresholds.
  • Attack Methodologies: Shadow-to-target transfer faces dimension mismatch because the two datasets can produce posterior vectors with different numbers of labels.The attack therefore designs features over posteriors rather than directly using posterior coordinates.
  • Attack Methodologies: Transfer attacks represent shadow-dataset posterior pairs with eight distances and four entropy-based pairwise features.Entropy summarizes each posterior, and pairwise operations remove dependence on node ordering.
  • Attack Methodologies: Supervised attacks train an MLP from known links, while transferring attacks use features extracted from shadow data and, in some settings, the target partial graph.Feature families include posterior distances, entropy operations, reference-model posteriors, and node-attribute distances.
  • Attack Taxonomy: 8 attack scenarios combine adversary knowledge of node attributes, a partial graph, and a shadow dataset into three categories.The paper distinguishes attacks by which of these three knowledge dimensions are available.

5 Evaluation

Across eight real-world datasets, the attacks effectively steal links from GNNs, with performance shaped by distance metrics, background knowledge, feature design, and dataset domain. The strongest attacks achieve very high AUC, while some defenses and architectural changes do not eliminate the privacy risk.

  • Correlation distance performs best for Attack-0 across datasets, reaching AUC 0.959 on Citeseer versus 0.801 for Canberra distance.Performance varies by dataset: Correlation distance reaches 0.635 AUC on ENZYMES.
  • Positive node pairs have smaller posterior Correlation distances than negative pairs, and Attack-0 performs better on pairs with lower distances.This supports the intuition that linked nodes aggregate one another’s features and become closer in representation.
  • Target partial graphs are more informative than shadow datasets, while combining features can suffer from dimension-mismatch constraints.Attack-4 performs worse than Attack-3, and Attack-7 drops below Attack-6 because it uses fewer features to combine target and shadow information.
  • Most attacks outperform traditional link prediction; on COX2, Attack-6 gains more than 20% over the link-prediction model.The attacks remain effective across GCN, GraphSAGE, and GAT, while top-k defense leaves AUC at 0.855 and creates a utility–privacy trade-off.
  • Average AUC exceeds 0.95 on 7 of 8 datasets for Attack-6, demonstrating effective link stealing from GNNs.

6 Related Work

The paper situates link stealing attacks among machine-learning security and privacy attacks, distinguishing their graph-structure privacy target from related threats. Existing GNN defenses primarily improve robustness against adversarial manipulation rather than preventing privacy leakage.

  • Membership Inference: Membership inference determines whether a data sample belongs to a model’s training dataset.Prior work also connects membership inference with model overfitting and studies attacks under relaxed adversary assumptions.
  • Model Inversion: Model inversion learns sensitive training-data attributes from target-model outputs.Examples include inferring patients’ genetic markers from models and demographic information.
  • Model Extraction: Model extraction steals target-model parameters, hyperparameters, or behavior through queries and prediction pairs.Related methods include equation solving, hyperparameter theft, and training functionally equivalent or knockoff models.
  • Adversarial Attacks on Graph Neural Networks: Adversarial attacks on GNNs manipulate graph structure or node features to fool node-classification models.These attacks target training or testing behavior and differ from link stealing’s privacy objective.
  • Adversarial Attacks on Graph Neural Networks: Existing GNN defenses improve model robustness against adversarial attacks rather than preventing privacy leakage.Related work also includes attacks and defenses for non-GNN graph models.

7 Conclusion and Future Work

The paper introduces the first GNN link-stealing attacks, showing that black-box model access can reveal whether node pairs were linked in the training graph. It defines eight attacks across three background-knowledge dimensions and evaluates them on eight real-world datasets, while identifying broader GNN settings and defenses as future work.

  • Conclusion: The paper proposes the first link stealing attacks against GNNs.The attacks infer links in graphs used to train GNN models.
  • Conclusion: Black-box access to a target GNN can support accurate inference of whether node pairs are connected.The threat model characterizes adversary knowledge along three dimensions and jointly defines eight attacks.
  • Conclusion: Evaluation on eight real-world datasets shows that the attacks can accurately steal links.The paper reports this as the main empirical conclusion.
  • Future Work: Future work includes extending the attacks to graph-classification GNNs and developing defenses against them.The conclusion specifically mentions these two directions.

A Appendix

The appendix documents distance metrics, pairwise vector operations, attack evaluation tables, and the relationship between attack-training-data ratios and AUC scores. These materials provide supplementary views of attack performance across datasets and attack variants.

  • Supplementary Metrics: Distance metrics use f_i(u) to denote the i-th component of node u’s output vector and can also apply to node attributes.The appendix lists these metrics in Table 13.
  • Supplementary Metrics: Pairwise vector operations likewise use f_i(u) and can apply to node attributes and entropies summarized from posteriors.These operations are documented in Table 14.
  • Attack Evaluation: The relationship between the attack-training-dataset ratio and AUC is plotted across all eight datasets.The figure uses ratio on the x-axis and AUC score on the y-axis.
  • Attack Evaluation: Table 22 reports average precision and recall with standard deviation for Attack-7, using the best-performing shadow dataset.This extends the appendix’s supplementary evaluation coverage to the final attack variant.
Loading 2005.02131v2…