More Like this

1. Triangle Counting with Local Edge Differential Privacy

   https://doi.org/10.4230/LIPICS.ICALP.2023.52  

   Eden, Talya; Liu, Quanquan C.; Raskhodnikova, Sofya; Smith, Adam (January 2023, Leibniz International Proceedings in Informatics (LIPIcs):50th International Colloquium on Automata, Languages, and Programming (ICALP 2023))

   Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)

   Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the noninteractive and interactive local model with edge differential privacy (that, intuitively, requires that the outputs of the algorithm on graphs that differ in one edge be indistinguishable). In this model, each party’s local view consists of the adjacency list of one vertex. In the noninteractive model, we prove that additive Ω(n²) error is necessary, where n is the number of nodes. This lower bound is our main technical contribution. It uses a reconstruction attack with a new class of linear queries and a novel mix-and-match strategy of running the local randomizers with different completions of their adjacency lists. It matches the additive error of the algorithm based on Randomized Response, proposed by Imola, Murakami and Chaudhuri (USENIX2021) and analyzed by Imola, Murakami and Chaudhuri (CCS2022) for constant ε. We use a different postprocessing of Randomized Response and provide tight bounds on the variance of the resulting algorithm. In the interactive setting, we prove a lower bound of Ω(n^{3/2}) on the additive error. Previously, no hardness results were known for interactive, edge-private algorithms in the local model, except for those that follow trivially from the results for the central model. Our work significantly improves on the state of the art in differentially private graph analysis in the local model. 

   more » « less
2. Triangle Counting with Local Edge Differential Privacy

   Eden, Talya; Liu, Quanquan C.; Raskhodnikova, Sofya; Smith, Adam D. (January 2023, International Colloquium on Automata, Languages, and Programming)

   Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the noninteractive and interactive local model with edge differential privacy (that, intuitively, requires that the outputs of the algorithm on graphs that differ in one edge be indistinguishable). In this model, each party’s local view consists of the adjacency list of one vertex. In the noninteractive model, we prove that additive Ω(n^2) error is necessary, where n is the number of nodes. This lower bound is our main technical contribution. It uses a reconstruction attack with a new class of linear queries and a novel mix-and-match strategy of running the local randomizers with different completions of their adjacency lists. It matches the additive error of the algorithm based on Randomized Response, proposed by Imola, Murakami and Chaudhuri (USENIX2021) and analyzed by Imola, Murakami and Chaudhuri (CCS2022) for constant ε. We use a different postprocessing of Randomized Response and provide tight bounds on the variance of the resulting algorithm. In the interactive setting, we prove a lower bound of Ω(n3/2) on the additive error. Previously, no hardness results were known for interactive, edge-private algorithms in the local model, except for those that follow trivially from the results for the central model. Our work significantly improves on the state of the art in differentially private graph analysis in the local model. 

   more » « less
3. Practical and Accurate Local Edge Differentially Private Graph Algorithms

   https://doi.org/10.14778/3749646.3749687  

   Mundra, Pranay; Papamanthou, Charalampos; Shun, Julian; Liu, Quanquan C (July 2025, Proceedings of the VLDB Endowment)

   The rise of massive networks across diverse domains necessitates sophisticated graph analytics, often involving sensitive data and raising privacy concerns. This paper addresses these challenges usinglocal differential privacy (LDP), which enforces privacy at the individual level, whereno third-party entity is trusted, unlike centralized models that assume a trusted curator. We introduce novel LDP algorithms for two fundamental graph statistics:k-core decomposition and triangle counting. Our approach leverages input-dependent private graph properties—specifically degeneracy and maximum degree—to improve theoretical utility. Unlike prior methods, our error bounds depend on the maximum degree rather than the total edge count, yielding significantly tighter guarantees. For triangle counting, we improve on the work of Imola, Murakami, and Chaudhury [USENIX Security '21, '22], which bounds error in terms of edge count. Our algorithm instead achieves bounds based on degeneracy by leveraging a private out-degree orientation, a refined variant of Eden et al.'s randomized response technique [ICALP '23], and a novel analysis, yielding stronger guarantees than prior work. Beyond theoretical gains, we are the first to evaluate local DP algorithms in a distributed simulation, unlike prior work tested on a single processor. Experiments on real-world graphs show substantial accuracy gains: ourk-core decomposition achieves errors within 3xof exact values, far outperforming the 131x error in the baseline of Dhulipala et al. [FOCS '22]. Our triangle counting algorithm reduces multiplicative approximation errors by up tosix orders of magnitude, while maintaining competitive runtime. 

   more » « less
4. Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

   https://doi.org/10.1609/aaai.v36i6.20565  

   Chaturvedi, Anamay; Jones, Matthew; Nguyen, Huy L. (January 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   Given a data set of size n in d'-dimensional Euclidean space, the k-means problem asks for a set of k points (called centers) such that the sum of the l_2^2-distances between the data points and the set of centers is minimized. Previous work on this problem in the local differential privacy setting shows how to achieve multiplicative approximation factors arbitrarily close to optimal, but suffers high additive error. The additive error has also been seen to be an issue in implementations of differentially private k-means clustering algorithms in both the central and local settings. In this work, we introduce a new locally private k-means clustering algorithm that achieves near-optimal additive error whilst retaining constant multiplicative approximation factors and round complexity. Concretely, given any c>sqrt(2), our algorithm achieves O(k^(1 + O(1/(2c^2-1))) * sqrt(d' n) * log d' * poly log n) additive error with an O(c^2) multiplicative approximation factor. 

   more » « less
5. Differentially Private Clustering via Maximum Coverage

   Jones, Matthew; Nguyen, Huy L.; Nguyen, Thy D (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   This paper studies the problem of clustering in metric spaces while preserving the privacy of individual data. Specifically, we examine differentially private variants of the k-medians and Euclidean k-means problems. We present polynomial algorithms with constant multiplicative error and lower additive error than the previous state-of-the-art for each problem. Additionally, our algorithms use a clustering algorithm without differential privacy as a black-box. This allows practitioners to control the trade-off between runtime and approximation factor by choosing a suitable clustering algorithm to use. 

   more » « less