Locally Differentially Private Frequent Itemset Mining

### Overview Presented by a researcher named Aha, this talk introduces a framework for frequent itemset mining under local differential privacy (LDP), conducted as joint work with advisors from Purdue University and the University of Wisconsin–Madison. Organizations routinely seek to collect user data from mobile phones and wearable devices to generate recommendations, make predictions, or block malicious calls. However, privacy concerns and regulations frequently prevent users from sharing raw data. The speaker addresses this challenge using randomized response and local differential privacy protocols, which allow users to perturb their data locally before reporting to an untrusted central aggregator, ensuring plausible deniability while preserving data utility.

### Key Topics - **Local Differential Privacy (LDP):** A formal privacy standard where each client perturbs their data using an epsilon-LDP perturbation function before transmission, limiting the centralized aggregator's ability to infer individual values. - **Frequency Oracles:** Algorithmic mechanisms used by the central aggregator to estimate the frequency distribution of domain values based on noisy reports. - **Frequent Itemset Mining:** Identifying both the most frequent singleton items and itemsets when users hold variable-sized sets of items. - **Pad-and-Sample Techniques:** Methods addressing variable-length user sets by padding sets to a fixed size with dummy items and sampling a subset before reporting. - **Sources of Estimation Error:** Balancing variance from perturbation noise against systematic underestimation from sampling. - **Privacy Amplification:** Exploiting the randomness of sampling prior to perturbation to obtain tighter privacy bounds and enable larger effective privacy parameters.

### Technical Details Prior work such as LDPstream/LDP-Miner (from CCS 2016) approached singleton mining using a two-phase protocol: users pad their itemsets to a designated threshold (such as the 90th percentile of size distribution, denoted *L*), randomly sample one item, report it using randomized response, and subsequently refine frequency estimates against top candidates. However, this approach does not natively handle frequent itemset mining and relies on suboptimal parameter selections.

The speaker identifies two primary sources of error in pad-and-sample frequency oracles: 1. **Variance:** Inherent noise added during perturbation, which scales quadratically with padding size *L*. 2. **Underestimation:** Signal dilution when users possessing larger itemsets sample items at a lower rate than the scaling multiplier assumes.

To optimize this trade-off, the authors propose an adaptive protocol called **SVSM** (set-valued item mining). SVSM departs from existing approaches by: - Having users sample an item in the first phase without padding dummy values to preserve raw signal strength for identifying frequent candidates. - Computing the 90th percentile of intersection sizes and adaptively selecting the optimal frequency oracle parameters based on overall variance and privacy amplification by sampling. - Employing privacy amplification, wherein sampling prior to perturbation yields a more favorable privacy ratio, allowing the mechanism to choose a larger effective parameter $\epsilon'$ during reporting.

Experimental evaluation on the POS dataset (containing thousands of distinct items) demonstrated improved F1-scores over baseline LDP-Miner variants for both singleton identification and frequency estimation.

### Takeaways - Standard frequency oracles should not be treated as opaque black boxes; inspecting their internal dynamics enables substantial utility gains through adaptive parameter tuning. - Sampling items before perturbation provides privacy amplification, improving accuracy under strict privacy budgets. - To avoid correlation-based privacy leakage and privacy budget doubling, users are partitioned across protocol phases so that each client reports only once.