Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions

• URL: http://arxiv.org/abs/2312.07055v1
• Date: Tue, 12 Dec 2023 08:12:18 GMT
• Title: Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions
• Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn and Tetsuo Shibuya
• Abstract summary: We suggest the use of hash functions to cut down the communication costs when counting subgraphs under edge local differential privacy. With a sampling rate of $s$, our method can cut communication costs by a factor of $s2$.
• Score: 3.1815791977708834
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We suggest the use of hash functions to cut down the communication costs when counting subgraphs under edge local differential privacy. While various algorithms exist for computing graph statistics, including the count of subgraphs, under the edge local differential privacy, many suffer with high communication costs, making them less efficient for large graphs. Though data compression is a typical approach in differential privacy, its application in local differential privacy requires a form of compression that every node can reproduce. In our study, we introduce linear congruence hashing. With a sampling rate of $s$, our method can cut communication costs by a factor of $s^2$, albeit at the cost of increasing variance in the published graph statistic by a factor of $s$. The experimental results indicate that, when matched for communication costs, our method achieves a reduction in the $\ell_2$-error for triangle counts by up to 1000 times compared to the performance of leading algorithms.

Related papers

• Communication-Efficient Publication of Sparse Vectors under Differential Privacy [2.9123921488295768]
  We propose a differentially private algorithm for publishing matrices aggregated from sparse vectors.<n>Our algorithm significantly reduces this cost to $O(varepsilon m)$, where $varepsilon$ is the privacy budget.<n>We theoretically prove that our method yields results identical to those of randomized response.
  arXiv  Detail & Related papers  (2025-06-25T08:25:46Z)
• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  We study the problem of computing pairwise statistics, i.e., ones of the form $binomn2-1 sum_i ne j f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc.
  arXiv  Detail & Related papers  (2024-06-24T04:06:09Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
  We show that a simple invocation of $textttAboveThreshold$ can give more accurate and robust estimates on the highest quantiles. We show that an improved analysis of $textttAboveThreshold$ can improve the privacy guarantees for the widely used Sparse Vector Technique.
  arXiv  Detail & Related papers  (2023-05-02T03:23:07Z)
• Privacy Amplification via Shuffling: Unified, Simplified, and Tightened [20.10078781197001]
  We propose a comprehensive framework for privacy amplification in both single-message and multi-message shuffle protocols. Our theoretical results demonstrate that our framework provides tighter bounds, especially for local randomizers with extremal probability design. Our bounds also result in a remarkably efficient $tildeO(n)$ algorithm that numerically amplifies privacy in less than $10$ seconds for $n=108$ users.
  arXiv  Detail & Related papers  (2023-04-11T06:27:25Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  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.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• 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)
• Differentially Private Quantiles [12.917299605014419]
  We propose an instance of the exponential mechanism that simultaneously estimates $m$ quantiles from $n$ data points. Our method significantly outperforms the current state of the art on both real and synthetic data.
  arXiv  Detail & Related papers  (2021-02-16T16:02:59Z)
• BUDS: Balancing Utility and Differential Privacy by Shuffling [3.618133010429131]
  Balancing utility and differential privacy by shuffling or textitBUDS is an approach towards crowd-sourced, statistical databases. New algorithm is proposed using one-hot encoding and iterative shuffling with the loss estimation and risk minimization techniques. During empirical test of balanced utility and privacy, BUDS produces $epsilon = 0.02$ which is a very promising result.
  arXiv  Detail & Related papers  (2020-06-07T11:39:13Z)

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.