Introduction
Differential Privacy (DP) is the gold standard for protecting individual privacy in data analysis. However, the random noise injected by DP mechanisms often results in data that violates fundamental logical or physical constraints—such as negative population counts or inconsistent hierarchical totals. This paper introduces a unified theoretical framework for Constrained Differential Privacy (CDP) by drawing parallels with AI theories of belief change.
The Two Views of Constrained DP
The authors propose that any constrained DP mechanism can be understood through one of two lenses: Belief Revision or Belief Update.
- Belief Revision (Conditioning): This view treats constraints as new information about a static world. It uses Bayesian conditioning to filter the unconstrained DP output. For linear constraints, this method is proven to be "congenial," meaning it preserves the original privacy guarantees without additional leakage. Implementation typically involves Markov Chain Monte Carlo (MCMC) methods, such as the Metropolis-Hastings algorithm.
- Belief Update (Imaging): This view treats constraints as a response to a changing world. It functions by projecting the noisy output to the nearest point in the feasible subspace (often via $L_2$-distance minimization). This is the approach used by existing systems like the US Census Bureau's TopDown algorithm.
Theoretical Properties and Composition
A significant contribution of this work is the formalization of how these two views handle privacy and composition.
As shown in the property matrix above, both views are post-processing stable but differ in their composition properties. The authors introduce Disjoint-union Composition for the Revision view and Mixture Composition for the Update view. These properties allow researchers to understand how privacy budgets are consumed when multiple constrained queries are combined.
Experimental Evaluation: NYC Taxi Data
To test these frameworks, the authors utilized the New York City Taxi Dataset (February 2022). They focused on estimating trip frequencies across a three-level hierarchy (City, Borough, and Zone), where the sum of sub-region trips must equal the parent region's total.
The experiments compared the MCMC-based conditioning approach ($M_{MH}$) against the TopDown projection algorithm. The results demonstrated that the Belief Revision (MCMC) approach consistently yielded higher utility (lower $L_1$ error) than the Belief Update (TopDown) approach across various privacy budgets ($\epsilon$). For instance, at $\epsilon = 0.5$, the MCMC method's error at the City level was significantly lower (0.013) compared to TopDown (0.036).
Conclusion and Future Directions
This paper bridges the gap between DP and belief change theory, providing a rigorous foundation for constrained mechanisms. While Belief Revision offers superior data utility, it comes with higher computational costs due to the nature of MCMC sampling. Future work aims to address these computational hurdles and explore the application of these views to data-dependent constraints and causal inference.
Summary updated