Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Authors: Hongjie Chen
Jingqiu Ding
Yiding Hua
Stefan Tiegel
Venue: NeurIPS 2025 poster ()
Keywords: Robust statistics
random graph estimation
sum-of-squares
Primary area: theory

Abstract: We study the problem of robustly estimating the edge density of Erdos Renyi random graphs $\mathbb{G}(n, d^\circ/n)$ when an adversary can arbitrarily add or remove edges incident to an $\eta$-fraction of the nodes.
We develop the first polynomial-time algorithm for this problem that estimates $d^\circ$ up to an additive error $O\left({[\sqrt{\log(n) / n}  + \eta\sqrt{\log(1/\eta)} ] \cdot \sqrt{d^\circ} + \eta \log(1/\eta)}\right)$.
Our error guarantee matches information-theoretic lower bounds up to factors of $\log(1/\eta)$.
Moreover, our estimator works for all $d^\circ \geq \Omega(1)$ and achieves optimal breakdown point $\eta = 1/2$.

Previous algorithms [Acharya et al 2022, Chen et al 2024], including inefficient ones, incur significantly suboptimal errors.
Furthermore, even admitting suboptimal error guarantees, only inefficient algorithms achieve optimal breakdown point.
Our algorithm is based on the sum-of-squares (SoS) hierarchy.
A key ingredient is to construct constant-degree SoS certificates for concentration of the number of edges incident to small sets in $\mathbb{G}(n, d^\circ/n)$.
Crucially, we show that these certificates also exist in the sparse regime, when $d^\circ = o(\log n)$, a regime in which the performance of previous algorithms was significantly suboptimal.

