Abstract
This study presents the first differentially private and fair clustering method, built on the recently proposed density-based fair clustering approach. The method addresses the limitations of fair clustering algorithms that necessitate the use of sensitive personal information during training or inference phases. Two novel solutions, the Gaussian mixture density function and Voronoi cell, are proposed to enhance the method's performance in terms of privacy, fairness, and utility compared to previous methods. The experimental results on both synthetic and real-world data confirm the compatibility of the proposed method with differential privacy, achieving a better fairness-utility trade-off than existing methods when privacy is not considered. Moreover, the proposed method requires significantly less computation time, being at least 3.7 times faster than the state-of-the-art.
Introduction
In unsupervised learning, biased clustering can lead to discriminatory outcomes, such as unfairly excluding minority groups from targeted marketing or resource allocation. To address this, researchers developed "fair clustering" algorithms, which typically rely on "fairlet decomposition"—a technique that groups data into small, demographically balanced micro-clusters (fairlets) before standard clustering.
However, fairlet decomposition requires repeated access to sensitive demographic variables, making it fundamentally incompatible with Differential Privacy (DP), the gold standard for data privacy. Furthermore, existing density-based fair clustering methods rely on computationally expensive kernel-based support functions that struggle to scale and fail in high-dimensional spaces. This paper bridges the gap by proposing a fast, density-based fair clustering method that strictly adheres to DP.
Methodology
The proposed method overhauls the traditional density-based fair clustering pipeline with three key innovations:
- Gaussian Mixtures (GMs) for Density Estimation: Instead of using Support Vector Domain Description (SVDD), the authors use GMs. GMs are much faster to train, scale linearly with the number of samples, and can easily be made differentially private using existing DP-EM (Expectation-Maximization) algorithms.
- Voronoi Cells and Bridging Points: Traditional density clustering finds "Transition Points" (TPs) between "basin cells" to determine if two clusters are adjacent—a process that is computationally intensive in high dimensions. The authors replace this by calculating the Voronoi cells of the GM centers. They define "Bridging Points" (BPs) at the intersections of these Voronoi cells, providing a mathematically simpler and highly efficient way to measure the distance and density between adjacent clusters.
- Differentially Private Fair Labeling (FLDP): To merge clusters fairly without leaking sensitive data, the algorithm calculates the demographic balance of the initial, disjoint clusters. It applies the Laplace mechanism to add noise only to the aggregate sum of sensitive variables in these initial clusters. Because of DP's "post-processing property," the subsequent hierarchical merging of these clusters consumes zero additional privacy budget.
Experimental Evaluation
The authors evaluated their method on a mix of synthetic and real-world datasets, including Twomoon (non-convex clusters), 18-Gaussian (convex blobs), and standard benchmarks like the Bank, Adult, and Diabetes datasets from the UCI Machine Learning Repository.
Key Results
- Massive Speedups: The proposed method is exceptionally fast, performing at least 3.7x faster than the quickest baseline (FairScale) and up to 3,000x faster than traditional Fairlet methods. On the Twomoon dataset, it outperformed the baseline density-based method (FairSVC) by 20-30x.
- Superior Fairness-Utility Trade-off: Even without DP enabled, the method achieved better Silhouette scores and lower Davies-Bouldin indices than most baselines, while maintaining high demographic balance.
- High Resilience to Privacy Noise: When strict privacy was enforced ($\epsilon = 0.001$), the proposed method maintained a balance score of around 0.2 on the Adult dataset. In contrast, the baseline FairSVC algorithm's balance plummeted to near zero under the same privacy constraints.
Conclusion
While the proposed method significantly improves speed and privacy, the authors note that it can produce clusters of unequal sizes. This can artificially inflate certain intra-cluster error metrics, making the clustering appear slightly worse on paper even if the actual groupings are logical. Future work suggests combining DP with cryptographic techniques—such as homomorphic encryption and secure multi-party computation—to further protect input privacy, particularly in cloud environments where the data owner and the modeler are different entities.
Summary updated