tbl_patients

Query:

The query above will group the results by "diagnosis", which are our partitions, and then count the number of "user_id" per partition.

If we use standard DP mechanisms to answer this query, we would basically add noise to the total counts of each partition/diagnosis, and release e.g. the following result on the right:

(without differentiating noise added and total count, here shown just for illustration)

What is the problem with releasing this result on the right?

• In tbl_patients the user with id "003" is the only one that has "diabetes". Therefore, just by outputting the partition "diabetes" using a standard DP mechanism, it becomes easy to differentiate tbl_patients from a neighboring table without the user with id "003", since the partition "diabetes" would not appear in the result without this user.
• For this reason, the algorithm use above would violate differential privacy, as intuitively we should not be able to differentiate the results of neighboring datasets/tables.

Result:

How do we solve this problem?

1. If you have domain knowledge (i.e. you know which partitions exist without looking at the data) you can pass the list of possible partitions and the DP mechanism would release only the result for these partitions (adding noise to them even if their total count is zero).
2. More generally, another option is to use a DP mechanism just to find the possible partitions and then pass these partitions to a noise-adding mechanism such as the one seen above, to release the noisy result only for such partitions.
• In the literature, this approach is referenced as differentially private "partition selection" or "set union".

Previous work related to DPSU [1, 2] designed mechanisms with two phases:

• Phase 1 builds a histogram on ${\cup }_i{W}_i$ by iterating over the users and getting their contributions in terms of items.
• To provide DP, the contribution of every single user needs to be bounded in terms of number of items and weights.
• Thus, STEP 1 samples items from $W_i$ into $\overline{W_i}$ to limit user contribution to at most ${\mathrm{\Delta }}_0$ items.
• In STEP 2 a total weight budget of $1$ is distributed among the items in $\overline{W_i}$, and the histogram is updated for each item in $\overline{W_i}$.
• After Phase 1, which runs the two steps above for all existing users, a histogram $H$ is built.
• Phase 2 takes as input the histogram $H$ constructed in the previous phase.
• STEP 3 adds noise to the total weights of each item in the histogram.
• Finally, in STEP 4, only items with a noisy weight above the threshold $\rho$ will be outputted.

There are a few options for DP selection mechanisms, with the Exponential Mechanism (EM) [1] being one of the most used.

• Using EM, we select some element $i$ from a dataset $D$ with probability: $Pr[EM(D)=i]\propto \exp (\frac{\epsilon \cdot f(i,D)}{2\cdot \mathrm{\Delta }f})$
• So in practice we have a random selection with a probability of selection for every element in the full domain of elements (i.e. all known/existing elements - the image above shows the full domain of the example).
• Moreover, the random selection is biased towards elements with high score (which is want we want), and we also have DP guaranteed (going into details of EM is out of scope now).
• To select k elements, we simply use EM iteratively, renormalizing probabilities and removing elements selected at every iteration.

Now consider a dataset with 1 million elements to select the top-10. How do we do this with DP?

• As mentioned above we can apply EM 10 times
• This means normalizing probabilities of 1 million elements 10 times, and then also running a random selection 10 times.
• It easy to see that this iterative process is not practical for real-world systems, especially when the selection is part of a larger and more complex analysis pipeline.
• There is an equivalent approach in the literature [2] that is more efficient:
• It adds Gumbel noise once to all 1 million scores, then sorts the noisy score and returns the 10 elements with highest noisy scores.
• However, even this one-shot approach can still be time consuming for large datasets.
• In fact, we saw that, without considering the time to access the database, (i.e. only counting the time for the private top-k selection) this approach takes around 0.5 seconds to do a DP top-10 selection on a dataset with one million elements.

How can we improve the computational efficiency of DP top-k selection?

• To address computational efficency within DP top-k selection, [2] proposed selecting elements from a restricted domain, which we explain below.

Restricted domain top-k mechanisms select k elements by choosing from the elements that have the top-$\overline{k}$ scores, for a chosen $\overline{k}\ge k$. The image on the right illustrates this setting.

• This means only processing $\overline{k}$ elements, instead of the full domain (as it was with EM).
• This improves computational efficiency dramatically.
• In fact, our experiments showed DP top-k selection on restricted domain up to 200 times faster than traditional DP selection.

