Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new algorithm designed to privately and efficiently answer complex sets of counting queries from a database.
The proposed algorithm builds on top of Private-PGM and provides a more scalable way of reconstructing the noisy measurements by relaxing consistency constraints of queries.
main_review: - Paper is well written and easy to read
- The experimental results show how the proposed algorithm can improve existing techniques to answer counting queries.
- The authors might consider the local least square approximation inference step in [0] and show how it compares with the proposed algorithm for large number of queries.
- How does the proposed algorithm compares against FEM? In the current paper, the authors add the inference step to FEM, but they do not show a straightforward comparison between FEM and APPGM.


[0] Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphical-model based estimation and404
inference for differential privacy. In International Conference on Machine Learning


limitations_and_societal_impact: The limitations of the proposed algorithm are clearly discussed in the paper
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: For the problem of differentially privacy query answering, a standard paradigm is select-measure-reconstruct. In most methods, the reconstruction step needs to represent the data in vector form, which is impossible when the data is high dimensional. Private-PGM is an approach that uses a graphical model to represent the data more compactly, and it has been shown to improve the scalability of many popular algorithms while decreasing error. However, Private-PGM works best when the graphical model is sparse, and it becomes very inefficient when the graph is dense, which is due to the hardness of exact marginal inference. Therefore, Private-PGM has limited applications for real-world settings. The authors propose a new algorithm that relaxed the marginal inference step to allow Private-PGM to be adapted to more settings. To prove that their method is more scalable, they used the FIRE dataset, which has 15 attributes and 300K rows. 

main_review: 
This paper provides a technique to make private-pgm more scalable which I believe is a valuable contribution. In particular, they are able to run HDMM with much larger clique feature set without losing much accuracy.  They also show that the their technique can improve scalability of MWEM. However feel that the paper would be stronger if the authors included more comprehensive experiments. Right now the experiments include only one dataset with 15 features.

Minor comments/questions:

Can you obtain better accuracy by running the gradient descent longer or what is the optimization /accuracy trade-off?
limitations_and_societal_impact: no.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper address the problem of answering a complex set of counting queries subject to DP.  They present a basic paradigm that is shared across typical DP approaches: select a set of queries, measure those queries, and reconstruct a dataset from the noisy measurements.  This paper addresses the last phase, where traditional approaches do not scale to large dimensional datasets.  The 2nd phase can easily be done with noise addition mechanisms, e.g. Laplace or Gaussian mechanisms, while the 1st phase is a much more challenging problem that is left open.  The main technical contribution is generalizing Private-PGM (the winning entry in the 2018 NIST DP contest).  Private-PGM suffers from not being scalable in many settings. The new APPGM enjoys many of the benefits of Private-PGM, while also being able to be deployed in more settings.  

main_review: The presentation of Private-PGM could be improved.  It is difficult to see the main challenge with Private-PGM, which is the motivation for this work.  The paper presents the optimization problem and the algorithms very succinctly, but this is done with heavy notation.  In the introduction, the reason for Private-PGM not scaling is due to “the graphical model typically becomes dense”, which is impossible to understand without getting into the details.  

The technical contributions in this work seem very broad and not just specific to DP.  Relaxing the consistency constraints from global to local seems natural and might find other applications.  The experiments are also quite interesting.  Although the results show that using Private-PGM can get much better results than the approximate version (with the Region Graph), there gets to be a point where computational resources will not allow for it to get better.  This is where the power of the approach presented in this work comes through because things like MWEM can run much more rounds and get better accuracy given the same computational resources.  

Minor Comments: 
- What is $s$ and what is P_{s \to r} in line 74? 


#### 
Update: I have reviewed the author responses and other reviewers comments and will keep my score unchanged.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper the authors propose an algorithm for reconstructing data representations from noisy measurements and answering new queries using reconstructed data. Their algorithm, APPGM, builds on a recent method called Private-PGM, a reconstruction method that obtains data representations by solving an optimization problem using graphical models. By relaxing the consistency constraints on overlapping marginals, their algorithm achieves better scalability at the cost of some loss in accuracy.
main_review: This paper proposes an algorithm for reconstructing data representations from noisy measurements and answering new queries using reconstructed data. Such algorithm is part of the popular select-measure-reconstruct paradigm for answering linear queries on private datasets. In such a framework, data analysts carefully choose a set of queries to send to the data owner. The data owner executes those queries on the private dataset and returns the answers with noise instrumented using standard differential privacy mechanisms to protect the privacy of individuals in the dataset. The data analyst then reconstructs (a representation of) the data and resolves any inconsistencies in the noisy measurements. The reconstructed data can be used to obtain more accurate answers to the original queries or answer new queries with no additional privacy cost. 

The proposed APPGM algorithm builds on a recent method called Private-PGM. It has two components, one for reconstructing data and one for answering new queries using reconstructed data. For reconstruction, the authors propose the concept of Region Graph, which leads to pseudo marginals that enforces some but not all internal consistency constraints. The resulting optimization problem can be solved by using existing methods, for example, Prox-PGM with Convex-GBP. For answering new queries, instead of enforcing that the new marginals agree with reconstructed pseudo marginals on overlapping attributes, the authors minimize the L2 norm of constraint violation. By relaxing the consistency constraints, their algorithm achieves better scalability at the cost of some loss in accuracy. 


Strength: 
+ The concept of Region Graph is novel. It allows various partial consistency constraints to be expressed in a uniform framework. 

+ The presentation is clear. The paper did a good job in explaining complex concepts using consistent and sensible mathematical notations. 

+ The related work section is comprehensive and includes comparisons to many existing methods in the literature. 

Weakness:

- The paper does not contain formal analysis on the loss of accuracy due to relaxation of consistency constraints. As mentioned by the authors, the estimates of out-of-model marginals can be poor in the MWEM experiment. From the graphs, it seems that Private-PGM always outperform APPGM in terms of accuracy when it works. Should one only use APPGM when PPGM fails to run? How large can the drop in accuracy be when both can be applied? 

- The paper is not sufficiently self-contained as several important technical details and algorithms are in the supplementary material. As such, it is difficult for reviewers to verify some of the claims in the paper.



Other Comments:
In the experiment (Fig. 2) Private-PGM demonstrates quite different behavior under two clique selection schemes: it can handle many more cliques when they are selected greedily to minimize the junction tree size, compared to when they are selected randomly. Such difference is not present in APPGM. Why is this the case?

Typos:
Line 14: in the design -> in the design of

limitations_and_societal_impact: The authors discussed several limitations when using their method in practice. More discussion on theoretical limitations could be beneficial to potential users of the algorithm.
review_title: null

Meta-review: The reviewers unanimously enjoyed this paper. Thanks for the strong submission. 
Decision: Accept (Poster)