Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Authors: Hongjie Chen
Jingqiu Ding
Yiding Hua
David Steurer
Venue: NeurIPS 2024 spotlight (2024)
Keywords: differential privacy
robustness
random graph
sum of squares
average-case complexity
Primary area: privacy
TL;DR: A private, robust and polynomial-time algorithm based on sum-of-squares hierarchy that achieves optimal error rate for edge density estimation of random graphs

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

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Hongjie Chen ETH Zürich
Jingqiu Ding ETH Zürich
Yiding Hua ETH Zürich
David Steurer ETH Zürich
Abstract
We give the first polynomial-time differentially node-private, and robust algorithm for estimating the edge density of Pédós-Rényí random graphs and their generalization, inhomogeneous random graphs. We further prove informattion-thooretiin lower bounds, showing that the enror rate our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates.
Two key ingredients our algorithm are (1) new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy robustness based sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).
1 Introduction
Privacy has nowadays become 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 be differentially private if the distribution of its output remains largely unchanged under the change of 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 data point; and node differential privacy [BBDS13, KNRS13] where each node along with its incident edges is regarded 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 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 n-node Erdós-Rényí random graph of which each edge is present with probability pd independently, output an estimate P of the edge density parameter p", subject to node differential privacy. We consider the error metric f/pp" - which can reflect the fact that, the task is more difficult for smaller p".
38th Conference Neural Information Processing Systems (NeurIPS 2024).

---

Without privacy requirement, the empirical edge density P achieves the information theoretically optimal error rate 10/p"- 1| & ((1/(Ny²)). The standard way to achieve e-differential node privacy is to add Laplace noise with standard deviation ((1((en)) to the empirical edge density p. This will incur an additional privacy cost of ((1/(emp") which dominates the non-private error ((1/(Nvp")) Surprisingly, Borgs et al. [BCSZ18] gave an algorithm with privacy cost only Ó(1/(En which negligible to the non- private error for any & > 1/ However, their algorithm 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 (np)") + + +1/(==??p") which is much greater than that of [BCSZ18] for E < 1/(y)p²). 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 Rényi random graphs. This leads us to the following question:
Is there polynomial-timet differentially node-private, and rate-optimal edge density estimation algorithm for Rénís random graphs?
We essentially settled this question in this paper. Specifically, we give polynomial-time and differentially node- code-private algorithm with privacy cost Ó(1/(en )n(")) Moreover, we show this error rate is optimal up to a angarithmicfactor by proving
wewpmmmttooo-thoreetii lower bound of 2 (E1 <np*)) )). Our algorithm actually works for the more general inhomogeneous random graphs [B]R07]. 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 [HLLL33], 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 CDd*24). In particular, 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 tools sum-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.
1.1 Results
To state our results formally, we need the following definitions.
Definition 1.1 (Node distance, neighboring graphs). Let n e N. The node distance between two n-node graphs G and G', denoted by dist(G, G'), is the minimum number of nodes in G that need to be rewired to obtain G'. Moreover, we say G and G' are neighboring graphs if dist(G, G') < 1.
Definition 1.2 (Node differential privacy). Let G be the set of graphs. A randomized algorithm A G - is e-differentially (node-)private if for every neighboring graphs G, G
and every < R, we have
([A E E & e" P[A(G')
Definition 1.3 (Node corruption model). Let n E N and n E |0, For an n-node graph G, we say an n-node graph G' is an n-corrupted version of G if dist(G, G') < mn.
Erdös-Rényi random graphs. We provide a polynomial-time differentially node-private and robust edge density estimation algorithm for Erdös-Rény random graphs.
'Te (empirical) edge density of n-node graph equals the number of edges divided by n(n - 1)/2.

---

lower Theorem 1.4 (Erdós-Rényi random graphs, combination of Theorem D.1 and Theorem F.1). There are constants C₁ C2, C3 such that the following holds. For any n, Ct C2 lo and pº > C3/n, n,, there exisls polynomial-timg time E- e-differentially node-private algorithm which, given an n-corrupted Erdōs Réndi random graph G(n, p²), outputs an estimate p satisfying
p p
Vog n 11 VV
log' n
1 g f1
En Env
vnp
with probubility 1 -Q(1),
The first term O( /l is the sampling error that necessary even without privacy or robustness. The second term (n)))(n))/( (n) (un))p") )) is the privacy cost of our algorithm, which matches the exponential-time algorithm in [BCSZ18]. The third term O(n log // vap²) is the robustness cost of our algorithm, which matches the information-theoreet bound (1/ Vmp?) in [AJK'S 22, Theorem 1.5] up to a log nt factor.
Moreover, we provide the following lower bound which shows that the privacy cost of our algorithm is optimal up to a log n factor.²
Theorem 1.5 (Privacy lower bound for Erdós-Rényi random graphs). Suppose there is an E-differentially node-prioate algorithm that, given an Erdōs-Rényi random graph G(n, p"), outputs an estimate p satisfying 1p/p" - & a with probability 1 B. Then we must have
a > Q log(1/B)
En Enyup
Inhomogeneous random graphs. Given an n-by--1 edge connection probability matrix Q", the inhomogeneous random graph model G(n, Qa) defines distribution over n-node graphs where each edge {i, is present with probability (Q");; independently.
We Weprovide polynomial-time, differentially node-private and robust density estimation algorithm for inhomogeneous random graphs.
Theorem 1.6 (Inhomogeneous random graphs, combination of Theorem D.1 and Theo- rem E. Let Q" be n-by-n edge connection probability matrix and let := Ei, Qi,/(n2 nn). Suppose 11 & Rp for some R. There is sufficiently small constant e such that the following holds. For any 17 such that n Rog(1/n)) c, there exists polymomial time e-differentially node- private algorithm which, given an n-corrppeed inhomogeneous random graph G(n, Qº), outputs an estimate p satisfying
p po
Vlogn
R Rlog n Rnllg(111)
< 0
"Vp
en
with probability 1- -Q1).
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 Ō(R/(en) + n/((2ndd)), while our algorithm only has privacy cost Ö(R((En)) To the best of our knowledge, even without privacy requirement and in the special case of Réndi random graphs, no previous algorithm can match our guarantees in the sparse regime. Specifically, when d' & log and n Q(1), our algorithm can provide a constant-facter approximation of d,, while the best previous robust algorithm [A]K*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.
BBorgs 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ény: Rényi random graphs.
3

---

Theorem 1.7 (Robustness lower bound for inhomogeneous random graphs). Suppose there is an algorithm satisfies the following guarantee for any symmettric matrix Q E [0, 1]2Xn Given an n-corrupted inhomogeneous random graph G(n, Q9), the algorithm outpuls an estimate P satisfying 1p/p" -1| & with probability at least 0.99, where pd Li, 22y -n). n). Then we must have a a Q(R)),, where R = maxi,) Qijlp".
Theorem 1.8 (Privacy lower bound for inhomogeneous random graphs). Suppose there is an e-diferrntially node-private algorithm satisfies the following guaranlee for any symmetric matrix Q [0, 1] Given an inhomogeneous random graph G(n, Qº), the algorithm outputs an estimate i satisfying 1p/p" 1 & a with probability 1 1 B, where pº Σi, Qi 2ij/(n² 2 - n). Then we must have
R Rlog(11B)
a 3
11
where R = maxi, Qij/p"
1.2 Techniques
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ényí random graphs to avoid a proliferation of notation. Specifically, given an 17-orrupted Ladós-Rééyi random graph G(n, d' /n), our goal is to output private estimate of d
Reduction from privacy to robustness. Hopkins et al. [HKMN233 and Asi et al. [AUZ23] independently discovered the following black-box reduction from privacy to robustness. Given a robust algorithm Arobust, one can directly obtain a private algorithm via applying the exponential mechanism [MT07] with the following score function,
score(d; == min
| Alobusi(AA) di < 1/poly(n)).
(1.1)
A'
where A the adjacency matrix of input graph and d is 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 typical Erdós-Rénn Rénds random graph, the exponential mechanism will with high probability output à of score ((log())ee) e)) Then we can argue that such a à is close to d using the robustness of Arobust. 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/(en )d)).
However, directly plugging in the robust algorithm in [AJK 22] will lead to exponential- time algorithm, as single evaluation of the score function requires enumerating all n-node graphs. To obtain polynomial-tine algorithm, we develop a new robust algorithu via the sum-of-squares method.3
Robust algorithm via sum-of-squares. The sum-of-squares method uses convex program- ming (in particular, semidefinite programming) to solve polynomial programming. It is very powerful tool for designing polynomial-timg robust estimators (see [RSS18]). To obtain robust algorithm via sum-of-squares, we first identify a set of polynomial constraints that a typical (uncorrupted) Erdós-Rényi 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.
*nn 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 Ij 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 d', even when 7j fraction of nodes in the input graph are arbitrarily corrupted. Importantly, the proof is simple enough that 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 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 private algorithm. More specifically, we apply the exponential mechanism with the sum-of- squares relaxation of the score function in Eq. (1.1). In this way, we obtain private algorithm that is also robust to adversarial corruptions.
1.3 Notation
We introduce some notation used throughout this paper. We write f & g to denote the inequality f < C. g for some absolute constant C 0. We write O(f) and (2f) to denote quantities f- and f. satisfying f- x and s fi respectively, We use boldface to denote X,Y, Let and denote the all-one and all-zero vector respectively, of which the size will be clear from the context. We use graph when there is no ambiguity. For an n-by-n matrix M, we use d(M) to denote its average row row/coling cow/column& sum, i.e., d(M) = Σi, Mjj/n. For any matrices (or vectors) M, of the same shape, we use M N to denote the element-wise product (aka Hadamard product) of M and N.
random variables, e.g., e,g,,X, Y, Z. For matrix M, we use || for the spectral norm of M.
and its adjacency matrix = A(G) interchangeably
1.4 Organization
The rest of the paper is organized follows. In Section 2, we give 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 general sum-of- squares 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 full proof of its guarantees (Theorem E.1). In Appendix F, we present our fine estimation algorithm for Firdós-Rény random graphs and give 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 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 Trdós-Rénye random graph model G(n, po), estimating its edge density parameter pº is equivalent to estimating its expected average degree d' == np? 4 For the convenience of notation, we set our goal as estimating the expected average degree de throughout this section.
'Strictly speaking, the expected average degree of G(n, pD) should be (n - -1)p". Here we call np the expected average degree just for notational convenience. In the end, (I 1)p" 1/n) np".

---

