This paper studies how to enforce differential privacy by using the randomized response in the data collection scenario. Given a client's value, the randomized algorithm executed by the client reports to the untrusted server a perturbed value. The use of randomized response in surveys enables easy estimations of accurate population statistics while preserving the privacy of the individual respondents. We compare the randomized response with the standard Laplace mechanism which is based on query-output independent adding of Laplace noise. Our research starts from the simple case with one single binary attribute and extends to the general case with multiple polychotomous attributes. We measure utility preservation in terms of the mean squared error of the estimate for various calculations including individual value estimate, proportion estimate, and various derived statistics. We theoretically derive the explicit formula of the mean squared error of various derived statistics based on the randomized response theory and prove the randomized response outperforms the Laplace mechanism. We evaluate our algorithms on YesiWell database including sensitive biomarker data and social network relationships of patients. Empirical evaluation results show effectiveness of our proposed techniques. Especially the use of the randomized response for collecting data incurs fewer utility loss than the output perturbation when the sensitivity of functions is high.
The problem of protecting individual privacy in the process of data collection, querying, mining, and release has been researched extensively. Roughly speaking, there are two scenarios in the data privacy protection. One is the privacy preserving data publishing scenario, as in which a trusted server releases datasets of individual information or answers queries on such datasets. The second one is the data collection scenario, as in which an untrusted server collects personal information from individuals.
Our paper studies how to protect privacy in the data collection scenario by using randomized response, a surveying technique for learning statistics on individuals’ sensitive attribute information such as whether the survey respondent has cheated in an exam. Randomized response is purely a client-based privacy solution. It does not rely upon a trusted third-party server and puts control over data back to clients. Given a client’s value x, the randomized algorithm executed by the client reports to the untrusted server a perturbed value y. The parameters of the randomized algorithm are chosen in such a way so that to limit the server’s ability to learn with confidence what value x was. For example, the survey respondent can flip a biased coin, in secret, and answer the truth if it comes up head, but tell the opposite answer if it comes up tail. Using this procedure, the respondent retains confidentiality of their true value due to coin randomness.
In our analysis, we adopt the rigorous differential privacy, which
was introduced by Dwork et al. [
Differential privacy of each individual value can also be achieved
by using the classic Laplace mechanism [
We conduct our empirical evaluation on a biomarker dataset and a physical activity social network extracted from from the YesiWell pilot study about health. We compare the performance of the randomized response and that of the Laplace mechanism and report their estimates and standard deviations. One advantage of the use of the randomized response in the data collection scenario is that the collected data can be released for as much analysis as needed without worrying further privacy disclosure. This is different from the output perturbation where each additional analysis consumes further privacy budget. Moreover, the use of the randomized response for collecting data incurs less utility loss than the output perturbation when the sensitivity of functions is high, as demonstrated in our experiment where we calculate the number of triangles in the social network while preserving differential privacy. 2.1
Suppose there are n individual clients C1, ..., Cn; each client Ci has some private value xi regarding a sensitive attribute X. An untrusted server needs to learn certain aggregate (statistical) properties of the individual’s private data. However the clients are reluctant to disclose their personal information xi. To ensure privacy, each client Ci only sends to the server a perturbed version yi of xi. The server collects the perturbed information from all individuals and then recovers the statistical properties by following some reconstruction procedures.
We assume every private value xi about an individual belongs to the same fixed domain VX and each xi is chosen independently at random from the same fixed probability distribution X . Note that this distribution is not private and is unknown to clients. The server aims to reconstruct the distribution X or derive some statistical properties of this distribution. The independence assumption ensures that the private information xj of all individuals Cj besides Ci tells nothing new about Ci’s own private information xi once the distribution X is learned.
To protect privacy, each individual Ci hides its own sensitive information xi by applying a randomization algorithm. A random instance yi is sent to the untrusted server. The domain of all possible output of yi is denoted by VY . The server receives yi from client Ci and tries to learn distribution X . 2.2
Differential privacy ensures that the inclusion or exclusion of one individual’s record makes no statistical difference on the output.
DEFINITION 1. (Differential Privacy [
P r[A(D) ∈ S] ≤ eϵ · P r[A(D′) ∈ S] (1)
The privacy parameter ϵ controls the amount by which the
distributions induced by two neighboring datasets may differ (smaller
values enforce a stronger privacy guarantee). A general method for
computing an approximation to any function f while preserving
ϵ-differential privacy is given in [
DEFINITION 2. (Global Sensitivity [
GSf (D) := D,D′sm.t.Dax′∈Γ(D) ||f (D) − f (D′)||1
THEOREM 1. (Laplace Mechanism [
A(D) = f (D) + (Y1, ..., Yd) where the Yi are drawn i.i.d from Lap(GSf (D)/ϵ). The Algorithm satisfies ϵ-differential privacy. 3.
Suppose there are n individuals C1, ..., Cn and each individual Ci has a private binary value xi ∈ {0, 1} regarding a sensitive binary attribute X. To ensure privacy, each individual Ci sends to the untrusted server a modified version yi of xi. Using the randomized response, the server can collect perturbed data from individuals. 3.1
A randomized response scheme on a binary attribute X follows a 2 × 2 design matrix (also called distortion matrix):
P = ( p00 p10 p01 ) p11 (2) (3) (4) where puv = P [yi = u|xi = v] (u, v ∈ {0, 1}) denotes the probability that the random output is u when the real attribute value xi for Ci is v; here puv ∈ (0, 1). In the design matrix, the sum of probabilities of each column is 1.
In this section, we focus on two types of classic queries in the data collection scenario.
• Q1: what is the probability of correctly estimating xi of individual Ci corresponding to the sensitive binary attribute X? • Q2: what is the proportion of X = 1 (X = 0)?
For Q1, the original value xi = v(∈ {0, 1}) is outputted as yi = u(∈ {0, 1}) with probability puv from the design matrix P in Equation 4. Let x^i denote the reconstructed variable of xi and P r(xi = v → x^i = v) denote the probability of correctly reconstructing the individual’s value as v from the perturbed data, given that the original value xi is v where v ∈ {0, 1}. This reconstruction probability implies how much information is preserved in the randomization process. ∑ P (yi = u|xi = v)P (x^i = v|yi = u) (5) u=0,1
Q2 aims to learn the population distribution based on the collected randomized dataset. We use π0 (π1) to denote the true proportion of value 0 (1) to be estimated in the original population. The observed proportion of value 0 (1) in the collected dataset is denoted as λ0(λ1). We denote the unbiased estimator for π0, π1 respectively as π^0, π^1.
LEMMA 1. (Chapter 1.2 [
λb 2pbb − 1 (6) where pbb ̸= 0.5 and 0 < pbb < 1. Since the observed number of records whose attribute value equals b follows binomial distribution, the variance of π^b is var(π^b) = π^b(1 − π^b) n − 1 +
The values in each row u (u ∈ {0, 1}) of the design matrix denote the probability that the random output is u. For example, p00 (p01) denotes the distortion probability that the random output value is 0 when the real individual value is 0 (1). Without loss of generality, we assume the randomized response still favors the true value, i.e., p00, p11 > 0.5. Differential privacy requires that p00/p01 ≤ eϵ. Thus we show how the randomized response will achieve differential privacy in the following result. In addition, we also give the form of the design matrix that is expected to achieve the optimal utility while satisfying the given ϵ-differential privacy.
RESULT 1. For a given differential privacy parameter ϵ, the randomized response scheme following the design matrix P in Equation 4 satisfies ϵ-differential privacy if max{ pp0001 , p11 ϵ p10 } ≤ e .
In order to maximize p00 + p11 while satisfying ϵ-differential privacy, the design matrix should have the following pattern, Prr = ( eϵ 1+eϵ
1 1+eϵ
1 1+ϵeϵ e 1+eϵ )
PROOF. Assume pp0001 = p, pp1110 = q. In order to satisfy ϵdifferential privacy, we have 1 < p ≤ eϵ and 1 < q ≤ eϵ. In this case, the distortion matrix will have the general form: Prr = ( p(q−1) pq−1 p−1 pq−1 q−1 (ppq−−11)q pq−1 )
f unc(p, q) = Prr(1, 1) + Prr(2, 2) = p(q − 1) + (p − 1)q .
pq − 1 pq − 1 (q−1)2 (p−1)2 Since ∂func = (pq−1)2 > 0 and ∂func = (pq−1)2 > 0 when ∂p ∂q p, q ∈ (1, eϵ], thus f unc will achieve its maximum value if and only if p = q = eϵ. In this way, we get the form in Equation 8.
Similarly, individual Ci can achieve differential privacy by using the Laplace mechanism. The Laplace mechanism first adds a random noise generated from the Laplace distribution with parameter 1 (with a given ϵ and the global sensitivity of 1) to the true answer ϵ xi. Since the output should be a binary value, we postprocess the perturbed result by outputting 0 if the perturbed value is less than c and outputting 1 otherwise, shown in Equation 9.
yi = {0; if xi + Lap(1/ϵ) < c 1; if xi + Lap(1/ϵ) ≥ c (9)
The probability of yi = 0 is Fxi,1/ϵ(c) and the probability of yi = 1 is 1 − Fxi,1/ϵ(c) where Fµ,b = 12 + 12 sgn(x − µ)(1 − e(− |x−b µ| )) denotes the cumulative distribution function of Laplace distribution Lap(µ, b) with the location parameter µ and the scale parameter b (and with the mean µ and variance 2b2). Thus we can map the Laplace mechanism to the randomized response with the design matrix as Plm = ( )
For a given ϵ, the perturbed result of Laplace mechanism satisfies differential privacy because the postprocessing process does not consume any privacy budget. Thus we have the following result indicating the Laplace mechanism with the postprocessing satisfies ϵ-differential privacy. We also show that the best postprocessing strategy is to set c = 0.5 for Equation 9.
RESULT 2. For a given differential privacy parameter ϵ, the Laplace mechanism based scheme with the postprocessing strategy following Equation 9 satisfies ϵ-differential privacy.
The corresponding design matrix should have the following form, ϵ Plm = ( 1 −1 e2− 2ϵ
1 e− 2 2
ϵ 1 e− 2 2 ϵ
1 e− 2 1 − 2 ) , in order to maximize p00 + p11 while satisfying ϵ-differential privacy.
PROOF. With the assumption that we need to preserve the real
value with probability greater than 0.5, c in Equation 9 is in the
range [
Plm = ( 1 − 2
1 e−cϵ 1 e−cϵ 2 1 e−(1−c)ϵ 2
1 e−(1−c)ϵ
1 − 2
)
.
(11)
where c ∈ [
we have Thus the maximum value for f unc(c) is achieved when c = 0.5. 3.3
In this paper we measure the utility in terms of the mean squared error of the estimate for xi given a randomized mechanism A.
ERRORA(x^i) = E[(x^i − xi)2] (12)
Note that by replacing P (yi = u|xi = v) in Equation 5 with values in Prr of the randomized response and those in Plm of the Laplace mechanism, we can calculate the estimates x^ respectively. We can then compare the utility of the randomized response with that of the Laplace mechanism based on Equation 12.
Intuitively, under the same privacy standard, the mechanism with larger diagonal elements in the corresponding design matrix tends to achieve better utility. The diagonal elements in Equation 8 are larger than those in Equation 11. Based on such intuition, we can prove that the randomized response actually can achieve better utility than the classic Laplace mechanism in the scenario of binary data collection.
THEOREM 2. Given ϵ, for the randomized response scheme with Prr and the Laplace mechanism based on Plm, we have ERRORrr(x^i) ≤ ERRORlm(x^i).
PROOF. We have (x^i − xi)2 = 0 with probability P r(xi = v → x^i = v) in Equation 5; and (x^i − xi)2 = 1 with probability 1 − P r(xi = v → x^i = v). So ERRORA(x^i) = 0 × P r(xi = v → x^i = v) + 1 × (1 − P r(xi = v → x^i = v)) = 1 − P r(xi = v → x^i = v).
Without loss of generality, assume v = 1, we denote the prior probability of xi = 1 as π1. According to Bayes’s theorem, we have ERRORA(x^i) = 1−( p11π1 +p12p11π0(11 − π1) +
For a given ϵ > 0, since f unc(π1) is continual and it has only two
roots for the parameter range π1 ∈ [
In this case, we have
ERRORA(x^i) = 1 − (p121 + (1 − p121)). have ERRORrr(x^i) ≤ ERRORlm(x^i).
Since pr1r1 > pl1m1 > 0.5 for all ϵ > 0, we have f unc(0.5) > 0.
Thus for all π1 ∈ (0, 1) we have f unc(π1) > 0. The same idea
can be applied for the situation of v = 0. So for π1 ∈ [
Using either the randomized response or the Laplace mechanism based approach, the server can collect private data from individuals. Both collected datasets satisfy ϵ-differential privacy (rather than nϵ-differential privacy) according to the independence assumption. Formally, D^ rr denotes the dataset generated by the randomized response following the design matrix Prr as in Equation 8. Similarly, D^ lm denotes the dataset generated by the Laplace mechanism. We define the expected error of the estimator π^b as its variance, ERRORA(π^b) = var(π^b).
THEOREM 3. Given ϵ, for the randomized response scheme with Prr and the Laplace mechanism based on Plm, we have ERRORrr(π^b) ≤ ERRORlm(π^b).
PROOF. From Equation 7, we see comparing the utility of estimation from D^ rr and D^ lm relies only on pbb in the distortion m1ea−tri2x;PFo.rFtohrethraenLdaopmlaizceedmreescphoannsisem,w,weehahvaevepr1pr1l0m0==pr0pr0l1m1==eϵ1+ϵ−1.
ϵ e 2 Since pr1r1 > pl1m1 > 0.5 for all ϵ > 0, we have ERRORrr(π^b) ≤ ERRORlm(π^b), according to Equation 7.
In the previous section, we compared the Laplace mechanism
and the randomized response approach in collecting information
about one private binary attribute. In this section, we extend to a
sensitive polychotomous attribute with t(t ≥ 2) mutually exclusive
and exhaustive classes. Due to space limits, we skip all proofs of
results in this section. Refer to [
Similarly we have two types of classic queries in the data collection scenario.
• Q1: what is the probability of correctly estimating xi of individual Ci corresponding to the sensitive attribute X? • Q2: what is the proportion of X = 1, · · · , t?
Let P r(xi = v → x^i = v) denote the probability of correctly reconstructing the individual’s value as v from the perturbed data, given that the original value xi is v where v ∈ {1, · · · , t}. This reconstruction probability implies how much information is preserved in the randomization process.
The corresponding unknown proportions to be estimated are denoted as π1, ..., πt. The randomization device is such that an individual belonging to the vth category(v = 1, ..., t) reports a random value u (u = 1, ..., t) with probability puv and tu=1puv = 1 for all v = 1, ..., t.
The matrix P = {puv} is called the design matrix, where the sum of each column in P is 1.
In other words, in the optimal form of the design matrix, all diagonal entries are set as t−1e+ϵeϵ and all off-diagonal entries are set as t−11+eϵ . We can also achieve differential privacy by adding Laplace noise. The global sensitivity is t − 1. So the Laplace noise is generated from the distribution Lap( t−ϵ 1 ). Because the perturbed outputs are numerical, we postprocess to map them to an index value from 1 to t as shown in Equation 20.
yi = 1; if xi + Lap((t − 1)/λ) ∈ (−∞, c1] 2; if xi + Lap((t − 1)/λ) ∈ (c1, c2] ... u; if xi + Lap((t − 1)/λ) ∈ (cu−1, cu] ... t; if xi + Lap((t − 1)/λ) ∈ (ct−1, ∞) where cu is in the range [u, u + 1].
Note that in this scenario, the strategy of perturbation by Laplace mechanism is also a special case of the randomized response strategy. We give the form of the corresponding design matrix in Equation 21. The following result shows such Laplace mechanism with postprocessing satisfies ϵ-differential privacy. We also give the best postprocessing strategy with the corresponding design matrix.
RESULT 4. The Laplace mechanism of adding random noise from distribution Lap( t−ϵ 1 ), with postprocessing strategy following Equation 20 is ϵ- differentially private.
In order to maximize the sum of the diagonal elements in the corresponding design matrix for Laplace mechanism, Plm, we have cu = u + 0.5 for u ∈ {1, 2, ..t − 1} in Equation 20. The corresponding design matrix Plm = {puv} has the following form, puv = Fv, t−ϵ 1 (1.5); if u = 1
1 − Fv, t−ϵ 1 (t − 0.5); if u = t Fv, t−ϵ 1 (u + 0.5) − Fv, t−ϵ 1 (u − 0.5); otherwise (21) where Fv, t−ϵ 1 is the cumulative distribution function of Laplace distribution with mean value of v (v ∈ {1, 2, ..., t}), variance of 2λ2 and λ = (t − 1)/ϵ. 4.3
Intuitively, the utility depends on the diagonal elements in the design matrix. The Laplace mechanism based approach degrades the utility by favoring the values near the correct value. The sum of diagonal elements in Plm is actually smaller than that in Prr (for details see the proof of Theorem 4). In consistence with the binary case, the randomized response achieves better utility than the classic Laplace mechanism in data collection scenario.
THEOREM 4. Given ϵ, for the randomized response scheme with Prr and the Laplace mechanism based on Plm, we have ERRORrr(x^i) ≤ ERRORlm(x^i).
Similarly as the binary case, we define the expected error of the estimator π^v for the proportion of category v (v ∈ {1, 2, ..., t}) as its variance, the diagonal element in the unbiased estimate of (19) (20) dispersion matrix disp(^) following the randomized mechanism A. We have ERRORA(π^v) = disp( ^ )vv where v ∈ {1, 2, ..., t}.
However, it is intractable to directly prove that the randomized response strategy following the design matrix in Equation 19 could achieve lower expected error of the estimator π^v than the Laplace mechanism based approach following Equation 21 does. Intuitively we can see that the Laplace mechanism based approach will degrade the utility by favoring the values near the correct value. As shown in the proof of Theorem 4, the sum of the diagonal elements in Plm is smaller than that in Prr, which indicates that the estimation based on the randomized response mechanism following Prr is expected to achieve smaller error than that based on the Laplace mechanism following Plm. 5.
To be consistent with notations, we denote the set of variables by X = {X1, · · · , Xs}. Note that, for ease of presentation, we use the terms “attribute” and “variable” interchangeably. Each variable Xu has du mutually exclusive and exhaustive categories. We use iu = 1, · · · , du to denote the index of its categories. For each data record, we apply the randomized response model independently on each sensitive variable Xu using different settings of distortion.
Formally, let πi1,··· ,is denote the true proportion corresponding to the categorical combination of s variables (X1i1 ,· · · , Xsis ) in the original data, where iu = 1, · · · , du (u = 1, · · · , s), and X1i1 denotes the i1th category of attribute X1. Let be a vector with elements πi1,··· ,is arranged in a fixed order. The combination vector corresponds to a fixed order of cell entries in the contingency table formed by these s variables. Similarly, we denote λi1,··· ,is as the expected proportion in the randomized data.
For the case of s multi-variables, we denote λµ1,··· ,µs as the expected probability of getting a response (X1µ1 , · · · , Xsµs ) and the vector with elements λµ1,··· ,µs arranged in a fixed order. For example, given a dataset with two variables, Gender with domain values {male, female} and Race with domain values {black, white,asian}, we have d1 = 2 and d2 = 3. The vector = (π11, π12, π13,π21, π22, π23)′ corresponds to a fixed order of cell entries πij in the 2 × 3 contingency table. π12 denotes the proportion of records with male and white.
Let P = P1 × · · · × Ps, we can obtain = P
= (P1 × · · · × Ps) where × stands for the Kronecker product 1.
The original database D is changed to Drr after randomization. An unbiased estimate of based on one given realization Drr follows as
^ = P −1 ^ = (P1−1 × · · · × Ps−1) ^ where ^ is the vector of proportions calculated from Drr corresponding to and Pu−1 denotes the inverse of the matrix Pu. 5.2
Many measures (including entropy, mutual information, Pearson
Correlation, G2-likelihood) can be expressed as one derived
random variable (or function) from the observed variable . Similarly,
1Kronecker product is an operation on two matrices, an m-by-n
matrix A and a p-by-q matrix B, resulting in the mp-by-nq block
matrix
(22)
(23)
its estimate from the randomized data can be considered as
another derived random variable from the input variable ^ . One natural
question is how to calculate the variance of those estimates. In the
following, we introduce the use of the delta method [
Let Z be a random variable derived from the observed random variables Xi (i = 1, · · · , k): Z = g(X1, X2, ..., Xk). According to the delta method, a Taylor approximation of the variance of a function with multiple variables can be expanded as k var{g(X1, X2, ..., Xk)} = ∑{gi′(θ)}2var(Xi)
i=1 ∑ gi′(θ)gj′ (θ)cov(Xi, Xj ) + o(n−r) k + ∑
i̸=j=1 where θi is the mean of xi, gi′(θ) is the ∂g(X1,X2,...,Xk) evaluated ∂Xi at θ1, θ2, · · · , θk.
We use the entropy function as an example. The entropy function from information theory is defined as follows: (24) (26) H(X) = −
∑ j∈Range(X) πj log2πj (25)
We can estimate the entropy of the discrete random variable X with possible values {1, 2, .., t} in the original dataset using the estimator of the distribution and the estimator of the dispersion matrix disp( ) calculated following Equations 17 and 18.
RESULT 5. The variance of the estimated entropy can be computed following Equation 24 where i, j ∈ {1, 2, ..., t}, k = t, Xi = π^i , ∂g(X1,∂XX2i,...,Xk) = log2π^i + ln12 and var(Xi) = disp( ^ )(i, i), covi̸=j (Xi, Xj ) = disp( ^ )(i, j).
Different from the entropy which involves only one variable, some measures such as chi-square statistics involve multiple variables.
χ^2 = n ∑ i j ∑ {πij − πi+π+j }2 πi+π+j It is easy to see χ^2 can be considered as one derived variable from the observed elements π^X1···Xs and the marginal totals of the contingency table. Following the same delta method, we can derive its variance.
We conduct our empirical evaluation using the real dataset collected from the YesiWell pilot study. The study was conducted in 2010-2011 as the collaboration among several health laboratories and universities to help people maintain active lifestyles and lose weight. Data gained from this study includes information of various domains such as biomarker, biometrics, social activities.
We conduct experiments on a chosen table which contains 248 individuals’ biomarker information. In particular, we focus on two sensitive attributes: LDL cholesterol (LDL) with six domain levels and Total cholesterol (TC) with three domain levels. Under each differential privacy threshold ϵ, we compare the performance of the randomized response (with the corresponding derived design matrix Prr) and that of the Laplace mechanism (with the corresponding derived design matrix Plm) from the utility preservation perspective. We focus on proportion estimates of categories based 0.6 0.5 0.4 0.3 ˆ π 0.2 0.1 0
Original RR LM on LDL levels, the derived entropy of LDL, and the χ2 statistics of LDL and TC. For each statistics, we report their estimate values and derive standard deviations for two strategies: randomized response and Laplacian mechanism.
We also conduct experiments on the YesiWell physical activity social network which contains 185 users and 684 interactions. Each interaction, represented as an edge between two user nodes, is considered sensitive in our context. We study how to enforce edge differential privacy in our social network, i.e., the inclusion or exclusion of a link between two individuals from the graph makes no statistical difference to the results found. We focus on two classic graph features: the degree sequence D = {di} where each entry represents the degree of node i, and the number of triangle sequence N∆ = {N∆(i)} where each entry represents the number of triangles involving node i. We compare the performance of the randomized response and that of the Laplace mechanism and report their estimates and standard deviations for the above two graph statistics.
In addition to our above study in the data collection scenario, we also compare our randomized response with two mechanisms, Laplacian mechanism and smooth sensitivity, in the data query answering scenario where the trusted server keeps all unperturbed values and returns differential privacy preserving query answers. 6.2
1 2 3 4 LDL Level 5 6
We calculate the estimates of the entropy of the LDL. Figure 3 shows the estimation results of the calculated entropy values from 10−40 5 4.5 4 3.5 3 X) 2.5 ˆH( 2 1.5 1 0.5 0 −0.51.5 550 500 450 400 2 350 χ 300 250 200 1501.5 LM
RR 1 two approaches with varying ϵ. We can see that the red line (corresponding to the randomized response) is more close to the green line (corresponding to the real entropy value) than the blue line (corresponding to the Laplace mechanism). The bar values (corresponding to their standard deviation values) also clearly show the superiority of the randomize response. We calculate the estimates of the chi-square statistics between the LDL and TC. Figure 4 shows the estimation results of the χ2 statistics from two approaches with varying ϵ. We can see that the red line (corresponding to the randomized response) generally lies more close to the green line (corresponding to the real entropy value) than the blue line (corresponding to the Laplace mechanism) with varying ϵ values. The randomized response also has much smaller standard deviation values than the Laplace mechanism, which also indicates better utility preservation.
The graph of the YesiWell social network contains 185 nodes and 684 edges. In the data collection scenario, the untrusted server collects the link relationship information from users. The link relationship between two users is sensitive and should be protected. The collected social network data with n users and m relationships can be represented as an adjacency matrix An×n with 2m non-zero entries where Aij = 1 denotes the presence of an relationship between user i and user j, and Aij = 0 otherwise. In our setting, for Aij , the client Ci applies the randomized response (or the Laplace mechanism) to send the server a randomized output Yij ∈ 0, 1. After collecting all randomized relationships, the server then applies the reconstruction process and generates one instance of the social network with 2m non-zero entries (denoted as A^). The generated graph instance satisfies ϵ differential privacy and can be released for any analysis. In this experiment, we conduct performance comparison between the randomized response and the Laplace mechanism using two graph features, the degree sequence D = {di} and the number of triangle sequence N∆ = {N∆(i)}. Figure 5 and Figure 6 show comparison results in terms of the degree sequence and the number of triangle sequence respectively.
LM RR
LM−global 3 ǫ 1 2 4 5 6
Figure 5 shows the average entrywise error of the degree sequence calculated from different approaches with varying ϵ. In the figure, we denote the Laplace mechanism as LM and the randomized response as RR, each of which uses its randomized graph topology respectively. We also report the comparison with the output perturbation method, LM-global, which adds the Laplace noise directly to the query output. Note that LM-global is used in the data query answering scenario where the server is assumed to have all the true unperturbed data. However, any differential privacy preservation query consumes a separate privacy budget. On the contrary, the randomized data collected from LM and RR can be released for any analysis with the same privacy threshold. We can observe in Figure 5 that the randomized response achieves better utility preservation than the Laplace method in the data collection scenario and the LM-global incurs less estimation error than both RR and LM (due to its small global sensitivity value GSD = 2).
Figure 6 shows the average entrywise error of the number of
triangle sequence calculated from different approaches with varying
ϵ. Note that the global sensitivity of N∆ is 3(n − 2). We
denote the approach of directly adding the Laplace noise based on
the global sensitivity as LM-global. We denote the approach of
adding the Laplace noise based on the smooth sensitivity [
Randomized response techniques have been extensively
investigated in statistics (e.g., see a book [
Differential privacy research has been significantly studied from
the theoretical perspective, e.g., [
Local differential privacy was formally proposed in [
In this paper, we measure the utility preservation in terms of the
variance. Several theoretical works on the privacy mechanism
design (e.g., [
The authors would like to thank anonymous reviewers for their valuable comments and suggestions. This work was supported in part by U.S. National Science Foundation (DGE-1523115 and IIS1502273) and U.S. National Institute of Health (1R01GM103309).