Smooth Anonymity for Sparse Graphs

• URL: http://arxiv.org/abs/2207.06358v2
• Date: Tue, 14 May 2024 19:34:32 GMT
• Title: Smooth Anonymity for Sparse Graphs
• Authors: Alessandro Epasto, Hossein Esfandiari, Vahab Mirrokni, Andres Munoz Medina,
• Abstract summary: differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
• Score: 69.1048938123063
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When working with user data providing well-defined privacy guarantees is paramount. In this work, we aim to manipulate and share an entire sparse dataset with a third party privately. In fact, differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets, e.g. sparse networks, as one of our main results, we prove that \emph{any} differentially private mechanism that maintains a reasonable similarity with the initial dataset is doomed to have a very weak privacy guarantee. In such situations, we need to look into other privacy notions such as $k$-anonymity. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity. We further perform an empirical evaluation to back our theoretical guarantees and show that our algorithm improves the performance in downstream machine learning tasks on anonymized data.

Related papers

• Preserving Node-level Privacy in Graph Neural Networks [8.823710998526705]
  We propose a solution that addresses the issue of node-level privacy in Graph Neural Networks (GNNs) Our protocol consists of two main components: 1) a sampling routine called HeterPoisson, which employs a specialized node sampling strategy and a series of tailored operations to generate a batch of sub-graphs with desired properties, and 2) a randomization routine that utilizes symmetric Laplace noise instead of the commonly used Gaussian noise. Our protocol enables GNN learning with good performance, as demonstrated by experiments on five real-world datasets.
  arXiv  Detail & Related papers  (2023-11-12T16:21:29Z)
• Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learning [47.042811490685324]
  Mitigating the risk of this information leakage, using state of the art differentially private algorithms, also does not come for free. In this paper, we consider a representation learning objective that various parties collaboratively refine on a federated model, with differential privacy guarantees. We observe a significant performance improvement over the prior work under the same small privacy budget.
  arXiv  Detail & Related papers  (2023-09-11T14:46:55Z)
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging [20.39986955578245]
  We introduce pairwise network differential privacy, a relaxation of Local Differential Privacy (LDP) We derive a differentially private decentralized optimization algorithm that alternates between local gradient descent steps and gossip averaging. Our results show that our algorithms amplify privacy guarantees as a function of the distance between nodes in the graph.
  arXiv  Detail & Related papers  (2022-06-10T13:32:35Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Mixed Differential Privacy in Computer Vision [133.68363478737058]
  AdaMix is an adaptive differentially private algorithm for training deep neural network classifiers using both private and public image data. A few-shot or even zero-shot learning baseline that ignores private data can outperform fine-tuning on a large private dataset.
  arXiv  Detail & Related papers  (2022-03-22T06:15:43Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Privacy Adversarial Network: Representation Learning for Mobile Data Privacy [33.75500773909694]
  A growing number of cloud-based intelligent services for mobile users require user data to be sent to the provider. Prior works either obfuscate the data, e.g. add noise and remove identity information, or send representations extracted from the data, e.g. anonymized features. This work departs from prior works in methodology: we leverage adversarial learning to a better balance between privacy and utility.
  arXiv  Detail & Related papers  (2020-06-08T09:42:04Z)

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.