Overall: I like the paper -- node differential privacy has been shown to be extremely challenging to achieve -- and consequently, this work is a solid algorithmic advance. I think it deserves publication at neurips. That being said, there are two aspects of the paper that render it less useful than I would have liked it to be. The first is that almost no intuition is provided, which makes the algorithm rather opaque. Why is the "concentrated degrees" property needed? Where does the analysis break when this property is not there? A detailed discussion of this in my opinion is necessary. The second is that no constants are provided and all smoothed sensitivity calculations are carried out with a O notation. For example in Lemma 3.1 the local sensitivity calculation is done with a O. While this is fine for a theoretical paper, in my opinion this considerably lowers the value of this work. Any practitioner who would like to implement the algorithm would have to work out all the hairy details from scratch; this is exacerbated by the fact that these exact numbers are indeed needed to implement the algorithm correctly. In my view, addressing these two aspects would make the paper considerably stronger.

Positives about the paper: it states a clear, concrete problem, and provides a clear solution. It is (from a mathematical standpoint) nicely written. It is particularly nice that lower bounds are given as well as upper bounds. I enjoyed reading the paper. Negatives about the paper: it is not at all clear to me what the motivation for the paper is, other than people have looked at variations of the problem in the past, and differential privacy for random graphs is intrinsically interesting to a (small) set of mathematically inclined people. That is, it's not clear why anyone needs node differential privacy for Erdos-Renyi graphs -- either for an application, or even for other possbily related mathematical problems. In particular, while the paper clearly demonstrates the proposed algorithm achieves the formal definition of differential privacy, it's not clear how, for example, simply revealing the true parameter p affects the privacy of any individual node, particularly in a random graph. While the paper is working within a well-established framework, at least for this reader, a lack of explanation of this point (why one wouldn't just return p if known or the actual edge density) made it more difficult to understand the motivation for this type of result. The lower bound only holds for constrained graphs, not specifically for random graphs. I would not mind seeing the paper accepted; in general, I support mathematically interesting papers. However, it's hard to make a strongly compelling based on probable limited interest to a NIPS audience. But it should certainly be published somewhere, and NIPS is perhaps as reasonable a home as any. Detailed points: Any insight/thoughts on beta at line 140 would be welcome. The statement that it's a parameter to be determined later is a rather oblique. I personally would have like more clarity at lines 227-228; it's written rather vaguely. (I'm not sure what "suitably small" is, or what ie means to not affect the error in a "significant way".) I assume it is a space issue, as the rest of the writing is much more formal; these lines left me worried. ------- The reviewer thanks the author(s) for the detailed response and feedback. It may be useful to make clear some of this motivation in the revised version of the paper, e.g, this may serve as a building block in other protocols, and the connections to Lipschitz extensions. This reviewer found it helpful. Based on the detailed response clarifying issues raised by this reviewer as well as the other reviewers, this reviewer is raising the prior review score from a 5 to a 6. The reviewer also agrees with other reviewers to recommend acceptance.

The fact that a node-DP polynomial time algorithm is available and with almost the same error guarantees as the non-DP algorithm is quite an achievement. I haven't checked all the details of the proofs, but the reasoning seems to flow. The lower bound is also interesting, mostly because it shows that novel techniques are needed to get improvements for G(n,p). One doubt that I have is how the value of s (2nd to last line of Alg 1) can be computed efficiently. The paper feels a bit unpolished in the presentation, especially in terms of conveying intuition and explaining what is going to happen next. The pseudocode in particular feels unnecessary and can easily be replaced with a more thorough description in the text. Please use the correct accents above the 'o' of Erd\H{o}s: in LaTeX, use \H{o}, not \"{o}. Please do not italicize "et al.", as per most manuals of style.