# Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 92 references that are in the map.
- First posted on arXiv 21 Feb 2022.

## Builds on (most cited first, 30 of 32)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [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)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Releasing Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2109.08907/) (2021)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Manipulation Attacks in Local Differential Privacy](https://mlsanity.com/paper/1909.09630/) (2019)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Data Poisoning Attacks to Local Differential Privacy Protocols](https://mlsanity.com/paper/1911.02046/) (2019)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Cross-Domain Few-Shot Graph Classification](https://mlsanity.com/paper/2201.08265/) (2022)
- [Context-Aware Local Differential Privacy](https://mlsanity.com/paper/1911.00038/) (2019)
- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)
- [Utility-Optimized Local Differential Privacy Mechanisms for Distribution Estimation](https://mlsanity.com/paper/1807.11317/) (2018)
- [Graph Sample and Hold: A Framework for Big-Graph Analytics](https://mlsanity.com/paper/1403.3909/) (2014)
- [Approximately Counting Triangles in Sublinear Time](https://mlsanity.com/paper/1504.00954/) (2015)
- [How to Count Triangles, without Seeing the Whole Graph](https://mlsanity.com/paper/2006.11947/) (2020)

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

- [Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation](https://mlsanity.com/paper/2309.03190/) (2023)
- [Towards Differential Privacy in Sequential Recommendation: A Noisy Graph Neural Network Approach](https://mlsanity.com/paper/2309.11515/) (2023)
- [GraphPub: Generation of Differential Privacy Graph with High Availability](https://mlsanity.com/paper/2403.00030/) (2024)
- [Devil's Hand: Data Poisoning Attacks to Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2506.09803/) (2025)
- [Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions](https://mlsanity.com/paper/2312.07055/) (2023)
- [HoGS: Homophily-Oriented Graph Synthesis for Local Differentially Private GNN Training](https://mlsanity.com/paper/2602.08762/) (2026)
- [Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense](https://mlsanity.com/paper/2606.08067/) (2026)
- [EdgeRefine: Privacy-Utility Balance for Graphs via Jaccard Sampling under Edge Differential Privacy](https://mlsanity.com/paper/2607.08659/) (2026)
- [Trust-But-Verify: Poisoning-Resilient Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2609.07063/) (2026)

## Abstract (arXiv)

Differentially private GNNs (Graph Neural Networks) have been recently studied to provide high accuracy in various tasks on graph data while strongly protecting user privacy. In particular, a recent study proposes an algorithm to protect each user's feature vector in an attributed graph, which includes feature vectors along with node IDs and edges, with LDP (Local Differential Privacy), a strong privacy notion without a trusted third party. However, this algorithm does not protect edges (friendships) in a social graph, hence cannot protect user privacy in unattributed graphs, which include only node IDs and edges. How to provide strong privacy with high accuracy in unattributed graphs remains open. In this paper, we propose a novel LDP algorithm called the DPRR (Degree-Preserving Randomized Response) to provide LDP for edges in GNNs. Our DPRR preserves each user's degree hence a graph structure while providing edge LDP. Technically, our DPRR uses Warner's RR (Randomized Response) and strategic edge sampling, where each user's sampling probability is automatically tuned using the Laplacian mechanism to preserve the degree information under edge LDP. We also propose a privacy budget allocation method to make the noise in both Warner's RR and the Laplacian mechanism small. We focus on graph classification as a task of GNNs and evaluate the DPRR using three social graph datasets. Our experimental results show that the DPRR significantly outperforms three baselines and provides accuracy close to a non-private algorithm in all datasets with a reasonable privacy budget, e.g., epsilon=1. Finally, we introduce data poisoning attacks to our DPRR and a defense against the attacks. We evaluate them using the three social graph datasets and discuss the experimental results.