# LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 14 Aug 2021.

## Builds on (most cited first, 17 of 17)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Revisiting Membership Inference Under Realistic Assumptions](https://mlsanity.com/paper/2005.10881/) (2020)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [That which we call private](https://mlsanity.com/paper/1908.03566/) (2019)

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

- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (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)
- [A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applications](https://mlsanity.com/paper/2308.16375/) (2023)
- [Group Property Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2209.01100/) (2022)
- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)
- [Private Graph Extraction via Feature Explanations](https://mlsanity.com/paper/2206.14724/) (2022)
- [Unraveling Privacy Risks of Individual Fairness in Graph Neural Networks](https://mlsanity.com/paper/2301.12951/) (2023)
- [LPGNet: Link Private Graph Networks for Node Classification](https://mlsanity.com/paper/2205.03105/) (2022)
- [ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2304.08928/) (2023)
- [TrustGuard: GNN-based Robust and Explainable Trust Evaluation with Dynamicity Support](https://mlsanity.com/paper/2306.13339/) (2023)
- [Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection](https://mlsanity.com/paper/2307.06422/) (2023)
- [A Survey of Graph Unlearning](https://mlsanity.com/paper/2310.02164/) (2023)
- [Preserving Node-level Privacy in Graph Neural Networks](https://mlsanity.com/paper/2311.06888/) (2023)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [GraphGuard: Detecting and Counteracting Training Data Misuse in Graph Neural Networks](https://mlsanity.com/paper/2312.07861/) (2023)
- [A Privacy-Preserving Subgraph-Level Federated Graph Neural Network via Differential Privacy](https://mlsanity.com/paper/2206.03492/) (2022)
- [Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embedding](https://mlsanity.com/paper/2304.02932/) (2023)
- [Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation](https://mlsanity.com/paper/2309.03190/) (2023)
- [SoK: Unintended Interactions among Machine Learning Defenses and Risks](https://mlsanity.com/paper/2312.04542/) (2023)
- [Training Differentially Private Graph Neural Networks with Random Walk Sampling](https://mlsanity.com/paper/2301.00738/) (2023)
- [VertexSerum: Poisoning Graph Neural Networks for Link Inference](https://mlsanity.com/paper/2308.01469/) (2023)
- [Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach](https://mlsanity.com/paper/2309.08569/) (2023)
- [Practical Bayes-Optimal Membership Inference Attacks](https://mlsanity.com/paper/2505.24089/) (2025)
- [Finding MNEMON: Reviving Memories of Node Embeddings](https://mlsanity.com/paper/2204.06963/) (2022)

## Abstract (arXiv)

Graph structured data have enabled several successful applications such as recommendation systems and traffic prediction, given the rich node features and edges information. However, these high-dimensional features and high-order adjacency information are usually heterogeneous and held by different data holders in practice. Given such vertical data partition (e.g., one data holder will only own either the node features or edge information), different data holders have to develop efficient joint training protocols rather than directly transfer data to each other due to privacy concerns. In this paper, we focus on the edge privacy, and consider a training scenario where Bob with node features will first send training node features to Alice who owns the adjacency information. Alice will then train a graph neural network (GNN) with the joint information and release an inference API. During inference, Bob is able to provide test node features and query the API to obtain the predictions for test nodes. Under this setting, we first propose a privacy attack LinkTeller via influence analysis to infer the private edge information held by Alice via designing adversarial queries for Bob. We then empirically show that LinkTeller is able to recover a significant amount of private edges, outperforming existing baselines. To further evaluate the privacy leakage, we adapt an existing algorithm for differentially private graph convolutional network (DP GCN) training and propose a new DP GCN mechanism LapGraph. We show that these DP GCN mechanisms are not always resilient against LinkTeller empirically under mild privacy guarantees (varepsilon>5). Our studies will shed light on future research towards designing more resilient privacy-preserving GCN models; in the meantime, provide an in-depth understanding of the tradeoff between GCN model utility and robustness against potential privacy attacks.