CS Paper Radar

Data Poisoning Attacks to Locally Differentially Private Triangle Counting Protocols

Tingxuan Han, Wei Tong, Zijian Wang, Sheng Zhong

cs.CR ·submitted 2026-11-18 01:47 UTC · v1
top venue

Abstract

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.

Comment
Accepted by ICDE 2027

Closest papers

Nearest neighbours by meaning across the whole index.

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.77
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

Trinqet: Private Triangle and Quadrangle Counting over Distributed Graphs

cs.CR ·2026-09-13 ·Mushtari Sadia, Amrita Roy Chowdhury
similarity 0.74
Abstract

Triangle and quadrangle counts are core statistics in graph analysis. Yet many real-world graphs are distributed across multiple parties and encode highly sensitive relationships, precluding direct data sharing. Secure multi-party computation (MPC) provides a principled alternative, but introduces a fundamental tension: the protocol must hide the graph's topology, forcing fully data-oblivious operations over all potential edges--while real-world graphs are extremely sparse, making most of this work wasted. We propose Trinqet, a system that resolves this tension through new MPC-friendly algorithms for private triangle and quadrangle detection. Trinqet safely exploits sparsity using a suite of novel techniques that eliminate vast numbers of unnecessary operations while preserving strong security in the malicious threat model. Trinqet supports both counting and enumeration and, in our evaluation, outperforms all five baselines by up to 10^5 in runtime.

0.37

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

cs.LG ·2026-09-07 ·Longzhu He, Li Sun, Hao Peng, Ruijie Wang, Raymond Chi-Wing Wong +1 more
publishedbenchmark similarity 0.70
Abstract · ICDM 2026

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.

0.33

Privacy-Preserving Range Counting over Local Graph Statistics

cs.DB ·2026-11-12 ·Gengda Zhao, Yizhang He, Dong Wen, Kai Wang, Ruijia Wu +1 more
similarity 0.69
Abstract

Range counting over vertex statistics supports contact analysis, community profiling, and reputation screening. However, releasing exact range counts can disclose sensitive edges to an adversary with background knowledge. We study this problem under edge local differential privacy (edge LDP), where each vertex randomizes its report before sending it to an untrusted curator. We develop a layered framework that connects statistic estimation, direct range estimation, and adaptive estimator selection. Statistic-estimation methods provide complementary scalar estimators with explicit loss analyses, while indicator-estimation methods privatize range indicators directly. We next propose Bounded Conditional Range Inversion (BCRI), which derives unbiased range estimates from reusable bounded geometric reports through an explicit local inverse. Its boundary-conditioned estimator achieves no larger expected L2 loss than the unbounded inverse, and histogram preprocessing supports constant-time queries. The same reports also provide a nonnegative, unbiased variance estimate for every answer. At the center of the framework, Adaptive Estimator Selection (AES) privately predicts bias, variance, and covariance to combine BCRI with a conditional estimator from the same transcript. Experiments on diverse real-world graph tasks demonstrate the accuracy, efficiency, and workload scalability of the proposed framework.

0.18

FedGraph: Defending Federated Large Language Model Fine-Tuning Against Backdoor Attacks via Graph-Based Aggregation

cs.CR cs.AI ·2026-10-13 ·Xi Chen, Chunyi Zhou, Rui Zeng, Xiaogang Xu, Zhe Liu +1 more
published similarity 0.67
Abstract · Accepted at the ICLR 2026 Workshop on Principled Design for Trustworthy AI. This is an author-owned preprint, not the official proceedings v…

Federated fine-tuning of large language models (LLMs) allows multiple clients to collaboratively adapt models without sharing raw data, offering strong privacy benefits. However, this setting is highly vulnerable to backdoor attacks, in which malicious clients manipulate their updates to induce targeted behaviors while maintaining normal performance on benign inputs. In this work, we make a key observation specific to federated LLM fine-tuning: malicious clients tend to exhibit strong consistency in their model updates, whereas benign clients produce more diverse and dispersed updates. This structural difference is not well captured by existing defense methods, which typically rely on direct anomaly detection in high-dimensional parameter space and therefore struggle in the presence of entangled LLM updates. Motivated by this observation, we propose FedGraph, a graph-based aggregation framework that explicitly models relationships among client updates. By representing clients as nodes in a dynamically constructed graph and extracting structural features that characterize their relative positions and interactions, FedGraph derives compact client representations that effectively separate malicious and benign behaviors. These representations are then used to identify and suppress malicious contributions during aggregation. Extensive experiments demonstrate that FedGraph significantly improves backdoor defense. It consistently reduces attack success rates to below 10% while achieving high detection accuracy (95.5% on average) and a low false positive rate (2.33%), substantially outperforming existing federated learning defenses.

0.25

Link Inference Attack on Privacy-Preserving Knowledge Graphs

cs.CR ·2026-09-30 ·Emna Bouguerra, Ibtissam Harrouche, Ferran Alborch, Melek Önen
similarity 0.66
Abstract

Knowledge Graphs (KGs) are widely used to store and share structured information across sensitive domains such as healthcare, fi- nance, and social networks. A common privacy practice is to delete sen- sitive relations before publishing the graph, under the assumption that removing edges is sufficient to prevent their recovery. In this paper, we challenge this assumption and show that even when a relation is fully or partially hidden, its existence leaves structural traces in the public graph that can be exploited to recover it with high accuracy. To this end, we propose a link inference attack that operates on the topology of the public graph, and evaluate it under two privacy scenarios that differ in how the adversary exploits the knowledge available to him. In the first setting where the adversary exploits all topological information, the attack achieves near-perfect discrimination (AP = 0.949, ROC-AUC = 0.999), while in the more realistic one where the adversary makes use of some semantic information, it recovers up to 74% of hidden edges. Build- ing on these results, we further conduct a structural analysis to identify which topological properties of the graph drive the attack success, re- vealing that privacy risk is not uniform across entities and that certain structural patterns make specific relations significantly more vulnerable to inference than others.

0.15

Revisiting Continuous Noise Sampling for Multi-Party Differential Privacy

cs.CR ·2026-08-27 ·Yucheng Fu, Tianhao Wang
similarity 0.66
Abstract

Combining secure multi-party computation (MPC) with differential privacy (DP) enables multiple parties to release aggregate statistics without a trusted curator, and the core primitive is the protocol to sample noise from a continuous distribution under finite-precision arithmetic. In this paper, we revisit the continuous noise sampling protocols and present several improvements in both security and efficiency. We start by identifying a vulnerability in widely used sample-and-scale constructions. We demonstrate that the scaling operation in arithmetic circuits confines the noise to a sparse, publicly known set of values, so that an adversary can observe the released noisy queries and decide which dataset produced them. As concrete demonstrations, we instantiate attacks on two systems employing such ``flawed'' sampling protocols: Orchard (OSDI'20) for DP secure aggregation and DP-BREM$^+$ (USENIX Sec'25) for DP federated learning. We report a near-$100\%$ attack success rate on both systems, under any noise scaler $s\geq 2$ used in practice. The leakage we reveal is intrinsic to the scaling operation, and direct repairs either substantially sacrifice utility or add significant precision bits to make the sampling more expensive. To address the security and efficiency issues together, we turn to discrete sampling at the granularity of individual biased bits. We make several optimizations to the sampler and prove its security. Our implementation achieves $4\times \sim 612\times$ speedup over existing secure discrete samplers and orders-of-magnitude speedup over the insecure sample-and-scale paradigm, with negligible utility loss compared to the ideal continuous mechanism.

0.38

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