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

Longzhu He; Li Sun; Hao Peng; Ruijie Wang; Raymond Chi-Wing Wong; Sen Su

cs.LGSep 7, 2026

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

Authors: Longzhu He, Li Sun, Hao Peng, Ruijie Wang, Raymond Chi-Wing Wong, Sen Su

Organizations: Beijing University of Posts and Telecommunications · Beihang University · The Hong Kong University of Science and Technology · Chongqing University of Posts and Telecommunications

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.

Figures & tables

Fig. 1: Motivation and core intuition of Veritas . (a) Locally private graph learning protocol. Multiple users independently perturb their sensitive node features and adjacency information via local differential privacy (LDP) mechanisms. The resulting noisy reports are transmitted to an untrusted server, which performs graph learning on the collected perturbed data. (b) Data poisoning attacks against locally private graph learning, where red nodes denote injected malicious participants that submit carefully crafted poisoned reports to corrupt the training process and degrade downstream task performance. (c) Veritas detects and prunes malicious nodes through bilateral attestation, preserving graph learning utility while maintaining rigorous local privacy guarantees.

Fig. 2: Overview of Veritas . Veritas comprises four synergistic stages: ① local data perturbation for private data collection, ② attestation-driven malicious node pruning for adversarial participant removal, ③ utility restoration via dual denoising, and ④ robust private graph learning for downstream inference.

Panel of Figure 3 — Fig. 3: Performance comparison between our proposed Veritas (Ours) and attack baseline on the node classification task.

Type	Dataset	#Nodes	#Edges	#Features	#Classes
Citation Network	Cora	2,708	5,278	1,433	7
Citation Network	Citeseer	3,327	4,552	3,703	6
Social Network	LastFM	7,624	27,806	7,842	18
Social Network	Twitch	4,648	61,706	128	2

TABLE I: Statistics of graph datasets

GNN	Method	Cora	Citeseer	LastFM	Twitch
GraphSAGE	Baseline	69.2	67.6	72.4	72.7
GraphSAGE	Ours	75.7	72.9	76.3	76.9
GAT	Baseline	67.4	65.1	69.6	70.1
GAT	Ours	71.8	70.3	75.2	75.4

TABLE II: Comparison of classification accuracy between our defense and attack baseline across different GNN models.

Panel of Figure 6 — Fig. 4: Analysis of Veritas under data poisoning attacks. (a) Ablation study under different defense configurations, evaluating the contribution of each core component. (b)–(d) Parameter sensitivity with respect to the feature privacy budget $\epsilon_{x}$ , structural privacy budget $\epsilon_{a}$ , and injection rate $r^{\star}$ , respectively.

Explore similar work

Towards Personalized Differentially Private Learning for Decentralized Local Graphs
Jul 6, 2026Longzhu He, Peng Tang, Chaozhuo Li +5Graph Neural Networks Decentralized Learning
School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China · State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China · School of Cyber Science and Technology, Shandong University, Qingdao, China +2
Adversarial Attacks on Locally Private Graph Neural Networks
Mar 21, 2026Matta Varun, Ajay Kumar Dhakar, Yuan Hong +1Adversarial Attacks Graph Neural Networks
Indian Institute of Technology Kharagpur, India · University of Connecticut, USA
PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration
Aug 4, 2026Yuyang Xia, Ruixuan Liu, Li XiongDynamic Graph Learning Privacy-Preserving ML
Emory University Atlanta, Georgia, USA

Jul 6, 2026J/K move · Enter open · S save

Towards Personalized Differentially Private Learning for Decentralized Local Graphs

Longzhu He, Peng Tang, Chaozhuo Li, Jinhu Fu+4

School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China · State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China · School of Cyber Science and Technology, Shandong University, Qingdao, China+2

Graph Neural Networks Decentralized Learning Privacy-Preserving ML Differential Privacy

Open paper AskPDF arXiv

Graph-structured data is increasingly generated and stored in decentralized environments, such as social platforms, mobile applications, and edge networks, where users maintain control over their local graph data. However, collecting and analyzing such decentralized graph data for downstream learning tasks raises significant privacy concerns, as nodes and their attributes often contain sensitive personal information. Local Differential Privacy (LDP) has emerged as a promising solution for privacy-preserving data collection without relying on trusted servers. Nevertheless, existing LDP-based graph learning methods typically assume uniform privacy requirements across users, ignoring the heterogeneous and personalized privacy preferences commonly observed in real-world systems. This uniform treatment leads to inflexible noise injection at the data collection stage, resulting in substantial distortion of graph data and degraded utility in subsequent analysis. To address this limitation, we propose PPGNN, a personalized differentially private framework for decentralized graph data. PPGNN enables user-specific privacy budgets during local perturbation while preserving analytical utility. To handle heterogeneous privacy levels and noise distortion, we design a two-stage solution consisting of a Personalized Perturbation Mechanism (PPM) and a weighted calibration strategy, FlexProp. Extensive experiments on six real-world graph datasets demonstrate that PPGNN effectively balances personalized privacy protection and data utility in decentralized graph learning scenarios.

Abstract

Explore similar work

Towards Personalized Differentially Private Learning for Decentralized Local Graphs

Adversarial Attacks on Locally Private Graph Neural Networks

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration