Differentially Private High-Dimensional Data Publication

via Sampling-Based Inference

∗
Rui Chen Qian Xiao
Samsung Research America, USA National University of Singapore, Singapore
rui.chen1@[Link] xiaoqian@[Link]
Yu Zhang Jianliang Xu
Hong Kong Baptist University, Hong Kong Hong Kong Baptist University, Hong Kong
yuzhang@[Link] xujl@[Link]

ABSTRACT cation domains. Releasing such data has been a prerequisite

Releasing high-dimensional data enables a wide spectrum of for many data mining tasks. However, individual privacy has
data mining tasks. Yet, individual privacy has been a ma- been a major public concern in data sharing. In this paper,
jor obstacle to data sharing. In this paper, we consider the we consider the problem of releasing high-dimensional data
problem of releasing high-dimensional data with differential under differential privacy [6], a privacy notion widely advo-
privacy guarantees. We propose a novel solution to preserve cated due to its strong privacy guarantee. There have been
the joint distribution of a high-dimensional dataset. We a series of techniques proposed for differentially private low-
first develop a robust sampling-based framework to system- dimensional data publication [1,2,6,9,12,17,18,24,25,27,30].
atically explore the dependencies among all attributes and Unfortunately, when applied to high-dimensional data, al-
subsequently build a dependency graph. This framework is l these techniques suffer from the curse of dimensionality,
coupled with a generic threshold mechanism to significantly that is, they cannot achieve either reasonable scalability or
improve accuracy. We then identify a set of marginal ta- desirable utility [21,29]. Special treatment is needed to over-
bles from the dependency graph to approximate the joint come the challenges incurred by high dimensionality.
distribution based on the solid inference foundation of the In addressing the challenges, one of the most promising
junction tree algorithm while minimizing the resultant error. ideas is to decompose high-dimensional data into a set of
We prove that selecting the optimal marginals with the goal low-dimensional marginal tables C, along with an inference
of minimizing error is NP-hard and, thus, design an approx- mechanism that infers the joint data distribution from C.
imation algorithm using an integer programming relaxation This has been the rationale of the very recent study [29] in
and the constrained concave-convex procedure. Extensive which PrivBayes is proposed to learn a set of low-dimensional
experiments on real datasets demonstrate that our solution conditional probabilities via a Bayesian network and approx-
substantially outperforms the state-of-the-art competitors. imate the joint distribution by the chain rule for Bayesian
networks. While making substantial progress, it has two
major limitations due to the constraint of differential priva-
Categories and Subject Descriptors cy. First, one has to minimize probes over the underlying
K.4.1 [COMPUTERS AND SOCIETY]: Privacy dataset; otherwise the result of a probe becomes largely i-
naccurate. This implies that one often has to compromise
Keywords more sophisticated algorithms that require excessive access
to the data. For this reason, PrivBayes employs a simple
Differential privacy, high-dimensional data, joint distribu- greedy algorithm to learn a Bayesian network, whose perfor-
tion, dependency graph, junction tree algorithm mance is sensitive to the randomly selected initial attribute,
and limits the size of each attribute’s parent set to be iden-
1. INTRODUCTION tical. Second, with the increasing number of attributes, the
With the rapid development of computing technologies, privacy budget used for determining each attribute’s parent
high-dimensional data has become prevalent in many appli- set decreases quickly, making the learned conditional prob-
abilities unreliable. As a result, PrivBayes is still not able
∗Part of this work was done while the author was with Hong
to adequately capture the characteristics of the underlying
Kong Baptist University data in order to maximize data utility.
Permission to make digital or hard copies of all or part of this work for personal or In practice, the independence properties exist in many
classroom use is granted without fee provided that copies are not made or distributed high-dimensional datasets, which is the rationale behind prob-
for profit or commercial advantage and that copies bear this notice and the full citation abilistic graphical models [15]. It is beneficial to systemat-
on the first page. Copyrights for components of this work owned by others than the
author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
ically explore such (conditional) independences among at-
republish, to post on servers or to redistribute to lists, requires prior specific permission tributes. However, conducting such an exploration under
and/or a fee. Request permissions from Permissions@[Link]. differential privacy requires non-trivial efforts. The key tech-
KDD’15, August 10-13, 2015, Sydney, NSW, Australia. nical challenge is how to reliably learn all attributes’ pairwise
Copyright is held by the owner/author(s). Publication rights licensed to ACM. correlations using a limited privacy budget. For a dataset
ACM 978-1-4503-3664-2/15/08 ...$15.00. with d attributes, existing techniques require to divide the
DOI: [Link]

129


given privacy budget into d2 portions, each being used for a 2. RELATED WORK
pair of attributes. There is no doubt that none of these tech- Most of the existing works on differentially private data
niques can learn the correlations with reasonable accuracy. publishing focus on low-dimensional data (e.g., marginal ta-
We address this challenge by proposing a sampling-based bles or histograms). Xiao et al. [24] propose to apply the
testing framework and a generic threshold mechanism. This wavelet transformation to an input histogram and add noise
design allows us to learn the pairwise correlations

