Federated Heavy Hitters Discovery with Differential Privacy

Wennan Zhu, Peter Kairouz, Haicheng Sun, Brendan McMahan, Wei Li

Abstract

This paper introduces TrieHH, a novel federated algorithm designed to discover frequent items (heavy hitters) within a user population while maintaining rigorous differential privacy. Unlike traditional local differential privacy (LDP) methods that often sacrifice data utility for privacy, TrieHH leverages a decentralized trie-based structure and interactive thresholding. By utilizing the inherent randomness of user sampling and thresholding, TrieHH achieves high-accuracy discovery without the need for additive noise, significantly outperforming existing industry standards in both precision and recall.

Introduction

Service providers frequently need to identify popular trends, such as new words for auto-complete dictionaries, without compromising individual user privacy. Current approaches typically fall into two categories: Central Differential Privacy (DP), which requires absolute trust in a central server, and Local Differential Privacy (LDP), which adds noise at the source. While LDP offers stronger privacy by ensuring raw data never leaves the device, the resulting "noise at the source" often degrades utility, making it difficult to detect all but the most frequent items. This paper addresses this utility gap by proposing a system that maintains decentralized privacy while achieving centralized-level accuracy.

Methodology: The TrieHH Algorithm

The authors propose TrieHH, an interactive, trie-based algorithm that discovers heavy hitters character-by-character.

The Trie Structure and Interactive Rounds

Instead of querying for full sequences, the server constructs a prefix tree (trie). In each round, the server broadcasts a set of "popular prefixes." A random subset of users checks their local data against these prefixes. If a match is found, the user "votes" for the next character in their sequence.

TrieHH builds a prefix tree iteratively across multiple rounds of user interaction.

Privacy through Sampling and Thresholding

A key innovation of TrieHH is its approach to Differential Privacy. The server only extends a prefix in the trie if it receives more than $\theta$ votes. The authors prove that the combination of random user sampling and thresholding is sufficient to provide $(\epsilon, \delta)$-differential privacy. This eliminates the need for artificial noise (e.g., Gaussian noise), which typically plagues LDP implementations. Furthermore, the algorithm employs a strict "user-level" privacy definition, ensuring robustness even when users contribute multiple sequences.

Experimental Evaluation

The researchers evaluated TrieHH using two primary datasets:

  • Sentiment140: A large-scale Twitter dataset containing 1.6 million tweets from over 650,000 users.
  • Out-of-Vocabulary (OOV) Dataset: A subset of Twitter data filtered against a 260k-word dictionary to simulate the discovery of new words, slang, and usernames.

Key Results

TrieHH demonstrates significant improvements over existing methods like Apple’s Sequence Fragment Puzzle (SFP).

Superior Utility and Precision

In the OOV discovery task, TrieHH achieved a recall of 0.76 at $\epsilon=4$, whereas the LDP-based SFP reached only 0.19 to 0.32. In many scenarios, TrieHH maintained a precision of 1.0, ensuring that all discovered items were truly frequent in the population.

Comparison of F1 scores between TrieHH and SFP across different privacy budgets (epsilon) and top-K values.

Scalability

The algorithm scales effectively to large populations. For a group of $10^7$ users, TrieHH can maintain a strong privacy guarantee ($\epsilon=2$) while discovering items that appear in as little as 0.02% of the population.

Discussion and Future Work

While TrieHH offers a major leap in utility, it requires multiple communication rounds, which may be challenging for users with unstable connections. Future work aims to integrate Secure Aggregation to further protect individual votes from a potentially curious server and explore "local plausible deniability" to amplify privacy gains.

Summary updated

BibTeX
@inproceedings{zhu2020federated,
  author = {Wennan Zhu and Peter Kairouz and Haicheng Sun and Brendan McMahan and Wei Li},
  title = {{Federated Heavy Hitters Discovery with Differential Privacy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=vb7ftNnJcqoY},
}
Figure