Two Views of Constrained Differential Privacy: Belief Revision and Update

Likang Liu, Keke Sun, Chunlai Zhou, Yuan Feng

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.

Framework for Constrained DP: Conditioning (Revision) vs. Imaging (Update).
  1. 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.
  2. 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.

Comparison of privacy and composition properties between Belief Revision and Belief Update.

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

Abstract

In this paper, we provide two views of constrained differential private (DP) mechanisms. The first one is as belief revision. A constrained DP mechanism is obtained by standard probabilistic conditioning, and hence can be naturally implemented by Monte Carlo algorithms. The other is as belief update. A constrained DP is defined according to l2-distance minimization postprocessing or projection and hence can be naturally implemented by optimization algorithms. The main advantage of these two perspectives is that we can make full use of the machinery of belief revision and update to show basic properties for constrained differential privacy especially some important new composition properties. Within the framework established in this paper, constrained DP algorithms in the literature can be classified either as belief revision or belief update. At the end of the paper, we demonstrate their differences especially in utility on a couple of scenarios.
BibTeX
@inproceedings{liu2023two,
  author = {Likang Liu and Keke Sun and Chunlai Zhou and Yuan Feng},
  title = {{Two Views of Constrained Differential Privacy: Belief Revision and Update}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=7Ii02SM4wz},
}
Figure