Incorporating Item Frequency for Differentially Private Set Union

Ricardo Silva Carvalho, Ke Wang, Lovedeep GondaraAAAI 2022 · OpenReview

Abstract

This paper introduces GW (Greedy updates Without sampling), a novel approach to the Differentially Private Set Union (DPSU) problem. By incorporating local item frequencies and leveraging public datasets for knowledge transfer, the GW mechanism eliminates the need for wasteful random sampling, significantly lowering the noise threshold and increasing the number of items successfully released by up to 25%.

The DPSU Problem and the Sampling Bottleneck

The Differentially Private Set Union (DPSU) problem involves releasing the largest possible set of unique items (such as a vocabulary) from a collection of users' data without revealing the participation of any specific individual. Standard DP mechanisms typically follow a two-phase process: first, building a histogram where users "vote" for items they possess within a capped weight budget; second, adding noise to the histogram and outputting items that exceed a threshold $\rho$.

A major challenge in this framework is the sampling step. To bound sensitivity, traditional methods often require users to sample a limited number of items to vote for. This sampling is often "blind," potentially wasting a user's limited weight budget on common items that would have passed the threshold anyway. Furthermore, optimizing the sampling limit itself often requires additional privacy budget expenditure.

The GW Mechanism: Greedy Updates Without Sampling

The authors propose two main innovations to overcome these limitations:

  1. Eliminating Sampling via Greedy Updates: Instead of random sampling, the GW mechanism considers all of a user's items. It employs a Greedy Update (GU) strategy, using the user's local item frequency (how often an item appears in their specific documents) to decide how to spend their weight budget. Because the update order is determined by internal user data, it remains differentially private while being far more efficient.
  2. Knowledge Transfer (GW-KT): When a public, non-sensitive dataset is available, the mechanism can use global frequencies from that data to guide the greedy selection. This "hints" at which items are likely to be common, allowing the mechanism to reach the threshold for those items more rapidly.

Key Results and Performance

Mathematical proofs and empirical tests demonstrate that the GW mechanism consistently operates with a lower noise threshold $\rho$ than previous state-of-the-art "Policy" mechanisms, particularly at lower privacy budgets ($\epsilon$).

Figure 1: Comparison of the noise threshold $\rho$ across different DPSU mechanisms. GW consistently achieves a lower threshold than Policy Gaussian and Policy Laplace mechanisms, particularly at lower privacy budgets ($\epsilon$).

Evaluations on sensitive natural language datasets—including Reddit comments, Twitter customer service conversations, and financial news—show significant utility boosts. The basic GW mechanism outperformed previous state-of-the-art methods by approximately 10% on the Twitter and Finance datasets. When public data was incorporated for Knowledge Transfer (GW-KT), utility gains jumped by 12% to 25%.

Figure 2: Set union size (utility) comparison across Reddit, Twitter, and Finance datasets. The GW mechanism (blue) consistently yields larger set unions across various privacy budgets ($\epsilon$) and tuning parameters ($\alpha$) compared to baseline mechanisms.

Conclusion

The GW mechanism demonstrates that local frequency is a powerful, privacy-neutral tool for optimization. By replacing uniform sampling with greedy updates, the approach maximizes the utility of the privacy budget. Furthermore, the success of cross-domain knowledge transfer suggests that common linguistic patterns are consistent enough to boost DP utility even when public and private data domains differ significantly.

Summary updated

Abstract

We study the problem of releasing the set union of users' items subject to differential privacy. Previous approaches consider only the set of items for each user as the input. We propose incorporating the item frequency, which is typically available in set union problems, to boost the utility of private mechanisms. However, using the global item frequency over all users would largely increase privacy loss. We propose to use the local item frequency of each user to approximate the global item frequency without incurring additional privacy loss. Local item frequency allows us to design greedy set union mechanisms that are differentially private, which is impossible for previous greedy proposals. Moreover, while all previous works have to use uniform sampling to limit the number of items each user would contribute to, our construction eliminates the sampling step completely and allows our mechanisms to consider all of the users' items. Finally, we propose to transfer the knowledge of the global item frequency from a public dataset into our mechanism, which further boosts utility even when the public and private datasets are from different domains. We evaluate the proposed methods on multiple real-life datasets.
BibTeX
@inproceedings{carvalho2022incorporating,
  author = {Ricardo Silva Carvalho and Ke Wang and Lovedeep Gondara},
  title = {{Incorporating Item Frequency for Differentially Private Set Union}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=KKWX4JBBaw},
}
Figure