Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

Thank you for your valuable feedback!

While it is justified by lower bounds, an argument could be made that the additive error is large and is unlikely to yield a practical implementation.

We are hopeful that for dense graphs, where cuts can be as large as $\Omega(n^2)$, our techniques could yield improved practical results over the prior $n^{1.5}$ error algorithms. However, our focus is on proving an improved asymptotic privacy-utility trade-off.

There is a possible typo on line 365: all S should be S’

Thanks, we will update the typo.

Are there any prior applications of private expander decomposition? If not, I think this fact should be highlighted more.

To the best of our knowledge, we are the first to study private expander decomposition. In our paper we mainly focused on cuts, and it is an interesting future direction to study further applications of our private expander procedure. We will make sure to highlight this in the paper.

Thank you for your valuable feedback!

Thank you for your valuable feedback! We will adjust the final draft according to your suggestions, elaborating where there were points of confusion.

I'm confused by the proof of Theorem 3.2 It just says that it's in Algorithm 1. That's not really a proof. Or are you just trying to say that you will show this constructively by proving the correctness of Algorithm 1?

We apologize for the confusion. Please note that the proof environment for Theorem 3.2 ends on Line 310 and the proof is contained in Subsections 3.1 - 3.3. Each subsection handles the privacy, approximation, and success probability parts of the proof separately. However, we admit it is misleading to use numbered subsections to organize a proof. We will change the style.

For Theorem 4.1, maybe explain the meanings of d_exp and d_size. I don't know what they're supposed to mean beforehand, and what they're supposed to imply.

We used the same notation as in the prior work of Li & Saranurak. The intuition is that the theorem can find a cut such that any possible cut with substantially smaller sparsity (as measured by d_exp; note exp stands for expansion), must also be smaller in size in terms of the number of vertices (as measured by d_size). Note that later in Theorem 4.2 we obtain a private version of Theorem 4.1. We will update the text to include more intuition.

More explanation about the theorems and what their roles are would make sense. For example, some details about what Theorem 4.1 and 4.2 are saying, along with what Lemmata 4.3 and 4.4 are implying would be really helpful. It just feels like I'm reading technical statements without context/intuition on why they're going to be useful.

Thanks for the suggestion. We will include a more intuitive summary of Section 4 before the theorem statements and proofs in the paper. At a high level, in Theorem 4.1 and Lemma 4.3, we introduce the existence of an algorithm for non-private expander decomposition from prior work. By expander decomposition, we mean a partition of the vertices such that every part has high connectivity in the sense that every cut is non-sparse (has a high fraction of edges to vertices). We use Lemma 4.4 from prior work, which upper-bounds the recursive depth of this algorithm. Theorem 4.2 introduces our contribution, which replaces the core algorithm from Theorem 4.1 with a private analogue.

For Section 3.1, two partitions will get affected if you're doing replacement definition. Under add/remove, only one partition will be affected. Please, be clear about your model of privacy.

This is a good question. We use the standard model of edge-neighboring privacy, which is the same as the add/remove model over the database of edges. Importantly, two partitions are still affected in the add/remove model because a single edge touches two vertices.

Have you thought about node DP for this problem? What could the potential challenges be and how would the bounds be affected? It's just a speculative question, rather than something for the purpose of evaluation.

This is a nice open question raised by Elias et al. This setting is much harder and there is nothing non-trivial known for preserving cuts using node DP to the best of our knowledge.

Also, have you thought about proving lower bounds in this multiplicative error setting? I'm mostly speculating about the tightness of your bounds (mostly out of curiosity).

We are optimistic that near-linear additive error, when allowing constant multiplicative error, is possible to achieve in polynomial time. It is already known how to achieve this in exponential running time; see Eliás, Kapralov, Kulkarni, Lee SODA’20. We believe this is an interesting challenge for the field. We also note that $\Omega(n)$ error is necessary even when allowed a multiplicative approximation, see Dalirrooyfard, Mitrović, Yuriy Nevmyvaka, NeurIPS’23.

Thank you for your valuable feedback!

In definition 2.4, since non-edges are viewed as weight 0 edges, and (u, v) can be any pair of nodes, the edge set should be V^2? So E and E’ both should be V^2. This would be relevant for all the formal statements which mention E.

Thank you. This is a good point, and we will update the text to address it.

Do the results hold if the set of edges is fixed and only the weights of two existing edges differ by 1?

Yes, this is an easier setting (consider the non-edges to be zero-weight edges), so our results also hold.

It might be helpful to explain the main theorems a bit more as part of the technical contribution in section 1.2.

Thank you. We will add more exposition in Section 1.2 in the final version.

It would be useful to explain the notion of private expanders

By an expander partition, we intuitively mean a partition of the nodes into some number of parts such that the “connectivity inside” every part is high and the total number of edges in between the partitions is low. We use sparsity to formalize “connectivity” (see line 140, right column). We want to output such a decomposition which respects edge-neighboring privacy.

Is it possible to get better approximation using your approach if you preserve only large cuts lower bounded by some threshold?

Our results directly imply that we obtain a multiplicative approximation for all cuts above $n^{1.25}$ (ignoring logarithmic and privacy factors). This improves upon prior work which can only guarantee a multiplicative approx. for cuts above $n^{1.5}$. It is an interesting open question of whether one can do better.

Would the techniques work for other notions of expansion?

We did not consider other notions of expansion since our final goal was towards cut approximation, but this is an interesting direction for future work.