A Differentially Private Clustering Algorithm for Well-Clustered Graphs

2024-03-21 · Weiqiang He, Hendrik Fichtenberger, Pan Peng

We study differentially private (DP) algorithms for recovering clusters in well-clustered graphs, which are graphs whose vertex set can be partitioned into a small number of sets, each inducing a subgraph of high inner conductance and small outer conductance. Such graphs have widespread application as a benchmark in the theoretical analysis of spectral clustering. We provide an efficient ($\epsilon$,$\delta$)-DP algorithm tailored specifically for such graphs. Our algorithm draws inspiration from the recent work of Chen et al., who developed DP algorithms for recovery of stochastic block models in cases where the graph comprises exactly two nearly-balanced clusters. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters, and the misclassification ratio almost matches the one of the best-known non-private algorithms. We conduct experimental evaluations on datasets with known ground truth clusters to substantiate the prowess of our algorithm. We also show that any (pure) $\epsilon$-DP algorithm would result in substantial error.

📄 PDF Abstract BibTeX arXiv:2403.14332

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Differentially Private Clustered Federated Learning

2024-05-29 · Saber Malekmohammadi, Afaf Taik, Golnoosh Farnadi

Federated learning (FL), which is a decentralized machine learning (ML) approach, often incorporates differential privacy (DP) to provide rigorous data privacy guarantees. Previous works attempted to address high structu…

Clustering Fairness Federated Learning

Improving the Variance of Differentially Private Randomized Experiments through Clustering

2023-08-02 · Adel Javanmard, Vahab Mirrokni, Jean Pouget-Abadie

Estimating causal effects from randomized experiments is only possible if participants are willing to disclose their potentially sensitive responses. Differential privacy, a widely used framework for ensuring an algorith…

Causal Inference Clustering

Differentially-Private Sublinear-Time Clustering

2021-12-27 · Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee

Clustering is an essential primitive in unsupervised machine learning. We bring forth the problem of sublinear-time differentially-private clustering as a natural and well-motivated direction of research. We combine the …

Clustering

PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution

2026-05-29 · Thomas Humphries, Zinan Lin, Sergey Yekhanin arxiv

We study the problem of differentially private (DP) $k$-means clustering in Euclidean space. Previous solutions rely on summing the private data directly, which induces a sensitivity proportional to the domain. We introd…

Synthetic Data Generation

Differentially Private Correlation Clustering

2021-02-17 · Mark Bun, Marek Eliáš, Janardhan Kulkarni

Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering.…

BIG-bench Machine Learning Clustering