Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point

Thank you for your review and positive comments!

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

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

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

Thank you for your review and positive comments!

Regarding 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)}$.

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

Thank you for your review and positive comments!

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

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

Thank you for your review and positive comments!

The 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$.

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