2.1 General algorithm framework
Given an n-by-1 symmetric matrix A and a scalar y E (Y, be a polynomial system with indeterminates Y (Ysj),,jenn) and z = (Zi)ie[n) that encodes the node distance between Y and A:
202= (1,2) > > (1-1)) y)u T(Y, 11, Y
(2.1)
=
Let R(Y) be A polynomial system that encodes regularity conditions Erdós-Rényi random graphs. The key observation here is that, for any Y E (0, (),1) 1)"XM and (0, 1)" that satisfy constraints in (Y, z; A, R)U)(), Y is graph that behaves like Erdós-Rényi random graphs (in the sense of the regularity conditions) and is within node distance yn to A where they agree on (i E [m] : Zi 1}.
The key ingredient of our result is that, given proper regularity conditions R(Y), we can give degree-8 sum-of-squares proofs: for any Y that satisfies constraints in TTTTYY TYY, z; A, y) U R(Y), the average degree of Y is close to the expected average degree d even when the input graph A is y-corrupted Erdós-Rényi random graph G(n, dn/n.. As a result of the sum- of-squares troofs-t--algorithms framework (see Theorem A.6), can get efficient and robust estimator É [[)(,,, where É is a pseudo-expectation obtained by solving level-8 sum-of-squares relaxation of 7f ZY, Y) R(Y).
Based on the above identifiability proof for robust estimation, we design private and robust algorithm by applying the exponential mechanism with the following score function:
sos-score(d:A)
min yn s.t. 3 level-8 pseudo-expectation È satisfying 06y51
(2.2)
T(Y,z;A,y) U R(Y) U {Id(Y) d < 1/poly(n)).
Similar to Eq. (1.1), it is easy to observe this exponential mechanism is private. Lemma 2.1 (Privacy). Consider the distribution μA,x with support [0,n] and density
(d), exp(-e- sos-score(d;
(2.3)
where sos-score(d;A) is defined in Eg. (2.2), A sample from PA,e is 2e-differnntialy private.
Proof. Since the node distance between neighboring graphs is at most 1, the sensitivity of the following score function is bounded by 1:
score(d; == min yn s.t. ((,, 2X,) U R(Y) u {Id(Y) d) 1/poly(n)) is feasible. 0
One can show that such sensitivity bound is inherited by its sum-of-squares relaxation sos-score as defined in Eq. (2.2). By standard ennsitvvit-tt--prvaay argument (see e-g. [DR14, Theorem 3,10)), the exponential mechanism is 2e-differentially private.
To analyze the utility of the private algorithm, we use the robustness of the score function. Assume the input graph is uncorrupted for simplicity. For a typical Médos-Rényi random graph A G(n, d d'/n), we have sos-score(d" A²) 0. By standard volume argument (see e.g. [DR14, Theorem 3.11]), the exponential mechanism with high probability outputs a scalar d satisfying sos-score(d. dd; Ao) s log(n)/e. e. By the definition of our score function in Eq. (2.2), this implies that there exists a level-8 pssuud-diittrbuute with y log(n)/(En). The utility then follows from the above identifibility proof for robust estimation.
satisfying TY,, z;A", y) U R(Y)
"To efficiently implement this exponential mechanism, note that the score function Eq. (2.2) can be evaluated in polynomial time by combining binary search and semidefinite programming. By discretizing [0, n| step size 1/poly(n), one can sample from the distribution Eq. (2.3) with polynomial number of queries to the score function. For more detailed discussions, see Remark C.1 and Remark C.2.

---

2.2 Coarse estimation
In this part, we describe a private and robust algorithm that can estimate the expected average degree d' within constant approximation ratio.
Theorem 2.2 (Coarse estimation algorithm, informal restatement of Theorem D.1). For n smaller than some constant, there is a polynomial-time e-differentially node-private algoritim which, given an n-cornupted Erdös-Rémg Rényi random graph G(n, d /n)), outputs an estimate à such that - dd & 0.5d".
We give a proof sketch of Theorem 2.2 the end of this subsection. The formal theorem and proofs are deferred to Appendix D.
Identifiability proof for robust estimation. We first give polynomial system that can identify the expected average degree d' up to constant factors, even when f--fraction of nodes are corrupted. Consider the following regularity condition on degrees:
R(Y)= = (0)1) & 2lgg(1/n) d(Y), Vi [n]]
(2.4)
The following lemma shows that vrdōs-Rényi random graphs satisfy TY,, U R(Y) with high probability.
Lemma 2.3 (Feasibility). Let A G(n, d' /n) and let be an n-corrupted version of A With high probability, there exists a graph Y that satisfies the constraints in (Y, U RYY).
Proof sketch. For d' >> log(n), the maximum degree of A is of order O(d)). Therefore, the uncorrupted graph A satisfies the constraints. For de < log n, using concentration properties of random graphs, we can show that the number of high degree nodes is bounded by nn. A feasible graph can then be obtained from the uncorrupted graph A by trimming these highest degree nodes.
Next, we show that these polynomial constraints give an identifiability proof for the expected average degree d'.
Lemma 2.4 (Identifiability). Let A -Gn, d /n) and let A be an n-corrupted version of A a For 1 smaller than some constant and y & OTT), with high probubility there is a degree-8 sum-of-squares proof that, if Y satisfies T TYY, y) U R(Y), then Id(Y) d 0.001d
Proof sketch. We first assume that d' > log(n), for which the proof is simpler. By the degree- bound constraint R(Y), we have [d( (10)-((6 d(A)) ] < 2 log(1/n)) (d(Y) d') distt(y A²). Using the constraints Y O zz = A @ zz and (1,z) > (1 y)n, we have dist(Y, A) & yn. Since dist(A, & mn, by triangle inequality, we have dist(Y, A²) (y + r)m. Therefore, we have [d(Y) - d(A9) < 0.0001 when y, are at most some small constants. Finally, by random graph concentration, we have ld d(A") & old)) with high probability. Therefore, we have [d(Y) - d(A') < 0.001d
To deal with the sparse regime where d' & log we need to truncate the nodes of A with degree Q(oo((//)) 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 Id(Y) d(A") < 0.001d'.
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 pseudo- expectation satisfying T (Y, 2; A, A,2n) U RR()) R(Y) given in Eq. (2.4) and outputs B[d(()). By Lemma 2.3, such pseudo-expectation exists with high probability. It follows from the sum-of-squares identifiability proof in Lemma 2.4 that [[]](()] - d'| & 0. 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.5 and give a proof sketch of Theorem 2.2.
Algorithm 2.5 (Private coarse estimation for Erdós-Rényi random graphs). Input: 1/-orrupted Erdós-Rényi random graph A.
Privacy parameter: E,
Output: A sample from the distribution MA,e with support [0, n1] and density
(d,,,(d)) & exp(- e sos-score(d;A))
(2.5)
where
sos-score(d;A):
min yn s.t. 3 level-8 pseudo-expectation E satisfying 06 2(Y,2;A,)) U R(Y) u {Id(Y) dl & 1/poly(n))
(2.6)
with R(Y) given in Eq. (2.4).
Proof sketch of Theorem 2.2. Privacy. By Lemma 2.1, Algorithm 2.5 is 2e-differentiall private.
Utility. For simplicity, we consider the case when there is corruption (i.e. 17 0). The analysis for the case when 1j > 0 is similar. Let A ~ G(n, /n). Then with high probability sos-score(d";
O. By standard volume argument, Algorithm 2.5 outputs a scalar that satisfies sos-score d; A9 s log(n)/E with high probability. By the definition of sos-score Eq. (2.6), this implies that there exists a level-8 pseudo-distribttion satisfying T(Y, U R(Y) U {ld(Y) d < 1/poly(1)} with S log(n)/(zn). When log(n) (En) most a small constant, follows from our sum-of-squares identifiability proof in Lemma 2.4 that, Algorithm 2.5 outputs constant-factor approximation of d with high probability.
2.3 Fine estimation
From Section 2.2, we know how to obtain constant-factor approximation of d 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.5d < à 2d" For r, smaller than some constant, there is polynomial-timg -imeeilll--eeeeeee e-differentially node-prioate algorithm which, given an n-corrupted Erdōs-Réde Rénds random graph G(n, d /n) and à, outputs an estimate à such that
à
<
d=
Vnd
Vn
Va
We give proof sketch of Theorem 2.6 at the end of this section. The formal theorem and proofs are deferred to Appendix
Identifiability proof for robust estimation. We first give polynomial system which can identify the expected average degree d' with optimal error rate, when provided with coarse estimate d. Consider the following regularity conditions on degrees and eigenvalues:
(YY)); - -d() & Vālogn, Vi [n]
R(Y= = Y 10-40)0- 4(0) 11T
(2.7)
Vàlogn
op
Lemma 2.7 (Feasibility). Let A G(n, d d and let A be corrupted version of A Suppose d' / & à & 2d". Then with high probability, there exists graph Y that satisfies the constraints in AY, UR(Y)
Proof. By Chernoff bound, with high probability, the degree of each node in A deviates from d' by at most O(Vi logn). By the concentration of the spectral norm of random

---

log Hence, T(Y,;; U R(Y) is satisfied by Y A and = z" where z" is the indicator vector for uncorrupted nodes.
matrices [BvH16], with high probability, have ||,4 - 11 llop
diA")
Next we give sum-of-squares identifiability proof for expected average degree estimation with optimal accuracy.
Lemma 2.8 (Identifiabilitty) Let A G(n, d² /n) and let A be an n--orruupted version of A". Suppose d2/2 & à & 2d" For smallerr than some constant and y & O(n), with high probability there is a degree-8 sun-of-squares proof that, Y satisfies TY,, 2; A, 11) URY),, then
d(Y) do
=0
1
1
Vnd
Vd
Proof sketch. Let Y1, Y/ be two graphs satisfying the regularity condition R(Y)) and R(Y) as described in Eq. (2.7), respectively. We give sum-of-squares proof that, dist(Y,, Y2) En and [ is at most some small constant, then (d(Y)) - d(Y2)) < (Vdlogn.
Let w E 1)" be the indicator vector for the shared induced subgraph between Y1 and Y2, Le Y1 ww Y/2 O ww.. When dist(Y, Y1, 12) & [n, we have (w, 1) (1 ()n. We have
((()) - d(V2))
=(v Y2, 11T)
=(Y Y2, 11 www
=(1 d(Y))
11 d(Yi) 11
d(Y2)
11 d(Y2)
01 Y2, 11 - ww T>
H1
11
H1
d(Y))
d d(Y2)
=(1
11 11 -ww") >
11 - Y2, 11 wow"
d(Y)) 11
a(12) 10T, 11 ww T)
+
n
n
By rearranging terms, we can get
(1,
(d({) -(Y2)) = (Y1 d(Yi)
d(Y22
11 11 ww
11T - 11 -ww
For the first term (Y1 d(Yi) 11 / 11 www ) have
d(Y)) 11 -ww = 2(Y d(Y))
11T 1(1 (1-=) d(Yr)
(Y
11 (1==-w-
π
n
(Y\1); - d(X)) < Vālog()) for all i [n], we have
From constraints
(Y1 d(Yi)) 11 1(1 )) = (Yi - d(x)), - w) & Ingln) Vā.
"1
From constraints
| (1--(K)
.10) 11
< ,oā, we have
lop
d(Y (Y1)
11 (1,(1=)(( T) < Y1
d(K)
11
||1 w112 (nVVlog(n),
lop
The same bounds also apply for the second term (Y2
406)
11T 11 [--T-w T) Since (1, w) >
Q(n), it follows that [d(Y) - d(Y2) & Ō(Cvā) < Ō(CV7²).
Since the original uncorrupted graph satisfies the regularity conditions, this gives the identifiability proof that (d(Y))d(())) d(A') & V(tv By random graph concentration, with high probability, we have Id d(A') & Ō( (n). The claim thus follows.

---

Robust algorithm via sum-of-squares. Consider the algorithm that finds a level-8 pseudo- expectation satisfying 7;, U ((Y)-Waa R(Y) given in Eq. (2.7)- and outputs B[d(Y), By Lemma 2.7, such pseudo-expectation E exists with high probability. It follows from the sum-of-squares identifiability proof in Lemma 2.8 that [E[d(Y)/dd 1I ((1/Vnd 11/ v//vd).. Moreover, the algorithm 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 proof sketch of Theorem 2.6.
Algorithm 2.9 (Private fine estimation for Erdós-Rényí random graphs).
Input: corrupted random graph A, e-differentially private coarse estimate à.
Privacy parameter: E.
Output: A sample from the distribution HA,e with support [0, n] and density
(d),:(d) exp(-E sos-score(d;A))
(2.8)
where sos-score(d:A) A) is defined as
sos-score(d;A) min yn s.t. level-8 pseudo-expectation EE satisfying 0sy 2( U R(Y) u {Id(Y) dl < 1/poly(n)),
(2.9)
with R(Y) given in Eq. (2.7).
Proof sketch of Theorem 2.6. Privacy. By Lemma 2.1, Algorithm 2.9 is 2e-differentially private. Utility. For simplicity, we consider the case when there is no corruption (i.e. rj = 0). The analysis for the case when 1) > 0 is similar. Let A G(n, d /n).. Then with high probability sos-score(d") A") = 0. By a standard volume argument, Algorithm 2.9 outputs a scalar d that satisfies sos-score(dd) d; A*) log(n)/e with high probability. By the definition of sos-score in Eq. (2.9), this implies that with high probability there exists level-8 pseudo-distributin satisfying (Y,,;;A y) U R(Y) with log(n)/(En). Taking N = log(n)/ (en) in Lemma 2.8, it follows that Algorithm 2.9 outputs an estimate à such that - < O(1/Vnd=+1/en/) with high probability.
Lower bound
We sketch the proof of Theorem 1.5. Let E [0, and d = (1 - a)d'. We can construct coupling a between the distributions G(n, dd/)) and G(n, d' /ı)) with the following property. For (G, G') probability, By the definition of differential privacy, when Van & 1/polylog(n), the output of an e-differentially private algorithm are indistinguishable under G(n, d/n) and G(n, d d/). Therefore, by setting a Vd)),, we conclude that no e-differentially private algorithm can achieve error rate better than Ó(1/en This provides matching lower bound for our private edge density estimation algorithm.
we have dist(G, G') bounded by Ō(anvd') with overwhelmingly high
Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 815464). We thank the anonymous reviewers for constructive feedback.
10

---

References
[A]06]
José A Adell and Pedro Jodrá, Exacf kolmogorov and total variation distances between some familiar discrete distributions, Journal of Inequalities and Applications 2006 (2006), 1-8. 38
[2] Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, and Huanyu Zhang, Robust estimation for random graphs, Conference on Learning Theory, PMLR, 2022, pp. 130-166. 3, 4, 20,37 37
[3KT*23] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang, Privately estimating gaussian: Efficient, robust, and optimal, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 483-496.
2
[AUZ23] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou, From robustness to prioacy and back, International Conference on Machine Learning, PMLR, 2023, pp. 1121- 1146. 2,4
[BBDS13]
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet, Differentially private data analysis of social networks via restricted sensifioity, Proceedings of the 4th conference on Innovations in Theoretical Computer Science, 2013, pp. 87-96.
[BC17]
Christian Borgs and Jennifer Chayes, Graphons: A nonparametric method to model, estimate, and design algorithms for massive networks, Proceedings of the 2017 ACM Conference on Economics and Computation, 2017, pp. 665 672. 2
[BCS15]
Christian Borgs, Jennifer T. Chayes, and Adam Smith, Private graphon estimation for sparse graphs, 2015.
[BCSZ18]
Christian Jonnsfen Chayes, Adam Smith, and Ilias Zadik, Revealing network struclure, confidentially: Improved rates for node-private graphon estimation, 2018.
3
[BJR07]
Béla Bollobás, Svante Janson, and Oliver Riordan, The phase transition in inhomo- geneous random graphs, Random Structures & Algorithms 31 (2007), no. 1, 3-122.
2
[BS14]
Boaz Barak and David Steurer, Sum-of-qqurres proofs and the quest toward optimal algorithms, Proceedings of the International Congress of Mathematicians- Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, 2014, pp. 509-533. MR 3727623 14
[BS16]
Proofs, beliefs, and algorithums through the lens of sum-of-squares, lecture notes, 2016. 14
[BvH16] Afonso S. Bandeira and Ramon van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries, Ann. Probab. 44 (2016), no. 4, 2479-280 2506. MR 3531673 9, 18
[CCAd*23] Hongjee Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel, Private estimation algorithms for stochastic block models and mixlure models, Advances in Neural Information Processing Systems 36 (2023), 68134-68183.
[4] Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer, Private graphon estimation via sum-of-squares, arXiv preprint ar arXiv:2403.12213 (2024). 1, 2, 3, 19
[DL09]
Cynthia Dwork and Jing Lei, Differential privacy and robust statistics, Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, Pp. 371-380. 2
[DMNS06]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith, Calibrating noise to sensitivity in privale dala analysis, Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, Springer, 2006, pp. 265-284. 1
11

---

[DR14]
Cynthia Dwork and Aaron Roth, The algorithmic foundations of differential prioucy, Foundations and Trendsø in Theoretical Computer Science (2014), no. 3 3-4, 211-407. 5, 6
[DSSU17]
Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman, Exposed! survey of attacks on private data, Annual Review of Statistics and Its Application 4 (2017), 61-84.
[9KP*19] Noah Fleming, Pravesh Kothari, Toniann Pitassi, et al., Semialgebraic proofs and efficient algorithm design, Foundations and Trends@ in Theoretical Computer Science 14 (2019), no. 1-2, 1-221.
[GH22] Kristian Georgiev and Samuel Hopkins, Privacy induces robustness: Information- computation gaps and sparse mean estimation, Advances Neural Information Processing Systems (S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds.), vol. 35, Curran Associates, Inc., 2022, Pp. 6829-6842..
[HKM22]
Samuel B Hopkins, Gautam Kamath, and Mahbod Majid, Efficient mean estimation with pure differential prioacy via sum--of-squares exponential mechanism, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1406-1117. 2,5
[HMMN23]
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan, Robustness implies privacy in statistical estimation, Proceedings of the 55th Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC 2023, Association for Computing Machinery, 2023, p- 497-506. 2, 4, 18
[HL18] Samuel B. Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2018, Association for Computing Machinery, 2018, p. 1021-1034. 14
[HLL83]
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt, Stochastic blockmodels: First steps, Social networks 5 (1983), no. 2, 109-137. 2
[Hop20]
Samuel B Hopkins, Mean estimation with sub-gaussian rates in polynomial time,
The Annals of Statistics 48 (2020), no. 2, 1193-1213. 14
[HRH02]
Peter D Hoff, Adrian E Raftery, and Mark S Handcock, Latent space approaches to social network analysis, Journal of the american Statistical association 97 (2002), no. 460, 1090-1098. 2
[KM222]
Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker, Privale robust esti- mation by stabilizing convex relaxations, Proceedings of Thirty Fifth Conference on Learning Theory (Po-Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Research, vol. 178, PMLR, 02-05 Jul 2022, pp. 723-777. 2
[NNRS13]
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith, Analyzing graphs with node differential privacy, Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, Springer, 2013, pp. 457-476.
[RRSY11] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev, Privale analysis of graph structure, Proceedings of the VLDB Endowment 4 (2011), no. 11, 1146-1157.
[KSS18]
Pravesh K Kothari, Jacob Steinhardt, and David Steurer, Robust moment estimation and improved clustering via sum of squares, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1035-1046. 14
[LKKO21]
Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh, Robust and differen- tially private mean estimation, Advances in neural information processing systems 34 (2021), 3887-3901.
[LKO22]
Xiyang Liu, Weihao Kong, and Sewoong Oh, Differential privacy and robust statis- tics in high dimensions, Conference on Learning Theory, PMLRR, 2022, pp. 1167- 1246. 2
12

---

[MT07]
Frank McSherry and Kunal Talwar, Mechanism design via differential privacy, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), IEEE, 2007, pp. 94-103. 2, 4
[NRS07]
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith, Smooth sensitivity and sampling in pricale data analysis, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 75-84. 1
[NS09]
Arvind Narayanan and Vitaly Shmatikov, De-anonymizing social networks, 2009
30th IEEE symposium on security and privacy, IEÉE, 2009, pp. 173-187. 1
[PS17]
Aaron Potechin and David Steurer, Exac! tensor completion with sum-of-squares, Proceedings of the 2017 Conference on Learning Theory, 2017. 14
[RSS18]
Prasad Raghavendra, Tselil Schramm, and David Steurer, High dimensionnl estimation via sum-of-squares proofs, Proceedings of the International Congress of
Mathematicians: Rio de Janeiro 2018, World Scientific, 2018, pp. 3389-3423, 2,
14
[SU19]
Adam Sealfon and Jonathan Ullman, Efficiently estimating prdos-renyi graphs with node differential privacy, Advances in Neural Information Processing Systems 32 (2019). 2,
13

---

A Sum-of-squares background
A.1 Sum-of-squares hierarchy
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 pseudo- distributions, sum-of-squares proofs, and sum-of-squares algorithms.
Pseudo-distribution. We can represent a finitely supported probability distribution over R" by its probability mass function μ: R" - R such that and Exesupp(u) (u(x) = 1. We define npeudo-distribtionn as generalizations of such probability mass distributions by relaxing the constraint > to only require that passes certain low-degree non-negativity tests.
Definition A.1 (Pseudo-distributiion) A level-E pseudo-distributin μ over R" is finitely supported function μ R² - IR such that Exesuppir) p(x) 1 and Exesupp(H) [xx)f(x)²
for every polynomial f of degree at most 8/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 pseudo-distribution μ over R",, define the pseudo-expectation of function f R" - IR by
B Σ
fxx)
(A.1)
xCSupp(μ)
The following definition formalizes what it means for pseudo-distribution to satisfy system of polynomial constraints.
Definition A.3 (Constrained pseudo-distributionns)) Let R" - R be a level-f pseudo- distribution over R" Let A = (fi > 0,... fm > 0} be system of polynomial constraints. say that μ satisfies A at level r, denoted by μ l- A, if for every multiset $ S [m]] and every sum-of-squares polynomial h such that deg(h) + Eies max(deg(f),r)
k
f 0.
(A.2)
icS
We say μ satisfies A and write μ -== A (without further specifying the degree) if μ _/ A.
We remark that if is an actual finitely supported probability distribution, then we have - A if and only if μ is supported on solutions to म.
Sum-of-squares proof. We introduce sum-of-squares proofs as the dual objects of pseudo- distributions, which can be used to reason about properties of seeudo-distribution.. We say polynomial p is sum-of-squares polynomial if there exist polynomials (qi) such that == -
Definition A.4 (Sum-of-squares proof). A sum-of-squares proof that system of polynomial constraints A = (fi > O,..., fm > 0) implies q > 0 consists of sum-of-squares polynomials (ps)se(m) such that
9 Σ
ps fi iES
multiset SL [m]
If such a proof exists, we say that A (sos-)proces > 0 within degree f, denoted by A 1r > 0.
In order to clarify the variables quantified by the proof, we often write A(x) 1 q(x) > 0.
'eere follow the convention that lics fi 1 for S 0.
14

---

We say that the system A sos-refuted within degree A - 0. Otherwise, say that the system is sos-consistent up to degree f, which also means that there exists level-f pseudo-distribttion 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 y be a pseudo-distre distribbiirrr,,,, and let A, be systems of polynomial constraints.
Suppose there exists a sum-of-squares proof A 1,r B. If i F A, then μ 7-7''r B.
Sum-of-squares algorithm. Given a system of polynomial constraints, the sum-of-squares algorithm searches through the space of pseudo-ddstriiutions that satisfy this polynomial system by semidefinite programming.
Since semidefinite programing can only be solved approximately, distributions that approximately satisfy a given polynomial system. We say that a level-f crcudo-distribution approximately satisfies a polynomial system, if the inequalities in Eq. (A.2)
only find pseudo-
are satisfied up to an additive error of 2-"", || Ilssllfill. where ||-Il denotes the Euclidean norm of the coefficients of polynomial in the monomial basis.
Theorem A.6 (Sum-of-squares algorithm). There exists an (ı + m mn)000time algorithm that, given any explicitly bounded and salisfiable system? A of m polynomial constraints in variables, outputs a level-f pseudo-distributio that satisfies A approximately.
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.
A.2 Useful sum-of-squares lemmas
Lemma A.8.
(x2 x) H/2 0
Proof. The first inequality is trivial due to (x² = it follows that
x}
1 x = x² > For the second inequality,
x2
x 1
(x2 =x²=x) x
2 2
2
Rearranging the terms, we get
(x2 [==x)
Lemma A.9.
1. 1- 1 (x² x, x2
& x (1 y).
Proof. By Lemma A.8, it follows that
{x2= - x, x P2 0 x, 1.
Therefore, we have
{x² = x, =y
| k.y.
(1-y)( (1-y)(1-x)
"The choice of norm is not important here because the factor 2 n swamps the effects of choosing another norm.
'A system of polynomial constraints explicitly bounded contains a constraint of the form || M.
HHere assume that the bit complexity of the constraints in A is (ır 0(),
15

---

x.y x > xxy
4
x.y
2 x - y > 1-xy.
Lemma A.10. Given constant C, we have
{-C
Proof.
{-c <
1/2 (C + x)
2 C² x2 00
2 x2
Lemma A.11. Given constant C, we have
(x² & 2 1
C
Proof. For the first inequality, we have
x²
C
C
C
(x2 < c2 2 x
>
-C.
2C
2
2C
2
For the second inequality, we have
2
C²
C 2
(x² < c2)
2
x
<
2C
+
2
<
2C
=C
B
Concentration inequalities
Lemma B.1 (Average degree concentration). Let Q" be an n-by-n edge connection probability mairix and let d := d(Q"). ). Let G(n, Qº). Then for any ó (0,1),
nd
P((((A) d' od < 2 2xxp
Proof. Let μr = E EEiej Aij = Eisj Pij.
Using Chernoff bound, for E (0, 1),
> 6μ < 2exp (
8211
P
Σ [<]
Aij
3
82nd
P((((A) d81
8d))
exp
Lemma B.2 (Degree distribution). Let Q be an n n-by-n edge connection probability malrix. Let be parameter such that d > and ||Q I| & d/n. Then for every t [2e2 log n), inhomogeneous random graph G(n, Q²) has at least et in nodes with degree at least td with probability at most exp(-te 'nd/4).
16

---

Proof. Let my denote the number of nodes with degree at least k in G(n, Q²). Then for every y [0, 1},
yn²
d
ynid/2
P(ma 2 yn)
1/1
yntd/2
/2
yntd/2
2e
f
ld
1
)
e
exp
-
log
log
2
2
y
Plugging = e gives
(d
P(maa > nn & exp -te -te
log
1-1-1//))
1/t)
2
For Roe2,logro n| and d > 5,
P(ma > e nn) & exp -
2 4 < expl(tt
dd
5
Lemma B.3 (Degree pruning). Let Qa be an n-by-n edge connection probability matrix. Let be parameler such that and || & d/n. Then with probability at least 1 - n21-/44, inhomogeneous graph G(n, Q²) has the following property. For all [2e², log, n],, the number of edges incident to nodes with degree at least td is at most 2t;-
Proof. Let my denote the number of nodes with degree at least k in G(n, Q?). By Lemma B.2, for any t [2e², log n and 5,
P(mm i en'n) & expp(tte'nd/4) & nn-44
Applying union bound, the event that my & = for any integer [2e²d, (log )d] happens with probability at least 1 11-4/4 We condition our following analysis on this event.
aix E [2e², log The number of edges incident to nodes with degree least to is most
e²
Σ 2a+i+1 1)d e (1+1) nd Σ (i 1)e - 10
nde e- (e 1)2
e
21e 2id-'nd.
Lemma B.4 (Degree-truncated subgraph). Let Q be an n-by-n edge connection probability matrix and let d' d(Q²). Let d be parameter such that d > 5 and 11Q" & d/n. For E (0, 1), an inhomogeneous graph A ~ G(n, Qº) has the following property with probability at least n 1-d/4 exp(-8ndd /6). For every E [2e2, log n), A contains an n-node subgraph À of such that
(Ā1); & ld for any i [n];
8d 41e - d < d(A) & (1 + 5)d².
Proof. By Lemma B.1 and Lemma B.3, A ~ G(n, Qº) has the following two properties with probability at least - 1 1-4/4 exd(-=2d"/6))
Id(A) d' < 0d'.
For all f 22e² log n], the number of edges incident to nodes with degree at least td is at most 2te nd.
17

---

Consider graph A with the above two properties, Fix a e Ree",o..]. By removing at most nd edges from A, we can obtain a graph Á such that the maximum degree of A is at most td. Moreover,
d(A) d(A) 4te > (1 d)d d
d(A) & d(A) & (1 + d
Lemma B.5 (Spectral bound [BvH16]). Let A G(n, po) and suppose npo probability least 1 -o(),
5. Then with
- po(1 A - -dd) < < nnpooooo
C Sum-of-squares exponential mechanism
In this section, we present our sum-of-squares exponential mechanism and prove its properties in general setting that incorporates all special cases in Appendix D, Appendix E and Appendix F.
Setup. Let D c RN. Given an n-by-n symmetric matrix A, our goal is to output an element from D privately. We say two symmetric matrices are neighboring if they differ in most one row and one column. The utility of an element E D is quantified by score function defined follows.
Score function. For an n-by-n symmetric matrix A and a scalar y, consider the following polynomial system with indeterminates (Yij) (Zz)sefw) and coefficients that depend on A,
= (1,z) > (1 (1- y)n QYY
(1, Yozz Y =
(C.1)
For an element d E DD let Q2(Y; be polynomial system with coefficients depending on (and independent of A, y). Then for a matrix A and an element D, we define the score of d with regard to A to be
3 level-f pseudo-expectation È satisfying [Q,(Y U Q2(Y:
s(d; A) min yn s.t. 05
(C.2)
For A) to be well-defined, we assume that for every d e D there exists symmetric matrix A' E [0, 1]mX" such that (2(A";d) is true.
Remark C.1 (Score function computation). Observe that a level-f pseudo-expectation satisfy- ing AY; p) U Q2(Y:d) is also level-f pseudo-expectation satisfying Q A; y') U d) for any y' > Thus we can compute sdd; A) using binary search. Given a scalar y, checking if there exists level-( pseudo-expectation satisfying (Y, y) @z(Y:d) equivalent to checking if a semidefinite program of size n O10) is feasible. Since we only have efficient algorithms for semidefinite programming up to given precision, we can only efficiently search for pseudo-distributions that approximately satisfy a given polynomial system. In spite of this, as long as the bit complexity of the coefficients in our sum-of-squares proof are polynomially bounded, the analysis of our algorithm based on sum-of-squares proofs will still work due to our discussion in Remark A.7. We refer interested readers to [HKMN23] for a formal (and quite technical) treatment of approximate psendo-expectations.
Exponential mechanism. Given n-by-n symmetric matrix A, exponential mechanism with privacy parameter & outputs sample from the distribution μΛ that is supported on D and has density
(d.,c(d) exp(-e s(d;A))
(C.3)
18

---

Remark C.2 (Sampling). To efficiently sample from HA,e, we can use the following straightforward discretization scheme. More specifically, given discretization param- eter 6, we output an element d E {0, 0, 2ö...... ... I (n/8j with probability proportional to exp(-E sos-score(d; A)). As the error introduced by discretization is at most ó and our target estimation error is ((1/n), we can choose 5 = 1/n and the discretization error is then negligible. Moreover, our algorithm requires at most n² evaluations of score functions.
The following lemma shows that the sensitivity of score function s(d; is at most 1.
Properties.
Lemma C.3 (Sensitivity bound). For any d E D and any two n n-by-n symmetric matrices A, A' that differ in most one row and one column, the score function defined in Eq. (C.2) satisfies
|s(d; A) s(d;A)) 1.
Proof. Without loss of generality, we assume that A and A' differ in the first row and column. Consider the linear functions (&)) where (1() = and ((()) = 2: for > 2. Then for every polynomial inequality q(Y, 2) > 0 in QY A; 1/n) U @2(Y;d),
QY y) U Q2(Y:d)
q(Y, {(2)) > 0.
degig)
The same argument also holds for polynomial equalities. Then by [CDd+24, Lemma 8.1], s(d; A') & s(d; A) + 1. Due to symmetry of A and A', we also have s(d; A) & s(d; Therefore, |s(d; A) - Add < 1.
The following privacy guarantee of our exponential mechanism is direct corollary of Lemma C.3. Lemma C.4 (Privacy). The exponential mechanism defined in Eq. (C.3) 2e-diferrentially node private.
Lemma C.5 (Volume of low-score points). Let A E R and > 0. Consider the distribution
uAe defined by Eq. (C.3). Suppose A", 2²) is solution to Q1(Y, 2; y²), Then for any t
> 0,
sdd:A) y tlg 12
vD) vol(G(A")
d-HA.
where G(A)) (d E D Q2(A":d) is true).
Proof. Note (Y = A', = 2²) is also a solution to Q,(Y, U Q2(Y; for any d such
that ( is true. Let G(A*) = {d E Q2(A"; is true). Thus s(d; & y'n for any E G(A'). For 1 > O,
llg 8
vol(2) - exlp))-exp(eey'n--lll vol(G(A')) -xp-))eexpppp)y"" vol(G((A))
vol(D) n²
P d d=Haa
s(d:A) y'n
D Coarse estimation
In this section, we describe our coarse estimation algorithm that achieves constant multi- plicative approximation of the expected average degree d².
Theorem D.1 (Coarse estimation for inhomogeneous random graphs). Let Qo be n-by-n edge connection probability matrix and let d' == d(Q²). Suppose 1 & Rdd n for some R. There conslants C1, C2, C3 such that the following holds. For any n, d such that 1) log(1/n)R e-differentially node private
Ct
> C2 log (n (n)R/P n, and do > Ca, there exists polynomial- algorithm which, gioen an n-corrupted inhomogeneous random graph G(n, Qº), outputs estimate à satisfying jā/d 1| & 0.5 with probability n 201)
We make a few remarks on Theorem D.1.
19

---

Our algorithm in Theorem D.1 is a sum-of-squares exponential mechanism. R, 17 are parameters given as inputs our algorithm.
à Since & 2. We can get constant estimate of pd by taking P n-I p zs, it follows that
| 11 < 0.5.
When Q = p"(1T Id), the inhomogeneous random graph G(n, Q*) is just the Erdós-Rényi random graph G(n, Thus, by setting n-1 in Theorem D.1, we directly obtain a coarse estimation result for Erdós-Rényi random graphs.
h
The utility guarantee of our algorithm holds in the constant-degree regime (i.e. d =(1)). To the best of our knowledge, even without privacy requirement and in the special case of Erdós-Rényí random graphs, no previous algorithm can match our guarantees in the constant-degree regime. Specifically, when d' < log and > (111, the robust algorithm in [A]K*22] can not provide constant-factor approximation of d'.
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.
D.1 Sum-of-squares
For an adjacency matrix A and two nonnegative scalars and o, consider the following polynomial systems with indeterminates Y (Vi)),jan)) (Zz)iein and coefficients that depend on A, 7.:
20 =0 (1,,)) > (1 y)n "<", =A =
y;
(D.1)
Pa(Y:o) = ((YT); od(Y)
(D.2)
Vi [n]
For convenience of notation, we will consider the following combined polynomial system in remaining of the section
CVy=:AA,,,)):=PP0..: U P2(Y;o).
(D.3)
Lemma D.2. (A",, a feasible solution to C(Y, 0) and 1- - -2yo -y-- 0, then
follows that
Y,2 8 - (1-2ya-2y'o)duu d(Y) < 1- 2yo 2y"d d(A'). C(Y,z;A,,,))
Proof. Let w = =z x", by constraint Yozz = A zz and A 2'(zz A 2'(2'), we have
Y2 Yown Y zz 0z((2')
2zzzT0z(()) ==0z'(z') 2zz
= =A'Oz(z)) ozz
A' ww
Applying this equality, it follows that
Y,z
C 4 n d(Y)= (Y,
(YY T) (Y, 11 ww""
20

---

= (A", (ww)) - - (1-
- -
For the first term, since A E [0, 1,, 2, E (0, and C - 0 < z < for i [x], we have
v 4 wm 2112222 & Al.
c
Therefore, it follows that
Y2 C 1 (A',wi) now" < (A", & n d(A').
(D.4)
For the second term, have
C [ (Y, 2(1 w)1T) (2,,(11 w))
Σ
2(1 wi) (Y1);
ic[m]
Σ
2(1 212,)- (Y1);
ic[m]
Σ [e[a]
2(1 2 (Y1); Σ 2(122) (Y1);, ie[n]
where the last inequality due to Lemma A.9. From constraints Eie(n] 27 & y'n,
Eie[n] 1 2; & yn and (Y1); & od(Y) for all E [n], it follows that
c Yz + (, -
2(1 z;) od(Y)+
Σ ic[n]
2(1 27) od((Y
ictrr
(D.5)
2ad(YY
Σ 1 zi + +ad(YY
Σ 1-21
[e[n]
2ynod(Y) 2y')nd(()).
For the third term, since C 2 Y2 Yij > 0 and C
Y.2
1 - w; > 0 for all i, [n], it follows that
2
Y= (Y, (1 w1 - w) 00.
(D.6)
Combining Eq. (D.4), Eq. (D.5) and Eq. (D.6), we can get
C 8 d(Y) d(A") + 2ynad(Y) 2od)
Y,z d(Y) <
d(A')
ss
2y 2y
Swapping the roll of A and Y, we can use the same proof to get
C Y2
g d(A') < n ((dd()) + 2ynod(A') nod(AA)
Y2
(1 - 2 o)d(A") d(Y).
8
This completes the proof.
Lemma D.3. Let Q" be an n-by-n edge connection probability matrix and d := d(Q²). Suppose 110 & Rd /n for R E R. Let A be an n-corrupted adjacency matrix of a random graph Go
G(n, Q³). Suppose n7 1log(11/)) ( & C1 for some conslant C1 that is small enough. With probability 1 -01), there exists A and z" such that
1. Id(A") d < 0.1d
2. (A", ) is feasible solution to
d) with y 2n and llo((1/))
21

---

Proof. Let A be the adjacency matrix of G and z" E {0, denote the set of uncorrupted nodes (z; if and only if node is uncorrupted).
By Lemma B.2 and Lemma B.3, we know that, with probability 1 n --00) there exists degree-pruned adjacency matrix Á such that
1. || < ldd
2. At most nnn nodes are pruned.
3. At most 2n l Rdd edges are pruned.
Let 10, denote the set of unpruned nodes (z, 1 if and only if node i is not pruned).
We will show that A = and z' z" @ 2 satisfies the lemma.
Guarantee 1. By Lemma B.1, we know that, with probability - 1 -Q1)
do log
[d(A') - - < 10
(D.7)
n
From degree pruning guarantee (3), we have that [d(Á) d(A') & 2n
(D.8)
Combining Eq. (D.7) and Eq. (D.8), for some constant C1 that is small enough, we have
Id(A) d' < (d(A) d(A") Id(A') d'1
d log
< 10
2n log
Rd
n
(D.9)
log n
< 10
do + dc
< 0.1d
Guarantee It is easy to check that z' Oz 20, 11T and A' = (A')T. Since (1, > 1- nu by degree pruning condition (2) and (1,z²) > 1u by corruption rate, it is easy to verify that
(1,z") >
2nn.
Moreover, we have A' O'0z''zz)' =A0 due to
Ā Z T = A o 22 T 0z A 2z 2 = A (2) o T
From Eq. (D.9), can get that d < (A). Plugging this into degree pruning condition (1), we get
|A < log(1/n)Rd & <2oog(1/)Rdd(A)
Therefore, we have
(A't); < (logg\/)))d(A')
for all i E [m]] Thus, (A',z") is feasible solution to c(Y,z;A,y,o) with y = =2n and 2log(1/1)
D.2 Robust algorithm
In this section, we show that the following algorithm based on sum-of-squares proofs in Appendix D.1 obtains robust constant multiplicative approximation of d'.
22

---

Algorithm D.4 (Robust coarse estimation algorithm). Input: :i-corupted adjacency matrix A, corruption fraction 1j and parameter R.
Algorithm: Obtain level-8 pseudo-expectation È by solving sum-of-squares relaxation of program A σ) (defined in Eq. (D.3)) with A, y 21j and o = -
Output: B[d(Y)]
Theorem D.5 (Robust coarse estimation). Let Q" be an n-by-n edge connection probability matrix and let d := d(Q"). Suppose I|Q% & Rd /n for some R. Let A be an n-corrupted adjacency matrix of a random graph G G(n, Q²). Suppose 1j log(1/n)R & c for some constant that is small
enough. With probability 1 n Q(1), Algorithm D.4 outputs an estimate à satisfying 1 - 1| & 0.5.
Proof. By Lemma D.2 and Lemma D.3, we know that
Yz C(Y, c(Y,
1
(1 4y)))(()) <d(Y) 1 1-40
d(A"),
and,
Therefore, we have
1.1 do
C(Y, y,0 0.9(1 4yo)d < d(Y) 1 4yo
Consider 4ya, for constant c that is small enough, we have
4yo on
1/r)R 8c & 0.1.
This implies that 0.9(1 - 4yd) > 1 and 11
1-ya
<
11 &
Therefore, we have
Y,z C(Y, o)
d
3 < d(Y)
< 2
Thus, the level-8 pseudo-expectation E satisfies
3 d B(d(Y) _dd
which implies that
B[d(Y) d
1
1
<
2
D.3 Private algorithm
In this section, we present our algorithm and prove Theorem D.1. Our algorithm instantiates the sum-of-squares exponential mechanism in Appendix C.
Score function. For an n-by-n symmetric matrix and scalar d, we define the score of with regard to A to be
3 level-8 pseudo-expectation É satisfying (( U (ld(Y) - di & ad),
s(d; := min yn s.t. 0sys1
(D.10)
where 2, a) is the polynomial system defined in Eq. (D.3), and o, are fixed parameters whose values will be decided later. Note that (Y _ 11T, 0) is solution to the polynomial system 2,,, (ld(Y) d] & ad) for any A E Rax [0, n), and a > 1.
To efficiently compute A(d; can use the scheme as described in Remark C.1.
23

---

Exponential mechanism. Given privacy parameter é and an nı-y--t symmetric matrix A, our algorithm is the exponential mechanism with score function Eq. (D.10) and range [0, n].
Algorithm D.6 (Coarse estimation).
Input: Graph A.
Parameters: a,
Output: A sample from the distribution μa,e with support [0, n] and density
(d),,(d) & exp(-e sdd;A)),
(D.11)
where s(d; A) is defined in Eq. (D.10).
To efficiently sample from HA,e, we can use the scheme as described in Remark C.2.
Privacy. The following privacy guarantee of our algorithm is direct corollary of Lemma C.4.
Lemma D.7 (Privacy). Algorithm D.6 is 2e-differnntially node private.
Utility. The utility guarantee of our algorithm is stated in the following lemma.
Lemma D.8 (Utility). Let Qº be an n-by-n edge connection probability matrix and let de d(Q"). Suppose I| & Rdd /n for some R. There are constants C1, C2 C3 such that the following holds. For any n, e, d such that 17 llgg(1/n)R n-corrupted inhomogeneous random graph G(n, Qº), Algorithm D.6 oulputs an estimate à satisfying ld - d'1 & 0.5d with probability 1 n -
C1, & > C2 Colog (n) (n)R/n, and d > C3, given an
Before proving Lemma D.8, we need the following two lemmas.
Lemma D.9 (Volume of low-score points). Lef A E Rox= and Consider the distribution UA,, defined by Eq. (D.11). Suppose (Y = A", = 2") is solution to (o,((, A,A, y", σ) and d(A") > 2. Then for any > 0,
logn n
n
+11
P d d-Ha,-
s(d; A) y +
<
Proof. Apply Lemma C.5 with D |0, and
d(A')
d(A')
G(A') d E D
1+ < d < 1-a
As [d(A)/(1+a), C G(A') and d(A') > 2 1 + we have vol(G(A")) >
Lemma D.10 (Low score implies utility). Let R and consider the score function s(- AA) defined in Eq. (D.10). Suppose (Y = A', = 2²) is a solution to C(Y, 2; A, Y o). For scalar d such that sdd; A) & 'n and (y" + T)0 & 0.1,
0.8
1.25
1 d(A') & d
d(A')
a
Proof. Applying Lemma D.2 with (y + t)o 0.1, we have C(Y,z;A,T,))
Y
0.8d(A) < d(Y) 1.25d(A')
8
Thus,
Y= 0.8
1.25
C(Y,2;A,,,,) d & ad)
d(A') &
1- d(A")
1+a
Now ready to prove Lemma D.8.
24

---

Proof of Lemma D.8. Let A be realization of 1pcorrupted G(n, Q³). By Lemma D.3, the following event happens with probability - - There exists solution (Y 2 to C(Y, y, o) with y" 2n, o 2 log(1/n)) and 0.9d d(A") & 1.1d".
As d(A*) > 0.9d > 2, then it follows by setting 10 and 0.01 in Lemma D.9 that,
P (s(d; A) & Tn) > 1 1 - where 2n 10 (og))))(en).. d d-qA,
As 1リ-corrupted graph is actually uncorrupted when ll 1/11, can assume 1) > 1/(2n) without loss of generality. Thus,
(2n T) & (llog(1/)) 20log
ne
For r R and (n) smaller than some constant, we have (2n + 7)σ & 0.1. Let à be a scalar such that Add & tn. Then by Lemma D.10,
0.8 1+ d(A') < à 1.25
1-a d(A').
Plugging in a < 0.01 and 0.9d d(A)) & 1.1d", we have
0.5d < < 1.5d"
Proof of Theorem D.1. By Lemma D.7 and Lemma D.8.
E Fine estimation for inhomogeneous random graphs
From Appendix D, we have constant multiplicative approximation of the expected average degree d'. 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 Qo be an n-by-n edge connection probability matrix and let d := d(Q2). Suppose I|Q Rd /n for some R. There is a sufficiently small constant c such that the following holds. For any such that n log(1/n)R & there exists polynomial-time z-differentially node private algorithm which, given an c-corrpptdd inhomogeneous random graph G(n, Qº) and a constant-fuce approximation of do, outputs an estimate d satisfying
d
log n
R log' +log(1/1)
1
< 0
d
en
with probability 1 -Q(1)
We make a few remarks on Theorem E.1.
Our algorithm in Theorem E.1 is sum-of-squares exponential mechanism. R, n7 are parameters given as input to our algorithm.
We can get an estimate pa by taking p .. Since f. zE, follows that
log d
Rlog² mlog(1/n)) en
1
O
+
pD
Combining Theorem D.1 and Theorem E.1 gives efficient, private, and robust edge density estimation algorithm for inhomogeneous random graphs whose utility guarantee is enformation-thhorrttiaall optimal up factor of log and log(1/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 robust algorithm via sos proofs Appendix E.1. Then in Appendix F.3, we describe our algorithm and prove Theorem E.1.
25

---

E.1 Sum-of-squares
For adjacency matrix A and nonnegative scalars y, and å, consider the following polynomial systems with indeterminates Y = (Vi)),j(n) 2 = (2i)ie(n) and coefficients that depend on A,,, ,,,,
P;,Y, = 20 (1, > (1- 7)n 11, =0
(E.1)
P3(Yo, ((11), [
(E.2)
For convenience of notation, we will consider the following combined polynomial system in the remaining of this section
D(Y, D.. - P3(Y;o,ā).
(E.3)
Lemma E.2. (f',, z²) a feasible solution to y o, then follows that
Y2 [d(Y) d(A") < 2(y + y")od.
DY z;,,;A, y,
Proof. Let w = =2 Using similar analysis as in the proof of Lemma D.2, it follows that
Y2 YO www = A' o ww
D
and,
Y2 D
n d(Y) = (1,
8
(A", ww ) (Y,2(1-w)1") (V,(1=)(( -w)
& (A", 11 (Y1,2(1 w))
n d(A') 2(y + y')ond.
By rearranging the terms, we have
Y= 1 d(Y) - d(A') < 2(y + (1ly+y"jop y'ood.
D
Swapping the roll of Y and A", we can also get
D y d(A") d(Y) < 2(y y y')
This completes the proof.
Lemma E.3. Let Qo be an n-bb-n edge connection probability matrix and d' := d(Q"). Suppose 110 & Rd /n for R E R. Let A be an n-corrupted adjacency matrix of random graph G G(n, ).). Suppose 1i 1log(1/n)R & Cj for some constant C1 that small enough. With probability 1 n Q(1), there exists A and z" such that
Id(A') - d'1 10 de log log(o(//))
(A',z") is feasible solution to D(Y, à) with n-corrupted A, y = 21, 10log(1/n) and à ddp
Proof. Let A be the adjacency matrix of G and z" E 10, denote the set of uncorrupted nodes (z? = if and only node is uncorrpted).
By Lemma B.2 and Lemma B.3, we know that, with probability 1 -n -20),, there exists degree-pruned adjacency matrix À such that
1. ||il|l, < ld'
26

---

2. At most yn nodes are pruned.
3. At most 21j log(1 //) edges are pruned.
Let 10, denote the set of unpruned nodes (2; = and only node not pruned).
We will show that A and z' o satisfies the lemma.
Guarantee 1. By Lemma B.1, know that, with probability 1 11 -2()
do log
Id(A') -d d')
< 10
(E.4)
From degree pruning guarantee (3), we have that
[d(A) d(A*) & log(((/)))
(E.5)
Combining Eq. (E.4) and Eq. (E.5), we have
ld(Ā) - d'l < Ia(A) d(A9) Id(A)) dd
do log
< 10
+ logg0(1/))
n
Guarantee 2. It is easy to check that z' 0'' =0, & 11T and A' = ". Since Since (1, > 1 11 nn by degree pruning condition (2) and (1,z²) > - qu by corruption rate, is easy to verify that
(1,z') > 1 2nn
Moreover, we have A =A0=(=))) due to
Āo (z) A 22 o 2z²) A 0z" Ao =0 ozE T
By degree pruning condition (1), we have
(A' 1); < log(1/n)Rd & on.
for all E [n]] Thus, (A',z") is a feasible solution to 2,,,, with y = 2nj, a 100ogg1/r) and > dd"
E.2 Robust algorithm
In this section, we show that the following algorithm based on sum-of-squares proofs in Appendix E.1 obtains robust approximation of d that is optimal up to logarithmic factors.
Algorithm E.4 (Robust fine estimation algorithm for inhomogeneous random graphs). Input: corrrppee adjacency matrix A, corruption fraction n and parameter R. Algorithm:
1. Obtain coarse estimator à by applying Algorithm D.4 with A, 17, as input.
Obtain level-8 pseudo-expectation È by solving sum-of-squares relaxation of program D(Y, z; A, y, o, a, (defined in Eq. (F.3)) with A, y 2n, o 10log(1/r)R and à.
Output: B[d(Y)
Theorem E.5 (Robust fine estimation for inhomogeneous random graphs). Let Q2 be an n-by-n edge connection probability matrix and let d' := d(Qº). Suppose 1|Q & Rd for some R. Let A be an n-corrupted adjacency matrix of random graph G G(n, Q"), Suppose
27

---

Ilog(1/n) & c for some constant c that small enough. With probability 1- 1-n-00) Algorithm E.4 outputs an estimate satisfying
log n + log(1/n)R
1
& 0
d
Proof. By Theorem D.5, we have dd < à < dd d Let y 21,, by Lemma E.2 and Lemma E.3, follows that
D(, |d(Y) d(A')l 2(y + o'o
3 d 2 4n 10 10 /n)
2 2a
120n log(1/n))dd
and,
d log n
Id(A') d'l & 10
2r/ log(1/n))
Therefore, we have
Y= |d(Y) d'1 l0gglo/(1/))Re + +10 2(Y, lo
d log
Thus, the level-8 pseudo-expectation É satisfies
d log
[[[d()] d 200n log(1/n))Rd 10
which implies that
B[d(O)
log d'n + log((111)))
& <0
d
E.3 Private algorithm
In this section, present our algorithm and prove Theorem E.1. Our algorithm instantiates the sum-of-squares exponential mechanism in Appendix
Score function. For an n-by-n symmetric matrix and a scalar d, we define the score with regard to A to be
3 level-8 pseudo D(Y, U (Id(Y) - d| & ad).
satisfying
s(d; min yn s.t. d
(E.6)
where 2; G, 2) is the polynomial system defined in Eq. (F.3), à a coarse estimate, and o, a are fixed parameters whose values will be decided later. Note that (Y 1 0) a solution to the polynomial DY,, z; A, 1, a, â) (ld(Y) d & ad) for any A e RIXH and any such that 0 & d & min(ad, n). To efficiently compute s(d; A),
the scheme described in Remark C.1.
Exponential mechanism. Given a privacy parameter and n-by-n symmetric matrix A, our private algorithm in Theorem E.1 is the exponential mechanism with score function Eq. (E.6) and range [0, min(od, nt].
28

---

Algorithm E.6 (Fine estimation for inhomogeneous random graphs).
Input: Graph A, coarse estimate à.
Parameters: E, a,
Output: A sample from the distribution μA with support [0, min HT] and density
dd),c(d) (((())-s(d;A)),
(E.7)
where A) is defined in Eq. (F.6).
To efficiently sample from MA,e, we can use the scheme as described in Remark C.2.
Privacy. The following privacy guarantee of algorithm is direct corollary of Lemma C.4.
Lemma E.7 (Privacy). Algorithm E.6 is 2c-differentially node private.
Utility. The utility guarantee of our algorithm is stated in the following lemma. Lemma E.8 (Utility). Let Q" be n-by-n edge connection probability matrix and let d d(Q²). Suppose I1Q & Rdd /n for some R. There a sufficiently small conslant c such that the following holds. For any 7 such that 17 log(1 (n))) c, given nycorrupted inhomogeneous random graph G(n, Qa) and a coarse estimate such that 0.5d à 2d', Algorithm E.6 outputs an estimate satisfying
d
log n
log # en
-
&
0
+n1og(1/n)R
d=
d
with probability 11 -Q1),
Before proving Lemma E.8, we need the following two lemmas.
Lemma E.9 (Volume of low-score points). Let A RIx and > O. Consider the distribution
UA,e defined by Eq. (E.7). Suppose (Y = A', = 2²) solution to D(Y,,;A, ,,, a) and 2 < d(A') & od. Then for any 1 > 0,
s(d; > y'n log
til
P d HA
a
Proof. Apply Lemma C.5 with D 10, min(od, n)] and
G(A') d e D d(A')
d(A')
I+ < d < 1-a
As [d(A')((1 ()) S G(A') and d(A') > 2
a, we have vol(G(A')) >
Lemma E.10 (Low score implies utility). Lef A E R and consider the score function s(-; A) defined in Eq. (E.6). Suppose (Y A', z²) a solution D(Y, Z; o, d). For scalar such that Ad; & Tn,
d(A') 2(y" + tz)a
d(A') 2(y" + z
& d
+ a
1-a a
Proof. By Lemma E.2,
D(Y, Y |d(Y) d(A') & <2(v" z)od.
Thus,
A,,, (ld(Y) dl < ad)
Y,z d(A') - 2(y" + r)od dd g d(A') 2(y + T)o
1 a
a
29

---

Now we are ready to prove Lemma E.8.
Proof of Lemma E.8. Let be realization of n-corrupted G(n, Q*). By Lemma E.3, the following event happens with probability at least 1 (Q01) There exists solution (Y A',z=z0 to D(Y, y', a, a) with y" = =2,, 10log(1 /n)R, and
[d(A") d0| 10 1 log(n)) 2ng
For llo((1/)) smaller than some constant, have 0.9d² & d(A') 1.1d". Note that d(A') > 0.9d and d(A') & 1.1d od. Then it follows by setting 10 and a = n in Lemma E.9 that,
P (s(d;A) & Tn) > 1 n where 2n 10log(r))(ee)) d~uAA.c
Let à be scalar such that s(d:A) TH. Then by Lemma E.10,
d(A') 2(2n + t)od
d(A') 2(2n + t)oa
< à
1+a a
1-a a
Plugging in everything, we have
log
R Rlog(1/n)logr + Rn log(1/n)
- < 0
do
d
As an 1--orrupptd graph actually uncorrupted when 7 1/n, we can assume 1) > 1/(2n) without loss of generality. Therefore,
à
log n d
Rlog²
1
40
+
Rn 1og(1/1))
d
en
Proof of Theorem E.1. By Lemma E.7 and Lemma E.8.
F Fine estimation for Erdós-Rényi random graphs
From Appendix D, we have constant multiplicative approximation of the expected average degree d', 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 conslants C1, C2, C3 such that the following holds. For any 1 C1, > C2 C2log(n)/n, and d' > Ca, there exists polynomial-time E-differentially node private algorithm which, given an cccoruppedd Erdós Erdōs-Rényi random graph G(n, d' /n) and a conslant- factor approximation of d', outputs an estimate satisfying
à
log d
log2 n Vd
1log1
<
+
d
vd=
with probubility -90)
We make a few remarks on Theorem F.1.
Our algorithm in Theorem F.1 is sum-of-squares exponnntial mechanism. R, n, are parameters given as input to our algorithm.
à We can get an estimate of pa by taking P . Since f F it follows that
log n
log2n. n
17 log
<
p
Vn v od
30

---

Combining Theorem D.1 and Theorem F.1 gives us an efficient, private, and robust edge density estimation algorithm for Rénós random graphs whose utility guarantee is information-theorrtcaall optimal up to factor of log nt
In Appendix F.1, set up polynomial systems that algorithm uses and prove useful sos inequalities. In Appendix F.2, we show that we can easily obtain a robust algorithm via proofs in Appendix F.1. Then in Appendix F.3, describe our algorithm and prove Theorem F.1.
Sum-of-squares
For an adjacency matrix and nonnegative scalars y, a and à, consider the following polynomial systems with indeterminates Y (.f)). (Zi)ietw] and coefficients that depend on y, a, ō,
z (1,z) (1- 7)n 0<Y =0zz=A02
p=();
(F.1)
[(Y1): < ov P,(Y)
Vi [n]
|||--011
400) 11 ovā
(F22
op
For convenience of notation, we will consider the following combined polynomial system in remaining of the section
U Pa(Y;a,
(F33
Lemma F.2. (f(A",z") is feasible solution to E(Y, 6, 2) and y + y <1, then it follows that
4(y y')o ( 2(y + +
8(Y, ,0, -00)-444 1
(1 y1-y
Proof. Let =z Notice that, by Lemma A.9, we have & _ 1 1-w; i [n]. Moreover, using similar analysis in the proof of Lemma D.2, it follows that
w) < 2 2; 2 for all
Y
ww Yoww
Yo
A" o www
Therefore, we can get
Σ Yz n ((d( d(A))
=(Y - 11
=(Y =(Y-A; -", 11 -ww! )
=(Y d(M) 11T d(Y), 11 d(A')
11 + d(A')
11 - - 11T www"
=(Y d(Y)
11T, 11 www T) d(A')
11 A", 1T -ww!
d(Y) 11 d(A')
1TT 11 ww
=(Y d(Y)
11T 11 www T) d(A') n
11 A", 11T www
n
11 n- (1, w/2 + (aM) d(A3))
(F.4)
By rearranging terms, we can get
8 Y,z (1,
(d()) - -d(Aa) (Y d(Y)
11 11 www + 11T A", -ow
d(A")
T).
(F.5)
31

---

We bound the two terms on the right-hand side separately. For the first term (Y-
d00) 11T, 111 www" we have
"1
8 Y= (Y d(9) 11 11 [ow' ww)) = d(Y) 11", 1(1 111-)110))+) dM 11 (1
(F.6)
From constraints (YY1); d(Y) & ov forall [m], (1, > (1- and (1,z") > (1-y")n we have
& Y2 (Y
d(Y)
11 1(1 - w) = (YI d(Y),, 1 w)
Σ
(1 w))ovaa
i6[n]
(F.7)
< <ovā
Σ iE(N]
- zi zi
(y+ y")nova.
From constraints
Y d(Y) 11T
< &dvd, (1, > (1 - y)n and (1,z") > (1 - y')n, we have
op
d(Y)
d(Y)
8
11 Y, (1 (0 - >)) < X
11
| w
n
n
lop
< 88v.
Σ
w. )
(E[m]
= vvā.
Σ - w0;
(F.8)
[E(m]
< &oV.
Σ
2 - 2: 27
[c|N]
< < + y')n
where the equality is because & (1 - w;) = (1 - 2;2,2 = 2izZ Wi.
Plugging Eq. (F.7) and Eq. (F.8) into Eq. (F.6), it follows that
M (Y d(Y), 8
11T 11 ww < 2(y y')no + (y + y'vv.
(F.9)
n
For the second term [(AA) 11T - 1 ww T) we can apply the same proof as above to get
8 Y,2 d(A')
- A", 11 ww < 2(y +y'no vā (y + y'novd.
(F.10)
8
Plugging Eq. (F.9) and Eq. (F.10) into Eq. (F55,, it follows that
Y= &
2))
d(Y) -(A))
4(y + y>)+y)novaaa 20y + n'Vv..
8 n
Using the same proof strategy, we can also get
Y,2 g
(1, (d(A') a(m) 4(y + Myy+ynnova + 20y + b nova.
B
n
32

---

Applying Lemma A.10, it follows that
8 Y= (1,w)*
-(A))) & (4<y+ + 2(y + y')nova)
(F.11)
n²
Now, we would like to lower bound (1,w)*, By Lemma A.9, we have & _ w, > 2j + for all [n]. Therefore,
V.2 - (1, &
Σ
20
ic|n]
ic(n]
Since + <1, we have 1 y O, and, therefore,
& _ (1, (1 - y--->"""""
Plugging this into Eq. (F.11), we have
Y2 (1 - y1-y->") -d(a))))))())) & (42y + y 2(y + y y'vvv)
&
Y,2 ((()) -(Aa)) y4 2(y y")ova)
(1 (1-y- yn)
Applying Lemma A.11, it follows that
4(y + y Voovvva + 2(y yovv
Y= Id(Y) d(A)) <
8
(1 y1-y-y"*
Lemma F.3. Let A be an n-corrupted adjacency matrix of a random graph G G(n, 4) With probability 1 -00), there exists A and z" such that
Id(A*) d'1 < 10
log
(A',z") feasible solution to E(Y, Z,Y, 0, with n, o =4log n, 4C n for some constant C. and >> 1dd.
Proof. Let A be the adjacency matrix of G and 2" E 1)" denote the set of uncorrupted nodes (z, 1 and only if node is uncorrupted).W. We will show that A" A and z" z satisfies the lemma.
Guarantee 1. By Lemma B.1, we know that, with probability 1 n Q(1)
do log
Id(A)) - dol < 10
(F.12)
Guarantee 2. It is easy to check that z z', 0 A' < 11T A (1,z*) 1n. By Lemma B.2, we know that, with probability 1-m -Q0),
(A9) and
|| 1 & va log
(F.13)
Combining Eq. (F.12) and Eq. (F.13), we have
|| UlA") & ||'' - 1ll.o + ||d dl
do log
< V log n + 10
(F.14)
< 2 2oog n V
33

---

Therefore, for 4 n and _d, it follows that
((A1)); d(A') & 2logn & ovā,
for all [n]]. By Lemma B.5, we know that, with probability -Q11,, for some universal constant C,
d
A
C d' logn.
(F.15)
11
lp
Combining Eq. (F.12) and Eq. (F.15), we have
1o d(AA)
1 d(A))
d(AA)
d 11
11
11
op
op
op
da log 1
(F.16)
< Cyde log 10
< 2C 2C logn.
Therefore, for ö 4C Vlog and à ddp it follows that
d(A)) A'
< 2C logn & oVπ.
10
n
op
Thus, 2"" is a feasible solution to ,Y, with = 17, a 4logn,, 4C Vlogo n and à > _dd.
F.2 Robust algorithm
In this section, we show that the following algorithm based on sum-of-squares proofs in Appendix F.1 obtains robust approximation of d' that is optimal up to logarithmic factors.
Algorithm F.4 (Robust fine estimation algorithm for Erdós- Erdós-Rényi random graphs). Input: -ccorrpped adjacency matrix and corruption fraction !).
Algorithm:
1. Obtain coarse estimator à by applying Algorithm D.4 with A, R = 1 as input.
Obtain level-8 pseudo--eppccation È by solving sum-of-squares relaxation of
program E(Y, 6, d, (defined in Eq. (F.3)) with A, = IJ, 4 4log 11
5 = 4C4C-llorr and à.
Output: B[d(Y)]
Theorem F.5 (Robust fine estimation for Erdós-Rényi random graphs). Let A be an corrrppeed adjacency matrix of random graph G G(n, $). With probability 1 - 20), Algorithm F.4 outputs an estimate satisfying
log n d
17 log n
1
&
d
Vd
Proof. By Theorem D.5, we have dp & à < dd. Let = n7, by Lemma F.2 and Lemma F.3, it follows that
4(y + V'v + 2(y + +
Yz 80,,:;A,,,,, O0) (d(Y) -(A')
(1- y--y-y y-)2
34

---

40m log n 'd 40Cr/ log
(1 (1-2n)²
C'nlognVa'
for some constant C', and,
de logn
Id(A") -d'l & 10y
"1
Therefore, we have
Yz 8YY, 0, o0) [d(Y) - d') C'nlogn 10
de log
n1
Thus, the level-8 pseudo-expectation satisfies
do log 11
B[d(Y) d'l C'nlogn 10
which implies that
B[d(Y)]
log dn
g Vd=
10
F.3 Private algorithm
In this section, we present our algorithm and prove Theorem F.1. Our algorithm instantiates the sum-of-squares exponential mechanism Appendix C.
Score function. For an n-by-n symmetric matrix A and scalar d, we define the score of with regard to to be
3 level-8 pxeudo-expectation È satisfying
s(d; min yn s.t. (& A, à) U (Id(Y) - d| add, (ky
(F.17)
where &(Y, y, G, 8, 2) is the polynomial system defined in Eq. (F.3), is coarse estimate, and a, 5, a are fixed parameters whose values will be decided later. Note that (Y 1 0) is a solution to the polynomial system 2,Y, à) u (Id(Y)dd - 1| < a} for any A E RO* and any d n].
To efficiently compute s(d; A), we can use the scheme as described in Remark C.1.
Exponential mechanism. Given a privacy parameter E and an n-by-n symmetric matrix A, our private algorithm in Theorem F.1 is the exponential mechanism with score function Eq. (F.17) and range [0, n].
Algorithm F.6 (Fine estimation for Erdós-Rényi random graphs).
Input: Graph A, coarse estimate à.
Parameters: E, ,, 8,a.
Output: A sample from the distribution μA,e with support [0, n1] and density
dus,e(d) æ exp(-e-spee s(d;A)),
(F.18)
where s(d; A) is defined Eq. (F.17).
To efficiently sample from MA,e, we can use the scheme as described in Remark C.2.
Privacy. The following privacy guarantee of our algorithm is direct corollary of Lemma C.4.
Lemma F.7 (Privacy). Algorithm E.6 is 2e-differnntially node private.
35

---

Utility. The utility guarantee of our algorithm is stated in the following lemma.
Lemma F.8 (Utility.. There are constants C1 C2, C3 such that the following holds. For any n & C1 s C2 C2log(n)/n and dº > C3, given n-corrupted Erdōs-Rényi random graph G(n, d'/n) and coarse estimate such that 0.5d & a & 2d', Algorithm E.6 outputs an estimate à satisfying
à
log f1 n
log² n
1log n1 V
1 & 0
d=
Vd EN
with probability n --1))
Before proving Lemma F.8, we need the following two lemmas.
Lemma F.9 (Volume of low-score points). Let E R and e > 0. Consider the distribution
UA,, defined by Eq. (F.18). Suppose (Y A", z²) is solution to E(Y, A, and d(A") > 2. Then for any > 0,
tlogn
11
-1+1
P d-NA,
s s(d; A) > y'n
<
a
Proof. Apply Lemma C.5 with D = [0, n1 and
d(A)) 1+a a
d(A")
G(A") d D)
< d <
l-a
As a0))//(+a,,, c G(A") and d(A') > 2 > 1 + a, we have vol(G(A')) >
Lemma F.10 (Low score implies utility). Let A E R and consider the score function s(- A) defined in Eq. (F.17). Suppose (Y = A", 2 z²) a solution &YY, A, For scalar such that s (d;; A) & un and y + < 0.1,
1 a [((A') -5yy t)(a + ō)vî < d a (d(A)) 50y" + 7)(o 8)
1
Proof. Applying Lemma F22 with y + 0.1, we have
Yz 8(Y2;AATT) i |d(Y) d(A') < 5(y + z) + Syvā.
Thus,
8(Y,2;A, 2; U (Id()) dl < ad)
Y
1
(((A))5(0) - + ( - < < & 1-a
[d(A))+ +((4))5((*++ +T)(o +8)va)
8 1+a
Now we are ready to prove Lemma F.8.
Proof of Lemma F88. Let A be realization of 1/-oorupptd G(n, d d//n.. By Lemma F3,, the following event happens with probability at least n Q11), There exists solution (Y y", a, Ö, d) where y" r1, a & O(logn), ö < O(ylogn), and Id(A') d31 O Vd log(n)/1
A', = z²) to
As d(A')= 0.9dt > 2, then follows by setting 10 and a - in Lemma E.9 that, P (s(d; A) & TH) > 1 ~7 where : := 2n + 10 10log(n)/(en). d~uA.-
Let à be scalar such that s(d; A) & Tn. For n and log(n)/(en) smaller than some constant, we have 2n + & 0.1. Then by Lemma F.10,
1 + a (A(A)) 5(1 () + 8)vî < d
1 1- a [(A')++
1
((AA))5((+++ a) + 0yva).
36

---

Plugging in everything, we have
a d=
log n d
log21 n
n log
< <0
+
+
Vd en
Proof of Theorem F.1.
By Lemma F.7 and Lemma E.8.
G Lower bounds
In this section, we prove Theorem 1.5, Theorem 1.7, and Theorem 1.8.
G.1 Lower bound for Erdós-Rényi random graphs
In this section, we prove Theorem 1.5.
Theorem (Restatement of Theorem 1.5). Suppose there is an e-differentially node-private algorithm Brdōs-Rényi
that, given an Erdōs- Rényi random graph G(n, p)), outputs an estimate salisfying 1p/p" - 1| < a with probability 1 B. Then we must have
log(1 1/B)
a > Ω
En /up
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 construct a coupling of G(n, p*) and G(n, (1 2a Jp") such that for (G, G') (,, the typical distance between G and G' can be well controlled. However, such a coupling tricky to construct directly, as the node degrees in an Erdós-Rényi random graph are not independent. To avoid dealing with such dependence, we instead consider the directed Erdós- Rénsi random graphs, which is inspired by the proof of [AJK*22, Theorem 1.5]. The directed frdōós-Réníí random graph model, denoted by G(n, ))), is distribution
ı-node directed graphs where each edge (i, is present with probability p" independently. Since the outdegrees in directed Erdós-Rényi random graph are i.i.d. Binomial random variables, it is not so difficult to construct coupling of G(n, convert such coupling into coupling of G(n, p²) and
and G(1, (1 - 2)) Then
G(n, (1 - 2).
Lemma G.1 (Coupling). Lef pa [0, 1}, a E [0,1/2|, and p' := (1- 2axpp.. There exists coupling of G(n, (a) and G'n,p') with the following property. For (G, G') w, the distribution of dist(G, G') the binomial distribution Bin(n, A) where TV(Bin(n, p²), Bin(n, p')),,p')) Moreover, p c and c// vnp for some constants c, c, then S ax'pp"
Proof. We first show that it suffices to construct coupling of G(n, p¹) and G(n, p'). For directed graph G, it can be converted into an undirected graph U(G) by letting (i, f) e u(G) iff i & and (i, j) Č. It is easy to see that dist(C, C') = (ist(LU(C), U())). Also observe that if Č Ü(H, pd) then u(Ō) G(n, po). Therefore, a coupling @ of G(n,p") and G(n,p') can be easily converted in to a coupling a of G(n, p²) and G(n,p') such that, for (G, G')- ~ and (G, G') w,, we have
dist(E, G') a dist(G, G")
Now we construct a coupling of G(n, po) and G(n, p'). Instead of sampling each edge independently, an equivalent way to sample from G(n, pd) is as follows. For each i [n]]
"oFor a directed graph G, we define its adjacency matrix Ā to be Á(i, i) ((ii e G). The (node) distance between two n-node directed graphs G, G', denoted by dist(G, G'), is number of nonzero rows of À A'A' A'.
37

---

Sample an outdegree d ~ Bin(n, p*).
Sample a uniformly random subset S S [n] of size d. For each j e S, add an edge from to j.
Then it is easy to see there exists coupling @ of G(n, p*) and G(n, p²) such that if (G, G') @ then dist(G, G') Bin(n, A) where
A = (V( p"), Bin(n, p'))
We have the following bound on the total variation between binomial distributions (see e.g. [A]06, Equation (2.15)]). For 0 < 1 and 0 < x
< 1--P p,
Ve 7(x)
TV(Bin(N, p), Bin(N, +
2 (1 T(x))2
where r(x):= := x 2p(1-p) provided 7(x) < 1. Plugging in = n1 p = p", and x 2ap", we
N+2
have
A = TV(Bin(n,,) p"), p')) aa
provided p" < and c' Vnp for sufficiently small absolute constants c,
Proof Theorem 1.5. Let A be an algorithm satisfying the theorem's assumptions. Let p':= (1 2a)pp. Let be coupling of G(n, pº) and G(n,p') as guaranteed by Lemma G.1. Then for GG, ~ w, we have dist( G, G') ~ Bin(n, A) where A = TV(BBnnn,, p²), Bin(n,,p)).
By the utility assumption of algorithm A,
P
(AG) p01 < ap') > 1 1-B.
P,
As algorithm A is DD, we have for any graphs G' G' that, P( - p'l < apd) < dist(C))))) PP( < ap²).
Taking expectation w.r.t. the coupling a on both sides gives
EE 1 (["( p'' ap') } < E e dds) F. 1 ( p'l ap'),
A
(LA(G') pp' ap") E e dist((,,))) A,
(G) pp' < app)
(G.1)
0,7
By the utility assumption of algorithm A and p' < pp, the left-hand side of Eq. (G.1) is at least - B. Using the Sccwwrrt inequality, the right-hand side of Eq. (G.1) can be upper bounded as follows,
e dis) ((A - < app} < ..9
E e2c Gist( a,7
E ([ - p'l app)
E Bin(n,A)
e2c-X
P G,.
(A p'l ap").
By squaring both sides of Eq. (G.1) and plugging in the above two bounds, we have
- B) <
E
P (LA(G) p'l ap").
Bin(n.A)
g1,6(,p")
Using the formula for the moment generating function of binomial distributions, we have
[2=x]] = (1 (1+ +(eee -1)) < -1)
E Bin(n,A)
Then
P (A( p'l ap') (1 -B2 a -n
38

---

Since p' -p" = 2xp", the two events (p: :p:p- 1ppppl < ap*) and {p: 1 1-pp < ap") are disjoint. Thus,
(I( p'l ap²) <
P ,,G((,
([A(G) - p"1 < app) < p.
3,G(n,p))
Therefore, we have the following lower bound
2 (1 B) + log(1/B)
n(e2c - 1)
which is A z log(1//)) for samll enough and B.
By Lemma G.1, pf & c and a & c'/ v'Iv for some constants c, then A & avnpp. Combined with the lower bound A z
log(1/p)
we have
we
a 2 log(1/B)
NE np
G.2 Lower bound for inhomogeneous random graphs
In this section, we prove Theorem 1.7 and Theorem 1.8.
We first show the lower bound for the error rate of robust estimation.
Theorem (Restatement of Theorem 1.7). Suppose there is an algorithm satisfies the following guarantee for any symmetric matrix Qo E [0, 1| Given an n-corrupted inhomogeneous random graph G(n, Q²), the algorithm outputs an estimate P satisfying 1p/p² 1| with probability at least 0.99, where p² Σi, (n² n). Then we must have (2T)),, where maxi, /
Proof. Let pe [0, 1], and let Q e [0, 1]RX" be the matrix, in which all entries are pd, except for the rows and columns corresponding to set of nn nodes setting to be Rpº. Let Q be the matrix, which all entries are p", except for the rows and columns corresponding set of nu nodes setting to be O.
We construct the following pair of distributions Do and D1;
Dr: The distribution of G ~ G(Q").
D1: The distribution of G ~ G(Q).
Then we have 1111
|IQl | > Q(Rnn?p").
On the other hand, there is coupling between G G(Q") and & G(Q) such that dist(G &¹ rn. Therefore, the two distributions are indistinguishable under the r corruption model. Since the edge density of G(Q") differs from G(Q) by Q(Rnp"), no algorithm can achieve error rate of Rmp²) with probability 1 o(1) for both distributions under the corruption of p-fraction of the nodes.
Theorem (Restatement of Theorem 1.8). Suppose there is an e-differentially mode- algorithm satisfies the following guarantee for any synmmetric matrix Q E [0,1] Given an inhomogeneous random graph G(n, Q"), the algorithm outputs estimate 6 satisfying 1p/p² 1| with probability 1 B, where pd Σi,; 2i (n22 n). Then must have
R (og((1/))
a > Ω
nE
where R = maxi, p./pp'
39

---

Proof of Theorem 1.8. We will prove the lower bound by constructing pair of distributions Do and Dj such that the total variation distance between them small, but the difference in edge density is significant. Then since e-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 17 E |0, 0.001). Let pa [0, 1I, and let Q" [0, 1| be the matrix, in which all entries are p", except for the rows and columns corresponding to set of ıjn nodes setting to be 0. Let Q be the matrix, in which all entries are p", except for the rows and columns corresponding to set of nn nodes setting to be Rp".
We construct the following pair of distributions Do and D1:
Do: The distribution of G G(Q").
Dj: The distribution of G G(Q).
Let p'
10 and p x²
1Qll n²
We have Ip - p'l Rnpº.
On the other hand, there is a coupling between & G(Q) and & ~ G(Q") such that dist(G, < mnn Taking expectation w.r.t. the coupling w on both sides gives
EE 1 न
[ -pl 2
Rι
pe
E eessii
(( -p p|
Rm
2 p
[ -(
Rn p
E e dist w,9
(9()) - p| 2
Rι 7 pr)
a,,()))
2
By the utility assumption of algorithm A and p pp, the left-hand side is at least p. Using the Cauchy- inequality, the right-hand side can be upper bounded as follows,
E disttt a.A
1((010)- - pl
Rn pr 2-12
<
E @ A.7
E 4.7l
Rn [(G)) - pl
2 p
R1j [(())
< exp(Enn)
P
pl
po
a,,(@))
Thus
Rι
(1 (1-8) B) < exp(erm))
A - p/
2
A.((()
Then
(9( - pl
2 po > (1 - (1- exp(-enn).
A,G(
Since 1p - p > Ryp" the two events {p |B - po1
Ry p and {p : 1B - pl < Rg
2
pp
are
disjoint, which implies
[ - -pl
Rn 0o
|(()) - p71 < hnp0 pp < pB.
Rn
P a.G(()
<
P A.G(()
Therefore, we have B (1- (1- ;)2 exp((xerr)) As result, we need to have 17 Q
log(p) em
Thus
have
R Rlog(f)p
1p - p'l >
En
Since pd > p', follows that
R llg((B)p
pp - p'l > Q
en
which finishes the proof.
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have formal proofs for what we claim in the abstract and introduc-
tion.
Guidelines:
The answer NA means that the abstract and introduction do not include the
claims made the paper.
The abstract and/ / /r introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize to other settings.
is fine include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We prove matching upper and lower bounds of error rate. We show polynomial running time of our algorithm.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., the approach was only tested on few datasets results often depend on implicit assumptions, which should be articulated.
with few runs. In general, empirical
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to- system might not be used reliably provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
41

---

Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer: [Yes]
Justification: We state everything formally and provide full proofs. When we say something intuitive and informal, we always have formal counterparts in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be com- plemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution a dataset and /or model, the authors should describe the steps taken to make their results reproducible
verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways, For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or way to reproduce the model (e-g., with an open-source dataset or instructions for how to construct the dataset).
42

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-souree models, it may be that access to the model limited some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.
ssi onPolicy) for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submis- sion /utpg httpp//accc.ciiieee/oooooooiiiio for more details.
(https://nips.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data,
and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g,, data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This is theoretical paper that does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA]
Justification:
This is theoretical paper that does not include experiments.
43

---

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 ttent 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 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.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 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 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.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: This is 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:://eeurippeeeeeeeeee htteuripp..cccuubbll///ticciiiii
Answer: [Yes]
Justification: The authors conform, in every respect, with the NeurlPS Code of Ethics while writing this paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e-g., there a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
44

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper on random graph estimation that does not have societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness con- siderations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security consider- ations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technol- ogy is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g,, gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release
releass of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: This is theoretical paper that does not poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
45

---

Justification:
This is a theoretical paper that does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This a theoretical paper that does not involve new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/ codee/cco//////// modd//model model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: This is a theoretical paper that does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
46

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/ prrovaa/reeviww review based on the requirements your country or institution) were obtained?
Answer: [NA]
Justification: This is theoretical paper that does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS
Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "A9Sd38xJnP", "reviewer": "Reviewer_ikor", "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.\n\nThe paper considers a node-private robust flavor of the question, however:\n\n1. 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.)\n\n2. 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.)\n\nThe 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.\n\nAdditionally, the paper gives an extension of the result to non-homogeneous random graphs.", "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": "No limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a technically impressive achievement with the paper combining many desirable properties of algorithms for a natural toy problem. This is an interesting result for anyone studying private estimation and private release of graph parameters.", "weaknesses": "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.\n\nThe algorithm may be difficult to implement and run in practice due to the complexity of tools used, which include semidefinite programming.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1:**\n> 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.\n\n**Response 1:**\nIndeed, developing realistic and mathematically tractable random graph models is an important and long-standing question in the field. \nOur algorithm and theoretical analysis extend to more general graphs in the following aspects:\n\n- In the paper, we extend our algorithms and theoretical guarantees for the much more general inhomogeneous random graph models, where we make minimal assumptions beyond the independence between the edges. \nAlso, since our algorithm is robust under node corruption, the guarantees will still hold even under minor dependence between the edges in the graph. \n    \n- Moreover, we expect that the guarantees of our algorithm easily extend to graphs with bounded maximum degree and bounded spectral radius, which goes beyond the setting where the edges in the graph are independent.\nParticularly these assumptions are easy to test given the graph instance.    \n\nTherefore, our work can be viewed as a first step towards private and efficient algorithms for statistical estimation in more realistic graph models.\n\n\n**Comment 2:**\n> The algorithm may be difficult to implement and run in practice due to the complexity of tools used, which include semidefinite programming.\n\n**Response 2:**\nWe completely agree that it remains a fascinating and important open question to obtain algorithms for this problem that are more practical or at least have better running times, ideally nearly-linear time.\nOur theoretical work shows that polynomial-time algorithms for this problem exist and that there are no complexity-theoretic obstacles toward practical algorithms.\nWe believe that such basic, polynomial time solvable problems ought to have practical algorithms. \nWe hope that some of the ideas behind our algorithm could pave the way toward such practical algorithms for this basic problem.\n\n\n**Question 3:**\n> 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?\n\n\n**Response 3:**\nNo, our algorithm does not need to know $Q^{\\circ}$. We assume there is an unknown $Q^{\\circ}$. Given a graph generated by $Q^{\\circ}$, our goal is to estimate the average of the entries in the matrix $Q^{\\circ}$.\nThe privacy cost of our algorithm is $\\frac{R \\log n}{\\epsilon n}$ where $R$ is the ratio between the largest entry of $Q^{\\circ}$ and the average of $Q^{\\circ}$. \nFor $Q^{\\circ}$ equal to a graph adjacency matrix, we have $R=1/p$ where $p$ is the edge density of the graph.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GZIIjZpTIL", "reviewer": "Reviewer_ZgW7", "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.", "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?\n\n2) Is there prior work on robust estimation of general inhomogeneous random graphs, and if so, what rate was achieved?\n\n3) Can we hope to extend the privacy lower bounds (Theorem 1.5 and 1.8) to (epsilon, delta)-DP and not just epsilon-DP?\n\nMinor comment: \nline 188: should d^\\circ be defined as (n-1) p^\\circ instead of n p^\\circ?", "limitations": "Yes, adequately addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "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.\n\nFor 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question 1:**\n> How does the rate achieved for inhomogeneous random graphs compare to the rate achieved by the exponential-time algorithm of [BCSZ18] for graphons?\n\n**Response 1:**\n[BCSZ18] uses the Laplace mechanism for edge density estimation of graphons. \nThe privacy cost of their algorithm is $\\mathrm{polylog}(n) R/(\\epsilon d)$, significantly worse than $\\mathrm{polylog}(n) R/(\\epsilon n)$ in our result.\n\n\n**Question 2:** \n> Is there prior work on robust estimation of general inhomogeneous random graphs, and if so, what rate was achieved?\n\n**Response 2:**\nTo the best of our knowledge, no previous work had studied robust estimation of general inhomogeneous random graphs.\n\n\n**Question 3:** \n> Can we hope to extend the privacy lower bounds (Theorem 1.5 and 1.8) to (epsilon, delta)-DP and not just epsilon-DP?\n\n**Response 3:**\nOur proof of the $\\epsilon$-DP lower bound uses a packing argument. Packing arguments can also be used to prove ($\\epsilon$,$\\delta$)-DP lower bounds, but they usually would not result in meaningful ($\\epsilon$,$\\delta$)-DP lower bounds.\nA standard and powerful tool to prove ($\\epsilon$,$\\delta$)-DP lower bounds is the so-called fingerprinting technique [BUV14], which is totally different from packing arguments.\nWe expect some non-trivial work is needed to prove meaningful ($\\epsilon$,$\\delta$)-DP lower bounds for this problem.\nThis is an interesting open question.\n\n\n**Comment 4:**\n> line 188: should $d^\\circ$ be defined as $(n-1) p^\\circ$ instead of $n p^\\circ$?\n\n**Response 4:**\nThank you for pointing this out.\nWe define $d^\\circ = n p^\\circ$ just for notational convenience. \nStrictly speaking, the expected average degree should be $(n-1) p^\\circ$ instead of $d^\\circ$.\nHowever, these two quantities are equivalent as $(n-1) p^\\circ = \\frac{n-1}{n} d^\\circ$.\n\n**Reference:**\n- [BUV14] Bun, Mark, Jonathan Ullman, and Salil Vadhan. \"Fingerprinting codes and the price of approximate differential privacy.\" Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014.\n- [BCSZ18] Borgs, Christian, et al. \"Revealing network structure, confidentially: Improved rates for node-private graphon estimation.\" *2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)*. IEEE, 2018.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HH9N3x8qw6", "reviewer": "Reviewer_teKp", "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.", "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": "There was no explicit discussion regarding the limitations of this work in the main body.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main result of the paper is novel and significantly advances the area of DP algorithms for estimating graph parameters in random graphs.", "weaknesses": "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.\nGeneral 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment 1:**\n> You should define the quantity edge density formally somewhere since the whole paper hinges on the reader understanding what it is.\n\n**Response 1:**\nThank you for pointing it out! We will add a formal definition in our proceedings version.\n\n\n**Question 2:**\n> 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.\n\n**Response 2:**\nThis is a great question. We will discuss in more detail in the proceedings version.\n- [HKMN23] and [AUZ23] showed a general connection between privacy and robustness. In general, this connection does not provide guarantees in terms of computational complexity. However there are several important examples where this connection can be used to transform efficient robust algorithms to efficient private algorithms.\n- 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 an iterative algorithm [AJK+22]. For such algorithms not based on convex relaxation, it is completely unclear how to use the aforementioned connection between privacy and robustness estimation toward an efficient private algorithm.\n- We cannot just apply previous robust mean estimation algorithms based on sum-of-squares (e.g. Hopkins et al 2024). On the one hand, if we view edge density estimation as a one-dimensional Bernoulli mean estimation task, then previous algorithms are only optimal under edge corruption, but suboptimal for the node corruption model. On the other hand, if we view edge density estimation as an $n$-dimensional mean estimation task, then samples (i.e. rows of the adjacency matrix) are not independent.\n- In general, when designing a sum-of-squares algorithm, the main challenges are identifying the right set of polynomial constraints and coming up with sum-of-squares proofs.\n\n\n**Reference:**\n- [AJK+22] Acharya, Jayadev, et al. \"Robust estimation for random graphs.\" *Conference on Learning Theory*. PMLR, 2022.\n- [HKMN23] Hopkins, Samuel B., et al. \"Robustness implies privacy in statistical estimation.\" *Proceedings of the 55th Annual ACM Symposium on Theory of Computing*. 2023.\n- [AUZ23] Asi, Hilal, Jonathan Ullman, and Lydia Zakynthinou. \"From robustness to privacy and back.\" *International Conference on Machine Learning*. PMLR, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D5HuLPqOqZ", "reviewer": "Reviewer_Se7o", "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).", "questions": "1. Is it possible to design algorithms when the entries of the connection probability matrix are not independent?\n2. Do any algorithmic ideas translate to other graph statistics like the number of triangles and k-stars?", "limitations": "Limitations and negative social impact are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical results are very strong. The authors prove matching (up to logarithmic factors) error bounds for both Inhomogeneous and Erdos-Renyi graphs. The algorithms are polynomial-time.\n2. The techniques are interesting. The authors use recent results for the connection between privacy and robustness. To design a time-efficient algorithm, the authors go beyond simple reduction from privacy to robustness and apply the sum-of-squares method.\n3. The paper is well-written.", "weaknesses": "There is no obvious weakness with regard to the results and technical parts of the paper. The only minor weaknesses are the problem formulation.\n1. 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.\n2. The algorithm only works for edge density estimation. There should be many other interesting graph statistics, even on the Erdos-Renyi graph.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question 1:**\n> Is it possible to design algorithms when the entries of the connection probability matrix are not independent?\n\n**Response 1:**\nYes, our algorithm guarantees can extend to some settings where the edges in the graph are not independent:\n\n- As our algorithm is robust under node corruption, the guarantees still hold even under minor dependence between the edges in the graph. \n- Moreover, we expect that the guarantees of our algorithm easily extend to graphs with bounded maximum degree and bounded spectral norm, as we only exploit these properties of the graph for adding constraints to the sum-of-squares semidefinite programming.\n\nThese assumptions are easy to test given the graph instance, and are significantly weaker than the independence assumption.   \n\n\n**Question 2:**\n> Do any algorithmic ideas translate to other graph statistics like the number of triangles and k-stars?\n\n**Response 2:**\nThis is a great question. \n\n- For Erdos-Renyi random graphs, as the only parameter for the distribution is the edge density $p^\\circ$, we can obtain non-trivial (and potentially optimal) guarantees for estimating the number of triangles/k-stars by relating the expectation to $p$. \n- For inhomogenous random graphs, we are not so sure. We expect our techniques can lead to private algorithms for counting constant-size subgraphs such as triangles and k-stars with non-trivial guarantees, when the inhomogeneity (measured by the ratio between the maximum edge connection probability and the average edge density) is bounded. \nThe observation is that, when a small $\\eta$-fraction of the nodes are corrupted, the number of triangles/k-stars in a large induced subgraph of the given corrupted graph with bounded degree and supported on $(1-\\eta)n$ vertices is still close to the total number of triangles/k-stars in the original uncorrupted random graph.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X1r8MgGdUa", "reviewer": "Reviewer_97Rf", "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.\n\nTo 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.", "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?\n2. 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": "This paper discusses several limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Graph parameter approximation under node-level privacy is an important topic, and this paper gives optimal algorithm with a polynomial time implementation by sum-of-squares relaxation, under the most natrual setting of random graphs.\n2. Their techniques of using sum-of-squares method for exponential mechanism is sophisticated.\n3. All theorems are clearly stated and technically correct.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question 1:**\n> 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?\n\n**Response 1:**\nOn the one hand, the algorithm in [CDd+24] uses an edge density estimation algorithm based on [SU19] as a preprocessing step and proceeds by an sum-of-square exponential mechanism to privately estimate the underlying graphon.\nConcretely for the task of edge density estimation, [CDd+24] does not improve over [SU19] and uses in fact the same algorithm as [SU19].\nTo improve the edge density estimation results in [SU19], we developed a new private edge density estimation algorithm using the sum-of-squares hierarchy, which is completely different from the techniques in [SU19] based on smooth sensitivity. \n\nOn the other hand, although [CDd+24] also relies on the sum-of-squares exponential mechanism for graphon estimation, our program constraints and identifiability proof are significantly different. \nThere are two particularly notable technical differences:\n\n- Our strategy is closely related to the reduction from robustness to privacy framework developed in [HKMN23], while [CDd+24] relies on sum-of-squares Lipshitz extensions. \n- The private graphon estimation algorithm in [CDd+24] relies on a single sum-of-squares program, while our algorithm has two stages: the rough estimation and the fine estimation, each with a different sum-of-squares program. The reason is that we found it difficult to achieve nearly optimal error rate using a single sum-of-squares program.\n\n**Question 2:**\n> 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.]?\n\n**Response 2:**\nWe will add more discussion about the results in [CDd+24] in our proceedings version.\nFor the task of edge density estimation, [CDd+24] actually does not make use of any structure specific to stochastic block random graphs, but just treat them as inhomogeneous random graphs.\nSo [CDd+24, Lemma 4.10] is essentially a result on edge density estimation of inhomogeneous random graphs.\nThe algorithm behind [CDd+24, Lemma 4.10] uses an edge density estimation algorithm based on [SU19].\nThe error bound stated in [CDd+24, Lemma 4.10] is actually only the privacy cost. The total error bound of [CDd+24, Lemma 4.10] should also include the non-private error which is the same as the non-private error in our Theorem 1.6.\nIn terms of privacy cost, our Theorem 1.6 actually improves over the guarantees of Lemma 4.10 in [CDd+24].\nMore specifically, the privacy cost of [CDd+24, Lemma 4.10] is\n$$\n    |{\\hat{\\rho}-\\rho}|^2 \\leq \\tilde{O} \\left(\\frac{R^2\\rho^2}{\\epsilon^2 n^2}+\\frac{1}{\\epsilon^4 n^4}\\right) .\n$$\nIn comparison, our Theorem 1.6 gives a privacy cost of\n$$\n    |{\\hat{\\rho}-\\rho}|^2 \\leq \\tilde{O} \\left(\\frac{R^2\\rho^2}{\\epsilon^2 n^2}\\right) .\n$$\n\n\n**Reference:**\n\n- [CDd+24] Chen, Hongjie, et al. \"Private graphon estimation via sum-of-squares.\" Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.\n- [SU19] Ullman, Jonathan, and Adam Sealfon. \"Efficiently estimating erdos-renyi graphs with node differential privacy.\" Advances in Neural Information Processing Systems 32 (2019).\n- [HKMN23] Hopkins, Samuel B., et al. \"Robustness implies privacy in statistical estimation.\" Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are very grateful to all reviewers for constructive feedback.
We will incorporate these helpful suggestions into the proceedings version of our paper.

**Question:**
What is the key conceptual contribution of our paper, compared to previous work [BCSZ18] and [SU19]?

**Answer:**
[BCSZ18], [SU19] and our work all consider $\epsilon$-differentially node private algorithms for edge density estimation under Erdos-Renyi graph distribution $\mathbb{G}(n,d^\circ/n)$. 

- The privacy cost of [SU19] is negligible when $\epsilon \gg (nd^\circ)^{-1/4}$. In comparison, the privacy cost for our algorithm is negligible when $\epsilon \gg n^{-1/2}$, which is a significantly wider privacy parameter range. Our guarantee matches that of the exponential-time algorithm in [BCSZ18].

- [BCSZ18], [SU19] and our work use different techniques. [BCSZ18] uses a generic Lipschitz extension based on exponential mechanisms. [SU19] uses the smooth sensitivity technique. Our work uses the sum-of-squares exponential mechanism. 

- [SU19] can only exploit the degree concentration property of Erdos-Renyi graphs. In fact, the privacy cost of [SU19] is optimal on degree-concentrated graphs and thus cannot be further reduced. The reason why our algorithm can surpass their lower bound is that our algorithm can also make use of spectral norm. More specifically, we exploit the property of Erdos-Renyi graphs that the spectral norm of centered adjacency matrix is bounded by $\tilde{O}(\sqrt{d})$. Note for graphs with maximum degree $d$, the centered adjacency matrix can have spectral norm as large as $\Omega(d)$.

- Moreover, we show that the privacy cost of our algorithm is information-theoretically necessary (up to a $\log n$ factor). In this sense, our result is nearly optimal. 

- We also extend our results to the inhomogenous random graph models, improving the results from [CDd+24].
 
**Reference:**

- [BCSZ18] Borgs, Christian, et al. "Revealing network structure, confidentially: Improved rates for node-private graphon estimation." 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018.
- [SU19] Ullman, Jonathan, and Adam Sealfon. "Efficiently estimating erdos-renyi graphs with node differential privacy." Advances in Neural Information Processing Systems 32 (2019).
- [CDd+24] Chen, Hongjie, et al. "Private graphon estimation via sum-of-squares." Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.

Meta-review: 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).
Decision: Accept (spotlight)