without to wavelet coefficients. Hay et al. [12] exploit the consis-
splitting the privacy budget in proportion to d2 and further tency constraints that should hold over the noisy output to
enjoy the privacy budget amplification due to sampling. improve accuracy. These two methods are special cases of
With the learned correlations, how to develop an infer- a more general matrix mechanism [17], which calculates the
ence model to estimate the joint distribution with minimum answers to a set of queries from another set of properly se-
error remains a second challenge. We decompose this task lected queries called query strategy. Yaroslavtsev et al. [26]
into two steps. First, we build a solid statistical inference further explore the idea of using a query strategy by adding
foundation by employing the well-established junction tree non-uniform noise. Yuan et al. [27] introduce the low-rank
algorithm. Unfortunately, the junction tree algorithm does mechanism for answering batch linear counting queries based
not take into consideration the differential privacy constrain- on low-rank matrix approximation. Hardt et al. [9] present
t. Directly injecting noise into the marginals of the cliques an algorithm based on multiplicative weights and the ex-
returned by the junction tree algorithm usually leads to ex- ponential mechanism. In another line of research, Xu et
cessive noise. We then formulate an optimization problem al. [25] propose to group a histogram’s adjacent bins with
for finding the optimal marginals with the minimum error close counts to trade for smaller Laplace noise. A similar
and solve it by the constrained concave-convex procedure. idea is proposed by Acs et al. [1]. They design a hierarchi-
Contributions. Our key contribution is a novel sampling- cal bisection algorithm to identify a good grouping scheme.
based solution for publishing high-dimensional data under Zhang et al. [30] indicate that global clustering achieves bet-
differential privacy, which features a solid statistical infer- ter utility than local grouping. Li et al. [18] propose to
ence foundation. More specifically, we make the following answer range queries by taking into consideration both the
contributions: underlying data and the query set.
First, we design a sampling-based testing framework to In general, the above methods cannot overcome the inher-
systematically explore pairwise dependencies while satisfy- ent challenges due to the curse of dimensionality. In spite of
ing differential privacy. This framework is made possible by its wide applications, differentially private high-dimensional
a generic threshold mechanism, which is an extended ver- data publication has been relatively rarely studied. Barak
sion of the sparse vector technique [10] and the threshold et al. [2] show how to construct a synthetic database to pre-
query technique [16]. This threshold mechanism allows to serve all low-dimensional marginals by adding noise to the
use multiple thresholds and may substantially improve the Fourier domain. The problem in [2] is equivalent to publish-
accuracy of many algorithms. ing OLAP cubes, which is studied by Ding et al. [5]. They
Second, we propose to apply the junction tree algorithm first compute a subset of cuboids and then generate the re-
to establish an inference mechanism for inferring the join- maining cuboids from this subset. The main limitation of
t data distribution. How to generate differentially private these two approaches is their exponential complexity in the
marginals to feed the inference mechanism with minimum dimensionality of the domain. Mohammed et al. [20] intro-
error is vital to the final accuracy. We prove that this opti- duce probabilistic generalization to overcome the curse of
mization problem is NP-hard and propose an approximation dimensionality. However, with the increasing dimensionali-
algorithm using an integer programming relaxation and the ty, the benefit of generalization diminishes rapidly. Cormode
constrained concave-convex procedure. et al. [4] solely consider the scalability aspect of the prob-
Third, we extend the mutual consistency technique in [21] lem. They design a statistical process to compute a private
to the general case where the noisy marginals are of different summary without materializing the entire contingency table.
sizes and attributes may not be binary, and propose a simple Very recently, Qardaji et al. [21] study how to generate
yet effective thresholding strategy to mitigate the systematic accurate k-way marginals for a binary dataset. They pro-
bias due to rounding negative noisy counts to 0. We also pose PriView that uses covering design to select a set of
show how to efficiently generate synthetic datasets from the low-dimensional marginals called views and then generates
noisy marginals using the junction tree representation. k-way marginals based on maximum entropy optimization.
We conduct extensive experiments over five standard real The work closest to ours is PrivBayes [29], which iteratively
datasets for two different analysis tasks. We show that our learns the parent sets of the attributes in a Bayesian net-
solution not only significantly outperforms PrivBayes [29], work by applying the exponential mechanism with a sur-
the state-of-the-art technique for releasing high-dimensional rogate function for mutual information. Compared with
data, but also achieves comparable, and sometimes bet- PrivBayes, our solution features a systematic exploration
ter, accuracy to that of PriView [21], the state-of-the-art of attribute correlations and a series of new generic tech-
technique tailored to generating k-way marginals over high- niques, which together achieve substantially better perfor-
dimensional data. Moreover, our solution works for both mance. The connection between probabilistic inference and
binary and non-binary data while PriView only works for differential privacy is also studied in [23].
binary data1 .
3. PROBLEM FORMULATION
3.1 Problem Statement
1
To handle non-binary data, PriView requires adapting ex-
isting covering design algorithms to the case where different
views may have different sizes [21]. To our best knowledge, In this paper, we consider the following problem: Given
there does not exist such an algorithm. a dataset D with d attributes (either numerical or categori-

130
cal) A = {A1 , A2 , · · · , Ad }, we want to generate a synthetic
dataset that accurately preserves the joint distribution of the
tuples in D while satisfying differential privacy.
We denote the value domain of an attribute Ai by Ωi
and its size (i.e., the number of distinct values in Ωi ) by
|Ωi |2 . Therefore, the entire output domain is defined by (a) A sample dependency graph
Ω1 × Ω2 × · · · × Ωd , whose size is |Ω1 | × |Ω2 | × · · · × |Ωd |. We
focus on the case where |Ω1 | × |Ω2 | × · · · × |Ωd | is too large to
be handled by the existing low-dimensional data publishing A4 A4
techniques. We assume that the size of the dataset D (i.e.,
the number of tuples), denoted by |D|, is known. This is (b) A junction tree
Figure 1: A dependency graph and its junction tree
a common assumption under our definition of neighboring
databases [6]. Note that the dataset D does not have to be general idea is to represent the joint distribution P (A) of
a relational table. It can also be, for example, a set-valued all attributes A = {A1 , A2 , · · · , Ad } in a dataset as a func-
dataset in which all attributes are binary. tion of the marginals of a set of maximal cliques and their
Differential Privacy. Differential privacy is built on the separators. Let Ci be a clique in the junction tree T , and
notion of indistinguishability of two neighboring databases. Sij = Ci ∩ Cj be the separator between cliques Ci and Cj .
We consider two databases D and D′ to be neighbors if D The joint distribution can be calculated as follows:
can be obtained from D′ by changing the value of exactly Q
C ∈T P (Ci )
one tuple. Intuitively, differential privacy guarantees that P (A) = Q i , (1)
any computational result from D and D′ will be statistically Sij ∈T P (Sij )
indistinguishable. A formal definition is given below.
where P (Ci ) and P (Sij ) are the marginal distributions of
Definition 1. (ǫ-Differential Privacy [6]) A randomized al- the cliques and the separators, respectively. This establish-
gorithm M satisfies ǫ-differential privacy, if for any two es the theoretical foundation of exactly inferring the joint
neighboring databases D and D′ , and for any O ⊆ Range(M), distribution from a junction tree.
A junction tree can be constructed in two steps. The first
P [M(D) ∈ O] ≤ exp(ǫ) · P [M(D′ ) ∈ O], step is triangulation. An undirected graph is said to be tri-
where the probability is taken over M’s randomness. angulated if and only if there is an edge between any two
non-successive vertices in every cycle. A triangulated graph
Differential privacy can be achieved by the Laplace mech- is guaranteed to have a junction tree. Then we can construc-
anism [6], which injects properly calibrated Laplace noise t the junction tree in one of two basic ways: (1) based on
into a function’s output to mask the impact of any single variable elimination and (2) based on direct graph manip-
tuple. The maximal impact of a tuple to the output of a ulation. In either way, the resultant junction tree satisfies
function f is called its sensitivity. For any two neighboring the running intersection property: for each pair of vertices
databases D and D′ , the sensitivity of f : D → Rd is defined u and v, all vertices on the path between u and v contain
as ∆f = maxD,D′ kf (D) − f (D′ )k1 . the intersection u ∩ v.
Theorem 1. [6] For any function f : D → Rd , the mech- Example 1. Figure 1(a) gives the dependency graph G
anism M, of a sample dataset with attributes A = {A1 , A2 , · · · , A6 }.
     Since the cycle A2 − A3 − A5 − A4 − A2 has non-successive
∆f ∆f
M (D) = f (D) + Lap1 , . . . , Lapd vertices that are not connected, we add the edge (A3 , A4 ) to
ǫ ǫ
make G triangulated, as illustrated by the dashed line. Note


