Differentially Private n-gram Extraction
Authors: Kunho Kim
Sivakanth Gopi
Janardhan Kulkarni
Sergey Yekhanin
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Ngram Extraction

Abstract: We revisit the problem of $n$-gram extraction in the differential privacy setting. In this problem, given a corpus of private text data, the goal is to release as many $n$-grams as possible while preserving user level privacy. Extracting $n$-grams is a fundamental subroutine in many NLP applications such as sentence completion, auto response generation for emails, etc. The problem also arises in other applications such as sequence mining, trajectory analysis, etc., and is a generalization of recently studied differentially private set union (DPSU) by Gopi et al. (2020). In this paper, we develop a new differentially private algorithm for this problem which, in our experiments, significantly outperforms the state-of-the-art. Our improvements stem from combining recent advances in DPSU, privacy accounting, and new heuristics for pruning in the tree-based approach initiated by Chen et al. (2012).

Differentially Private n-gram Extraction"
Kunho Kim Microsoft kuki @microsoft.ccm
Sivakanth Gopi Microsoft Research si zigopi @mi crosoft. com
Janardhan Kulkarni Microsoft Research j akul @mi crosoft. com
Sergey Yekhanin Microsoft Research yelhhaninemiccroofff..o
Abstract
We revisit the problem of n-gram extraction in the differential privacy setting. In this problem, given corpus of private text data, the goal is to release many n-grams as possible while preserving user level privacy. Extracting n-grams a fundamental subroutine in many NLP applications such as sentence completion, response generation for emails etc. The problem also arises other applications such as sequence mining, and is generalization of recently studied differentially private set union (DPSU). this paper, we develop a new differentially private algorithm for this problem which, in experiments, significantly outperforms the ttate-of-the-art. Our improvements stem from combining recent advances in DPSU, privacy accounting, and new heuristics for pruning in the tree-based approach initiated by Chen et al. (2012) (CAC12).
Introduction
We revisit the problem of n-gram extraction in the differential privacy setting. In this problem, we are given a set of N users, and each user has some text data, which can be collection of emails, documents, or conversation history. An n-gram any sequence of n consecutive words that appears in the text associated with some user. For example, suppose there are two users and t22 and they have texts "Serena Williams is a great tennis player" and "Erwin Schrodinger wrote book called What is Life". Then, "great tennis player' is a 3-gram as it appears in the text of uj 'book called What is Life' a valid 5-gram as it appears Serena" is not a 3-gram as that sequence does not appear in the text of either of the users. Similarly 'wrote called What" not a 3-gram as it does not appear as a contiguous subsequence of either text. Our goal is to extract many nz-grams"] as possible, of all different lengths up to some maximum length T,, while guarantceing differential privacy.
text the u2. the other hand, 'tennis player
Our motivation to study this question comes from its applications to Natural Language Processing (NLP) problems. The applications such as suggested replies for e-mails and dialog systems rely on the discovery of n-grams, and then training a DNN model to rank them [HLLC14) KKR 16 CLB B 19 DBS19]. However, n- n-grams used for training come from individuals, and may contain sensitive information such as social security numbers, medical history, etc. Users may be left vulnerable if personal information is revealed (inadvertently) by an NLP model. For example, a model could complete sentence or predict the next word that can potentially reveal personal information of the
"Code available at at/ttps:: //g: thub com com/microooff//tiiii wttpft///fffffefaaaaaaaa allly private grivate--gram www.nngggtreeeeeeeeeee extraction In some papers, an rı-gram model specifically refers a probabilistic prediction model based on Markov chains. We do not make any probabilistic assumptions on how user data is generated.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

