Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: - DPNE has wide applications, but there has not been much research on this problem in the setting of differential privacy.
- The experiments show that the proposed method practically outperforms the DPSU on DPNE problem.
- The theoretical depth is weak: there is no clear accuracy guarantee and the privacy analysis is straightforward.
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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:
1.  Find S(1), the set of all 1-grams (the alphabet) using DPSU
2.  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.

The 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.


Strength: 
+ The problem formation is clear. The authors clearly state what problem they are trying to address.

+ The algorithm is simple and intuitive, and it works! The improved performance is demonstrated by experiments.

+ The paper is well-written. The presentation is clear.

Weakness:
- 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.

- 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.

- 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.

Typos: 
line 138, bother -> both

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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Paper studies the problem of n-gram extraction with differential privacy as a generalization of differentially private set union.
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:

1. 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.
2. In contributions, last line stating that the proposed algorithms have been used in industry serve no purpose in my opinion.
3.  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
4. 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.
5. 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.

----------------------------------------------------------------------------------------------
post-rebuttal
I have read authors' response.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.
limitations_and_societal_impact: NA
review_title: null

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)