∆f
gives ǫ-differential privacy, where Lapi ǫ are i.i.d Laplace that the triangulation procedure may not be unique. For ex-
variables with scale parameter ∆f . ample, adding the edge (A2 , A5 ) also makes G triangulated.
ǫ
A junction tree of the triangulated graph is given in Fig-
3.2 Junction Tree Algorithm ure 1(b), where cliques are represented by oval nodes and
separators by rectangle nodes. Similarly, the junction tree of
The key to overcoming the curse of dimensionality in our
a triangulated graph is not unique.
problem is to factorize the joint probability distribution in-
to modular components based on conditional independences
that exist in many real-world datasets. Probabilistic graphi- 4. OUR SOLUTION
cal models are an elegant tool for identifying such a modular Broadly, our solution first systematically explores pair-
structure. Markov networks are the most widely used graph- wise dependencies to construct the dependency graph and
ical model based on undirected graphs. In our problem, we then differentially privately infers the joint distribution by
record the independences in terms of a dependency graph, applying the junction tree algorithm. More specifically, our
which is essentially a Markov network in that the nodes rep- solution is composed of the following four steps.
resent the attributes in a dataset, and the edges correspond
to the dependencies between the attributes [15]. 1. Build the dependency graph. The first step is to
The junction tree algorithm is a standard method to pa- learn the pairwise correlations of all attributes under
rameterize a Markov network so that the joint distribution a sampling-based testing framework, from which the
and marginal distributions can be readily calculated. The dependency graph is generated.
2 2. Form attribute clusters. We apply the junction
Continuous attributes can be discretized to fit into our so-
lution. tree algorithm to the dependency graph in order to

131
 generate the set of cliques to form the inference founda- Algorithm 1 Generate Dependency Graph
tion and further identify a collection of attribute clus- Input: Dataset D with attributes A = {A1 , A2 , · · · , Ad }
ters to derive all the cliques’ noisy marginals with the Input: Privacy parameter ǫ1
minimum error. Output: Dependency graph G
3. Generate noisy marginals. For each attribute clus- 1: Initialize G = (V, E) with V = {A1 , A2 , · · · , Ad } and
ter, we generate a differentially private marginal ta- E = ∅;
ble and enforce consistency constraints over all such 2: Calculate sampling rate β;
marginals. 3: Generate Ds by sampling tuples in D with rate β;
4: ǫa = ln(eǫ1 − 
1 + β) − ln β;
4. Produce a synthetic dataset. We make use of the 2∆I
5: η = Lap ;
noisy marginal tables and the inference model to effi- ǫa

