A representative solution is PrivBayes [9], which constructs a Bayesian network to model the data correlations and conditional probability distributions, allowing one to approximate the distributions of the original data using a set of low-dimensional marginal distributions. However, such an approach suffers from poor data utility and high communication cost, since too much noise is added when there are too many attribute pairs resulting in unreliable conditional probabilities. Moreover, most approaches generally ignore the different roles a dimension may play for a speci c query -one dimension may be more important than another for a particular query. Additionally, one dimension may release more information than another if the same amount of noise is added; thus evenly allocating the total privacy budget to each dimension degrades the performance.

In this paper, we provide a two-phase mechanism (DP2-Pub) consisting of a Markov-blanket-based learning process and an invariant post randomization (PRAM) process satisfying local differential privacy to overcome the above difculties. Our contributions can be summarized as follows:

To capture the dependencies between the attributes in the dataset, we resort to differentially private Bayesian network construction, employing the exponential mechanism to attribute pairs using the mutual information as the score function.

We propose the procedure of attribute clustering with a Markov blanket learning algorithm based on the constructed Bayesian network. Our most fundamental purpose is to split attributes into several lowdimensional clusters with high intra-cluster cohesion and low inter-cluster coupling, thus obtaining a reasonable allocation of privacy budget determined by the conditional independence among attributes and the importance of each cluster.

Invariant PRAM is an important perturbation technique for privacy protection, which transforms each record stochastically in a dataset using delicately pre-selected probabilities. It ensures no loss of statistical information, thus can signi cantly preserve data utility. Motivated by this, we provide a doubleperturbation mechanism to achieve invariant PRAM and differential privacy for two-valued and multivalued attributes, then apply it to each attribute cluster.

Resorting to the randomized mapping based postprocessing property for differential privacy, we prove that the proposed double-perturbation mechanism satis es differential privacy.

To tackle the data privacy preservation problem for the scenario where each individual contributes a single data record to a semi-honest server, we extend our DP2-Pub mechanism to handle the highdimensional data publication in a local-differentialprivacy manner, in which each user locally perturbs its data satisfying local differential privacy, then the server conducts all the operations including attribute clustering and post randomization over the privatized data.

We evaluate the performance of data utility on four real-world datasets from two aspects, the total variation distance between the original dataset and the perturbed dataset and the classi cation error rate of 108 SVM classi cation on the perturbed dataset. Experi-109 mental results indicate that our approach can obtain 110 higher data utility of the published data compared 111 with the state-of-the-art.

The rest of this paper is organized as follows. We provide 113 a literature review in Section 2. Section 3 formulates our 114 problem and presents necessary background knowledge on 115 Bayesian network, differential privacy, random response 116 and post randomization. In Section 4, we propose our DP2-117 Pub mechanism by detailing the constructions of differen-118 tially private Bayesian network, attribute clustering, and 119 invariant PRAM. Comprehensive experimental studies on 120 four real-world datasets are presented in Section 6. Section 121 7 concludes the paper with a future research discussion.

Various differentially private mechanisms for high-124 dimensional data publications have been proposed in recent 125 years. In this section, we briefly review the most relevant 126 works from two perspectives: under centralized setting or 127 distributed setting, and discuss how our work differs from 128 the existing ones.

A powerful approach of dimensionality reduction is the 131 Bayesian network model proposed in [9], in which Zhang 132 et al. developed a differentially private scheme PrivBayes 133 for publishing high-dimensional data. PrivBayes rst con-134 structs a Bayesian network to approximate the distribution 135 of the original dataset, then adds noise into each marginal 136 of the Bayesian network to guarantee differential privacy, 137 next constructs an approximate distribution of the original 138 dataset, and nally samples the tuples from the approximate 139 distribution to construct a synthetic dataset.

Researchers also have developed sampling techniques to 141 support differentially private high-dimensional data publi-142 cations. In [10], Chen et al. provided a solution to protect the 143 joint distribution of the dimensions in a high-dimensional 144 dataset compared with PrivBayes. They rst established a 145 robust sampling-based approach to investigate the depen-146 dencies over all attributes for constructing a dependence 147 graph, then applied a junction tree algorithm to provide an 148 inference mechanism for deriving the joint data distribution. 149 Both [9] and [10] constructed a dependency graph and 150 generated a differentially private marginal table to enforce 151 consistency constraints over all marginals, during which 152 they evenly split the privacy budget into portions, each 153 being used for a pair of attributes.

