Differentially Private Streaming Data Release under Temporal Correlations via Post-processing

Data collection and analysis in many real-world scenarios are performed in a streaming fashion, such as location traces [23], web page click data[13], and real-time stock trades. However, releasing data continuously may result in privacy risks. To this end, differentially private streaming data release have been thoroughly studied [4, 3, 8, 12, 13, 14, 15, 16, 24, 9]. The curator of the database can use a differentially private mechanism, such as Laplace Mechanism (LM), that adds noises to the query results at each time point for satisfying a formal privacy guarantee called $\epsilon$-Differential Privacy ($\epsilon$-DP) [10], where $\epsilon$ is the parameter (i.e., privacy budget) controlling trade-off between privacy protection and utility of data release. A small $\epsilon$ indicates a high level of privacy and thus requires adding a larger amount of noise. Taking location traces as an example to elaborate, Fig. 1 (a) (c) (d) illustrate how differentially private location statistics are released using LM at each time point where (a) represent real-time location raw data sets (i.e., values of longitude and latitude of residence, company, shopping mall respectively) of users in a database $D$ collected by devices with GPS sensors (i.e., GPS, GNSS) [23], (c) are the true counts of each location computed by a count query function $f(D)$ and (d) what will be released and sent to the public are streaming private counts through a differentially private mechanism such as Laplace Mechanism (LM) [11].

However, recent studies [6, 5, 29, 28, 25, 18] reveal that, when the data are correlated, more noises have to be added to prevent leakages which deteriorates the utility. They point out that differential privacy algorithms suffer extra privacy leakage on correlated data and develop techniques to enhance differential privacy with a smaller $\epsilon$. In the context of streaming data release, a Markov chain could be used to model the temporal correlations. For example, as shown in Fig.  1 (b), temporal correlation is manifested as the transition probabilities between different locations, which can be obtained through public information such as road networks or traffic data. Based on the temporal correlation presented in Figure 1(b), we have the probability of users proceeding from location $loc1$ to $loc2$ will be $Pr(l^{t+1}=loc2|l^{t}=loc1)=1$ if we have the knowledge that another road is congested. Cao et al. [6, 5] quantified such a private leakage and proposed a special privacy definition on temporal correlated data named $\alpha\text{-}DP_{\mathcal{T}}$, to calibrate a smaller privacy budget in order to cover the extra privacy leakage caused by temporal correlations. Song et al. [25] proposed Wasserstein Mechanism for Pufferfish privacy (i.e., a privacy notion that generalizes differential privacy) and Markov Quilt Mechanism specifically when correlation between data is described by a Bayesian Network or a Markov chain. Similar to [6, 5], they calculate an enlarged $\epsilon$ to enhance the privacy but sacrifice more utility. Hence, the challenge is how to boost the utility of differentially private streaming data release on temporally correlated data.

Our approach to addressing the aforementioned issue involves capitalizing on the existing temporal correlations as prior knowledge about the original data through post-processing. Although post-processing [17, 20, 22, wang21] has been extensively researched as a means to enhance the utility of differential privacy, current methods are ill-equipped to deal with temporal correlations. Post-processing primarily aims to refine differentially private (noisy) results by enforcing them to comply with certain ground-truth constraints or prior knowledge about the data. For instance, deterministic consistency constraints between data points are frequently employed in previous studies to represent inherent properties of the data (e.g., released counts in histograms should be integers). In this study, we apply the post-processing technique to improve the utility of differentially private streaming data release in the presence of temporal correlations. By accounting for temporal correlations along with other consistency constraints, we strive to obtain the most accurate current counts which could be estimated from previous private counts while approximating the true current counts.

In this study, we formulate post-processing as a nonlinear optimization problem within the Maximum A Posteriori (MAP) framework, accounting for both probabilistic constraints of temporal correlations and deterministic consistency constraints. Similar to [6, 5, 25], we assume that temporal correlations are public knowledge and are expressed by a transition matrix. As illustrated in Fig. 2, our approach leverages the transition matrix to enhance the utility of differentially private counts. Thus, we pose the problem of determining the most plausible counts that satisfy the constraints (both probabilistic and deterministic) and exhibit the least distance from the released private data. To model this probabilistic distribution, we employ the knowledge of Laplace noise distribution and introduce a Markov chain model to calculate the distribution of true counts. Finally, extensive experiments demonstrate and validate the effectiveness of our methods.

