On the Optimal Number of Grids for Differentially Private Non-Interactive $K$-Means Clustering

• URL: http://arxiv.org/abs/2603.26963v1
• Date: Fri, 27 Mar 2026 20:10:59 GMT
• Title: On the Optimal Number of Grids for Differentially Private Non-Interactive $K$-Means Clustering
• Abstract summary: $K$-means clustering enables releasing cluster centers derived from a dataset while protecting the privacy of the individuals.<n>We propose a refined grid-size selection rule derived by minimizing an upper bound on the expected deviation in the K-means objective function.<n>Our grid resolution differs both in its dependence on the number of clusters and in the scaling with dataset size and privacy budget.
• Score: 4.840369931441299
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Differentially private $K$-means clustering enables releasing cluster centers derived from a dataset while protecting the privacy of the individuals. Non-interactive clustering techniques based on privatized histograms are attractive because the released data synopsis can be reused for other downstream tasks without additional privacy loss. The choice of the number of grids for discretizing the data points is crucial, as it directly controls the quantization bias and the amount of noise injected to preserve privacy. The widely adopted strategy selects a grid size that is independent of the number of clusters and also relies on empirical tuning. In this work, we revisit this choice and propose a refined grid-size selection rule derived by minimizing an upper bound on the expected deviation in the K-means objective function, leading to a more principled discretization strategy for non-interactive private clustering. Compared to prior work, our grid resolution differs both in its dependence on the number of clusters and in the scaling with dataset size and privacy budget. Extensive numerical results elucidate that the proposed strategy results in accurate clustering compared to the state-of-the-art techniques, even under tight privacy budgets.

Related papers

• Towards Personalized Differentially Private Learning for Decentralized Local Graphs [62.244412935520025]
  Local Differential Privacy (LDP) has emerged as a promising solution for privacy-preserving data collection without relying on trusted servers.<n>Existing LDP-based graph learning methods typically assume uniform privacy requirements across users.<n>We propose PPGNN, a personalized differentially private framework for decentralized graph data.
  arXiv  Detail & Related papers  (2026-07-06T08:07:48Z)
• CNMBI: Determining the Number of Clusters Using Center Pairwise Matching and Boundary Filtering [10.865555707958057]
  We propose an approach named CNMBI that exploits the distribution information inherent in the data space.<n>We find that different samples have different confidence levels and thereby actively remove low-confidence ones.<n> CNMBI is robust and allows for more flexibility in the dimension and shape of the target data.
  arXiv  Detail & Related papers  (2026-03-23T07:43:03Z)
• Towards Federated Clustering: A Client-wise Private Graph Aggregation Framework [57.04850867402913]
  Federated clustering addresses the challenge of extracting patterns from decentralized, unlabeled data.<n>We propose Structural Privacy-Preserving Federated Graph Clustering (SPP-FGC), a novel algorithm that innovatively leverages local structural graphs as the primary medium for privacy-preserving knowledge sharing.<n>Our framework achieves state-of-the-art performance, improving clustering accuracy by up to 10% (NMI) over federated baselines while maintaining provable privacy guarantees.
  arXiv  Detail & Related papers  (2025-11-14T03:05:22Z)
• Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering [0.0]
  Graph clustering aims to process graph-structured data while protecting individual privacy.<n>We construct a differentially private and interpretable graph clustering approach based on metric embedding.<n>Our proposed framework outperforms existing methods in various clustering metrics while strictly ensuring privacy.
  arXiv  Detail & Related papers  (2025-09-07T21:28:23Z)
• Differentially Private Federated Clustering with Random Rebalancing [9.331231828491461]
  Federated clustering aims to group similar clients into clusters and produce one model for each cluster.<n>We propose RR-Cluster, that can be viewed as a light-weight add-on to many federated clustering algorithms.<n>We analyze the tradeoffs between decreased privacy noise variance and potentially increased bias from incorrect assignments.
  arXiv  Detail & Related papers  (2025-08-08T09:56:47Z)
• Differentially Private Federated $k$-Means Clustering with Server-Side Data [19.962475029447127]
  FedDP-KMeans is an algorithm for $k$-means clustering that is fully-federated as well as differentially private.<n>Our algorithm achieves excellent results on synthetic and real-world benchmark tasks.
  arXiv  Detail & Related papers  (2025-06-04T14:53:25Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• DPM: Clustering Sensitive Data through Separation [2.2179058122448922]
  We present a privacy-preserving clustering algorithm called DPM that separates a data set into clusters based on a geometrical clustering approach. We show that DPM achieves state-of-the-art utility on the standard clustering metrics and yields a clustering result much closer to that of the popular non-private KMeans algorithm.
  arXiv  Detail & Related papers  (2023-07-06T13:12:19Z)
• Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
  clustering clusters (FedC) problem aims to accurately partition unlabeled data samples distributed over massive clients into finite clients under the orchestration of a server. We propose a novel FedC algorithm using differential privacy convergence technique, referred to as DP-Fed, in which partial participation and multiple clients are also considered. Various attributes of the proposed DP-Fed are obtained through theoretical analyses of privacy protection, especially for the case of non-identically and independently distributed (non-i.i.d.) data.
  arXiv  Detail & Related papers  (2023-01-03T05:38:43Z)
• Differentially Private Vertical Federated Clustering [13.27934054846057]
  In many applications, multiple parties have private data regarding the same set of users but on disjoint sets of attributes. To enable model learning while protecting the privacy of the data subjects, we need vertical federated learning (VFL) techniques. The algorithm proposed in this paper is the first practical solution for differentially private vertical federated k-means clustering.
  arXiv  Detail & Related papers  (2022-08-02T19:23:48Z)
• 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)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. We provide implementable differentially private clustering algorithms that provide utility when the data is "easy" We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
  arXiv  Detail & Related papers  (2021-12-29T08:13:56Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)

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.