# Trust-But-Verify: Poisoning-Resilient Locally Private Graph Learning Protocols

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Membership inference attacks, one of 12 directions in LLM safety and security.
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Placed in

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

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

- [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)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [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)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [Collecting and Analyzing Multidimensional Data with Local Differential Privacy](https://mlsanity.com/paper/1907.00782/) (2019)
- [Adaptive Laplace Mechanism: Differential Privacy Preservation in Deep Learning](https://mlsanity.com/paper/1709.05750/) (2017)
- [Group Property Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2209.01100/) (2022)
- [Estimating Numerical Distributions under Local Differential Privacy](https://mlsanity.com/paper/1912.01051/) (2019)
- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation](https://mlsanity.com/paper/2309.03190/) (2023)
- [Privacy-Preserving Graph Embedding based on Local Differential Privacy](https://mlsanity.com/paper/2310.11060/) (2023)
- [Devil's Hand: Data Poisoning Attacks to Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2506.09803/) (2025)

## Abstract (arXiv)

Built upon local differential privacy (LDP), locally private graph learning protocols have emerged as an important paradigm for decentralized graph learning, balancing privacy protection and learning utility. Under such protocols, each user locally perturbs their node features and adjacency information before transmission, ensuring formal privacy guarantees without original data leaving the device. However, the inherently open participation nature renders these protocols critically vulnerable to data poisoning attacks, where adversaries inject carefully crafted malicious nodes to corrupt neighborhood aggregation and degrade downstream utility. Despite the severity of this threat, effective defenses in this setting remain largely unexplored. In this paper, we propose VERITAS, a poisoning-resilient locally private graph learning protocol built on a trust-but-verify paradigm. By introducing a verification list encoding graded peer trust levels, VERITAS jointly privatizes node features and graph structure on the user side, while exploiting bilateral attestation asymmetry on the server side to identify and prune malicious nodes. Concretely, VERITAS comprises four synergistic stages: (1) local data perturbation, (2) attestation-driven malicious node pruning, (3) utility restoration via dual denoising, and (4) robust private graph learning. Extensive experiments on four real-world benchmark datasets across multiple LDP mechanisms and GNN architectures demonstrate that VERITAS effectively defends against data poisoning attacks and significantly improves downstream graph learning utility under rigorous privacy guarantees.