What is the problem with DP top-k selection on Restricted domain?

• DP mechanisms working on restricted domain still need to provide DP guarantees for the full domain of all elements.
• That's because the restricted domain itself (i.e. the top-$\overline{k}$ elements) is sensitive.
• Therefore, simply enforcing DP on the restricted domain is not sufficient to guarantee privacy.
• Moreover, proving DP on the full domain when accessing only the restricted domain is a really complex task.

• In this context, the current approach is to start with a traditional DP top-k mechanism, and modify it such that it maintains the DP guarantee on the full domain while only selecting from the restricted domain.
• The problem with this approach is that you have to go through a complex DP analysis for every DP top-k mechanism you want to use on restricted domain.
• This limits the applicability of restricted domain mechanisms, especially because new improved top-k mechanisms are being proposed every year.
• Therefore, a highly practical setting (restricted domain selection) becomes of limited use in practice.

How can we solve this problem?

1. In our work detailed below, we propose a "framework" that takes a novel mechanism-agnostic approach to create restricted domain mechanisms.
• We develop an easy-to-use framework to allow any DP top-k mechanism to be used on restricted domain.
• Our framework guarantees DP for the full domain by default, therefore it does not need any additional DP proof.

Our "framework" for differentially private top-k selection aims to be highly practical.

• It takes as a black-box any given DP top-$k$ mechanism and automatically "converts" it into a restricted domain mechanism.
• The framework provides a unified proof of privacy "for free", which is already valid by default for any given mechanism.
• This property greatly simplifies adoption in practice, as it eliminates the need for any privacy analysis to work on restricted domain.

The framework can be built on top of any regular database system without internal modification, leveraging existing optimized data infrastructure. See the image below.

1. When a user requests DP top-$k$ queries.
2. Our framework first queries the database system.
3. The database returns the true top-$\overline{k}$ elements.
• Then the framework applies, as a blackbox, any traditional DP top-$k$ selection mechanism to the top-$\overline{k}$ together with additional private computation.
4. Finally it returns at most $k$ elements while guaranteeing DP by default for the full domain.

• The novelty is that our framework can be used to easily create new restricted domain mechanisms from any traditional DP top-$k$ mechanism, while guaranteeing DP for the full domain by default and without needing any additional DP proof.
• Therefore, our approach eliminates the hassle involved in the DP analysis of individual mechanisms.
• This means that every time a new traditional DP selection mechanism is proposed in the literature, e.g. [3, 4], we can already directly leverage it on restricted domain by using our framework.

Aside from being practical, our framework also have better utility (formally proven) compared to previous restricted domain mechanisms [2].

• Moreover, our experiments confirm the improved utility on multiple datasets and settings.
• Some settings show our framework returning three times more elements than previous restricted domain mechanisms [2].

In summary, our framework has FOUR main advantages that make it highly practical:

1. It adapts traditional DP top-k mechanisms to restricted domain automatically, without needing any DP proof.
2. By selecting from a restricted domain, it is computationally efficient (e.g. 200 times faster than one-shot full domain approaches).
3. Has better utility compared to previous restricted domain mechanisms (e.g. returning three times more elements than previous mechanisms).
4. Can be directly used on top of any database system, without needing to modify such system.

Consider we have a dataset of users, where each user has a set of words.

• In this setting, we consider potential privacy problems with one sensitive word per user.
• The idea is to replace each sensitve word by a new word that cannot be easily linked back to the original word, thus improving privacy.
• Additionally, we want to keep the context of the sentence.

Below we an example of such dataset:

Thus, in this setting, we are protecting users at the individual word level.

• Our main goal is to take an input word and perturb it to obtain an output word that would be indistinguishable from the input word.
• i.e. an adversary that sees the output word would not be able to tell the input word with high probability, which in turn protects the user's identity.
• But we also intentionally want to maintain the original context that can be observed by the aggregation of words from each user.
• i.e. we are still interested in the Context for, e.g., Intent Classification, in a downstream NLP task.
• Note that we could also privatize all words in a sentence, while still keeping the context, with similar results.

It is no surprise that disclosing just a single word is enough to impact a user's privacy, as it may represent a password, disease diagnosis or political preference. So this is a really important problem to address.

