# Stealing Links from Graph Neural Networks

arXiv: https://arxiv.org/abs/2005.02131 · HTML: https://mlsanity.com/paper/2005.02131/

## Key facts

- Cited by 115 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2020.

## Built on by (most cited first, 30 of 115)

- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [PLeak: Prompt Leaking Attacks against Large Language Model Applications](https://mlsanity.com/paper/2405.06823/) (2024)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [ML-Doctor: Holistic Risk Assessment of Inference Attacks Against Machine Learning Models](https://mlsanity.com/paper/2102.02551/) (2021)
- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defences](https://mlsanity.com/paper/2206.08451/) (2022)
- [Mitigating Membership Inference Attacks by Self-Distillation Through a Novel Ensemble Architecture](https://mlsanity.com/paper/2110.08324/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Membership Inference Attacks Against Recommender Systems](https://mlsanity.com/paper/2109.08045/) (2021)
- ["Real Attackers Don't Compute Gradients": Bridging the Gap Between Adversarial ML Research and Practice](https://mlsanity.com/paper/2212.14315/) (2022)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Adapting Membership Inference Attacks to GNN for Graph Classification: Approaches and Implications](https://mlsanity.com/paper/2110.08760/) (2021)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [Model Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2112.08331/) (2021)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Quantifying and Mitigating Privacy Risks of Contrastive Learning](https://mlsanity.com/paper/2102.04140/) (2021)
- [Property Inference Attacks Against GANs](https://mlsanity.com/paper/2111.07608/) (2021)
- [Privacy Leakage on DNNs: A Survey of Model Inversion Attacks and Defenses](https://mlsanity.com/paper/2402.04013/) (2024)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [StolenEncoder: Stealing Pre-trained Encoders in Self-supervised Learning](https://mlsanity.com/paper/2201.05889/) (2022)
- [A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applications](https://mlsanity.com/paper/2308.16375/) (2023)
- [IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2407.19398/) (2024)
- [Group Property Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2209.01100/) (2022)
- [Backdoor Attacks Against Dataset Distillation](https://mlsanity.com/paper/2301.01197/) (2023)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [False Claims against Model Ownership Resolution](https://mlsanity.com/paper/2304.06607/) (2023)
- [Teacher Model Fingerprinting Attacks Against Transfer Learning](https://mlsanity.com/paper/2106.12478/) (2021)
- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)

## Abstract (arXiv)

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.