Graph learning protocols defend against data poisoning with privacy
Trust-But-Verify: Poisoning-Resilient Locally Private Graph Learning Protocols
Machine Learning
Summary
Some computer programs learn from connected data (graphs) while keeping individual information private, by hiding details before sharing. But bad actors can still add harmful fake data to confuse these programs. This paper presents VERITAS, a system that checks trust between users, spots suspicious data, and removes it while still protecting privacy. The authors show that VERITAS can keep learning useful while blocking attacks, using tests on real-world data.
What this means in practice
- •For mobile app developers: Integrate poisoning-resilient local privacy techniques to protect user data and maintain graph-based features' accuracy in decentralized apps.
- •For social network platform engineers: Deploy robust graph learning methods that defend against malicious user data and preserve privacy in large-scale social graphs.
Authors
Longzhu He, Li Sun, Hao Peng, Ruijie Wang, Raymond Chi-Wing Wong, Sen Su
Abstract
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.