In [11], Li et al. proposed a differentially private data 155 synthetization technique called DPCopula using Copula 156 functions to handle multi-dimensional data. In [12], Xu et 157 al. developed a high-dimensional data publishing algorithm 158 under differential privacy to optimize the utility by rst 159 projecting a -dimensional vector of user's attributes into a 160 lower -dimensional space using a random projection, then 161 adding Gaussian noise to each resultant vector to obtain a 162 synthetic dataset. The authors represent each user's feature 163 attributes as a -dimensional vector and ignore the different 164 roles a dimension may play for a speci c query and the correlation between different attributes.

The approaches mentioned above mainly consider centralized scenarios. Some efforts have also been devoted to differentially private high-dimensional data publications under distributed setting. Based on PrivBayes, Cheng et al. [13] considered a multi-party setting from multiple data owners and proposed a differentially private sequential update of the Bayesian network (DP-SUBN) approach, allowing the parties to collaboratively identify the Bayesian network that best approximates the joint distribution of the integrated dataset. Wang et al. [14] introduced a framework with a simple and generic aggregation and decoding technique. LoPub can rst learn from the distributed data records to build correlations and joint distributions of attributes, then synthesize an approximate dataset achieving a good compromise between local differential privacy and data utility. In [18], Ju et al. also considered the high-dimensional data publication problem under local differential privacy in the crowdsourced-sensing system. They proposed an aggregation and publication mechanism which provides local privacy guarantees for crowd-sensing users, approximates the statistical characteristics of high-dimensional perception data and publishes synthetic data. Wang et al. [19] proposed two mechanisms for collecting and analyzing users' private data under local differential privacy, which can collect multidimensional data with both numerical and categorical attributes. In [20], Domingo-Ferrer developed several random-response-based complementary approaches for multi-dimensional data preservation. In [21], Takagi et al. presented a privacy-preserving phased generative model (P3GM) for high-dimensional data, which employs a twophase learning process for training the model to increase the robustness to the differential privacy constraint.

In light of the above analysis, the following aspects distinguish our work from the existing approaches. First, since the sensitivity of distinct dimensions are different and evenly allocating the total privacy budget to each dimension cannot obtain good performance, we consider the privacy budget allocation problem to realize attribute clustering with a reasonable allocation of privacy budget. Second, we design a double-perturbation mechanism to achieve invariant PRAM instead of generating noisy conditional distributions of the Bayesian network, then apply it to each attribute cluster, which can signi cantly improve the data utility while satisfying local differential privacy.

In this paper, we consider the following problem: a data server collects data containing a vast amount of individual information and aims to release an approximate dataset to third parties for their uses such as data analysis and rec-222 ommendations. Let Local differential privacy ensures the similarity between the output results of any two records. Random response (RR) [27] is currently the most widely used technique for achieving local differential privacy.

Random response (RR) is a technique developed in social science to collect statistical data about individuals' sensitive information. Its main idea is to provide data privacy protection by making use of the uncertainty of responses to sensitive questions. Privacy comes from the randomness of the answers while accuracy comes from the noise generation procedure [28].

Post randomization (PRAM) is another important perturbation technique for privacy protection, which stochastically transforms each record in a dataset using pre-selected probabilities. For a random variable with categories , let , and

. The basic idea of PRAM is to select a transition probability matrix with for . Then the original category is changed to with probability . Let denote the transformed variable. We have , , and .

Mathematically, PRAM is equivalent to RR. Therefore many mathematical results developed for RR such as the local differential privacy guarantee can be applied to PRAM [29]. In this paper, we employ PRAM for the case when a trusted data server is available (Section 4), where all the data can be processed at the server to maintain differential privacy, and RR for the case when the server is semihonest, in which case local differential privacy is adopted for collecting data from each user to the server (Section 5).

In this section, we propose a novel differentially private high-dimensional data publication mechanism based on a double-perturbation process, namely DP2-Pub, assuming the availability of a trusted server that can access the original data. We rst present an overview on DP2-Pub, then detail its modules in the following subsections.

