Hospitals, registries and phone users often cannot hand over their raw records. A coordinator that wants to find patient subgroups across them usually gets only summaries: means, counts, or the centroids each site computed locally. Clustering methods like $k$-means depend heavily on where they start, and a coordinator that sees only summaries tends to start badly. It may place centers in empty space between real groups, or on outliers. The best current fix for privacy-protected federated clustering needs the coordinator to hold its own unlabeled data set, which a pure coordinating hub in a hospital consortium does not have.
We propose that the sites jointly build a coarse, noise-protected histogram of the data in a shared low-dimensional space, refined only where the data are not yet uniform. The coordinator then treats this histogram as a stand-in data set and picks starting centers at its density peaks, meaning cells that are both crowded and far from any more crowded cell. Clustering then proceeds from those centers with no further rounds of private communication. The point is to send the coordinator a summary of the shape of the data, including where the empty valleys are. A list of local centroids cannot show this.
Core Claim
Three ingredients exist separately. The first is private voting on server-held points, from Differentially Private Federated $k$-Means Clustering with Server-Side Data. Its central result motivates this proposal: in 80–90% of Pareto-optimal runs the best clustering used zero refinement steps, so under differential privacy (a guarantee that the output barely changes if any one record is removed, achieved by adding calibrated noise) the starting point is almost the whole game. The second is adaptive space partitioning, from Density Estimation via Discrepancy Based Adaptive Sequential Partition. That method (DSP) splits space into boxes until each box looks uniform, and found that seeding $k$-means at the densest boxes beat $k$-means++. The third is density-peak seeding with boundary merging, from Clustering by fast search and merge of local density peaks for gene expression microarray data.
Our claim is that these three can be combined into a single one-shot protocol. That protocol needs no server-side data, which FedDP-KMeans explicitly leaves open. It should also outperform centroid-summary initialization specifically when clusters are non-spherical, differ in density, or are contaminated by heavy-tailed outliers. It should match centroid-summary initialization, but not beat it, on compact Gaussian clusters. Our claim is limited to the first regime, and the experiments are designed to show both cases.
Research Program
The protocol has three stages.
In the first stage, the sites privately compute a shared projection to a low-dimensional subspace. We reuse the private projection step of FedDP-KMeans unchanged. This keeps the partition in roughly $k$ dimensions, where box-based density estimation is tractable. It also lessens the axis-alignment bias of box partitions, because the projected axes follow the main directions of the data rather than the raw features.
In the second stage, the coordinator grows a partition tree top-down without ever seeing a record. At each step it proposes a cut of a box along a coordinate. Each site returns counts for the two halves, and the coordinator receives the noised sum. The coordinator keeps splitting a box while a noisy uniformity test fails, using DSP's star-discrepancy criterion adapted to noisy counts. It stops when counts fall to the noise floor. Cut locations come from noisy medians or fixed fractions rather than DSP's data-dependent maximum gaps, because exact gap locations would leak individual coordinates.
The privacy accounting is simple. Each record falls in exactly one box per tree level, so the counts at one level compose in parallel. The total budget is the projection cost plus one count release per level, split over a fixed depth $L$. Nothing further is spent afterward. This differs from G-FKM (Greedy Centroid Initialization for Federated $K$-means), whose sites transmit local $k$-means++ centroids and cluster sizes with no density information and no privacy noise. It also differs from FedDP-Init, which needs auxiliary server points to vote on.
In the third stage, the coordinator works on the resulting map of weighted boxes. For each box $b$ it computes density $\rho_b$, the noisy count divided by box volume. It also computes $\delta_b$, the distance from box $b$ to the nearest box of higher density. Candidate centers are boxes with large $\rho_b \delta_b$. Adjacent peaks are merged using Mehmood et al.'s rule: two peaks merge if the highest density along their shared boundary is at least half the average of their peak densities. The top $k$ surviving peaks become initial centroids. Lloyd iterations then run on the map itself at no privacy cost. Optionally, a final private pass assigns points.
The map also supports a support check that matters for evidence synthesis. Jiang et al. (A critical assessment of matching-adjusted indirect comparisons in relation to target populations) show that reweighting one trial to match another's means can flip which drug looks better, and that means alone cannot reveal whether the target population lies in a region with no data. We treat this check as a secondary diagnostic, not the main contribution.
The analysis has two parts. First, we derive the error of the noisy box densities as a function of depth, $\epsilon$ and site sample sizes, building on DSP's $O(n^{-1/2})$ rate for the non-private estimator. Second, we characterize when Laplace noise on small boxes creates spurious peaks. This sets a minimum count per box that the stopping rule must respect, and it is the main failure mode we expect.
Baselines
The naive reference is random initialization followed by private federated Lloyd's iterations at the same total $\epsilon$. This is the standard pipeline that Scott et al. showed degrades as rounds accumulate noise. Beating it is necessary but uninformative.
The strongest existing method is FedDP-KMeans with server-side data (Differentially Private Federated $k$-Means Clustering with Server-Side Data). The file reports that on synthetic mixtures it "reached near-optimal (non-private) clustering costs at a low privacy budget of $\epsilon \approx 0.4$". The file gives no per-dataset cost numbers for folktables or Stack Overflow, so we will rerun their released setup. Because it uses extra data we do not allow ourselves, we treat it as an upper reference. Matching it within its confidence interval without server data counts as success. We will also run a data-free version of it in which the server points are drawn uniformly over the projected bounding box. This is the obvious way to remove its requirement, and our method must clearly beat it.
The strongest data-free summary competitor is G-FKM with Gaussian noise added to the transmitted centroids and sizes, at equal $\epsilon$. Its only reported results are that it is "comparable to Centralized K-means" in cost and adjusted Rand index (ARI), and that it needed 33% fewer iterations on MNIST; the file gives no private-setting numbers.
The ablation that isolates our key ingredient runs plain weighted $k$-means++ on the same private box map, with no density-peak selection. A second ablation replaces the adaptive tree with a fixed grid of equal total budget.
All methods use the same site splits, the same total $\epsilon$ (including any budget spent on tuning), the same projection dimension and the same number of hyperparameter configurations. Results are averaged over 20 seeds.
Why not just…?
Why not just run weighted $k$-means++ on noisy local centroids, as in a private G-FKM? This is the real threat. On compact Gaussian clusters we expect it to tie with our method. The ablation that runs weighted $k$-means++ on our own box map tests exactly this: if density-peak selection adds nothing over weighted $k$-means++ in that comparison, the contribution reduces to "send a private histogram." The case for our method rests on the outlier and varying-density settings. In those settings local $k$-means++ is known to seed on outliers (see A provable initialization and robust clustering method for general mixture models), and centroid lists hide the valleys between proposals.
Why not just give FedDP-Init synthetic or public server data? If uniform or public proxy points work as well, Gap 3 is not a real gap. We test the uniform-proxy variant directly. Our expectation is that uniform points spend votes evenly over empty space, while adaptive splitting concentrates resolution where mass lies. The results on folktables will settle this.
Why not just release a private fixed-grid histogram? Fixed grids need a number of cells exponential in dimension and waste budget on empty cells. The grid ablation measures how much the adaptive tree actually buys at equal $\epsilon$.
Proposed Experiments
We use the FedDP-KMeans benchmarks: synthetic Gaussian mixtures with up to 5,000 clients, folktables census employment data split across 51 US states as silos, and Stack Overflow embeddings across devices. We add the 68-dimensional US Census data from DSP, split across synthetic sites. To probe the regime where density matters, we use UCI Letter Recognition with Cauchy noise added and partitioned non-IID. For that dataset the centralized non-private references in the file are 32–42% mislabeling for the robust initialization-plus-clustering method of Jana et al. and 50–65% for Lloyd's. We also generate synthetic stress sets matched to the topology-mismatch and scale-heterogeneity regimes of CHB, where the reported median normalized mutual information (NMI) is about 0.53 and 0.70 respectively.
The metrics are $k$-means cost relative to non-private centralized $k$-means++, ARI and NMI where labels exist, and full cost-versus-$\epsilon$ curves.
The decisive checks are three. First, at equal $\epsilon$, density-peak seeding on the private map must beat weighted $k$-means++ on the same map in ARI on the Cauchy-noise and heterogeneous-density sets, while tying on Gaussians. Second, on folktables without server data, our method must beat uniform-proxy FedDP-Init and private G-FKM and approach FedDP-Init with server data. Third, we vary the minimum box count and test whether spurious-peak rates at small $\epsilon$ follow the predicted noise-floor threshold. If the first check fails, we will report the private adaptive histogram as the contribution and drop the density-peak claim.
References
- Differentially Private Federated $k$-Means Clustering with Server-Side Data
- Density Estimation via Discrepancy Based Adaptive Sequential Partition
- Clustering by fast search and merge of local density peaks for gene expression microarray data
- Greedy Centroid Initialization for Federated K-means
- A critical assessment of matching-adjusted indirect comparisons in relation to target populations
- A provable initialization and robust clustering method for general mixture models
- CHB: A Diagnostic Toolkit for Hardness-Aware Clustering Evaluation