Abstract
Sharing sensitive tabular data is critical for research but poses significant privacy risks. Traditional de-identification methods often degrade data utility, while modern deep-learning-based generative models are computationally expensive and prone to "memorization." This paper presents $\epsilon$-PrivateSMOTE, a lightweight synthetic data generation tool that combines interpolation heuristics with Differential Privacy (DP). By targeting only high-risk data points for synthesis, the method achieves a 9x speedup over state-of-the-art generative models like PATE-GAN while maintaining high predictive accuracy and robust privacy guarantees.
Introduction
The proliferation of data-driven decision-making has increased the demand for sharing sensitive datasets, such as medical records and financial histories. However, traditional "de-identification" techniques—like generalization and suppression—often fail to provide adequate protection against re-identification attacks or severely limit the data's utility for machine learning.
While Generative Adversarial Networks (GANs) and Variational Autoencoders (VAEs) have emerged as powerful tools for creating synthetic datasets, they face a "Goldilocks" problem: they are either too computationally intensive for many organizations or they inadvertently "memorize" training data, leading to privacy leaks. Furthermore, integrating Differential Privacy (DP)—the gold standard for mathematical privacy guarantees—into these complex architectures frequently results in a significant drop in model accuracy. This research addresses these challenges by introducing a targeted, efficient synthesis method that finds the "sweet spot" where data remains private, useful, and inexpensive to process.
Methodology: $\epsilon$-PrivateSMOTE
The proposed method, $\epsilon$-PrivateSMOTE, adapts the Synthetic Minority Over-sampling Technique (SMOTE) for privacy preservation rather than class imbalance. Rather than synthesizing the entire dataset, it focuses on records that pose the highest re-identification risk.
1. High-Risk Selection
The algorithm first identifies "high-risk" individuals—those who are easily "singled out" due to unique combinations of Quasi-Identifiers (QIs) like age, zip code, and gender. These records are characterized by low $k$-anonymity, making them vulnerable to linkability attacks.
2. Noise-Induced Interpolation
For these identified high-risk cases, the tool finds their nearest neighbors and generates new synthetic data points through interpolation. This process creates "look-alikes" that mask the original unique records, effectively obfuscating the outliers.
3. Differential Privacy Integration
To provide formal mathematical privacy guarantees, the method incorporates the Laplace mechanism. Noise is calibrated according to a privacy budget ($\epsilon$) and injected during the interpolation process. This ensures that the resulting synthetic points are statistically indistinguishable from the original data, satisfying the requirements of Differential Privacy.
4. Handling Diverse Attributes
The algorithm is designed for heterogeneous tabular data, handling numerical attributes via interpolation and nominal/categorical attributes through randomized selection from the record's neighborhood.
Experimental Evaluation
The researchers evaluated $\epsilon$-PrivateSMOTE using 15 diverse classification datasets from the OpenML repository. These datasets covered various real-world scenarios, including pathology identification, housing characterization, and banking behavior. The datasets ranged in size from approximately 1,000 to 15,500 instances, with attribute counts between 5 and 103, providing a robust test for scalability and generalizability.
Key Results and Insights
Efficiency and Resource Utilization
$\epsilon$-PrivateSMOTE demonstrated significant performance advantages over deep learning alternatives. It achieved at least a 9x speedup compared to PATE-GAN (a leading DP-generative model) and required 1.7x to 2.1x less memory. Because it does not rely on complex neural architectures or backpropagation, the tool can run entirely on standard CPUs, making privacy-preserving data sharing accessible to organizations without expensive GPU clusters.
Predictive Utility
A primary goal of synthetic data is to maintain the utility of the original dataset for downstream machine learning tasks. In many test cases, models trained on data synthesized by $\epsilon$-PrivateSMOTE achieved an Area Under the Curve (AUC) nearly identical to models trained on the original, unprotected data. Using the Bayes Sign Test, the authors found a 60% probability that their method is "practically equivalent" to an ideal oracle model—far higher than the <15% score achieved by other generative techniques.
Privacy Protection
The method effectively mitigated "Linkability Risk," reducing the probability of an attacker successfully matching a synthetic record to a real individual to near zero. By focusing obfuscation efforts on the most vulnerable records (targeted obfuscation), the method preserves the integrity of "safe" records while securing the overall dataset.
Limitations and Future Work
Despite its advantages, the authors identify several areas for future research:
- QI Selection: The process currently requires manual identification of Quasi-Identifiers by a human expert, which may lead to risks if identifying attributes are overlooked.
- High-Dimensionality: Further study is needed to assess performance on extremely high-dimensional datasets with thousands of attributes.
- Outlier Persistence: While the method targets high-risk cases, some extreme outliers might still persist in a way that could be exploited by sophisticated inference attacks.
- Data Modality: The current implementation is restricted to tabular data and is not applicable to unstructured formats like images or text.
Conclusion
$\epsilon$-PrivateSMOTE offers a compelling alternative to heavy-weight generative models for privacy-preserving data sharing. By leveraging simple interpolation heuristics and targeted Differential Privacy, it provides a fast, resource-efficient, and accurate solution for managing re-identification risks in tabular datasets. This research demonstrates that targeted obfuscation can outperform global synthesis in both speed and utility.
Summary updated