CS Paper Radar

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.LG ·submitted 2026-09-07 05:38 UTC · v1
publishedbenchmark

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.

Comment
ICDM 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Data Poisoning Attacks to Locally Differentially Private Triangle Counting Protocols

cs.CR ·2026-11-18 ·Tingxuan Han, Wei Tong, Zijian Wang, Sheng Zhong
top venue similarity 0.70
Abstract · Accepted by ICDE 2027

Local differential privacy (LDP) has become a crucial paradigm for privacy-preserving graph analytics, enabling graph analytics tasks such as subgraph counting without requiring a trusted curator. However, while LDP provides strong privacy guarantees, the integrity and robustness of LDP subgraph counting protocols in the presence of malicious participants remain poorly understood. In particular, since data are randomized locally before collection, it is inherently difficult to distinguish malicious users from honest ones based solely on their submitted reports, and small, protocol-compliant local manipulations can be systematically amplified through reconstruction and calibration into large global estimation bias. In this paper, we use LDP triangle counting as a representative task to characterize the vulnerability of LDP subgraph counting to data poisoning attacks. For both non-interactive and interactive LDP triangle counting protocols, we analyze their attack surfaces and develop a unified gain-driven framework that captures how adversarial users can manipulate calibrated subgraph count estimates, which we instantiate on representative protocols of both types. Extensive experiments on four real-world graph datasets demonstrate that these attacks can significantly distort triangle count estimates across different protocols and adversarial settings. Moreover, we show that existing and straightforward defenses are insufficient to mitigate these attacks, underscoring the need for robustness mechanisms tailored to LDP subgraph counting.

0.49

Robust and Private Swarm Learning via Zero-Knowledge Validator Admission and Consensus Aggregation

cs.CR cs.AIcs.LG ·2026-11-08 ·Marco Arazzi, Mert Cihangiroglu, Antonino Nocera
similarity 0.69
Abstract

Swarm Learning improves resilience and removes the need for a single trusted coordinator by distributing model aggregation and validation across participating nodes. However, it also delegates the validation of model updates to peers whose private data may be biased, unrepresentative, or adversarial, and existing Swarm Learning protocols generally do not attest that data, leaving decentralized validation as an attack surface. We present a robust, privacy-preserving Swarm Learning framework that makes verifiable data quality the condition for admission to the learning task. A validator joins only after a zero-knowledge attestation proves, without revealing any raw sample, that a reference model ran correctly on its private data. The attested outputs also yield a label-free class profile, so the network assembles a collectively IID validator pool from individually skewed validators as accurately as an oracle with the true labels (total-variation distance to uniform 0.025, against 0.021 for the oracle and 0.21 for random selection). Admitted validators score client updates and, through a Tendermint-style Byzantine Fault Tolerant consensus, agree on a gradient mask and a quality-derived aggregation weight for each submission, replacing dataset-size weighting with a quality-aware signal. Adapting the cut-layer idea of Split Learning, a challenge-based audit lets peers re-verify that a mask was computed on the attested data without an expensive end-to-end zero-knowledge proof. Across four benchmarks under non-IID partitions the framework matches FedAvg on clean data; under a gradient-scaling attack that collapses FedAvg to random chance, it retains 94% of clean accuracy on CIFAR-100 and over 99% on FashionMNIST, where FedAvg achieves only 2.1% and 11%. The result is a private, robust, and auditable foundation for decentralized learning.

0.15

LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure

cs.DB ·2026-10-07 ·Jiawei Dong, Zhikun Zhang, Quan Yuan, Zhe Liu, Yunjun Gao
top venuecode/data similarity 0.68
Abstract · Accepted at IEEE ICDE 2027. Extended version with appendices

The widespread application of graph data inevitably brings significant privacy risks, as its unprotected use can lead to the leakage of sensitive information. These risks are particularly acute in the setting with an untrusted curator, where the data remains decentralized and each user only holds the connections to their neighbors. To mitigate such privacy risks, we adopt local differential privacy (LDP) to collect users' private information and generate a synthetic graph. However, existing methods suffer from either excessive noise injection by perturbing the local adjacency lists or significant structural information loss due to the simplistic graph encoding process. To address these issues, we propose LDPGraph, an effective graph synthesis algorithm that takes one step further by exploiting neighborhood structures under LDP. To obtain neighborhood statistics beyond degrees, LDPGraph aggregates a noisy global view from perturbed adjacency lists and combines it with projected local connections to estimate node-level triangle counts. To correct the structural inconsistency caused by separately perturbing degree and triangle count, LDPGraph jointly refines them into feasible degree-triangle targets. To reconstruct a global graph from these estimated targets, LDPGraph adopts a triangle-first strategy that first preserves local clustering structures and then fulfills remaining degree requirements. Extensive experiments on four real-world datasets and multiple commonly used graph metrics validate the superiority of LDPGraph. Source code is available at https://github.com/ZJU-TrustAID/LDPGraph.

0.44

BackDFL: A Unified Benchmark For Backdoor Attacks and Defenses In Decentralized Federated Learning

cs.LG cs.CRcs.DC ·2026-08-21 ·Mouhamed Amine Bouchiha, Gregory Blanc, Yufei Han
publishedbenchmarkposition similarity 0.67
Abstract · Accepted for presentation at the ANUBIS Workshop, co-located with ESORICS'26