Figure 2 illustrates the main procedure of DP2-Pub, which runs in two phases of attribute clustering and data randomization, with both being performed by the trusted server. Since both phases require access to the original dataset, we divide the total privacy budget into two portions with being used for the rst phase and for the second phase, and demonstrate that the two phases are both differentially private.

To learn the correlations between different attribute variables, we adopt the approach of constructing a differentially private e a c h cl u st er, f oll o wi n g t h e pri n ci pl e st ati n g t h at t h e s m all er 4 4 t h e pri v a c y b u d g et, t h e hi g h er t h e l e v el of pri v a c y pr e s er- or c 2 eit h er r e m ai n s u n c h a n g e d wit h pr o b a bilit y q , or i s 4 9 4 c h a n g e d t o t h e ot h er v al u e wit h t h e pr o b a bilit y of 1 -q ; t h at 4 9 5 i s q 1 1 = q 2 2 = q a n d q 1 2 = q 2 1 = 1 -q . T h u s, t h e tr a n siti o n 4 9 6 pr o b a bilit y m atri x Q of t h e t w o-v al u e d v ari a bl e X i s a 2 × 2 4 9 7 m atri x, w hi c h c a n b e s h o w n a s f oll o w s:

N ot e t h at t h e tr a n siti o n pr o b a bilit y m atri x 5 0 0 s ati s fi e s ⃗ λ = Q ⃗ π .

5 0 1 I n t hi s s etti n g, l et q = e ϵ 1 + e ϵ . T h e n t h e l o c al diff er e nti al 5 0 2 pri v a c y c a n b e s ati s fi e d a s: of the perturbed data . The advantage of this doubleperturbation mechanism lies in that there is no need to know the probability distribution of the original data in advancewe actually do not know the probability distribution of -the transition probability matrix of the original data is thus constructed adaptively. After obtaining the perturbed data with , we can obtain the estimate of the original attribute variable distribution:

(4)

Then we compute the transition probability of each variable for the second perturbation as follows:

Accordingly, we obtain the transition probability matrix for the second perturbation:

Therefore, to obtain the invariant PRAMed data of the attribute variable , we apply to the perturbed data during the second perturbation. These two phases of data perturbation with and successfully realize an invariant PRAM with , where can be considered as the inverse of while ensuring that is also a transition probability matrix.

The perturbation of the multivalued attributes is similar to that of the two-valued one. Since an attribute cluster may include more than one two-562 valued or multivalued attribute variables which are strongly 563 correlated, one can treat all these variables as a compound 564 one. Thus an invariant PRAM for compound variables [29] 565 is needed, which rst computes the transition probabil-566 ity matrix for each attribute variable, then computes the 567 transition probability matrix for the compound one. dataset achieving -differential privacy according to the sequential composition theorem [30].

Accordingly, one can obtain the following theorem.

Theorem 2. The DP2-Pub satis es -differential privacy according to sequential composition theorem [30].

The emergence of Internet of Things (IoT) has changed people's daily life and the way the world learns, where mobile devices, home appliances, transportation facilities and crowd sensors can all be used as data acquisition equipment in IoT. It provides a platform for the seamless communication between smart devices and sensors in a smart environment and allows information sharing across platforms. IoT devices and the generated data can reveal personal information of the users including their behaviors and preferences [31]. Despite the bene ts of the IoT, it raises privacy concerns of the sheer amount of data. Most of existing privacy-preserving data publishing mechanisms focus on the processing of the collected data with a trustful central server. However, what is stored in the server is unprotected while the central server is vulnerable to internal attacks or single-point attacks; even the server itself may not be trustworthy -it is generally semi-honest, i.e., honest-butcurious, which faithfully follows the protocol but tries its best to infer as much knowledge as possible. Moreover, the data or updates (under federated learning framework) held by the resource-constrained devices can be easily observed or analyzed, which may pose a threat to the privacy protection of participating devices and ultimately discourages participation in the distributed model. Therefore, in this section, we extend our DP2-Pub mechanism to consider a semi-honest server. A number of users generate multi-dimensional data records, then send them to a server who intends to release an approximate dataset to third-parties for various applications. Formally, each user contributes a data record constituting a dataset , where denotes the data record of user and is the total number of records/users. Figure 4 illustrates the main procedure of DP2-Pub with a semi-honest server, which includes three main steps: privacy preservation of local data satisfying local differential privacy, Markov-blanket-based cluster learning based on Bayesian network, and the PRAM perturbation on the private data. Both the attribute clustering and PRAM perturbation are conducted at the data server, while the local differential privacy protection is performed by each user. Although the data server is semi-honest, it can only access the private data processed by each user.

