Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust

Authors: hongjie  chen
david  steurer
eth  zürich
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:53:31

Abstract: We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of Erdős-Rényi random graphs and their generalization, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates.

Two key ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy to robustness based on sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).

Main paper: 
 introduction: 
 Privacy has nowadays become a major concern in large-scale data processing. Releasing seemingly harmless statistics of a dataset could unexpectedly leak sensitive information of individuals (see e.g. [NS09, DSSU17] for privacy attacks). Differential privacy (DP) [DMNS06] has emerged as a by-now standard technique for protecting the privacy of individuals with rigorous guarantees. An algorithm is said to be differentially private if the distribution of its output remains largely unchanged under the change of a single data point in the dataset.For datasets represented by graphs (e.g. social networks), two notions of differential privacy have been investigated in the literature: edge differential privacy [NRS07, KRSY11] , where each edge is regarded as a data point; and node differential privacy [BBDS13, KNRS13] , where each node along with its incident edges is regarded as a data point. Node differential privacy is an arguably more desirable notion than edge differential privacy. On the other hand, node differential privacy is also in general more difficult to achieve without compromising on utility, as many graph statistics usually have high sensitivity in the worst case. It turns out that many graph statistics can have significantly smaller sensitivity on typical graphs under natural distributional assumptions. Several recent works could thus manage to achieve optimal or nearly-optimal utility guarantees in a number of random graph parameter estimation problems [BCS15, BCSZ18, SU19, CDd + 24].In this paper, we continue this line of work and study perhaps the most elementary statistical task in graph data analysis: Given an 𝑛-node Erdős-Rényi random graph of which each edge is present with probability 𝑝 • independently, output an estimate p of the edge density parameter 𝑝 • , subject to node differential privacy. We consider the error metric | p/𝑝 • -1| which can reflect the fact that, the task is more difficult for smaller 𝑝 • . Without privacy requirement, the empirical edge density1 p achieves the information theoretically optimal error rate | p/𝑝 • -1| ⩽ Õ(1/(𝑛 √ 𝑝 • )). The standard way to achieve 𝜀-differential node privacy is to add Laplace noise with standard deviation Θ(1/(𝜀𝑛)) to the empirical edge density p. This will incur an additional privacy cost of Θ(1/(𝜀𝑛𝑝 • )) which dominates the non-private error Õ(1/(𝑛 √ 𝑝 • )). Surprisingly, Borgs et al. [BCSZ18] gave an algorithm with privacy cost only Õ(1/(𝜀𝑛 √ 𝑛𝑝 • )) which is negligible to the nonprivate error for any 𝜀 ≫ 1/ √ 𝑛. However, their algorithm is based on a general Lipschitz extension technique that has exponential running time. Later, Sealfon and Ullman [SU19] provided a polynomial-time algorithm based on smooth sensitivity with privacy cost Õ(1/(𝜀𝑛 √ 𝑛𝑝 • ) + 1/(𝜀 2 𝑛 2 𝑝 • )), which is much greater than that of [BCSZ18] for 𝜀 ≪ 1/( √ 𝑛𝑝 • ). Moreover, [SU19] gives evidence that their approach is inherently prohibited from achieving better privacy cost. On the other hand, known lower bounds in [BCSZ18, SU19] are not for Erdős-Rényi random graphs. This leads us to the following question: Is there a polynomial-time, differentially node-private, and rate-optimal edge density estimation algorithm for Erdős-Rényi random graphs?We essentially settled this question in this paper. Specifically, we give a polynomial-time and differentially node-private algorithm with privacy cost Õ(1/(𝜀𝑛 √ 𝑛𝑝 • )). Moreover, we show this error rate is optimal up to a logarithmic factor by proving an information-theoretical lower bound of Ω(1/(𝜀𝑛 √ 𝑛𝑝 • )). Our algorithm actually works for the more general inhomogeneous random graphs [BJR07] . The inhomogeneous random graph model encompasses any random graph model where edges appear independently (after conditioning on node labels). Notable examples include the stochastic block model [HLL83] , the latent space model [HRH02] , and graphon [BC17] .Our algorithm largely exploits the close connection between differential privacy and adversarial robustness in statistics. This connection dates back to [DL09] and has witnessed significant progress in the past few years [LKKO21, LKO22, KMV22, GH22, AUZ23, HKM22, HKMN23, AKT + 23, CCAd + 23, CDd + 24]. In particular, a very recent line of works [HKM22, HKMN23, CDd + 24] could efficiently achieve optimal or nearly-optimal accuracy guarantees in a number of high-dimensional statistical tasks, by integrating two powerful toolssum-of-squares method [RSS18] and exponential mechanisms [MT07] -in robustness and privacy respectively. Our algorithm extends this line of work. The key technical ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation and (2) an exponential mechanism whose score function is based on the sum-of-squares program. As a consequence, our private algorithm is also robust to adversarial corruptions.To state our results formally, we need the following definitions.Definition 1.1 (Node distance, neighboring graphs). Let 𝑛 ∈ ℕ. The node distance between two 𝑛-node graphs 𝐺 and 𝐺 ′ , denoted by dist(𝐺, 𝐺 ′ ), is the minimum number of nodes in 𝐺 that need to be rewired to obtain 𝐺 ′ . Moreover, we say 𝐺 and 𝐺 ′ are neighboring graphs if dist(𝐺, 𝐺 ′ ) ⩽ 1. Definition 1.2 (Node differential privacy). Let 𝒢 be the set of graphs. A randomized algorithm 𝒜 : 𝒢 → ℝ is 𝜀-differentially (node-)private if for every neighboring graphs 𝐺, 𝐺 ′ and every 𝑆 ⊆ ℝ, we haveℙ[𝒜(𝐺) ∈ 𝑆] ⩽ 𝑒 𝜀 • ℙ[𝒜(𝐺 ′ ) ∈ 𝑆] .Definition 1.3 (Node corruption model). Let 𝑛 ∈ ℕ and 𝜂 ∈ [0, 1]. For an 𝑛-node graph 𝐺, we say an 𝑛-node graph 𝐺 ′ is an 𝜂-corrupted version of 𝐺 if dist(𝐺, 𝐺 ′ ) ⩽ 𝜂𝑛.Erdős-Rényi random graphs. We provide a polynomial-time, differentially node-private and robust edge density estimation algorithm for Erdős-Rényi random graphs.Theorem 1.4 (Erdős-Rényi random graphs, combination of Theorem D.1 and Theorem F.1).There are constants 𝐶 1 , 𝐶 2 , 𝐶 3 such that the following holds. For any 𝜂 ⩽ 𝐶 1 , 𝜀 ⩾ 𝐶 2 log(𝑛)/𝑛, and 𝑝 • ⩾ 𝐶 3 /𝑛, there exists a polynomial-time 𝜀-differentially node-private algorithm which, given an 𝜂-corrupted Erdős-Rényi random graph 𝔾(𝑛, 𝑝 • ), outputs an estimate p satisfyingp 𝑝 • -1 ⩽ 𝑂 log 𝑛 𝑛 √ 𝑝 • + log 2 𝑛 𝜀𝑛 √ 𝑛𝑝 • + 𝜂 log 𝑛 √ 𝑛𝑝 • ,with probability 1 -𝑛 -Ω(1) .The first term 𝑂( log 𝑛/(𝑛 √ 𝑝 • )) is the sampling error that is necessary even without privacy or robustness. The second term 𝑂(log 2 (𝑛)/(𝜀𝑛 √ 𝑛𝑝 • )) is the privacy cost of our algorithm, which matches the exponential-time algorithm in [BCSZ18] . The third term 𝑂(𝜂 log 𝑛/ √ 𝑛𝑝 • ) is the robustness cost of our algorithm, which matches the information-theoretical lower bound Ω(𝜂/ √ 𝑛𝑝 • ) in [AJK + 22, Theorem 1.5] up to a log 𝑛 factor. Moreover, we provide the following lower bound which shows that the privacy cost of our algorithm is optimal up to a log 𝑛 factor.2 Theorem 1.5 (Privacy lower bound for Erdős-Rényi random graphs). Suppose there is an 𝜀-differentially node-private algorithm that, given an Erdős-Rényi random graph 𝔾(𝑛, 𝑝 • ), outputs an estimate p satisfying | p/𝑝 • -1| ⩽ 𝛼 with probability 1 -𝛽. Then we must have𝛼 ⩾ Ω log(1/𝛽) 𝜀𝑛 √ 𝑛𝑝 • .Inhomogeneous random graphs. Given an 𝑛-by-𝑛 edge connection probability matrix 𝑄 • , the inhomogeneous random graph model 𝔾(𝑛, 𝑄 • ) defines a distribution over 𝑛-node graphs where each edge {𝑖, 𝑗} is present with probability (𝑄 • ) 𝑖𝑗 independently.We provide a polynomial-time, differentially node-private and robust edge density estimation algorithm for inhomogeneous random graphs.Theorem 1.6 (Inhomogeneous random graphs, combination of Theorem D.1 and Theorem E.1). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑝 • := 𝑖,𝑗 𝑄 • 𝑖𝑗 /(𝑛 2 -𝑛).Suppose ∥𝑄 • ∥ ∞ ⩽ 𝑅𝑝 • for some 𝑅. There is a sufficiently small constant 𝑐 such that the following holds. For any 𝜂 such that 𝜂 log(1/𝜂)𝑅 ⩽ 𝑐, there exists a polynomial-time 𝜀-differentially nodeprivate algorithm which, given an 𝜂-corrupted inhomogeneous random graph 𝔾(𝑛, 𝑄 • ), outputs an estimate p satisfyingp 𝑝 • -1 ⩽ 𝑂 log 𝑛 𝑛 √ 𝑝 • + 𝑅 log 2 𝑛 𝜀𝑛 + 𝑅𝜂 log(1/𝜂) ,with probability 1 -𝑛 -Ω(1) .We improve on the previous private edge density estimation algorithm for inhomogeneous random graphs by Chen et al. [CDd + 24, Lemma 4.10]. Their algorithm is based on [SU19] and has privacy cost Õ(𝑅/(𝜀𝑛) + 1/(𝜀 2 𝑛𝑑 • )), while our algorithm only has privacy cost Õ(𝑅/(𝜀𝑛)). To the best of our knowledge, even without privacy requirement and in the special case of Erdős-Rényi random graphs, no previous algorithm can match our guarantees in the sparse regime. Specifically, when 𝑑 • ≪ log 𝑛 and 𝜂 ⩾ Ω(1), our algorithm can provide a constant-factor approximation of 𝑑 • , while the best previous robust algorithm [AJK + 22] can not.We also provide matching lower bounds, showing that the guarantee of our algorithm in Theorem 1.6 is optimal up to logarithmic factors.Theorem 1.7 (Robustness lower bound for inhomogeneous random graphs). Suppose there is an algorithm satisfies the following guarantee for any symmetric matrix 𝑄 𝑖𝑗 /𝑝 • . Theorem 1.8 (Privacy lower bound for inhomogeneous random graphs). Suppose there is an 𝜀-differentially node-private algorithm satisfies the following guarantee for any symmetric matrix 𝑄 • ∈ [0, 1] 𝑛×𝑛 . Given an inhomogeneous random graph 𝔾(𝑛, 𝑄 • ), the algorithm outputs an estimatep satisfying | p/𝑝 • -1| ⩽ 𝛼 with probability 1 -𝛽, where 𝑝 • = 𝑖,𝑗 𝑄 • 𝑖𝑗 /(𝑛 2 -𝑛). Then we must have 𝛼 ⩾ Ω 𝑅 log(1/𝛽) 𝑛𝜀 , where 𝑅 = max 𝑖,𝑗 𝑄 • 𝑖𝑗 /𝑝 • .We give an overview of the key techniques used to obtain our algorithm. As our techniques for Erdős-Rényi random graphs can be easily extended to the more general inhomogeneous random graph model, we will focus on Erdős-Rényi random graphs to avoid a proliferation of notation. Specifically, given an 𝜂-corrupted Erdős-Rényi random graph 𝔾(𝑛, 𝑑 𝐴 ′ dist(𝐴 ′ , 𝐴) : |𝒜 robust (𝐴 ′ ) -𝑑| ⩽ 1/poly(𝑛) , (1.1)where 𝐴 is the adjacency matrix of input graph and 𝑑 is a candidate estimate. For privacy analysis, note that the sensitivity of the above score function is bounded by 1, as the node distance between neighboring graphs is at most 1. For utility analysis, when the input graph is a typical Erdős-Rényi random graph, the exponential mechanism will with high probability output a d of score 𝑂(log(𝑛)/𝜀). Then we can argue that such a d is close to 𝑑 • using the robustness of 𝒜 robust . For example, if we plug in the robust algorithm in [AJK + 22, Theorem 1.3], then the corresponding exponential mechanism will only incur a privacy cost of Õ(1/(𝜀𝑛 √ 𝑑 • )). However, directly plugging in the robust algorithm in [AJK + 22] will lead to an exponentialtime algorithm, as a single evaluation of the score function requires enumerating all 𝑛-node graphs. To obtain a polynomial-time algorithm, we develop a new robust algorithm via the sum-of-squares method.3Robust algorithm via sum-of-squares. The sum-of-squares method uses convex programming (in particular, semidefinite programming) to solve polynomial programming. It is a very powerful tool for designing polynomial-time robust estimators (see [RSS18] ). To obtain a robust algorithm via sum-of-squares, we first identify a set of polynomial constraints that a typical (uncorrupted) Erdős-Rényi random graph would satisfy. Specifically, these polynomial constraints encode the following regularity conditions: (1) the degrees of the nodes are highly concentrated, and (2) the centered adjacency matrix is spectrally bounded.3In general, the black-box reduction by [HKMN23, AUZ23] does not provide guarantees in terms of computational complexity. For the problem of robust edge density estimation under node corruption, there is no known sum-of-squares algorithm before our work, and we are only aware of the iterative algorithm [AJK + 22]. For such algorithms not based on convex relaxation, it is completely unclear how to use the aforementioned connection between private and robust estimation towards an efficient private algorithm.We also include the constraint that at most 𝜂 fraction of the nodes in the graph are corrupted. Then we give a proof that if a graph satisfies the above constraints, then its average degree will be close to 𝑑 • , even when 𝜂 fraction of nodes in the input graph are arbitrarily corrupted. Importantly, the proof is simple enough that it is captured by the sum-of-squares proof system (see [FKP + 19]). This allows us to extend the utility guarantee of the polynomial program to its semidefinite programming relaxation, which results in a polynomial-time robust algorithm.Sum-of-squares exponential mechanism. Given the above robust algorithm, we then use the sum-of-squares exponential mechanism developed in [HKM22, HKMN23] to obtain a private algorithm. More specifically, we apply the exponential mechanism with the sum-ofsquares relaxation of the score function in Eq. (1.1). In this way, we obtain a private algorithm that is also robust to adversarial corruptions.We introduce some notation used throughout this paper. We write 𝑓 ≲ 𝑔 to denote the inequality 𝑓 ⩽ 𝐶 • 𝑔 for some absolute constant 𝐶 > 0. We write 𝑂( 𝑓 ) and Ω( 𝑓 ) to denote quantities 𝑓 -and 𝑓 + satisfying 𝑓 -≲ 𝑓 and 𝑓 ≲ 𝑓 + respectively. We use boldface to denote random variables, e.g., 𝑿 , 𝒀 , 𝒁. For a matrix 𝑀, we use ∥𝑀 ∥ op for the spectral norm of 𝑀.Let 𝟙 and 𝟘 denote the all-one and all-zero vector respectively, of which the size will be clear from the context. We use a graph 𝐺 and its adjacency matrix 𝐴 = 𝐴(𝐺) interchangeably when there is no ambiguity. For an 𝑛-by-𝑛 matrix 𝑀, we use 𝑑(𝑀) to denote its average row/column sum, i.e., 𝑑(𝑀) = 𝑖,𝑗 𝑀 𝑖𝑗 /𝑛. For any matrices (or vectors) 𝑀, 𝑁 of the same shape, we use 𝑀 ⊙ 𝑁 to denote the element-wise product (aka Hadamard product) of 𝑀 and 𝑁.The rest of the paper is organized as follows. In Section 2, we give a proof overview of our results and defer full proofs to the appendices. The appendices are organized as follows. We provide some sum-of-squares background in Appendix A and some concentration inequalities for random graphs in Appendix B. In Appendix C, we present a general sum-ofsquares exponential mechanism that all of our private algorithms in this paper are based on. In Appendix D, we present our coarse estimation algorithm and give a full proof of its guarantees (Theorem D.1). In Appendix E, we present our fine estimation algorithm for inhomogeneous random graphs and give a full proof of its guarantees (Theorem E.1). In Appendix F, we present our fine estimation algorithm for Erdős-Rényi random graphs and give a full proof of its guarantees (Theorem F.1). All lower bounds are proved in Appendix G. 
private and robust algorithm for erdős-rényi random graphs: 
 In this section, we describe our private and robust algorithm for Erdős-Rényi random graphs. We also give an overview of the analysis of our algorithm and sketch the proof of our lower bounds.Our overall algorithm consists of two stages. In the first stage, we compute a coarse estimate that approximates the edge density parameter within constant factors. In the second stage, we improve the accuracy of this coarse estimate to the optimum. Since our algorithm is private in both stages, it is also private overall by the composition theorem of differential privacy (see [DR14, Section 3.5]).We remark that for the Erdős-Rényi random graph model 𝔾(𝑛, 𝑝 • ), estimating its edge density parameter 𝑝 • is equivalent to estimating its expected average degree 𝑑 • := 𝑛𝑝 • .4 For the convenience of notation, we set our goal as estimating the expected average degree 𝑑 • throughout this section.Given an 𝑛-by-𝑛 symmetric matrix 𝐴 and a scalar 𝛾 ∈ [0, 1], let 𝒯 (𝑌, 𝑧; 𝐴, 𝛾) be a polynomial system with indeterminates 𝑌 = (𝑌 𝑖𝑗 ) 𝑖,𝑗∈[𝑛] and 𝑧 = (𝑧 𝑖 ) 𝑖∈[𝑛] that encodes the node distance between 𝑌 and 𝐴: EQUATIONIn this part, we describe a private and robust algorithm that can estimate the expected average degree 𝑑 • within a constant approximation ratio. Theorem 2.2 (Coarse estimation algorithm, informal restatement of Theorem D.1). For 𝜂 smaller than some constant, there is a polynomial-time 𝜀-differentially node-private algorithm which, given an 𝜂-corrupted Erdős-Rényi random graph 𝔾(𝑛, 𝑑 • /𝑛), outputs an estimate d such that| d -𝑑 • | ⩽ 0.5𝑑 • .We give a proof sketch of Theorem 2.2 at the end of this subsection. The formal theorem and proofs are deferred to Appendix D.Identifiability proof for robust estimation. We first give a polynomial system that can identify the expected average degree 𝑑 • up to constant factors, even when 𝜂-fraction of nodes are corrupted. Consider the following regularity condition on degrees:ℛ(𝑌) := (𝑌𝟙) 𝑖 ⩽ 2 log(1/𝜂) • 𝑑(𝑌) , ∀𝑖 ∈ [𝑛] .(2.4)The following lemma shows that Erdős-Rényi random graphs satisfy 𝒯 (𝑌, 𝑧; 𝐴, 2𝜂) ∪ ℛ(𝑌) with high probability.Let 𝐴 • ∼ 𝔾(𝑛, 𝑑 • /𝑛) and let 𝐴 be an 𝜂-corrupted version of 𝐴 • . With high probability, there exists a graph 𝑌 that satisfies the constraints in 𝒯 (𝑌, 𝑧; 𝐴, 2𝜂) ∪ ℛ(𝑌).Proof sketch. For 𝑑 • ≫ log(𝑛), the maximum degree of 𝐴 • is of order 𝑂(𝑑 • ). Therefore, the uncorrupted graph 𝐴 • satisfies the constraints. For 𝑑 • ≪ log 𝑛, using concentration properties of random graphs, we can show that the number of high degree nodes is bounded by 𝜂𝑛. A feasible graph can then be obtained from the uncorrupted graph 𝐴 • by trimming these highest degree nodes.Next, we show that these polynomial constraints give an identifiability proof for the expected average degree 𝑑 • . Lemma 2.4 (Identifiability). Let 𝐴 • ∼ 𝔾(𝑛, 𝑑 • /𝑛) and let 𝐴 be an 𝜂-corrupted version of 𝐴 • . For 𝜂 smaller than some constant and 𝛾 ⩽ 𝑂(𝜂), with high probability there is a degree-8 sum-of-squares proof that, if 𝑌 satisfies 𝒯 (𝑌, 𝑧; 𝐴, 𝛾) ∪ ℛ(𝑌), then |𝑑(𝑌) -𝑑 • | ⩽ 0.001𝑑 • .Proof sketch. We first assume that 𝑑 • ≫ log(𝑛), for which the proof is simpler. By the degreebound constraint ℛ(𝑌), we have 𝑛|𝑑(𝑌) -𝑑(𝐴 • )| ⩽ 2 log(1/𝜂) • (𝑑(𝑌) + 𝑑 • ) • dist(𝑌, 𝐴 • ). Using the constraints 𝑌 ⊙ 𝑧𝑧 ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤ and ⟨1, 𝑧⟩ ⩾ (1 -𝛾)𝑛, we have dist(𝑌, 𝐴) ⩽ 𝛾𝑛. Since dist(𝐴, 𝐴 • ) ⩽ 𝜂𝑛, by triangle inequality, we have dist(𝑌, 𝐴 • ) ⩽ (𝛾 + 𝜂)𝑛. Therefore, we have |𝑑(𝑌) -𝑑(𝐴 • )| ⩽ 0.0001𝑑 • when 𝛾, 𝜂 are at most some small constants. Finally, by random graph concentration, we have |𝑑 • -𝑑(𝐴 • )| ⩽ 𝑜(𝑑 • ) with high probability. Therefore, we have|𝑑(𝑌) -𝑑(𝐴 • )| ⩽ 0.001𝑑 • .To deal with the sparse regime where 𝑑 • ≪ log 𝑛, we need to truncate the nodes of 𝐴 • with degree Ω(log(1/𝜂)𝑑 • ). Our key observation is that, the average degree of the graph before and after truncation only differ by a constant factor. Therefore, we can still get|𝑑(𝑌) -𝑑(𝐴 • )| ⩽ 0.001𝑑 • .Furthermore, it can be shown that this proof is a degree-8 sum-of-squares proof.Robust algorithm via sum-of-squares. Consider the algorithm that finds a level-8 pseudoexpectation satisfying 𝒯 (𝑌, 𝑧; 𝐴, 2𝜂) ∪ ℛ(𝑌) -with ℛ(𝑌) given in Eq. ( Utility. For simplicity, we consider the case when there is no corruption (i.e. 𝜂 = 0). The analysis for the case when 𝜂 > 0 is similar. Let 𝐴 • ∼ 𝔾(𝑛, 𝑑 • /𝑛). Then with high probability sos-score(𝑑 𝒯 (𝑌, 𝑧; 𝐴, 𝛾) ∪ ℛ(𝑌) ∪ {|𝑑(𝑌) -𝑑| ⩽ 1/poly(𝑛)} with 𝛾 ≲ log(𝑛)/(𝜀𝑛). When log(𝑛)/(𝜀𝑛)is at most a small constant, it follows from our sum-of-squares identifiability proof in Lemma 2.4 that, Algorithm 2.5 outputs a constant-factor approximation of 𝑑 • with high probability.□From Section 2.2, we know how to obtain a constant-factor approximation of 𝑑 • privately and robustly. In this section, we show how to improve the accuracy to the optimum.Theorem 2.6 (Fine estimation algorithm, informal restatement of Theorem F.1). Let 0.5𝑑 𝑑 • -1 ⩽ Õ 1 √ 𝑛𝑑 • + 1 𝜀𝑛 √ 𝑑 • + 𝜂 √ 𝑑 • .We give a proof sketch of Theorem 2.6 at the end of this section. The formal theorem and proofs are deferred to Appendix F.Identifiability proof for robust estimation. We first give a polynomial system which can identify the expected average degree 𝑑 • with optimal error rate, when provided with a coarse estimate d. Consider the following regularity conditions on degrees and eigenvalues: EQUATIONNext we give a sum-of-squares identifiability proof for expected average degree estimation with optimal accuracy. Lemma 2.8 (Identifiability). Let 𝐴 • ∼ 𝔾(𝑛, 𝑑 • /𝑛) and let 𝐴 be an 𝜂-corrupted version of 𝐴 • .Suppose 𝑑 • /2 ⩽ d ⩽ 2𝑑 • .For 𝜂 smaller than some constant and 𝛾 ⩽ 𝑂(𝜂), with high probability there is a degree-8 sum-of-squares proof that, if 𝑌 satisfies 𝒯 (𝑌, 𝑧; 𝐴, 𝜂) ∪ ℛ(𝑌), then𝑑(𝑌) 𝑑 • -1 ⩽ Õ 1 √ 𝑛𝑑 • + 𝜂 √ 𝑑 • .Proof sketch. Let 𝑌 1 , 𝑌 2 be two graphs satisfying the regularity condition ℛ(𝑌 1 ) and ℛ(𝑌 2 ) as described in Eq. (2.7), respectively. We give sum-of-squares proof that, if dist(𝑌 1 , 𝑌 2 ) ⩽ 𝜁𝑛and 𝜁 is at most some small constant, then|𝑑(𝑌 1 ) -𝑑(𝑌 2 )| ⩽ 𝜁 d log 𝑛 .Let 𝑤 ∈ {0, 1} 𝑛 be the indicator vector for the shared induced subgraph between 𝑌 1 and 𝑌 2 ,i.e 𝑌 1 ⊙ 𝑤𝑤 ⊤ = 𝑌 2 ⊙ 𝑤𝑤 ⊤ . When dist(𝑌 1 , 𝑌 2 ) ⩽ 𝜁𝑛, we have ⟨𝑤, 𝟙⟩ ⩾ (1 -𝜁)𝑛. We have 𝑛 𝑑(𝑌 1 ) -𝑑(𝑌 2 ) =⟨𝑌 1 -𝑌 2 , 𝟙𝟙 ⊤ ⟩ =⟨𝑌 1 -𝑌 2 , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ =⟨𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ + 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ - 𝑑(𝑌 2 ) 𝑛 𝟙𝟙 ⊤ + 𝑑(𝑌 2 ) 𝑛 𝟙𝟙 ⊤ -𝑌 2 , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ =⟨𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + ⟨ 𝑑(𝑌 2 ) 𝑛 𝟙𝟙 ⊤ -𝑌 2 , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + ⟨ 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ - 𝑑(𝑌 2 ) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ .By rearranging terms, we can get⟨𝟙, 𝑤⟩ 2 𝑛 𝑑(𝑌 1 ) -𝑑(𝑌 2 ) = ⟨𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + ⟨ 𝑑(𝑌 2 ) 𝑛 𝟙𝟙 ⊤ -𝑌 2 , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ .For the first term ⟨𝑌 1 -𝑑(𝑌 1 )𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩, we have ⟨𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ = 2⟨𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ , 𝟙(𝟙-𝑤) ⊤ ⟩ + ⟨ 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ -𝑌 1 , (𝟙-𝑤)(𝟙-𝑤) ⊤ ⟩ . From constraints |(𝑌 1 𝟙) 𝑖 -𝑑(𝑌 1 )| ⩽ d log(𝑛) for all 𝑖 ∈ [𝑛], we have ⟨𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ , 𝟙(𝟙 -𝑤) ⊤ ⟩ = ⟨𝑌 1 𝟙 -𝑑(𝑌 1 )𝟙, 𝟙 -𝑤⟩ ⩽ 𝜁𝑛 log(𝑛) d . From constraints 𝑌 1 -𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ op ⩽ 𝛿 d, we have ⟨ 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ -𝑌 1 , (𝟙 -𝑤)(𝟙 -𝑤) ⊤ ⟩ ⩽ 𝑌 1 - 𝑑(𝑌 1 ) 𝑛 𝟙𝟙 ⊤ op ∥𝟙 -𝑤∥ 2 2 ⩽ 𝜁𝑛 d log(𝑛) ,The same bounds also apply for the second term ⟨𝑌 2 -𝑑(𝑌 2 )𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩. Since ⟨𝟙, 𝑤⟩ ⩾ Ω(𝑛), it follows that |𝑑(𝑌 1 ) -𝑑(𝑌 2 )| ⩽ Õ(𝜁 d) ⩽ Õ(𝜁 √ 𝑑 • ).Since the original uncorrupted graph satisfies the regularity conditions, this gives the identifiability proof that |𝑑(𝑌) -𝑑(𝐴 ⩽ Õ(1/ √ 𝑛𝑑 • + 𝜂/ √ 𝑑 • ). Moreover, the algorithm can be implemented by semidefinite programming and run in polynomial time.Private and robust algorithm via sum-of-squares exponential mechanism. We present our private and robust algorithm in Algorithm 2.9 and give a proof sketch of Theorem 2.6. Algorithm 2.9 (Private fine estimation for Erdős-Rényi random graphs). Input: 𝜂 corrupted random graph 𝐴, 𝜀-differentially private coarse estimate d.Output: A sample from the distribution 𝜇 𝐴,𝜀 with support [0, 𝑛] and densityEQUATIONwhere sos-score(𝑑; 𝐴) is defined asEQUATIONwith ℛ(𝑌) given in Eq. (2.7).Proof sketch of Theorem 2.6. Privacy. By Lemma 2.1, Algorithm 2.9 is 2𝜀-differentially private. Utility. For simplicity, we consider the case when there is no corruption (i.e. 𝜂 = 0). The analysis for the case when 𝜂 > 0 is similar. Let 𝐴 • ∼ 𝔾(𝑛, 𝑑 • /𝑛). Then with high probability sos-score(𝑑 • ; 𝐴 • ) = 0. By a standard volume argument, Algorithm 2.9 outputs a scalar 𝑑 that satisfies sos-score(𝑑; 𝐴 • ) ≲ log(𝑛)/𝜀 with high probability. By the definition of sos-score in Eq. (2.9), this implies that with high probability there exists a level-8 pseudo-distribution satisfying 𝒯 (𝑌, 𝑧; 𝐴, 𝛾) ∪ ℛ(𝑌) with 𝛾 ≲ log(𝑛)/(𝜀𝑛). Taking 𝜂 = log(𝑛)/(𝜀𝑛) in Lemma 2.8, it follows that Algorithm 2.9 outputs an estimated such that | d/𝑑 • -1| ⩽ Õ(1/ √ 𝑛𝑑 • +1/(𝜀𝑛 √ 𝑑 • )) with high probability.We sketch the proof of Theorem 1.5. Let 𝛼 ∈ [0, 1] and 𝑑 = (1 -𝛼)𝑑 • . We can construct a coupling 𝜔 between the distributions 𝔾(𝑛, 𝑑/𝑛) and 𝔾(𝑛, 𝑑 • /𝑛) with the following property. For (𝑮, 𝑮 ′ ) ∼ 𝜔, we have dist(𝑮, 𝑮 ′ ) bounded by Õ(𝛼𝑛 √ 𝑑 • ) with overwhelmingly high probability. By the definition of differential privacy, when 𝜀𝛼𝑛 √ 𝑑 • ⩽ 1/polylog(𝑛), the output of an 𝜀-differentially private algorithm are indistinguishable under 𝔾(𝑛, 𝑑/𝑛) and 𝔾(𝑛, 𝑑 • /𝑛). Therefore, by setting 𝛼 = Õ(1/𝜀𝑛 √ 𝑑 • ), we conclude that no 𝜀-differentially private algorithm can achieve error rate better than Õ(1/𝜀𝑛 √ 𝑑 • ). This provides a matching lower bound for our private edge density estimation algorithm.In this paper, we use the sum-of-squares semidefinite programming hierarchy [BS14, BS16, RSS18] for both algorithm design and analysis. The sum-of-squares proof-to-algorithm framework has been proven useful in many optimal or state-of-the-art results in algorithmic statistics [HL18, KSS18, PS17, Hop20]. We provide here a brief introduction to pseudodistributions, sum-of-squares proofs, and sum-of-squares algorithms.Pseudo-distribution. We can represent a finitely supported probability distribution over ℝ 𝑛 by its probability mass function 𝜇 : ℝ 𝑛 → ℝ such that 𝜇 ⩾ 0 and 𝑥∈supp(𝜇) 𝜇(𝑥) = 1. We define pseudo-distributions as generalizations of such probability mass distributions by relaxing the constraint 𝜇 ⩾ 0 to only require that 𝜇 passes certain low-degree non-negativity tests.Definition A.1 (Pseudo-distribution). A level-ℓ pseudo-distribution 𝜇 over ℝ 𝑛 is a finitely supported function 𝜇 : ℝ 𝑛 → ℝ such that 𝑥∈supp(𝜇) 𝜇(𝑥) = 1 and 𝑥∈supp(𝜇) 𝜇(𝑥) 𝑓 (𝑥) 2 ⩾ 0 for every polynomial 𝑓 of degree at most ℓ /2.We can define the expectation of a pseudo-distribution in the same way as the expectation of a finitely supported probability distribution. Definition A.2 (Pseudo-expectation). Given a pseudo-distribution 𝜇 over ℝ 𝑛 , we define the pseudo-expectation of a function 𝑓 :ℝ 𝑛 → ℝ by Ẽ 𝜇 𝑓 := 𝑥∈supp(𝜇) 𝜇(𝑥) 𝑓 (𝑥) . (A.1)The following definition formalizes what it means for a pseudo-distribution to satisfy a system of polynomial constraints.Definition A.3 (Constrained pseudo-distributions). Let 𝜇 : ℝ 𝑛 → ℝ be a level-ℓ pseudodistribution over ℝ 𝑛 . Let 𝒜 = { 𝑓 1 ⩾ 0, . . . , 𝑓 𝑚 ⩾ 0} be a system of polynomial constraints.We say that 𝜇 satisfies 𝒜 at level 𝑟, denoted by 𝜇 𝑟 𝒜, if for every multiset 𝑆 ⊆ [𝑚] and every sum-of-squares polynomial ℎ such that deg(ℎ)+ 𝑖∈𝑆 max{deg( 𝑓 𝑖 ), 𝑟} ⩽ ℓ , Ẽ 𝜇 ℎ • 𝑖∈𝑆 𝑓 𝑖 ⩾ 0 . (A.2)We say 𝜇 satisfies 𝒜 and write 𝜇 𝒜 (without further specifying the degree) if 𝜇 0 𝒜.We remark that if 𝜇 is an actual finitely supported probability distribution, then we have 𝜇 𝒜 if and only if 𝜇 is supported on solutions to 𝒜.Sum-of-squares proof. We introduce sum-of-squares proofs as the dual objects of pseudodistributions, which can be used to reason about properties of pseudo-distributions. We say a polynomial 𝑝 is a sum-of-squares polynomial if there exist polynomials (𝑞 𝑖 ) such that 𝑝 = 𝑖 𝑞 2 𝑖 . Definition A.4 (Sum-of-squares proof). A sum-of-squares proof that a system of polynomial constraints 𝒜 = { 𝑓 1 ⩾ 0, . . . , 𝑓 𝑚 ⩾ 0} implies 𝑞 ⩾ 0 consists of sum-of-squares polynomials(𝑝 𝑆 ) 𝑆⊆[𝑚] such that6 𝑞 = multiset 𝑆⊆[𝑚] 𝑝 𝑆 • 𝑖∈𝑆 𝑓 𝑖 .If such a proof exists, we say that 𝒜 (sos-)proves 𝑞 ⩾ 0 within degree ℓ , denoted by 𝒜 ℓ 𝑞 ⩾ 0.In order to clarify the variables quantified by the proof, we often write 𝒜(𝑥) ℓ 𝑥 𝑞(𝑥) ⩾ 0.6Here we follow the convention that 𝑖∈𝑆 𝑓 𝑖 = 1 for 𝑆 = ∅.We say that the system 𝒜 sos-refuted within degree ℓ if 𝒜 ℓ -1 ⩾ 0. Otherwise, we say that the system is sos-consistent up to degree ℓ , which also means that there exists a level-ℓ pseudo-distribution satisfying the system.The following lemma shows that sum-of-squares proofs allow us to deduce properties of pseudo-distributions that satisfy some constraints.Lemma A.5. Let 𝜇 be a pseudo-distribution, and let 𝒜, ℬ be systems of polynomial constraints.Suppose there exists a sum-of-squares proof 𝒜 𝑟 ′ ℬ.If 𝜇 𝑟 𝒜, then 𝜇 𝑟•𝑟 ′ +𝑟 ′ ℬ.Sum-of-squares algorithm. Given a system of polynomial constraints, the sum-of-squares algorithm searches through the space of pseudo-distributions that satisfy this polynomial system by semidefinite programming.Since semidefinite programing can only be solved approximately, we can only find pseudodistributions that approximately satisfy a given polynomial system. We say that a level-ℓ pseudo-distribution approximately satisfies a polynomial system, if the inequalities in Eq. (A.2) are satisfied up to an additive error of 2 Remark A.7 (Approximation error and bit complexity). For a pseudo-distribution that only approximately satisfies a polynomial system, we can still use sum-of-squares proofs to reason about it in the same way as Lemma A.5. In order for approximation errors not to amplify throughout reasoning, we need to ensure that the bit complexity of the coefficients in the sum-of-squares proof are polynomially bounded.Lemma A.8.{𝑥 2 = 𝑥} 2 𝑥 0 ⩽ 𝑥 ⩽ 1 .Proof. The first inequality is trivial due to {𝑥 2 = 𝑥} 2 𝑥 𝑥 = 𝑥 2 ⩾ 0. For the second inequality, it follows that{𝑥 2 = 𝑥} 2 𝑥 𝑥 ⩽ 𝑥 2 2 + 1 2 = 𝑥 2 + 1 2 .Rearranging the terms, we get{𝑥 2 = 𝑥} 2 𝑥 𝑥 ⩽ 1 . □ Lemma A.9. {𝑥 2 = 𝑥, 𝑦 2 = 𝑦} 4 𝑥,𝑦 1 -𝑥 𝑦 ⩽ (1 -𝑥) + (1 -𝑦) .Proof. By Lemma A.8, it follows that{𝑥 2 = 𝑥, 𝑦 2 = 𝑦} 2 𝑥,𝑦 0 ⩽ 𝑥, 𝑦 ⩽ 1 .Therefore, we have{𝑥 2 = 𝑥, 𝑦 2 = 𝑦} 4 𝑥,𝑦 (1 -𝑦)(1 -𝑥) ⩾ 07The choice of norm is not important here because the factor 2 -𝑛 ℓ swamps the effects of choosing another norm.8A system of polynomial constraints is explicitly bounded if it contains a constraint of the form∥𝑥 ∥ 2 ⩽ 𝑀.9Here we assume that the bit complexity of the constraints in 𝒜 is (𝑛 + 𝑚) 𝑂(1) .4𝑥,𝑦 1 -𝑥 -𝑦 ⩾ -𝑥 𝑦 4 𝑥,𝑦 2 -𝑥 -𝑦 ⩾ 1 -𝑥 𝑦 .Lemma A.10. Given constant 𝐶, we have{-𝐶 ⩽ 𝑥 ⩽ 𝐶} 2 𝑥 𝑥 2 ⩽ 𝐶 2 .Proof.{-𝐶 ⩽ 𝑥 ⩽ 𝐶} 2 𝑥 (𝐶 -𝑥)(𝐶 + 𝑥) ⩾ 0 2 𝑥 𝐶 2 -𝑥 2 ⩾ 0 2 𝑥 𝐶 2 ⩾ 𝑥 2 .Lemma A.11. Given constant 𝐶, we have{𝑥 2 ⩽ 𝐶 2 } 2 𝑥 -𝐶 ⩽ 𝑥 ⩽ 𝐶 .Proof. For the first inequality, we have{𝑥 2 ⩽ 𝐶 2 } 2 𝑥 𝑥 ⩾ - 𝑥 2 2𝐶 - 𝐶 2 ⩾ - 𝐶 2 2𝐶 - 𝐶 2 = -𝐶 .For the second inequality, we have{𝑥 2 ⩽ 𝐶 2 } 2 𝑥 𝑥 ⩽ 𝑥 2 2𝐶 + 𝐶 2 ⩽ 𝐶 2 2𝐶 + 𝐶 2 = 𝐶 .Lemma B.1 (Average degree concentration). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑑 • := 𝑑(𝑄 • ). Let 𝑨 ∼ 𝔾(𝑛, 𝑄 • ). Then for any 𝛿 ∈ (0, 1), ℙ(|𝑑(𝑨) -𝑑 • | ⩾ 𝛿𝑑 • ) ⩽ 2 exp - 𝛿 2 𝑛𝑑 • 6 , Proof. Let 𝜇 := 𝔼 𝑖<𝑗 𝑨 𝑖𝑗 = 𝑖<𝑗 𝑝 𝑖𝑗 . Using Chernoff bound, for 𝛿 ∈ (0, 1), ℙ 𝑖<𝑗 𝑨 𝑖𝑗 -𝜇 ⩾ 𝛿𝜇 ⩽ 2 exp - 𝛿 2 𝜇 3 , ℙ(|𝑑(𝑨) -𝑑 • | ⩾ 𝛿𝑑 • ) ⩽ 2 exp - 𝛿 2 𝑛𝑑 • 6 . □ Lemma B.ℙ(𝒎 𝑡𝑑 ⩾ 𝛾𝑛) ⩽ 𝑛 𝛾𝑛 𝛾𝑛 2 𝛾𝑛𝑡𝑑/2 𝑑 𝑛 𝛾𝑛𝑡𝑑/2 ⩽ 𝑒 𝛾 𝛾𝑛 2𝑒 𝑡 𝛾𝑛𝑡𝑑/2 = exp -𝛾𝑛 𝑡𝑑 2 log 𝑡 2𝑒 -log 𝑒 𝛾 .Plugging in 𝛾 = 𝑒 -𝑡 gives happens with probability at least 1 -𝑛 1-𝑑/4 . We condition our following analysis on this event.ℙ 𝒎 𝑡𝑑 ⩾ 𝑒 -𝑡 𝑛 ⩽ exp -𝑡𝑒 -𝑡 𝑛 𝑑 2 log 𝑡 2𝑒 -1 -1/𝑡 . For 𝑡 ∈ [2𝑒Fix a 𝑡 ∈ [2𝑒 2 , log 𝑛]. The number of edges incident to nodes with degree at least 𝑡𝑑 is at most𝑖=0 (𝑡 + 𝑖 + 1)𝑑 • 𝑒 -(𝑡+𝑖) 𝑛 = 𝑛𝑑 𝑖=𝑡 (𝑖 + 1)𝑒 -𝑖 = 𝑛𝑑𝑒 -𝑡 𝑒 𝑒 -1 𝑡 + 𝑒 2 (𝑒 -1) 2 ⩽ 2𝑡𝑒 -𝑡 𝑛𝑑 .Lemma B.4 (Degree-truncated subgraph). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑑 • := 𝑑(𝑄 • ). Let 𝑑 be a parameter such that 𝑑 ⩾ 5 and ∥𝑄 • ∥ ∞ ⩽ 𝑑/𝑛. For 𝛿 ∈ (0, 1), an inhomogeneous graph 𝑨 ∼ 𝔾(𝑛, 𝑄 • ) has the following property with probability at least 1 -𝑛 1-𝑑/4 -exp(-𝛿 2 𝑛𝑑 • /6). For every 𝑡 ∈ [2𝑒 2 , log 𝑛], 𝐴 contains an 𝑛-node subgraph Ã of such that• ( Ã𝟙) 𝑖 ⩽ 𝑡𝑑 for any 𝑖 ∈ [𝑛]; • (1 -𝛿)𝑑 • -4𝑡𝑒 -𝑡 𝑑 ⩽ 𝑑( Ã) ⩽ (1 + 𝛿)𝑑 • .Proof. By Lemma B.1 and Lemma B.3, 𝑨 ∼ 𝔾(𝑛, 𝑄 • ) has the following two properties with probability at least 1 -𝑛 1-𝑑/4 -exp(-𝛿 2 𝑛𝑑 • /6).• |𝑑(𝐴) -𝑑 • | ⩽ 𝛿𝑑 • .• For all 𝑡 ∈ [2𝑒 2 , log 𝑛], the number of edges incident to nodes with degree at least 𝑡𝑑 is at most 2𝑡𝑒 -𝑡 𝑛𝑑.Consider a graph 𝐴 with the above two properties. Fix a 𝑡 ∈ [2𝑒 2 , log 𝑛]. By removing at most 2𝑡𝑒 -𝑡 𝑛𝑑 edges from 𝐴, we can obtain a graph Ã such that the maximum degree of Ã is at most 𝑡𝑑. Moreover,𝑑( Ã) ⩾ 𝑑(𝐴) -4𝑡𝑒 -𝑡 𝑑 ⩾ (1 -𝛿)𝑑 • -4𝑡𝑒 -𝑡 𝑑 , 𝑑( Ã) ⩽ 𝑑(𝐴) ⩽ (1 + 𝛿)𝑑 • .□ Lemma B.5 (Spectral bound [BvH16] ). Let 𝑨 ∼ 𝔾(𝑛, 𝑝 0 ) and suppose 𝑛𝑝 0 ⩾ 5. Then with probability at least 1 -𝑛 -Ω(1) , 𝑨 -𝑝 0 (𝟙𝟙 ⊤ -Id) op ⩽ 𝑂 𝑛𝑝 0 log 𝑛 .In this section, we present our sum-of-squares exponential mechanism and prove its properties in a general setting that incorporates all special cases in Appendix D, Appendix E and Appendix F.Setup. Let 𝒟 ⊂ ℝ 𝑁 . Given an 𝑛-by-𝑛 symmetric matrix 𝐴, our goal is to output an element 𝑑 from 𝒟 privately. We say two symmetric matrices are neighboring if they differ in at most one row and one column. The utility of an element 𝑑 ∈ 𝒟 is quantified by a score function defined as follows.For an 𝑛-by-𝑛 symmetric matrix 𝐴 and a scalar 𝛾, consider the following polynomial system with indeterminates (𝑌 𝑖𝑗 ) 𝑖,𝑗∈[𝑛] , (𝑧 𝑖 ) 𝑖∈[𝑛] and coefficients that depend on 𝐴, 𝛾:𝒬 1 (𝑌, 𝑧; 𝐴, 𝛾) :=        𝑧 ⊙ 𝑧 = 𝑧, ⟨𝟙, 𝑧⟩ ⩾ (1 -𝛾)𝑛 0 ⩽ 𝑌 ⩽ 𝟙𝟙 ⊤ , 𝑌 = 𝑌 ⊤ 𝑌 ⊙ 𝑧𝑧 ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤        . (C.1)For an element 𝑑 ∈ 𝒟, let 𝒬 2 (𝑌; 𝑑) be a polynomial system with coefficients depending on 𝑑 (and independent of 𝐴, 𝛾). Then for a matrix 𝐴 and an element 𝑑 ∈ 𝒟, we define the score of 𝑑 with regard to 𝐴 to be ⩾ 𝛾 * 𝑛 + 𝑡 log 𝑛 𝜀 ⩽ vol(𝒟) • exp -𝜀𝛾 * 𝑛 -𝑡 log 𝑛 vol(𝒢(𝐴 * )) • exp(-𝜀𝛾 * 𝑛) = vol(𝒟) vol(𝒢(𝐴 * ))• 𝑛 -𝑡 .In this section, we describe our coarse estimation algorithm that achieves constant multiplicative approximation of the expected average degree 𝑑 d satisfying | d/𝑑 • -1| ⩽ 0.5 with probability 1 -𝑛 -Ω(1) .We make a few remarks on Theorem D.1.• Our algorithm in Theorem D.1 is a sum-of-squares exponential mechanism. 𝑅, 𝜂, 𝜀 are parameters given as inputs to our algorithm.• We can get a constant estimate of 𝑝 • by taking p= d 𝑛-1 . Since p 𝑝 • = d 𝑑 • , it follows that | p 𝑝 • -1| ⩽ 0.5.• When 𝑄 • = 𝑝 • (𝟙𝟙 ⊤ -Id), the inhomogeneous random graph 𝔾(𝑛, 𝑄 • ) is just the Erdős-Rényi random graph 𝔾(𝑛, 𝑝 • ). Thus, by setting 𝑅 = 𝑛 𝑛-1 in Theorem D.1, we directly obtain a coarse estimation result for Erdős-Rényi random graphs.• The utility guarantee of our algorithm holds in the constant-degree regime (i.e. 𝑑 • ⩾ Ω(1)). To the best of our knowledge, even without privacy requirement and in the special case of Erdős-Rényi random graphs, no previous algorithm can match our guarantees in the constant-degree regime. Specifically, when 𝑑 • ≪ log 𝑛 and 𝜂 ⩾ Ω(1), the robust algorithm in [AJK + 22] can not provide a constant-factor approximation of 𝑑 • .In Appendix D.1, we set up polynomial systems that our algorithm uses and prove useful sos inequalities. In Appendix D.2, we show that we can easily obtain a robust algorithm via sos proofs in Appendix D.1. Then in Appendix D.3, we describe our algorithm and prove Theorem D.1.For an adjacency matrix 𝐴 and two nonnegative scalars 𝛾 and 𝜎, consider the following polynomial systems with indeterminates 𝑌 = (𝑌 𝑖𝑗 ) 𝑖,𝑗∈[𝑛] , 𝑧 = (𝑧 𝑖 ) 𝑖∈[𝑛] and coefficients that depend on 𝐴, 𝛾, 𝜎: 𝒫 1 (𝑌, 𝑧; 𝐴, 𝛾) :=        𝑧 ⊙ 𝑧 = 𝑧, ⟨𝟙, 𝑧⟩ ⩾ (1 -𝛾)𝑛 0 ⩽ 𝑌 ⩽ 𝟙𝟙 ⊤ , 𝑌 = 𝑌 ⊤ 𝑌 ⊙ 𝑧𝑧 ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤        , (D.(1 -2𝛾𝜎 -2𝛾 * 𝜎)𝑑(𝐴 * ) ⩽ 𝑑(𝑌) ⩽ 1 1 -2𝛾𝜎 -2𝛾 * 𝜎 𝑑(𝐴 * ) . Proof. Let 𝑤 = 𝑧 ⊙ 𝑧 * , by constraint 𝑌 ⊙ 𝑧𝑧 ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤ and 𝐴 * ⊙ 𝑧 * (𝑧 * ) ⊤ = 𝐴 ⊙ 𝑧 * (𝑧 * ) ⊤ , we have 𝒞 4 𝑌,𝑧 𝑌 ⊙ 𝑤𝑤 ⊤ = 𝑌 ⊙ 𝑧𝑧 ⊤ ⊙ 𝑧 * (𝑧 * ) ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤ ⊙ 𝑧 * (𝑧 * ) ⊤ = 𝐴 ⊙ 𝑧 * (𝑧 * ) ⊤ ⊙ 𝑧𝑧 ⊤ = 𝐴 * ⊙ 𝑧 * (𝑧 * ) ⊤ ⊙ 𝑧𝑧 ⊤ = 𝐴 * ⊙ 𝑤𝑤 ⊤ .Applying this equality, it follows that𝒞 4 𝑌,𝑧 𝑛 • 𝑑(𝑌) = 𝑌, 𝟙𝟙 ⊤ = 𝑌, 𝑤𝑤 ⊤ + 𝑌, 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ = 𝐴 * , 𝑤𝑤 ⊤ + 𝑌, 2(𝟙 -𝑤)𝟙 ⊤ -𝑌, (𝟙 -𝑤)(𝟙 -𝑤) ⊤ .For For the second term, we have𝒞 4 𝑌,𝑧 𝑌, 2(𝟙 -𝑤)𝟙 ⊤ = ⟨𝑌𝟙, 2(𝟙 -𝑤)⟩ = 𝑖∈[𝑛] 2(1 -𝑤 𝑖 ) • (𝑌𝟙) 𝑖 = 𝑖∈[𝑛] 2(1 -𝑧 𝑖 𝑧 * 𝑖 ) • (𝑌𝟙) 𝑖 ⩽ 𝑖∈[𝑛] 2(1 -𝑧 𝑖 ) • (𝑌𝟙) 𝑖 + 𝑖∈[𝑛] 2(1 -𝑧 * 𝑖 ) • (𝑌𝟙) 𝑖 ,where the last inequality is due to Lemma A.9. From constraints𝑖∈[𝑛] 1 -𝑧 * 𝑖 ⩽ 𝛾 * 𝑛, 𝑖∈[𝑛] 1 -𝑧 𝑖 ⩽ 𝛾𝑛 and (𝑌𝟙) 𝑖 ⩽ 𝜎𝑑(𝑌) for all 𝑖 ∈ [𝑛], it follows that 𝒞 4 𝑌,𝑧 𝑌, 2(𝟙 -𝑤)𝟙 ⊤ ⩽ 𝑖∈[𝑛] 2(1 -𝑧 𝑖 ) • 𝜎𝑑(𝑌) + 𝑖∈[𝑛] 2(1 -𝑧 * 𝑖 ) • 𝜎𝑑(𝑌) = 2𝜎𝑑(𝑌) • 𝑖∈[𝑛] 1 -𝑧 𝑖 + 2𝜎𝑑(𝑌) • 𝑖∈[𝑛]1 -𝑧 Let z ∈ {0, 1} 𝑛 denote the set of unpruned nodes (𝑧 • 𝑖 = 1 if and only if node 𝑖 is not pruned). We will show that 𝐴 * = Ã and 𝑧 * = 𝑧 • ⊙ z satisfies the lemma.Guarantee 1. By Lemma B.1, we know that, with probability 1 -𝑛 -Ω(1) ,|𝑑(𝑨 • ) -𝑑 • | ⩽ 10 𝑑 • log 𝑛 𝑛 . (D.7)From degree pruning guarantee (3), we have that|𝑑( Ã) -𝑑(𝑨 • )| ⩽ 2𝜂 log(1/𝜂)𝑛𝑅𝑑 • . (D.8)Combining Eq. (D.7) and Eq. (D.8), for some constant 𝐶 1 that is small enough, we have|𝑑( Ã) -𝑑 • | ⩽ |𝑑( Ã) -𝑑(𝑨 • )| + |𝑑(𝑨 • ) -𝑑 • | ⩽ 10 𝑑 • log 𝑛 𝑛 + 2𝜂 log 1 𝜂 𝑅𝑑 • ⩽ 10 log 𝑛 𝑛 𝑑 • + 2𝐶 1 𝑑 • ⩽ 0.1𝑑 • .(D.9) Guarantee 2. It is easy to check that 𝑧 * ⊙ 𝑧 * = 𝑧 * , 0 ⩽ 𝐴 * ⩽ 𝟙𝟙 ⊤ and 𝐴 * = (𝐴 * ) ⊤ . Since ⟨𝟙, z⟩ ⩾ 1 -𝜂𝑛 by degree pruning condition (2) and ⟨𝟙, 𝑧 • ⟩ ⩾ 1 -𝜂𝑛 by corruption rate, it is easy to verify that ⟨𝟙, 𝑧 * ⟩ ⩾ 1 -2𝜂𝑛 .Moreover, we have 𝐴 * ⊙ 𝑧 * (𝑧 * ) ⊤ = 𝐴 ⊙ 𝑧 * (𝑧 * ) ⊤ due toÃ ⊙ z z⊤ ⊙ 𝑧 • (𝑧 • ) ⊤ = 𝑨 • ⊙ z z⊤ ⊙ 𝑧 • (𝑧 • ) ⊤ = 𝑨 • ⊙ 𝑧 • (𝑧 • ) ⊤ ⊙ z z⊤ = 𝐴 ⊙ 𝑧 • (𝑧 • ) ⊤ ⊙ z z⊤ .From Eq. (D.9), we can get that 𝑑 • ⩽ 2𝑑( Ã). Plugging this into degree pruning condition (1), we getÃ𝟙 ∞ ⩽ log(1/𝜂)𝑅𝑑 • ⩽ 2 log(1/𝜂)𝑅𝑑( Ã) .Therefore, we have(𝐴 * 𝟙) 𝑖 ⩽ 2 log(1/𝜂)𝑅𝑑(𝐴 * ) .for all 𝑖 ∈ [𝑛].Thus, (𝐴 * , 𝑧 * ) is a feasible solution to 𝒞(𝑌, 𝑧; 𝐴, 𝛾, 𝜎) with 𝛾 = 2𝜂 and 𝜎 = 2 log(1/𝜂)𝑅.In this section, we show that the following algorithm based on sum-of-squares proofs in Appendix D.1 obtains a robust constant multiplicative approximation of 𝑑 • .Input: 𝜂-corrupted adjacency matrix 𝐴, corruption fraction 𝜂 and parameter 𝑅.Algorithm: Obtain level-8 pseudo-expectation Ẽ by solving sum-of-squares relaxation of program 𝒞(𝑌, 𝑧; 𝐴, 𝛾, 𝜎) (defined in Eq. (D.3)) with 𝐴, 𝛾 = 2𝜂 and 𝜎 = 2 log(1/𝜂)𝑅.Theorem D.5 (Robust coarse estimation). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑑 • := 𝑑(𝑄 • ). Suppose ∥𝑄 • ∥ ∞ ⩽ 𝑅𝑑 • /|𝑑(𝐴 * ) -𝑑 • | ⩽ 0.1𝑑 • .Therefore, we have𝒞(𝑌, 𝑧; 𝐴, 𝛾, 𝜎) 8 𝑌,𝑧 0.9(1 -4𝛾𝜎)𝑑 • ⩽ 𝑑(𝑌) ⩽ 1.1 1 -4𝛾𝜎 𝑑 • .Consider 4𝛾𝜎, for constant 𝑐 that is small enough, we have4𝛾𝜎 = 8𝜂 log(1/𝜂)𝑅 ⩽ 8𝑐 ⩽ 0.1 .This implies that 0.9(1 -4𝛾𝜎) ⩾ 1 2 and 1.1 1-4𝛾𝜎 ⩽ 11 9 ⩽ 3 2 . Therefore, we have 𝒞(𝑌, 𝑧; 𝐴, 𝛾, 𝜎) 8 𝑌,𝑧 1 2𝑑 • ⩽ 𝑑(𝑌) ⩽ 3 2 𝑑 • .Thus, the level-8 pseudo-expectation Ẽ satisfies 1 2𝑑 • ⩽ Ẽ[𝑑(𝑌)] ⩽ 3 2 𝑑 • , which implies that Ẽ[𝑑(𝑌)] 𝑑 • -1 ⩽ 1 2 .In this section, we present our algorithm and prove Theorem D.1. Our algorithm instantiates the sum-of-squares exponential mechanism in Appendix C. where 𝒞(𝑌, 𝑧; 𝐴, 𝛾, 𝜎) is the polynomial system defined in Eq. (D.3), and 𝜎, 𝛼 are fixed parameters whose values will be decided later. Note that (𝑌 = 𝑑 𝑛 𝟙𝟙 ⊤ , 𝑧 = 𝟘) is a solution to the polynomial system 𝒞(𝑌, 𝑧; 𝐴, 1, 𝜎) ∪ {|𝑑(𝑌) -𝑑| ⩽ 𝛼𝑑} for any 𝐴 ∈ ℝ 𝑛×𝑛 , 𝑑 ∈ [0, 𝑛], and 𝜎 ⩾ 1.To efficiently compute 𝑠(𝑑; 𝐴), we can use the scheme as described in Remark C.1. where 𝑠(𝑑; 𝐴) is defined in Eq. (D.10).To efficiently sample from 𝜇 𝐴,𝜀 , we can use the scheme as described in Remark C.2. From Appendix D, we have a constant multiplicative approximation of the expected average degree 𝑑 • . In this section, we show how to use this coarse estimate to obtain our fine estimator for inhomogeneous random graphs. Theorem E.1 (Fine estimation for inhomogeneous random graphs). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑑 • := 𝑑(𝑄 • ). Suppose ∥𝑄 • ∥ ∞ ⩽ 𝑅𝑑 • /𝑛 for some 𝑅. There is a sufficiently small constant 𝑐 such that the following holds. For any 𝜂 such that 𝜂 log(1/𝜂)𝑅 ⩽ 𝑐, there exists a polynomial-time 𝜀-differentially node private algorithm which, given an 𝜂-corrupted inhomogeneous random graph 𝔾(𝑛, 𝑄 • ) and a constant-factor approximation of 𝑑 • , outputs an estimate d satisfyingd 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝑅 log 2 𝑛 𝜀𝑛 + 𝜂 log(1/𝜂)𝑅 ,with probability 1 -𝑛 -Ω(1) .We make a few remarks on Theorem E.1.• Our algorithm in Theorem E.1 is a sum-of-squares exponential mechanism. 𝑅, 𝜂, 𝜀 are parameters given as input to our algorithm.• We can get an estimate of 𝑝 • by takingp = d 𝑛-1 . Since p 𝑝 • = d 𝑑 • , it follows that p 𝑝 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝑅 log 2 𝑛 𝜀𝑛 + 𝜂 log(1/𝜂)𝑅 .• Combining Theorem D.1 and Theorem E.1 gives us an efficient, private, and robust edge density estimation algorithm for inhomogeneous random graphs whose utility guarantee is information-theoretically optimal up to a factor of log 𝑛 and log(1/𝜂).In Appendix E.1, we set up polynomial systems that our algorithm uses and prove useful sos inequalities. In Appendix E.2, we show that we can easily obtain a robust algorithm via sos proofs in Appendix E.1. Then in Appendix E.3, we describe our algorithm and prove Theorem E.1.For an adjacency matrix 𝐴 and nonnegative scalars 𝛾, 𝜎 and d, consider the following polynomial systems with indeterminates 𝑌 = (𝑌 𝑖𝑗 ) 𝑖,𝑗∈[𝑛] , 𝑧 = (𝑧 𝑖 ) 𝑖∈[𝑛] and coefficients that depend on 𝐴, 𝛾, 𝜎, d:𝒫 1 (𝑌, 𝑧; 𝐴, 𝛾) :=        𝑧 ⊙ 𝑧 = 𝑧, ⟨𝟙, 𝑧⟩ ⩾ (1 -𝛾)𝑛 0 ⩽ 𝑌 ⩽ 𝟙𝟙 ⊤ , 𝑌 = 𝑌 ⊤ 𝑌 ⊙ 𝑧𝑧 ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤        , (E.1) 𝒫 3 (𝑌; 𝜎, d) := (𝑌𝟙) 𝑖 ⩽ 𝜎 d ∀𝑖 ∈ [𝑛] . (E.2)For convenience of notation, we will consider the following combined polynomial system in the remaining of this section 𝒟 8 𝑌,𝑧 𝑛 • 𝑑(𝑌) = 𝑌, 𝟙𝟙 ⊤ = 𝐴 * , 𝑤𝑤 ⊤ + 𝑌, 2(𝟙 -𝑤)𝟙 ⊤ -𝑌, (𝟙 -𝑤)(𝟙 -𝑤) ⊤ ⩽ 𝐴 * , 𝟙𝟙 ⊤ + ⟨𝑌𝟙, 2(𝟙 -𝑤)⟩ ⩽ 𝑛 • 𝑑(𝐴 * ) + 2(𝛾 + 𝛾 * )𝜎𝑛 d .• := 𝑑(𝑄 • ). Suppose ∥𝑄 • ∥ ∞ ⩽ 𝑅𝑑 • /𝑛 for 𝑅 ∈ ℝ.Let 𝐴 be an 𝜂-corrupted adjacency matrix of a random graph 𝑮 • ∼ 𝔾(𝑛, 𝑄 • ). Suppose 𝜂 log(1/𝜂)𝑅 ⩽ 𝐶 1 for some constant 𝐶 1 that is small enough. With probability 1 -𝑛 -Ω(1) , there exists 𝐴 * and 𝑧 * such that Let z ∈ {0, 1} 𝑛 denote the set of unpruned nodes (z 𝑖 = 1 if and only if node 𝑖 is not pruned). We will show that 𝐴 * = Ã and 𝑧 * = 𝑧 • ⊙ z satisfies the lemma. Guarantee 1. By Lemma B.1, we know that, with probability 1 -𝑛 -Ω(1) ,• |𝑑(𝐴 * ) -𝑑 • | ⩽ 10 𝑑 • log 𝑛 𝑛 + 2𝜂 log(1/𝜂)𝑅𝑑 • . • (𝐴 * ,|𝑑(𝑨 • ) -𝑑 • | ⩽ 10 𝑑 • log 𝑛 𝑛 . (E.4)From degree pruning guarantee (3), we have that|𝑑( Ã) -𝑑(𝑨 • )| ⩽ 2𝜂 log(1/𝜂)𝑅𝑑 • . (E.5)Combining Eq. (E.4) and Eq. (E.5), we have|𝑑( Ã) -𝑑 • | ⩽ |𝑑( Ã) -𝑑(𝐴 • )| + |𝑑(𝐴 • ) -𝑑 • | ⩽ 10 𝑑 • log 𝑛 𝑛 + 2𝜂 log(1/𝜂)𝑅𝑑 • .Guarantee 2. It is easy to check that 𝑧 * ⊙ 𝑧 * = 𝑧 * , 0 ⩽ 𝐴 * ⩽ 𝟙𝟙 ⊤ and 𝐴 * = (𝐴 * ) ⊤ . Since ⟨𝟙, z⟩ ⩾ 1 -𝜂𝑛 by degree pruning condition (2) and ⟨𝟙, 𝑧 • ⟩ ⩾ 1 -𝜂𝑛 by corruption rate, it is easy to verify that⟨𝟙, 𝑧 * ⟩ ⩾ 1 -2𝜂𝑛 . Moreover, we have 𝐴 * ⊙ 𝑧 * (𝑧 * ) ⊤ = 𝐴 ⊙ 𝑧 * (𝑧 * ) ⊤ due to Ã ⊙ z z⊤ ⊙ 𝑧 • (𝑧 • ) ⊤ = 𝑨 • ⊙ z z⊤ ⊙ 𝑧 • (𝑧 • ) ⊤ = 𝑨 • ⊙ 𝑧 • (𝑧 • ) ⊤ ⊙ z z⊤ = 𝐴 ⊙ 𝑧 • (𝑧 • ) ⊤ ⊙ z z⊤ .By degree pruning condition (1), we have(𝐴 * 𝟙) 𝑖 ⩽ log(1/𝜂)𝑅𝑑 • ⩽ 𝜎 d . for all 𝑖 ∈ [𝑛].Thus, (𝐴 * , 𝑧 * ) is a feasible solution to 𝒟(𝑌, 𝑧; 𝐴, 𝛾, 𝜎, d) with 𝛾 = 2𝜂, 𝜎 = 10 log(1/𝜂)𝑅 andd ⩾ 1 2 𝑑 • .In this section, we show that the following algorithm based on sum-of-squares proofs in Appendix E.1 obtains a robust approximation of 𝑑 • that is optimal up to logarithmic factors.Input: 𝜂-corrupted adjacency matrix 𝐴, corruption fraction 𝜂 and parameter 𝑅.1. Obtain coarse estimator d by applying Algorithm D.4 with 𝐴, 𝜂, 𝑅 as input.2. Obtain level-8 pseudo-expectation Ẽ by solving sum-of-squares relaxation of program 𝒟(𝑌, 𝑧; 𝐴, 𝛾, 𝜎, d) (defined in Eq. (E.3)) with 𝐴, 𝛾 = 2𝜂, 𝜎 = 10 log(1/𝜂)𝑅 and d.Theorem E.5 (Robust fine estimation for inhomogeneous random graphs). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑑 • := 𝑑(𝑄 • ). Suppose ∥𝑄 • ∥ ∞ ⩽ 𝑅𝑑 • /𝑛 for some 𝑅. Let 𝐴 be an 𝜂-corrupted adjacency matrix of a random graph 𝑮 • ∼ 𝔾(𝑛, 𝑄 • ). Suppose 𝜂 log(1/𝜂)𝑅 ⩽ 𝑐 for some constant that is small enough. With probability 1 -𝑛 -Ω(1) , Algorithm E.4 outputs an estimate d satisfyingd 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝜂 log(1/𝜂)𝑅 .Proof. By Theorem D.5, we have 12 𝑑 • ⩽ d ⩽ 3 2 𝑑 • . Let 𝛾 * = 2𝜂, by Lemma E.2 and Lemma E.3, it follows that 𝒟(𝑌, 𝑧; 𝐴, 𝛾, 𝜎, d) 8 𝑌,𝑧 |𝑑(𝑌) -𝑑(𝐴 * )| ⩽ 2(𝛾 + 𝛾 * )𝜎 d ⩽ 2 • 4𝜂 • 10 log(1/𝜂)𝑅 • 3 2 𝑑 • = 120𝜂 log(1/𝜂)𝑅𝑑 • .and,|𝑑(𝐴 * ) -𝑑 • | ⩽ 10 𝑑 • log 𝑛 𝑛 + 2𝜂 log(1/𝜂)𝑅𝑑 • .Therefore, we have 𝒟(𝑌, 𝑧; 𝐴, 𝛾, 𝜎, d)𝑂(1) 𝑌,𝑧 |𝑑(𝑌) -𝑑 • | ⩽ 200𝜂 log(1/𝜂)𝑅𝑑 • + 10 𝑑 • log 𝑛 𝑛 .Thus, the level-8 pseudo-expectation Ẽ satisfiesẼ[𝑑(𝑌)] -𝑑 • ⩽ 200𝜂 log(1/𝜂)𝑅𝑑 • + 10 𝑑 • log 𝑛 𝑛 , which implies that Ẽ[𝑑(𝑌)] 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝜂 log(1/𝜂)𝑅 .In this section, we present our algorithm and prove Theorem E.1. Our algorithm instantiates the sum-of-squares exponential mechanism in Appendix C.For an 𝑛-by-𝑛 symmetric matrix 𝐴 and a scalar 𝑑, we define the score of 𝑑 with regard to 𝐴 to be𝑠(𝑑; 𝐴) := min 0⩽𝛾⩽1 𝛾𝑛 s.t. ∃ level-8 pseudo-expectation Ẽ satisfying 𝒟(𝑌, 𝑧; 𝐴, 𝛾, 𝜎, d) ∪ {|𝑑(𝑌) -𝑑| ⩽ 𝛼𝑑} , (E.6)where 𝒟(𝑌, 𝑧; 𝐴, 𝛾, 𝜎, d) is the polynomial system defined in Eq. (E.3), d is a coarse estimate, and 𝜎, 𝛼 are fixed parameters whose values will be decided later. Note that (𝑌 = 𝑑 𝑛 𝟙𝟙 ⊤ , 𝑧 = 𝟘) is a solution to the polynomial system 𝒟(𝑌, 𝑧; 𝐴, 1, 𝜎, d) ∪ {|𝑑(𝑌) -𝑑| ⩽ 𝛼𝑑} for any 𝐴 ∈ ℝ 𝑛×𝑛 and any 𝑑 such that 0 ⩽ 𝑑 ⩽ min{𝜎 d, 𝑛}.To efficiently compute 𝑠(𝑑; 𝐴), we can use the scheme as described in Remark C.1. Exponential mechanism. Given a privacy parameter 𝜀 and an 𝑛-by-𝑛 symmetric matrix 𝐴, our private algorithm in Theorem E.1 is the exponential mechanism with score function Eq. (E.6) and range [0, min{𝜎 d, 𝑛}].Input: Graph 𝐴, coarse estimate d.Output: A sample from the distribution 𝜇 𝐴,𝜀 with support [0, min{𝜎 d, 𝑛}] and density d𝜇 𝐴,𝜀 (𝑑) ∝ exp(-𝜀 • 𝑠(𝑑; 𝐴)) , (E.7)where 𝑠(𝑑; 𝐴) is defined in Eq. (E.6).To efficiently sample from 𝜇 𝐴,𝜀 , we can use the scheme as described in Remark C.2.The following privacy guarantee of our algorithm is a direct corollary of Lemma C.4. Lemma E.7 (Privacy). Algorithm E.6 is 2𝜀-differentially node private.Utility. The utility guarantee of our algorithm is stated in the following lemma. Lemma E.8 (Utility). Let 𝑄 • be an 𝑛-by-𝑛 edge connection probability matrix and let 𝑑 • := 𝑑(𝑄 • ).Suppose ∥𝑄 • ∥ ∞ ⩽ 𝑅𝑑 • /𝑛 for some 𝑅. There is a sufficiently small constant 𝑐 such that the following holds. For any 𝜂 such that 𝜂 log(1/𝜂)𝑅 ⩽ 𝑐, given an 𝜂-corrupted inhomogeneous random graph 𝔾(𝑛, 𝑄 • ) and a coarse estimate d such that 0.5𝑑• ⩽ d ⩽ 2𝑑 • , Algorithm E.6 outputs an estimate d satisfying d 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝑅 log 2 𝑛 𝜀𝑛 + 𝜂 log(1/𝜂)𝑅 ,with probability 1 -𝑛 -Ω(1) .Before proving Lemma E.8, we need the following two lemmas. Now we are ready to prove Lemma E.8.Proof of Lemma E.8. Let 𝐴 be a realization of 𝜂-corrupted 𝔾(𝑛, 𝑄 • ). By Lemma E.3, the following event happens with probability at least 1 -𝑛 -Ω(1) . There exists a solution (𝑌 = 𝐴 * , 𝑧 = 𝑧 * ) to 𝒟(𝑌, 𝑧; 𝐴, 𝛾 * , 𝜎, d) with 𝛾 * = 2𝜂, 𝜎 = 10 log(1/𝜂)𝑅, and|𝑑(𝐴 * ) -𝑑 • | ⩽ 10 𝑑 • log(𝑛)/𝑛 + 2𝜂 log(1/𝜂)𝑅𝑑 • .For 𝜂 log(1/𝜂)𝑅 smaller than some constant, we have 0.9𝑑• ⩽ 𝑑(𝐴 * ) ⩽ 1.1𝑑 • . Note that 𝑑(𝐴 * ) ⩾ 0.9𝑑 • ⩾ 2 and 𝑑(𝐴 * ) ⩽ 1.1𝑑 • ⩽ 𝜎 d.Then it follows by setting 𝑡 = 10 and 𝛼 = 𝑛 -2 in Lemma E.9 that,ℙ 𝒅∼𝜇 𝐴,𝜀 (𝑠(𝒅; 𝐴) ⩽ 𝜏𝑛) ⩾ 1 -𝑛 -7where 𝜏 := 2𝜂 + 10 log(𝑛)/(𝜀𝑛) .Let d be a scalar such that 𝑠( d; 𝐴) ⩽ 𝜏𝑛. Then by Lemma E.10,𝑑(𝐴 * ) -2(2𝜂 + 𝜏)𝜎 d 1 + 𝛼 ⩽ d ⩽ 𝑑(𝐴 * ) + 2(2𝜂 + 𝜏)𝜎 d 1 -𝛼 .Plugging in everything, we haved 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝑅 log(1/𝜂) log 𝑛 𝜀𝑛 + 𝑅𝜂 log(1/𝜂) .As an 𝜂-corrupted graph is actually uncorrupted when 𝜂 < 1/𝑛, we can assume 𝜂 ⩾ 1/(2𝑛) without loss of generality. Therefore,d 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + 𝑅 log 2 𝑛 𝜀𝑛 + 𝑅𝜂 log(1/𝜂) .Proof of Theorem E.1. By Lemma E.7 and Lemma E.8.From Appendix D, we have a a constant multiplicative approximation of the expected average degree 𝑑 • . In this section, we show how to use this coarse estimate to obtain our fine estimate for Erdős-Rényi random graphs. Theorem F.1 (Fine estimation for Erdős-Rényi random graphs). There are constants 𝐶 1 , 𝐶 d 𝑑 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + log 2 𝑛 √ 𝑑 • 𝜀𝑛 + 𝜂 log 𝑛 √ 𝑑 •, with probability 1 -𝑛 -Ω(1) .We make a few remarks on Theorem F.1.• Our algorithm in Theorem F.1 is an sum-of-squares exponential mechanism. 𝑅, 𝜂, 𝜀 are parameters given as input to our algorithm.• We can get an estimate of 𝑝 • by taking p= d 𝑛-1 . Since p 𝑝 • = d 𝑑 • , it follows that p 𝑝 • -1 ⩽ 𝑂 log 𝑛 𝑑 • 𝑛 + log 2 𝑛 √ 𝑑 • 𝜀𝑛 + 𝜂 log 𝑛 √ 𝑑 • .• Combining Theorem D.1 and Theorem F.1 gives us an efficient, private, and robust edge density estimation algorithm for Erdős-Rényi random graphs whose utility guarantee is information-theoretically optimal up to a factor of log 𝑛.In Appendix F.1, we set up polynomial systems that our algorithm uses and prove useful sos inequalities. In Appendix F.2, we show that we can easily obtain a robust algorithm via sos proofs in Appendix F.1. Then in Appendix F.3, we describe our algorithm and prove Theorem F.1.For an adjacency matrix 𝐴 and nonnegative scalars 𝛾, 𝜎 and d, consider the following polynomial systems with indeterminates 𝑌 = (𝑌 𝑖𝑗 ) 𝑖,𝑗∈[𝑛] , 𝑧 = (𝑧 𝑖 ) 𝑖∈[𝑛] and coefficients that depend on 𝐴, 𝛾, 𝜎, 𝛿, d:𝒫 1 (𝑌, 𝑧; 𝛾) :=        𝑧 ⊙ 𝑧 = 𝑧, ⟨𝟙, 𝑧⟩ ⩾ (1 -𝛾)𝑛 0 ⩽ 𝑌 ⩽ 𝟙𝟙 ⊤ , 𝑌 = 𝑌 ⊤ 𝑌 ⊙ 𝑧𝑧 ⊤ = 𝐴 ⊙ 𝑧𝑧 ⊤        , (F.1) 𝒫 4 (𝑌; 𝜎, 𝛿, d) :=        |(𝑌𝟙) 𝑖 -𝑑(𝑌)| ⩽ 𝜎 d ∀𝑖 ∈ [𝑛] 𝑌 -𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ op ⩽ 𝛿 d        . (F.2)For convenience of notation, we will consider the following combined polynomial system in remaining of the section ℰ 4 𝑌,𝑧 𝑛 𝑑(𝑌) -𝑑(𝐴 * ) =⟨𝑌 -𝐴 * , 𝟙𝟙 ⊤ ⟩ =⟨𝑌 -𝐴 * , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ =⟨𝑌 - 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ + 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ - 𝑑(𝐴 * ) 𝑛 𝟙𝟙 ⊤ + 𝑑(𝐴 * ) 𝑛 𝟙𝟙 ⊤ -𝐴 * , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ =⟨𝑌 - 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + ⟨ 𝑑(𝐴 * ) 𝑛 𝟙𝟙 ⊤ -𝐴 * , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + ⟨ 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ - 𝑑(𝐴 * ) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ =⟨𝑌 - 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + ⟨ 𝑑(𝐴 * ) 𝑛 𝟙𝟙 ⊤ -𝐴 * , 𝟙𝟙 ⊤ -𝑤𝑤 ⊤ ⟩ + 𝑑(𝑌) -𝑑(𝐴 * ) 𝑛 - 1 𝑛 ⟨𝟙, 𝑤⟩ 2 .(F.4)By rearranging terms, we can get (1 -𝑤 𝑖 )𝜎 d (𝑧 𝑖 + 𝑧 * 𝑖 -1) ⩾ (1 -𝛾 -𝛾 * )𝑛 .⩽ 𝜎 d • 𝑖∈[𝑛] 2 -𝑧 𝑖 -𝑧 * 𝑖 ⩽ (𝛾 + 𝛾 * )𝑛𝜎 d . (F.7) From constraints 𝑌 -𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ op ⩽ 𝛿 d, ⟨𝟙, 𝑧⟩ ⩾ (1 -𝛾)𝑛 and ⟨𝟙, 𝑧 * ⟩ ⩾ (1 -𝛾 * )𝑛, we have ℰ 8 𝑌,𝑧 ⟨ 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ -𝑌, (𝟙 -𝑤)(𝟙 -𝑤) ⊤ ⟩ ⩽ 𝑌 - 𝑑(𝑌) 𝑛 𝟙𝟙 ⊤ op ∥𝟙 -𝑤∥ 2 2 ⩽ 𝛿 d • 𝑖∈[𝑛] (1 -𝑤 𝑖 ) 2 = 𝛿 d • 𝑖∈[𝑛] 1 -𝑤 𝑖 ⩽ 𝛿 d • 𝑖∈[𝑛]Since 𝛾 + 𝛾 * < 1, we have 1 -𝛾 -𝛾 * > 0, and, therefore,ℰ 8 𝑌,𝑧 ⟨𝟙, 𝑤⟩ 4 ⩾ (1 -𝛾 -𝛾 * ) 4 𝑛 4 .Plugging this into Eq. (F.11), we have ℰ 8 𝑌,∥𝐴 • 𝟙 -𝑑 • 𝟙∥ ∞ ⩽ √ 𝑑 • log 𝑛 . (F.13)Combining Eq. (F.12) and Eq. (F.13), we have By Lemma B.5, we know that, with probability 1 -𝑛 -Ω(1) , for some universal constant 𝐶,∥𝐴 • 𝟙 -𝑑(𝐴 • )𝟙∥ ∞ ⩽ ∥𝐴 • 𝟙 -𝑑 • 𝟙∥ ∞ + ∥𝑑 • 𝟙 -𝑑(𝐴 • )𝟙∥ ∞ ⩽ √ 𝑑 • log 𝑛 + 10 𝑑 • log 𝑛 𝑛 ⩽ 2 log 𝑛 √ 𝑑 • .𝐴 • - 𝑑 • 𝑛 𝟙𝟙 ⊤ op ⩽ 𝐶 𝑑 • log 𝑛 .(F.15)Combining Eq. (F.12) and Eq. (F.15), we have 𝐴 • - 𝑑(𝐴 • ) 𝑛 𝟙𝟙 ⊤ op ⩽ 𝐴 • - 𝑑(𝐴 • ) 𝑛 𝟙𝟙 ⊤ op + 𝑑(𝐴 • ) 𝑛 𝟙𝟙 ⊤ - 𝑑 • 𝑛 𝟙𝟙 ⊤ op ⩽ 𝐶 𝑑 • log 𝑛 + 10 𝑑 • log 𝑛 𝑛 ⩽ 2𝐶 𝑑 • log 𝑛 .In this section, we show that the following algorithm based on sum-of-squares proofs in Appendix F.1 obtains a robust approximation of 𝑑 • that is optimal up to logarithmic factors. Thus, the level-8 pseudo-expectation Ẽ satisfies⩽ 40𝜂 log 𝑛 √ 𝑑 • + 40𝐶𝜂 𝑑 • log 𝑛 (1 -2𝜂) 2 ⩽ 𝐶 ′ 𝜂 log 𝑛 √ 𝑑 • , for some constant 𝐶 ′ ,Ẽ[𝑑(𝑌)] -𝑑 • ⩽ 𝐶 ′ 𝜂 log 𝑛 √ 𝑑 • + 10 𝑑 • log 𝑛 𝑛 , which implies that Ẽ[𝑑(𝑌)] 𝑑 • -1 𝑂 log 𝑛 𝑑 • 𝑛 + 𝜂 log 𝑛 √ 𝑑 • .In this section, we present our algorithm and prove Theorem F.1. Our algorithm instantiates the sum-of-squares exponential mechanism in Appendix C. where 𝑠(𝑑; 𝐴) is defined in Eq. (F.17).To efficiently sample from 𝜇 𝐴,𝜀 , we can use the scheme as described in Remark C.2.The following privacy guarantee of our algorithm is a direct corollary of Lemma C.4. Lemma F.7 (Privacy). Algorithm F.6 is 2𝜀-differentially node private.Utility. The utility guarantee of our algorithm is stated in the following lemma. In this section, we prove Theorem 1.5, Theorem 1.7, and Theorem 1.8.In this section, we prove Theorem 1.5.Theorem (Restatement of Theorem 1.5). Suppose there is an 𝜀-differentially node-private algorithm that, given an Erdős-Rényi random graph 𝔾(𝑛, 𝑝 • ), outputs an estimate p satisfying | p/𝑝 • -1| ⩽ 𝛼 with probability 1 -𝛽. Then we must have𝛼 ⩾ Ω log(1/𝛽) 𝜀𝑛 √ 𝑛𝑝 • .We leave the formal proof of Theorem 1.5 to the end of this section. Now we sketch the proof idea. One natural idea to prove this theorem is to construct a coupling 𝜔 of 𝔾(𝑛, 𝑝 • ) and 𝔾(𝑛, (1 -2𝛼)𝑝 • ) such that for (𝑮, 𝑮 ′ ) ∼ 𝜔, the typical distance between 𝑮 and 𝑮 ′ can be well controlled. However, such a coupling is tricky to construct directly, as the node degrees in an Erdős-Rényi random graph are not independent. 10For a directed graph G, we define its adjacency matrix Ã to be Ã(𝑖, 𝑗) := 𝟙{(𝑖, 𝑗) ∈ G}. The (node) distance between two 𝑛-node directed graphs G, G′ , denoted by dist( G, G′ ), is number of nonzero rows of Ã -Ã′ .• Sample an outdegree 𝒅 ∼ Bin(𝑛, 𝑝 • ).• Sample a uniformly random subset 𝑺 ⊆ [𝑛] of size 𝒅. For each 𝑗 ∈ 𝑺, add an edge from 𝑖 to 𝑗.Then it is easy to see there exists a coupling ω of G(𝑛, 𝑝 • ) and G(𝑛, 𝑝 ′ ) such that if ( G, G′ ) ∼ ω then dist( G, G′ ) ∼ Bin(𝑛, Δ) where Δ = TV(Bin(𝑛, 𝑝 • ), Bin(𝑛, 𝑝 ′ )) .We have the following bound on the total variation between binomial distributions (see e. Proof of Theorem 1.8. We will prove the lower bound by constructing a pair of distributions 𝒟 0 and 𝒟 1 such that the total variation distance between them is small, but the difference in edge density is significant. Then since 𝜀-differentially node-private algorithm needs to have similar distributions in the output, it could not succeed in accurately estimating the edge density accurately under both distributions.Let 𝜂 ∈ [0, 0.001). Let 𝑝 • ∈ [0, 1], and let 𝑄 • ∈ [0, 1] 𝑛×𝑛 be the matrix, in which all entries are 𝑝 • , except for the rows and columns corresponding to a set of 𝜂𝑛 nodes setting to be 0. Let 𝑄 be the matrix, in which all entries are 𝑝 • , except for the rows and columns corresponding to a set of 𝜂𝑛 nodes setting to be 𝑅𝑝 • .We construct the following pair of distributions 𝒟 0 and 𝒟 1 :• 𝒟 0 : The distribution of 𝑮 ∼ 𝔾(𝑄 • ).• 𝒟 1 : The distribution of 𝑮 ∼ 𝔾(𝑄).Let 𝑝 ′ = ∥𝑄 • ∥ 1 𝑛 2 and 𝑝 = ∥𝑄 ∥ 1 Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This is a theoretical paper that does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The authors conform, in every respect, with the NeurIPS Code of Ethics while writing this paper.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).1The (empirical) edge density of an 𝑛-node graph equals the number of edges divided by 𝑛(𝑛 -1)/2.2Borgs et al.[BCSZ18] proved a lower bound for a variant of Erdős-Rényi random graphs. However, it is not clear whether their proof technique can be easily extended to Erdős-Rényi random graphs.4Strictly speaking, the expected average degree of 𝔾(𝑛, 𝑝 • ) should be (𝑛 -1)𝑝 • . Here we call 𝑛𝑝 • the expected average degree just for notational convenience. In the end, (𝑛 -1)𝑝 • = (1 -1/𝑛) • 𝑛𝑝 • . 
 
 Appendix:  


Decision: This paper considers the problem of differentially private (DP) density estimation for Erdos-Renyi random graphs. The input is an Erdos-Renyi random graph, where each edge is present independently with probability an unknown $p^o$. The goal is to output an estimate to $p^o$. The DP requirement here is w.r.t. node adjacency level, i.e. two graphs are neighbors if they differ only on edges of a single node. The main contribution of this paper is to give a polynomial-time algorithm for this problem that is optimal (up to polylogarithmic factor); previously, only inefficient algorithm [Borgs et al., 2018] or efficient but non-optimal algorithm [Sealfon and Ullman, 2019] are known. In fact, the paper presents an algorithm even in the inhomogeneous case where the probabilities of all pairs may not be equal (but still not too different) and in the "robust" setting where up to some fraction of the nodes can be arbitrarily corrupted. Interestingly, the algorithm presented in this paper provides new results even without privacy constraint in the sparse and highly-corrupted regime. As for the techniques, the high-level algorithm follows those of [Hopkins et al., 2023] in using Sum-of-Square (SoS) relaxation together with exponential mechanism. The main novelty here is in giving a constant-degree SoS proof for identifying $p^o$ robustly.

Overall, this is a technically solid and well-written paper that tackles a fundamental problem and gives nearly tight bounds. The fact that the algorithm provides improvement even in the non-private setting suggests that the techniques can be useful even beyond the privacy context. Given this, we recommend acceptance (spotlight).

Reviews: review: paper_summary: paper_summary: The paper concerns the graph density estimation question for random Erdos-Renyi graphs. The optimal algorithm, without additional constraints, for this problem is to output the density of edges in the graph.

The paper considers a node-private robust flavor of the question, however:

1. The output is not supposed to reveal much information about any node. More precisely, for any node, the distribution on estimates the algorithm produces is not supposed to be significantly different whether it is included or not. (This task is much easier to achieve in the edge privacy model.)

2. The algorithm is supposed to be robust, i.e., if the edges involving a small number of vertices are arbitrarily edited, this should not throw the estimate off significantly. (This may require, for instance, disregarding some fraction of vertices that are significantly off.)

The paper gives a near optimal algorithm in this setting that runs in polynomial time and it establishes asymptotic bounds on the error achieved by the algorithm.

Additionally, the paper gives an extension of the result to non-homogeneous random graphs.
strength_weakness: strength_weakness: This is not directly a very practical problem, since Erdos-Renyi graphs do not appear frequently in natural contexts and even the generalization assumes that the selection of different edges is independent, which is not true for many models of real-world graphs.

The algorithm may be difficult to implement and run in practice due to the complexity of tools used, which include semidefinite programming.
questions: questions: Just to make sure, in the inhomogeneous setting, the algorithm has to know $Q^\circ$, right? Otherwise, it could be a zero-one matrix equal to the graph adjacency matrix. What guarantees can be given if $Q^\circ$ is unknown?
limitations: limitations: No limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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: limitations: Yes, adequately addressed.
paper_summary: paper_summary: This paper gives the first polynomial time DP algorithm for estimating edge density of random graphs (Erdos-Renyi and inhomogeneous). The authors also give information-theoretic lower bounds to show that the error achieved is optimal (up to log factors). The paper utilizes the recent results of Hopkins et al who gave a black box reduction from privacy to robustness via a sum-of-squares exponential mechanism to design their new algorithm. Their main new contribution is a sum-of-squares algorithm for estimating the edge density which they then use together with the Hopkins et al framework to get their final algorithm.
strength_weakness: strength_weakness: The techniques used heavily rely on the recent framework given by the Hopkins et al STOC paper. What is unclear to me is --- what were the challenges in designing the sum-of-squares algorithm for estimating the edge density? Since this algorithm is the main contribution of the paper in some sense, I would like to understand better if the design of the sum-of-squares algorithm itself was previously known and one only needed the Hopkins et al framework to obtain this result.
General comment about the paper --- you should define the quantity edge density formally somewhere since the whole paper hinges on the reader understanding what it is.
questions: questions: The results of this paper are very important and exciting. However, can you expand on the challenges in designing the sum-of-squares algorithm for estimating the edge density? I would like to be more convinced that this result is not simply piggybacking off on the Hopkins et al result. Thanks!
limitations: limitations: There was no explicit discussion regarding the limitations of this work in the main body.
paper_summary: paper_summary: The authors propose a robust and efficient (polynomial time) algorithm to estimate the edge density of Erdos-Renyi graph, which achieves optimal error up to logarithmic factors. The authors also design an optimal algorithm for inhomogenous graphs where edges are drawn iid from different Bern(p_i).
strength_weakness: strength_weakness: There is no obvious weakness with regard to the results and technical parts of the paper. The only minor weaknesses are the problem formulation.
1. Both the Erdos-Renyi graph and the inhomogeneous model assume edges are independently chosen. In real applications, graphs are often fixed, and edges may not be independent.
2. The algorithm only works for edge density estimation. There should be many other interesting graph statistics, even on the Erdos-Renyi graph.
questions: questions: 1. Is it possible to design algorithms when the entries of the connection probability matrix are not independent?
2. Do any algorithmic ideas translate to other graph statistics like the number of triangles and k-stars?
limitations: limitations: Limitations and negative social impact are adequately addressed.
paper_summary: paper_summary: This paper studies edge density estimation for Erdos-Renyi random graph under node-level differential privacy. They then show that their approach can actually be used to estimating edge density for inhomogeneous graphs. In particular, this paper proposes an efficient algorithm with optimal privacy cost $O(1/(\varepsilon n \sqrt{np}))$, which is negligible to the non-private error for any epsilon in a moderate regime. To achieve this, the main technical approach in this paper is to design a new sum-of-squares algorithm for robust edge density estimation, and then based on the reduction from privacy to robustness in Hopkins et al., this paper uses an exponential mechanism whose score function is based on the correspoinding the sum-of-squares program.

To design a robust algorithm for edge density estimation of ER random graphs, this paper established several polynomial constraints to ensure that a ER random graph will satisfy with high probability. The proof that if a graph meets these constraints, its average degree will remain close to $d$ is straightforward enough for the sum-of-squares proof system, extends the utility guarantee of the polynomial program to its semidefinite programming relaxation, resulting in a polynomial-time robust algorithm.
strength_weakness: strength_weakness: As far as I can see, the most relevant work is Chen et al. "Private graphon estimation via sum-of-squares", but it appears to me that this paper lacks discussion and comparison in [Chen et al.]. Please see "Questions" for details. I would be happy to raise my score if all my questions are adressed.
questions: questions: 1. Could you please elaborate on which part of your proof technique deviates from that in [Chen et al.]? Alternatively, are the proof techniques similar, while you are just addressing different problems in this paper?
2. There is also a theorem in [Chen et al.] for edge density estimation of stochastic block random graphs (Lemma 4.10), and it appears that their utility is better. Could you explain the fundamental obstacle between stochastic block random graphs and the more general inhomogeneous graphs that prevents the estimation for inhomogeneous graphs from achieving results as good as those for stochastic block random graphs? Would you mind adding more discussion about the results in [Chen et al.]?
limitations: limitations: This paper discusses several limitations.

Comments: title: Thanks for your response
comment: Thank you for your responses to my questions.
Thanks for addressing my questions. I am keeping my score.
Thank you for your response and in particular, replying to my question.
Thank you for the rebuttal.
Thanks for clarifying, I have updated my score.