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

Question 1:

Could you please elaborate on which part of your proof technique deviates from that in [Chen et al.]? Alternatively, are the proof techniques similar, while you are just addressing different problems in this paper?

Response 1: On the one hand, the algorithm in [CDd+24] uses an edge density estimation algorithm based on [SU19] as a preprocessing step and proceeds by an sum-of-square exponential mechanism to privately estimate the underlying graphon. Concretely for the task of edge density estimation, [CDd+24] does not improve over [SU19] and uses in fact the same algorithm as [SU19]. To improve the edge density estimation results in [SU19], we developed a new private edge density estimation algorithm using the sum-of-squares hierarchy, which is completely different from the techniques in [SU19] based on smooth sensitivity.

On the other hand, although [CDd+24] also relies on the sum-of-squares exponential mechanism for graphon estimation, our program constraints and identifiability proof are significantly different. There are two particularly notable technical differences:

• Our strategy is closely related to the reduction from robustness to privacy framework developed in [HKMN23], while [CDd+24] relies on sum-of-squares Lipshitz extensions.
• The private graphon estimation algorithm in [CDd+24] relies on a single sum-of-squares program, while our algorithm has two stages: the rough estimation and the fine estimation, each with a different sum-of-squares program. The reason is that we found it difficult to achieve nearly optimal error rate using a single sum-of-squares program.

Question 2:

There is also a theorem in [Chen et al.] for edge density estimation of stochastic block random graphs (Lemma 4.10), and it appears that their utility is better. Could you explain the fundamental obstacle between stochastic block random graphs and the more general inhomogeneous graphs that prevents the estimation for inhomogeneous graphs from achieving results as good as those for stochastic block random graphs? Would you mind adding more discussion about the results in [Chen et al.]?

Response 2: We will add more discussion about the results in [CDd+24] in our proceedings version. For the task of edge density estimation, [CDd+24] actually does not make use of any structure specific to stochastic block random graphs, but just treat them as inhomogeneous random graphs. So [CDd+24, Lemma 4.10] is essentially a result on edge density estimation of inhomogeneous random graphs. The algorithm behind [CDd+24, Lemma 4.10] uses an edge density estimation algorithm based on [SU19]. The error bound stated in [CDd+24, Lemma 4.10] is actually only the privacy cost. The total error bound of [CDd+24, Lemma 4.10] should also include the non-private error which is the same as the non-private error in our Theorem 1.6. In terms of privacy cost, our Theorem 1.6 actually improves over the guarantees of Lemma 4.10 in [CDd+24]. More specifically, the privacy cost of [CDd+24, Lemma 4.10] is

$$|{\hat{\rho}-\rho}|^2 \leq \tilde{O} \left(\frac{R^2\rho^2}{\epsilon^2 n^2}+\frac{1}{\epsilon^4 n^4}\right) .$$

In comparison, our Theorem 1.6 gives a privacy cost of

$$|{\hat{\rho}-\rho}|^2 \leq \tilde{O} \left(\frac{R^2\rho^2}{\epsilon^2 n^2}\right) .$$

Reference:

• [CDd+24] Chen, Hongjie, et al. "Private graphon estimation via sum-of-squares." Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.
• [SU19] Ullman, Jonathan, and Adam Sealfon. "Efficiently estimating erdos-renyi graphs with node differential privacy." Advances in Neural Information Processing Systems 32 (2019).
• [HKMN23] Hopkins, Samuel B., et al. "Robustness implies privacy in statistical estimation." Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023.

Question 1:

Is it possible to design algorithms when the entries of the connection probability matrix are not independent?

Response 1: Yes, our algorithm guarantees can extend to some settings where the edges in the graph are not independent:

• As our algorithm is robust under node corruption, the guarantees still hold even under minor dependence between the edges in the graph.
• Moreover, we expect that the guarantees of our algorithm easily extend to graphs with bounded maximum degree and bounded spectral norm, as we only exploit these properties of the graph for adding constraints to the sum-of-squares semidefinite programming.

These assumptions are easy to test given the graph instance, and are significantly weaker than the independence assumption.

Question 2:

Do any algorithmic ideas translate to other graph statistics like the number of triangles and k-stars?

Response 2: This is a great question.

• For Erdos-Renyi random graphs, as the only parameter for the distribution is the edge density $p^\circ$, we can obtain non-trivial (and potentially optimal) guarantees for estimating the number of triangles/k-stars by relating the expectation to $p$.
• For inhomogenous random graphs, we are not so sure. We expect our techniques can lead to private algorithms for counting constant-size subgraphs such as triangles and k-stars with non-trivial guarantees, when the inhomogeneity (measured by the ratio between the maximum edge connection probability and the average edge density) is bounded. The observation is that, when a small $\eta$-fraction of the nodes are corrupted, the number of triangles/k-stars in a large induced subgraph of the given corrupted graph with bounded degree and supported on $(1-\eta)n$ vertices is still close to the total number of triangles/k-stars in the original uncorrupted random graph.

Comment 1:

You should define the quantity edge density formally somewhere since the whole paper hinges on the reader understanding what it is.

Response 1: Thank you for pointing it out! We will add a formal definition in our proceedings version.

Question 2:

Can you expand on the challenges in designing the sum-of-squares algorithm for estimating the edge density? I would like to be more convinced that this result is not simply piggybacking off on the Hopkins et al result.

Response 2: This is a great question. We will discuss in more detail in the proceedings version.