We rst propose a local randomization using RR on each user's data making it satisfy LDP, then the sanitized data is sent to and aggregated at the central server. Each user has a -dimensional data record , and the perturbation process is conducted on each dimension with the privacy budget . t o t h e f oll o wi n g r ul e i n R R:

of w hi c h k = 1 , 2 , ⋯ , s. f er e nti al pri v a c y. T h er ef or e, t h e D P 2-P u b m e c h a ni s m wit h 7 2 a s e mi-h o n e st s er v er i s diff er e nti all y pri v at e wit h pri v a c y 7 2 b u d g et ϵ . privacy budget is completely allocated to the local privacy procedure. For the parameter used in the construction of the Bayesian network, we test . Since the time cost for larger values is typically higher, we do not try the cases of . Based on our experiments, we observe that the influence of on the experimental results is not obvious. The reason possibly lies in that the structure of the Markov blanket can help to accurately learn the data correlations between different attributes. In the following section, we present the experimental results of .

In this subsection, we carry out independent runs for each of the experiments mentioned above and report the averaged results for statistical con dence.

For the task of examining the accuracy of -way marginals, we compute all the -dimensional attribute unions and compare the averaged variation distance of PrivBayes, JTree, DPPro, DP-Pub and DP-Pub , with a varying privacy budget from to .

Figure 5 shows the average results of the variation distance of each approach on the four datasets. From Figure 5, one can see that the average variation distances of these three approaches decrease when increases over the four datasets. It is obvious that when is larger, smaller noise is required, and the data utility is higher. One can also observe that our approach clearly outperforms PrivBayes and DPPro in all cases for ACS and NLTCS, while for BR2000 and Adult, the relative superiority is more pronounced when is small. There are several reasons that DP2-Pub outperforms PrivBayes, JTree and DPPro. First, PrivBayes constructs a Bayesian network while JTree adopts a junction tree algorithm to model the data correlation, and both of them generate a set of noisy conditional distributions of original datasets. That is, for each attribute-parent pair, both PrivBayes and JTree generate differentially private conditional distributions by adding Laplace noise which makes the data utility of the dataset drastically decrease. In our approach, we only utilize the Bayesian network to learn the correlations between different attributes and adopt our proposed invariant post randomization to achieve data perturbation, which ensures that there is almost no loss of statistical information. The probability distribution of each attribute variation is basically unchanged after the double-perturbation. Second, the random projection method DPPro does not consider the data characteristics and only preserves the pairwise distance when generating the random projection matrix, thus it may lead to relatively low utility especially when there exist data correlations between different attributes. In our approach DP2-Pub, we learn the data correlations of the original dataset and consider the importance of different attributes when allocating the privacy budget. DP-Pub performs better than DP-Pub according to the results shown in Figure 5. This is counter-intuitive as centralized differential privacy usually performs better than local differential privacy because centralized differential privacy adds noise based on the sensitivity of a particular the misclassi cation rate is not obvious when is larger than

. This indicates that a higher privacy level with a small 909 leads to a lower data utility. in the rst phase, we present the procedure of attribute clustering using the Markov blanket model based on the differentially private Bayesian network to achieve attribute clustering and obtain a reasonable allocation of privacy budget. In the second phase, we design a detailed invariant post randomization method by conducting a doubleperturbation while satisfying local differential privacy. Our privacy analysis shows that DP2-Pub satis es differential privacy. We also extend our mechanism making it suitable for the scenario with a semi-honest server in a localdifferential privacy manner. Comprehensive experiments on four real-world datasets demonstrate that DP2-Pub outperforms existing methods and improves data utility with strong privacy guarantee.

In our future research, we intend to combine other effective dimensionality reduction techniques [36,37] with differential privacy to investigate their impact on the data utility of published data. Particularly, we intend to combine DP with manifold learning [36], which is a popular approach for non-linear dimensionality reduction that maps a high dimensional data space into a low-dimensional manifold representation of the data while preserving a certain form of geometric relationships between the data points.