Privacy-Preserving Synthetic Datasets Over Weakly Constrained Domains

Luke Rodriguez, Bill HowearXiv 2018 · arXiv

Introduction

Differential privacy (DP) is widely regarded as the gold standard for protecting individual privacy in data sharing. However, standard DP mechanisms often rely on a critical, yet frequently overlooked, assumption: the availability of a well-defined global domain. In many real-world scenarios, such as free-text fields or large categorical sets, the domain is "weakly constrained"—it is either unknown or prohibitively large.

Applying traditional DP to these domains presents a significant challenge. If a researcher only includes values observed in the raw data in their synthetic output, they risk leaking information about rare individuals. Conversely, adding noise to every possible value in a massive domain (e.g., every possible English word) is computationally infeasible and destroys data utility. This paper introduces CatHist, an algorithm designed to handle such weakly constrained domains efficiently while maintaining rigorous privacy guarantees.

The CatHist Algorithm

The core innovation of CatHist is the move away from materializing every possible bin in a histogram. The authors first establish the Bad Bins Theorem, proving that any DP mechanism must have a non-zero probability of returning elements from outside the "active domain" (the values present in the data). Failing to do so creates a "zero-probability trap" where the absence of a value reveals its absence in the original dataset.

CatHist addresses this by analytically modeling the unrepresented part of the domain as a probability distribution. The algorithm operates through a thresholding and "pollution" process:

  1. Thresholding: It calculates a threshold ($\tau$) based on the domain size and a user-defined tolerance parameter, $\rho$.
  2. Filtering: Laplace noise is added to real category counts; those falling below $\tau$ are discarded.
  3. Pollution: The dataset is augmented with a mathematically determined number of random "fake" bins from the global domain, ensuring that the output distribution remains private.
Sensitivity to threshold selection: CatHist filters low-frequency active domain values and introduces noise-induced data to maintain privacy.

Experimental Setup

The researchers evaluated CatHist using the UCI Adult dataset, focusing on three attributes: 'Sex' (small domain), 'Workclass' (long-tailed distribution), and 'Marital-status' (medium categorical domain). To simulate weakly constrained environments, they artificially expanded the domains to include hundreds of thousands or even billions of potential values (e.g., treating 'Sex' as if its domain were all English words).

Results and Discussion

The performance was measured using a Fidelity (F) metric, comparing the synthetic distribution to the original active categories.

Fidelity across 'sex', 'workclass', and 'marital-status' as a function of tolerance (ρ) and privacy budget (ε).

The results highlight several key insights:

  • Domain Support Matters: Attributes with high support, like 'Sex', maintained near 100% fidelity because their real counts remained significantly higher than the noise threshold.
  • The Long-Tail Challenge: 'Workclass' showed lower fidelity, particularly at high privacy levels (low $\epsilon$). In long-tailed distributions, rare but legitimate values are often indistinguishable from noise and are filtered out.
  • Tolerance Trade-offs: Increasing the tolerance for randomness ($\rho$) generally improved fidelity. A higher $\rho$ lowers the threshold $\tau$, allowing more low-count real categories to be preserved, albeit at the cost of including more "pollution" in the synthetic data.

Conclusion

CatHist provides a computationally efficient path for generating differentially private synthetic data in open domains. By replacing the exhaustive materialization of bins with analytical modeling, it avoids the computational pitfalls of massive domains. However, a trade-off remains: to protect privacy in large domains, users must accept a degree of "pollution" in the form of random values. Future work will explore extending this approach to continuous data and multi-dimensional correlations.

Summary updated

Abstract

Techniques to deliver privacy-preserving synthetic datasets take a sensitive dataset as input and produce a similar dataset as output while maintaining differential privacy. These approaches have the potential to improve data sharing and reuse, but they must be accessible to non-experts and tolerant of realistic data. Existing approaches make an implicit assumption that the active domain of the dataset is similar to the global domain, potentially violating differential privacy. In this paper, we present an algorithm for generating differentially private synthetic data over the large, weakly constrained domains we find in realistic open data situations. Our algorithm models the unrepresented domain analytically as a probability distribution to adjust the output and compute noise, avoiding the need to compute the full domain explicitly. We formulate the tradeoff between privacy and utility in terms of a "tolerance for randomness" parameter that does not require users to inspect the data to set. Finally, we show that the algorithm produces sensible results on real datasets.
BibTeX
@misc{rodriguez2018privacy,
  author = {Luke Rodriguez and Bill Howe},
  title = {{Privacy-Preserving Synthetic Datasets Over Weakly Constrained Domains}},
  year = {2018},
  eprint = {1808.07603},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.07603},
}
Figure