• [HKMN23] and [AUZ23] showed a general connection between privacy and robustness. In general, this connection does not provide guarantees in terms of computational complexity. However there are several important examples where this connection can be used to transform efficient robust algorithms to efficient private algorithms.
• For the problem of robust edge density estimation under node corruption, there is no known sum-of-squares algorithm before our work, and we are only aware of an iterative algorithm [AJK+22]. For such algorithms not based on convex relaxation, it is completely unclear how to use the aforementioned connection between privacy and robustness estimation toward an efficient private algorithm.
• We cannot just apply previous robust mean estimation algorithms based on sum-of-squares (e.g. Hopkins et al 2024). On the one hand, if we view edge density estimation as a one-dimensional Bernoulli mean estimation task, then previous algorithms are only optimal under edge corruption, but suboptimal for the node corruption model. On the other hand, if we view edge density estimation as an $n$-dimensional mean estimation task, then samples (i.e. rows of the adjacency matrix) are not independent.
• In general, when designing a sum-of-squares algorithm, the main challenges are identifying the right set of polynomial constraints and coming up with sum-of-squares proofs.

Reference:

• [AJK+22] Acharya, Jayadev, et al. "Robust estimation for random graphs." Conference on Learning Theory. PMLR, 2022.
• [HKMN23] Hopkins, Samuel B., et al. "Robustness implies privacy in statistical estimation." Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023.
• [AUZ23] Asi, Hilal, Jonathan Ullman, and Lydia Zakynthinou. "From robustness to privacy and back." International Conference on Machine Learning. PMLR, 2023.

Question 1:

How does the rate achieved for inhomogeneous random graphs compare to the rate achieved by the exponential-time algorithm of [BCSZ18] for graphons?

Response 1: [BCSZ18] uses the Laplace mechanism for edge density estimation of graphons. The privacy cost of their algorithm is $\mathrm{polylog}(n) R/(\epsilon d)$, significantly worse than $\mathrm{polylog}(n) R/(\epsilon n)$ in our result.

Question 2:

Is there prior work on robust estimation of general inhomogeneous random graphs, and if so, what rate was achieved?

Response 2: To the best of our knowledge, no previous work had studied robust estimation of general inhomogeneous random graphs.

Question 3:

Can we hope to extend the privacy lower bounds (Theorem 1.5 and 1.8) to (epsilon, delta)-DP and not just epsilon-DP?

Response 3: Our proof of the $\epsilon$-DP lower bound uses a packing argument. Packing arguments can also be used to prove ($\epsilon$,$\delta$)-DP lower bounds, but they usually would not result in meaningful ($\epsilon$,$\delta$)-DP lower bounds. A standard and powerful tool to prove ($\epsilon$,$\delta$)-DP lower bounds is the so-called fingerprinting technique [BUV14], which is totally different from packing arguments. We expect some non-trivial work is needed to prove meaningful ($\epsilon$,$\delta$)-DP lower bounds for this problem. This is an interesting open question.

Comment 4:

line 188: should $d^\circ$ be defined as $(n-1) p^\circ$ instead of $n p^\circ$?

Response 4: Thank you for pointing this out. We define $d^\circ = n p^\circ$ just for notational convenience. Strictly speaking, the expected average degree should be $(n-1) p^\circ$ instead of $d^\circ$. However, these two quantities are equivalent as $(n-1) p^\circ = \frac{n-1}{n} d^\circ$.

Reference:

• [BUV14] Bun, Mark, Jonathan Ullman, and Salil Vadhan. "Fingerprinting codes and the price of approximate differential privacy." Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014.
• [BCSZ18] Borgs, Christian, et al. "Revealing network structure, confidentially: Improved rates for node-private graphon estimation." 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018.

Comment 1:

This is not directly a very practical problem, since Erdos-Renyi graphs do not appear frequently in natural contexts and even the generalization assumes that the selection of different edges is independent, which is not true for many models of real-world graphs.

Response 1: Indeed, developing realistic and mathematically tractable random graph models is an important and long-standing question in the field. Our algorithm and theoretical analysis extend to more general graphs in the following aspects:

• In the paper, we extend our algorithms and theoretical guarantees for the much more general inhomogeneous random graph models, where we make minimal assumptions beyond the independence between the edges. Also, since our algorithm is robust under node corruption, the guarantees will still hold even under minor dependence between the edges in the graph.

• Moreover, we expect that the guarantees of our algorithm easily extend to graphs with bounded maximum degree and bounded spectral radius, which goes beyond the setting where the edges in the graph are independent. Particularly these assumptions are easy to test given the graph instance.

Therefore, our work can be viewed as a first step towards private and efficient algorithms for statistical estimation in more realistic graph models.

Comment 2:

The algorithm may be difficult to implement and run in practice due to the complexity of tools used, which include semidefinite programming.

Response 2: We completely agree that it remains a fascinating and important open question to obtain algorithms for this problem that are more practical or at least have better running times, ideally nearly-linear time. Our theoretical work shows that polynomial-time algorithms for this problem exist and that there are no complexity-theoretic obstacles toward practical algorithms. We believe that such basic, polynomial time solvable problems ought to have practical algorithms. We hope that some of the ideas behind our algorithm could pave the way toward such practical algorithms for this basic problem.

Question 3:

Just to make sure, in the inhomogeneous setting, the algorithm has to know $Q^\circ$, right? Otherwise, it could be a zero-one matrix equal to the graph adjacency matrix. What guarantees can be given if $Q^\circ$ is unknown?

Response 3: No, our algorithm does not need to know $Q^{\circ}$. We assume there is an unknown $Q^{\circ}$. Given a graph generated by $Q^{\circ}$, our goal is to estimate the average of the entries in the matrix $Q^{\circ}$. The privacy cost of our algorithm is $\frac{R \log n}{\epsilon n}$ where $R$ is the ratio between the largest entry of $Q^{\circ}$ and the average of $Q^{\circ}$. For $Q^{\circ}$ equal to a graph adjacency matrix, we have $R=1/p$ where $p$ is the edge density of the graph.