# Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 57 references that are in the map.
- First posted on arXiv 6 Sep 2023.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [Collecting and Analyzing Multidimensional Data with Local Differential Privacy](https://mlsanity.com/paper/1907.00782/) (2019)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Secure Deep Graph Generation with Link Differential Privacy](https://mlsanity.com/paper/2005.00455/) (2020)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)
- [LPGNet: Link Private Graph Networks for Node Classification](https://mlsanity.com/paper/2205.03105/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)

## Built on by (most cited first, 6 of 6)

- [Devil's Hand: Data Poisoning Attacks to Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2506.09803/) (2025)
- [How Feasible is Augmenting Fake Nodes with Learnable Features as a Counter-strategy against Link Stealing Attacks?](https://mlsanity.com/paper/2503.09726/) (2025)
- [Panther: A Cost-Effective Privacy-Preserving Framework for GNN Training and Inference Services in Cloud Environments](https://mlsanity.com/paper/2511.01654/) (2025)
- [HoGS: Homophily-Oriented Graph Synthesis for Local Differentially Private GNN Training](https://mlsanity.com/paper/2602.08762/) (2026)
- [Auditing Privacy Risks in LLM-Enhanced Graph Neural Networks](https://mlsanity.com/paper/2608.25727/) (2026)
- [Trust-But-Verify: Poisoning-Resilient Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2609.07063/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have gained an increasing amount of popularity due to their superior capability in learning node embeddings for various graph inference tasks, but training them can raise privacy concerns. To address this, we propose using link local differential privacy over decentralized nodes, enabling collaboration with an untrusted server to train GNNs without revealing the existence of any link. Our approach spends the privacy budget separately on links and degrees of the graph for the server to better denoise the graph topology using Bayesian estimation, alleviating the negative impact of LDP on the accuracy of the trained GNNs. We bound the mean absolute error of the inferred link probabilities against the ground truth graph topology. We then propose two variants of our LDP mechanism complementing each other in different privacy settings, one of which estimates fewer links under lower privacy budgets to avoid false positive link estimates when the uncertainty is high, while the other utilizes more information and performs better given relatively higher privacy budgets. Furthermore, we propose a hybrid variant that combines both strategies and is able to perform better across different privacy budgets. Extensive experiments show that our approach outperforms existing methods in terms of accuracy under varying privacy budgets.