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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.
Fig. 3: Performance comparison between our proposed Veritas (Ours) and attack baseline on the node classification task.
TypeDataset#Nodes#Edges#Features#Classes
Citation NetworkCora2,7085,2781,4337
Citeseer3,3274,5523,7036
Social NetworkLastFM7,62427,8067,84218
Twitch4,64861,7061282
TABLE I: Statistics of graph datasets
GNNMethodCoraCiteseerLastFMTwitch
GraphSAGEBaseline69.267.672.472.7
Ours75.772.976.376.9
GATBaseline67.465.169.670.1
Ours71.870.375.275.4
TABLE II: Comparison of classification accuracy between our defense and attack baseline across different GNN models.
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 ϵx\epsilon_{x} , structural privacy budget ϵa\epsilon_{a} , and injection rate r⋆r^{\star} , respectively.

Explore similar work

CardsList
Jul 6, 2026

Towards Personalized Differentially Private Learning for Decentralized Local Graphs

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.

Longzhu He, Peng Tang, Chaozhuo Li +5

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 NetworksDecentralized LearningPrivacy-Preserving MLDifferential Privacy
AskPDF
Mar 21, 2026

Adversarial Attacks on Locally Private Graph Neural Networks

Graph neural network (GNN) is a powerful tool for analyzing graph-structured data. However, their vulnerability to adversarial attacks raises serious concerns, especially when dealing with sensitive information. Local Differential Privacy (LDP) offers a privacy-preserving framework for training GNNs, but its impact on adversarial robustness remains underexplored. This paper investigates adversarial attacks on LDP-protected GNNs. We explore how the privacy guarantees of LDP can be leveraged or hindered by adversarial perturbations. The effectiveness of existing attack methods on LDP-protected GNNs are analyzed and potential challenges in crafting adversarial examples under LDP constraints are discussed. Additionally, we suggest directions for defending LDP-protected GNNs against adversarial attacks. This work investigates the interplay between privacy and security in graph learning, highlighting the need for robust and privacy-preserving GNN architectures.

Matta Varun, Ajay Kumar Dhakar, Yuan Hong +1

Indian Institute of Technology Kharagpur, India · University of Connecticut, USA

Adversarial AttacksGraph Neural NetworksPrivacy-Preserving MLDifferential Privacy
AskPDF
Aug 4, 2026

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

Graph inference over relational data can expose sensitive edge information, and this risk becomes more severe in dynamic graphs, where repeated model updates cause privacy loss to accumulate. We formulate Edge-level Differentially Private Dynamic Graph Inference (EDG) and propose PriDyG, a private inference framework that combines GNN-based structural learning with LLM-based semantic reasoning. PriDyG introduces incremental private multi-hop aggregation, which buffers newly arrived edges and processes each edge exactly once. By parallel composition, the total privacy cost equals that of a single static release, independent of the number or schedule of model updates. Compared with geometrically decaying budget allocation, incremental aggregation avoids exponentially increasing noise while preserving exact one-hop signals and at least half of two-hop information transfers. PriDyG further complements privatized GNN outputs with LLM predictions derived solely from node text, incurring no additional edge-level privacy cost. Experiments on four benchmarks for node classification and link prediction show that PriDyG consistently outperforms geometrically decaying baselines under the same privacy budget and matches the utility of naive per-update retraining while reducing cumulative privacy cost by up to three orders of magnitude.

Yuyang Xia, Ruixuan Liu, Li Xiong

Emory University Atlanta, Georgia, USA

Dynamic Graph LearningPrivacy-Preserving MLDifferential Privacy
AskPDF