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

• URL: http://arxiv.org/abs/2609.07063v1
• Date: Mon, 07 Sep 2026 05:38:06 GMT
• Title: Trust-But-Verify: Poisoning-Resilient Locally Private Graph Learning Protocols
• Abstract summary: We propose VERITAS, a poisoned-resilient locally private graph learning protocol built on a trust-but-verify paradigm.<n>We show that VERITAS effectively defends against data poisoning attacks and significantly improves downstream graph learning utility under rigorous privacy guarantees.
• Score: 24.683527596262905
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Towards Personalized Differentially Private Learning for Decentralized Local Graphs [62.244412935520025]
  Local Differential Privacy (LDP) has emerged as a promising solution for privacy-preserving data collection without relying on trusted servers.<n>Existing LDP-based graph learning methods typically assume uniform privacy requirements across users.<n>We propose PPGNN, a personalized differentially private framework for decentralized graph data.
  arXiv  Detail & Related papers  (2026-07-06T08:07:48Z)
• Privacy-Preserving Federated Learning Scheme with Mitigating Model Poisoning Attacks: Vulnerabilities and Countermeasures [10.862166653863571]
  We propose an enhanced privacy-preserving and Byzantine-robust federated learning scheme.<n>Our scheme guarantees privacy preservation and resilience against model poisoning attacks.
  arXiv  Detail & Related papers  (2025-06-30T08:39:01Z)
• Devil's Hand: Data Poisoning Attacks to Locally Private Graph Learning Protocols [46.94619400437805]
  This work introduces the first data poisoning attack targeting locally private graph learning protocols.<n>The attacker injects fake users into the protocol, manipulates these fake users to establish links with genuine users, and sends carefully crafted data to the server.<n>The effectiveness of the attack is demonstrated both theoretically and empirically.
  arXiv  Detail & Related papers  (2025-06-11T14:46:11Z)
• Efficient and Privacy-Preserved Link Prediction via Condensed Graphs [49.898152180805454]
  We introduce HyDROtextsuperscript+, a graph condensation method guided by algebraic Jaccard similarity.<n>Our method achieves nearly 20* faster training and reduces storage requirements by 452*, compared to link prediction on the original networks.
  arXiv  Detail & Related papers  (2025-03-15T14:54:04Z)
• Unveiling Privacy Vulnerabilities: Investigating the Role of Structure in Graph Data [17.11821761700748]
  This study advances the understanding and protection against privacy risks emanating from network structure. We develop a novel graph private attribute inference attack, which acts as a pivotal tool for evaluating the potential for privacy leakage through network structures. Our attack model poses a significant threat to user privacy, and our graph data publishing method successfully achieves the optimal privacy-utility trade-off.
  arXiv  Detail & Related papers  (2024-07-26T07:40:54Z)
• Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks [50.87615167799367]
  We certify Graph Neural Networks (GNNs) against poisoning attacks, including backdoors, targeting the node features of a given graph.<n>Our framework provides fundamental insights into the role of graph structure and its connectivity on the worst-case behavior of convolution-based and PageRank-based GNNs.
  arXiv  Detail & Related papers  (2024-07-15T16:12:51Z)
• Unveiling the Role of Message Passing in Dual-Privacy Preservation on GNNs [7.626349365968476]
  Graph Neural Networks (GNNs) are powerful tools for learning representations on graphs, such as social networks. Privacy-preserving GNNs have been proposed, focusing on preserving node and/or link privacy. We propose a principled privacy-preserving GNN framework that effectively safeguards both node and link privacy.
  arXiv  Detail & Related papers  (2023-08-25T17:46:43Z)
• Independent Distribution Regularization for Private Graph Embedding [55.24441467292359]
  Graph embeddings are susceptible to attribute inference attacks, which allow attackers to infer private node attributes from the learned graph embeddings. To address these concerns, privacy-preserving graph embedding methods have emerged. We propose a novel approach called Private Variational Graph AutoEncoders (PVGAE) with the aid of independent distribution penalty as a regularization term.
  arXiv  Detail & Related papers  (2023-08-16T13:32:43Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)
• Information Obfuscation of Graph Neural Networks [96.8421624921384]
  We study the problem of protecting sensitive attributes by information obfuscation when learning with graph structured data. We propose a framework to locally filter out pre-determined sensitive attributes via adversarial training with the total variation and the Wasserstein distance.
  arXiv  Detail & Related papers  (2020-09-28T17:55:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.