For text privatization, standard DP approaches do not work well in the context above.

• For standard DP to work, we would have to ensure that a word can be replaced by any other word in the vocabulary
• This would potentially ruin the utility of any DP algorithm by adding an excessive amount of noise.

To deal with this issue, previous research [1] has proposed two modifications:

1. Privatize words in the continuous embedding space.
2. Use a generalization of DP for metric spaces called metric differential privacy (mDP) [2]

See below an example of word embeddings where each user's data is a word with their home city.

• For each word, we perform a lookup in the embedding space (in this case 2-dimensional) and the word embedding is the returned vector numerically representing each word.

Using mDP, previous methods [1] generally work with three main steps as we see in the image below.

1. First, they retrieve the embedding vector of the input word that needs to be privatized.
2. In the second step, the vector is perturbed by, for example, adding random noise.
3. Finally, as a noisy vector is unlikely to exactly represent a valid word, the output is the word that is closest to the noisy vector (obtained via nearest neighbor search in the representation space).

What are the problems with the privatization approach above?

• That approach considers the representation space as non-sensitive (i.e. public), as it does not account for privacy loss in the nearest neighbor search (STEP 3).
• Moreover, each existing mechanism assumes one specific distance metric (e.g. Euclidean in [1]) is being used when proving DP.
• Also, the approach would not be viable to privatize text on-device, due to large storage and computational requirements.
• Finally, the noise added to a vector does not take into account the density of the region that the vector lies in, which tends to reduce utility.
• For example, if a word is on a highly dense area in the embedding space, the noise added could be small, as the word already has some indistinguishability.
• However, the current mechanisms do not adapt the noise depending on the area of the word embedding vector being privatized.

How do we solve the problems above?

1. In our work shown below, instead of seeing text privatization as a vector perturbation problem, we pose the task as a selection problem.
2. Additionally, we use binary embeddings and optimized nearest-neighbors search, to make our approach possible to be used on-device.
• These two modifications will solve all the problems described above, as we detail next.

Example of embedding space

• Let the image on the left be a two-dimensional embedding space, with a few vectors represented as dots.
• In previous work, the perturbation method was the same for all vectors, including both the red and the green embedding vectors.
• On the other hand, our approach adds less randomness/noise to high density areas (red vector) and also adds more randomness/noise to low density areas (green vector).
• This dynamic noise behavior, adapted to the density, intuitively makes sense:
• The high density areas (red vector) already have vectors that are somewhat indistinguishable, so less randomness is required.
• In other words, if you add small noise to the red vector, it is already hard to know which of the vectors in that area was the actual input.
• However, if you add small noise to the green vector (low density area), then it is still easy to identify it as the input - so more noise is required here to make the output indistinguishable.
• This more-efficient randomness adaptation approach led to 42% better utility than previous work [1].

Moreover, as usual on selection problems, we do not release the scores, just the selected element.

• Therefore, unlike previous work, the embedding space can be sensitive, as they are used to define the scores.
• Moreover, the mechanisms do not depend on the distance metric used to define the scores.
• This means we can use any distance metric, and the mDP guarantee will still hold.

As mentioned above we also use binary embeddings to represent the words.

• We use recent research [3] that converts real-valued embedding vectors into binary representations, explicitly aiming at keeping the semantic meaning while transforming representations.
• They show binary embeddings losing only approximately 2% in semantics, but with the upside of reducing the embeddings' size by 97%.
• They use an autoencoder model, where an encoder binarizes the real-valued word vector and a decoder reconstructs such input vector - so the binarized vector is the latent representation of the autoencoder.
• Another advantage is that binary data leverages hardware-level optimizations for nearest neighbors search.
• Additionally, we can implement randomization with efficient operations such as XOR.
• These properties allow privatization on-device, as showed in our experiments:
• The required disk space for the embeddings decreased 98% compared to previous work [1].
• Execution time decreased by 68% compared to previous work.

Therefore, our approach has the following THREE main practical advantages:

• It allows text privatization on-device (fast execution time and small storage requirement)
• Improved utility with density-aware randomness
• More flexibility of use in practice: allows the use of sensitive embeddings and any distance metric.