Robustness of Locally Differentially Private Graph Analysis Against Poisoning

• URL: http://arxiv.org/abs/2210.14376v2
• Date: Wed, 10 Sep 2025 09:47:49 GMT
• Title: Robustness of Locally Differentially Private Graph Analysis Against Poisoning
• Authors: Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri,
• Abstract summary: Locally differentially private (LDP) graph analysis allows private analysis on a graph that is distributed across multiple users.<n>We study the impact of poisoning attacks for graph degree estimation protocols under LDP.<n>We design robust degree estimation protocols under LDP that can significantly reduce the impact of data poisoning and compute degree estimates with high accuracy.
• Score: 34.86995628705397
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Locally differentially private (LDP) graph analysis allows private analysis on a graph that is distributed across multiple users. However, such computations are vulnerable to data poisoning attacks where an adversary can skew the results by submitting malformed data. In this paper, we formally study the impact of poisoning attacks for graph degree estimation protocols under LDP. We make two key technical contributions. First, we observe LDP makes a protocol more vulnerable to poisoning -- the impact of poisoning is worse when the adversary can directly poison their (noisy) responses, rather than their input data. Second, we observe that graph data is naturally redundant -- every edge is shared between two users. Leveraging this data redundancy, we design robust degree estimation protocols under LDP that can significantly reduce the impact of data poisoning and compute degree estimates with high accuracy. We evaluate our proposed robust degree estimation protocols under poisoning attacks on real-world datasets to demonstrate their efficacy in practice.

Related papers

• Poisoning Attacks to Local Differential Privacy Protocols for Trajectory Data [14.934626547047763]
  Trajectory data, which tracks movements through geographic locations, is crucial for improving real-world applications.<n>Local differential privacy (LDP) offers a solution by allowing individuals to locally perturb their trajectory data before sharing it.<n>Despite its privacy benefits, LDP protocols are vulnerable to data poisoning attacks, where attackers inject fake data to manipulate aggregated results.
  arXiv  Detail & Related papers  (2025-03-06T02:31:45Z)
• Data Poisoning Attacks to Locally Differentially Private Range Query Protocols [15.664794320925562]
  Local Differential Privacy (LDP) has been widely adopted to protect user privacy in decentralized data collection.<n>Recent studies have revealed that LDP protocols are vulnerable to data poisoning attacks.<n>We present the first study on data poisoning attacks targeting LDP range query protocols.
  arXiv  Detail & Related papers  (2025-03-05T12:40:34Z)
• Data Poisoning Attacks to Local Differential Privacy Protocols for Graphs [12.565077847109974]
  This paper shows that an attacker can inject fake users into Local Differential Privacy protocols for graphs and design data poisoning attacks to degrade the quality of graph metrics.<n>As a proof of concept, we focus on data poisoning attacks on two classical graph metrics: degree centrality and clustering coefficient.<n> Experimental study on real-world datasets demonstrates that our attacks can largely degrade the quality of collected graph metrics datasets.
  arXiv  Detail & Related papers  (2024-12-23T11:16:23Z)
• PoisonCatcher: Revealing and Identifying LDP Poisoning Attacks in IIoT [13.68394346583211]
  Local Differential Privacy (LDP) is widely adopted in the Industrial Internet of Things (IIoT) due to its lightweight, decentralized, and scalable.<n>This work proposes a LDP poisoning defense for IIoT in the resource-rich aggregator.
  arXiv  Detail & Related papers  (2024-12-20T09:26:50Z)
• Data Poisoning Attacks to Locally Differentially Private Frequent Itemset Mining Protocols [13.31395140464466]
  Local differential privacy (LDP) provides a way for an untrusted data collector to aggregate users' data without violating their privacy. Various privacy-preserving data analysis tasks have been studied under the protection of LDP, such as frequency estimation, frequent itemset mining, and machine learning. Recent research has demonstrated the vulnerability of certain LDP protocols to data poisoning attacks.
  arXiv  Detail & Related papers  (2024-06-27T18:11:19Z)
• GraphCloak: Safeguarding Task-specific Knowledge within Graph-structured Data from Unauthorized Exploitation [61.80017550099027]
  Graph Neural Networks (GNNs) are increasingly prevalent in a variety of fields. Growing concerns have emerged regarding the unauthorized utilization of personal data. Recent studies have shown that imperceptible poisoning attacks are an effective method of protecting image data from such misuse. This paper introduces GraphCloak to safeguard against the unauthorized usage of graph data.
  arXiv  Detail & Related papers  (2023-10-11T00:50:55Z)
• On Practical Aspects of Aggregation Defenses against Data Poisoning Attacks [58.718697580177356]
  Attacks on deep learning models with malicious training samples are known as data poisoning. Recent advances in defense strategies against data poisoning have highlighted the effectiveness of aggregation schemes in achieving certified poisoning robustness. Here we focus on Deep Partition Aggregation, a representative aggregation defense, and assess its practical aspects, including efficiency, performance, and robustness.
  arXiv  Detail & Related papers  (2023-06-28T17:59:35Z)
• Temporal Robustness against Data Poisoning [69.01705108817785]
  Data poisoning considers cases when an adversary manipulates the behavior of machine learning algorithms through malicious training data. We propose a temporal threat model of data poisoning with two novel metrics, earliness and duration, which respectively measure how long an attack started in advance and how long an attack lasted.
  arXiv  Detail & Related papers  (2023-02-07T18:59:19Z)
• Lethal Dose Conjecture on Data Poisoning [122.83280749890078]
  Data poisoning considers an adversary that distorts the training set of machine learning algorithms for malicious purposes. In this work, we bring to light one conjecture regarding the fundamentals of data poisoning, which we call the Lethal Dose Conjecture.
  arXiv  Detail & Related papers  (2022-08-05T17:53:59Z)
• Autoregressive Perturbations for Data Poisoning [54.205200221427994]
  Data scraping from social media has led to growing concerns regarding unauthorized use of data. Data poisoning attacks have been proposed as a bulwark against scraping. We introduce autoregressive (AR) poisoning, a method that can generate poisoned data without access to the broader dataset.
  arXiv  Detail & Related papers  (2022-06-08T06:24:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.