PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.07063v1cs.LG

TL;DR

Open participation makes locally private graph learning vulnerable to poisoning, while LDP noise complicates identifying malicious participants. VERITAS uses a trust-but-verify protocol with bilateral attestation to prune malicious nodes while preserving LDP guarantees. Experiments report defense against poisoning and improved task utility across four datasets, multiple LDP mechanisms, and GNN architectures.

  • Problem

    Locally private graph learning remains vulnerable to poisoning, and effective defenses are largely unexplored despite noisy reports making malicious participants difficult to distinguish.

    Source: A. Problem Definition · p. 2, C. Locally Private Graph Learning · p. 9

  • Method

    VERITAS uses a verification list and bilateral attestation asymmetry to identify and prune malicious nodes while retaining local privacy guarantees.

    Source: §I · p. 2

  • Results

    Across four datasets, multiple LDP mechanisms, and GNN architectures, VERITAS consistently defends against poisoning and significantly improves task utility.

    Source: §VII · pp. 9–10

  • Takeaways & Limitations

    The results establish a promising direction for robust privacy-preserving graph learning that integrates security considerations.

    Source: §VII · p. 10

Abstract

from arXiv · show

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.

I. INTRODUCTION

Locally private graph learning protects sensitive node features and relationships, but its open participation model leaves it vulnerable to poisoning that is hard to distinguish from LDP noise. VERITAS combines privacy-preserving collection with attestation-based pruning to address this problem.

I. INTRODUCTION

  • Poisoned feature and topology reports can propagate through message passing, contaminating node representations and degrading downstream tasks, while LDP noise obscures malicious reports.Open participation can let adversaries create sybil accounts and infiltrate the graph through links with legitimate users.Source: §I · p. 1
  • Existing defenses are difficult to apply because LDP withholds raw data, its noise blurs adversarial signals, and centralized defenses assume unperturbed graphs.These constraints make it difficult to distinguish malicious participants from honest ones using noisy observations.Source: §I · pp. 1–2
  • VERITAS uses a trust-but-verify paradigm and a verification list of graded peer trust levels to identify and prune malicious nodes while preserving LDP guarantees.Its four stages are local perturbation, attestation-driven pruning, dual denoising, and robust private graph learning.Source: §I · p. 2
  • VERITAS defends against poisoning and improves learning utility across multiple LDP mechanisms and GNN architectures.The reported experiments use real-world datasets.Source: §I · p. 2

A. Problem Definition

  • The problem setting treats both node features and adjacency information as sensitive, with the goal of accurate downstream learning under rigorous privacy guarantees.Users perturb their local feature and adjacency data before the server learns from noisy reports.Source: A. Problem Definition · p. 2

B. Local Differential Privacy

  • LDP protects data through local randomization, while link-level LDP extends protection to adjacency changes affecting one edge.The privacy budget controls the privacy-utility trade-off, and post-processing and sequential composition are stated as properties used by the framework.Source: B. Local Differential Privacy · p. 3

C. Locally Private Graph Learning

The user-side stage locally perturbs node features and adjacency information before transmission. The feature and link mechanisms use separate privacy budgets whose sum provides the stated overall LDP guarantee.

1) User-Side Perturbation:

  • For features, VERITAS samples m dimensions uniformly, perturbs each with an (ϵx/m)-LDP mechanism, and sets the remaining dimensions to zero.The piecewise mechanism is given as an illustrative feature mechanism.Source: 1) User-Side Perturbation · p. 3
  • For graph structure, randomized response independently flips each adjacency entry, with probabilities determined by ϵa.An entry is retained with probability e^ϵa/(e^ϵa + 1) and flipped with probability 1/(e^ϵa + 1).Source: 1) User-Side Perturbation · p. 3
  • The feature and link perturbation budgets, ϵx and ϵa, sum to ϵ, so the combined mechanism satisfies ϵ-LDP.Raw private data stays on the user's device; the server receives samples from the perturbed distribution.Source: 1) User-Side Perturbation · p. 3

2) Server-Side Learning:

The server reconstructs a noisy graph from perturbed reports and trains a GNN over perturbed neighborhoods. It uses learned representations from labeled nodes to infer labels for unlabeled nodes.

2) Server-Side Learning:

  • The server reconstructs a noisy graph from received perturbed reports and trains a K-layer GNN for downstream tasks such as node classification.Because the true neighborhood is not directly observable under local perturbation, learning uses a perturbed neighborhood.Source: 2) Server-Side Learning · p. 3
  • At each layer, node embeddings are computed through neighborhood aggregation followed by a learnable nonlinear update.The aggregation function is permutation-invariant, with mean and sum given as examples.Source: 2) Server-Side Learning · p. 3
  • After K layers, representations encode multi-hop structure from the perturbed graph and support training on labeled nodes and inference on unlabeled nodes.The unlabeled set is defined as V \ Vl.Source: 2) Server-Side Learning · p. 3

III. THREAT MODEL

The threat model includes privacy inference by a semi-honest server and poisoning by a malicious external attacker. It specifies the attacker’s capabilities and the privacy constraints relevant to both threats.

III. THREAT MODEL

  • The model considers both semi-honest-server privacy inference attacks and malicious-external-attacker data poisoning.The two threats may coexist in locally private graph learning.Source: §III · p. 3

A. Privacy Inference Attacks by Semi-Honest Server

  • A semi-honest server may use trained GNN interactions to attempt attribute, link, or membership inference, while LDP formally protects each user’s raw input.The protocol imposes ε-LDP requirements on both features and links.Source: A. Privacy Inference Attacks by… · p. 4

B. Data Poisoning Attacks by Malicious Attacker

1) Adversary Capability:

  • The attacker knows the public protocol and its perturbation mechanisms and privacy budgets, but lacks raw user data, exact neighborhoods, and access to server-side model internals.This is framed as a black-box threat model.Source: 2) Adversary Knowledge · p. 4

2) Adversary Knowledge:

The attack constructs malicious nodes using protocol knowledge while seeking to degrade downstream GNN utility under a stealth budget. VERITAS counters poisoning through a four-stage private-defense pipeline.

2) Adversary Knowledge:

  • The attack algorithm creates fake nodes, selects target nodes, constructs adjacency links, and coordinates connectivity among the fake nodes.The attacker must construct malicious inputs without structural knowledge or feedback from the target model.Source: 2) Adversary Knowledge · p. 4

3) Adversary Objective:

  • The attacker seeks to maximize downstream GNN impact while keeping feature and link perturbations within a stealth budget Δ.For node classification, the impact metric usually corresponds to increasing the misclassification rate.Source: 3) Adversary Objective · p. 4

IV. METHODOLOGY

  • VERITAS couples local perturbation, attestation-driven pruning, dual denoising, and robust private graph learning in a trust-but-verify protocol.The overview assigns these stages to private collection, adversarial participant removal, utility restoration, and downstream inference.Source: §IV · p. 4, Figure 2 · p. 5

A. Local Data Perturbation

VERITAS locally privatizes both node features and graph structure, then uses bilateral attestation signals to prune suspicious nodes. Its verification list encodes both relationships and graded peer trust.

A. Local Data Perturbation

2) Graph Structure Perturbation:

  • The verification list encodes structural absence as 0 and neighbor trust levels as 1 through κ; KRR perturbation satisfies εa-link LDP.Together with feature perturbation on disjoint attributes, the composition theorem gives overall ε-LDP with ε = εx + εa.Source: 2) Graph Structure Perturbation · p. 5

B. Attestation-Driven Malicious Node Pruning

1) Bilateral Signal Extraction:

VERITAS derives three bilateral trust signals and combines them into an edge confidence score, giving less weight to unconfirmed or asymmetric relationships.

1) Bilateral Signal Extraction:

  • An edge is structurally valid only when both parties acknowledge the relationship; either party denying it gives the edge zero confidence.This mutual-acknowledgment rule acts as a hard gate.Source: 1) Bilateral Signal Extraction · p. 6
  • Among mutually acknowledged edges, the lower reported trust level is used, limiting a malicious node’s attempt to claim maximum trust toward every neighbor.The minimum anchors effective trust in the honest party’s more conservative assessment.Source: 1) Bilateral Signal Extraction · p. 6

2) Edge Confidence Scoring:

3) Suspicion Scoring and Node Pruning:

VERITAS scores nodes by directional bias in bilateral trust assessments, removes nodes above a threshold, then denoises the retained graph before learning.

3) Suspicion Scoring and Node Pruning:

  • A node’s suspicion score aggregates directional bias in its bilateral assessments; a positive score indicates that it rates others more highly than they rate it.The score is calculated over nodes claiming any relationship with it.Source: 3) Suspicion Scoring and Node Pruning · p. 6
  • Under the stated fake-node and honest-neighbor assumptions, malicious nodes have expected suspicion (2pa−1)(κ−1), while honest nodes with symmetric assessments have expectation zero.Here, pa is the truthful reporting probability of KRR; the expected gap grows with privacy budget ϵa and trust-level granularity κ.Source: 3) Suspicion Scoring and Node Pruning · p. 6
  • Nodes with suspicion above threshold γ are removed, and the retained graph keeps only edges with positive bilateral support.The resulting graph is passed to the next stage.Source: 3) Suspicion Scoring and Node Pruning · p. 6

C. Utility Restoration via Dual Denoising

  • Dual denoising applies L1-regularized Node Feature Regularization to reduce feature dimensionality and a High-Order Aggregator to expand the effective neighborhood.Together, these components produce denoised features and a refined adjacency structure for robust private graph learning.Source: C. Utility Restoration via Dual… · pp. 6–7

D. Robust Private Graph Learning

The protocol trains a GNN on the denoised, pruned graph while preserving an end-to-end LDP guarantee. Its pruning and denoising stages have near-linear graph-size complexity, and experiments use four citation and social-network benchmarks.

D. Robust Private Graph Learning

  • The server trains a GNN on labeled nodes in the denoised graph, then predicts labels for its unlabeled retained nodes.The paper states that pruning and noise mitigation yield a cleaner graph for downstream learning.Source: D. Robust Private Graph Learning · p. 7

1) Privacy Analysis:

  • Perturbing features under ϵx-LDP and verification lists under ϵa-link LDP gives VERITAS an end-to-end guarantee of (ϵx + ϵa)-LDP.Server-side operations use collected reports and consume no additional privacy budget through post-processing.Source: 1) Privacy Analysis · p. 7

2) Complexity Analysis:

  • Pruning costs O(|V|+|E|), while HOA and NFR cost O(K|E|d) and O(|V|d), respectively; the paper characterizes both stages as near-linear in graph size.K is the number of propagation steps and d is the feature dimension.Source: 2) Complexity Analysis · p. 7

V. EXPERIMENTS

  • The evaluation section reports experiments on four benchmark datasets and directs readers to its settings and results subsections.The supplied dataset passage identifies Cora and Citeseer as citation networks and LastFM and Twitch as social networks.Source: §V · p. 7, 1) Datasets · p. 7

1) Datasets:

  • The benchmarks comprise Cora and Citeseer citation networks, plus LastFM and Twitch social networks.Nodes represent papers in the citation datasets and users in the social datasets.Source: 1) Datasets · p. 7

2) GNN Models:

Across datasets and LDP mechanisms, VERITAS improves node-classification accuracy over the poisoned baseline, and ablations identify pruning as its primary defense stage. The evaluation uses multiple GNN backbones and privacy mechanisms.

2) GNN Models:

  • The evaluation considers GCN, GraphSAGE, and GAT, using two graph-convolutional layers with hidden dimension 64 and GCN as the default backbone.The models are implemented with PyTorch and PyTorch-Geometric.Source: 2) GNN Models · p. 7

3) LDP Mechanisms:

  • Feature protection is evaluated with six LDP mechanisms, while graph-structure protection perturbs the verification list using KRR.PM is the default feature mechanism; the six include 1B, LP, AG, PM, MB, and SW.Source: 3) LDP Mechanisms · p. 7

1) Effectiveness:

  • VERITAS consistently improves node-classification accuracy over the poisoned model without defense across four datasets and LDP mechanisms, with substantial utility restoration under GraphSAGE and GAT.The figure compares VERITAS with the attack baseline; Table II compares classification accuracy across GNN models.Source: Figure 3 · p. 8, 1) Effectiveness · p. 8, Table II · p. 8

4) Parameter Settings:

  • The default settings use trust granularity κ=5 and injection rate r⋆=0.01, with threshold γ and asymmetry penalty λ tuned on validation data.The injection rate is varied across five listed settings.Source: 4) Parameter Settings · p. 8

5) Evaluation Metrics:

  • For node classification, task performance is measured by test accuracy (%), with results averaged over 10 independent runs and reported with 95% confidence intervals; experiments run on an NVIDIA A800 80GB GPU.Source: 5) Evaluation Metrics · p. 8

2) Ablation Studies:

  • Removing either attestation-driven pruning or dual denoising lowers performance, with pruning’s removal causing the larger drop; the full model performs best.The ablation results characterize the two stages as complementary and indispensable.Source: 2) Ablation Studies · p. 8

3) Parameter Analysis:

VERITAS remains effective as privacy budgets and poisoning intensity vary; the surrounding discussion reviews LDP, GNNs, and locally private graph learning before concluding that VERITAS improves task utility under poisoning.

3) Parameter Analysis:

  • Accuracy improves as feature or structural privacy budgets increase, while performance remains stable at relatively low malicious-node proportions and degrades moderately as injection rate rises.Fig. 4(a) compares defense configurations; removing Stage II causes the largest performance drop, while removing Stage III also reduces accuracy.Source: 3) Parameter Analysis · pp. 8–9, Figure 4 · p. 9

A. Local Differential Privacy

  • LDP lets users perturb sensitive data before transmission, providing privacy guarantees without relying on a trusted data curator.The review names randomized response for categorical data and Laplace, Gaussian, piecewise, multi-bit, and square wave mechanisms for numerical data.Source: A. Local Differential Privacy · p. 9

B. Graph Neural Networks

  • GNNs learn graph representations by iteratively aggregating neighboring-node information, but trained models can expose attributes, membership, and links to inference attacks.The review connects these privacy risks to the broader motivation for privacy-preserving graph learning.Source: B. Graph Neural Networks · p. 9

C. Locally Private Graph Learning

  • Locally private graph learning supports collaborative learning from perturbed graph data, yet LDP obfuscation makes many centralized defenses ineffective against poisoning signals propagated by GNN aggregation.The review identifies a need for defenses tailored to the local-privacy setting.Source: C. Locally Private Graph Learning · p. 9

VII. CONCLUSION

  • Across four datasets, multiple LDP mechanisms, and GNN architectures, VERITAS consistently defends against poisoning and significantly improves task utility.The conclusion frames integrating security into locally private graph learning as important for robust privacy-preserving systems.Source: §VII · pp. 9–10

Related papers

Loading 2609.07063v1…