Enhancing Utility in the Watchdog Privacy Mechanism

Industries and governments are increasingly sharing data to unlock economic and societal benefits through advances in data analytics and machine learning. However, such data also contains sensitive information about individuals or businesses, which makes the privacy regulators, users, and data providers concerned about the leakage of confidential information, either explicitly or implicitly. In signal processing and information theory, data privacy is underpinned in terms of a measure called information lift[1, 2].

To evaluate how much private data $X$ is informative about the confidential data $S$, the lift measures the change in the posterior belief $p(s|x)$ from the prior belief $p(s)$ for each instance of $s$ and $x$ by

It is clear that a small lift indicates limited private information gain by the adversary and therefore the more private $X$ is. The lift is the elementary measure in almost all information leakage measures, e.g., mutual information [1, 3], Sibson mutual information [4, 5, 6], $\alpha$-leakage [7] and local differential privacy [8, 9]: as proved in [2], if lift is bounded, all these leakage measures are also bounded.

The existing approach to attain lift-based privacy is the watchdog method proposed in [2]. For a specific privacy constraint, i.e., a threshold $\epsilon$ on the lift, the watchdog method filters out and privatizes the high-risk symbols of $X$. The authors in [2] adopted a uniform approach: merging all high-risk symbols together into a ‘super’ symbol, which is proved in [10, 6] to be the optimal privatization scheme in attaining data privacy. However, this uniform approach neglects an important issue in data privacy: to achieve the benefits of data sharing, the privatized data should provide a satisfactory level of usefulness in $X$.¹¹1The data utility is usually quantified by average performance measures such as mutual information [3], $f$-divergence [11] and Hamming distortion [12]. We use mutual information in this paper. Despite the relaxation attempts in [10, 6], the complete merging method minimizes the resolution of high-risk symbols and significantly deteriorates data utility, which is at odds with the purpose of data sharing.

In fact, even a small alteration can greatly enhance the data utility. In Table 1, we arbitrarily cut the high-risk symbol set (of size 7) into two subsets, each of which is then privatized individually. The utility (measured by mutual information) is increased significantly without sacrificing too much data privacy, which remains below the design constraint $\epsilon$. This not only shows that the complete merging approach is an ‘overkill’ in terms of data utility, but also suggests a partitioned privatization approach.

In this paper, we propose the subset merging method for watchdog mechanism to enhance the data utility. Finding the best partition of high-risk symbols set to achieve optimal utility is generally a combinatorial problem. Accordingly, we propose a heuristic greedy algorithm to find good subsets to merge, which guarantees data privacy. To do so, this greedy algorithm tries to search the finest partition of the original high-risk symbols set that ensures the resulting lift of the whole dataset does not exceed $\epsilon$. It starts with the singleton partition of high-risk symbols (highest resolution) and iteratively merges symbols until lift values of the resulting subsets are all below $\epsilon$. Numerical simulations show that our proposed algorithm enhances utility significantly and maintains the privacy leakage constraint.

Denote random variables $S$ and $X$ the sensitive and public data, respectively. The joint distribution $p(s,x)$ describes the statistical correlation between $S$ and $X$. To protect the privacy of $S$, we sanitize $X$ to $Y$ by the transition probability $p(y|x)$. Here, for each $x,y$, $p(y|x)=p(y|x,s),\forall s$ and therefore the Markov chain $S\rightarrow X\rightarrow Y$ is formed.

The watchdog method is based on the logarithm of the lift measure

For each $x\in\mathcal{X}$, denote the maximum symbol-wise information leakage by $\max_{s\in\mathcal{S}}|i(s,x)|$, where

Applying an upper bound $\epsilon$ to $\omega(x)$ for all symbols $x\in\mathcal{X}$, the whole alphabet $\mathcal{X}$ is divided into two subsets: the low-risk subset is given by $\mathcal{X}_{\varepsilon}\triangleq\{x\in\mathcal{X}:\omega(x)\leq\varepsilon\}$ that is safe to publish, and the high-risk symbol set

that requires some treatment before the data publishing.

The authors in [10, 6] adopt a uniform randomization scheme

where $R(y)$ is complete merging solution, e.g., where there is only one super symbol $y^{*}\in\mathcal{X}_{\varepsilon}^{c}$ such that $R(y^{*})=1$ for all $x\in\mathcal{X}_{\varepsilon}^{c}$ and $R(y)=0$ otherwise.

