Controlling The Spread of Epidemics on Networks with Differential Privacy
Authors: Dung Nguyen
Aravind Srinivasan
Renata Valieva
Anil Vullikanti
Jiayi Wu
Venue: NeurIPS 2025 poster ()
Keywords: Differential privacy
network science
computational epidemiology
public health
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Algorithms to Contain the Spread of Epidemics by Reducing the Maximum Degree and Spectral Radius under Differential Privacy.

Abstract: Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited.
This is a challenging question when the contact network is very heterogeneous, and strategies based on controlling network properties, such as the degree and spectral radius, have been shown to be effective.
Implementation of such strategies requires detailed information on the contact structure, which might be sensitive in many applications.
Our focus here is on choosing effective vaccination strategies when the edges are sensitive and differential privacy guarantees are needed.
Our main contributions are $(\varepsilon,\delta)$-differentially private algorithms for designing vaccination strategies by reducing the maximum degree and spectral radius.
Our key technique is a private algorithm for the multi-set multi-cover problem, which we use for controlling network properties.
We evaluate privacy-utility tradeoffs of our algorithms on multiple synthetic and real-world networks, and show their effectiveness.

Controlling the Spread of Epidemics on Networks with Differential Privacy
Dung Nguyen
Aravind Srinivasan
Department of Computer Science Haverford College Haverford, PA 19041
Department of Computer Science
University of Maryland College Park, MD 20742
d @haverford. edu
sr srin01umm 1ann00mmm@@mmalll com
Renata Valieva
Anil Vullikanti
Department of Mathematics University of Maryland College Park, MD 20742 rvalieva@umd, edu
Department of Computer Science
University of Virginia Charlottesville, VA 22904
vaakumar@virginia. edu
Jiayi Wu
Department of Computer Science University of Maryland College Park, MD 20742 j jwu12328tterpmail. umd. edu
Abstract
Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited. This is a challenging question when the contact network is very heterogeneous, and strategies based controlling network properties, such the degree and spectral radius, have been shown to effective. Implementation of such strategies requires detailed information the contact structure, which might be sensitive in many applications. Our focus here is on choosing effective vaccination strategies when the edges sensitive and differential privacy guarantees are needed. Our main contributions are (s, -)ddiffrrent private algorithms for designing vaceination strategies by reducing the maximum degree and spectral radius. Our key technique is a private algorithm for the multi-set multi-cover problem, which use for controlling network properties. We evaluate privacy- utility tradcoffs of our algorithms on multiple synthetic and real-world networks, and show their effectiveness.
Introduction
fundamental public health problem is implement interventions such vaccination control the spread of an outbreak, e.g., (37 g. This is especially important in the early stages of an outbreak, when resources are limited. Here, focus network based models for epidemic spread, such as SI/SIS/SIR models, in which the disease spreads on a contact network G (V, E') from an infected node E V each susceptible neighbor of u independently with some probability, e.g., [32 16, 36]; such models (which are simplifications of agent based models) have been used extensively in public health analyses in recent years. Interventions such as vaccination and isolation, can be modeled as node removal in such models [32] The Vaccination Problem (VP), introduced
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in [15] for an SI type model (a similar version was considered in (2I)), formalizes the design of an optimal vaccination strategy as choosing a subset S V so that the expected number of infections in the residual graph GIV S] is minimized. This problem remains a challenging computational
problem, and is NP-hard, in general [21 15 45.
Due to the computational hardness of the vaccination problem, a number of heuristics have been proposed for choosing set 5 vaccinate, which involve choosing nodes based on properties related to the underlying contact network, such as degree and different notions of centrality, e.g., betweenness, pagerank and eigenscore 8 9 [6] ; such heuristics have been shown to be much more effective that picking nodes randomly. In particular, choosing nodes which lead to reduction in certain network properties of the residual network (i.e., after the vaceinated nodes are removed), below a critical threshold are quite effective. Examples of such strategies are reducing the maximum degree (the MAXDEG problem) 4 36 9, and the spectral radius (the MinSR problem) 46 38]; we note that heuristics for the MAXDEG and MinSR problems have been used in many network based epidemic models, such as SIS, SIR, SHIR, etc. [38. as well as other contagion models, such as spread of influence 227 43 Optimal choice of such nodes (whose removal leads to the maximum reduction in such metrics) is also a difficult computational problem. There is a lot of work on approximation algorithms, e.g.. 46
40 and is our focus here.
In most settings, data privacy is a fundamental challenge, due to the risk of revealing sensitive private information of users. For instance, individuals might wish to keep certain kinds of contacts private, since these might reflect sensitive activities they participate in. Privacy concerns were a
major factor limiting user adoption of digital contact tracing apps [5] Differential Privacy (DP) [3 has emerged as very popular notion for supporting queries on private and sensitive data. Here, we study the problems of choosing nodes with edge DP guarantees to minimize the maximum degree MPRIVMAXDEO and the spectral radius (PRIVMINSR), we note that the edge DP model has been studied quite extensively (the other commonly used model of node DP, e.g., 126 49 25], is not suitable for the MAXEM and PRIVMINSR problems, since the goal is to output selected nodes).
There has been recent work on different kinds of epidemic analyses with privacy. e.g., 7 31 30)
and for more general problems of network science and graph mining, e.g., [34 12 However, the PRIVMAXDEG and PRIVMINSR problems have not been studied so far.
10
26
49 25
The PRIVMAXDEG and PRIVMINSK problems are closely related to a fundamental problem in combinatorial optimization, namely multi-set multi-cover. While there has been some work on covering problems with privacy, e.g., [19 30 [ the version we study has not been considered before. Further, most of the prior work on covering problems with privacy, except [30], considers an implicit or blackboard model, which does not make the solution explicit; instead, sets which are part of the solution know this implicitly. This kind of implicit solution is not suitable for problems of epidemic control we consider here, and we design techniques to make our private solutions explicit. Our main contributions are summarized below.
1. Minimizing the maximum degree with edge DP (PRIVATEMAXDDG), We design Algo- rithm [ (Section 4.2) for this problem, and show that it gives an O(In with high probability. PRIVMAXDEG can be reduced the private multi-set multi-cover problem UPRIAAEEMULSSET... generalization of the set cover problem with privacy, which has not been con- sidered before. We show that the iterative exponential mechanism can be used for PRIVATEMULSSET (Section 4). and discuss how PRIVMAXDEG can be solved by reducing to it (Algorithm D). We also show how to construct explicit solutions for PRIVMAXDEG (Algorithm 2 using the sparse vector technique [13].
2. Minimizing the spectral radius with edge DP (INIVM This turns out to be much harder problem because non-private algorithms use metrics (c.g., number of walks through a node) which have high sensitivity 44 While the spectral radius satisfies p(G) S A, where p(G) and A denote the spectral radius and maximum degree, respectively, this bound can be quite weak in many graphs. We present two algorithms which lead to stronger bounds on p(G) under different regimes (Section 55; the first is based on reducing the number of walks of a certain length, as in and the second is in terms of the average degree of neighbors [7..
3. Lower bounds. It is well-known that for the covering problems, no differentially private algorithms can both output a non- nov-trivial explicit solution and satisfy the covering requirement at the same time. We derive the lower bounds for even outputting an explicit partial coverage requirement, stating that any (e, -iiffeerrentillly private algorithm using no more than (log + |OPT] must incur an
2

---

additive partial coverage requirement error of at least m2) Similarly, for the PRIVATEMAXDEG, the explicit solution must have an additive error of at least ([lo n) for the target maximum degree.
Experimental results. We evaluate our methods on realistic and random networks. Our solutions lead to good bounds on both the maximum degree and the spectral radius. We find that implicit solutions have a higher cost relative to the non-private solutions, while the explicit solutions are quite sensitive the privacy parameters, highlighting the need for carefully choosing the privacy parameters. We observe that our empirical results for the PRIVATEMAXDES problem are consistent with the theoretical bounds we prove for our algorithms.
Most of the technical discussions - including algorithms, proofs, and experimental results are deferred to the supplementary appendices due to space constraints. In particular, Appendices C.I.1 and C.I.A 2 provide full technical treatments of the Unweighted and Weighted variants of PRI- VATEMUL.STT, including the utility and runtime analyses of Algorithms [ and 6 respectively. Additional technical details on the PRIVATEMAXDEGG problem are presented in Appendix [c.2 Appendix C.3 discusses lower bounds, while Appendix D contains the proof's and runtime analysis relevant to the PRIVMINSR problem. Finally, Appendix E contains additional experimental results.
Related Work
As mentioned earlier, the PRIV and PRIVMINSR problems have not been studied earlier. We briefly summarize prior work two areas directly related to work: (1) network-based epidemic control and (2) differential privacy for network and graph problems; additional discussion presented in Section [A] in the appendix. There has been lot of work on non-private algorithms for controlling epidemic spread on networks, e.g., [48]
33). As mentioned earlier, strategies have been shown be quite effective in many classes of networks (including random graphs). There has also been prior work on reducing the spectral radius of the contact network, e.g.. 41 39
based on degree centrality, e.g.,
(9] 33
35 which is closely related the concept of epidemic threshold-a a quantity that determines if there will be large outbreak or not.
While there is a lot of work private computation of diffferent kinds graph properties (c.g., degree distribution, subgraph counts and community detection), e.g., [26]
there is no prior work the problems of controlling metries related to epidemic spread. The most relevant work involves private algorithms for other problems in computational epidemiology e.g., computing the reproductive number 77. estimation of the number of infections locations for vaccine distribution (30 However, none of these methods imply solutions for the problems we study here.
22
3 23
(31), and determining facility
3 Preliminaries
Definition 3.1. A mechanism M - is (dife-iiier private for any two neighboring inputs X, ~ X2, and any measurable subset of the output space S C y, the following holds: Px(M(()) E ST I et PX) E S 5 [33
When 5 O, say that M is e-differentially private. We study graph datasets, i.c., X' corresponds to the set graphs with n nodes. We consider the edge-DP model, where V, the set of nodes, is public and F, the set of edges, is kept private. More formally, considered neighbors if Vi = V/2 and there exists an edge e such that F5 = E2 (e)(e) (i.e. they differ in the existence of single edge). We note that there in graphs, such as node DP, e.g., [26;; since our problems involve choosing subsets of nodes to be vaccinated, this model is not relevant here, and we only focus on edge DP.
networks G1 (Vi, Fr); G2 (V2, F22), (e) or F2 = E, (e) other models of privacy
We also utilize some standard privacy techniques and notations, such as the Exponential mechanism, Laplace mechanism, and AboveThreshold. See Appendix B for their definitions.
3.1 Problem Formulations
We study interventions for epidemic control, such as vaccination or isolation, which can be modeled removing nodes from a contact network G (V, E') under the SIR model [32] 16 Reducing
3

---

structural properties of the contact network such as the maximum degree A(G) or the spectral radius p(G) can help limit epidemic spread [32 38
Let n = V and m = -|E]- For a graph G, let d(u, G) denote the degree of a node v, and let A(G = max, d(v, G) be the maximum degree in G. Let p(G) denote the largest eigenvalue of the adjacency matrix of G. We also consider weighted graphs where w(r) is the weight of node t.
Definition 3.2. (PRIvMAXDEG problem) Given a graph G = (V, E"), target max degree D < AGG), and privacy parameters e, the goal is compute the smallest subset S C V to remove (or vaccinate), such that the induced subgraph G' = G[V \ S] satisfies A(G") I D, while satisfying edge-DP.
We refer to the non-private version of this problem MAXDEG, and use OPTMANDEO(C D) min[|S] : S C V, V.A(G \ S)) < D} to denote the optimal solution of the non-private version. Additionally, GSMAXDEO denotes the global sensitivity of MAXDEG.
Definition 3.3. (PRIVMINSR problem) Given graph G, larget threshold r, and privacy parame-
ters 6. the goal is to compute the smallest subset S C V to remove, such that p[G[V \ S)) s T, while satisfying edge-DP.
We refer to the non-private version of this problem by MinSR. Many bounds known for the spectral radius, including: p(G) < AG) and p(G) S max, vd(v, G)d G), where d2 G)
Eneo d(u, G)/d(v, G) 24).
Explicit and implicit solutions. For the problems discussed above, the explicit version outputs an actual solution that satisfies edge-DP. However, for covering type problems, this is often challenging under DP [9). We therefore also consider implicit solutions these output a differentially private quantity x such that each node o can determine whether it is part of the solution based on π and G.
3.2 Multi-set Multi-cover problem
To solve some of the above problems, we reduce them to the Multi-set Multi-cover problem, which we formally define as follows:
Definition 3.4. (MULSET problem) Let U = Cn) be a universe set on distinct elements. For each element e E U, let the covering requirement Te be the minimum number of times e must be covered, and let R = {re]eeu. Let = {S,....,, Sm } be a collection of multi-sets, where each set S; contains m(S,, e) copies of element e. We refer to m(SS, e) as the multiplicity of in St. It is common to denote as q = maxses [S] the largest set size, and as f max.et HS S)m((S, e) 2 1}1 the largest frequency of any element. The MULSET(U, S, R) asks to find the smallest sub-collection S' C such that each element e U is covered at least re times by the sets St.
In the WEIGHTEDMULSER problem (U,S, R, C), each set S E S has a cost, given by the function ::S. S + R. The objective is to find a cover 8 that minimizes the total cost, i.e., EseS C(S).
Now, we consider the differentially private version of this problem, denoted PRIVATEMUL To match the edge-DP model described earlier, we define neighboring instances of the Multi-set Multi-cover problem as follows. Two instances (U,S, R) and (U,S', R') are said to be neighbors one of the following conditions holds:
There exists an element E U such that Ira - r''l = 1, and all other coverage requirements and sets are identical. That is, S = S' and RAR' = (re: } for some e E U.
There exists an element e E U and an index E [m] such that the multi-sets S and S differ only in the multiplicity of e: (m(S,, e) - m SV. e)] 1. All other sets and coverage requirements remain unchanged, i.c., SAS' = {S,, S and
R.'
Reducing a graph's 'ss degree- -ased objective such as max, d(v, G) or max, d(v. G) dz(u, G) below a target threshold D can be naturally formulated as an instance of the MULSET problem. Specifically, we define the universe as U = V(G) and associate each vertex E ((G) with a multi-set Sn containing u and its neighbors. The covering requirements R are then defined to reflect how much the degree-related quantity, such as тe = max(d(r, G) D, 0) or max(d(v (v, G)- (r. G) D, 0), must be reduced at each vertex. These reductions are described formally in the corresponding sections.

---

4 PRIVATEMULSET and PRIVATEMAXDEG Problems
We now describe private algorithms for reducing degree- graph properties under the edge-DP model. These problems are reduced to instances of the PRIVATEMULSE framework introduced earlier. The intuition the following: for example, in the MAXDEGREE problem, the utility of removing node should naturally depend on how much its degree exceeds the threshold D, i.e., max(d(e, v. G) D) This translates naturally into the MULSET framework, where each element (e.g., edge neighborhood constraint) has coverage requirement, and sets (vertices) contribute to meeting them. More generally, any problem where elements contribute toward satisfying some threshold-based constraints can be reduced to instance of MUI.SET. We apply the same reduction principle to the SPECTRAL AARRAALAAAUS problem as well. In this section, we highlight the main ideas and results, using the private algorithm for MULSET black box. All formal details are deferred the appendix.
4.1 Multi-set Multi-cover Problem: Algorithm and Analysis
In this section we discuss the Unweighted case. The algorithm and analysis of the Weighted case are similarly constructed, and are discussed in Appendix C.1.2] Our differentially private algorithm for the PRIVATEMULSEY problem is inspired by [19]. The high-level idea to assign a utility score to each set according to how much it contributes toward the remaining coverage requirements. The algorithm then repeatedly samples sets using the exponential mechanism thereby ensuring differential privacy based on these utility scores. Once there are no sets left, the algorithm outputs an implicit solution - a permutation æ E (S) over the sets rather than an explicit cover. The permutation defines valid solution: for each element U, select the first few sets in the order of π so that the coverage requirement re is satisfied.
Lemma 4.1. Algorithm 5 is (e. diffferrenn private, and its output is a solution to PRI- VATEMULSET of cost most ((In m)/e + lnq) |OPT with probability least 1 - 1/m, where OPT denotes the cost of an optimal non-private solution.
4.2 The Private MaxDegree (PRIVATEMAXDEG) problem
The edge-privacy model of ARIVATEMAXDDE. is equivalent to the privacy model of PRIVATEMUL under natural transformation described in Lines 1-6 of Algorithm Specifically, vertex v with star set in PRIVATEMULSET, so
neighbors {u u :} in PRIVATEMAXDEG corresponds that the utility of selecting v that is naturally proportional to its degree (Gg is preserved in the PRIVATEMULSEET instance as well.
For the privacy preservation, we observe that, under this transformation, neighboring graphs G ~ G' that differ by a single edge (u, v) map PRIVATEMUL.SH instances that are most 4-step neighbors. Specifically, the covering requirements for and e change by at most 1 - i.e., Ir, ru S 1 and Ir. rl 1 and the multiplicities m(S., v)) and m(S,; u) also change by most 1.
Algorithm 1 Private algorithm for PRIVATEMAXDEG
Input: (c, graph G, target degree D
2: Initialize set system S <- 0, requirements R <-
3: for each e E V do
4: Define multiset S, with m(S., oo and m(S., u) for all w
5: S 2-& U-S (S.). R (ro = max(deg(u) D.0)}
6: end for
7: Set e' e/4, 8' + 8/403e'
8: Return: Algorithm 5 8 S, AApplying the private multi-set algorithm*
Utility analysis. Since reduce the PRIVATEMAXDEG problem instance of the PRI- VATEMULSET and apply Algorithm solve it, the utility of A (stated by Theorem 4.2) follows the utility of Algorithm 5 by setting [V 2GSMa 2 in Lemma 4.1 The
Note that without the privacy constraints greedy algorithm achieves an approximation ratio of H (maxs Ee e)) 0lnm)) [2]
5

---

analysis for the weighted PRIVATEMAXDEG problem follows identically to the unweighted case, using A the weighted version PRIVATEMULSET discussed earlier. Consequently, all arguments and results discussed previously are applicable with minimal modifications required for the utility bounds.
Theorem 4.2. Algorithm /
(e, ddiffferrtyy private, and the cost of its output is B [MATMA (((1+1/c) In (V]) with high probability.
4.2.1 Explicit Solution
We also provide an explicit solution of which nodes to remove, incurring an additional privacy cost of 461. Unlike the implicit solution, the explicit output may allow some remaining nodes whose degrees exceed the the target degree threshold D. This approach builds upon the permutation æ generated by the implicit algorithm: by applying the AboveThrrehold mechanism and removing only the first k nodes in we ensure that the maximum degree is bounded by D + O(log m/c). The resulting solution removes most O[OOPT] log k) nodes.
Algorithm 2 Explicit solution algorithm for PRIVATEMAXDEG
Input: Instance of PRIVATEMAXDES and a permutation obtained from the exponential mechanism
2: 7" 6 61n 6lnn/e' Lap(2/e1)
3: for i = n do
4: % + +; L4p(4/c))
5: end for
6: Let k be the first index such that Thk S T"
7: Output: ( (k))
Utility Analysis. Theorem 4.3 states the utility of the explicit solution output by Algorithm 2
We first
observe that if we stop the algorithm at some iteration where the selected node (and its equivalent set) longer improves the coverage requirement by an amount degree of the remaining graph is off from the target D by an amount at most Olog n).. Steps 2 6 of the algorithm follows the AboveThreshold technique select the first index & that approximately satisfies the covering requirement of k, i.e the noisy utility "/k of the set chosen step is relatively small enough (less than the noisy threshold 7"' of the true target threshold 7'). We then utilize the accuracy guarantee of the AboveTTheshool routine to argue that the selected index & is in fact not too far away from the "true" stopping iteration & where its utility truly falls below the threshold T.
6 log n//é,, then the maximum
Theorem 4.3. The output is of Algorithm 2 satisfies A(G - U (m - D + O(log n/c") with high probability. In addition, O(OPT logn/// n/c)) with high probability.
Lower bounds. The explicit solutions cannot guarantee the coverage for the PRIVATEMULSS under DP guarantee. In this section, argue that any explicit solution of the PRIVATEMULSSH containing no more than |O [T] + (log n.) sets can only guarantees some partial covering with the additive error at least 2llog n). For the PRIVATEMAXDEG, the following lemma states the additive error of the target maximum degree, similar to the lower bounds of the PRIVATEMULSET. which we present in Appendix C
Lemma 4.4. Lower bound of PRIVATEMAXDER Any explicit (c, 5)-differentiallly private algo- rithm for the PRIVATEMAXDEGRES removing at most O(logn) + |OPT] nodes with probability at least 1 C,C = n- RR1), must incur an additive error A(G U (T.) D + 220og n), where
(k) are the removed nodes.
Private SPECTRALRADIUS
In this section, we introduce two algorithms designed to reduce the spectral radius, p(G), of a given graph G (V, F). In particular, these algorithms minimize specific graph metries that upper bound pGG).

---

5.1 Bound via PARTIALSETCOVER
Our first approach based on the idea of reducing [W)(G)), the number of walks of length four, where (G) is the set of all such walks. We choose walks of length four because longer walks would have higher global sensitivity (generally, it is exponential in length of a walk), leading to larger privacy loss. Then, reducing [W) below nT implies bound on the spectral radius p(G) I O(n!/tT) Setting the threshold parameter T = A 1/2 thus achieves bound of ((11/1A1/2) which improves significantly over the bound p{G) S when A ((V)).
We employ the GREEDY WALK node selection algorithm from 44], which follows a greedy strategy to reduce the number of paths of a specified length. This algorithm, combined with the exponential mechanism, forms the first part our approach. Further, we reduce our problem to an instance of the Partial Set Cover problem: each vertex in the graph corresponds to set, and removing vertex "hits" R (or covers) a collection
walks that include it. Specifically, the utility of removing vertex is defined as the number of walks of length 4 that pass through v, formally given by: A(v) = w E W4(G) U E w)]. A differentially private algorithm for Partial Set Cover problem was introduced in (0),, using an approach similar to Algorithm However, it is important note that in this context, the sensitivity of [Wa(G) is 2
Algorithm 3 Private Hitting Walks Algorithm for PRIVMINSR
1: Input: Graph G = (V, E), privacy parameters (c, initialize permutation <
2: Set c' t
3: for i 1 to n do
4: Sample
with prob. & exp(e' A(v)), append and remove from V
5: end for
6: Set T A1/2 0 4nT + 0 Lap(2/e1)
7: for i = 1 to n do
8: % f- WG {T(,, ...,, ..........(()))) Lap(a/)))
9: end for
Let & be the first iteration such that 7/k S
11: Output: (I())....,
Lemma 5.1. Algorithm 3 is (e +i A3 -iifffrriirr private. IfT 2 61n n/é', the oufput V' {mI...., , Th of Algorithm 3 satisfies Wa(G[V \ V') S nT* + OOlogn and gives an O(log n) approximation with high probability.
5.2 Bound via PRIVATEMULSET
We can also apply Algorithm for PRIVATEMULSET to indirectly reduce p(G). According the spectral radius bounded by p(G) S max v V.en d(v. G), which always better than the trivial bound p(G) A. This improvement especially significant degree-disassortative graphs, where high-degree vertices are typically adjacent to many low-degree vertices. For further discussion see Appendix D.2
Algorithm 4 Private algorithm for PRIVATEMAXDEG
1: Input: (e, input graph G, target max degree D
2: S {Sa. v E V}. such that S, contains d copies of and d(u, G) copies of each u that is
adjacent
3: R (rv U VJ. V + max Emro d(u, G) D.0)
4: é' + e/4A
5: 8' + 1-844e
6: Return Algorithm
5 5',,''
Theorem 5.2. Algorithm 4 (e. didffffereetiallly private, and the cost of output B |
O + 1/e') In [VI) with high probability.
7

---

Network 1
Network 2
Network
800
Budget Used
600
400
200
0.25
0.5
1.0 Epsilon
2.0
4.0
0.25
0.5
1.0
4.0 2.0
4,0
0.25 0.5
1.0
2.0
Epsilon
Epsilon
Privacy
Non private
Figure 1: Effect of Privacy Budget Requirements on Montgomery County Subnets
6
Experimental evaluation
We evaluate the performance of our algorithms on different realistic and random networks in terms of
the following questions
Effeets of privacy budgets on the utility of our algorithm (both in terms vaccination budget and epidemic metries (G)) and p())).
Tradcoff between vaccination cost, different epidemic metrics, and privacy parameters.
Comparison between the implicit and explicit solutions.
Graph Name
#nodes
#edges
Subgraph of digital twin of 10,000
83842, 84025,
contact network for Mont- gomery. VA [16]
84549
BTER 28 with Power Law 1000
31530, 31582,
Degree (
0.5.p
31621
0.95, 7 0.05)
Table I: Network datasets used in evaluation
Datasets and setup. We consider two classes of networks, as summarized in Table The digital twin of a contact network 22] 16 model of real world activity based contact networks; we consider three subgraphs with 10,000 nodes of the network for Montgomery county VA. The BTER model (28) is a random graph model, which preserves both degree sequence and clustering, we consider three randomly generated networks. Both classes of networks have been used in a number
of epidemiological analyses, e.g., 332 g 1
Effect of privacy solution cost for the PRIVATEMANDES problem. Figure I shows the cost of the implicit solutions computed using Algorithm for the three subgraphs of the Montgomery county networks (labeled as Network 1-3). We use privacy budget of 10-6 and (0.25, 0.5, 1, 4). and set target degree of 45. For each e, we show a distribution over results computed by multiple runs of the algorithm. As described in the implicit Algorithm 5 for PRIVATEMUI.SHE the implicit solution computed and plotted here. The cost of the solution to non non- private greedy algorithm for the multi-set multi-cover problem (which has HA -a-proximmation(22 where H,, denotes the n-th harmonic number) is shown as the baseline. We note that the solution of Algorithm iis within a factor of about 10 of the non- non-private baseline, which could be viewed as being consistent with Theorem 4.2 further, the cost of the private solutions has a slight reduction with c.
Figure 2 shows the impact of privacy cost on the cost of the explicit solution for PRIVATEMAXDER for the three BTER networks (Table [D computed by Algorithm 2 with a target = 20. We pick 8 = 1/n 10-3 here, and have relaxed the privacy to the multi-set multi-cover definition rather than the edge private definition neighboring datasets. The results show, somewhat counter-intuitively that the solution cost actually increases with e. Since in explicit solutions the solution cost is mainly

---

Network
200
-0+++
Budget USe
120
100
80
4.0
5.0
6.0 Fpeloon
7.0
8.0
4,0
6.0 Epstion
7.0
4.0
3.0
7.0
8.0
Epetton
20
Figure 2: Effect of Privacy on Budget Requirements on BTER Graphs
Network
Network
Network
Degree Violatio
30
5.0
6.0
7.0
8.0
6.0 Epsilon
7.0
4.0
5.0
7.0
Easilon
Target Degree
20
25
30
Figure 3: Effect of Privacy Max Degree Violation on BTER Graphs
determined by Above Threshold step (in Algorithm| 2) which allows lower to halt set selection carlier (before certain vertices meet their cover requirements). the algorithm is closer to fulfilling the entire covering requirement in the non-private version increases, which explains this behavior. This is also consistent with Figure 3 which shows that the resulting violation in the maximum degree from the target decreases significantly with This suggests that the choice of the privacy budget needs to be done carefully.
Implicit Explicit solutions. We investigate the performance of the implicit and explicit solutions (Table 2). The main difference between two methods lies when the permutations terminate, explicit would halt before the target degree is fully satisfied whereas implicit would not. This is demonstrated in that implicit solutions perform much better with metrics like max degree whereas explicit solutions have significantly lower vaccination costs.

---

Table 2: Comparison of Average Performance of Implicit Explicit Solutions (c 4.0)
7
p
EXPLICIT?
BUDGET
MAX DEGREE
SPECTRAL RADIUS
YES
83.89
92.78
72.28
0.3
0.95
0.05
No
506.62
20
18.35
YES
66.19
92.80
77.99
0.5
0.95
0.05
No
430.36
20
18.55
Conclusion
We initiate the study of the challenging and largely unexplored problems of epidemic control networks under differential privacy. Our focus is on the approach of removing nodes from graph to optimize certain properties. such as the maximum degree and spectral radius the residual graph. which models the vaccination effect on contact network. We design the first set of algorithms along with rigorous utility analyses for minimizing the maximum degree and spectral radius under the edge differential privacy model. One of our main techniques involves transforming these problems into multi-set multi-cover problem and using its private solution to determine the sets of nodes to be removed (or vaccinated). While providing explicit solutions for covering-type problems is challenging. we employ the sparse vector technique to relax the covering requirement, allowing for approximate explicit solutions that can be used to design vaccination strategies. The experimental results of our algorithms, evaluated on multiple realistic and random networks, demonstrate good privacy-utility trade-offs.
Acknowledgments. We thank the NeurIPS reviewers for their thoughtful comments.
Disclosure Funding. This research is partially supported by NSF grants CCF- CCF-1918656, CNS- 2317193, I18-2331315, CCF-1918749 and CNS-2317194, and the Virginia Commonwealth Cyber Initiative Cybersecurity Research Award.
10

---

References
[1] Aniruddha Adiga, Devdatt Dubhashi, Bryan Lewis, Madhav Marathe, Srinivasan Venkatra- manan, and Anil Vullikanti. Mathematical models for covid-19 pandemie: comparative analysis. Journal of the Indian Institute of Science, pages 1-15, 2020.
[2] C. L. Barrett, R. J. Beckman, M. Khan, et al. Generation and analysis of large synthetic social contact networks. In Proceedings of the 2009 Winter Simulation Conference (WSC), pages 1003-1014, 2009.
[3] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, page 87-96, New York, NY, USA, 2013. Association for Computing Machinery.
[4] B. Bollobás and O. Riordan. Robustness and vulnerability of scale-free random graphs. Internet Mathematics, 2004.
[5] Eugene Chan and Najam Saqib. Privacy concerns can explain unwillingness to download and use contact tracing apps when covid-19 concerns are high. Computers in Human Behavior, 1 19:110671,, 01 2021.
[6] Bo Chen, Calvin Hawkins, Kasra Yazdani, and Matthew Hale. Edge differential privacy for algebraic connectivity of graphs. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2764-2769, IEEE, 2021.
[7] Bo Chen, Baike She, Calvin Hawkins, Alex Benvenuti, Brandon Fallin, Philip E Paré, and Matthew Hale. Differentially private computation of basic reproduction numbers in networked epidemic models. In 2024 American Control Conference (ACC), pages 4422-4427. IEEE, 2024.
[8] Jiangzhuo Chen, Stefan Hoops, Achla Marathe, Henning Mortveit, Bryan Lewis, Srinivasan Venkatramanan, Arash Haddadan, Parantapa Bhattacharya, Abhijin Adiga, Anil Vullikanti, et al. Effective social network-based allocation of covid-19 vaccines. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4675-4683, 2022.
[9] Reuven Cohen, Shlomo Havlin, and Daniel ben Avraham. Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett., 91:247901, Dec 2003.
[10] Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi. Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub M Tarnawski. Near-optimal correlation clustering with privacy. Advances in Neural Information Processing Systems, 35:33702-3333 -33115, 2022.
[11] Laxman Dhulipala and George 7 Li. Fine-grained privacy guarantees for coverage problems. arXiv preprint arXiv:2403.033337 2024.
[12] Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Diffcrential privacy from locally adjustable graph algorithms: k-core dccomposi- tion, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 765-765. IEEE, 2022.
[13) Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3 9):-4):211-44 2014.
[14] Ken T.D. Eames, Jonathan M. Read, and W. John Edmunds. Epidemic prediction and control in weighted networks. Epidemics, 1(1):70 - 76, 2009.
[15] S. Eubank, V. S. Anil Kumar, M. V. Marathe, A. Srinivasan, and N. Wang. Structure of Social Contact Networks and Their Impact Epidemics. In Discrete Methods in Epidemiology, volume 70, pages 179-200. American Math. Soc., Providence, RI, 2006.
[16] Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 18066688) 2004.

---

[17] Odile Favaron, Maryvonne Mahéo, and Jean-François Saclé. Some eigenvalue properties in graphs (conjectures of grafitii ii). Discret. Math., 111:997-220, 1993.
[18] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Adam Sealfon. Individualized privacy accounting via subsampling with applications in combinatorial optimization. arXiv preprint arXiv:2405. 18534, 2024.
[19] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. 2009.
[20] Calvin Hawkins, Bo Chen, Kasra Yazdani, and Matthew Hale. Node and edge differential privacy for graph laplacian spectra: Mechanisms and scaling laws. IEEE Transactions on Network Science and Engineering, 1 1(2):1690-170., 2023.
[21] Ara Hayrapetyan, David Kempe, Martin Pál, and Zoya Svitkina. Unbalanced graph cuts. In Proceedings of the 13th Annual European Conference on Algorithms, ESA'05, page 191-202, Berlin, Heidelberg, 2005. Peringer-Verlag.
[22] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In 30th USENIX Symposium on Security, 2021.
[23] Tianxi Ji, Changqing Luo, Yifan Guo, Jinlong Ji, Weixian Liao, and Pan Li. Differentially private community detection in attributed social networks. In Asian Conference on Machine Learning, pages 16 16-31. PMLR, 2019.
[24] M Kargar and T Sistani. New upper bounds on the spectral radius of graphs. Journal of Mathematical Extension, 14(4), 2020.
[25] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. ACM Transactions Database Systems (TODS), 39(3):1-33, 2014.
[26] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyz- ing graphs with node differential privacy. In Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC' 13, pages 457-476, Berlin, Heidelberg, 2013. Springer- Apringer-Verlag.
[27] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In Proceedings of the ninth ACM SIGKDD international conference Knowledge discovery and data mining, pages 137-146, 2003.
[28] Tamara Gibson Kolda, Ali Pinar, and Seshadhri Comandur. The bter graph model: Blocked two-level erdos-renyi. Technical report, Sandia National Lab((SN,,CA), Livermore, CA (United States), 2011.
[29] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap... wtw.aap.staffor...omooo edu/data, June 2014.
[30] George Z Li, Dung Nguyen, and Anil Vullikanti. Differentially private partial set cover with applications to facility location. In Proceedings of the Thirty-Second International Joint Conference Artificial Intelligence, pages 4811-4811, 2023.
[31] George Z Li, Dung Nguyen, and Anil Vullikanti. Computing epidemic metrics with edge differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 4303-4311. PMLR, 2024.
[32] Madhav Marathe and Anil Vullikanti. Computational cpidemiology. Communications of the ACM, 56(7):88-99))) 96, 2013.
[33] Joel C. Miller and James Mac Hyman. Effective vaccination strategies for realistic social networks. pages 780-785, 2007.
[34] Dung Nguyen and Anil Vullikanti. Differentially private densest subgraph detection. In 38th International Conference Machine Learning (ICML). PMLR, July 2021.
12

---

[35] Masaki Ogura and Victor M. Preciado. Optimal Containment of Epidemics in Temporal and Adaptive Networks, pages 241-266. Springer Singapore, Singapore, 2017.
[36] Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. Epidemic processes in complex networks. Reviews of modern physics, 87(3):925, 2015.
[37] Govind Persad, Ezekiel Emanuel, Samantha Sangenito, Aaron Glickman, Steven Phillips, and Emily A Largent. Public perspectives on covid-19 vaccine prioritization. JAMA network open, 2e22119933-2219944 2021.
[38] Aditya Prakash, Deepayan Chakrabarti, Nicholas C Valler, Michalis Faloutsos, and Christos Faloutsos. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and information systems, 33:549-575, 2012.
[39] Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, and George J. Pappas. Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks. In IEFE Conference on Decision and Control. IEEE, 2013.
[40] Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, and George J. Pappas. Optimal resouree allocation for network protection against spreading processes. In IEEE Transactions on Control of Network Systems, pages 99 108. IEEE, 2014.
[41] Victor M. Preciado, Michael Zargham, and David Sun. A convex framework to control spreading processes in directed networks. In Annual Conference on Information Sciences and Systems (CISS). IEEE, 2014.
[42] S. Rajagopalan and V.V. Vazirani. Primal-dual me approximation algorithms for (multi)-so (multi)-cover and covering integer programs. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 322-331, 1993.
[43] Daniel M Romero, Brendan Meeder, and Jon Kleinberg. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proceedings the 20th international conference on World wide web, pages 695-704, 2011.
[44] Sudip Saha, Abhijin Adiga, B Aditya Prakash, and Anil Kumar S Vullikanti. Approximation algorithms for reducing the spectral radius to control epidemic spread. In Proceedings of the 2015 SIAM International Conference on Data Mining, pages 568-576. SIAM, 2015.
[45] Zoya Svitkina and Éva Tardos. Min-max multiway cut. In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 207-218, Berlin, Heidelberg. 2004. Springer Berlin Heidelberg
[46] Piet Van Mieghem, Dragan Stevanović, Fernando Kuipers, Cong Li, Ruud Van De Bovenkamp, Daijie Liu, and Huijuan Wang. Decreasing the spectral radius of graph by link removals. Physical Review E E-Sutiistial,, Nonlinear, and Soft Matter Physics, 84(1):016101, 2011.
[47] Yue Wang, Xintao Wu, and Leting Wu. Differential privacy preserving spectral graph analysis. In Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, April 14-17, 2013, Proceedings, Part Il 17, pages 340-340. Springer, 2013.
[48] Yingrui Yang, Ashley McKhann, Sixing Chen, Guy Harling, and Jukka-Pekka Onnela, Efficient vaccination strategies for epidemic control using network information. Epidemics, 27:115- 122, 2019.
[49] Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD '15 page 731-745, New York, NY, USA, 2015. Association for Computing Machinery.
13

---

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: Our abstract claims a (e. 6) differential private algorithm for minimize maxi- mum degree and spectral radius, which is the result of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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 can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals 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 recognize that the problem of minimizing the number of infections is NP-hard and hence used the heuristic of minimizing max degree and spectral radius, which is shown to be useful in decreasing infections. In addition, we present the setups of our experiments and the limitations that they are run with.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant 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
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We have clearly stated the requirements of theorems and provided proofs for
each.
Guidelines:
The answer NA means that the paper does 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 in 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 provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The steps taken to produce the experiments are detailed in the algorithms of the paper and the datasets are clearly described with the appropriate setups.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a 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, 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 replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(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-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The instructions to reproduce the experiments are detailed in the algorithms. All datasets are publicly available with their sources cited.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/griide//ddeStttmii otr.ooodeeeamiiiiioooooooooioie. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to 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 NeurlPS code and data submission guidelines (https for more details.
//nips //ips.cc/puut cttp:/scccpbblccgguiieeeeaec guides http:///lli/ciiiiee//oeeeuuaaaaa
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. only 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) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
All the parameters to set up the experiments are listed in the respective sections.
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 is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: [Yes]
Justification:
The experimental results and analyses include the error bars of the distribution results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test 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 to a 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 The authors should preferably report a 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 out of range (e.g. negative error rates).
If error bars are 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
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: We presented the computational complexity of our algorithms, which was quite reasonable for the networks we considered in our experiments. Since the experiments can be performed by typical workstations without specialized hardware and in relatively short amount of time, we have decided not to include such information.
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 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 the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: There is no violation of the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper is aimed to increase the effectiveness of vaccination strategies under of sensitive data. There may exist other societal impacts that are out the of the scope of this work. Currently, find negative societal impacts of this work.
17

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If 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 unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
No additional data nor trained models are generated.
Guidelines:
The answer NA means that the paper poses 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or 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?
Answer: [Yes]
Justification:
All assets are properly cited.
Guidelines:
The answer NA means that the paper does not use 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 used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are 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 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:
No new assets produced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
The paper 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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 equivalent for research with human subjects
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 of your country or institution) were obtained?
Answer: [NA].
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

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
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.
Question:
Answer: [NA].
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips hett::///earrrpsscc//oooerrreeee cc////ooeeeeeecs//22/////.. for what should or should not be described.
20

---

Supplementary Material
A Related Work
We include additional discussion on related work here.
7 studied the problem of estimating the reproductive number Ro of an epidemic on its contact network in the SIS and SIR models. The reproductive number Rg closely related the spectral radius, i.e, the reproductive number Rg can be expressed function of the first eigenvalue of the adjacency matrix. Their privacy model protected the "weights" of the weighted contact network. Moreover, the work did not specify or imply any approach to modify the contact network to reduce such quantity, in order to reduce the spread of the pandemic.
There has been several work to calculate the spectral radius of an input graph-that is of independent interest from the perspective epidemic control. 47 computed the eigenvalues and cigenvectors of an input graph under the edge-differentic privacy. G also under the egde egde-differential privacy model, estimated the second smallest eigenvalues (A2), which is also commonly refered to as "algebraic connectivity".. Similarly, (20 studied the same problem, but also considered the problem under the node-differentia privacy model, in which two neighbor graphs differ by a node and adjacent edges. None of the work suggested method to reduce the spectral radius of the input network.
B Background
We briefly discuss the basic ideas of DP here; see for more details.
Definition B.1 (Exponential mechanism). Given utility function u X x R. + R, let GS maxTER max (u(xr)) - u(x', r) be the global sensitivity of u. The exponential mechanism Mar, u. R) outputs element E R. with probability x exp( 2GS.
Lemma B.2. The exponential mechanism is e-differentially private. Furthermore, for a fixed dataset x E X", let OPT = max,eR u(x, r), then the exponential mechanism satisfies
Pr[u(x, (x, u, R) S OPT 2 GGS (In [())
Definition B.3 (Laplace mechanism). Let f:: x - Rd be a function with global Ei-sensitivity A₃ maX [f(x) f(x)), The Laplace mechanism releases
M(x) = f(z) + (Z,,...,Za)
where Zi ~ Lap(A) A /)) are independent random variables drawn from the Laplace distribution with scale parameter /
Lemma B.4. The Laplace mechanism is e-differentially private. Moreover, each coordinate of the output concentrated around the true value of (xr) with noise magnitude proportional A/c.
Definition B.5 (AboveThreshold), Let f1....: x + R be sequence of queries with sensitivity 1. Given a threshold T and a privacy parameter e, the AboveThreshold mechanism adds Laplace noise Lap(2/e) and Lap(4/e) the threshold and to each query, and returns the first index i such that the noisy query exceeds the noisy threshold.
Lemma B.6. The AboveThreshold mechanism (e, ddifferrrenl private.
C PRIVATEMULSET and PRIVATEMAXDEG Problems
We start by describing and analyzing an algorithm for solving PRIVATEMULSEET problem that is later used for PRIVATEMAXDEG.
C.1 PRIVATEMULSET
C.1.1 Unweighted case.
present an algorithm the PRIVATEMUI.SS problem, building upon the framework and
analysis from [19]. First, define utility function A : S R2o. For set S, S and an element
21

---

e E U, the marginal utility is defined as A(S;, e) := em) and then the total utility of set S; is given by =(s,)= = A(S, e). The algorithm will sample sets based on these utility scores computed in each iteration.
It is important note that directly outputting explicit solution i.e., listing only the sets that form valid cover would violate differential privacy. In particular, this is because the solution the vertex cover problem, which is a special case of the set cover problem,
known retain privacy iff the output contains at least [V] - vertices [9]. Therefore, in order to preserve privacy, the algorithm must produce an implicit solution, typically in the form of permutation и E a(S) over the sets in S. Intuitively, should have the sets arranged in the order of decreasing utility. This ordering implicitly defines a cover: for each element E U, we select the first few sets that would fully cover e, Formally, let मe == (-())
S S n min (
m(Sri)), e), -
0} be the indices of sets that contribute to covering e according to Then {S ;j E Uceu ] forms a valid multi-cover of U.
re) re) min أj=1 1 m(STO): e),
Algorithm 5 Private algorithm for PRIVATEMULSET
1: Input: privacy parameters (c, 6), set system S, covering requirement R.
2: Set 2m(e/8)
3: Initialize empty permutation π f- 0
4: Initialize re f- for all e E U, U t S
5: for = to [S] do
6: Define (S) (=8)==X. ==s:==Ess>: min(m(S,e) (See),e r))
7: Sample Sj E S()) with probability x (S)))
8: Append j to т: tii) jj
9:
Update available set system: s(++) - s(i) \ {
for e S, do
11: Update covering requirement: r0 max(0, re (6-1) m))
12: end for
13:
end for
14:
Output permutation π
Lemma C.I. The output of the Algorithmm5 is at most O(I fln with probubility least
1 1- 1/m, where OPT denotes the cost of an optimal nor-private solution, and y = max E. A(S,e) the size of the largest set.
Proof. Without loss of generality, we may assume that the permutation output by the Algorithm is ग = (1,2....,m)) m).. In other words, the sets S1, S2,..., are sequentially added to the cover in this exact order.
Let [(0 max (S) max (S,) be the maximum utility possible at step i; this also implies that there is a multi-set of that utility. Then the probability of selecting set of small utility < (6) 3 In given that we have at most m sets to select from, is less than
m. e - 3mm)
1/m²
I 1/m² S 1/m²²
erp(e'Lo) + m wee.eeppeeLo 3 31mm
Next, consider two cases:
6 mlmm The probability that every multi-set selected has utility at least ( - 3 3
i2 (1-1/m²)m (1-14 1/m). Because the greedy approximation O(In q)
approximation, Algorithm can cover this region in at most O(OPT In multi-sets with high probability.
L < 6 In At this point there are at most OPT ( elements that require covering, and OPT. I < OPT. O (())). Since the post-processing of the implicit solution selects only sets that cover least one element, covering the remaining OO elements takes an additional O(OPT In m/ee) sets.
22

---

Therefore, the algorithm uses at most O( + lnq) sets.
Lemma C.2. Algorithm is (c,8)-DP.
Proof. Similar to Lemma
C.1 we assume that π = (1.2....,m)) so that S(0 = [S}
First, we consider neighboring problems A = (U, R). A'' (U,S', , R) that share the same coverage requirements R = R' fre : e E U} but differ the multiplicity of a particular element eo in one set, such that (m, eo) m eo) 1 for some & E [mm] Define as the epoch when element Eg is fully covered in both instances A, A'. We wish to establish a bound for (A)= Pr (
(A(M x|
(S))
e (8)))
PA) =
n et (S,))
Pj= c (AA()
EE 1 (S.))
(5))))))
Di (511
12 ec ((A))))))
(S)
e (8,))
where the last equality holds because if > I, then the element ep was fully covered by iteration i, implying that (S,) (5)) for all j 2 i. Also, given that all elements are eventually covered, we have Ei= (S.) = A (S))
Σner (8)
Assuming &s S t, we break up the product IT
into three terms 11, 12, I3 follows:
Eszr of (8)
(5))
Σjzn (A(()))
I2 I3
es (013))))))
Σj (r(11(8))
Σ E/yy e A (10))))) (8))
II iik+1
In the case when < l (or 1 S k)) the terms 12 and I3 (or just Ia) vanish, and k is replaced by t. However, the argument by enlarge would remain unaffected by this adjustment.
We proceed by considering two possible cases: m(Sk. e0) > m(S eo) and m(S,, eo) < m(S eo).
m(Sk, eo) > m(S ep) In this scenario, both J, and Tz are less than or equal to 1. Therefore, it is sufficient to focus upper bounding T3. Define index-set
S := {j A (S,) + (S)).
Note that (eo) < (()))(()) when A < < t, and thus, ( < (S') for k < i S t. Specifically, we have that ( = (5, + for any j E S1. Therefore, we can write I3 as
Σ EESE (S))
11) Ejss jESt e (8,) (8,) + EZiz (S,)
13
II i=++1
II
Σn ef (S))
Σ Enstet (CAA)))))
1=++1
Ejegr. e e1( (00
1+ [ -1) E5 ((AAW113))
#=+1
23

---

((al)1))))
Recall that Pr(a(() = -
is probability of sampling set Sj at epoch i.
Ee et ('
Therefore, we can write the above expression simply as
f II (1+ 2=++1
Pr(T(() E 5t P))-((((
II 1=
Pr(s".").
Additionally, observe that to sample set from S means to fully cover eu. which can only occur at step t. Next, we will need the following lemma from 19:
Lemma C.3. The probabilistic process is modeled by flipping coin over rounds. pi is the probability that would come up heads in round i, and p; can be chosen adversarially based on the previous i 1 rounds. Let Zi be the indicator for the event that no coin comes up heads in the first i steps. Let Y = Ei= PiZz. Then for any Pr(Y q] S exp(-q).
In setup, Z4 corresponds the indicator of the event "en is fully covered at round i". If
R Pr[St In o then we obtain
(A) ল| (A' = π.
- la
II expl(e" PI(
since + S E
kmb+1
eexp(2e' Σ PI(
S + 2x for small x 2
i=k+1
ccxp(2c(In11/0)) + Pr(s4.1))
(cxp(2((Im(18)) + 1)) cxp(c).
Finally, by Lemma C.3
the probability of the event Ei=k+1 Pr[Sr']Z, > 1n is upper bounded by 8. Consequently, P denotes the set of outcomes, we conclude that
(A) E PI S exp(e) E
For a more detailed proof, see 19]
m(Sk, eo) < mS en). In this scenario. I3 < 1. Our focus then shifts to / 12, following an analogous argument to the one discussed above, we obtain
(S)
1
et (S,)
I[ (1 + (e 1) Pr(m(i) E st:t))
i=1
-II (e 1) Pr(a(i) Sx))
since 8 =
-1.== (k: for i S
expp(ee - 1) Pr( = Sa))
since + S e
1=1
5 (2e
Pr(m(1) = Sv,)
ex < + 2x for small 2 0
We then apply Lemma C.3 analogous to the above discussion, which completes the proof.
24

---

Next, we turn to the instance where the neighboring problems have different covering constraints R. # R'. As before, let t denote the epoch at which the covering constraint for ep satisfied by both (( and M(A). Although S = S', we refer to the sets in S' as S' for for clarity.
This case is straightforward, since Ei= (S.)
E.= (S) = Teo - Po = 1.
Tep >
6g
We obtain
(A) || Pr Mr[M(A' = π
Σ
A(S))
el A(S,) S exp(c').
Teo < reo In this case we have
(A)M(A) = π. Pr[M((A') = π
121 et A(S))
i=1 123 e A(S;]
Se II
1 + (e" -1)-Pr(T() E s1
1=1
II (1+ (e" -1) -1)-Pr(S"..) ==k+1
The remainder of the proof utilizes the same arguments as previously discussed.
Lemma C.4. Algorithm 5 runs in Ö(as(S)) where y is the maximum set size and f is the muximum frequency of any element (ignoring multiplicity).
Proof. Initially, the algorithm computes (.) for all sets in S, which can be done in O([S]g) Then the algorithm runs for [S] iterations, once per set, contributing the |S] factor. In each iteration, set is sampled according to the exponential mechanism, where probabilities are proportional to exp(e' A(S)). Sampling can be done in Ô(1).
After a set S, is selected, the algorithm updates the covering requirements for each element e Sy. which affects the utilities A(S") for all other sets S' containing e. Since each element appears in at most sets, and each set contains most q elements, the number of affected utilities per iteration is at most qf-
C.1.2 Weighted case.
Here we briefly discuss the weighted version of PRIVATEMULSET, and adapt the methodology of [19] with some minor modifications. First, we may assume without loss of generality that minses C(S) 1, and W maxses C(S) with = S). Let M E.gyre Te. Similar to the unweighted version, we define A(S) = E min(re, m(S, e)) for set S S S. and we say that the utility u(S) is defined to be equal to A(S) C(S). Additionally, we add dummy set halve to S
with utility u(halve) = -7 for T O + log( MWW).. When halve is selected by Algorithm 6 it indicates that set was actually chosen. Additionally, unlike other selections, halve is never removed from S.
Lemma C.S. The cost of the output of is at most O(Tlog n OPT) with probubility at least 1 - 1/poly(n).
Proof. This follows from a verbatim argument in 19 with n replaced by M and m replaced by n in our notation.
Lemma C.6. 6 is (e, private.
Proof. The proof is identical to the privacy proof of the algorithm in the unweighted case, with A(S) replaced by u(S).
Identically to 199, we can remove the dependency on W to obtain an O(log M M(logn++oo log M/e))-
approximation.
25

---

Algorithm 6 Private algorithm for WEIGHTEEDRRVATEMULSET
1: Input: (e, (), set system S, covering requirement R (re)aeu
2: e' 2ln(e/ō)' initialize permutation +
3: 8 <- M,T
log b
4: f 1e < for all eEU, S
5: while 0 2 1/W do
6:
Define (=)
min(m((,ee e), re - C(S)/0
-
7: Sample S ( with probability exp(e'u (
8:
i = hal then
9:
0- 0/2
1(++) S()
11:
Te - fe
for all e U
else
13:
Append S to
14:
((++) + 86) \ {S}
for e do
Te + max re (i-1) m(),e)) end for end if
16:
18:
end while
20:
Output concatenated with random permutation of ((() \ [hal]
C.2 MAXDEGREE
Algorithm (restated). Private algorithm for PRIVATEMAXDEGG
1: Input: (), graph G, target degree T)
2: Initialize set system <- W. requirements R <
3: for each E V do
4: Define multiset S, with m(S,, oo and m(S,, u) = for all a R RU (r. max(deg(v) D,0)
5: S S
6: end for
7: Set + c/4, 8' 3/
8: Return: Algorithm 5ke',8' (,,SS,)) 1 AApplying the private multi-set algorithm*/
Theorem 4.2. Algorithm / is (c. (c.ffdiifrreentialll private, and the cost of its output is < MOPTTa O((1 + 1/c / In [Vi) with high probability.
Proof. Since PRIVATEMAXDES reduces to PRIVATEMULSET. the optimal solutions for both prob- lems are equivalent. In addition, since Algorithm outputs a Olmm/é é + In l))))opprximmaatonn and [V g GS(G) < V), have (In m/ é' + In q) I 0((1 1/e") In [V).
C.2.1 Explicit solution for MAXDEGREE
Algorithm (restated). Explicit solution algorithm for PRIVATEMAXDEG
1: Input: Instance of PRIVATEMAXDEG and a permutation obtained from the exponential
mechanism
2: T" +- 6 mnnee Lap(2/e1)
3: for = 1 to n do
4: 7/s f- (t) Lap(4/er)
5: end for
6: Let & be the first index such that n T
7: Output: (()).....,x())))
26

---

Theorem 4.3. The output k of Algorithm 2 satisfies A(G - - - D O(logn/e) with high probability. In addition, O(OPT log n/e') with high probability.
Proof. It well established that the 6lnn/cl > a] I B, with
algorithm is (a, accurate, i.e., Pr(
8(1og log(2/3))
a
61
Then, for 3 = 1/n, we obtain a = 16 1 = O(logn/c) Thus, L(0 < Ollogn/c) with high probability.
the other hand, observe that AG - ( > D + x, then there is a node j that has degree at least D + x. The multi-set corresponding to this node would have size at least since removing this node would satisfy its covering requirement completely. Therefore, S T,(k), and hence, A - (x(1) S S k)) I + x with probability at least 1/n.
Let be the "true" stopping point (,)k) < 6 6lnn/e. Using the proof for Lemma C.I the exponential mechanism satisfies h < O(OPT log n//')) when ( 2 6log n/c'. - It is sufficient to show that k h < O(logn/e) Observe that for i 2 k, ( < 6mmn/e but Y 2 T', the Laplace noise added to (( is greater than that added to T, this occurs with probability at most 1/2 (since the Laplace distribution is symmetric about 0). Then the probability Pr(k k 2 log2 n) S 1/n, so k S OOPP logn//// n/e') with high probability.
C.3 Lower Bounds
In this section, we state the lower bounds of even outputting an explicit partial coverage requirements, that (1) any (c, -)dddfffrrentillly private algorithm outputting (explicitly) a multiplicative coverage requirements (covers at least are for all e, a < must output least m sets, and (2) any (c, 6)- differentially private algorithm outputting (explicitly) an additive coverage requirements (covers more than re - 3 for all e) using no more than Ollog n) + [OPT], where OPT indicates the optimal solution without privacy, must do so with 3 = (loog ni). The multiplicative case straightforward to verify, as setting r. 1 for some element Any multiplicative partial cover must cover least a total copy of e. This impossibility of this instance reduced to the impossibility of the set cover problem stated by [19].
Theorem C.7. Any (c, differrrentl private algorithm outputting an additive coverage require- ments explicitly (covers at least - for all e) using less than O(log n) + |OPT] with probability at least C, C = n -0(1) must do so with B = 22(oog n.)
Proof. Assume an algorithm M that is 0) with d ((1/poly(n) that outputs explicit cover that can partially cover at least re - B, using less than O n) + OPT sets for all e with probability (1))
Let = {e).
Let a be a positive constant, such that the number of sets that M outputs no more |OPT] + a log with probability at least C. Let r > 8 + 3a log n)).
Let S₁ = (e x (r - B - log n)). i.e., set with (r- - 3 - a log n) copies Let the set system be S = (S,, {e) x (8 + a l)].
Consider four instances of the the input with coverage requirements 11 = (re r2. r), (r+ (re - - 1, 1) respectively, with the set system S. It
r2 3,S), I3 (r. = - 1---1116 -,,1, clear that S is enough fully cover all the instances.
Let S" = {S C S: : S, E S. S < a n). In other words, each contains S, and up to a copies ofe.
copies of (e). Then every S E S* covers most 7
Consider instance J,. M guarantees to cover at least r copies of with probability at least 1-C. Therefore, (1)) S*] C.
27

---

Consider instance 1z. Without privacy, S1 is the optimal solution, hence OPP = 1| for 12. If Si & (I2). M (12) must use least rf 3 a logn a a log n sets. With probability at least 1 C- the output contains Sj and using no more than log n sets, hence Pr(M((2) E E C.
C,
Because /, 12 are B-step neighbors, using group privacy have:
C-C Pr((() E*)
S Hh PH(((I) E S*) + 86
S c 36
Therefore
1-c Bes.
< 1/poly(n). It clear that 3 = ([(log n).
Lemma 4.4. Lower bound of PRIVATEMAXDEG, Any explicit (c.8)- differrentill private algorithm for the PRIVATEMAXDEGRER removing at most + -OPT nodes with probability at least 1 - C, C = n -I(), must incur an additive error A(G U {m.) = D + 22(log n), where (1),,..., (k) are the removed nodes.
Using the same setup as in Theorem C.7 setting r. = max(d(v, G) - D,0) for all nodes v. Similar Theorem C.7, any explicit (c, 5)-DDPP algorithm removing fewer than Ollog n) [OPT] nodes will guarantee cover each node v no more than d(v: G) - 22(log n) times, i.e., the maximum degree of the remaining graph is A (A D -2(lg n)) = + 22log n))
D SPECTRAI.RADUU
D.1 Bound via PARTIALSETCOVER
Algorithm (restated), Private Hitting Walks Algorithm for PRIVMINSR
1: Input: Graph G (V, E), privacy parameters (c,
2: Set e' < e/(2 (2ln(e/))), initialize permutation ग +
3: for i = 1 to do
4: Sample E with prob. & exp(c' A(v)), append to æ and remove v from V
5: end for
6: Set T + 1/22 0 +- 4n7 0 + Lap(2/e1)
7: for to do
8:
+ WG[G[V -
9: end for
10: Let & be the first iteration such that 5 θ
Output: (I())...., (k))
Lemma D.1. 1 > 6lnn/é', the output V = (....... R of Algorithm satisfies (a VT)) S n Olognnje and gives (log approximation with high probability; the algorithm (e+(e)))), 24 differrntttl private and runs in time Ó( A where w is the matrix multiplication exponent for X n matrices.
Proof. Since AboveTThrehhen is (a, -ccaurae,, for 3 1/n, obtain Wi(V \ V nT Ollo n/e') whp, similar to the proof for Theorem
Let L; denote the utility of the largest set after the V; { ........ ..... } have been removed (i.c. L, max, A(v)). For < k. (V(V) V.) Z ndd > n- 6 n / and (VVV) V4) < Evev A(v) I nLi Hence, L 2 6l nu/e'. By the same argument as in Proof 4.3 A(T)) 2 L./2 whp. In other words, the utility of the chosen set is at least half of that chosen by non-private greedy algorithm. Since the greedy algorithm a O n) approximation, Algorithm would be 0(2 n) = 0(n approximation.
28

---

Lemma D.2. Algorithm is (A)( -1 -private.
Proof. Since A(u) has sensitivity of A?, neighboring datasets in Private Hitting Walks would be step neighbors in Partial Set Cover and Above Threshold instead.
Algorithm 3 is the composition of a (A²c, A 2 ) )-private set cover algorithm and 1 -1-pvivtte AboveTThreshood process, hence the overall privacy budget would be (A² (e) A (1(4)-1))) D
D.2 PRINATESPPECRRA via PRIVATEMULSET
Algorithm 4 (restated), Private algorithm for PRIVATEMAXDEG
1: Input: (). input graph G, target max degree D
2: S = {S, v }.. such that S, contains do copies of and d(u, G) copies of each that is adjacent to
3: (rv : V V).
max d(u, G) D,0)
4: é + c/4A
5: 8' + 8/4AA(44-1Id
6: Return Algorithm 8',,8',
We approach the problem of reducing (VX v E the PRIVATEMAXDEG case by reformulating it as an instance of PRIVATEMUT.SET. First, we define sets (Sa) uEV, so that m(S.. u) = co and m(,,, Additionally, for each vertex u E V, set r. = max(0, Euno, d(v, G) - D), where vD a target upper bound. We can then apply the same analysis used in the PRIVATEMAXDEG case. However, we must adjust our edge-privare could cause neighboring graphs in the PRIVATEMULSET formulation become 4 4A-ncighbors. This happens because such an edge addition can increase both the covering requirements ra and r, as well as the multiplicities m(S., 7) and m(S., u) by up to A. Thus, the algorithmic approach and results from PRIVATEMAX AXDEG largely carry over, but the sensitivity needs to be adjusted from to 4A. All combined we obtain the following result:
yow d(u, G) using a similar strategy as in
d(u, G) for all vertices v adjacent to u.
model for this scenario. In the worst case, adding an edge (u, v)
Theorem 5.2. Algorithm 4 is (c. diffferrrettilllyy private, and the cost of its output is B < [OPT
O(11 + 1/e') [VI) with high probability.
E
Additional Experiments
Effect of the on the spectral radius. F the p(G[V S]) for the explicit solutions S computed using Algorithm for BTER networks, for the same parameters and privacy budgets mentioned earlier. The results here show that the resulting spectral radius is quite bit smaller than the maximum degree. As expected, the resulting spectral radius of the residual graphs follow a similar trend as the max degree, with higher c budgets obtaining better metrics due to less privacy constraints.
Cost of achieving different epidemic metrics. Figures and the violation in the target degree (for D 20) and the spectral radius the explicit solution cost (computed using Algorithm (2). for different in the BTER networks. As noted earlier, the violation and spectral radius decrease significantly the solution cost increases, which is achieved for higher
Privacy vs Vaccination Cost in BTER. We also investigated the tradcoff of privacy and vaccination 0.05) for implicit PRIVATEMAXDEG, with
cost in the 3 BTER graphs (Y 0.5, 0.95, target degree D = 20, as shown in Figure The non-private greedy algorithm used as a baseline comparison. Due to the relaxed privacy budget of 8 0.01, the variation of has much more pronounced effect on vaccination budget, and the algorithm's 's performance is much closer to that of the non-private greedy as compared to Figure and are within the bounds expected from Lemma 4.2
Effect on Infection Simulation. Finally, we computed the 300 explicit solutions using various privacy budgets (and 8 = 0.01) and target max degree 10 for 3 "social circles" in the SNAP Facebook datasets (29]. we then performed 200 simulations of SIR with transmission probability 0.2 and 20 initial infections to determine the average vaccination budget and infection size and
29

---

Network
Network
Network
85
Spectral Radius
55
4.0
5.0
Epsilon
Epsilon
Epsilon
Target Degree
20
Figure 4: Effect of Privacy Spectral Radius on BTER Graphs
Network
Network
Network 3
60
Degree
50-
100
150
200
100
150
200
100
150
200
Budget Used
Budget Used
Budget Used
Epsiion
4.0
5.0
6.0
6.5
7.5
Figure 5; Tradeoff of Degree Violation vs Budget on BTER Graphs
Network
Network
Network 3
ediiew adoie edit wiiaeeaaaaa
Spectral Rodius
70
60
50
150
200
100
150
200
100
200
Budge: Used
Budget Used
Budget Used
Epsiion
5.0
6.0
7.5
Figure 6: Tradeoff of Spectral Radius Budget on BTER Graphs
30

---

Network
Network
Network
640
035
410
6.0 Epsilon
7.0
6.0
4.0
5.0
6.0 Epsitoo
7.0
8.0
4.0
6.0
7.0
5.0
Epsilon
Figure 7: Tradeoff Spectral Radius vs Budget on BTER Graphs for Implicit Solution (D 20)
Table 3: Infection Spread on Facebook Social Circles
4
c
c
Network
Budget
Spread
Budget
Spread
Budget
Spread
Circle
14.52
205.18
30.48
171.55
42.28
138.02
Circle
311.70
586.99
411.53
413.50
546.56
251.49
Circle 2
45.52
138.29
73.45
90.07
94.57
60.38
demonstrate the effectiveness of the solutions to minimize infection spread. Note that we used the more relaxed mutltiset multicover version differential privacy for these experiments.
31


Reviews:
[{"review_id": "xp9Ctn6QGH", "reviewer": "Reviewer_7rGB", "summary": "The paper studies the problem of designing interventions (vaccination or isolation strategies) to control the spread of epidemics through a network. The main challenge arises from having to do the interventions in a privacy-preserving way in order to protect sensitive information like which users share contact (edges of the network). The paper considers interventions that can influence network properties like Max Degree or Spectral Radius. Their main contribution is three-fold: i) developing a private algorithm for the general Multi-Set Multi-cover problem, ii) showing that the problems of minimizing max degree or spectral radius can be reduced to instances of the multi-set multi-cover problem which they already know how to solve privately, and iii) finally, demonstrating effectiveness of their algorithm on real-world and synthetic networks.", "questions": "Detailed Comments & Questions: \n\nSection 4:\n\n1. At the start of section 4.1, the authors say that they are discussing the Unweighted case, which according to their Defn 3.4 should try to minimize the number of sets to be chosen from S to achieve the desired coverage for all elements. However, their main result Lemma 4.1 mentions an approximation ratio on the worst case cost which leads the reviewer to think that this is the weighted case ? Can the authors clarify ? \n\n2. What does f mean ? The statement says \"maximum frequency of an element (ignoring multiplicity)\" -- this is not clear. Are the authors talking about the maximum number of sets S_i any element can occur in ? \n\n3. The authors should provide a description of their main algorithm, specifically including where the modifications are due to privacy. The entire description before Lemma 4.1 has no mention of privacy at all. They should at least mention that the sampling is done using the exponential algorithm on the total utility of set S_i.  This is especially important for readability because their other algorithms build on this.\n\n4. The reviewer is not familiar with previous literature on the best achieved approximation ratio for the multi-set problem in the non-private case. Can the authors provide that and discuss how their ratio compares with it. It is expected to be worse due to differential privacy, but by how much? \n\n5. I do not understand the distinction between implicit and explicit solutions in this case. In the normal setting, given a permutation \\pi, we can map it back to a collection of sets {S_u} which can be mapped back to a set of nodes {u} to be treated/removed. Is the mapping hindered by privacy ? This should not be the case because the central planner (who is deciding where to intervene) knows the contact graph fully ? The impression I got from reading the introduction is that the goal is to design the intervention in a privacy-preserving way, but the designer knows the contact graph. Can the authors clarify the privacy model ? \n\n6. I do not understand Lemma 4.5. Why does the privMaxDeg algorithm only achieve partial coverage ? My intuition from the privMultiSet algorithm is that privacy causes us to remove more sets than we actually need to, incurring a larger cost than OPT, but always achieving full coverage. If MaxDeg exactly reduces to MultiSet, why does full coverage break ? \n\n7. Minor typo (Lemma 4.1): The authors probably mean O((ln m)/ϵ + ln q) · |OP T|, not ϵ'.\n\nSection 5:\n1. What is T in Sec 5.1 ? \n\n2. Can the authors comment on the relationship between spectral radius and max degree of a graph? How should we interpret the results in Table 2 ? I ask this because Max Degree of a graph seems to be a much poorer indicator of how connected a graph is/how easily infection spreads over the network. Spectral Radius seems to be a more holistic metric to try and minimize. Can the authors provide examples of graph classes where Max Degree reduction is the better way to go ?  \n\n\nI will be willing to reconsider my score if my questions are answered meaningfully.", "limitations": "Overall, the reviewer feels that the paper would benefit greatly from a more streamlined way of presenting results. The paper in its current form is overloaded with technical results without (in many cases) clear explanation of why those results are important to the context. For example, why would a reader care about graph-theoretic connections between the spectral radius and walks of length 4. A lot of these unnecessary technicalities can be removed from the main body.  Lots of notation are introduced on the fly without formal definitions. Several results like runtime complexity can be omitted entirely from the main body or just mentioned in passing.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 4, "originality": 3, "strengths_and_weaknesses": "*Quality*: Although the reviewer has not checked the mathematical details/proofs, the paper appears to be technically thorough. Technical questions below. \n\n*Significance and originality*: The paper studies a very important problem. Differential privacy has enormous scope in the public health domain. As the paper rightly points out, people are in general concerned about privacy which degrades the efficacy of interventions (for, example, reluctance to provide information to help with contact-tracing during Covid-19). From that point of view, the paper tries to make a meaningful contribution which is both significant and original. \n\n*Clarity*: The paper has serious deficiencies when it comes to clarity. Please find detailed comments and questions below.", "was_revised": true, "final_justification": "The authors engaged with the questions asked during review. Most of my technical concerns were addressed (including clarification on the privacy model, difference between the implicit and explicit solutions, other questions about notation). I have also read through other reviews to calibrate my judgement. I feel positively about the paper in general and am willing to look past some of the presentation issues highlighted during review. My final score is adjusted accordingly.", "rebuttal": "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:\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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).\n\n- 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.\n\nWe appreciate the reviewer’s comments and believe that addressing these would help improve the clarity and accessibility of the paper."}, {"review_id": "mYp5neRCMr", "reviewer": "Reviewer_MnSu", "summary": "This paper studies vaccination strategies for epidemic control on contact networks under differential privacy constraints. The authors focus on two key network properties known to influence epidemic spread: maximum degree and spectral radius. Their key technical approach reduces both problems to instances of a \"multi-set multi-cover\" problem, for which they design private algorithms using the exponential mechanism. They provide both implicit solutions (outputting a permutation from which nodes can determine inclusion) and explicit solutions (directly outputting the vaccination set).", "questions": "Mostly around significance and how applicable it is.", "limitations": "More discussion on actual applicability. Their evaluation was on a small network, way smaller than a typical city where such a thing would be used.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 1, "originality": 3, "strengths_and_weaknesses": "Strength -\n1. The lower bound results are impressive and establish the limitations in private cover problems.\n2. The multi-set multi-cover reduction is clever and the approach to providing both implicit and explicit solutions addresses a known challenge in private covering problems.\n3. Contact tracing privacy concerns were a major barrier during COVID-19, making this a practically motivated research direction even if the current results have limitations.\n\nWeaknesses -\n1. The edge-DP model assumes node identities are public while only edge relationships are private. Knowing who exists but not who they contact severely limits the model's applicability.\n2. In covering problems, even the optimal non-private solution often requires vaccinating a significant fraction of nodes (hundreds to thousands). Multiplying this by large approximation factors makes the solution require vaccinating most of the network.\n3. I think generally, the issue is that while logarithmic factors are asymptotically good, the hidden constants and practical parameter values make these bounds. Therefore, I recommend this paper to focus on the theory instead of tying the problem to actual application. If application is still their focus, then they have to first start with answering what is a practically acceptable privacy-utility trade-off and then make a convincing case whether their solution satisfies that.", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "RhGW0TNvCB", "reviewer": "Reviewer_MSr6", "summary": "This paper studies the problem of epidemic control on networks under edge-differential privacy. It focuses on designing vaccination strategies by minimizing network properties such as the maximum degree (PRIVATEMAXDEG) and the spectral radius (PRIVMINSR). The authors reduce these problems to a differentially private version of the multi-set multi-cover problem (PRIVATEMULSET), and develop both implicit and explicit algorithms using techniques like the exponential mechanism and AboveThreshold. Experimental results are provided on real and synthetic networks to evaluate the trade-off between privacy and utility under different privacy budgets.", "questions": "- Figure 2 shows an unexpected trend where stronger privacy (lower epsilon) leads to lower vaccination cost. The explanation is brief and needs more justification. The paper does not discuss how to choose an optimal epsilon, nor what happens when epsilon is very small (e.g., < 4) in Figure 2.", "limitations": "YES", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper addresses an important and timely problem of epidemic control under differential privacy.\n- It introduces a novel reduction of PRIVATEMAXDEG and PRIVMINSR to a private multi-set multi-cover problem (PRIVATEMULSET), enabling algorithmic design using known private mechanisms.\n\nWeaknesses:\n- The connection between PRIVMINSR and PRIVATEMULSET is not clearly demonstrated. A concrete example would help clarify the transformation.\n- The use of different privacy parameters (epsilon, epsilon', epsilon_1, delta') across lemmas and algorithms is confusing and lacks clear explanation.\n- In the Montgomery County subnet, the private algorithm requires a vaccination budget nearly 10 times higher than the non-private baseline, which raises practical concerns.", "was_revised": true, "final_justification": "After considering the rebuttal, other reviews, and the AC’s comment, I am raising my score by 1. The authors clarified the scope of their theoretical guarantees and addressed applicability concerns. While some scalability and utility–privacy trade-off issues remain, these are reasonable for future work. Given the novelty, relevance, and positive consensus, I find acceptance reasonable.", "rebuttal": "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."}, {"review_id": "gpFAI9i3ib", "reviewer": "Reviewer_Aeve", "summary": "This paper gives a differentially private algorithm for two important problems.\n\n(1) PrivateMaxDeg: Remove the minimum number of nodes such that the remaining graph has maximum degree no larger than a given value $D$.\n\n(2) PrivMinSR: Remove the minimum number of nodes such that the remaining graph has largest eigenvalue no larger than a given value $\\Delta$.\n\nThe authors give algorithms with theoretical guarantees, give lower bounds to demonstrate that the algorithms are tight, and also give experimental results for the proposed algorithms.", "questions": "I am willing to raise my score if the authors can clarify the derivation at Line 754 and confirm that it is not a typographical error or an omission in explanation.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I think that this paper has a very high potential. Unfortunately, I think that it may need some improvements on the following matters.\n\n(1) The problems addressed in this paper are quite similar to graph coloring problems, and the techniques that the authors introduced are quite similar to theirs. I believe that the authors should have cited the following works and explain the differences between their techniques and the techniques introduced in those papers:\n\n> Private graph colouring with limited defectiveness\n\n> Aleksander B. G. Christiansen, Eva Rotenberg, Teresa Anna Steiner, Juliette Vlieghe\n\n(2) I think the paper misses an explanation at the most important part of the proof that hinders me from understand the proof.\nAt line 754 of the full paper, I wonder why we can move from the second to the third, and also from the third to the fourth of the equation chain.", "was_revised": true, "final_justification": "I have confirmed that all the proofs are sound, and the paper has a clear contribution.", "rebuttal": "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:\n\n1. 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.\nTherefore, 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.\n\n2. 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$.\n\n3. 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}]$."}]

Author rebuttal:

Meta-review: After the author response and discussion, the paper received unanimously positive scores. The review team is unanimous that the studied problem of deciding which nodes to protect under differential privacy constraints is interesting, novel, and timely, and the review team is generally happy with the state of the results. I will point out that there were concerns about the writing and clarity of the paper in places, that I would encourage the author team to address for the camera-ready.
Decision: Accept (poster)