Differentially Private Data Publishing and Analysis: A Survey <s> Frequent Itemset Mining <s> Discovering frequent patterns from data is a popular exploratory technique in datamining. However, if the data are sensitive (e.g., patient health records, user behavior records) releasing information about significant patterns or trends carries significant risk to privacy. This paper shows how one can accurately discover and release the most significant patterns along with their frequencies in a data set containing sensitive information, while providing rigorous guarantees of privacy for the individuals whose information is stored there. We present two efficient algorithms for discovering the k most frequent patterns in a data set of sensitive records. Our algorithms satisfy differential privacy, a recently introduced definition that provides meaningful privacy guarantees in the presence of arbitrary external information. Differentially private algorithms require a degree of uncertainty in their output to preserve privacy. Our algorithms handle this by returning 'noisy' lists of patterns that are close to the actual list of k most frequent patterns in the data. We define a new notion of utility that quantifies the output accuracy of private top-k pattern mining algorithms. In typical data sets, our utility criterion implies low false positive and false negative rates in the reported lists. We prove that our methods meet the new utility criterion; we also demonstrate the performance of our algorithms through extensive experiments on the transaction data sets from the FIMI repository. While the paper focuses on frequent pattern mining, the techniques developed here are relevant whenever the data mining output is a list of elements ordered according to an appropriately 'robust' measure of interest. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Frequent Itemset Mining <s> The discovery of frequent itemsets can serve valuable economic and research purposes. Releasing discovered frequent itemsets, however, presents privacy challenges. In this paper, we study the problem of how to perform frequent itemset mining on transaction databases while satisfying differential privacy. We propose an approach, called PrivBasis, which leverages a novel notion called basis sets. A θ-basis set has the property that any itemset with frequency higher than θ is a subset of some basis. We introduce algorithms for privately constructing a basis set and then using it to find the most frequent itemsets. Experiments show that our approach greatly outperforms the current state of the art. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Frequent Itemset Mining <s> We consider differentially private frequent itemset mining. We begin by exploring the theoretical difficulty of simultaneously providing good utility and good privacy in this task. While our analysis proves that in general this is very difficult, it leaves a glimmer of hope in that our proof of difficulty relies on the existence of long transactions (that is, transactions containing many items). Accordingly, we investigate an approach that begins by truncating long transactions, trading off errors introduced by the truncation with those introduced by the noise added to guarantee privacy. Experimental results over standard benchmark databases show that truncating is indeed effective. Our algorithm solves the "classical" frequent itemset mining problem, in which the goal is to find all itemsets whose support exceeds a threshold. Related work has proposed differentially private algorithms for the top-k itemset mining problem ("find the k most frequent itemsets".) An experimental comparison with those algorithms show that our algorithm achieves better F-score unless k is small. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Frequent Itemset Mining <s> Discovering frequent graph patterns in a graph database offers valuable information in a variety of applications. However, if the graph dataset contains sensitive data of individuals such as mobile phone-call graphs and web-click graphs, releasing discovered frequent patterns may present a threat to the privacy of individuals. Differential privacy has recently emerged as the de facto standard for private data analysis due to its provable privacy guarantee. In this paper we propose the first differentially private algorithm for mining frequent graph patterns. We first show that previous techniques on differentially private discovery of frequent itemsets cannot apply in mining frequent graph patterns due to the inherent complexity of handling structural information in graphs. We then address this challenge by proposing a Markov Chain Monte Carlo (MCMC) sampling based algorithm. Unlike previous work on frequent itemset mining, our techniques do not rely on the output of a non-private mining algorithm. Instead, we observe that both frequent graph pattern mining and the guarantee of differential privacy can be unified into an MCMC sampling framework. In addition, we establish the privacy and utility guarantee of our algorithm and propose an efficient neighboring pattern counting technique as well. Experimental results show that the proposed algorithm is able to output frequent patterns with good precision. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Frequent Itemset Mining <s> Frequent itemset mining is a core data mining task and has been studied extensively. Although by their nature, frequent itemsets are aggregates over many individuals and would not seem to pose a privacy threat, an attacker with strong background information can learn private individual information from frequent itemsets. This has lead to differentially private frequent itemset mining, which protects privacy by giving inexact answers. We give an approach that first identifies top-k frequent itemsets, then uses them to construct a compact, differentially private FP-tree. Once the noisy FP-tree is built, the (privatized) support of all frequent itemsets can be derived from it without access to the original data. Experimental results show that the proposed algorithm gives substantially better results than prior approaches, especially for high levels of privacy. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Frequent Itemset Mining <s> Mining frequent subgraphs from a collection of input graphs is an important topic in data mining research. However, if the input graphs contain sensitive information, releasing frequent subgraphs may pose considerable threats to individual's privacy. In this paper, we study the problem of frequent subgraph mining (FGM) under the rigorous differential privacy model. We introduce a novel differentially private FGM algorithm, which is referred to as DFG. In this algorithm, we first privately identify frequent subgraphs from input graphs, and then compute the noisy support of each identified frequent subgraph. In particular, to privately identify frequent subgraphs, we present a frequent subgraph identification approach which can improve the utility of frequent subgraph identifications through candidates pruning. Moreover, to compute the noisy support of each identified frequent subgraph, we devise a lattice-based noisy support derivation approach, where a series of methods has been proposed to improve the accuracy of the noisy supports. Through formal privacy analysis, we prove that our DFG algorithm satisfies e-differential privacy. Extensive experimental results on real datasets show that the DFG algorithm can privately find frequent subgraphs with high data utility. <s> BIB006
Frequent itemset mining aims to discover itemsets that frequently appear in a dataset D. Suppose I is the set of items in D, and an itemset refers to a subset of I. Let each record r i 2 D denote as a transaction that contains a set of items from I. Given an itemset I j , if transaction r i contains I j , we say r i supports I j , and the proportion of supporting transactions in the dataset is defined as the support of I j . An itemset with a frequency larger than the predefined support threshold is called a frequent itemset or a frequent pattern. Let U represent all frequent itemsets, where the topk most frequent itemsets in U should be released under differential privacy guarantee. Laplace noise is normally added to the frequency; however, the main challenge is that the total number of itemsets is exponential to the number of items: If I contains n items, the number of all possible itemsets is jUj ¼ P k i¼1 ð n i Þ. Decreasing the number of candidate itemsets is a major research issue in differentially private frequent itemset mining. Bhaskar et al. BIB001 solved the problem by providing a truncated frequency to reduce the number of candidate itemsets. They proposed an algorithm that uses the exponential mechanism to choose the top-k itemsets. The score function of each candidate is the frequency defined as d pðUÞ ¼ maxðpðUÞ; p k À gÞ, where p k is the frequency of the kth most frequent itemsets and g 2 ½0; 1 is an accuracy parameter. Every itemset with a frequency greater than p k À g is computed as its normal frequency pðUÞ while the frequency of the rest is truncated to p k À g. All the itemsets with frequencies of p k À g are grouped into one set, and the algorithm uniformly selects itemsets from this set. In this way, the computational cost is significantly reduced. The advantage of truncating frequency is that it can significantly decrease the size of candidate itemsets. However, it is only applicable when k is small. Another weakness is that the length of top-k itemsets needs to be predefined, which affects the flexibility of frequent itemset mining. To address these weaknesses, Li et al. BIB002 constructed a basis set B ¼ fB 1 ; B 2 ; . . .g in which any itemset with a frequency higher than a threshold is a subset of the basis set B i . The algorithm generated candidate itemsets based on B and the algorithm could release itemsets with arbitrary length. However, generating basis sets B is not easy; furthermore, when the length of the itemset and the number of basis sets are large, the cardinality of the candidate itemsets is still too big to handle. Efficiently decreasing the number of the candidate itemsets is still a challenge. Zeng et al. BIB003 proposed an algorithm that randomly truncates transactions in a dataset according to a predefined maximal cardinality. The algorithm iteratively generates candidate itemsets and perturbs the support of those candidate itemsets. Lee et al. BIB005 proposed an FP-tree based frequent itemset mining algorithm. The algorithm first identifies all frequent itemsets without knowing their exact supports, but only that their supports are above a predefined threshold. The proposed algorithm injects noise into the data structure at the intermediate (FP-tree) step. The final output can be further refined through an optional post-processing step. The advantage of the algorithm is that information disclosure affecting differential privacy occurs only for count queries above the predefined threshold; negative answers do not count against the privacy budget. Shen et al. BIB004 applied a Markov chain Monte Carlo (MCMC) sampling method to deal with the challenge of large candidate itemsets. They claim that an MCMC random walk method can bypass the problem, and the exponential mechanism can then be applied to select frequent itemsets. They use this method to mine frequent graph patterns. Xu et al. BIB006 applied a binary estimation method to identify all possible frequent itemsets and then use an exponential mechanism to privately select frequent itemsets. The number of candidates is eventually a logarithm of the original number using a binary search. Discussion. Frequent itemset mining is a typical data mining task, which suffers from searching large candidate sets. Differential privacy makes the problem worse. BIB001 , BIB003 , BIB005 and BIB002 tried to merge some candidates into groups using different methods. BIB004 adopted a sampling method to search the candidate itemsets. BIB006 applied a binary search method. All of those methods decreased the searching space from exponential to polynomial, which is a big achievement. However, the noise still remains high, which needs to be decreased further. Table 13 summarizes those key methods.