To summarize, our contributions are as follows:

• •

  To the best of our knowledge, this paper presents the first attempt to enhance the utility of differentially private data release under temporal correlations. We propose a post-processing framework using maximum a posteriori estimation, which incorporates both probabilistic correlations and deterministic constraints.

• •

  We implement the post-processing framework for temporal correlations in the differentially private continual data release. Specifically, we formulate this problem as constrained nonlinear programming, which can be solved using off-the-shelf optimization software.

• •

  Our experiments on synthetic data demonstrate the effectiveness of the proposed approach. We show that the utility of differentially private data is significantly improved, with nearly a $100$-fold reduction in mean square error under a strict privacy budget, while preserving temporal correlations between data.

We would like to note that this work is an extension of our previous poster paper [2], in which we briefly presented the idea without delving into technical details. This paper provides a clearer and more in-depth exploration of our previous work, offering a comprehensive understanding of the proposed MAP-based post-processing framework.

Several well-studied methods exist to enhance the utility of differentially private data, as post-processing is an effective tool. In this section, we review related works on improving the utility of private data through post-processing.

One of the most widely studied approaches for utility enhancement is the utilization of consistency constraints [17, 20] in data (e.g., the sum of the released data should be a fixed number, or the released values should be integer in the case of counting queries). In our location traces scenario, these consistency constraints can be expressed by the sum of location records or the total number of users as a fixed value (e.g., $n$) for each time point, with counts always being integers. Previous works formulate the problem as a least squares estimation (LSE) problem [17] or a maximum likelihood estimation (MLE) problem [20], demonstrating the effectiveness of such post-processing approaches.

Hay et al. [17] focused on improving the accuracy of private histograms through post-processing, solving an LSE problem given consistency constraints such as $sum$, $sorted$, and $positive$ to find the ’closest’ private histograms that also satisfy these constraints. Furthermore, Lee et al. [20] considered noise distribution (Laplace distribution in their scenario) to boost the utility of private query results. They formulated their post-processing problem as an MSE problem and employed the ADMM algorithm to solve the programming problem.

However, when publishing statistics continually, the data points are often temporally correlated. The post-processing methods mentioned above only focus on single-time data release and cannot efficiently capture probabilistic temporal correlations. Moreover, it remains unclear how to formulate probabilistic correlations as constraints, as existing works assume deterministic constraints as prior knowledge about the data. We also observe that many existing works on differentially private streaming data release neither provide a formal privacy guarantee under temporal correlations [4, 3, 8, 12, 13, 14, 15, 16, 24] nor offer reasonable utility for private outputs. Therefore, our study represents the first attempt to enhance the utility of DP with formal privacy under temporal correlations.

This section will introduce and formulate the primary issue we aim to address. First, below we present the notations used throughout this paper. We use ${D}$ to represent a bounded database consisting of $n$ users. We prefer to use bold letters to indicate vectors. We use $r^{t}_{l}$ to denote a specific query output at a given time point $t$ and location $l$. $\mathcal{T}$ represents a transition matrix modeling temporal correlations between data. More detailed notations are in Table  1.

Temporally Correlated Stream Data. In our scenario of location traces mentioned above, we assume that $n$ people (labeled from $1$ to $n$) staying at $m$ locations (labeled from $1$ to $m$) respectively at single time point $t$ (shown in Fig. 1 (a)). Let $\mathbf{Loc}$ denote the sets of locations. Naturally, the data at each time point are temporally correlated: for each user, her current location depends on the previous location in the form a transition matrix $\mathcal{T}$. Without loss of generality, we assume the transition matrix is the same for all users and is given in advance since it can be learned from public information such as road networks. This assumption follows existing works [5, 25].

