Epidemic models, especially network based, are commonly used in public health analyses, e.g., (Marathe and Vullikanti, 2013;Adiga et al., 2020). Such a model is defined on a contact network G = (V, E), where V denotes the population, and E denotes the set of edges, on which infections could spread. In the Susceptible-Infected-Recovered (SIR) model of disease spread, an infected node v ∈ V spreads the infection to each susceptible neighbor, independently, with some probability. The simplest metrics of interest in epidemic analyses are expected number of infections, peak size (which are at a population level), and individual risk of infection (which is at an individual level). There has been a lot of previous work on forecasting such metrics, e.g., (Mamidi et al., 2021;Adiga et al., 2022). One limitation of previous approaches is the lack of data privacy guarantees. These methods use diverse kinds of datasets as inputs, including mobility traces, contacts, and infection status. Some individual risk prediction models were based on electronic medical record data, e.g., (Mamidi et al., 2021), and contact tracing apps relied on contacts inferred through phones, e.g., (Akinbi et al., 2021). Many of these are very sensitive datasets. For instance, many individuals might prefer to keep their contacts and disease states private; indeed, privacy is considered to be one of the reasons the deployment of contact tracing apps were not adopted by a large fraction of the population (Akinbi et al., 2021). Our work attempts to address this limitation via the framework of differential privacy (Dwork et al., 2006).
We initiate the study of differentially private estimation of the expected number of infections in a graph G resulting from s source infections, denoted by f (G). If the initial infections set is given, we show that any differentially private algorithm must incur an additive Θ(n) factor in general (see Section 6). Therefore, we focus on the setting where the s source infections are selected randomly. For this setting, we show that we can beat the Ω(n) lower bound, in contrast to hardness results in the fixed-source setting. We show that the global sensitivity of f (G) in the random initial infection setting is Θ(n/s) (see Section 3). Combined with the Laplace mechanism (Dwork et al., 2014), this implies an differentially private algorithm with Θ(n/s) expected additive error. While this is significantly better than a naive bound of Ω(n), it can lead to poor utility in general.
This motivates alternative approaches to global sensitivity such as various local sensitivity based methods. We first show that the smooth sensitivity technique (Nissim et al., 2007) can be applied to our problem, and can greatly improve utility over global sensitivity-based methods. Since the smooth sensitivity is difficult to compute, we show computing a multiplicative approximation for smooth sensitivity suffices for privacy. We then give a quasi-polynomial time algorithm for computing approximate smooth sensitivity for our problem.
To address the slow running time, we give a generalization of the classical propose-test-release approach, and use it to give a polynomial-time algorithm with strong utility guarantees for a class of sparse but wellconnected graphs called expanders. Since many social networks are believed to satisfy approximate expansion properties, this gives the first positive result for estimating infection size with differential privacy for social network graphs. Additionally, we believe that our generalized propose-test-release framework will be of independent interest, since it was the only approach which improved over the quasi-polynomial runtime.
There is no prior work on the problem we study here, and there has been little work on private computation of epidemic metrics. The most closely related work is the work on the Individual Risk Prediction problem (Harrison et al., 2023), which involves privately predicting the probability of infection for a node in the next ∆ time steps. Recent work by Liu and Smith (2023) develops a federated learning method for this problem, while guaranteeing node differential privacy. While this method could be used to determine the expected outbreak size by summing the probabilities, the accuracy would be much worse than directly estimating the size. Specifically, the performance of their algorithm degrades very rapidly for large ∆, which would be needed for estimating the full outbreak size. This work is orthogonal to ours. More generally, there has been a lot of work on private algorithms for computing a variety of graph statistics (e.g., degree distribution and counts of subgraphs) in node, edge and attribute privacy models (Kasiviswanathan et al., 2013;Mülle et al., 2015;Imola et al., 2021;Blocki et al., 2013;Ji et al., 2019;Hay et al., 2009;Zhang et al., 2015;Dhulipala et al., 2022Dhulipala et al., , 2023)). Since graph statistics generally have high global sensitivity (e.g., the number of triangles in a graph has a sensitivity of n -2 under edge privacy), using the Laplace mechanism can be very inaccurate. Consequently, more advanced techniques based such as smooth sensitivity (Nissim et al., 2007;Karwa et al., 2014), ladder functions (Zhang et al., 2015), proposetest-release (Dwork et al., 2014), and inverse sensitivity (Asi and Duchi, 2020) have been developed to provide much more accurate counts for some problems, but are computationally expensive (see (Li et al., 2023) for a recent survey on private graph algorithms). Our work contributes to and generalizes some approaches in this line of work.
We consider the Independent Cascades (IC) model, which is the simplest instance of the more general Susceptible-Infected-Recovered (SIR), on a contact graph G = (V, E) (Marathe and Vullikanti, 2013). In this model, each node v is in one of Susceptible (S), Infectious (I) or Recovered (R) state. In the beginning (t = 0), we have a subset I 0 ⊆ V of source nodes in the infected state, with s := |I 0 |, and all remaining nodes are in the Susceptible state. Let I t denote the set of nodes which are infected at time t. At each time-step t, an infected node u can infect each susceptible neighbor v with probability p, independent of other neighbors of v. An infected node v is assumed to recover after one time step, so all nodes in I t are Recovered in the next timestep. The expected total number of infections f (G) = E[| t I t |] is one of the most basic metrics in epidemic analyses, which we will try to estimate given an input graph and transmission probability p.
We use the notion of differential privacy (Dwork et al., 2014), which is one of the most widely used standards of privacy, and has been extended to graph data (Blocki et al., 2013;Kasiviswanathan et al., 2013). We focus on the edge privacy model (Blocki et al., 2013), which guarantees differential privacy for the contact data between two individuals. Formally, edge-privacy is defined as follows.
Definition 2.1. We say that two graphs G, G ′ are edge-neighbors, i.e., G ∼ G ′ , if they differ in exactly one edge, i.e., |E(G)∆E(G ′ )| = 1, where E(G) denotes the set of edges of graph G.
Definition 2.2. Let G denote the set of all undirected graphs. A (randomized) algorithm M : G → R is (ϵ, δ)edge differentially private if for all subsets S ⊂ R of its output space, and for all
One of the most common mechanisms for guaranteeing differential privacy is the Laplace mechanism (Dwork et al., 2014), which adds suitably scaled Laplace noise to a statistic to guarantee privacy. We now state the mechanism formally in the context of graph algorithms.
Definition 2.3. Let h : G → R be any graph statistic. The Laplace mechanism M h is defined as
In our problem, we will be given a contact graph G = (V, E) and transmission probability p. We will also be given a parameter s, indicating the number of starting infections I 0 . Our goal is to estimate the expected number of infections in the graph G when the s source nodes are chosen uniformly at random. We denote this quantity by f s (G). Formally, our goal is to obtain an (α, β)-approximation for computing f s (G).
Definition 2.5. We say f (G) is an (α, β)-
We make some remarks on our problem definition. First, we note that our model has random sources instead of a fixed set of sources given as input. This is justified in Section 6, where we show strong lower bounds for the fixed-sources model: Ω(n) additive error is necessary even for expander graphs. Second, we note that our notion of approximation contains multiplicative and additive error. This is the standard one in differential privacy, since additive noise is needed to guarantee privacy while multiplicative approximation is necessary even in the non-private setting.
In this section, we show that the global sensitivity of f s (G) is Θ(n/s) when p = 1, where s is the number of random source nodes. We will show that this implies a differentially private algorithm for estimating the expected number of infections with multiplicative error 1 + η and additive error Θ(n/s), for any given η > 0. We first give a proof of the global sensitivity bound.
Lemma 3.1. For p = 1, the global sensitivity of f s (G) is Θ(n/s) for each s.
Proof. Consider the vector x(G) ∈ [0, 1] V where x v (G) for each v ∈ V is the probability that v is infected under the random seeded starting infections. Let C 1 , . . . , C r denote the connected components of G and let C(v) denote the connected component node v ∈ V lies in. We can calculate
Now, we calculate the global sensitivity of the statistic f s (G) under the addition or removal of an edge. As mentioned above, this is exactly the ℓ 1 -sensitivity of the vector x(G). Since we are considering the global sensitivity, we can without loss of generality consider only edge additions; let's say the edge (u, v) ∈ E is added to the graph G and suppose C(u) ̸ = C(v). Now, consider the changes in the vector x(G). For w ∈ C(u), the probability of infection increases from 1 -
Since the remaining probabilities don't change, the ℓ 1 -sensitivity of x is A 1 + A 2 , where
The global sensitivity is the maximum of
This can clearly be computed in polynomial time, so we now have an efficient and private algorithm for computing the expected infections size.
We will now try to upper bound this expression to obtain accuracy guarantees. Then the expression above can be upper bounded by the following by using 1-x ≤ e -x for all x ∈ R:
Since the two terms in the above expression are independent with respect to |C(u)|, |C(v)|, we can optimize them separately. Simple calculus then gives us that the expression is maximized when |C(u)| = n s , so we have an upper bound of n es . A similar procedure shows that the second term is also upper bounded by n es , so the entire expression is upper bounded by 2n es , so the global sensitivity is O(n/s). Taking |C(u)| = |C(v)| = n/s in the expressions for A 1 and A 2 also shows that the global sensitivity is Ω(n/s), proving Lemma 3.1.
Next, we use our bound on the global sensitivity in the deterministic case to give an algorithm with nontrivial guarantees in the general probabilistic case.
Theorem 3.2. Given any constant η > 0, there exists a polynomial-time ϵ-edge differentially private algorithm which computes a (1 + η, O(n/sϵ))approximation for f s (G) in expectation.
Proof. Observe that the running an SIR process on the graph with probability p is equivalent to removing each edge with probability p and then running an SIR process on the resulting graph with probability 1. Given this observation, our algorithm proceeds as follows. We sample N graphs G 1 , . . . , G N , where each G i is obtained from G by retaining edge with probability p.
so the global sensitivity of the average fs (G) must also be O(n/s). Our algorithm concludes by outputting fs (G) using the Laplace mechanism, which guarantees edge-differential privacy by Lemma 2.4. By a standard argument via Chernoff-Hoeffding bounds, the average is within a 1 ± η multiplicative factor of f s (G) when N = Ω(n 2 ), giving us the multiplicative approximation guarantee. The additive approximation guarantee follows directly from combining the bound on the sensitivity with the utility of the Laplace mechanism (Lemma 2.4).
In this section, we explore a local sensitivity-based approach to the problem, called smooth sensitivity.
We show that one can compute a good approximation for smooth sensitivity, which we show suffices for guaranteeing differential privacy. The drawback of this approach is that it is difficult to obtain polynomial run-time, and all algorithms here require quasipolynomial time to implement. This illustrates the difficulties when applying local sensitivity-based approaches, which we overcome in Section 5.1. We note that a similar problem arises when using an approximate version of inverse sensitivity to estimate the infection size, but we omit the details here as it is unrelated to our main results.
First, let us recall the definition of smooth sensitivity from Nissim et al. (2007). Definition 4.1. For β > 0, the β-Smooth Sensitivity of f is
where LS f (y) is the local sensitivity of f at y. Nissim et al. (2007) show that for some β = β(ϵ, δ), adding Laplace noise calibrated by the β-Smooth Sensitivity to the statistic f (x) suffices to guarantee (ϵ, δ)differential privacy. However, this mechanism requires the exact calculation of the β-Smooth Sensitivity, which is intractable in our setting. We demonstrate here that instead of the exact calculation, we may use the approximation of the Smooth Sensitivity to calibrate the noise. This slightly generalizes recent work by Nguyen et al. (2023), which used approximate smooth sensitivity for faster subgraph counting.
To state and prove our results, we first define our notion of approximating the smooth sensitivity and recall the definition of an admissible noise distributions from Nissim et al. (2007). Definition 4.2. We say that Sf,β is a (γ, τ, δ ′ )approximation of S * f,β if with probability at least 1 -δ ′ , we have the following for all datasets x:
We may drop the parameter τ in the notation when τ = 0.
and for all measurable S ⊂ R, we have the following
(3)
In particular, the Lap(1) distribution is
Now, we are ready to state the privacy guarantee of approximate smooth sensitivity mechanisms.
Theorem 4.4. Let Sf,β be a (γ, τ, δ ′ )-approximation of S * f,β , assume we have a lower bound ρ on the smallest value of the smooth sensitivity min x S * f,β (x), and let Z be sampled from some (α, γ+β+τ /(ρe γ ))-admissible distribution. Then mechanism
Proof. Fix a pair of neighboring datasets x ∼ y. Let E be the event that S * f,β (x) ≤ Sf,β (x) ≤ e γ S * f,β + τ and E ′ be the event that S * f,β (y) ≤ Sf,β (y) ≤ e γ S * f,β (y)+τ . From the definition of our notion of approximation, we have that Pr[E and E ′ ] ≥ 1 -2δ ′ by the union bound. We will prove that conditioned on events E and E ′ , we have that M f (x) is (ϵ, e ϵ/2 +1 2 δ)-differentially private. Since E and E ′ both occur with probability at least 1 -2δ ′ , this implies the desired result directly by a standard characterization of differential privacy.
For the remainder of the proof, condition on the events that E and E ′ occur. Fix some measurable subset S ⊆ R of the co-domain of f . We have that Pr
In inequality (a), we used the Sliding Property with
= log e γ+β + log 1 + τ e γ • min x S * (x)
(5)
Finally, the two equalities follow by definition of the mechanism M f (x), completing the proof.
We now show how to approximately compute the smooth sensitivity for our problem in quasi-polynomial time. Specifically, fix some constant η > 0 and take
. We will show how to approximately compute the smooth sensitivity of f (G). Specifically, assume ϵ = O(1) and δ = 1/poly(n); we will show how to compute the βsmooth sensitivity of f for β = 1/O(log n).
Recall the definition of the β-smooth sensitivity for f :
In the above equations, the second equality follows since d(G, G ′ ) lies between 1 and n 2 . Since LS f (G ′ ) ≤ n for all graphs G ′ , observe that whenever k = Ω(log 2 n), we have that LS f (G ′ ) • e -βk ≤ 1/poly(n). Hence, it suffices to compute the following approximation which only considers k < Θ(log 2 n); this gives (γ, τ, δ ′ )-approximation for γ = 0, τ = 1/poly(n), and δ ′ = 1/poly(n) for arbitrarily large polynomials in n. Formally, our approximation is defined as follows:
This approximation can easily be computed in Õ(n log 2 n ) time by trying all possible G ′ , since computing the local sensitivity of f can be done in polynomial time.
In order to apply Theorem 4.4, we need a lower bound ρ on the smooth sensitivity of any input. To do this, we simply augment any input graph G with an additional isolated node before inputting the graph into the algorithm for computing approximate smooth sensitivity. This way, the algorithm may assume that all input graphs have at least one isolated node, so that the local sensitivity is always at least ρ = 1. Using this algorithm for computing approximate smooth sensitivity with the results of Theorem 4.4 gives a new private algorithmfoot_0 for estimating the expected infection size. Unfortunately. it is unclear how to obtain an approximation for the smooth sensitivity faster than trying all possible G ′ , since the structure of the local sensitivity of f is so complex.
In this section, we will give a polynomial-time algorithm for estimating the expected number of infections with differential privacy. Our approach will be based on the Propose-Test-Release framework of Dwork and Lei (2009), which is another instance of the local sensitivity-based methods explored in the previous section. We show that a suitable generalization of the framework suffices to give a polynomial-time algorithm. We then show that the utility guarantees of the algorithm match the ones given in the previous section up to poly-logarithmic factors. For ease of exposition, we will consider the case where there is only one random source (i.e., s = 1). Our claims and method extends to general s, but the expressions are more complicated.
We first review the propose-test release framework for an arbitrary statistic f (X) on database X ∈ X n .
1. Propose a bound β on the local sensitivity.
3. Compute noisy distance γ = γ + Lap(1/ϵ).
4. If γ ≤ ln(1/δ)/ϵ, return ⊥. Otherwise, return f (X) + Lap(β/ϵ). Dwork and Lei (2009) showed that the above mechanism preserves (2ϵ, δ)-differential privacy. Furthermore, the mechanism can provide much stronger utility guarantees if the bound β is much less than the global sensitivity. We generalize the framework slightly for our application. One difficulty in applying the framework is that the bound β on the local sensitivity needs to be derived analytically for a specific class of input databases. To provide more generality, we can instead use a noisy binary search to find a near-optimal bound β given the input database X. The other difficulty is computing the distance γ; this often cannot be computed in an efficient manner. Instead, we propose that it suffices to replace γ(X) with any non-negative statistic ϕ(X) with sensitivity 1 which is a lower bound on γ(X). In some cases such as ours, the algorithm designer can choose a ϕ(X) which can be efficiently computed and well approximates the original distance γ(X); this freedom enables us to give computationally efficient algorithms using propose-test-release in new settings. Our mechanism is formalized below.
1. Let ϵ ′ = ϵ/ log 2 (GS f ), where GS f is an upper bound on the global sensitivity 2. Binary search β ∈ {1, . . . , ⌈GS f ⌉} for an upper bound on the local sensitivity LS f (X).
a. Compute lower bound ϕ(X) on distance γ(X) = d(X, {X ′ : LS f (X ′ ) ≥ β}). b. Add Laplacian noise to the lower bound φ(X) = ϕ(X) + Lap(1/ϵ ′ ).
c. If φ ≤ ln(1/δ)/ϵ ′ , increase guess β. Otherwise, decrease guess β.
3. Let β be the smallest β where ϕ(X) > ln(1/δ)/ϵ ′ .
4. Return f (X) + Lap( β/ϵ).
We will first show that the above algorithm is still (2ϵ, δ)-differentially private. In the next subsection, we will illustrate how the above variant of propose-testrelease can be applied to our problem of estimating the expected number of infections in a contact network.
Lemma 5.1. The above algorithm is (2ϵ, δ)-DP.
Proof. Let's first analyze each iteration of the binary search. Since we have assumed that the statistic ϕ(X) has sensitivity 1, the output φ(X) is ϵ ′ -differentially private by the privacy guarantees of the Laplace mechanism. Consequently, the decision of whether to increase or decrease β in the binary search is also ϵ ′differentially private by post-processing. By basic composition of adaptive mechanisms, we have (ϵ, 0)differential privacy for the output of the binary search. Now consider step 6 of the mechanism and let β be as defined in the algorithm. Suppose that β ≥ LS f (X); then by the privacy guarantees of the Laplace mechanism, we have ϵ-differential privacy. Now suppose that β < LS f (X); then we have γ(X) = 0 by definition which implies ϕ(X) = 0 since 0 ≤ ϕ(X) ≤ γ(X) for all X by assumption on ϕ. But by the PDF of the Laplace distribution, the probability that φ(X) ≥ log(1/δ)/ϵ ′ is at most δ. As a result, we can conclude that step 6 is (ϵ, δ)-differentially private.
Again by basic composition of adaptive mechanisms, we can conclude that our generalized propose-testrelease framework is (2ϵ, δ)-differentially private.
We will apply the generalized propose-test-release framework described in Section 5.1 to our problem of interest. The primary difficulty in applying the generalized propose-test-release framework is finding a nonnegative statistic ϕ(X) which lower bounds γ(X) and is efficiently computable. Recall that γ(X) is defined to be the minimum number of edges which need to be added or removed such that the local sensitivity of f exceeds β. Thus, we need to understand the local sensitivity LS f (G) and how it is affected by adding or removing edges from the graph before designing a good function ϕ(•). As before, we first consider the case where the transmission is deterministic (Lemma 5.3). Then we will use results from the deterministic case to give an algorithm for the general problem with probabilistic transmission (Lemma 5.4).
For our algorithm, we will need the following result from Aissi et al. ( 2017):
Lemma 5.2. For an undirected graph G = (V, E), we say that a cut (S, V -S) is a b-balanced cut if there is at least b vertices on the smaller side of the cut. The minimum b-balanced cut of a graph (and its corresponding size) can be computed in polynomial time (Aissi et al., 2017).
Next, we define our statistic ϕ(G, β). For each B ∈ [n 2 ] and each k ≤ B, we will compute the following quantities: let
| and let U 2 (B, k) denote the maximum b such that there is a b-balanced cut of size B -k. Finally, we define ϕ(G, β) as the minimum B such that there exists k ≤ B where U 1 (B, k) + U 2 (B, k) ≥ β. We will now prove that this is a feasible statistic:
Further, ϕ(G, β) has sensitivity 1 and a polynomial time algorithm.
Proof. Recall that the statistic f we wish to estimate is the expected number of infections in the giant component of G. Since there is only one random source (s = 1), we can write f as a function of |C 1 (G)| as follows:
always, so it suffices to consider the local sensitivity of |C 1 (G)| and how it's affected by addition or removing edges from the graph. More formally, define f (G) = |C 1 (G)| to be our auxiliary statistic. Since f is a 1-Lipschitz function of f , we have that LS f (G) ≤ LS f (G). This implies that the distance γ f (G, β) to the closest dataset which has large local sensitivity is lower bounded by γ f (G, β). As a result, it suffices to find a statistic ϕ f (G, β) which lower bounds γ f (G, β) in order to obtain our desired statistic ϕ f (G, β). For the remainder of the proof, we will be working with the auxiliary statistic f (G) = |C 1 (G)|. Now let β be given; we wish to find the minimum number of edges to add or remove from G to obtain G ′ satisfying LS f (G ′ ) ≥ β. We will first characterize its local sensitivity LS f (G). If one edge is removed from G, the size of the giant component can only change if G is a bridge graph; the local sensitivity will then be the size of the smaller half of the bridge graph. If one edge is added to G, the size of the largest component can change by at most |C 2 (G)| by adding an edge connecting the first and second largest components. We will compute a lower bound φ f (G) on the minimum number of edges to add or remove from G to obtain
. This is because the two quantities differ by at most 1, by adding or removing the single edge which connects the two components.
As a consequence of the above claim, we only need to reason about increasing |C 2 (G ′ )| by adding or removing edges to G. Suppose for each B and k, we can show that U 1 (B, k) + U 2 (B, k) is an upper bound of how much |C 2 (G)| can increase. We claim that this implies that the output φ f (G) of the algorithm is a lower bound for the number of edge changes required to obtain |C 2 (G ′ )| ≥ β. Indeed, if it was possible to use less than φ f (G) edge changes to obtain |C 2 (G ′ )| ≥ β. Then using those exact edge changes, we can obtain U 1 (B, k) + U 2 (B, k) ≥ β, contradicting the assumption that φ f (G) was the minimal B output by the algorithm. Thus, it suffices to show that U 1 (B, k) + U 2 (B, k) is a valid upper bound. The remainder of the proof focuses on showing this claim. The outline is as follows. We show that given a graph, the amount which k edge additions can increase |C 2 (G)| is upper bounded by LS add (G) ≤ U 1 (B, k). In order to make use of the B -k edge removals, our goal is to find B -k edges to remove so that the impact LS add (G) of the edge additions is maximized. We will then show that the amount which LS add (G) can be increase by B -k edge removals is at most U 2 (B, k). Combining the results gives our desired claim.
When adding edges, the optimal choice for increasing |C 2 (G)| is to iteratively add an edge connecting the second largest component C 2 (G ′ ) with the third largest component C 3 (G ′ ); this can be proven by a standard exchange argument. In particular, one can observe that LS add (G) is a monotone and Lipschitz function of |C i (G)| for all i > 1. Furthermore, it is clear that the amount which the k edge additions can increase |C 2 (G ′ )| without using the budget of B -k for edge removals is upper bounded by LS add (G) ≤ k+2 i=3 |C i (G)|. Next, we wish to find B -k edges to remove first, so that the k edge additions afterwards can optimally increase |C 2 (G ′ )|. Since LS add (G) is a monotone function of all |C i (G)| for i > 1, removing edges from within C i (G) for any i > 1 can never increase LS add (G). Thus, we may assume without loss of generality that all edges are removed from
Next, we use the results in Lemma 5.3 to solve the general problem. Let N denote the number of samples which we will specify later. As in the non-private version of the problem, let G 1 , . . . , G N be N samples of the infection process, taking each edge in G with probability p. Our estimate of the number of infections in
We will now apply the generalized propose-test-release framework to our statistic f p (G), which uses the following definition of ϕ(G, β):
) is defined as in Lemma 5.3. Then ϕ(G, β) is a valid lower bound on γ(G, β) and has sensitivity 1.
Proof. Observe that we have
since we already have that ϕ(G i , β) ≤ γ(G i , β) for each i ∈ [n] by Lemma 5.3. Thus, it suffices to show that min i∈[n] γ(G i , β) ≤ γ(G, β). Suppose for the sake of contradiction that γ(G, β) < min i∈[n] γ(G i , β). Then there exists a sequence of γ edge additions or removals from G to obtain G ′ where LS fp (G ′ ) ≥ β.
) contains an edge if and only if G i (resp. G ′ i ) contains the edge. Consequently, we can conclude that γ(G, β) edges also suffices to transform G i into some G ′ i so that LS f (G ′ i ) ≥ β. But this implies that min i∈[n] γ(G i , β) ≤ γ(G, β), contradicting our original assumption. Our claim that ϕ(G, β) has sensitivity 1 follows directly since ϕ(G i , β) has sensitivity 1, so we are done. Now that we have a valid statistic ϕ(G, β), we can apply the generalized propose-test-release framework from Section 5.1 to obtain a polynomial-time private mechanism for releasing an estimate of the expected number of infections. In the next subsection, we will analyze its utility in a special class of graphs.
Let us first define the class of graphs we will work with.
Definition 5.5. A (n, d, λ)-spectral expander is a dregular graph on n vertices where its eigenvalues (that is, the eigenvalues of its normalized adjacency matrix)
Spectral expanders have many nice properties which will enable us to give theoretical guarantees when computing the expected outbreak size. For example, the size of the giant component of G under percolation is of size Θ(n) when an outbreak occurs in G. Such a property is necessary for our approach to work since we made a simplifying assumption that the smaller components only contribute to lower order terms.
Lemma 5.6. Let G be a (n, d, λ)-spectral expander and let G(p) denote the resulting (random) subgraph formed by retaining each edge of G with probability p. Then for p = 1+α d , there is (with high probability) a unique giant component of size Θ(n) and all other components are of size O(log n).
Additionally, spectral expanders have the nice property that the resulting giant component after percolation is a vertex expander for sets which are not too small (Diskin and Krivelevich, 2022). Using this property, we can show that our statistic ϕ(G, β) is not too small when β = polylog(n). As a result, we can obtain high accuracy estimates of the expected outbreak size.
Lemma 5.7. Let α > 0 be a small enough constant and let β > 0 be such that β ≤ α 4 . Let G = (V, E) be a (n, d, λ)-spectral expander with λ ≤ δ. Fix p ≥ 1+α d and let G(p) denote the resulting (random) subgraph formed by retaining each edge of G with probability p. If C 1 is the largest component of G(p), then there exists an absolute constant c > 0 such that with high probability for any S ⊆ L 1 with 16 ln(n)
Now that we have stated the necessary properties, let us prove our utility guarantees.
Theorem 5.8. Let G be a (n, d, λ)-spectral expander. Then our algorithm is an (1+η, poly log(n)/ϵ)approximation algorithm for estimating the expected number of infections, with high probability.
Proof. Consider β ′ = C log 3 (n) for some sufficiently large constant C; we will show that for all β ≥ β ′ , we have φ ≥ ln(1/δ)/ϵ ′ in Line 5 with high probability for our statistic ϕ described above. As a consequence, we have that β ≤ β ′ in Line 6, so our additive error is at most O(β ′ • log(n)/ϵ) = O(log 3 (n))/ϵ with high probability by the tail bounds of a Laplace distribution. Since we have that f (X) is within a 1 ± η multiplicative factor of the true expected number of infections by a standard Chernoff-Hoeffding argument, we will have our desired approximation guarantees.
Fix β ≥ β ′ . We will show that the lower bound ϕ on the distance d(X,
for some large enough constant C ′ . This would imply that with high probability, we have φ(X) > ln(1/δ)/ϵ ′ by the concentration of the Laplace distribution and the assumption that δ = 1/poly(n). The claim that ϕ ≥ C ′ log 2 (n)/ϵ ′ follows by the properties of spectral expander graphs discussed before. If we use edge additions, we know that all non-giant components are of size O(log n) so it requires at least Ω(log 2 (n)) edge additions in order to increase the local sensitivity to be greater than β. If we use edge deletions, then it requires Ω(log 2 (n)) edge deletions since the sampled graph G(p) is an edge expander with high probability (see Theorem 5.7). Thus, we have proven that ϕ ≥ C ′ log 2 (n)/ϵ ′ and we are done.
In this section, we'll give lower bounds for other natural settings in which one may wish to estimate the expected infection size. For example, our model assumes a random set of sources. We show when the set of source nodes are given, there are strong lower bounds even when the underlying graph is a spectral expander. Similarly, we show in the Appendix that if we instead wish to guarantee attribute privacy instead of edge privacy (in the fixed-source model), there are similar lower bounds showing that incurring Θ(n) additive error is inevitable. These lower bounds explain and justify our use of the random source model in our paper.
Here, we justify our use of the random source SIR model by showing if we allow for fixed sources, any differentially private algorithm must incur Θ(n) additive error. We remark that our lower bound even applies to spectral expanders in the interesting regime of sparse graphs, which most social network graphs satisfy. This is in contrast to our positive results in the previous section for the random source model.
Theorem 6.1. Let ϵ > 0 be a constant and let δ = o(1). Then any (ϵ, δ)-differentially private algorithm for estimating the expected number infections with a fixed source must incur an additive Θ(n) expected error, even if the underlying graph is a constant degree spectral expander.
Proof. Suppose for contradiction that there exists some (ϵ, δ)-differentially private algorithm M which guarantees sublinear additive error for the problem with a fixed source. Take any (n, d, λ)-spectral expander G for some constant d and λ with some fixed source node s and let the transmission probability be p = 1. Let G ′ denote the graph with all edges incident on s removed from G and note that G ′ is a d-edge neighbor of G. Since G is an expander, we know that it is connected so the expected number of infections in G with source s is n. Because the M has sublinear expected error, we know that 1).
But by group privacy properties, we have that Pr[A(G ′ ) ∈ o(n)] ≤ exp(dϵ) • o(1) + de (d-1)ϵ δ.
Since we have assumed that ϵ, d = Θ(1) and δ = o(1), the right hand side is o(1) so A(G ′ ) ∈ Θ(n) with high probability. But in G ′ , the source node is an isolated vertex so the expected number of infections is 1, so the expected error of the algorithm when run on G ′ is Θ(n), a contradiction.
Our work initiates the study of estimating the expected infection size of an epidemic, modeled by an SIR model, under edge differential privacy. Our main result is a polynomial-time edge-differentially private algorithm for the problem with only poly-logarithmic additive error on expander graphs. We believe our algorithms perform well on real-world graphs, because they often have good expansion properties. However, we note that this isn't immediately implied by our theoretical results, as our results only apply for d-regular graphs.
It turns out that this algorithm only incurs polylogarithmic additive error on a class of graphs called expander graphs (defined in Section 5.1), but we omit the proof since it the algorithm is superseded by the one in Section 5.1.