After randomization, the log-lift is given by $i(s,y)=\log\frac{p(y|s)}{p(y)}$ where $p(y|s)=\sum_{x\in\mathcal{X}}p(y|x)p(x|s)$ due to the Markov property and $p(y)=\sum_{x\in\mathcal{X}}p(y|x)p(x)$. We can extend the notion of the log-lift, and $\omega(x)$ from a single $x\in\mathcal{X}$ to a subset $\mathcal{X}_{Q}\subseteq\mathcal{X}$ [10]:

where $p(\mathcal{X}_{Q}|s)=\sum_{x\in\mathcal{X}_{Q}}p(x|s)$ and $p(\mathcal{X}_{Q})=\sum_{x\in\mathcal{X}_{Q}}p(x)$.

Applying $p(y|x)$, the value of $\max_{y\in\mathcal{Y}}\omega(y)$ as the upper bound on privacy leakage after randomization is given by [10]

It is obvious that $\max_{y\in\mathcal{X}_{\varepsilon}}\omega(y)\leq\varepsilon$, so it attains the privacy constraint. However, the value of $\omega(\mathcal{X}_{\varepsilon}^{c})$ is variable and depends on the joint probability distribution.

In Example 1, the leakage in the high-risk subset after randomization is $\omega(\mathcal{X}_{\varepsilon}^{c})=0.0627$, which is an order of magnitude smaller than the original privacy constraint $\varepsilon=0.8$, based on which $\mathcal{X}_{\varepsilon}^{c}$ was obtained. Although this small leakage guarantees a very high level of privacy, it damages utility drastically, the utility decreases from $H(X)=1.6034$ to $I(X;Y)=0.5269$. On the other hand, when a threshold $\varepsilon$ is given as the privacy constraint, it is acceptable to just keep the privacy leakage less than $\varepsilon$, even if it becomes very close to this threshold. Thus, in the next section, we propose a subset merging method to enhance utility where the privacy leakage increases, but remains under $\varepsilon$ to the extent possible.

In this section, we introduce an approach to enhance utility while maintaining a set privacy constraint. We measure utility by mutual information which for the bi-partition $\{\mathcal{X}_{\varepsilon},\mathcal{X}_{\varepsilon}^{c}\}$ and complete merging randomization $\mathcal{X}_{\varepsilon}^{c}$ is given by [10]

Clearly, the utility depends on $p(x)$ for $x\in\mathcal{X}_{\varepsilon}^{c}$ and the overall $p(\mathcal{X}_{\varepsilon}^{c})$. Our proposed approach to enhance data utility is through increasing data resolution. That is, we propose to randomize subsets of $\mathcal{X}_{\varepsilon}^{c}$ separately rather than the complete merging of the whole set $\mathcal{X}_{\varepsilon}^{c}$.

Let $[p]=\{1,2,\cdots,p\}$ and consider a bi-partition $\{\mathcal{X}_{\varepsilon},\mathcal{X}_{\varepsilon}^{c}\}$, a further partitioning of elements in $\mathcal{X}_{\varepsilon}^{c}$ denoted by $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}=\{\mathcal{X}_{1},\cdots,\mathcal{X}_{p}\}$, and complete merging randomizations $R_{i}(y),i\in[p]$ where $\sum_{y\in\mathcal{X}_{i}}R_{i}(y)=1$. In other words, we partition $\mathcal{X}_{\varepsilon}^{c}$ to subsets $\mathcal{X}_{i}$, so $\mathcal{X}_{\varepsilon}^{c}=\cup_{i=1}^{p}\mathcal{X}_{i}$ and each subset $\mathcal{X}_{i}$ is randomized by the corresponding randomization $R_{i}(y)$. Note that for $y\in\mathcal{X}_{i}$ we have $p(y)=\sum_{x\in\mathcal{X}_{i}}p(y|x)p(x)=p(\mathcal{X}_{i})R_{i}(y)$. The resulting mutual information $I(X;Y)$ is

Then the normalized mutual information-loss for partition $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}$ on $\mathcal{X}_{\varepsilon}^{c}$ is defined as

Since $p(\mathcal{X}_{i})\leq p(\mathcal{X}_{\varepsilon}^{c})$ for $i\in[p]$ the data resolution increases for each $x\in\mathcal{X}_{i}$ and this can results in a larger mutual information and hence a lower utility loss. The following definition and derivations formalize this observation.