Improved Robust Estimation for Erdós-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Hongjie Chen
Jingqiu Ding
ETH Zürich
ETH Zürich jingqiu. www.ddii..nnnnieeeemee ethz.
hongjie. cww.eeenceeencccccmm ethz.ch
Yiding Hua
Stefan Tiegel
ETH Zürich yiding. www.whf.. ethz.ch
ETH Zürich stefan. tiefen.tiegeliine wta.....ttzcch
Abstract
We study the problem of robustly estimating the edge density of Erdós- Rényi random graphs G(n, d d'/n) when an adversary can arbitrarily add or remove edges incident to an n-fraction of the nodes. We develop the first polynomial-time algorithm for this problem that estimates d' up to an additive error O([Vlog(n)/n + 7//ogg(/n)] væ + log(1 /n)) Our error guarantee matches information-theorete lower bounds up factors of log(1/n). Moreover, our estimator works for all d > Q(1) and achieves optimal breakdown point 7 1/2.
Previous algorithms [A]K*22, CDHS24), including inefficient ones, incur significantly suboptimal errors. Furthermore, even admitting suboptimal error guarantees, only inefficient algorithms achieve optimal breakdown point. Our algorithm is based on the sum-of-squares (SoS) hierarchy. A key ingredient is to the number of edges incident small sets in G(n, d /n). Crucially, show that these certificates also exist in the sparse regime, when d o(log f1), a regime in which the performance of previous algorithms was significantly suboptimal.
constant-degree SoS certificates for concentration
1 Introduction
We study the problem of estimating the expected average degree of Erdós-Rényi random graphs under node corruptions. The Erdós-Rényi random graph model [Gil59, ER59 is fundamental statistical model for graphs that has been extensively studied for decades. This model has two parameters: the number of nodes (n) and the degree parameter (d") and is denoted by G(n, d' /n). It is a distribution over graphs with n nodes where each edge is sampled independently with probability d' /n. Note that every node in G(n, d' /nn) has the same expected degree (1 (1-1/n) d The most fundamental statistical task in Erdós-Réme Rényi random graphs the following: given a graph sampled from G(n, d' /n), find an estimate for the ground truth parameter dº, It is well known that the empirical average degree achieves the information-theerriien optimal error rate la d o @(Vlog(n)/n Vdo).
Throughhut this paper, the statistical utility guarantees we state hold with probability 1 1/poly(n) the randomness of both the input graph and the algorithm, if not otherwise specified.
39th Conference Neural Information Processing Systems (NeurIPS 2025).

---

Although many phenomena in network analysis are captured by Erdós-Rényi random graphs, the distributions of real-world networks can deviate significantly from such a basic model. This may tremendously impact the performance of algorithms that are tailored too much towards the Frdós-Rénn" model. In particular, this already occurs for the very basic task of estimating the expected average degree, which is also the task we focus on in this work. Simple estimators such as the mean or the median of all degrees, or variations thereof, are known to fail drastically even when perturbing edges incident to few of the nodes [2].* This motivates the study of robust estimation algorithms for random graphs. Following [AJK*22, CDHS24] we study robust estimation for Trdōs--éény random graphs under node corruptions, defined as follows.
Definition 1.1 (n-corrupted Erdós-Rényi random graphs). For 17 [0, 1], an r--oorupted Erdós-Rényi random graph is generated by first sampling graph from G(n, d /n), and then adversarially picking an n-fraction of the nodes and arbitrarily adding and removing edges incident to them.
Given the corruption rate 1 and observation of an n--orrupted Erdós-Rényi random graph, the goal is to estimate the edge parameter d'.
Previous work. While this a seemingly simple one-dimensional robust estimation problem, in the work that initiated this line of research, [AJK 22] showed that many standard robust estimators, such as the median estimator, and their natural variants, such as the truncated median estimator, provably incur very suboptimal errors. On high level, this occurs because the degrees of the uncorrupted graphs are not independent and further, because the adversary can change all of them by just corrupting single node. On the other hand, if we do not consider any structural properties of the node corruptions and treat the problem as that of robustly estimating the parameter of a Bernoulli distribution, this can at best get error nn². In [A]K*22], they gave a polynomial-ting
algorithm that achieves an error rate of O (I (I//oogm))/n +1 + /log(1/1)))) - log 11) when 17 < 1/60.3 3 Note that the term vlog n/ Vd= is information- theortticall necessary even in the non-robust case. Additionally, [AJK*22] gave a companion lower bound, showing that anformation-theoretiaall no algorithm can achieve an error rate better than Q( max(n ..)).
Sparse regime. It might seem that the error rate of [A]K*22] is only worse than the optimal by logarithmic factors. However, because of this, it fails to provide any non-trivial statistical guarantees in the sparse regime. For example, when do < log n and r = (2(1,, their error bound is (17 log n)) which is much larger than the ground truth parameter d'.
Notice that, for statistical estimation problems random graphs, it is often the case that sparse graphs are more difficult than dense graphs, such as community detection in stochastic block models [FO05, GV16, LM22, DdHS23]. When d o(log n),, Erdös-Rényi random graphs behave fundamentally different than when d' > Qllog n), and usually new algorithmic and proof ideas are required. When d > Q(log n), the graph rather regular in the sense that every vertex has degree (1 # e)d for a small constant &, and the spectrum of the adjacency matrix concentrates nicely around its expectation: || EAAl = O(Vdo ) (See e.g. [FO05].) However, when d = o(log n), significant number of vertices have degree (dd). In particular, when d a constant, there are vertices of degree Q(log n /log log n)) [KS03), As result, the spectral norm of the centered adjacency matrix is Q2log n /looglog
The first step towards robust edge density estimation for sparse random graphs was made in [CDHS24]. They proposed a polynomial-time algorithm that estimates d' up to an additive error of d' /110 when 17 is at most some sufficiently small constant that is much smaller than 1/2. However, their statistical guarantees are suboptimal when d' grows with nt, e.g. d log log n, since the estimator does not achieve o1) approximation ratio for estimating d=
g
Even in the easier corruption model in which each sample is drawn from Ber( d with probability 1 - and some error distribution with probability n, it is not possible to get error better than 7n (note that the adversary can simulate this model up to constant shifts in 17).
Prrevious works [AJK' 22, CDHS24] use a different parametrization G(r, and consider the task of estimating the edge density parameter pº. Since pa and d' differ by known factor of π1, these two parameterizations are equivalent.
2

---

Optimal breakdown point. Besides optimal error rates, another desirable feature of robust estimation algorithms is high breakdown point. In the node corruption model, the breakdown point of an estimator is defined to be the minimum fraction of nodes to corrupt such that the estimator cannot give any non-trivial guarantees. For the robust edge density estimation problem, it is easy to see that any estimator has breakdown point at most 1/2, as an adversary can make G(n, 0) and G(n, 1) indistinguishable half the nodes. In [AJK*22], they provide an exponential-time algorithm achieving the optimal breakdown point 1/2 with error rate O(Vd + /). Note that this error rate is quite suboptimal, it does not recover the non-robust case when there are no corruptions, and does not provide any non-trivial guarantee in the sparse regime. On the other hand, previous polynomial-ting algorithms [AJK*22, CDHS24] can provably work only when the corruption rate is at most some sufficiently small constant bounded away from 1/2.
allowed to corrupt
To summarize, current algorithms, including inefficient ones are far from the information- theoretic lower bound. This holds, even when allowing suboptimal breakdown points. Furthermore, all known efficient algorithms are both far from known lower bounds and have suboptimal breakdown points. This leads us to the following question:
Can polynomial-time algorithms achieve error rates matching the information-theoreti lower bound? If so, can polynomial-time algorithms simultaneously achieve optimal breakdown point 1/2?
We answer both questions affirmatively in this paper, up to factors of log(1/1) in the error rate.
1.1 Results
We give the first polynomial-time algorithm for node-robust edge density estimation in Erdös-Rényi random graphs that achieves near-optimal error rate and reaches the optimal breakdown point 1/2.
Theorem 1.2 (Informal restatement of Theorem C.1). For any 0 & π < 1/2 and de > 1, there exists polymomialltime algorithm which, given n and a graph that is an n-corruption of an Erdōs-Rényi random graph sampled from G(n,d=/n) outputs an estimator à satisfying
log(n)
p d
+ 7 log(1/n)
Nd + 7lgg(1/1))
with probability at least 1/poly(n).
We make few comments on the statistical guarantee of our algorithm. Our error rate is optimal up to the log(1/1) factor, as any algorithm must incur an error of ((max .n)) [A]K*22]. In comparison, the error rate achieved by [A]K* ((LVVogfm///+n//ooo(( Vd + log r),, which worse than ours in every parameter regime. The error rate achieved by [CDHS24] is Odd),, which is worse when 17 is small; in particular, it does not recover the non-robust case when 0.
The condition on d' can be relaxed to d > for arbitrary positive constant c. We remark that the condition d' > Q(1) is information-theoreiilllly necessary if we want non-trivia guarantees for constant 17, as when d' o(1) most nodes will be isolated with high probability and the adversary can erase all edges, removing all information about d=
We leave it as an open question whether the factor of log(1/7) is inherently necessary, at least for polynomial-time algorithms. We remark that the lower bound in [A]K*22] is for oblivious adversaries, that are not allowed to see the uncorrupted graph before choosing their corruptions. Whereas we consider adaptive adversaries, that have full knowledge of the underlying graph. For other rob statistical inference problems, there are known separatiis between these models. In particular, for robustly estimating the mean of a high-dimensional
4 "This result does not state the dependence on 1 when 17 is small.
3

---

Gaussian, there are polynomial-time algorithms that achieve error O(7) against oblivious adversaries [DKK*18]] 18]. But against adaptive adversaries, there are statistical query lower bound suggesting that obtaining error better than ((0]/og(11/)) takes super-polynomial time [DKS17].
As observed in [AJK' 22] the key property that makes the edge density estimation problem challenging is the dependencies among the degrees of vertices. Indeed, consider the related, but much simpler, problem, in which are given и points that are i-corruption of i..d. samples from Binomial distribution with parameters n and d //. In this setting, the marginal distribution of each uncorrupted sample is the same in our setting, but there are no dependencies between samples. It is not too hard to show that in this setting, the median
estimator obtains error (1))d") with probability last exp(-172n (for completeness, we give a proof of this fact in Appendix D). Our main theorem shows that we can obtain the same guarantees up factor of Vlog(1/n) in the graph setting (in most parameter regimes).
1.2 Notation
We introduce some notations used throughout this paper. We write f & g to denote the inequality f & C. g for some absolute constant C > 0. We also use the standard asymptotic notations Ó(f) and (ff) for upper and lower bounds, respectively. Random variables are denoted using boldface symbols, e.g., X, Y, Z. For matrix M, we use || op for its spectral norm and || | for its Frobenius norm, and let d(M) denote its average row row/column sum, iee d(M) == Σ., My/nn. Let and 0 denote the all-one and all-zero vectors, respectively. Their dimensions will be clear from the context. We use 11-112 for the 2-norm of vectors. For any matrices (or vectors) M, N of the same shape, we use MO N to denote the element-wise product (aka Hadamard product) of M and N. We use G to denote graph and A = A(G) for its adjacency matrix, interchangeably, when the context is clear. Given graph G and subset S of nodes, let ec(S) denote the number of edges in the subgraph induced by S and let ec(5, 5) denote the number of edges in the cut (S, When the graph G is clear from the context, we might drop the subscript and write e(S) and S),
1.3 Organization
The rest of the paper is organized follows. In Section 2, we give technical overview of our results. In Appendix C, we present our main algorithm and the detailed proofs. In Appendix A, we provide some sum-of-squares background, including basic sum-of-squares proofs used in our paper. In Appendix B, we prove concentration inequalities that are used in our proofs. In Appendix D, we prove statistical guarantees of median for robust binomial mean estimation.
2 Techniques
Our algorithm follows the so-called proofs-to-llorittmn framework based on the sum-of- squares (SoS) hierarchy of semidefinite programs. This framework has successfully been applied to a wide range of robust estimation tasks such as robustly estimating the mean and higher-order moments, robust linear regression, learning mixture models, and many more [KSS18, HL18, KKM18, BP21]. We refer to [RSS18] for an overview. In this framework, one first constructs a proof of identifiability of the model parameters. This already leads to an inefficient algorithm. If additionally, this proof is captured by the SoS framework, we directly obtain an efficient algorithm with the same error guarantees.
Our work thus consists of two parts: First, constructing a "simple" proof of identifiabilyy and second, showing that it can be made efficient using the sum-of-squares hierarchy. We discuss the proof of identifiability in Section 2.1 and then construct the necessary SoS proof in Section 2.2. Section 2.3 we discuss how our approach relates to prior works. Compared
Formally, they work for the so-called Huber contamination model.

---

to previous works, our proof is surprisingly simple, and we will be able to discuss it almost entirely in this section. We also view this strength of our work.
2.1 An inefficient algorithm via identifiability
The first part of our results is to find proof of identifiability that lends itself to the "proofs- to-algorithms" paradigm. This approach different from previous works and key part of our work. In particular, it requires to identify a certain "goodness" condition that captures the essence of the problem. The inefficient algorithm based on this identifiability argument already surpasses the state-of-the-ard among inefficient a algorithms.
Denote by G the uncorrupted graph and denote by d(G its empirical average degree. For brevity, denote sem == n/ n/log(1/n)Vd + 17 /)g))(/)). Since with probability 1 1-1 -1/poly(n), holds that (d( d'I < O( Oyloogn))n Vd²), it is enough to estimate d(G") up to error (6 For the rest of this section will focus this task.
Our proof of identifiability follows the same line of reasoning as in many recent works (algorithmic) robust statistics: If two datasets from some parametric distribution have first, large overlap and second, both satisfy an appropriate " "goodness" condition, their underlying parameters must be close. The "goodness" condition also needs to hold for the uncorrupted dataset with high probability. This approach underlies algorithms for robust mean estimation, clustering mixture models, robust linear regression, and more." 6 This immediately yields inefficient algorithm: Enumerate over all possible alterations of the data that still have large overlap with the input and check if they satisfy the condition. If yes, output empirical estimator for the parameter wish to estimate, e.g., the empirical mean.
In our setting, the datasets are graphs on nodes and large overlap refers to one graph can be obtained by arbitrarily modifying the edges incident to at most 1n nodes. We refer to two such graphs as n-close.
Concentration of edges incident to small sets as goodness condition. We next describe our goodness condition and how it leads to a proof of identifiability, and thus an inefficient algorithm. The idea behind our goodness condition is strikingly simple: Let G and G' be two graphs that are clooo and let be the set of node which they disagree. We denote by ec(S), ec(S, S) the number of edges of the subgraph induced by S and the number of edges in the cut induced by S (i.e., between S and 5), respectively. When the graph G is clear from context, we omit the subscript. Consider the difference in their empirical average degree,
(d(()) - d(G')) (ea(S) + ea(S, 5) - eG) es,
Note that the difference only depends on edges incident to the set S. Now, for G coming from G(n,d' /n), we know that this number is tightly concentrated around 1" (1) + d" [n - |S]) In particular, this holds for any set S of this size. If the same were true also for both G', the expectation terms would cancel out and only the fluctuation remains, which would indeed be small enough. Thus, our goodness condition is exactly requiring this concentration property, replacing d' by the empirical average degree of the graph."
Formally, denote by N(S) = (09) + +IS[(n -
the maximum number of possible edges in the subgraph and cut induced by S. We require the following.
Definition 2.1 (5-good graphs). Let be graph on n nodes. We say that G is ö-good, if for every subset S C [n] of size at most qn, it holds that
(c(S)) ec(S, A(G). N(S) & &nn
nn.
(2.1)
The parameter d may depend on G.
in many of these cases the goodness condition bounded moments, or related conditions.
This is reminiscent of the notion of resilience, which is the goodness condition underlying robust mean estimation for distributions with bounded moments.

---

Denote by d(G) / (lg()/) By a Chernoff bound and union bound over all sets of size at most 1nи, it can be shown that if G G(n, d. dn/dd)) then G is ((G) with probability at least 1 - 1/poly(n) (cf. Lemma B.4). Further, nō(G) = O(éer)) with at least the same probability (in the latter d(G) is replaced by d³).
Identifiability. We next claim that this leads to identifiability; In particular, if G and are 211close and ö(G) and Ó(G') good then Id(G) d(G')) & O( Note that this immediately gives an inefficient algorithm with error rate (δ Simply enumerate over all graphs G that are s--close to the input and if one of them is good, output the empirical average degree. Since this search includes the uncorrupted graph, this is successful with probability at least 1 - 11) Further, any "good" graph that we find is 21p-close to the uncorrupted graph. then follows that
- d(G')l ec((S) + ec(s, eG.(S) - SS S)
ec(S) + es( -
AIG') N(S) C ec(s 4G
N(S)
|d(G)) - N(S)
(2.2)
n²
Since S has size most 27, follows that our goodness condition yields that
1
{ (1122)) Rearranging and applying N(S)
(1 (1-2n)))d()) d(G') < 2nd(G) + 2n0(G")
=0 (o(llog(1//)
[/l[c)+ (1rlog(1/1)),
which is the guarantee we aimed for up the (d') term. Let y (1 2n1
100
Using the
AM-GM inequality and d(G) > 1", it follows that
d(G') d(G) d(G)
Vyd(G)+ d(G) < (d(G)) + (1+y)d(
Vyd(G)
Taking square roots and using that vx+y < vx vy, it follows that
(1 (1-2n) ld(G) - d(G') + 20
Vd(G
(1 (1-21)) 21) Vd((G)
10
Plugging this back into Eq. (2.2) yields
IVlog(1/n) vd(G)
n (log(1/1)
M(G))d((G') x
(1 (1-2n)4
(1 (1-21)²
For any 7) strictly bounded away from 1/2, this indeed O(šer), also showing that our @ breakdown point is 1/2.
2.2 An efficient algorithm via sum-of-squares
We next describe how to design an efficient algorithm using the -f--uuuqqss framework. This algorithm will inherit the error rate and optimal breakdown point of the inefficient algorithm, proving Theorem 1.2.
A key part of the analysis of the inefficient algorithm was to show that the goodness condition holds with high probability for the uncorrupted graph, such that we can guarantee the exhaustive search over all clclose graphs to our input is successful. On a high level, if we additionally require that there is a certificate of goodness in the uncorrupted case, we can replace the exhaustive search of the inefficient algorithm by an SDP that we can solve in
8 For simplicity, the reader may ignore the second part on first read.
Any other constant, potentially smaller than 1, also works.

---

polynomial time. Existence of the certificate then implies that this SDP is feasible. More formally, we will require that there is constant-degree SoS proof of this fact.
turns out that, given this certificate, we can reuse the identifiability proof above in an rate. For this section,
almost black-box way to obtain an algorithm with the same will thus focus mainly on showing existence of this certificate. Towards the end, we will briefly explain how to use this to construct a sum-of-squares recovery algorithm. This section does not assume in-depth knowledge of the SoS proof system. We refer to Appendix A for formal treatment.
In order to describe the certificate, we will first present an algebraic formulation of the goodness condition. Let G G(n, d /n) be graph with node set [n] and A be its adjacency matrix. For set S, let ( (0, 1)" be its indicator vector. Since it will be important later on, we will slightly switch notation and denote the empirical average degree by d(A), instead of d(G), to make clear that it is function of A well. We also denote by (A(A) the degree of node v. Note that
ec(S)+ + ec(s,
Σ dc(() ec(S) =
Σ Wy dA( DE[n]
Let pı(w) = Evdn) (do((A) d(A)) and p2(w) w (A condition holds if and only if for all S of size at most m
A(A) 11T).. Then, the goodness
(pi(wo())) 222((2()))) $ 6(A)2 (nn)²
(2.3)
where we defined 8(A) = O(vlog(1/n)/((A)) log(1 (n)) as before. 10
The certificate is a strengthening of this fact. In particular, consider the following set of polynomial equations in variables W1,..., Wn: (l; = [Vo: w Wp EEp wy & mj) which contains all the (0()) We require that there is so-called SoS proof of Eq. (2.3), in variables w. In particular, we require that the difference between right-hand side and left-hand side can be expressed as a polynomial of the form
11
Σ sr(w)2 + Σ (w - wi) + Σ (w))
n
w
w where Sr, Pi,r', Sy are constant-degree polynomials in w. We denote this by Alabel lom (pi(w()) ())( s 8(A)2 ((p)). All of the proofs in this section will be of constant- degree, so will drop the O(1) subscript.
We will construct this in two parts. Since the SoS proof system captures the fact that (a + b)2 2a² + 2b2, it follows that Alaeel 10 (pi(w) }22(w)) & 2p (w)) + p2(w)3 Since SoS proofs obey composition, it is enough to certify that both (((w) and p2(w)) are at most O(1) (0).)(()222)) (
Upper bounding P1 via concentration of degrees small sets. We start by bounding P1 in SoS. Note that w would correspond to a fixed point in Aas n), i.e., the indicator of set of size at most nn, this would immediately follow from the standard goodness condition.
We construct the necessary SoS proof case by showing that something more general is true: Given n numbers A.,..., An R such that for all S C [m]] of size at most nn it holds that (Eves 2²)2 & B, there exist constant-degres SoS proof of this fact. Lee,
(wa 17)
< B.
O(1)
On high level, this follows by comparing the set indicated by the w, variables to the of the rpn largest a s. The proof only uses elementary arguments inside SoS, such as that
10 Again, since it will be useful later on, switched notation from 8(G) to 8(A).

---

w = wp implies that 0 & W & 1. We give the proof in Lemma A.9. The bound on p1 follows as a direct corollary by picking a, (A) d(A)) for E V (where we identify V with [n]).
Upper bounding P2 via spectral certificates. We next turn to upper bounding p2. A common strategy to show SoS upper bounds on quadratic forms is using the operator norm. Indeed, for a matrix M, the polynomial ||x Mx a sum-of-squares in x since the matrix || 1 M is positive semidefinite and can hence be written LL". Thus, ||] x Mx ||x]|]?
Unfortunately, applying this naively to bound p2 does not work. Indeed, using that Σ w, & nn implies z||l [|
1jn, we can bound
P2(w)= = w (A A(A)
11
A- w < 4AA
a(A) 11 mm.
So we would need the operator norm to be the order of O ((llgg(1/)) ( log(1 (1))). While this is true in the dense case, when d > 1)(lggn) [FO05], this completely fails in the
sparse case: In particular when d = O(1), the operator norm is scales as
log log vd(A)
log
[KS03]. As a consequence, the error guarantees we would obtain would (roughly) be of the
form aa d'1
loga which is very far from optimal when d' = O(1).
loglog
The reason for this failure that the spectral norm is dominated by outlier nodes that have much higher degrees than d'. Yet, there is reason for hope: The associated eigenvectors are very localized and have small correlation with the vectors of the form w that we care about. Indeed, we can apply diagonal rescaling to the centered adjacency matrix that downweighs the effect of such outlier nodes to obtain a more benign spectrum. Concretely, variants of the results in [Le16] (see also Lemma B.6 on how we need to adapt their results), show the following: Let D E R nxn be the diagonal matrix, such that D max do (A) Then, d(A) DDT)D- s vd(A)." "
with probability at least 1 1/poly(n), it holds that D (A2
While promising, this does not come for free and we still have ensure, that the resulting reweighing of our variables does not increase z|a too much. In particular, so far we can show
Ala 1" p2(10) w T((AA
d(A)
11 20
(D11/20) (D-1/22/ A- ALA) 11 D 117)D-112) (D12
<|D-11/2 4(A)
1ID 11
s vd(A)- ( (2.4)
It remains bound 1/222 For this, will use similar techniques in the upper bound of pt. Indeed, expanding the squared-norm and using that w W., we obtain
Alabel(w:)) [| = Σ
w. Doo =
Σ
wy max 1, da(A)
Σ SEV
W +
1
Σ
woda(A)
2d
2d
AEV
DEV
DE
1
< 2nj +
(d) do)
2d
BEV
Note that the last sum is exactly the same in Fı, except that d(A) replaced by d This is a minor difference and we can still apply the same techniques and conclude that the above upper bounded as
log(1/n) d=
/lg((//))
log(1/n) Vod
+ vlog(1/n)
n
$ nm
Vo
11 Instead of rescaling, an alternative approach to ensure better spectral behavior is to delete high-degree nodes [FOU5]. We believe that this approach would likely yield an alternative certificate.

---

Plugging this back into Eq. (2.4) and using that d" = d(A), it follows that
Albel (w; r)
w F p2(W) $ 6(G) np.
Formally, we require an SoS bound on P2(w)² instead. This can be obtained by using that similarly to the upper bound, we also have that | x Mx > M||||| Finally, we can use that {-C < x & C) l x² C2 (cf. Lemma A.8).
Short certificates lead to efficient algorithms. We briefly describe how to turn this into an efficient algorithm. See Appendix C for full details. In particular, consider the following constraint system in scalar-valued variables 2y and matrix valued variable Y. A is the adjacency matrix of the (corrupted) input graph. graph. All but the last constraint (3... ensure that Y is n-close to the input graph (by o we denote entrywise multiplication). The last constraint ensures that satisfies the goodness condition.
the "guess" of SoS for the uncorrupted
20
(z, & nM
0 Y< Y (1- -2) = = (1 z)(1 - 2)
;())=;A,m)
(2.5)
SoS proof,
(w;
(Y 4Y
11 2w11 ww s ((Y)
The constraint Y 11 meant entry-wise. We remark that the last constraint is formally not a polynomial inequality but can be written as such using auxiliary variables. Writing this formally would very much obfuscate what happening and we omit the details for clarity. This technique is by now standard and we refer to, e.g., [FKP+19] for more detail. On high level, one uses auxiliary variables to search for the coefficients of the SoS proof.
The arguments in the previous section show that the uncorrupted graph corresponds to feasible solution (cf. Lemma C.3). Further, an SoS version of the proof of identifiability we have given before shows that (cf. Lemma C.4 for the full version)
V= (d(Y) - d') s nf log(1/n) + +1 logr)
A(Y,,;A,
then follows by known results (see, e.g,, [RSS18, Theorem 2.1]) that in time n o1) we can compute an estimator à such that
|a d
2.3 Relation to previous works
While previous works do not exactly follow the general strategy to show identifiability here, they can be interpreted as implicitly trying to exploit the existence of such certificates. The crucial difference is how they try to upper bound the deviation degrees over small subsets. In particular, they establish this by requiring that all degrees d. This only holds when d' 2 log n and fails in the sparse regime. In this work, we showed that this strong concentration is not necessary. Intuitively, it is not necessary since the outlier degrees in the sparse case are washed out when averaging over the set
tightly concentrated around
Besides the efficient algorithm, we also view the fact that you can apply the proofs-to- algorithms framework to this problem as a contribution of the paper. As we established, this leads to very clean analysis and improved guarantees, that in particular also work in the sparse case and achieve optimal breakdown point.
References
(AJK+22] 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. 1, 2,

---

[BP21]
Ainesh Bakshi and Adarsh Prasad, Robust linear regression: Optimal rates in polynomial time, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 102-115. 4
[BS14]
Boaz. Barak and David Steurer, Sum-of-squaree proofs and the quest foward optimal algorithms, Proceedings of the International Congress of Mathematicians Mathematicians-Seoul -Soul
2014. Vol. IV, Kyung Moon Sa, Seoul, 2014, pp. 509-533. MR 3727623 12
[BS16]
Proofs, beliefs, and algorithms through the lens of sum- sqquoees lecture notes, 2016. 12
[CDHS24] Hongjie Chen, Jingqiu Ding, Yiding Hua, and David Steurer, Private edge density estimation for random graphs: Optimal, efficient and robust, The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. 1,
[DdHS23] Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, and David Steurer, Reaching kesten- stigum threshold in the stochastic block model under node corruptions, Proceedings of Thirty Sixth Conference on Learning Theory (Gergely Neu and Lorenzo Rosasco, eds.), Proceedings of Machine Learning Research, vol. 195, PMLR, 12-15 Jul 2023, PP. 4044-4071. 2
[DKK+18] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Robustly learning gaussian: Getting optimal error, efficienlly, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 2683 2003-2702.4 4
[DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 73-84. 4
[ER59]
Paul Erdós and Alfréd Rényi, On random graphs. I., Publicationes Mathematicae Debrecen (1959). 1
19K 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. 9,18
[FO05]
Uriel Feige and Eran Ofek, Spectral techniques applied to sparse random gnaphs, Random Structures Algorithms 27 (2005), no. 2, 251-275. MR 2155709 2,
[Gil59]
Edgar N Gilbert, Random graphs, The Annals of Mathematical Statistics 30 (1959), no. 4, 1141-1144. 1
[GV16] Olivier Guédon and Roman Vershynin, Community detection in sparse networks via grothendieck's 's inequality, Probability Theory and Related Fields 165 (2016), no. 3, 1025-1049.
[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. 4, 12
[Hop20]
Samuel B Hopkins, Mean estimation with sub-gaussian rates in polynomial time, The Annals of Statistics 48 (2020), no. 2, 1193-1213. 12
[KMM88]
Adam Klivans, Pravesh K Kothari, and Raghu Meka, Efficient algorithms for outlier- robust regression, Conference On Learning Theory, PMLR, 2018, pp. 1430. 4
[KS03]
Michael Krivelevich and Benny Sudakov, The largest eigenvalue of sparse random graphs, Combinatorics, Probability and Computing 12 (2003), no. 1, 61-72. 8
[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. 4, 12, 18
[Le16] Can M Le, Estimating community structure in networks by spectral methods., Ph.D.
thesis, 2016. 8, 17
10

---

[LM22]
Allen Liu and Ankur Moitra, Minimax rates for robust community detection, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 823-831.
[PS17]
Aaron Potechin and David Steurer, Exacl lensor completion with sum-of-squares, Proceedings of the 2017 Conference Learning Theory, 2017. 12
[RSS18]
Prasad Raghavendra, Tselil Schramm, and David Steurer, High dimensional es- timation via sum-of-squares proofs, Proceedings of the International Congress of Mathematicians; Rio de Janeiro 2018, World Scientific, 2018, pp. 3389-3423, 4, 9,
12
11

---

A Sum-of-squares background
In this paper, we use the sum-of-squares (SoS) semidefinite programming hierarchy [BS14, BS16, RSS18J for both algorithm design and analysis. The sum-of-squares proofs-to- algorithms framework has been proven useful in many optimal or state-of-the-art results in algorithmic statistics [HL18, KSS18, PS17, Hop20]. We provide here a brief introduction to pseudo-distriiutionn,, sum-of-squares proofs, and sum-of-squares algorithms.
A.1 Sum-of-squares proofs and algorithms
Pseudo-distribution. We can represent a finitely supported probability distribution over R" by its probability mass function μ: R" - R such that μ > and Exespp(u)) (u(x) = 1. We define pseuuo-disttibutions as generalizations of such probability mass distributions by relaxing the constraint 0 to only require that μ passes certain low-degree non-negativity tests.
Definition A.1 (Psendo-distributtion) A level-f pseuuo-distribution μ over R" is finitely supported function μu R² - IR such that Σxesupp(y) ((x)= and Exesupp(r) H(x)f(x)² for every polynomial f of degree at most 8/2.
We can define the expectation of a pseuuo-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 a function f R"" - IR by
E f
Σ
fxx)
(A.1)
xesupp(p)
The following definition formalizes what it means for pseudo-distribution to satisfy system of polynomial constraints.
Definition A.3 (Constrained pseudo-distributions)) Let : R" - R be level-f pseudo- distribution over R". Let A = (fi 0,..., fm > 0} be system of polynomial constraints.
We say that μ satisfies A level r, denoted by μ f A, if for every multiset $ S [m]] and every sum-of-squares polynomial h such that deg h) + Eies max(deg(fi), < f,
Eh 0 0. iES
(A.2)
We say i 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 u -| A if and only if μ is supported on solutions to A.
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 pseudo-distributions We say polynomial p is sum-of-squares polynomial if there exist polynomials (q:) such that >=Σ;-
Definition A.4 (Sum-of-squares proof). A sum-of-sqqures proof that system of polynomial constraints A = {fi > O,..., fm > 0} implies q > 0 consists of sum-of-squares polynomials (ps)sc(m) such !
9 = Σ
ps | fr. ieS
multiset S5(m]
such a proof exists, we say that A (sos-)prozes q > within degree f, denoted by A 1z > In order clarify the variables quantified by the proof, we often write A(x) | q(x) >
Here follow the convention that Ies fi 1 for S = 0.
12

---

We say that the system A sos-refuted within degree A 7 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 to deduce properties of pseudo-distriutiins that satisfy some constraints.
Lemma A.5. Let y be psendo-distribution, and let A be systems of polynomial constraints.
Suppose there exists num-oof-squares proof A | B. If = F A, then μ 'rr'tT B.
Sum-of-squares algorithm. Given a system of polynomial constraints, the sum-of-squares algorithm searches through the space of pseudo-distributions that satisfy this polynomial system by semidefinite programming.
Since semidefinite programing can only be solved approximately,
only find pseudo-
distributions that approximately satisfy a given polynomial system. We say that a level-f dseudo-distribttion approximately satisfies a polynomial system, if the inequalities in Eq. (A.2)
are satisfied up to an additive error 2-xL hIl Ilesll where ||-|| denotes the Euclidean norm 13 of the coefficients of polynomial the monomial basis.
Theorem A.6 -Sum-oo-squares algorithm). There exists an (π + m))00-timee algorithm that, given any explicitly bounded and satisfiable system 15 A of m polynomial constraints in n variables, that satisfies A approximately.
outputs a level-E
Remark A.7 (Approximation error and bit complexity). For pseudo-distribution that only approximately satisfies a polynomial system, we can still use sum-of- ofu-oo-squaaes 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 Sum-of-squares toolkit
In this part, we provide some basic SoS proofs that are useful in our paper. Lemma A.8. Given constant C O, have
[cEx
Proof.
- |
2 (C - xC + x)
2 C² 00
C2 x².
2
Lemma A.9 (SoS subset sum). Lef a .,,..., an E IR and B E RR Suppose for any subset S C [m1] with|] |S] & k, we have EEie ail & Then
h Σ
(0 X1, ......,,,y. < 1, Σ X,
axx;
< B.
1=1
The choice of norm is not important here because the factor nd another norm.
swamps the effects of choosing
A system of polynomial constraints explicitly bounded contains constraint of the form | M.
15 Here assume that the bit complexity of the constraints in A is (ır 0(),
13

---

Proof. We first show Σ 0ji; & B. Without loss of generality, assume d1 > e an-
Case 1: ag O. It is straightforward to see {0 & X1,...,A Xn & 1, Σ, k) h
B
ai
ai
k 1=1 4; < B)
1=1
i=1
Σ
a; xi)
a;xi
i=k+1
Σ
ax xx)
a
(0xx
i+++1
= 0:
k
Xi
0.
( xi < k)
Case 2: ax < Let & be the largest index such that at 0. (Note f E (0,1, ...., k- 13.) Then
E a; B)
2iXi
a:
a:X;
1=1
1=1
1=1
a;(1 x1)
(-a:)xi
0,
where in the last inequality we used A1, ..., 41 > 0 and aeil...., On < O, as well as 0 < x; < 1 for all i.
Observe that we can apply the same argument above to -a, an and conclude (-a)xx & B, or equivalently, E a;x; -B. Therefore,
| xi....,,A Xn 1,, Σ x & k 1
|- <
> i=1
ax3; & B
B Concentration inequalities
In this section, we prove several concentration inequalities for Erdós-Rényi random graphs are crucially used to derive our main results. We feefistttrronn introduce two classical concentration bounds.
our
Lemma B.1 (Chernoff bound). Let X1, X2, XN be independent random variables taking values in {0, 1). Let ΣN X,. Then for any
12
P(X EX + & exp
+ X
$2
P(X < EX - f) < exp
2EX
Lemma B.2 (McDiarmid's inequality). Let X2,...... XN be independent random variables.
Let f RNN R be measurable function such that the value of f(x) can change by at most e; > under an arbitrary change of the i-th coordinate of x RRN That is, for all x, x' RN differing only in the i-th coordinate, we have 1x(x) f(x') C,. Then for any 0,
212
(((((x)
=) 2xxp
ΣNN c2
14

---

Lemma B.3 (Average degree concentration). Let A ~ G(n, /n). Let d(A) := Li, Aij. Then
for every constant C > 0, there exists another constant C' which only depends on C. such that
log n
log
P [ ( & C' max
Val
> 11-n
Proof. Note d(A) 3 Eiee and (Aglisj Ber(p") independently. Also note Ed(A) (1 (1-1/ 1/nn d Then by Chernoff bound Lemma B.1, for any > 0,
2/ P((((A) Ed(A))
22
>
exp
π
2t + (n 1) /2
12
< exp
2 max(2t, (n 1) /2)
t²
2exp
min
4' (n - 1) do
12
2max exp
, exp
(n- - 1)
Lemma B.4 (Degrees subset sum). Let A ~ G(n, d /n). For S S [n], let e(S) := Lijes, i4 Aij
and let e(S, == Eics, jæs Aij. Then for every constant C 0, there exists another constant C which only depends on C such that with probability n -C, we have for every S = [m],
(((s - Ee(s,S) < C². ([s] log(en//)))) + /d log(en/|S())
and
-e()) & C' ((s) /|5| (
Proof. LetN N and X .... XN Ber(p" independently. Consider their sum X == X; By Chernoff bound Lemma B.1, for any 5 > 0,
P EX 5) < exp
8
2
Fix a [n]. By union bound, the probability that there exists a k-sized subset C [n] such that - e(S, 5)
is at most
(1]
[1
52
82
en
2 exp
< 2exp
+ k log
k
8 (+
8 2 E e(S
k
We want to set such that
82
> C k log en k
8 21 2
for some sufficiently large positive constant C. Then it will imply the above probability is at most
2exp (exp(-(C-1) - loo
en k
2exp(-(C 1) log(en)) < (C-1)
where we used the fact that x log $ is increasing function for x & 1. Since
82
82
82
8
82
min
min
ò + 2+2Ee(S,S)
2
8
2' 4Ee(S, 3)
it suffices to ask for
ô > max
2C klog
4C Ecee,s klog k
k
15

---

Then we can apply union bound to all k = 1,..., , and conclude that with probability at least - n (C-2), every subset S _ [n] satisfies
le(s, 5) Ee(s, S) | |sglenn||| |S| log(en//S))
Similarly, we can replace all e(s, by e(S) in the above argument and conclude that with probability at least - n1 (C-2), every subset S S [n] satisfies
le(S) - E ee() & |S] log(en SI) +
Lemma B.5. Let A G(n, d /n). Then for every constant C O, there exists another constant C' which only depends on C such that with probability 1 n the number of vertices with degree larger than 2 E d(A) is at most C'n/d".
Proof. Fix some O. (We will set = in the end.) For [n], let B; be the {0, 1)- valued indicator random variable of the event that the degree of node in A is larger than (1 + (++))Ed(A)) Let pi P(B; 1). By Chernoff bound Lemma B.1,
x2 (Ed(A)
p: = P(B: = 1) & exp
(B.1)
E+2
Fix some deviation ò 0. We going to upper bound P(Σ; - > 8). To this end, consider the n-stage vertex exposure martingale (note B ss are not independent) where at the ith stage reveal all edges incident to the first i nodes. Formally, let S; := {Aij}jz (note S are independent) and define f(S ,ii....,,,,,, S,) == Σ; B; However, the Lipschitz constant of f is Q(n) which is too large for us to apply McDiarmid's inequality. To reduce the Lipschitz constant, we introduce truncation function & as follows. Fix bound A > 1. For i E [n], let f(S;) = S; if there are at most A ones in Sj otherwise, set t(S,) = O. Let g(S,,..., S.) == f(((S)),.... ((S))) Then it is straightforward to see the Lipschitz constant of g is at most 3A. Then by McDiarmid's inequality Lemma B.2,
28
P(g Eg 5) & exp
9n
To make this probability at most n -, it suffices to set > / logn.
Then we relate and g. By the definition of g, we have f(S], S₂) g( Sp) with probability 1, which implies f > Eg. By Chernoff bound and union bound, there exists constant Č' 0 which only depends
such that the maximum degree of is at most +C d log n log 1) with probability 1-n Thus, we we A = +C' log + log n). Then we have f(S), S.) = g(S), ........ Sn) with probability 1 -
Putting things together, by union bound, f g and g Eg < happen simultaneously with probability 1 2n -c. Together with E gg, they imply
f f- R < V9C/2. vn log dd + Cd log n + C' C'
with probability 1 1-2n-
Finally, plugging in = 1 to Eq. (B.1), we have the expectation of the number of nodes with degree larger than (Ed(A) is upper bounded by
ne Ed(A)3 & 2n En/Ed(as Ed((),,
where we used e x/3 < 2/x for x > 0. To ensure the deviation at most O(n/d"), it suffices to require
n log dd dd logn - + logn) $
-
-
-
d' s (n (n/logn)* 1/4
Note when do 2 (æ/log 1/4 it is easy see the maximum degree of A is (1 o(1))d with
probability 1 - 1/poly(n).
16

---

Lemma B.6. Lef A ~ G(n, (1), Let D be the n-by-n diagonal matrix whose i-th diagonal entry max 1, d 4//2E((A). where d; is the degree of node i. Then with probability 1 - 1/poly(n),
| 1 11pp s vd
Proof. First, let T C [n]] be the index set corresponding to vertices of degree larger than 2 d(A. By Lemma B.5, we know that [T] x n dd with probability at least 1/poly(n). We condition on this event. Note that this implies that the rescaling by D-1/2 affects at most O(n/d)) vertices. By [Lel6, Theorem 2.2.1] (see also Point 4 Section 2.1.4), follows that || |Í0-1/A 1122
EAllop s vd with probability at least 1 - (/))ll())).lt is thus enough to show that with the same probability ||EA D-1/2 B[A] 1-
Vd'. Note a 111,, , it can be easily checked that the difference is lower order term. Let = 1 1. We will show that with probability at least 1/poly(n), which implies the claim.
that EAA A = (11 I.). Throughout the proof we will pretend it is equal to d
l|eet 11 x Var
Note that for i $ T it holds that = 1. Further, for all i, we have 0 & < 1. Thus,
n² (1+ ctec) 4n| $ do
||cc_
11 -
& llec 11 - 2
Σ
icT,je[m]
C Robust edge density estimation algorithm
In this section, we show that there exists an algorithm that achieves the following guarantee. Theorem C.1. Given corruption rate 17 E 10, 1) and the n-corrupted adjacency matrix of an Erdōss-Res Rényi random graph A G(n, d' /n) where d > c for any constant O, there exists polynomial-tine algorithm that outputs estimator à that satisfies
log(n)- do 1/ log(1/n) d
[log(1/n)
pa d9|
n1
(1 (1- (1-2n)4
(1 21))
with probability 1 11poll(nn) Remark C.2. When 17 E for any constant & (0,1/2], the error bound becomes
log(n) do + ny log(1/n) d' 1logg1111)
a - d31 x
The main idea of the algorithm follows the general paradigm of robust statistics via sum-of- squares: given observation of the n--orrupted graph A, find graph that differs from A by at most тn vertices and satisfies set of properties p of the uncorrupted Erdös-Rény: graph A G(n, d /)) then output the average degree d(Y) as the estimator.
The crux of the algorithm is to determine the properties P that Y satisfies such that:
P sufficient to show that d(Y) is provably close to the d
P is efficiently certifiable in SoS.
In our algorithm, this paradigm is implemented by the following three polynomial systems with variables Y (Yij),,e[m) and (zi)se(n) and with inputs the corruption rate 1] and n-corrupted adjacency matrix A.
The first polynomial system guarantees that Integrality and size constraint of labeling. is integral and sums up to at most 17n.
Alabel(Z;)) == fz0z= =z, (1,z) & <m)).
(C.1)
17

---

The second polynomial system is to certify that Y differs from the observed 7i-coruupted graph by at most 1i vertices.
Graph agreement constraint.
0 < Y 11 Y =YT
}.
Agraph(Y, =
(C.2)
Y (1 2)(1 22) = A - -2)(122) -)
Sum-of-squares certification of degree concentration. The third polynomial system is the property P that is efficiently certifiable and guarantees that d(Y) will be provably close to d'.
3 SoS proof in that, (w; 2n) 1t- (Y 4M2 117,
Adegree (Y; =
2101 ww < Ci(1) n² d(Y) C2(m) n²
(C.3)
where Ci(n) = Cdeg? log(1n)) C2()) Cdeg' log (1/n), and Cdeg is a universal constant.
Note that the SoS certificate constraint Aee can be formally modeled using poly- nomial inequalities by introducing auxiliary variables for the SoS proof coefficients. This a standard technique and we refer the reader to [KSS18, 1KP-19] for more detailed discussions.
For the convenience of notation, we will consider the following combined p in remaining of the section
A(Y, z) Atabe((Z;1)) Agraph(Y, U Adegree (,,)))
(C.4)
We will show that A(Y, 2;A,, A))
is both feasible and provides meaningful guarantees.
Feasibility. It can be shown that A(Y, z; 1j) is satisfied by uncorrupted Erdös-Rényi random graphs with high probability. More concretely, will prove the following feasibility lemma in Appendix C.1.
Lemma C.3 (Feasibility). Let A G(n, d /n) with d' c any constant 0. Let [0, 1/2) and A be an rp-orruppted version of A". With probability 1- - 1/poly(n), there exists z" E {0, 1) such that (Y, 2) (A", z²) is a feasible solution to A(Y,z;A,1))
Utility. It can be shown that any pairs of feasible solutions (Y',z") and (Y, z) to low-degree SoS relaxation of AY A, 1)) satisfy that (at) d(Y")) is sufficiently small. More concretely, we will prove the following utility lemma in Appendix C.2.
Lemma C.4 (Utility). Given A E {0, 1)2xn feasible solution to ((,,,;AA,)) and d(Y") > Cr- for any constant Cr- 0, then
nxn and constant n such that rJ E [0, 1/2), if 20)")")) is
(d(Y) - d(Y))) s 7" log(/)
d(Y") + 10gl (1/n) (1 2n)
Y= 8
A
(1 27)*
Now, we are ready to describe our algorithm that satisfy Theorem C.1. The algorithm computes the degree-8 pseudo-expectation É of A(Y ()) by solving the level-8 SoS relaxation of the integer program in Eq. (C.4), then it outputs [E[d(Y)) as the estimator à.
Algorithm C.5 (Robust edge density estimation).
Input: s-corrupted adjacency matrix and corruption fraction
Algorithm:
Obtain degree-8 exeuto-expectation É by solving level-8 sum-of-squares
relaxation of program A(Y, 2; (defined in Eq. (C.4) with input A and 17.
Output: B[d()).
Proof of Theorem C.1. We will show that Algorithm C.5 satisfies the guarantees of Theo- rem C.1.
By Lemma C.3, we know that, with probability 1 - 1/poly(n), A(Y,z;A, z;A, is satisfied by (Y, = (A9, where A G(n, d' dn/n)n)))))))) is the uncorrupied graph and zz is the set of corrupted vertices.
18

---

By Lemma B.3, the average degree of A ~ G(n, dn/n) satisfies, with probability 1 1-1 1-1/poly(n),
do log(n)
(d(A))-')) $
(C.5)
de login)
Therefore, d(A)) > d
> c- 0 > CAs.
Now, we can apply Lemma C.4 with (Y', = 2A) and Cy = CAs. This implies that the d pseudo-expectation E obtained in Algorithm C.5 satisfies
(og((n)) d(A')
n log (1 - 2n)*
(((()))d(A9))))
(1 (1-21) (1-2n)s
By Jensen's inequality for pseuddo-xpeectation,, it follows that
1/210 d(A") + 1o
- s
(1 (1- (1-2n)s
(1-
Since the estimator output by Algorithm C.5 à B[d(Y)), follows that
12 d(A") +
20 (1/n)
ja d(A())) $ VV
22)
(1 (1-21)) 2n)*
17 log(1/n)
17 1log(111) (1 21))
vd(A9)
(1 21)
d' log(n)
By Eq. (C.5), we have d(A9)= <
d & 2d with probability 1 1/poly(n). Therefore,
17 log(1/n)
Vd (log(1/1)
pa d(A)))) s
(1-2n)² (1 21-2
By triangle inequality and Eq. (C.5), we have
" log(111)) 11lo((111)
log(n) do
la l d3' < ja d(A") ( +1((A))
d'1
(1 (1-2n)+
(1 (1-2n)2
By union bound on failure probability of Lemma C.3 and Lemma B.3, Algorithm C.5 succeeds with probability 1 - 1/)o(((n.) This finishes the proof for the error guarantee.
For time complexity of Algorithm C.5, since Eq. (C.4) has polynomial bit complexity, solving the level-8 SoS relaxation of Eq. (C.4) and evaluating ÉE((()) can be done in polynomial time. Therefore, Theorem C.1 has polynomial runtime, which finishes the proof.
C.1 SoS feasibility
In this section, we prove Lemma C.3, which is direct corollary of the following lemma.
Lemma C.6. For any constants C > 0, the following holds. Let A G(n, d /n) with d' >
Let d(A) Σ,, Ai and y E [0, 1]. Then with probability at least n we have {w
w, (1,w) < yn) 4
A d(A) n
11 2w1 T ww ) & (' -((A) log
where C' only depends on and C.
19

---

Proof. Note
( d(A) 11T, 2w01 ~wo0" ) =2
(2. (2,,A1 A1 d(A)) 1) 10)ww -w T(TA- d(A)
11 w.
We will bound (w, d((A) 1) and w wA diAi 11 111T)a separately. By Lemma B.3, we have
log
log
(d(A) - Ed(A)) s max
with probability 1 - 1/poly(n). (Since d' > Q11), this bound can be simplified to [á(A)
d((A)) & Vlog(n)/n Vd We will condition our following analysis on this event.
Bounding (w, A1 d(A) 1). Note
(w,A1 A1 d(A) 1) (w, A1 Ed(A) 1) (Ed(A) - d(A)) (1,
(C.6)
where the second term on the right side can be easily bounded as follows, 10 (1, & yn)
T
(Ed(A) d(A)) - (1, < Ed(A) - d(A)) yn s max n, vn log(n)
(C.7)
Now we bound the first term on the right side of Eq. (C.6). For [n], let d be the degree of node i in A. Then
(w, A1 Ed(A) 11) Σ w; Ed((A))
For a subset S S [n], we have Eies di = e(S, 2e(S), which implies
Σ
d: Ed(A)) e(S 2e(S) - EE 5) 2
iES
Hence, by Lemma B.4, the following holds with probability - 1 1/poly(n): For every subset [n] with [S] < yn,
Σ d: Ed(A)) & (e(s,)) - EE(S, 2/((s) Ee(s) JES
$ +yloge//))n+++
By Lemma A.9, the above is also true in SoS, i.. (0 < 1, (1, w) < yn) T
Σ ww,(d (d: Ed((A) $ y
(C.8)
Therefore, putting Eq. (C.7) and Eq. (C.8) together, we have (0 < w < 1, (1, & yn) H
kw, A1 d(A) 1) s logle/y) http:/"))mxyyloo///// V
(C.9)
with probability 1 1 1/ppoly(n
Bounding w T(A d(A) 11T).. Note
2o" T (A- d(A)
11 w w (A- F.A (AAFAA
TT
EA
d(A)
11T w.
(C.10)
We bound the first term on the right hand side of Eq. (C.10). Let ò be the n-by-n diagonal matrix whose i-th diagonal entry max{ 1, d: / 2 EdA)). As
EA)D-1/2 (D)2 'A (A EAA (D'/2w)T D (1
w
20

---

then
[w- EA)Ø & | (A - -AAAD 1/2 1lop |
By Lemma B.6, the following holds with probability 1 1/poly(n):
[| - (AP(A-EAADD 1/2|| lo s vd
Since
(0 w
l |
Σ max 1,
d: 2E (AA)
w
w0 + Σ
d;
<
Wi
IE (()
3
Σ
1
Σ wi(d: Ed(A)),
20 +
2
2
then by Eq. (C.8),
log(e/v)
yVlogle/y)
(0 w & 1, (1, & yn) ī ||
$ yn
do
vd
Therefore, the following holds with probability - 1/poly(nn: 10 w 1 (1, & yn) |w [A (A - EA)w] $ yn Vn
h
y ylogle/y) Va
logle/y) n.
(C.11)
Now we bound the second term on the right hand side of Eq. (C.10). Since
d(A)
11 d
(11T - 1) d(A) d - d((A) 11 d I,
EA
11T
then
EA d(A)
do d(A)
d
w
11 w
(1, ),)
2
Thus, (0 & w & 1, (1,w) & yn) 2
a EA d(A)
11 20
& y²2 -d(A)) yd
$ 2 + y2 2 log(n) do + +yd
(C.12)
Therefore, putting Eq. (C.11) and Eq. (C.12) together, and assuming d' Q(1), we have (0 w < 1, (1) & yn) 1
d(A) 11 20 ylggle/y) + yoogle/y))nvt
w A
n
(C.13)
with probability 1 - 1/ 1/poly(n).
x.y ((x + y) & 2x2 + 2y²) and
Putting things together. Using two simple SoS facts
[|x] < B} _ {x2 & B2), together with Eq. (C.9) and Eq. (C.13), we have
A d(A)
2
d(A)
2
n 11T, 2T1T ww
= 22w Al d((A) 1) w A
11 20
n
< 8(w, - d(A) 1)2 + 2 T (A- TOT d(A) T w
n
$ y2 loglely)n y2 (g
$ x² ((A)) (e/y))²
where in the last step we used d(A) (1 o()))d
21

---

C.2 SoS utility
In this section, we prove Lemma C.4. The key observation is that Y and Y" will have large agreement because they both agree with A on (1 - nin vertices. Therefore, ((())d((Y))) only depends the set of vertices of size at most 2n that Y and Y* differ, which can be bounded by the SoS certificate in (Y;
Proof of Lemma C.4. Let - -1 By constraints Y (1 z) - z)T A (1 2) Z)T and
we have
Y22 A
Yo (1 w)(1 ww 0(-=))
4
=A0 000
-AO(1=2'((==)) (000=))))(((2)))
=Y 1-1 = (1-))((1-1))))))))))0()111)01111
=Yo () - w)
Therefore, it follows that
Yz d(Y) - d(r)) =(Y-Y1, 111)
A
8
=(Y My--,, Y, 11" -11 (1 - ))
=(Y- - Y 220 ww )
=(Y d(Y) 11 d(Y), 11 d(Y")
11 + d(Y")
11T -Y", 12,2 ww" T)
=(Y d(Y) 11 ,w0 1 ww"
d(Y')
11 Y,, www >
d(Y)
11 d(YY)
11 1ww -ww
n
Notice that
d(Y) d(Y"), 11 11 1 - -ww") ) = n (w, 1)
(w,1)) 1) ( (aM))
(w,
n
By re-arranging terms, we can get
Y= 8
=(Y- -(Y n (w, ) (aM-) a()))
d(Y). T1 1 ww + d(Y')
A
11 2"2 www" )
n
Squaring both sides, we get
Y,2 (w, 1) 4 (d(x) d(r:)) )²
n2 n2(11
A 8
n
=((r- d(Y) 11 2001 T -www + d(Y")
11 ,", TT -www" ")² ))
n
n1
<2(Y d(Y)
d(YY)
11 2w11 - www" y2 + 2
11 Y T www T)2
n
n1
(C.14)
By definition of w, follows that A | w w and
1 A
2
(1, w) =(1, (1 -) 21 z²))
= Σ (1 - z;) 2,))
ic[a]
(C.15)
= Σ zi +
Σ 2
Σ
z
it
:c[n]
<2n
22

---

Therefore, w satisfies (w;)), and, by the SOS certificate in Aderree it follows that
A I Y (Y d(Y)
10", ,201 wow ww & Ci(n) n² d(Y) C2(n) n²
(C.16)
and by Lemma C.3,
A Y= d(Y*) 8 11 22 ww & Ci(1) n² a2)d C2(1)- -??
(C.17)
Plugging Eq. (C.16) and Eq. (C.17) into Eq. (C.14), we get
A Y2
n²
(w,, 1) 4 (am)) ((())aa(r))) Ci(r) n² a(Y) + C (()))))nn-d(())))) +(2())(((()) n²
n
Dividing both sides by n², we get
Y 8
1
(w, 1) 4 ((()) (am)) < (((m))d(0) + Ci()) 2C2(n).
R
n
Plugging in A
22 2 (1, w) < 2n from Eq. (C.15), we get
Yz (1 - 2n) (am) (a() a(r3)) Ci(n) d(Y) Cit)) d(Y) 2C2(1).
(C.18)
Notice that, the following holds for any C > 0,
d(Y) a(Y) a0) d(Y)
C,- ((-- d(Y))
VC, d(Y")
(((Y) - -d(r)))
1
-G.. d(D))
2
(a()) a(r))) )²
Cg +1)a(r))
2C, d(Y*)
2
((() (d())d(Y))) -d(r)))
( + +1 1))()))
C
2C,
2
Plugging this into Eq. (C.18), it follows that
Ci(n) (a( -(()))
Y= 8
(1-2))((((
Cg C 2 2C,,Cr + +C((n)
+2))(()+2222mm (C.19)
Let Cy = Cy-(1-2nf 2n Since 1 log(1/1) < 1 for [0, 1),, we have Ci(r) = log(/))) <
(r)
50C
Plugging these into Eq. (C.19), it follows that Cdeg and C. (1--
V* H
(1 - 2n) (a()) - -d(r))
8
(1 2n)*
(d(Y) - -d(r))²
+c10n) Cy-(1 (160(Cr(11100
25C
22n)4 +2)dd(')+2))))00) +C2(r)
100
(1 2n)*
(((n)(25cdeg/Cy)
+2)
(am ((())d()))
d(Y') +C2(n)
100
(1 (1-2n)+
Rearranging the terms, it follows that
Ca(1) CCr + 2) (1 - 21)*
A K 0.99(1 2n) -
d(Y')++++ 2C2(m)
23

---

(a0) (40)-007) -d(r))
C1()) CCr +4)
4C2(1)
d(Y)+ (1-2n))
(1 27)s
(a(t) a(r))² (oy)-a(r)))
C1(1)
C2(1)
d( (Y + (1-22 2-111)
(1 21)
log Plugging in Ci(T)) Cf log (1g) and C2(1) = Cdeg!! 2 2 (1/n),
it follows that
A Yz (dm) d(r)) Cdeg log(1)) d(Y') + Caeg? (1/n)
22)
(1 21)
|olog(111) d(Y') 12 (1/1n) 2n) (1- 11))))
D Robust binomial mean estimation
In this section, we show that the sample median can robustly estimate the mean of binomial distribution. For simplicity, we prove the result for a smaller but rich enough parameter regime than main theorem Theorem 1.2. We also make basic integrality assumptions to avoid having to deal with floors and ceilings throughout the proof. To compare it with in the arguments below.
Theorem 1.2, we
The corrupted binomial model that we consider is defined as follows.
Definition D.1 (n-corrupted (m, n, d)-binomial model). Let 17 E [0, 1], the n-corrupted (m, n, d)-binomial model is generated by first sampling mn i.id samples Xi, X2, ....... X from
Bin(n, 1 ) then adversarially picking an n--raction of the samples and arbitrarily modifying them to get X1, X2,.... ,,,....,,,,, Xm-
The goal of robust binomial mean estimation is to estimate the mean d given observation of corrupted samples X1, X2,... Xm that are generated according to the n-corrupted (m, n, dd-binomial model from Definition D.1. We will show that the median of the corrupted samples satisfy the following error guarantee.
Theorem D.2. Given n-corrupted (m1, n, d)-binomial samples X1, X2,,..,,,,, when 10000 & d <
0.0001n n is an integer and 1000 & 17 & 0.01, the median à satisfies, with 1 1-4 exp((n" /4),
Vm
|a - d < O(Ivd).
To prove Theorem D.2, we need the following two lemmas.
Lemma D.3. When 10000 d & 0.0001n is an integer and r7 & 0.01, let X Bin(n, $) be binomial random variable, it follows that
P(d 100n < X & 1) 1)> 4n
(D.1)
and,
P(d & d 100n Vdl > 41
(D.2)
Proof. Consider an arbitrary integer E 100n d, d 100m Vd], it follows that
d
n-1
log(P(XX = t)) log
t
n1
11
log
n!!
d
(D.3)
t!
f)!
n!!
d
d
log
log
(n
1) t)log
f!( - t)!
71
n
24

---

f)3 By Stirling's approximation, it follows that
n!
V2Tmann)e((++00011))
f!(n - t)!
(1
(1) -100:/))0/2220000000000000// 0(1(nn 1)))
V 2T1(n - 1) (1 ((100) + O(1(nn (H) (11) n-
1 O(1/n)
)rr
(D.4)
n-1
10f n-
Plugging Eq. (D.4) into Eq. (D.3), we get
1
d' {
log(P(X f)) > log
t log
+ (n 8) log 11 カー
(D.5)
2
10t
For the second term log( we use the Maclaurin series of natural logarithm and get
d
d-
tlog
= =log
1
dd-t
(d
t)2
(d
21
3/3
(d - 1)2 (d
t)3
= =d -
2t
312
Since (d - 1)2 & 1000072d < d and - 100n Vd 0.99d, it follows that
f flog
-
(D.6)
For the last term (n f) log( (=d and get
we can also use the Maclaurin series of natural logarithm
nー
d
t-d d n1 n-
(n log
(n +)g
1
1
-
(t d)²
(t d)3
(n - +)
+
-
2(n - 1)2
3(1 f)3
(1- d)2
+ (1 -f- d)3
2(n - f)
3(n - 1)2
Since (t - d)2 < 1000072 < 0.0001n, it follows that
(n log π1 d
> t d
(D.7)
11
Plugging Eq. (D.6) and Eq. (D.7) into Eq. (D.5), get
1
-
1
log(P(X = ()) log
1
>
log
(D.8)
2
10:
2
Now, we are ready to prove Eq. (D.1) and Eq. (D.2). We first consider the regime [d - 100 d - 1], it follows that
e
log log(P(d PPd 100n x & d 11) = log
Σ P(X = f)
log
(100 P(X 100n
25

---

log((100)) log(d) log P(X d - 10-000m Vd))
> log((00n) log(d) log
100 -3
1
= -log(47) + 2 log
d - 100
log(41))
which implies that
P(d - 100n & X & d 1) > 41
The regime & E [d + 1,d + 100 can be proved in a similar way
dd-100rv2
log P(d+ +ed+ 1 < d+ 100n = log
Σ
P(X = t)
1=d+1
> log 100n d P(X d + 100
= =ogg(100)) +
2 log(d) log PIxX = d 100n Va))
Va)
1
> log((00n) log(d) log d 100
-3
d
= =log(4111)
log
2
d 100n
1
1
> log(4.11)
log
2
1.01
> log(4n)
which implies that
P & d 100n Va) > 47--
Lemma D.4. When 10000 & d & 0.0001n is an integer and 1000 < 0.01, let X2 Xi X be m i..dd binomial random variables from Bin(n, $),, with probability 1 exxp( - there are at least 2mm samples in range [d- 100 d d-1] and at least 2nm samples in range [d 1, 100n Vdl.
Proof. By Lemma D.3, we know that for each X E (Xi X2 X we have
P(d Pdd-100nvV & < d 1) > 4n,
(D.9)
and,
P(d+1< < d 100n Vāl > 47
(D.10)
Let us denote by Z; the event that X is in range [d 100n Va, 1]. By Eq. (D.9), we have E[Z,] > 41.. Since X,, Xi,,..... Xa are i..d., the events Z/'s are i..d. Bernoulli random variables. Therefore, by Chernoff bound, it follows that
P Σ
Zi < 2mm
< P
Σ
Zi
< (1
Σ
Ε Zi]
< exp
26

---

1m 2
& exp
Therefore, with probability least 1 1 exp(- 100n d - 1]. Using the same argument, it can also be shown that, with probability at least 1-exp(- ) at least 2mm samples are in range [d 1, d + 100yVa]. The lemma follows by union bound.
40 2
least 21pm samples are in range [d
Now, we are ready to prove Theorem D.2 for the error guarantee of median for corrupted binomial samples.
Notice that the median of Bin(n, d) is d when d is an integer, that is P(x; d) s and P(X: d) > for each [m.] Using similar arguments via Chernoff bound Lemma D.4, it is easy to check that with probability at least 1 2 exp(( there are at least (1-r)m uncorrupted
Proof of Theorem D.2. Consider the uncorrupted samples , X
(1-7)m samples that are at least d and at least 2 uncorrupted samples that are at most d.
By Lemma D.4, with probability 1 exp(-nm/22) 1 2exp(-n"m/4) there are at least 21m uncorrupted samples in range [d 100 d-1]] in range [d 1, + 10)
and at least 2pm uncorrupted samples
Therefore, combining the two bounds, with probability exp((172m/4 m/4), there are at least 3qm
2 + 3qm uncorrupted samples in range [d 100, n and at least m + uncorrupted samples in range [0, d + v00.
nM After corrupting nmm samples, there are still least _14 + 2 samples in range [d - 1007 Vd, n] qr and at least + 2 samples in range [0, d V0). Thus, the median satisfies, with probability - 4 exp(-=mmm/))
|a - d < O()v)).
27

---

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 discuss the gap between our result and the best known lower bound, and we propose it as a open problem for whether the gap is inherent.
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
28

---

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

---

(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-soure 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 or 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 guidelines for more details.
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.
30

---

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 /est 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:://eeurispeeeeeeeee htt.urpppp.cccpubb..////tcccciia
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
31

---

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]
32

---

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/ codet/cco//////// moode/moeel 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
33

---

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/ 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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used at all during this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components.
Please refer to our LLM policy (ht https//eeerippscccoofeeeeeeeeeee / for what should should not be described.
34


Reviews:
[{"review_id": "kmTjpZWth8", "reviewer": "Reviewer_Kp9b", "summary": "Consider a graph G generated from the classic Erdos-Renyi distribution G(n,p), where we think of p = d/n. So the average degree will be d. An adversary corrupts an $\\eta$-fraction of the nodes, by arbitrarily changing edges incident to these \"corrupted nodes\". The aim is to estimate d. Previous work showed that many standard estimators fail. There has been recent work getting estimators for this regime.\n\nThe main problem is that when d = Theta(1), no previous algorithm gets the optimal bound. The first result [AJK+22] has an additive O(log n) error. The next result [CDHS24] has an additive error of d/10, regardless of d. Also, these algorithms fail when $\\eta$ is larger than some small constant.\n\nThis paper gives an algorithm that avoids all of these issues, and gets (nearly) optimal error. The bounds are technical, but the main point is that it allows for $\\eta < 1/2$, d to be a constant, and the errors goes to zero as d becomes larger.\n\nThe main idea is to use tools for the Sum-of-Squares (SoS) machinery that builds a semi-definite program (SDP) to solve this problem.", "questions": "What is the running time of the algorithm?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The primary strength is getting an estimation result for the constant d case, with optimal threshold $\\eta < 1/2$, and a multiplicative error that goes to zero as d increases. \n\nThe primary weakness is that I doubt that this is a realistic algorithm. The polynomial running time is probably quite prohibitive. So this result is of somewhat narrow interest to the people who work on this problem.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and positive comments!\n\nThe runtime is a large polynomial in the input size. Degree-$\\ell$ sum-of-squares (SoS) programs can be solved in time $n^{O( \\ell )}$, where the constant in the big $O(\\cdot)$ is quite large (and comes from solving a semi-definite program with $n^{O(\\ell)}$ variables), for us $\\ell = 8$.\n\nIn the past, e.g., for robust Gaussian mean estimation, there were fast iterative algorithms that used the same principles as the SoS proofs-to-algorithms paradigm. These usually have runtime that is at most quadratic or cubic in the input size. We believe our identifiability proofs can also lead to such fast algorithms and believe this is an interesting follow-up question."}, {"review_id": "M0C6bXB9AC", "reviewer": "Reviewer_ighP", "summary": "The paper studies the problem of estimating the edge density of ER random graphs $G(n, d/n)$ under node corruptions. The paper proves that their method can estimate d within an additive error of $O((\\sqrt{\\log{(n)}/n}+\\eta \\sqrt{\\log{(1/\\eta)}})\\sqrt{d}+\\eta \\log{(1/\\eta)})$. This upper bound differs from the lower bound for this problem by a factor of $\\log{(1/\\eta)}$. The paper also emphasizes that the proposed algorithm works for all $d \\ge \\Omega(1)$ and can achieve optimal breakdown point $\\eta =1/2$.", "questions": "I think this paper is a clear accept and have no specific questions.", "limitations": "There is not much concern about the potential negative societal impact of this paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n\nS1. The paper studies the problem of estimating the edge density of Erdős–Rényi (ER) random graphs — a fundamental problem with both theoretical and practical significance. It improves the approximation error bound for this task. The prior bound in [AJK+] is suboptimal and does not recover the non-robust case when there are no corruptions. I think the paper is strong and is worthy of acceptance.\n\nS2. The paper is well written. Its structure is clear and easy to follow. Prior work is thoroughly reviewed, and the high-level intuition behind the proposed method is well explained.\n\nS3. As mentioned in the paper, the proof is relatively simple, which actually enhances the contribution of the paper\n\n\nWeaknesses\n\nW1. The additive error bound presented in the paper is not very clean and still leaves a gap compared to the optimal result. There remains room for further exploration in this direction.\n\nW2. The paper does not include any empirical study. However, since this is a theoretical paper, this is acceptable in my view.", "was_revised": true, "final_justification": "After reading the paper and the authors' rebuttal, I decided to keep my score.", "rebuttal": "Thank you for your review and positive comments!\n\nRegarding the first weakness, note that the only possible improvement are in terms of factors of $\\mathrm{poly}(\\log(1/\\eta))$. More specifically, our error upper bound can be written as $\\max \\left (\\sqrt{d} \\cdot \\sqrt{\\tfrac {\\log n} n}, \\sqrt{d} \\cdot \\eta \\sqrt{\\log (1/\\eta)}, \\eta \\log(1/\\eta) \\right )$. This matches the information theoretical lower bound of $\\max  \\left(  \\sqrt{d} \\cdot \\sqrt{\\tfrac {\\log n} n}, \\sqrt{d} \\cdot \\eta , \\eta \\right)$ up to factors of $\\log(1/\\eta)$ and $\\sqrt{\\log(1/\\eta)}$.\n\nIn our regime, when $d \\geq 1$, a clean and only slightly looser way to state our upper bound is $\\sqrt{d} \\cdot \\left(\\sqrt{\\tfrac {\\log n} n}+ \\eta \\log (1/\\eta) \\right)$. The first part corresponds to the \"non-robust\" error and the second part to the \"robust\" error."}, {"review_id": "qi3tyAkRRV", "reviewer": "Reviewer_uhWe", "summary": "This paper studies a robust statistics problem on Erdos-Renyi random graphs.  Suppose that we draw an ER graph with expected degree $d$, but then we allow an adversary to choose an arbitrary subset of $\\eta n$ nodes and completely change the edges incident on them (not just between them).  Can we still estimate the original parameter $d$?  This paper gives state of the art results, showing a polytime algorithm that essentially matches the information-theoretic lower bound (up to a log factor) for all possible regimes.  This is in contrast to previous work, which either gave optimal bounds for only some parameter regimes or gave suboptimal bounds.  Their algorithm is based on a sum-of-squares proof, where they first given an inefficient algorithm, but then identify from this algorithm a certificate that can be expressed as sum-of-squares.  Since there is a well-known duality between SoS proofs and certain semidefinite programs, this means that there is an SDP-based polytime algorithm for the problem.", "questions": "- Is this algorithm practical?\n- What's the motivation for this precise problem?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper seems to basically close this problem (up to the log factor), as they get almost optimal bounds in all regimes where bounds are possible.\n- The paper is well-written and understandable.\n\nWeaknesses:\n- While I understand that this is a theory paper, for NeurIPS I would expect there to be either experiments or some type of argument about practicality.  But my understanding is that SDP solvers are still quite slow, so the algorithm in this paper might not actually be practical.\n- There has been previous work on this problem, so it seems to be of interest to the community, but I wish the authors had bothered to motivate the problem a little bit.  Why this corruption model?  Why study ER graphs?  Naivel, I would have expected something like \"real-world graphs are often preferential-attachment or something similar, and so we focus on trying to statistically recover the parameters of those models in the presence of adversarial noise.  The exact model of adversarial noise depends on the application: one could imagine edges being corrupted, nodes being corrupted, or some combination of the two.  Here are motivating examples of why we might want to consider each of these types of corruption in each of these random graph models: ...\".", "was_revised": true, "final_justification": "I gave this paper a 5 before rebuttal, and I still feel like this paper should be accepted.", "rebuttal": "Thank you for your review and positive comments!\n\nRegarding the first weakness/question on practicality of the algorithm, the runtime of our sum-of-squares (SoS) algorithm is a large polynomial in the input size as it requires implementing large scale semidefinite programmings. Degree-$\\ell$ sum-of-squares (SoS) programs can be solved in time $n^{O(\\ell)}$, where the constant in the big $O(\\cdot)$ is quite large (and comes from solving a semi-definite program with $n^{O(\\ell)}$ variables), for us $\\ell = 8$. In the past, e.g., for robust Gaussian mean estimation, there were fast iterative algorithms that are inspired by the SoS certificates from the proofs-to-algorithms paradigm. These usually have runtime that is at most quadratic or cubic in the input size. We believe our identifiability proofs can also lead to such fast algorithms.\n\nRegarding the second weakness/question on motivation for the problem, the deviation of real-world networks from the Erdős–Rényi model can often be effectively captured by node corruptions. For instance, in social networks, individuals or organizations may create fake profiles to manipulate network statistics, thereby misleading recommendation systems for their own purposes. In communication systems, malfunctioning devices can emit arbitrary or adversarial signals that interfere with accurate analysis. In biological networks, contaminated experimental samples may exhibit spurious interactions with other proteins, distorting the underlying structure. While Erdős–Rényi graphs are simplified, idealized models of real-world networks, we view them as a fundamental first step toward addressing these critical challenges in real-world settings."}, {"review_id": "SPZpyHJ4ua", "reviewer": "Reviewer_mXLy", "summary": "This paper addresses the problem of robustly estimating the edge density parameter $d^\\circ$ of Erdős-Rényi random graphs $G(n, d^\\circ/n)$ under adversarial node corruptions. ​ The authors propose the first polynomial-time algorithm that achieves near-optimal error rates and reaches the optimal breakdown point of $ \\eta = 1/2 $. ​ The algorithm leverages the sum-of-squares (SoS) hierarchy to construct certificates for concentration properties of edges in sparse graphs, overcoming limitations of previous methods in the sparse regime ($d^\\circ = o(\\log n)$). ​ The paper provides formal proofs, theoretical guarantees, and a clean analysis of the algorithm's performance.", "questions": "Below are my detailed comments/questions:\n\n1. For the sake of completeness, it will be very useful for the authors to explain why robust mean estimation methods will not work in this setting. The paper has referred to dependencies of the degrees of the uncorrupted graph. While that is true, I cannot understand the limitation of the following simple trick: If I view the set of edges as a (n choose 2) binary vector, then each entry of this vector is iid generated with prob. $d^\\circ/n$. Therefore, estimating the mean is a simple 1D mean estimation problem - if some elements are corrupted, then why will median of means not work? median of means is optimal for robust mean estimation in 1D. \n\n2. While the results are strong, the lack of experiments is a glaring problem. Given that the setting is simple, the lack of experiments (even synthetic) hurts the value of the paper. Especially so since the authors have highlighted the efficiency and statistical guarantees of existing work as a limitation.", "limitations": "Simple Experiments even on synthetic datasets", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper is well-written and well-motivated. However, the lack of any sort of experiments (even synthetic) is glaring", "was_revised": true, "final_justification": "There are two main reasons \n\n1. The limitation of an existing statistically optimal approach has not been discussed in the context of this estimation problem\n2. The lack of experiments is glaring espescially since the authors have touted efficiency to be one of the main advantages", "rebuttal": "Thank you for your review and positive comments!\n\nRegarding the relation to 1-D robust mean estimation: On a very high level the issue is that the parameter we want to estimate is $n$ times the mean of the Bernoulli distribution.\n\nOne way to see that this strategy will incur very sub-optimal errors is as follows. If we do not consider any structural properties of the corruptions and treat the problem as that of robustly estimating the parameter of a Bernoulli distribution, this can at best get error $\\eta n$. Even in the easier corruption model in which each sample is drawn from $Ber(\\tfrac d  n)$ with probability $1-\\eta$ and some error distribution with probability $\\eta$, it is not possible to get error better than $\\eta n$ (note that the adversary can simulate this model up to constant shifts in $\\eta$). In particular, we can choose the error distribution to be $Ber(1)$, then the resulting input distribution is roughly $Ber(\\tfrac d n + \\eta) = Ber(\\tfrac {\\hat{d}} n)$ for $\\hat{d} \\approx \\eta n$. Thus, $\\lvert d - \\hat{d} \\rvert \\geq \\eta n$ but we cannot tell the two models apart. \n\nFor more intuition, consider the problem of robustly estimating the mean of a 1-D Gaussian with standard deviation $\\sigma$, given an $\\eta$-corrupted sample. Then, the optimal error we can achieve is $\\Omega(\\sigma \\cdot \\eta)$. I.e., there are two Gaussian distributions $G_1, G_2$ with mean $\\mu_1, \\mu_2$ and standard deviations $\\sigma_1, \\sigma_2$, such that $\\lvert \\mu_1 - \\mu_2 \\rvert \\geq \\Omega(\\min(\\sigma_1, \\sigma_2) \\cdot \\eta)$, but we cannot distinguish $G_1$ and $G_2$. We expect a similar lower bound for the i.i.d. Bernoulli case. In this case, the means would be $d_1/ n$ and $d_2/n$ and we get that $\\lvert \\tfrac {d_1} n - \\tfrac {d_2} n \\rvert \\geq \\Omega \\left ( \\sqrt{\\tfrac{\\min (d_1, d_2) } n}\\eta \\right )$. This implies that $\\lvert d_1 - d_2 \\rvert \\geq  \\Omega \\left ( \\sqrt{\\min ( d_1, d_2 ) }  \\sqrt{n}\\cdot \\eta \\right )$ which is much larger than the error we obtain."}]

Author rebuttal:

Meta-review: The paper proposes a sum-of-squares (SoS) relaxation for estimating the edge density of an Erdos-Renyi graph, where an adversary can arbitrarily add/remove edges incident to a fraction of the nodes. The main claims of going from exponential time to polynomial time, matching information-theoretic lower bounds, and achieving the optimal breakdown point, are properly defended, albeit only theoretically. Independent experimental confirmation would have been great to have as well.

Opinions were mixed but mostly positive. Thus I finally decided for acceptance. The most important concern raised by several reviewers was the lack of experiments. During the discussion, the authors agree that a level-$\ell$ SoS relaxation take $n^{O( \ell )}$ time where "the constant in the big $O(.)$ is quite large". In the appendix, the authors mention a level-8 SoS relaxation.

I still believe the contribution to be important (going from exponential time to polynomial time) but the high factor in the polynomial should be acknowledged in the abstract, introduction and over the whole manuscript (not only in the appendix) in the camera-ready version. Please also take into the account the comments from all reviewers.
Decision: Accept (poster)