Diverse Community Data for Benchmarking Data Privacy Algorithms

Aniruddha Sen, Christine Task, Dhruv Kapur, Gary Howarth, Karan BhagatNeurIPS 2023

Presented at NeurIPS 2023, this paper introduces a new framework for evaluating how well privacy-preserving algorithms handle diverse populations. It highlights a critical flaw in current deidentification methods: they often "erase" or distort minority groups because those groups are harder to protect without sacrificing data utility.

To address this, the authors introduce the Collaborative Research Cycle (CRC), a benchmarking ecosystem designed to expose how deidentification algorithms fail on diverse populations. By formalizing the concept of "subpopulation dispersal," they show that individuals with unique or independent feature combinations are often unfairly targeted by privacy-preserving techniques, leading to biased synthetic data.

The Problem: Subpopulation Dispersal

When organizations share sensitive data (like medical records or census info), they use deidentification algorithms—such as Differential Privacy or synthetic data generation—to protect individual identities. However, these algorithms aren't neutral.

The authors identify a phenomenon called subpopulation dispersal.

Visualizing subpopulation dispersal as features increase.

Imagine two groups: Group A is very homogeneous (e.g., most people have similar jobs and education levels), while Group B is very diverse (features are independent and varied). In a dataset, Group B's members will be "dispersed" into many tiny, unique categories as more features are considered.

Because privacy algorithms often work by suppressing or blurring "small-count" categories to prevent re-identification, they end up disproportionately erasing or distorting Group B. This creates a "diversity tax" where the most unique members of society are the first to be "cleaned" out of the data, leading to downstream AI models that are biased against them.

Methods and Tools

The paper contributes three main components to solve this evaluation gap:

  1. Formal Theory: The authors use information theory (Entropy and Uncertainty Coefficients) to define a Dispersal Ratio. This provides a mathematical way to predict how "identifiable" a subpopulation will be based on how independent its features are.
  2. The SDNist Tool: An open-source Python library for "metrology"—measuring the quality of deidentified data. Unlike standard metrics that just give a single accuracy score, SDNist uses visual diagnosis (PCA plots and regression heatmaps) and propensity metrics (training a classifier to distinguish between real and synthetic records).
  3. The CRC Archive: A massive repository of over 450 deidentified data samples generated by 33 different techniques, allowing researchers to compare how different "flavors" of privacy perform on the same data.

Datasets: NIST Diverse Community Excerpts

To power this research, the authors introduce the NIST Diverse Community Excerpts, curated from the 2019 U.S. Census Bureau’s American Community Survey (ACS). It includes 24 features across three geographic samples (Massachusetts, Texas, and a "National" set). Unlike standard ML datasets, these were specifically chosen because they contain "challenging" features and diverse subpopulations that trigger the dispersal issues the authors want to study.

Key Insights and Results

  • Independence is a Privacy Risk: The more "independent" a person's traits are (e.g., a rare combination of age, job, and location), the higher their dispersal ratio. This makes them an "outlier" that privacy algorithms struggle to model.
  • The "Aha" Moment on Equity: The paper proves that even if an algorithm has a "fair" privacy budget (like a fixed $\epsilon$ in Differential Privacy), the utility of the resulting data is often lower for minority groups. Privacy protection and data equity are often in direct tension.
Dispersal rates across different demographic groups and features.
  • Synthetic Data Hallucinations: The authors found that some popular generative models (like CTGAN) "hallucinate" impossible records, such as 7-year-old widows, because they fail to capture the logical constraints present in real-world diverse communities.
  • Algorithm Comparison: The authors compared several high-profile methods. MST (SmartNoise) was found to be a solid middle ground, providing decent privacy and utility. In contrast, PACSynth provided excellent privacy but at the cost of almost entirely erasing rare, dispersed records.
  • Privacy Leakage: Using a "Unique Exact Match" (UEM) metric, they showed that some "private" algorithms actually leaked 100% of certain records, reproducing the input data nearly exactly despite having formal privacy guarantees.
  • Subpopulation Bias: Visualizations showed that while a model might accurately represent majority groups, it often introduced bias in the data for minority groups, strengthening correlations that didn't exist in the original data and potentially obscuring real-world disparities.

Limitations and Future Work

The study notes a few limitations. First, the source data (ACS PUMS) already has some basic privacy measures applied by the Census Bureau, which might slightly "muddy" the ground truth. Second, the current dataset lacks relational data (like Household IDs), meaning it cannot yet test algorithms that model social networks or families. Finally, current privacy metrics like UEM are empirical; future versions of the benchmark should include more sophisticated, non-trivial re-identification attacks to truly stress-test the algorithms.

Summary updated

BibTeX
@inproceedings{sen2023diverse,
  author = {Aniruddha Sen and Christine Task and Dhruv Kapur and Gary Howarth and Karan Bhagat},
  title = {{Diverse Community Data for Benchmarking Data Privacy Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
}
Figure