ciently generate a synthetic dataset. 6: for each attribute pair (Ak , Al ) do 
7: e k , Al ) = I(Ak , Al ) + Lap 2∆I ;
I(A
Since only the first and third steps require access to the ǫa
input dataset, we divide the total privacy budget ǫ into two 8: θekl = θkl + η;
portions with ǫ1 being used for the first step and ǫ2 for the 9: e k , Al ) ≥ θekl then
if I(A
third step. In the following, we will show that the first and 10: Add edge (Ak , Al ) in G;
third steps are ǫ1 - and ǫ2 -differentially private, respectively. 11: return G;
Hence, by the composition property [6], our solution satisfies
ǫ-differential privacy as a whole, where ǫ = ǫ1 + ǫ2 .
4.1 Constructing the Dependency Graph size. This observation is vital to allow us to enjoy the sam-
pling property of differential privacy [19].
To build the dependency graph, we propose a sampling-
based dependency testing framework. The theoretical foun- Theorem 2. [19] Let M be an ǫ-differentially private
dation of our framework is derived from log-linear model- algorithm and Mβ be another algorithm that first indepen-
s [3] that have been extensively studied in the statistical dently samples each tuple in its input dataset with probability
literature. The saturated log-linear model states that the β and then applies M to the sampled dataset. Mβ satisfies
joint distribution can be modeled as a summation of effects ln(1 + β(eǫ − 1))-differential privacy.
whose dimensionality ranges from 0 up to d (i.e., the cor-
In Line 2, we calculate the sampling rate β by first deter-
relations of pairs of attributes, triples, quadruples, and so
mining a good sample size ns . Our intuition is to select the
forth). Yet, recent studies [13] have shown the diminishing
sample size that minimizes the ratio of noise magnitude to
return of maintaining higher order correlations, suggesting
the range of mutual information I on the sampled dataset,
that pairwise correlations are most important to approxi-
which is equivalent to identifying the best signal-to-noise ra-
mate the joint distribution. This result justifies why our
tio [29]. To quantify this size, we need to know the amplified
framework focuses on learning pairwise correlations.
privacy parameter ǫa due to sampling  and the sensitivity
 of
In the literature, the correlation between two attributes
can be measured by several metrics, such as chi-squared test I. From Theorem 2, we have ǫa = ln eǫ1 − 1 + |D| ns ns
−ln |D| .
χ2 , mean-square contingency, Cramer’s V φc and mutual Next we give the sensitivity of I.
information I, among others. In this paper, we choose mu- Theorem 3. [29]
tual information due not only to its small sensitivity but 
also to its capability of capturing both linear and non-linear  1 n−1 n
 log n + log , if any attr. is binary
correlations. Given two attributes Ak and Al , the mutual n n n−1
∆I =
information I(Ak , Al ) is defined as  2 log n + 1 + n − 1 log n + 1 , otherwise

n 2 n n−1
|Ωk | |Ωl |
XX pij
I(Ak , Al ) = pij log , where n is the sampled dataset size.
i=1 j=1
p i· p·j
Note that ∆I is insensitive to attributes’ domain sizes. It
where pij is the fraction of the tuples Pwhose Ak = i (i.e.,
P the only cares whether an attribute is binary. In Algorithm 1, if
ith value in Ωk ) and Al = j, pi· = j pij and p·j = i pij . all attributes of the input dataset are binary, we use ∆I =
1
As suggested by [14], we can consider that Ak and Al are n
log n + n−1
n
log n−1n
; otherwise we use ∆I = n2 log n+1 2
+
n−1 n+1
independent if I(Ak , Al ) ≤ θkl for some small θkl > 0. Yet, n
log n−1
. The reason of this choice will be made clear
how to set a reasonable θkl is unknown. In this paper, we soon. Thus, the best sample size can be calculated as
perform a more formal analysis on the choice of θkl by es-  1
tablishing the connection between mutual information and 
 log n + n−1 log n−1n
 argmin n

n
,if all attr. are binary


Cramer’s V φc . Mutual information can be well approximat-  n ln eǫ1 − 1 + |D| n n
− ln |D|
min(|Ωk |−1,|Ωl |−1)φ2 ns =
ed as I(Ak , Al ) ≈ c
. Since φc has a well- 2
2 
 log n+1 + n−1 n+1
log n−1
interpreted level of dependency (e.g., φc = 0.2 stands for 
 argmin
n 2 n

 n ln eǫ1 − 1 + n − ln n
  ,otherwise
weak dependency), we design θkl = σ min(|Ωk | − 1, |Ωl | − 1), |D| |D|
where σ is a parameter controlled by the φc value represent-
ing the desired level of dependency (e.g., φc = 0.2). where 1 < n ≤ |D| stands for all possible sample sizes.
We present our differentially private sampling-based frame- In Line 3, we sample the tuples in D by including each
ns
work in Algorithm 1. Previous work [13] has indicated that tuple with probability β = |D| . Then we learn the pairwise
the sample size required for learning correlations for a spec- correlations between all attributes over the sampled dataset
ified degree of accuracy can be independent of the dataset Ds . A simple attempt is to split the privacy parameter ǫa

132


into d2 portions, each being used for a pair of attributes. Once v <i is fixed, vi = 1 iff Ii + Lap( 2∆I
ǫa
) ≥ θi + η, where Ii
However, when d is relatively large, this simple scheme can and θi are the mutual information and threshold being used
barely obtain reliable results. In addressing this problem, we for generating vi . Let Hi (η) be the probability that vi = 1
generalize the threshold query technique [16], which is de- on D when the threshold is θi + η and Hi′ (η) be that on D′ .
rived from the sparse vector technique [10]. The key differ- Let λ = 2∆I
ǫa
. We have
ence is that in our problem, for different pairs of attributes
Ak and Al , I(Ak , Al ) needs to be compared with differen- Hi (η) = P (vi = 1|v <i ) = P (Lap(λ) + Ii − θi ≥ η | v <i )
t thresholds θkl = σ min(|Ωk | − 1, |Ωl | − 1), while in [16]  
all queries are compared with the same threshold. We call Let f (y|µ, λ) = 2λ1
exp − |y−µ| λ
. We can rewrite Hi (η) as
R∞
this generalized mechanism the threshold mechanism. The Hi (η) = η f (y|Ii − θi , λ)dy. After making the substitution
general intuition is that if what one wants to learn from a u = y − ∆I, we get
sequence of queries is a sequence of yes-or-no answers with Z ∞
respect to some threshold values (i.e., whether a query an- Hi (η) = f (u|Ii − θi − ∆I, λ)du
swer can pass the threshold), instead of the noisy values of η−∆I
R∞
the queries, there is no need to split the privacy parame- By definition of sensitivity, Hi (η) ≤ η−∆I f (u|Ii′ −θi , λ)du =
ter in proportion to the number of queries. Intuitively, this Hi′ (η − ∆I). Recall that η is a random Laplace variable with
is possible if the single tuple difference changes all yes-or-no scale 2∆I . It holds that p(η = x) ≤ exp( ǫ2a )p(η = x − ∆I),
ǫa
answers in the same way with respect to the thresholds. The
where p(·) is the probability density function. We have
threshold mechanism is instantiated in Lines 5-10. We will Z ∞
give its formal privacy guarantee later. Y Y
P (vi = 1|v <i ) = p(η = x) Hi (x)dx
In Line 5, we draw a random Laplace variable η with s- −∞
i:ai =1 i:ai =1
cale 2∆I
ǫa
to add randomness to all thresholds, where ∆I is Z
ǫa ∞ Y
the maximum sensitivity of all I(Ak , Al ). That is, if there ≤ exp( ) p(η = x − ∆I) Hi (x)dx
is at least an attribute Ai in D with |Ωi | > 2, we should 2 −∞ i:ai =1
use ∆I = |D2s | log |Ds2|+1 + |D|D
s |−1 |Ds |+1
log |D , where |Ds | is Z ∞ Y
s| s |−1 ǫa
3 ≤ exp( ) p(η = x − ∆I) Hi′ (x − ∆I)dx
the actual size of Ds . This is a must to establish the priva- 2 −∞ i:ai =1
cy guarantee of the threshold mechanism. In Lines 6-10, for Z
ǫa ∞ Y
each pair of attributes Ak and Al , we calculate the noisy ver- = exp( ) p(η = x) Hi′ (x)dx
e k , Al ), by adding Lap( 2∆I ).
sion of I(Ak , Al ), denoted by I(A 2 −∞ i:ai =1
ǫa
Here the noise scale does not depend on the number of ǫa Y ′
queries, which is the key benefit of employing the thresh- = exp( ) P (vi = 1|v <i ) (3)
2 i:a =1
old mechanism. In Line 9, I(A e k , Al ) is compared with the i

noisy threshold θekl = θkl + η. If I(A

e k , Al ) ≥ θekl , it indicates Similarly, we can prove that
that Ak and Al are correlated, and we record this correlation Y ǫa Y ′
by adding an edge between them in the dependency graph. P (vi = 0|v <i ) ≤ exp( ) P (vi = 0|v <i ) (4)
i:a =0
2 i:a =0
Now we formally prove the privacy guarantee of Algorith- i i

m 1, including that of the threshold mechanism. Using Formulae 2, 3 and 4, we derive

P (v = a) ǫa ǫa
Theorem 4. Algorithm 1 is ǫ1 -differentially private. ≤ exp( ) · exp( ) = exp(ǫa ) (5)
P ′ (v = a) 2 2
Proof. Let M be the version of Algorithm 1 without That is, M is ǫa -differentially private. Due to Theorem 2,
sampling (i.e., without Lines 2-3) and Ms be Algorithm 1. Ms achieves ǫ1 -differential privacy because
We first prove that M is ǫa -differentially private and then  
make use of Theorem 2 to show that Ms is ǫ1 -differentially e ǫ1 − 1
ln (1 + β(eǫa − 1)) = ln 1 + β( + 1 − 1) = ǫ1 .
private. Essentially, M outputs a vector v = [v1 , · · · , vw ], β
where vi takes a binary value to indicate whether the cor-
This concludes the proof.
responding pair of attributes is correlated, and w = d2 .
Let P (v = a) and P ′ (v = a) be the probabilities that a ∈ We would like to stress that in general, to make the thresh-
{0, 1}w is produced by two neighboring databases D and D′ , old mechanism work, all queries do not need to have the
respectively. By definition, we want to prove that for all D same sensitivity as long as we add noise to the queries and
and D′ and for all output vectors a of M, PP′(v=a)
(v=a)
≤ exp(ǫα ). thresholds based on the maximum sensitivity of all queries.
Let v <i denote the answers to the first (i − 1) elements in v This explains why we have to use the larger ∆I if there is an
and ai ∈ {0, 1} be an answer. attribute that is not binary. The randomness added to all
Qw threshold values must come from the same Laplace variable;
P (v = a) P (vi = ai |v <i ) otherwise we cannot establish the above proof.
′
= wi=1 ′
Q
For ease of discussion, in the following sections, we as-
i=1 P (vi = ai |v
P (v = a) <i )

Y P (vi = 1|v <i ) Y P (vi = 0|v <i ) sume that the dependency graph is connected. Otherwise,
= · we simply process each connected component separately.
P (vi = 1|v ) i:a =0 P ′ (vi = 0|v <i )
′ <i

4.2 Forming Attribute Clusters

i:a =1
i i
(2)
With the learned dependency graph, we can feed it into
3 the junction tree algorithm introduced in Section 3.2 to ob-
Note that |Ds | may not equal ns due to the Bernoulli sam-
pling process (Line 3) required by Theorem 2. tain the set of cliques and separators. A simple idea is to

133
directly generate noisy marginals based on these cliques so Algorithm 2 Form Attribute Clusters
that we can infer the joint distribution. There is no need to Input: Dependency graph G
generate marginals for the separators as they can always be Input: Attribute set A = {A1 , A2 , · · · , Ad }
derived from the cliques. However, the junction tree algo- Output: Junction cliques C
rithm selects the cliques irrespective of the differential pri- Output: Separators S
vacy constraint. In fact, the number of marginals is directly Output: Attribute clusters CL
related to the accuracy of the estimated joint distribution. 1: (C, S) ← JunctionTreeAlgorithm(G);
Our insight is that we can properly merge the cliques into 2: for i = |C| to 1 do
larger and fewer clusters from which we can derive the joint 3: CLi ← IdentifyOptimalMerging(C, i);
distribution with less noise. 4: Calculate the total noise variance V ar(CLi ) of the
Consider merging cliques C1 , · · · , Ck into a cluster CL, cliques’ marginals derived from CLi ;
which contains the set of attributes in C1 , · · · , Ck . Let the 5: CL = argminCLi (V ar(CLi ));
set of attributes be {A1 , · · · , Al }, ǫ2 be the privacy budget 6: return C, S, and CL;
for generating the noisy marginals and the total number
of marginals be m. Clearly, we can generate the cliques’
marginals from CL’s marginal with the total noise variance Since B4 < Ii < B2 , each Si must contain exactly three
k × 2( 2m
ǫ2
)2 × |Ω1 | × · · · × |Ωl |, where 2( 2m
ǫ2
)2 is the noise integers from S. We now show a polynomial-time reduction
variance added to each entry. We illustrate the benefit of from 3-PARTITION to OptimalMerging. Given an instance
merging cliques by the following example. of 3-PARTITION with n positive integers {I1 , I2 , · · · , In }
Example 2. Continue with Example 1. Assume that the and a bound B, we construct the corresponding instance of
domain sizes of A1 , A2 , A3 , A4 , A5 , A6 are 2, 2, 3, 4, 3 OptimalMerging as follows. We transform the input inte-
and 2, respectively. If we directly add Laplace noise to the gers to 3-PARTITION to {m10I1 , m10I2 , · · · , m10In } as the
10B
marginals of the cliques A1 A2 , A2 A3 A4 , A3 A4 A5 and A4 A6 , input to OptimalMerging, where ∀i ∈ {1, 2, · · · , n}, m 4 <
10B
the total variance of the marginals is 8960 ǫ2
. Alternatively, m 10Ii
< m 2 . We restrict OptimalMerging to just consid-
2
we can merge A1 A2 and A2 A3 A4 into A1 A2 A3 A4 , merge er merging n non-overlapping cliques into m clusters. Given
2
A3 A4 A5 and A4 A6 into A3 A4 A5 A6 , add Laplace noise to a fixed m, since 8m 2 is a constant, OptimalMerging aims
A1 A2 A3 A4 and A3 A4 A5 A6 , and derive the cliques’ marginal- P m ǫ2 Q
to minimize i=1 |Si | m
10Ij
∈Si
m10Ij , which we call the
s from A1 A2 A3 A4 and A3 A4 A5 A6 . The total variance of
objective function. Now ask whether one can obtain a val-
the cliques’ marginals is 7680 . Finally, it is also possible to
ǫ2
2 ue of the objective function at most 3m10B+2 . It is easy
merge A1 A2 and A4 A6 into A1 A2 A4 A6 and merge A2 A3 A4 to see that if there is a 3-PARTITION, putting all integers
and A3 A4 A5 into A2 A3 A4 A5 , and achieve a total variance in a subset into a cluster gives at most m · 3m · m10B for
6656
ǫ2
. the objective function. Conversely, suppose that there is a
2
merging scheme such that the objective function value is at
There are two important observations from Example 2: most m · 3m · m10B . We can map the clusters to the subset-
(1) If we properly merge the cliques and then derive their s in 3-PARTITION. Note that no subset can add to more
marginals from the merged clusters, we are able to reduce than B, since otherwise the product in that cluster would
the magnitude of noise; (2) the merging procedure does not be at least m10B+10 , which is already more than the objec-
have to depend on the junction tree structure (e.g., merging 10B
A1 A2 and A4 A6 , which are not adjacent in the junction tree,
tive function value m
B B
P· 3m · m . Since each Ii is in the
range of ( 4 , 2 ) and i Ii = mB, it follows that all subsets
leads to an even smaller variance). We formally define the in 3-PARTITION have size exactly 3. This establishes the
OptimalMerging problem as follows. proof.
Definition 2. (OptimalMerging) Given a set of attributes
A = {A1 , · · · , Ad } and the set of cliques C = {C1 , · · · , Ck } Considering the hardness of OptimalMerging, we design
derived from A, merge the cliques into the set of clusters an approximation algorithm using an integer programming
CL = {CL1 , · · · , CLm } such that: (1) The total noise vari- relaxation and the constrained concave-convex procedure.
P 8m2
Q Algorithm 2 gives the pseudocode of our solution. For each
ance of the cliques’ marginals m i=1 ǫ2 |CLi | Aj ∈CLi |Ωj |
2 possible number m of clusters, we identify the corresponding
is minimum w.r.t. all possible m values, (2) each clique is in optimal merging scheme by the IdentifyOptimalMerging
exactly one cluster, and (3) the clusters contain all cliques. procedure, which will be discussed next in detail.
We first introduce the notations for modeling the Opti-
While it has been clear that finding the optimal merging malMerging problem for a given number m of clusters. For
scheme may substantially improve the accuracy of the es- simplicity of notation, we slightly abuse some notations we
timated joint distribution, the OptimalMerging problem is, used before. Suppose there are a total of d attributes and
unfortunately, NP-hard to solve. the junction tree contains n cliques. The size of the ith at-
tribute is denoted by ci . We define the occurrence matrix
Theorem 5. The OptimalMerging problem is NP-hard.
O = [oi,j ]d×n where oi,j equals 1 when the ith attribute is
Proof. We establish the NP-hardness of our problem by contained in the jth clique and 0 otherwise. Let pi be the
the reduction from 3-PARTITION [7]: Given a multiset S product of the attributes’ domain sizes in the ith clique Ci .
of n = 3m positive integers {I1 , I2P , · · · , In } such that ∀i ∈ We define zi,k ∈ {0, 1} as the indicator of the ith clique in
{1, 2, · · · , n}, B4 < Ii < B2 and i Ii = mB, can S be the kth cluster, i.e., zi,k = 1 implies that the ith clique Ci
partitioned
P into m disjoint subsets S 1 , S2 , · · · , Sm such that has been merged into the kth cluster. The objective func-
∀j Ii ∈Sj Ii = B and ∪j Sj = S? tion to find an optimal merging scheme for a given number

134
m of clusters is formulated as ith clique belonging to the kth cluster. We call this relaxed
  Problem (7).
Xm Qn zi,k Pn
p z i,k Relaxed Problem (7) is a non-convex problem since the
min ln  Qd
i=1 Pi
n
i=1  − λr
Z,r j=1 zj,k oi,j −1 third and fifth constraints are non-convex. Here we use the
k=1 c
i=1 i
constrained concave-convex procedure (CCCP) [28] to solve
s.t. zi,k ∈ {0, 1}, ∀i, k it. The CCCP method requires that the non-convex con-
Xm straints can be formulated as the difference of two convex
zi,k = 1, ∀i functions. To guarantee that relaxed Problem (7) can be
k=1 solved by the CCCP method, we reformulate the third and
kzi − zj k22 ≥ r, ∀i 6= j fifth non-convex constraints as
Xn
zi,k ≥ 1, ∀k (6) r − kzi − zj k22 ≤ 0
|{z} | {z }
i=1 Convex Convex
!
where Z is an n × m matrix with zi,k as its (i, k)th elemen- n
X d
X n
X
t, zi denotes the ith column of Z, λ is a positive constant zi,k ln pi − tk − zj,k oi,j − 1 ln ci
to balance the trade-off between the two terms, and k · k2 i=1 i=1 j=1
| {z }
denotes the ℓ2 norm of a vector. Note that the first ter- Convex
m in the objective function is to minimize the logarithm of n
!!
X
the total noise variance derived from the m marginals (see − − ln zi,k ≤0
Definition 2), the first two constraints guarantee that each i=1
clique is merged into exactly one cluster, and the last con- | {z }
Convex
straint ensures that each cluster contains at least one clique.
Moreover, the third constraint enforces the assignments of Through the reformulation, we can see that the requirement
any two clusters to be different, and we expect that the d- of the CCCP method is satisfied, making it capable of solv-
ifference between the assignments captured by r is as large ing relaxed Problem (7). The CCCP method is an iterative
as possible, leading to the term ‘−λr’ in the objective func- method. In each iteration, the CCCP method first replaces
2
tion. Since the factor 8mǫ2
is a constant for each term in the the concave parts in the objective function and constraints
2
summation of the logarithmic function, it is omitted from with their first-order Taylor expansions based on the solu-
the objective function. tion in the previous iteration and then solves the resulting
We introduce m new variables {tk }m k=1 which upper-bound
convex subproblem. Specifically, for relaxed Problem (7),
each term in the summation of the first term in the objective the lth iteration of the CCCP method solves the following
function of Problem (6) via the exponential function, i.e., problem as
Qn zi,k Pn
m
!
i=1 p
P i
n
i=1 zi,k
≤ exp{tk }, which implies that X
Qd z o
j=1 j,k i,j
−1
min ln exp{tk } − λr
i=1 ci Z,t,r
! ! k=1
n
X n
X d
X n
X s.t. zi,k ≥ 0, ∀i, k
ln zi,k + zi,k ln pi ≤ tk + zj,k oi,j − 1 ln ci .
Xm
i=1 i=1 i=1 j=1
zi,k = 1, ∀i
Then we can reformulate Problem (6) as k=1
! (l−1) (l−1)
Xm r − 2(zi − zj )T pi,j + qi,j ≤ 0, ∀i 6= j
min ln exp{tk } − λr n
X
Z,t,r
k=1 zi,k ≥ 1, ∀k
s.t. zi,k ∈ {0, 1}, ∀i, k i=1
m
!
X n
X d
X n
X
zi,k = 1, ∀i zi,k ln pi − tk − zj,k oi,j − 1 ln ci
k=1 i=1 i=1 j=1
! Pn
r − kzi − zj k22 ≤ 0, ∀i 6= j n
X (l−1)
(l−1) i=1 (zi,k − zi,k )
Xn + ln zi,k + Pn (l−1)
≤ 0, ∀k (8)
zi,k ≥ 1, ∀k i=1 i=1 zi,k
i=1
n d n
! where zi,k
(l−1)
is the solution in the (l − 1)th iteration of
X X X
zi,k ln pi − tk − zj,k oi,j − 1 ln ci (l−1) (l−1) (l−1) (l−1)
the CCCP method, pi,j = zi − zj , and qi,j =
i=1 i=1 j=1 (l−1)
! kpi,j k22 . Note that the last two terms in the third and
n
X fifth constraints of Problem (8) compose the first-order Tay-
+ ln zi,k ≤ 0, ∀k (7)
lor expansion of the corresponding convex parts at Z(l−1) ,
i=1
the solution in the previous iteration of the CCCP method.
where t = [t1 , . . . , tm ]T . Problem (7) is an NP-hard integer Problem (8) is obviously convex since both the objective
programming problem. Here we relax the first constraint of function and constraints are convex, and we can use some
Problem (7) to zi,k ≥ 0, ∀i, k, that is, zi,k is relaxed to lie solver such as the CVX [8] to solve it. Moreover, the CCCP
in [0, 1], instead of belonging to the binary set {0, 1}. After method can guarantee to converge to a local optimum of re-
the relaxation, zi,k can be viewed as the probability of the laxed Problem (7) by solving Problem (8) in each iteration.

135
 Recall that the above solution gives the probabilities of
a clique belonging to different clusters. We thus assign a Table 1: Dataset statistics
Dataset Type Data Attr. Domain
clique to the cluster with the largest probability. We cal-
Size Number Size
culate the total noise variance for this merging scheme. We
iterate the IdentifyOptimalMerging procedure for all possi- AOL Binary 619,418 45 245
ble numbers of clusters from 1 to |C|, and return the scheme Retail Binary 88,162 50 250
with the minimal total noise variance. BR2000 Non-binary 38,000 14 ≈ 232
Adult Non-binary 45,222 15 ≈ 252
4.3 Generating Noisy Marginals TPC-E Non-binary 40,000 24 ≈ 277
Given the clusters identified by Algorithm 2, we use the
old to 0. The rationale behind this strategy is that we want
Laplace mechanism to generate their corresponding noisy
to filter out the bias introduced by the positive Laplace noise
marginal tables. Let the number of clusters be m. For each
added to low true counts.
cluster’s marginal table, we add Laplace noise Lap( 2m ǫ2
) to
each entry’s count. Therefore, the noisy marginals satisfy 4.4 Producing Synthetic Datasets
ǫ2 -differential privacy. In our problem, mutual consistency
With the junction tree and the noisy marginals, we can
among different noisy marginals is critical because for any
calculate the joint distribution by Equation 1. However, di-
separator Sij = Ci ∩ Cj we need to guarantee that the noisy
rectly sampling a synthetic dataset from the joint distribu-
marginal of Sij constructed from Ci is identical to that con-
tion is computationally prohibitive. To this end, we provide
structed from Cj so as to obtain consistent inference. We
an efficient way to generate a synthetic dataset by a series of
extend the post-processing technique in [21] to the gener-
local computations. We start by randomly choosing an ini-
al case where the noisy marginals are of different sizes and
tial clique from the junction tree and sampling its attributes
attributes may not be binary.
from its marginal distribution, and then continuously sam-
Consider a set of clusters CL1 , · · · , CLl . Let A = CL1 ∩
ple other attributes in the cliques adjacent to the cliques
CL2 ∩· · ·∩CLl 6= ∅. We use TCLi to denote CLi ’s marginal,
whose attributes have been fully sampled from their condi-
TCLi [A] to denote A’s marginal constructed from CLi and
tional distribution. A clique is adjacent to another clique if
TCLi [A] ≡ TCLj [A] to denote that the two marginals are
they share a common separator. We terminate this process
identical. We want to ensure TCL1 [A] ≡ · · · ≡ TCLl [A]. We
when all attributes have been sampled. It is easy to verify
achieve this goal in two steps. The first step is to derive the
that all these probability distributions are available from the
best approximation of A’s marginal table. Let a be a possi-
noisy marginals of the cliques and that the joint distribution
ble value in A’s domain and TA (a) be the count of a in A’s
of the synthetic dataset will be identical to that calculated
marginal. Since each TCLi (a) is an independent observation
from Equation 1.
of TA (a), we use inverse-variance weighting [11] to give the
approximation of TA (a) that minimizes the variance of the
weighted average as follows: 5. EXPERIMENTAL EVALUATION
Pl In this section, we demonstrate the performance of our so-
i=1 TCL (a)/σi2 lution (referred to as JTree) by comparing with two state-of-
TA (a) = P i 2 ,
i 1/σi the-art techniques, namely PrivBayes [29] and PriView [21].
Q Moreover, for SVM classification, we also compare with Pri-
where σi2 = Aj ∈(CLi \A) |Ωj | is proportional to the variance vateSVM [22], a method specialized for SVM classification.
of TCLi [A](a). The second step is to update all TCLi ’s to We make use of five standard real datasets (both binary
be consistent with TA . The general idea is to distribute the and non-binary) in our experiments. For binary datasets, we
difference between TA and TCLi [A] to all entries in TCLi deliberately choose the ones with larger domain sizes to test
with A = a, that is the performance of JTree. We use AOL, the real dataset with
the largest domain size used in [21], and another benchmark
TA (a) − TCLi (a)
TCLi (e) ← TCLi (e) + Q , frequent itemset mining dataset Retail4 . AOL is a search
Aj ∈(CLi \A) |Ωj | log dataset that includes users’ search keywords and is pre-
where e is the entries with their A = a. processed to contain 45 binary attributes [21]. Retail is a
To make all marginals consistent, we need to perform a retail market basket dataset, where each record consists of
sequence of mutual consistency steps. The order of these the distinct items purchased in a shopping visit. We prepro-
steps is critical, otherwise previously consistent results may cess Retail to include 50 binary attributes (for the reason of
be invalidated by subsequent steps. As suggested in [21], reproducibility, we choose the top 50 most frequent items as
this problem can be avoided by enforcing a partial order the binary attributes). For non-binary datasets, we use the
under the subset relation on all non-empty intersections of same datasets used in [29]. BR2000 contains the demograph-
some subset of the clusters and following a topological order ics information collected from Brazil in 2000. Adult contains
over these intersections. For space reasons, we refer the census data from the 1994 US census. TPC-E contains infor-
interested reader to [21] for more details. mation of “Trade”, “Security”, “Security status” and “Trade
In addition to mutual consistency, we propose a simple type” tables in the TPC-E benchmark. We summarize the
yet effective thresholding strategy to mitigate the systemat- statistics of the datasets in Table 1.
ic bias due to rounding negative noisy counts to 0. We select 5.1 Evaluation Methodology
a positive integer threshold such that the noisy counts above
We consider the same analysis tasks in [29], namely k-
the threshold sum up to a number N that is closest to |D|.
way marginals and SVM classification. Since PriView on-
We then normalize all noisy counts above the threshold by
4
multiplying |D|/N and set all noisy counts below the thresh- Retail is available at [Link]

136
ly works for binary datasets and cannot generate synthetic

1
JTree JTree
datasets for SVM classification, for binary datasets we only PriView
PrivBayes
PriView
PrivBayes
report the results on k-way marginals. We follow the same

0.

0.
1

1
L2 error

L2 error
evaluation scheme used in PriView : We use privacy budget
ǫ ∈ {0.1, 1.0} and generate 200 random k-way marginals for

0.

0.
01

01
each k ∈ {4, 6, 8}. We then plot the average L2 error, which
is normalized by the data size.

0.

0.
00

00
For non-binary datasets, when k is relatively large (e.g.,

1
4 6 8 4 6 8
4, 6 or 8), a k-way marginal is normally very sparse, and k way marginals k way marginals

therefore the evaluation scheme used by PriView may be (a) Retail, ǫ = 0.1 (b) Retail, ǫ = 1.0
significantly biased. As such, we choose to follow the same

1
JTree JTree
PriView PriView
methodology used in PrivBayes. We generate all 2-way and PrivBayes PrivBayes
3-way marginals and report the average total variation dis-

0.

0.
1

1
L2 error

L2 error
tance between the original datasets and the noisy datasets.
In addition, we test the classification results with SVM clas-

0.

0.
01

01
sifiers. Due to space limitation, we only report the results on
Adult, which is the most widely used benchmark dataset for

0.

0.
00

00
classification analysis. We train SVM classifiers on Adult to

1
4 6 8 4 6 8
k way marginals k way marginals
predict whether an individual (1) is a male, (2) holds a post-
secondary degree, (3) has salary > 50K per year, and (4) (c) AOL, ǫ = 0.1 (d) AOL, ǫ = 1.0
has never married. We evaluate each classification task with Figure 2: L2 error of k-way marginals on binary
privacy budget ǫ ∈ {0.2, 0.5, 0.8, 1.0}. Each task uses 80% datasets
of the tuples in Adult as the training set and the remaining s PrivBayes in almost all cases. In some cases, the total
20% for prediction. As in PrivBayes, we also employ the variation distance of JTree is just half of that of PrivBayes.
misclassification rate as the performance metric. The only case that PrivBayes performs better than JTree
For PriView , we report the results based on its full version is ǫ = 0.2 on TPC-E, but even in this case, the accuracy of
with the ripple non-negativity technique. For PrivBayes, as JTree is still close to that of PrivBayes.
suggested in [29], we allocate half of the privacy budget on SVM Classification. In the last set of experiments, we
the construction of the Bayesian network and the other half compare JTree, PrivBayes and PrivateSVM for SVM classi-
on generating conditional distributions. We set θ = 4 (for θ- fication. Due to space limitation, we only report the results
usefulness) to select the appropriate value of the degree of a on Adult, the benchmark dataset for classification. Figure 4
Bayesian network, as recommended in [29]. For JTree, when shows the misclassification rate of each method under dif-
ǫ = 0.1, we allocate ǫ1 = 0.05 on junction tree construction ferent ǫ values. The misclassification rate of the original
and ǫ2 = 0.05 on marginal generation. For all other ǫ values, dataset (denoted as Non Private) stands for the best per-
we allocate ǫ1 = 0.1 on junction tree construction and the formance we can achieve. We can observe that JTree con-
rest on marginal generation. All experimental results we sistently outperforms PrivBayes on Adult. Compared with
report below are the average of ten runs. PrivateSVM that is specialized for SVM classification, JTree
also achieves comparable performance. We interpret the s-
5.2 Results on Binary Datasets light performance degradation as the reasonable price for
In the first set of experiments, we compare the perfor- providing a generic data publishing solution.
mance of the three solutions on the binary datasets under
different privacy budgets, as presented in Figure 2. It can 6. CONCLUSION
be seen that the accuracy of JTree is substantially better
Publishing high-dimensional data with differential privacy
than that of PrivBayes in most cases. Note that the Y-axis
guarantees is one of the most fundamental and challenging
is in log-scale. Compared with PriView , JTree also achieves
problems. In this paper, we have proposed a novel sampling-
comparable accuracy. The superiority of JTree is more ob-
based inference framework to preserve the joint distribution
servable when ǫ is small (e.g., ǫ = 0.1). For the only case
of high-dimensional data under differential privacy. This
where JTree is less accurate than PriView , the L2 error of
framework features a sophisticated systematic exploration
JTree is already very small. Furthermore, we deem that
of pairwise attribute dependencies and establishes the solid
this represents an acceptable trade-off as JTree is a gener-
inference foundation based on the junction tree algorithm,
ic framework that publishes synthetic datasets for different
along with a series of new techniques. Extensive experiments
analysis tasks, while PriView is the state-of-the-art tech-
on real benchmark datasets demonstrate that our solution
nique specifically tailored for k-way marginals. In addition,
substantially outperforms the state-of-the-art competitors.
JTree can work seamlessly on non-binary datasets, which is
important for many real-world applications.
7. ACKNOWLEDGMENTS
5.3 Results on Non-Binary Datasets We would like to thank all reviewers for their valuable
suggestions. This work was supported by RGC/GRF Grants
k-Way Marginals. In the second set of experiments, we HKBU 211512 and 12200114 and NSFC 61305071.
study the average total variation distance of PrivBayes and
JTree for varying ǫ values on non-binary datasets and present
the results in Figure 3. Recall that PriView cannot pro- 8. REFERENCES
[1] G. Acs, C. Castelluccia, and R. Chen. Differentially private
cess non-binary datasets, and therefore it is not reported histogram publishing through lossy compression. In ICDM,
here. As can be observed, JTree substantially outperform- 2012.

137
 average variation distance average variation distance svm misclassification rates svm misclassification rates
0.3 JTree 0.4 JTree 40% JTree JTree
PrivBayes PrivBayes PrivBayes 60% PrivBayes
35%
0.3 PrivateSVM PrivateSVM
0.2 Non Private Non Private
30% 40%
0.2
25%
0.1
20%
0.1
20%

0.0 0.0 15% 0%

0.2 0.5 0.8 1 0.2 0.5 0.8 1 0.2 0.5 0.8 1 0.2 0.5 0.8 1
privacy budget ε privacy budget ε privacy budget ε privacy budget ε

(a) BR2000, 2-way (b) BR2000, 3-way (a) Adult, Y=gender (b) Adult, Y=education
average variation distance average variation distance svm misclassification rates svm misclassification rates
0.3 JTree 0.4 JTree 30% JTree 30% JTree
PrivBayes PrivBayes PrivBayes PrivBayes
0.3 PrivateSVM 25% PrivateSVM
0.2 25%
Non Private Non Private

0.2 20%

20%
0.1
0.1 15%

15%
0.0 0.0 10%
0.2 0.5 0.8 1 0.2 0.5 0.8 1 0.2 0.5 0.8 1 0.2 0.5 0.8 1
privacy budget ε privacy budget ε privacy budget ε privacy budget ε

(c) Adult, 2-way (d) Adult, 3-way (c) Adult, Y=salary (d) Adult, Y=marital
average variation distance average variation distance
0.3 JTree 0.4 JTree
PrivBayes PrivBayes
Figure 4: SVM misclassification rates on non-binary
0.3 datasets
0.2

0.2
[14] G. D. Kleiter. The posterior probability of Bayes nets with
0.1
0.1
strong dependences. Soft Computing, 3:162–173, 1999.
[15] D. Koller and N. Friedman. Probabilistic graphical models:
0.0 0.0
principles and techniques. MIT Press, 2009.
0.2 0.5 0.8 1 0.2 0.5 0.8 1
privacy budget ε privacy budget ε [16] J. Lee and C. Clifton. Top-k frequent itemsets via
differentially private FP-trees. In SIGKDD, 2014.
(e) TPC-E, 2-way (f) TPC-E, 3-way [17] C. Li, M. Hay, G. Miklau, and A. McGregor. Optimizing
Figure 3: Total variation distance of k-way marginals linear counting queries under differential privacy. In PODS,
on non-binary datasets 2010.
[18] C. Li, M. Hay, G. Miklau, and Y. Wang. A data- and
[2] B. Barak, C. Dwork, S. Kale, F. McSherry, and K. Talwar. workload-aware query answering algorithm for range queries
Privacy, accuracy, and consistency too: a holistic solution under differential privacy. PVLDB, 7(5):341–352, 2014.
to contingency table release. In PODS, 2007. [19] N. Li, W. H. Qardaji, and D. Su. On sampling,
[3] Y. M. Bishop, S. E. Fienberg, and P. W. Paul. Discrete anonymization, and differential privacy or, k-anonymization
multivariate analysis. MIT Press, 1975. meets differentail privacy. In ASIACCS, 2012.
[4] G. Cormode, C. M. Procopiuc, D. Srivastava, and T. T. L. [20] N. Mohammed, R. Chen, B. C. M. Fung, and P. S. Yu.
Tran. Differential private summaries for sparse data. In Differentially private data release for data mining. In
ICDT, 2012. SIGKDD, 2011.
[5] B. Ding, M. Winslett, J. Han, and Z. Li. Differentially [21] W. Qardaji, W. Yang, and N. Li. Priview: practical
private data cubes: optimizing noise sources and differentially private release of marginal contingency tables.
consistency. In SIGMOD, 2011. In SIGMOD, 2014.
[6] C. Dwork, F. McSherry, K. Nissim, and A. Smith. [22] B. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft.
Calibrating noise to sensitivity in private data analysis. In Learning in a large function space: privacy-preserving
TCC, 2006. mechanisms for SVM learning. Journal of Privacy and
[7] M. R. Garey and D. S. Johnson. Computers and Confidentiality, 4(1):65–100, 2012.
Intractability: a guide to the theory of NP-Completeness. [23] O. Williams and F. McSherry. Probabilistic inference and
W. H. Freeman, 1979. differential privacy. In NIPS, 2010.
[8] M. Grant and S. Boyd. CVX: Matlab software for [24] X. Xiao, G. Wang, and J. Gehrke. Differential privacy via
disciplined convex programming, version 2.1. wavelet transform. In ICDE, 2010.
[Link] 2014. [25] J. Xu, Z. Zhang, X. Xiao, and G. Yu. Differentially private
[9] M. Hardt, K. Ligett, and F. McSherry. A simple and histogram publicaiton. In ICDE, 2012.
practical algorithm for differentially private data release. In [26] G. Yaroslavtsev, G. Cormode, C. M. Procopiuc, and
NIPS, 2012. D. Srivastava. Accurate and efficient private release of
[10] M. Hardt and G. N. Rothblum. A multiplicative weights datacubes and contingency tables. In ICDE, 2013.
mechanism for privacy-preserving data analysis. In FOCS, [27] G. Yuan, Z. Zhang, M. Winslett, X. Xiao, Y. Yang, and
2010. Z. Hao. Low-rank mechanism: optimizing batch queries
[11] J. Hartung, G. Knapp, and B. K. Sinha. Statistical under differential privacy. PVLDB, 5(11):1352–1363, 2012.
meta-analysis with applications. John Wiley & Sons, 2008. [28] A. Yuille and A. Rangarajan. The concave-convex
[12] M. Hay, V. Rastogi, G. Miklau, and D. Suciu. Boosting the procedure. Neural Computation, 15(4):915–936, 2003.
accuracy of differentially private histograms through [29] J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and
consistency. PVLDB, 3(1):1021–1032, 2010. X. Xiao. Privbayes: Private data release via bayesian
[13] I. F. Ilyas, W. Markl, P. Haas, P. Brown, and networks. In SIGMOD, 2014.
A. Aboulnaga. CORDS: Automatic discovery of [30] X. Zhang, R. Chen, J. Xu, X. Meng, and Y. Xie. Towards
correlations and soft functional dependencies. In SIGMOD, accurate histogram publication under differential privacy.
2004. In SDM, 2014.

138