Differentially Private Stream Data Release. A server collects users’ real-time locations $l^{t}$ at time $t$ in a database $D$, and aims to release differentially private query results over $D$. In particular, we consider a query function $f:D\rightarrow\mathbf{N}^{m}$ that counts the total number of people at each location over the entire publishing time $T$, denoted as $f(D)$. The query outputs are represented by $\mathbf{R}=(R^{1},\dots,R^{t},\dots,R^{T})$ and $R^{t}=(r^{t}_{1},\dots,r^{t}_{m})$. Many existing works, such as [4, 3, 8, 12, 13, 14, 15, 16, 24], have considered a similar problem setting as ours. However, due to temporal correlations, increased noise is added to the true answers to preserve strict privacy [5, 25], which reduces the utility of the released private counts. Our question is: can we leverage the temporal correlations to improve the utility of differentially private data via post-processing (while preserving the enhanced privacy as [5, 25])?

In this section, we will explain how to formulate the post-processing problem for streaming data release under temporal correlations. To address the above-mentioned challenge, we use post-processing, allowing us to refine the private counts using publicly known prior knowledge.

Intuition. Our core idea is that the temporal correlations can be seen as probabilistic constraints on the data. We can formulate the problem as determining the most probable query outputs $\mathbf{\hat{R}}$ that satisfy such constraints when given $\mathbf{\tilde{R}}$, leveraging the knowledge of $\mathcal{T}$ as shown in Fig. 1 (b). Specifically, we aim to solve the programming problem of maximizing $Pr(\mathbf{\hat{R}}|\mathbf{\tilde{R}})$, subject to the transition matrix and other consistency constraints. Our method will demonstrate that the estimation depends on the noise distribution and the joint distribution of true counts, which are determined by the mechanism used and the inherent correlations within the raw data.

In this section, we present experimental results that demonstrate the effectiveness of our proposed MAP framework for post-processing continuous data release under temporal correlations. To validate our method, we apply it to both synthetic and real-world datasets, and evaluate its performance in terms of accuracy and utility. Furthermore, we have made our code available on GitHub²²2https://github.com/DPCodesLib/DBSec23, enabling other researchers to reproduce our experiments and extend our work. For statistical significance, all experiments are performed 50 times and the mean values are reported as the final results.

Environment. The experiments were executed on CPU: $Intel(R)Core(TM)\\ i7-11370H\ @3.30GHz$ with $Python$ version 3.7.

Nonlinear Programming Solver. The solver used for solving nonlinear constrained programming is $Gurobi\ Optimizer\ version\ 10.0.1$ API for $Python$.

Level of Temporal Correlations. To evaluate the performance of our post-processing method under different temporal correlations, we introduce a method to generate transition matrix in different levels. To begin with, we default a transition matrix indicating the “strongest” correlations which contains probability 1.0 in its diagonal cells. Then, we utilize Laplacian smoothing [26] to uniform the possibilities of $n\times n$ transition matrix $\mathcal{T}^{S}$ of ‘strongest’ correlations. Next, let $p_{ij}$ denote the element at the $i$th row and $j$th column of $\mathcal{T}^{S}$. The uniformed possibilities $\hat{p}_{i,j}$ can be generated from (11), where $s$ ($0\leq s<\infty$) is a positive parameter that controls the levels of uniformity of probabilities in each row. That’s, a smaller $s$ means stronger level temporal correlations. Also, We should note that, different $s$ are only comparable under the same $n$.

In this paper, we have shown that temporal correlations are often present in differential privacy data releases and proposed a MAP framework to address the post-processing problem in this context. Our experiments demonstrate the effectiveness of incorporating temporal correlations into the post-processing step, resulting in significant improvements in accuracy and utility.

Furthermore, our work suggests that the MAP framework can be a useful tool for addressing other post-processing problems involving correlated data, such as Bayesian DP and Pufferfish Privacy Mechanisms. While our approach assumes independence between users, this may not always hold true in practice. Future work could explore how to extend our framework to address post-processing for streaming data releases under temporal correlations when users are correlated.

Overall, our work contributes to advancing the state of the art in differential privacy data releases by providing a new perspective on post-processing under temporal correlations and opens up new avenues for future research in this area.

This work was partially supported by JST CREST JPMJCR21M2, JST SICORP JPMJSC2107, JSPS KAKENHI Grant Numbers 19H04215, 21K19767, 22H03595 and 22H00521.

Additionally, Xuyang would like to express appreciation to tutor for his meticulous instruction, as well as to his family and friend Yuchan Z. for their encouraging support in his research endeavors.