# Robustness of Locally Differentially Private Graph Analysis Against Poisoning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Membership inference attacks, one of 12 directions in LLM safety and security.
- Builds on 14 of its 54 references that are in the map.
- First posted on arXiv 25 Oct 2022.

## Placed in

- LLM safety and security / [Membership inference attacks](https://mlsanity.com/safety/membership-inference-attacks/)

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

- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [How To Backdoor Federated Learning](https://mlsanity.com/paper/1807.00459/) (2018)
- [Local Model Poisoning Attacks to Byzantine-Robust Federated Learning](https://mlsanity.com/paper/1911.11815/) (2019)
- [Analyzing Federated Learning through an Adversarial Lens](https://mlsanity.com/paper/1811.12470/) (2018)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [Manipulation Attacks in Local Differential Privacy](https://mlsanity.com/paper/1909.09630/) (2019)
- [EIFFeL: Ensuring Integrity for Federated Learning](https://mlsanity.com/paper/2112.12727/) (2021)
- [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)
- [Poisoning Attacks to Local Differential Privacy Protocols for Key-Value Data](https://mlsanity.com/paper/2111.11534/) (2021)
- [Preventing Manipulation Attack in Local Differential Privacy using Verifiable Randomization Mechanism](https://mlsanity.com/paper/2104.06569/) (2021)
- [Blackmarket-driven Collusion on Online Media: A Survey](https://mlsanity.com/paper/2008.13102/) (2020)

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

- [On Evaluating the Poisoning Robustness of Federated Learning under Local Differential Privacy](https://mlsanity.com/paper/2509.05265/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)

## Abstract (arXiv)

Locally differentially private (LDP) graph analysis allows private analysis on a graph that is distributed across multiple users. However, such computations are vulnerable to data poisoning attacks where an adversary can skew the results by submitting malformed data. In this paper, we formally study the impact of poisoning attacks for graph degree estimation protocols under LDP. We make two key technical contributions. First, we observe LDP makes a protocol more vulnerable to poisoning -- the impact of poisoning is worse when the adversary can directly poison their (noisy) responses, rather than their input data. Second, we observe that graph data is naturally redundant -- every edge is shared between two users. Leveraging this data redundancy, we design robust degree estimation protocols under LDP that can significantly reduce the impact of data poisoning and compute degree estimates with high accuracy. We evaluate our proposed robust degree estimation protocols under poisoning attacks on real-world datasets to demonstrate their efficacy in practice.