If $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}^{{}^{\prime}}$ is a refinement of $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}$ and $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}$ is an aggregation of $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}^{{}^{\prime}}$ then $\text{NMIL}(\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}^{{}^{\prime}})\leq\text{NMIL}(\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}})$. This is because

Generally, finding an optimal partition $\mathcal{P}_{\mathcal{X}_{\varepsilon}^{c}}$ that maximizes utility while maintaining the privacy constraint is combinatorial since it depends on the high-risk symbol probabilities $p(x)$, $x\in\mathcal{X}_{\varepsilon}^{c}$ and the joint probability distribution. However, we can use $\varepsilon$ as a stop criteria to make a heuristic agglomerative algorithm for obtaining a refinement of $\mathcal{X}_{\varepsilon}^{c}$ to enhance utility as much as possible.

To make a comparison between Algorithm 1 and complete merging, we randomly generated 1000 joint distributions $p(s,x)$ where $|\mathcal{X}|=20$ and $|\mathcal{S}|=13$. For each distribution, after randomization we obtained maximum privacy leakage of high-risk symbols $\max_{y\in\mathcal{X}_{\varepsilon}^{c}}\omega(y)$, maximum overall privacy leakage $\max_{y\in\mathcal{Y}}\omega(y)$, and the utility loss NMIL under Algorithm 1 and complete merging for different values of $\varepsilon\in\{0.25,0.5,0.75,\cdots,2.25,2.5\}$. Then for each $\varepsilon$, we derived the mean value and standard deviation of $\max_{y\in\mathcal{X}_{\varepsilon}^{c}}\omega(y)$, $\max_{y}\omega(y)$, and NMIL across these 1000 observations.

In Fig. 1 the mean value of $\max_{y\in\mathcal{X}_{\varepsilon}^{c}}\omega(y)$ is depicted for each $\varepsilon$, as well as its standard deviation (shown as tolerance bars). As expected, complete merging makes a strong guarantee on privacy leakage and keeps both mean and standard deviation much less than $\varepsilon$ in all cases. In contrast, algorithm 1 increases the privacy leakage and lets it be closer to $\varepsilon$ compared to complete merging, but crucially it still keeps the mean value and the corresponding deviation less than $\varepsilon$ in all cases. As the value of $\varepsilon$ increases, the standard deviation is also increased. This is because when $\varepsilon$ increases, the privacy constraint is less strict and consequently the size of $\mathcal{X}_{\varepsilon}^{c}$ decreases. As a result, the sample size to calculate the mean value of privacy leakage reduces, which causes a larger deviation.

Fig. 2 shows the normalized mutual information loss under Algorithm 1 and complete merging. It demonstrates that Algorithm 1 enhances utility substantially for each value of $\varepsilon$.

Finally, to have a clear privacy-utility trade-off (PUT) comparison, we present PUT curves for both Algorithm 1 and complete merging in Fig. 3. For each $\varepsilon$, the mean value of overall privacy leakage $\max_{y\in\mathcal{Y}}\omega(y)$ is shown versus the corresponding mean value of NMIL. Clearly, Algorithm 1 enhances utility significantly while satisfying the privacy leakage constraint. For a very strict constraint on privacy ($\varepsilon\leq 0.5$), complete merging results in perfect privacy with total utility loss where $\text{NMIL}=1$. However, Algorithm 1 keeps the average utility loss less than $1$.

In this paper, we introduced a method to enhance utility in the watchdog privacy mechanism. We showed that it is possible to maintain the privacy constraint and improve utility. In our approach, instead of randomizing the whole high-risk partition, we randomized subsets of high-risk symbols separately. Then we proposed a heuristic greedy algorithm to find subsets of high-risk elements and at the same time keep the leakage of each subset less than the privacy constraint, $\varepsilon$. The simulation results showed substantial utility enhancement and preservation of the privacy constraint.

In future research, it would be interesting to consider how to develop more efficient subset merging algorithms. Investigation of effective parameters like subset size and different privacy and utility measures could be helpful. It would be also beneficial to apply the proposed algorithm to real world data sets and measure actual practical utility. It would be also beneficial to apply the proposed algorithm to real world datasets and measure the obtained utility.