Decentralized Federated Learning (DFL) promises trust-free collaborative learning by replacing the centralized parameter server with peer-to-peer model exchange. However, this architectural shift fundamentally reshapes the threat landscape. Without globally coordinated aggregation, DFL becomes particularly susceptible to backdoor attacks, in which malicious participants implant persistent hidden behaviors while maintaining high clean-task performance. In this paper, we argue that the robustness of DFL has been significantly overestimated. Existing studies rely on simplified threat models, non-adaptive adversaries, fragmented evaluation protocols, inconsistent communication topologies, and ad hoc training configurations, leading to an incomplete understanding of DFL security. To address these limitations, we present BackDFL, a unified benchmark for systematically evaluating DFL under realistic and adaptive backdoor attacks. Through extensive experiments, BackDFL exposes critical failure modes of decentralized learning. Our results demonstrate that both state-of-the-art Byzantine-robust DFL methods and adapted FL backdoor defenses fail under modest malicious participation rates (as low as 15%), especially in heterogeneous settings, while their robustness varies substantially across communication graph topologies.

0.27

NOMAI: Scalable Federated Learning with Private Weights

cs.CR ·2026-10-15 ·Yiyi Sun, Mushtari Sadia, Amrita Roy Chowdhury
similarity 0.66
Abstract

The twin goals of privacy-preserving federated learning (FL) -- harnessing distributed data while protecting the parties who contribute it -- demands three properties: model privacy, data privacy, and integrity. Achieving all three in a realistic deployment -- with a single coordinator and millions of users -- remains an open challenge that prior work has yet to fully resolve. We present NOMAI, the first scalable MPC-based FL system to provide all three guarantees simultaneously. NOMAI operates under an honest-majority assumption in the semi-honest model, with an extension to the malicious-with-abort setting. At its core, NOMAI combines a multi-committee MPC architecture with packed Shamir secret sharing, enabling SIMD-style secure computation that scales far beyond what monolithic n-party protocols can support. We further introduce ML-aware optimizations and new cryptographic primitives that substantially reduce per-user overhead. Our evaluation shows NOMAI is practically deployable at unprecedented scale: it reduces per-user computation to just <350 ms (semi-honest) and <700 ms (malicious) for per iteration of training MNIST, achieving three orders-of-magnitude improvements over prior work while seamlessly supporting populations of over 106 users. This demonstrates, for the first time, that MPC-based FL can meet the scale demands of real-world systems without compromising on privacy or integrity.

0.13

End-to-End Verifiable and Robust Federated Learning

cs.LG ·2026-09-14 ·Doryan Lesaignoux, Enrique Mármol Campos, Gabriele Spini, José L. Hernández-Ramos, Stephan Krenn
similarity 0.65
Abstract · Conference, 21 pages, 9 figures, 5 tables

Federated learning enables multiple parties to train a shared model without centralizing raw data with the help of an aggregator, but introduces integrity risks once participants or infrastructure are not fully trustworthy. Two requirements are particularly important: robustness to poisoned or Byzantine client updates, and verifiability of the aggregator so that clients or third parties can audit the reported aggregation without learning individual updates. Existing work has largely treated these goals separately, and efficient public verifiability for robust, outlier-excluding aggregation remains limited. We present a verifiable federated learning protocol that makes a robust aggregation pipeline publicly auditable. Our design combines cryptographic commitments with non-interactive zero-knowledge proofs to certify both (i) cosine-similarity-based outlier exclusion and (ii) aggregation over the selected set, without revealing individual client updates to verifiers. In experiments under representative poisoning attacks, our method maintains high accuracy, with an average accuracy loss below 4\% across the evaluated configurations, while keeping verification overhead practical: proof artifacts can be generated and verified within minutes at the scale studied. In summary, our results show that robust outlier exclusion and public verifiability can be jointly achieved in a federated learning setting.

0.16

OPFL: Optimistic Verification of Federated Learning via Empirical Boundary

cs.CR cs.AI ·2026-09-29 ·Hongxu Su, Jianzhu Yao, Xuechao Wang, Pramod Viswanath
similarity 0.65
Abstract · 15 pages, 3 figures, 9 tables

Federated learning enables multiple clients to collaboratively train models without sharing their private data. However, the lack of visibility into local training makes it difficult to verify whether clients follow the prescribed training procedure or submit malicious updates, such as model poisoning. A natural approach is to replay client training for verification. However, privacy-preserving replay produces numerical results that cannot be directly matched with local client execution because the two run in different environments. We present OPFL, an optimistic verification framework for privacy-preserving federated learning. To protect data privacy, OPFL performs replay inside secure multi-party computation (MPC). Although gradients computed on MPC and local GPUs are not bitwise identical, we observe that their absolute differences are stable and bounded. OPFL therefore calibrates an empirical boundary offline and uses it to distinguish benign numerical deviations from malicious manipulation. To reduce the cost of expensive MPC replay, OPFL adopts optimistic verification by post auditing only sampled training steps. Experiments on LeNet, BERT, and Qwen show that the boundary generalizes across datasets, input lengths, and GPUs, while achieving $0$\% ASR against model poisoning and PGD-based attacks. On a LeNet workload, at $p=0.01$, OPFL is approximately $98.6\times$ faster than full MPC-based FL and $625.5\times$ faster than ZK-based approach.

0.15

Empirical Auditing of Edge-Private Graph Generators

cs.LG stat.ML ·2026-09-21 ·Anum Fatima, Stratis Limnios, James Adams, Lukasz Szpruch, Carsten Maple +2 more
similarity 0.65
Abstract

We empirically audit privacy leakage by testing whether outputs from edge-neighbouring inputs remain distinguishable, using statistically valid lower bounds on the privacy loss witnessed by our attacks. Our framework compares direct-edge, local-structural, and GNN-based attacks through the geometry surrounding a target edge. Experiments across two generators and two networks show that privacy leakage is both mechanism- and network-dependent, with learned representations revealing information not captured by conventional local statistics.

0.10