Controlling The Spread of Epidemics on Networks with Differential Privacy

We thank the reviewer for pointing out the lack of explanation in the proof in the appendix. We agree that this part of the argument can be difficult to follow, and we will revise the notation and provide additional clarification in the revised version. Below is an explanation of the equation chain:

1. Observe that for any pair of sets $S_j$ and $S_j'$, that are picked after step $t$, are identical, and $m(S_j, e_0) = m(S_j, e_0)$. However, $A(S_j)\leq A(S_j')$ since $e_0$ has been covered more in step $t$. The inequality is strict iff $S_{j'}$ fully satisfies $e_0$'s covering constraint of at the time it is selected. Therefore, by definition of $S^{I,i} = \{j:A_i(S_j)<A_i(S_j')\}$, for any $j\in S^{I,i}$ we have $A_i(S_j') = A_i(S_j)+1$, which implies the transition from line 1 to line 2.

2. For line 2 $\to$ line 3. Recall that in step $i$, set $S_{\pi_i}$, is sampled from among $j>t$ with probability proportional to $\exp(\epsilon'A_i(S_j))$, so it becomes $(\sum_{j\in S^{I,i}}Pr[j])/(\sum_{j\geq i}Pr[j])$, which corresponds to the probability of selecting an index $j \in S^{I,i}$ conditioned on $j \geq i$.

3. Line 3 $\to$ line 4. The numerator in the previous expression is simply the probability that $\pi_i\in S^{I,i}$, which we denote as $\Pr[S^{I,i}]$.

I think I can now understand the proof. I therefore will increase my score.

We thank the reviewer for pointing this out — it is a rather unexpected result: Stronger privacy requires larger degree violations, which more than offsets the increased randomness in the permutations. However, the authors believe that the optimal choice of $\epsilon$ is best left to the governing body to determine as there are serious ethical implications.

We thank the reviewer for their thoughtful comments and useful suggestions, which we will incorporate in the revised version of the paper. We agree that including too many technical results in the main body limits clarity, and the paper would benefit from moving some of these details to the appendix. We will also revise the notation and streamline the presentation to improve overall readability. Below, we address the reviewer’s specific questions and clarify some notation:

• Lemma 4.1 refers to the unweighted case, the cost $|OPT|$ is the number of sets required by the solution. $f$ is the maximum number of sets $S_i$ any element can occur in. This is clarified in the supplementary material, as this parameter is only used in the runtime analysis, which we plan to fully move to the appendix. The parameter $T$ in Section 5.1 is just a threshold value.

• In the non-private setting, a greedy algorithm achieves an approximation ratio of $H(\max_S \sum_e m(S,e))$ (see [42]). While we mention this in the special case discussed in Section 6, we agree that introducing it earlier would help contextualize our approximation results and the trade-offs in the private setting.

• The mapping from an implicit solution (a permutation) to a set of nodes is hindered by privacy, as it would depend on information about the edges, which are to be kept private. The central planner may conduct this step, at an additional privacy cost. We believe it inadvisable to publish the mapped set of nodes from the implicit solution on some special cases of PrivateMaxDeg: for example the case where target $D=0$ (vertex cover), in which every private solution must select at least all but one vertex.

• Lemma 4.5 result is for the explicit solution algorithm, which does not guarantee full coverage of all elements. There are lower bounds to the cost of explicit private solutions. For instance, in the vertex cover case ($D=0$), a private algorithm must choose all but 1 vertex (otherwise, if there are two vertex not in the output, then one can conclude that there is no edge between them).

• Indeed, minimizing solving MaxDegree problem provides weaker guarantees than solving spectral radius minimization. However, spectral radius is significantly harder to optimize, and the corresponding privacy and algorithm runtime guarantees are also weaker. In scenarios where privacy and efficiency are the primary concerns, using the max degree algorithms in Section 4 would be more practical.

We appreciate the reviewer’s comments and believe that addressing these would help improve the clarity and accessibility of the paper.