users in the training set 19]. Therefore, algorithms that allow the public release of the n-grams while preserving privacy are important for NLP models that are trained on the sensitive data of users.
In this paper we study private n-gram extraction problem using the rigorous notion of differential privacy (DP), introduced in the seminal work of Dwork et al. [DMNS06).
Definition 1.1 (Differential Privacy [RR44). A randomized algorithm A is (dff)-iiffeeettiaall private if for any two neighboring databases D and D', which differ in exactly the data pertaining to a single user, and for all sets S of possible outputs:
Pr(A(D) E S] S e Pr[A(D') E S]+ 5.
We consider the n-gram extraction problem guaranteeing user level differential privacy. We formalize the problem as follows. Let be some vocabulary set of words. Define Σ ExEx.. (k times) to be the set of length & sequences of words from Σ, elements of Σ are called k-grams. Let E" Uk20 * denote arbitrary length sequences of words from Σ, an element w E X. is called text. If w = 0102 ... a. where a, E Σ, any length & contiguous subsequence a,0;+1 ... 0i-k-1 of w is called a k-gram present in W. The set of all k-grams inside a text w are denoted by G& and we denote by G(w) (w)) the set of all n-grams of all lengths inside w.
Problem 1.1 (DP n-gram Extraction (DPNE)). Let E be some vocabulary set, possibly of unbounded size and let T be the maximum length of n-grams we want to extract. Suppose we are given a database D of users where each user i has some text w; E Σ* Two such databases are adjacent if they differ in exactly user. We want (effe-iiffrrentiially private algorithm A which outputs subsets St, Sp...., ST, where Sy C k such that the size of each Sy is as large as possible and Sy U,G& (w:) is as small as possible.
Note that in formulation, we assign the same weight n-grams irrespective of their length; that is. both a 8-gram and 2-gram carry equal weight of 1. While one can study weighted generalizations of the DPNE problems, both from an algorithm design perspective and the application of DPNE to NLP problems, our formulation captures the main technical hurdles in this space.
Many variants of n-gram discovery problems, closely related to DPNE, have been studied in the literature [CAC12 XSC 15 XCS 16 |XY 18). [CAC12] study this problem assuming certain probabilistic Markov chain model of generating n- -rgaamm. [XSC 15 XCS 16) study the problem of mining frequent sequences. Another of problems closely related to DPNE are mining or synthesizing trajectory data; see [HCM+15] CFDS12) and references there in. While we build upon some of the ideas in these works, to the best of our knowledge, the specific version of n-gram extraction problem formalized in DPNE has not been studied before.
A special case of DPNE problem, recently introduced by Gopi et al. |GGK is called Differen- tially Private Set Union (DPSU). In this problem, we are given a possibly unbounded universe of elements. and each user holds subset of these elements. The goal is to release the largest possible subset of the union of elements held by the users in a differentially private way. This problem can be considered simply extracting 1-grams. Another way to relate the problems is to assume that every possible n-gram as a separate item in the DPSU problem. While these interpretations do imply that can use the algorithms designed for DPSU to solve DPNE, the algorithms for DPSU fail to exploit the inherent structure of our new problem. In particular, note that if an algorithm for DPNE releases an n- n-gram of size 8, then one could extract all possible subgrams without any privacy cost by simply performing a post processing operation on the output of the algorithm. This structure is at the heart of the DPNE problem, and algorithms for DPSU do not take into account this, Not surprisingly, they do not give good utility as demonstrated in our experiments.
Our Contributions In this work we design new algorithms for the DPNE problem. The main contributions of the work are:
By combining ideas from the recent DPSU work with the tree based approach of (CAC12). we develop new differentially private algorithms to solve the DPNE problem. We also show an efficient implementation of our algorithm via an implicit histogram construction. Moreover, our algorithms can be easily implemented in the MAP-REDUCE framework. which is an important consideration in real-world systems.
Using a Reddit dataset, we show that our algorithms significantly improve the size of output n- g-gams compared to direct application of DPSU algorithms. Our experiments show

---

200000
DPNE
DPSU-all DPSU-even DPSU-single
175000
# of extracted n-grams
150000
125000
100000
75000
50000
25000
2
9
n-gram size
Figure 1: The figure illustrates the performance of DPNE algorithm compared to various ways one apply the DPSU algorithm for n-gram extraction. Here 'DPSU-all' refers running DPSU on all the different length n-grams together. 'DPSU-even' refers to splitting the privacy budget evenly and running DPSU to learn k-grams separately for each k. 'DPSU-single' refers spending all the privacy budget to learn k-grams for a single k. Note that for large k, DPNE learns many more k-grams than DPSU particular value of k. Here & = 4,6 10-7
when DPSU uses all its privacy budget to learn just k-grams for that
that DPNE algorithms extract more longer n-grams compared to DPSU even the DPSU algorithm spent all its privacy budget on extracting n-grams of particular size (see Figure M. Moreover, we recover most of the long n-grams which are used by at least 100 users in the database (see Figure
Our algorithms have been used in industry make basic subroutine in NLP application differentially private.
An Algorithm for DPNE
In this section we describe our algorithm for DPNE. The pseudocode is presented in Algorithm The algorithm iteratively extracts k-grams for k 1.2.... T, i.e., the algorithm uses the already extracted (k: 1)-grams to extract k-grams. Let Sş denote the extracted set of k-grams. The main features of the algorithm are explained below.
Build vocabulary set (1-grams) using DPSU: As the first step, use the DPSU algorithm from 22) to build a vocabulary set (1-grams), i.e., S₁. One can use any update policy from GGK + +2 in the DPSU algorithm. We the weighted gaussian policy because is simple and it scales well for large datasets. The DPSU algorithm with weighted gaussian update policy is presented in the Appendix B (Algorithm for reference.
DPSU-like update policy in each iteration: In each iteration, we build histogram H3 on k- grams using the weighted gaussian update policy from ( If we run DPSU as blackbox again learn k-grams (not making use of 5x-1), then algorithm will perform very poorly. This is because the number of unique k-grams grows exponentially with &. This causes the user budget to get spread too thin among the exponentially many k-grams. Therefore very few k-grams will get
'One can use update policy from GGK 20), we use weighted gaussian because of its simplicity and that it scales well to large datasets. The noise added will depend on the particular update policy chosen.

---

Algorithm 1: Algorithm for differentially private n-gram extraction
Input: A set of N users where each user has some text w,. T: maximum length of ngrams to be extracted
A1, A2, ................................ Ar: maximum contribution parameters
P1,
Threshold parameters
02,02: or: Noise parameters.
Output: S2...,,., Sr where Sj. is set of k-grams
// Run DPSU to learn 1-grams
S + Run DPSU with weighted gaussian update policy using A1, P1, to get set of
1-grams;
Vi < S1;
// Iteratively learn k-grams
for k = to 7 do
Vi f- (S1
(S Si):
culate valid k-grame
// Add all the valid k-grams with weight to histogram If for u in V2 do
L Hu [u] 0;
// Build a weighted histogram using weighted gaussian policy
for i 1-110 to N do
wht + Gu(w));
// Set of k-grams in text wy
U; <- G n
// Prune away invalid k-grama
// Limit user contributions
if [U > A. then
U, + Randomly choose AS items from U,;
for in U, do Ha[u] Ha[u] Viu.i
// Add noise to Hg and output k g-grams which cross the threshold Pk S = 0 (empty set); for и E Hy do
if H& [u] + o() > Pk then
S + SN {u}
Output S1, S2. . STi
enough weight to get output by the DPSU algorithm. To avoid this we will prune the search space for Sc.
Pruning using valid k-grams: Let us imagine that S is the set of "popular" k- k-grams, i.e., occurs in the text of many users. Then for k--ram to be popular, both the (k 1)-grams inside have popular. If we approximate the popular
1]-grams with Sk-1, the set of extracted (k - 11)-gramss, then can narrow down the search space to Vz (Sa-1 x Si) n (S) x Sa-1). This set Vi, called the set of valid k-grams. Therefore when we build the histogram Hş to extract k-grams, we will throw away any k-grams which do not belong to V2 (this is the pruming step). Pruning significantly improves the performance of the algorithm as shown the experiments (see Section 3. Pruning also results in the following nice property for the output of Algorithm []]
Proposition 2.1. The output of Algorithm I. S₁ U S2 U... Sr, is downward closed w.r.t taking subgrams. In particular, we cannot improve the output of the algorithm by adding subgrams of the output to itself.
Proof. We will prove that any collection of ngrams S S1 U S2 U ... U ST (where Sş are k- grams) is downward closed iff Ss C (S) x Sk-1) n (St-1 x Si) for all k. One direction obvious, if S is downward closed then S C (S) x u S, then d1 02 ... ag- 1, a2gg..........................3. ..... ... proved by induction T. Suppose S& C (S) x Sp-1) ) n (Sa1 x S1) for every k. By induction
S1) because if a102
S and 01 ..2....,0. 0g S.. The other direction can be

---

S1 UUSS S2 U is downward closed. If w = 0102.... E Sr, then any subgram of w is either subgram of a 022 ... .7-11 1 ST-1 1 or subgram of a2d3 ... ar ST By induction, that subgram has to lie in Si US2 U... US
IT
Controlling spurious n-grams using pi: In our privacy analysis (Section 2.1 we will show that the privacy of the DPNE algorithm depends only on f1 and 01, 22..0.,,0.................... or. In particular, P2..... Pr do not affect privacy. Instead, they are used to control the number of spurious ngrams that we extract, i.e., ngrams which are not actually used by any user but output by the algorithm.
Proposition 2.2. For k 2, the expected number of spurious k-grams output by Algorithm is at most [Va((1 (R)) where Φ is the Gaussian CDF. And the algorithm will not output any spurious I-grams.
Proof. A spurious k-gram will have zero weight in the histogram H. that the algorithm builds. So after adding N(0, of) noise, the probability that it will cross the threshold Pk is exactly 1 (px/Ox).
Larger we set Pks smaller the number of spurious k-grams. But setting large Pk will reduce the number of non-spurious k-grams extracted by the algorithm. So p2....;P7 Pr should be set delicately to balance this tension. One convenient choice Ps for h 2 is to set,
Pk 0z Φ- (1 (1- 7y min {,, |
1)
V&
for some 17 E (0. 1). This implies that the expected number of spurious k-grams output is at most " min S [V by Proposition 2.2 And the total number of spurious ngrams output is at most n[[1] + [Sa] + .... [Sr-1)). Therefore spurious ngrams output by the algorithm are at most an 7--fraction of all the ngrams output.
For extremely large datasets, Algorithm I can become impractical to run. The main difficulty is that the set of valid k-grams V22 = (S1 x Sx-1) n (Sk-1 X Si) is hard to compute explicitly if [Si] and [ are both extremely large. Luckily, we can easily modify the DPNE algorithm to make it scalable. The trick is to never actually compute the set of valid k-grams explicitly. Observe it is trivial to check if a given le-gram is valid or not (asumming we know S1 and Sk-1). Thus we implement the pruning step implicitly without computing Vz. The next problem is building the histogram HŞ on Vn, Note that any spurious k- k-gram will have weight in Hş after all the users update it. So instead of explicitly inserting the spurious k E-grams into Hę with weight 0, we implicitly assume that they are present. When we add noise to the histogram and output all the k-grams which cross the threshold Pk. the number of spurious k-grams that should have been output follow the binomial distribution B& ~ Binomial (lV& - [supp(HF H&)) ), (- px)/ So we can sample B& spurious k-grams from V& supp(())). then we can just add them the output Sk at the end. And generating a random sample from Ví supp HRx) is easy. Sample a random element from w Sk-1 S1 and output if w (Sa-1 Si) \ supp(([x) else repeat. Combining these ideas we can implement scalable version of DPNE which is included in Appendix (Algorith Our experiments use this faster and scalable version DPNE.
Scaling up DPNE:
2.1 Privacy Analysis
To analyse the privacy guarantees of the DPNE algorithm (Algorithm I.. we will need a few preliminaries.
Proposition 2.3 (DRS11)). The composition of Gaussian mechanisms with fz-sensitivity and noise parameters 1 02 .2. or has the same privacy as Gaussian mechanism with Ez-sensitivity I and noise parameter a where:
T
0²
Proposition 2.4 (BWI8) For any > O, the Gaussian mechanism with ég-sensitivity and noise parameter a satisfies (e, DDP where
8
-E0 +
20 - c. Φ
-E0
20
5

---

We are now ready to prove the privacy of our DPNE algorithm.
Theorem 2.1. Let and
Let o² be obtained by solving the equation
8
1 +
+
-0
2a e 1 -E0- 20
(1)
2
where + is the CDF of a standard Gaussian. Then Algorithm as follows:
is (c, 6)-DP if we set 11.... or
0
02
of
+ o Φ-1 ((1-2)))
PI
max I8KS
Proof. The privacy of DPSU algorithm (Algorithm 5) is given by the composition of Gaussian mech- anism with fz-sensitivity and noise σi composed with (0, 8/2)-algoriihh as shown in [GGK+20) if we set P1 shown. The construction of k--gams is a Gaussian mechanism with fz-sensitivity and noise σg. By Proposition 2.3 the composition of all these mechanisms is the composition of Gaussian mechanism with noise o* and (0, 8/2) mechaniss. Now applying Proposition 2.4 and using the simple composition theorem for DP and completes the proof
Experiments
In this section, we empirically evaluate the performance of our algorithms on two datasets: Reddit and MSNBC. The Reddit data is natural language dataset used extensively NLP applications. and is taken from TensorFlow repository [ The MSNBC dataset consists page visits of users who browsed msnbc.com on September 28, 1999, and recorded at the level of URL and ordered by time Ø This dataset has been used in the literature in frequent sequence mining problems, which is summarize the salient properties of these datasets. As primary focus of our paper is on NLP applications, we perform more extensive experiments Reddit dataset, which also happens to be a significantly larger dataset compared to the MSNBC dataset.
closely related problem ours. Tables] [ 2
Table I: Dataset Statistics
Users
Posts
# Sequences/Users
Sequences
# Unique Sequences
Reddit
1,217,516 989,818
3,843,330 989,818
3653.81
43.39B
23.24B 357.84K
MSNBC
18.02
17.84M
Table 2: Average number of sequences per user calculated for each sequence length
2
4
6
8
Total
Reddit
497.60
470.76
444.37
418.77
393.72
369.32
345.65
322.80
300.82
3563.81
MSNBC
4.67
3.67
3.04
2.57
2.19
1.88
18.02
3.1 Experiments on Reddit Dataset
Throughout this section we fix T' unless otherwise specified.
10-7,4. = ... Ag = Ao = 300, = 0.01
3.1.1
Hyperparameter tuning
There are several parameters in Algorithm D such as dk; Ak. Pk. We study the effect important hyperparameters the number of n-grams extracted by our algorithm.
'The simple composition theorem states that if M, satisfies (e,, 6, -D for = 2, then the composition of M, M2 satisfies (&, E2, 61 + DDP
htttpe://mw tensorflow... hataaa/rrrroo...aaaaeettttttttte
battps//arrciveee ics wtt.://wwww.eaaaateeeaaccaa..oaa

---

140000
140000
122000
120000
100
1,00000-
- 200
300
100000
50000
80000
60000
pigram 522e
n-gram 5:de
Figure 2: The figures illustrate the effect of hyperparameters on DPNE algorithm: User contribution
Ao (left), privacy parameter (right).
Setting DS and st This is quite similar to setting Ao parameter in the DPSU algorithm from |GGK A good starting point is to set A₂ around the median number of valid k-grams that users have in their text. In our experiments we set A A2 _... A Ao. The effect of Au the performance of the algorithm is shown in Figure 2 As predicted the performance of the algorithm improves with increasing Åg until Ag ze 300 which is approximately the average number of k-grams per in the Reddit dataset (see Table 3 Also the right side of Figure shows the effect of varying e. As expected, we can extract more n-grams for all lengths by increasing &, which leads weaker differential privacy guarantee.
250000
4 2.00
0.01
5.02
0.05
450000
100000
50000
am 5ize
size
Figure 3: The figures illustrate the effect of hyperparameters on DPNE algorithm: Fraction of spurious n-grams 1) (left), and privacy budgeting parameter e (we set σ c0k (right).
Setting Pk and yp We have already discussed how to set Pk- These should be set based on the fraction the spurious k-grams we are willing to tolerate in the output. The effect of 1 on the performance of the algorithm is shown in Figure As expected, increasing increases the number of extracted n-grams for all lengths. Table 3 shows the actual ratio of spurious n-grams extracted by varying 7) value, which experimentally confirms that the algorithm extracts at most fy-fraction of the output.
Table 3: Actual ratio of spurious n- n-grams extracted by varying 7
0.005
0.01
0.02
0.05
0.1
0.2
Actual Ratio 0.004
0.088
0.017
0.419
0.086
0.168
Setting og: As can be observed, each iteration of k-gram extraction for A 1, 1, .., consumes
some privacy budget. If we set a small value of aı, we will consume more privacy budget constructing fixed based the final s, we want achieve (see
k-grams. Since
o,
7

---

Equation T). we need to balance various T. accordingly. Given these observations, how much privacy budget we should spend for each iteration of our algorithm? A simple strategy is same value of or for all k; this corresponds to spending the same privacy budget for extracting k-grams for all values of k.
One other heuristic is the following. In any data, we expect that 1-grams are more frequent than 2-grams, which should be more frequent than 3-grams and so on. We can afford add larger noise in the beginning and add less noise in later stages. Thus one could set σß = C0 for some geometric rate. And thus we consume more privacy
<<< 1; that is, we decay the noise budget in extracting k-grams than k - 1 --gams. The effect of c is shown in Figure 3 As expected, spending more privacy budget to extract longer n-grams produces more longer n-grams the cost of smaller number of shorter n-grams. On the other hand, one can make a strategy to extract more shorter n-grams by setting c 1.
Figure 4 shows effect of using different pruning rules, V/2 = Sk x Sj (single-side) or V22 -S S (S, x Sk-1) (both-side). While both-side pruning is stricter rule compared to the single-side pruning and we expect to perform better overall, our experiments suggest that the situation is more intricate than our intuition. In particular, both rules to lead similar number of discovered n-grams; However, it is interesting to see the distribution on the length of the output n- grams. The both-side pruning rule favors shorter length n-grams where as single-side side pruning favors the longer length n- n-grams, We believe that understanding how pruning rules affect the performance of DPNE algorithms is an interesting research direction.
Pruning rule:
3.1.2 Comparison to K-anonymity and DPSU
K K-anonymity: Figure shows what fraction of n-grams whose count is at least K is extracted by our algorithm, which similar comparing against K-anonymity based benchmarks. Figure 4 shows that DPNE algorithms can extract most of the n-grams which have frequency at least 100 and have length least In particular, our new algorithm could output 90% of the n-grams of length 6,7,8 that appear in the dataset at least 100 times.
Single
1.0
Bath
3.8
K=100
02
Figure 4: The left figure illustrates the effect of different pruning rules Vn = = x S₁ (single-side) or Vi2 (Sa-1 x (S) Sk-1) (both-side). The right figure compares DPNE with K -anonnymiyy, it shows how much fraction of n-grams with frequency K are covered by the DPNE algorithm.
DPSU: In Table and Figure we compare our DPNE algorithm with the DPSU algorithm of GGK-20) We implement DPSU algorithms to solve DPNE in three different ways:
In DPSU-all, we run DPSU algorithm with the maximum user contribution TA and treat all n-grams similarly irrespective of their length.
In DPSU-even, we allocate the privacy budget of =2 E/VT (using advanced composition) to extract the n-grams of each particular length & separately, for each k E [I,2,..., 9). Maximum user contribution for each & is set Ag.
Finally, in DPSU-single, we allocate all the privacy budget of & towards extracting 7--grmm of a fixed length k;, for each k [1, 2....999 9). Maximum user contribution for each l is set to Ao.
8

---

Table 4: Comparison of DPNE and DPSU methods using parameters Ao
100,
4,8 =
10 .7 0.01. See Figure for explanation of the different versions of DPSU.
1
2
3
4
5
7
Total
DPNE
16,173
59,918
110,160
119.039
88,174
51,816
23,144
9,019
2,748
480,191
DPSU-all
18,010
54,937
38,283
10,990
1,978
352
71
16
124,637
DPSU-even 16,164
44,871
35,032
11,093
2,210
440
113
28
109,958
DPSU-single 44,635
194,131
201,901
92,486
25,451
5,906
1,385
329
92
As we can see, except for smaller length n-grams, DPNE completely outperforms the DPSU algorithm. This is not surprising DPSU algorithms do not exploit the rich structure inherent in n-grams. The most interesting statistic to note is the last row of : Here we see that our new algorithm beats the DPSU algorithm even when all the privacy budget allocated to extracting certain fixed sized n-grams. For example, the DPSU algorithm with privacy budget of (s = 4, 6 10-?) allocated to extracting only 8-grams managed to output only 329 8-grams, where as the DPNE algorithm with same privacy budget spread across all the n-grams still could extract 9,019 8-grams. We also observe that the number of spurious n R-grams output by our algorithm is always at most 17-faccion of output designed, omit the number of spurious n-grams from Table 4 for clarity.
3.2 Experiments on MSNBC Dataset
Table S reports comparison DPSU and DPNE algorithms on the MSNBC datasets. Although MSNBC dataset is significantly smaller than the Reddit dataset, behavior of the algorithms remain roughly the same.
Table 5: Comparison of DPSE and DPSU methods on MSNBC data (Ap = 10, = 1, 10-7, 0.01)
4
5
6
Total
DPNE
17
254
1,273
1,954
2,221
2,020
7,739
DPSU-all
17
249
930
1,145
1,007
768
4,116
DPSU-even
17
246
899
1,107
996
766
4,031
DPSU-single
17
260
1,483
2,180
2,210
1,819
4 Conclusion
In this paper, motivated by its applications NL.P problems, we initiated the study DPNE problem, and proposed new algorithms for the problem. We believe that our algorithmic framework can be extended or improved on multiple fronts: a more careful scheduling of privacy budget across different length n-grams, understanding the pruning strategies, etc. Given the ubiquitous nature of this problem NLP, we hope that our work brings more attention to this problem.
Acknowledgement
We would like to thank Robert Sim, Chris Quirk and Pankaj Gulhane for helpful discussions and encouraging us to work on this problem.
References
[BW18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. International Conference on Machine Learning, pages 403 412, 2018.
[CAC12] Rui Chen, Gergely Acs, and Claude Castelluccia. Differentially private sequential data publication via variable-length n-grams. In Proceedings of the 2012 ACM conference Computer and communications security, pages 638-649, 2012.

---

[CFDS12]
Rui Chen, Benjamin CM Fung, Bipin C Desai, and Nériah M Sossou. Differentially private transit data publication: a case study on the montreal transportation system. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 213-221, 2012.
[CLB+19] Mia Xu Chen, Benjamin N. Lee, Gagan Bansal, Yuan Cao. Shuyuan Zhang, Justin Lu, Jackie Tsay, Yinan Wang. Andrew M. Dai, Zhifeng Chen, and et al. Gmail smart compose: Real-time assisted writing. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 2287-2295. 2019.
[CLE+19) 19] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th {USENIX} Security Symposium (1 (!USENIX) Security 19), pages 267-284, 2019.
[DBS19] Budhaditya Deb, Peter Bailey, and Milad Shokouhi. Diversifying reply suggestions using a matching-conditiona variational autoencoder. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Industry Papers), Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(344)211-4077 2014.
[RRS19] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXiv: 023833. 2019.
[G)K+200 Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhi, and Sergey Yekhanin. Differentially private set union. In International Conference on Machine Learning, pages 3627-3636. PMLR, 2020.
[HCM+15] 15] Xi He, Graham Cormode, Ashwin Machanavaijhala, Cecilia M Procopiuc, and Divesh Srivastava. Dpt: differentially private trajectory synthesis using hierarchical reference systems. Proceedings of the VLDB Endowment, 8(1 ((11):1554111 2015.
[HLLC14] Baotian Hu, Zhengdong Lu, Hang Li, and Qingcai Chen. Convolutional neural network architectures for matching natural language sentences. In Advances in neural information processing systems, pages 2042-2050, 2014.
[KKR+16] 16) Anjuli Kannan, Karol Kurach, Sujith Ravi, Tobias Kaufmann, Andrew Tomkins, Balint Miklos, Greg Corrado, Laszlo Lukacs, Marina Ganea, Peter Young, et al. Smart reply: Automated response suggestion for email. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 955-964, 2016.
[WXY+18] Ning Wang, Xiaokui Xiao, Yin Yang, Ta Duy Hoang, Hyejin Shin, Junbum Shin, and Ge Yu. Privtrie: Effective frequent term discovery under local differential privacy. In 2018 IEEF 34th International Conference on Data Engineering (ICDE), pages 821-832. IEEE, 2018
IXCS 16] Shengzhi Xu, Xiang Cheng. Sen Su. Ke Xiao, and Li Xiong. Differentially private frequent sequence mining. IEEE Transactions on Knowledge and Data Engineering. 28(11):910-2926, 2016.
[5SC+15] Shengzhi Xu, Sen Su, Xiang Cheng, Zhengyi Li, and Li Xiong. Differentially private frequent sequence mining via sampling- candidate pruning. In 2015 IEEE 31st International Conference on Data Engineering, pages 1035-1046. IEEF, 2015.
10


Reviews:
[{"review_id": "qDvZeDG_ukh", "reviewer": "Reviewer_GGc1", "summary": "The paper provides an algorithm for n-gram extraction that is Differentially Private. They also provide a scalable version of the DP algorithm and provide experimental results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and easy to follow. I also think the relevant literature is discussed properly. The main strength of this paper is the impact it can have on products as it tackles a real world problem where privacy is a concern. It is even discussed in the paper that the algorithm has been implemented in industry which I think is great. It could be argued that a weakness of this work is that the algorithm and its analysis follow very easily from previous work (in particular [GGK+20]). I personally do not consider the previous a weakness since I don’t think that important problems need complicated solutions. All the theoretical claims seem to be correct.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "lNbIdpdDyXU", "reviewer": "Reviewer_S4Sy", "summary": "Paper studies the problem of n-gram extraction with differential privacy as a generalization of differentially private set union.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "paper proposes to deal with the problem of extracting n-grams with differential privacy posed as a generalization of DPSU. Paper is clearly written and deals with an important issue as n-gram extraction with privacy has multitude of potential applications as suggested by the authors. That being said, in some places (such as Section 2.1), it seems like some material is missing or has been left out, which is understandable due to page limits but can occasions make the reading a bit harder. My comments are provided below in detail:\n\n1. Figure 1 shows the comparison for a fixed privacy budget, it will be nice to have similar comparisons with varying epsilon, even if they can go in supplementary material.\n2. In contributions, last line stating that the proposed algorithms have been used in industry serve no purpose in my opinion.\n3.  it will be helpful to add a line to state why is the construction of k-grams is a Gaussian mechanism with l_2 sensitivity=1\n4. It will also help in the introduction, where authors state the dangers of leaking something like a SSN, to state how will a DP model solve the problem.\n5. Minor: in the checklist, authors have answered \"yes\" to many questions that I cant seem to correlate with the paper, such as limitations, code, error bars, compute used, etc.\n\n----------------------------------------------------------------------------------------------\npost-rebuttal\nI have read authors' response.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "hLxz5LpaWve", "reviewer": "Reviewer_Qhy6", "summary": "This paper proposes a differentially private algorithm to extract all n-grams of length 1 up to some maximum length T from a texture data corpus where each user’s data is represented by a single string. It uses an earlier algorithm called Differentially Private Set Union (DPSU) to find all 1-grams (the alphabet), then iteratively builds the set of n-grams of length from 2 to T by effectively pruning the search space, building a noisy weighted histogram on the pruned candidate set and taking the n-grams whose counts are above predetermined thresholds.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of n-gram extraction is an important task in many NLP applications. In this paper, the authors propose a differentially private algorithm to extract all n-grams of length 1 up to some maximum length T from a texture data corpus where each user’s data is represented by a single string. Their algorithm is a simple extension of a previous algorithm called Differentially Private Set Union (DPSU), which aims to find all items owned by users where each user owns a set of items from some universe. The algorithm works as follows:\n1.  Find S(1), the set of all 1-grams (the alphabet) using DPSU\n2.  Iteratively build S(k), the set of k-grams for k from 2 to T. To build S(k) from S(k-1), it first prunes the search space for S(k) by restricting it to the intersection of S(1) \\times S(k-1) and S(k-1) \\times S(1). The rationale is that the two substrings of length (k-1) of a k-gram in S(k) should already be in S(k-1). Then it computes a noisy weighted histogram on the pruned search space and extracts k-grams whose counts are above predefined thresholds, which are considered hyperparameters.\n\nThe novel part is the combination of DPSU with effective pruning. DPSU does not consider the structures of items and will regard all n-grams as unrelated entities. When combined with tree-based pruning approach, it will produce improved results on extraction of n-grams, as is verified by the experiment.\n\n\nStrength: \n+ The problem formation is clear. The authors clearly state what problem they are trying to address.\n\n+ The algorithm is simple and intuitive, and it works! The improved performance is demonstrated by experiments.\n\n+ The paper is well-written. The presentation is clear.\n\nWeakness:\n- In all experiments the authors report the number of n-grams extracted or the coverage ratio. However, it is also important to know the number of false positives, or the so-called spurious n-grams in the paper. Thus, it would be more desirable for the experiments to also report other metrics such as the F-scores.\n\n- Limitations of the algorithm are not adequately discussed. The algorithm relies on the set of shorter n-grams to build the set of longer n-grams. Any error that happens in the early stage will propagate to subsequent computations. The paper argues that for privacy budget allocation, one could use smaller budgets and thus larger noises for shorter n-grams because shorter n-grams are more frequent than longer ones and have larger counts. However, there is no analysis or experiment to back up this claim and I am not convinced this is true. After all, the algorithm is to identify as many n-grams that appear in the corpus, not just the frequent ones.\n\n- The part on related work could be expanded. There are many related algorithms that aim to identify existing n-grams, both in the central DP setting and the local DP setting. Those works should be mentioned to provide a more thorough review of the literature in this area.\n\nTypos: \nline 138, bother -> both\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned in the main review, the authors could expand their discussion on the limitations of their work. For example, how does the algorithm perform on dataset where the distribution of n-grams is highly concentrated? Can the algorithm be improved to use privacy budget more efficiently for those n-grams whose counts are very high and way above the threshold, as pointed out in the DPSU paper? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "0UvJx6TXUub", "reviewer": "Reviewer_mTUU", "summary": "This paper studies the problem of differentially private n-gram extraction (DPNE). The authors combines the idea of DPSU and a tree based approach to solve the DPNE problem, where the basic building blocks are histogram construction and the Gaussian mechanism.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- DPNE has wide applications, but there has not been much research on this problem in the setting of differential privacy.\n- The experiments show that the proposed method practically outperforms the DPSU on DPNE problem.\n- The theoretical depth is weak: there is no clear accuracy guarantee and the privacy analysis is straightforward.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a DP algorithm to extract all n-grams (sequence of n consecutive words appearing in the data) of length 1 up to some maximum length T, where each user’s data is represented by a single string. It uses an earlier algorithm to find all 1-grams, then iteratively builds the set of n-grams of length from 2 to T by effectively pruning the search space. The reviewers agree that this is an interesting paper, and all of them support acceptance.
Decision: Accept (Poster)