Summary
This paper presents a sum-of-squares-based polynomial-time differentially node-private algorithm for estimating the edge density of Erdos-Renyi random graphs that achieves optimal accuracy; the algorithm is simultaneously robust to corruptions. Specifically, if p is the true Erdos-Renyi parameter, then the estimate q released by the algorithm has error |q/p - 1| bounded by 1/(n sqrt{p}) + 1/(eps n \sqrt{np}) + eta / sqrt{np} (up to factors of log n), where eta is the corruption rate for robustness. Up to log n factors, the first term is the information-theoretically optimal error rate with neither privacy or robustness (which is also the error of the empirical edge density), and the third term is known to be required for robustness ([AJK+22]). The paper further shows a lower bound demonstrating that the remaining error term is necessary for privacy (a lower bound had been shown by BCSZ18 for a closely related family of random graphs but not for standard Erdos-Renyi graphs, so the new lower bound closes this gap). Moreover, the paper extend this result to present an algorithm for the much more general problem of edge density estimation in inhomogeneous random graphs (e.g. SBMs or graphons) and proves lower bounds in this setting as well showing that this algorithm also achieves optimal error rate up to logarithmic factors.
Strengths
This paper achieves optimal accuracy in polynomial time for both private and robust edge density estimation of Erdos-Renyi graphs and for the more general setting of inhomogeneous random graphs, nicely closing the gaps from prior work. It achieves this by bringing a new approach to the problem: the sum-of-squares framework, along with leveraging a reduction from privacy to robustness. The paper is generally well-written.
For DP edge density estimation of Erdos-Renyi graphs (even without requiring robustness), the new algorithm matches the (already optimal) accuracy achieved by [BCSZ18] while running in polynomial time instead of exponential time; it also improves over the rate of the polynomial-time algorithm of [SU19], which was suboptimal in the sparse or very-high-privacy regimes (that is, when epsilon * sqrt{pn} << 1). For robust edge density estimation of Erdos-Renyi graphs (even without requiring privacy), the new algorithm also improves of the accuracy of prior work ([AJK+22]) in the sparse regime. Thus, the Erdos-Renyi result improves on SOTA for both privacy and robustness, achieving the optimal bound (up to log n factors). Moreover, the results are extended to the more challenging inhomogenous random graph setting, achieving optimal rate in polynomial time here as well, and novel, tight lower bounds are shown for both settings as well.
Weaknesses
The discussion of prior work is clear for the Erdos-Renyi setting, but it would be useful to have a clearer discussion of what was previously known for the more general inhomogeneous random graph setting under DP and under robustness; see the specific questions 1--2 below.
Questions
1) How does the rate achieved for inhomogeneous random graphs compare to the rate achieved by the exponential-time algorithm of [BCSZ18] for graphons?
2) Is there prior work on robust estimation of general inhomogeneous random graphs, and if so, what rate was achieved?
3) Can we hope to extend the privacy lower bounds (Theorem 1.5 and 1.8) to (epsilon, delta)-DP and not just epsilon-DP?
Minor comment:
line 188: should d^\circ be defined as (n-1) p^\circ instead of n p^\circ?
Limitations
Yes, adequately addressed.