Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control
Authors: Sepehr Elahi
Paula Mürmann
Patrick Thiran
Venue: ICML 2025 poster (2025)
Keywords: Structure learning
SIS models
Epidemics
Vaccinations
Spectral radius minimization
Bounded treewidth
Dynamic programming
Parameterized algorithms
Primary area: probabilistic_methods->structure_learning
TL;DR: We develop algorithms to learn the graph structure and control SIS epidemics, providing sample complexity bounds, strategy optimality, and experimental validation.

Abstract: The Susceptible-Infected-Susceptible (SIS) model is a widely used model for the spread of information and infectious diseases, particularly non-immunizing ones, on a graph. Given a highly contagious disease, a natural question is how to best vaccinate individuals to minimize the disease's extinction time. While previous works showed that the problem of optimal vaccination is closely linked to the NP-hard *Spectral Radius Minimization* (SRM) problem, they assumed that the graph is known, which is often not the case in practice. In this work, we consider the problem of minimizing the extinction time of an outbreak modeled by an SIS model where the graph on which the disease spreads is unknown and only the infection states of the vertices are observed. To this end, we split the problem into two: learning the graph and determining effective vaccination strategies. We propose a novel inclusion-exclusion-based learning algorithm and, unlike previous approaches, establish its sample complexity for graph recovery. We then detail an optimal algorithm for the SRM problem and prove that its running time is polynomial in the number of vertices for graphs with bounded treewidth. This is complemented by an efficient and effective polynomial-time greedy heuristic for any graph. Finally, we present experiments on synthetic and real-world data that numerically validate our learning and vaccination algorithms.

Learn to Vaccinate:
Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control
Sepehr Elahi" 1
Paula Mürmann 1
Patrick Thiran'
Abstract
through networks (Nowzari et al., 2016). These models capture the complex interactions between agents, helping to predict dissemination patterns and devise strategies to con- trol unwanted spread (Lokhov & Saad, 2017). Among these models, the work is particularly well-suited for representing scenarios where agents can undergo multiple cycles of infection and recovery. While simple in structure, the interactions be- tween neighboring agents in an SIS model can give rise to complex behavior, which makes predicting and controlling its dynamics challenging.
The Susceptible- Saaeee--nneeee--Ssseeeeee Susceptible (SIS) model is a widely used model for the spread of infor- mation and infectious diseases, particularly non- immunizing ones, on a graph. Given highly con- tagious disease, natural question is how best vaccinate individuals to minimize the disease's extinction time. While previous works showed that the problem of optimal vaccination is closely linked to the NP-hard Spectral Radius Minimiza- tion (SRM) problem, they assumed that the graph is known, which is often not the case in practice. In this work, we consider the problem of minimiz- ing the extinction time of an outbreak modeled by an SIS model where the graph on which the disease spreads is unknown and only the infection states of the vertices are observed. To this end, we split the problem into two: learning the graph and determining effective vaccination strategies. We propose novel inclusion-exclusion based learn- ing algorithm and, unlike previous approaches, establish its sample complexity for graph recov- ery. We then detail an optimal algorithm for the SRM problem and prove that its running time is polynomial in the number of vertices for graphs with bounded treewidth. This is complemented by greedy
(SIS) frame-
The SIS model is represented using a contact graph where each vertex corresponds to an agent that can be in one of two states: susceptible or infected. The state of each ver- tex evolves probabilistically, influenced by the infection statuses of its neighboring vertices, allowing for multiple cycles of infection and recovery. In recent years, SIS mod- els have seen applications in fields such as the modeling of credit and financial markets (Chen & Fan, 2023; Barja et al., 2019), rumor spreading in social networks (Dong & Huang, 2018), malware attacks on computer networks (Märtens et al., 2016), and epidemiology (Nowzari et al., 2016; Grandits et al., 2019).
To mitigate the adverse effects of contagions modeled by the SIS framework, it is often necessary to perform strategic interventions. These interventions, in the form of regulatory interventions (Chen & Fan, 2023), installation of updates and patches (Muthukumar al., 2024), vaccinations or quarantines of vertices (i.e., person community), are de- signed to reduce transmission rates, limit the reach of the contagion, and accelerate its extinction. However, devising effective intervention strategies is particularly challenging when the underlying graph is unknown, a common scenario in practice (Rosenblatt et al., 2020).
an efficient and effective polynomial- heuristic for any graph. Finally, we present ex- periments synthetic and real-world data that numerically validate our learning and vaccination algorithms.
1. Introduction
Spreading models are essential frameworks for understand- ing how information, diseases, or behaviors propagate
We provide motivating example in the field of epidemiol- ogy. While we adopt the epidemiological terminology in this work, our approaches are general and can be readily applied to any other domain that utilizes the SIS framework.
'Equal contribution 'EPFL, Switzerland. Correspondence to: Sepehr Elahi Esepehr.elahi@epff.ch. Paula Mürmann <paula.murman @epfl.ch>.
Motivating Example. Consider the spread of cholera (Vib- rio cholerae), a highly contagious waterborne disease that in- dividuals can contract multiple times, making it well-suited
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Structure Learning and Vaccination for Epidemic Control
to the SIS model (Ryan & Calderwood, 2000). In many regions, the exact network of human interactions and envi- ronmental factors that facilitate cholera transmission is often not fully mapped, compelling public health officials to rely on observed infection data to infer these interaction patterns. By learning this underlying contact network, public health authorities can implement ring vaccination strategies, which involve targeting vaceinations individuals to effectively reduce transmission rates and extinction time (Ali et al., 2016).
minimization as vaccination heuristic (Van Mieghem et al., 2011; Kiji al., 2022). However, these methods assume the complete removal of either the vaccinated vertices or collection of their incident edges. More importantly, no work has addressed the problem of vaccinations when the graph structure is unknown.
Furthermore, existing work often considers continuous- SIS models, where vaccinations are applied continuously and can boost vertices' recovery rates (Abad Torres et al., 2017; Scaman et al., 2016; Drakopoulos et al., 2014). In contrast, we adopt a discrete-time SIS model with simulta- neous updates and focus on one-time vaccinations that only reduce infection probabilities. This model allows for both sparser observations of the states and fewer interventions, which often more applicable in practice.
In this paper, we focus on determining effective vaccina- tion strategies for an SIS epidemic when the underlying graph is unknown and only infection data is observed. In- spired by real-world approaches like ring vaccination, our approach combines network learning with a targeted vac- cination strategy minimize disease extinction time and control contagion spread.
Original Contributions. We address the challenge of de- vising effective vaccination strategies in an ongoing SIS process where the underlying graph is unknown. We ap- proach this problem by decomposing it into two tasks: first learning the network from observed infection states, and then designing effective vaceination strategies based on the inferred graph. Our primary contributions are as follows:
Structure Learning. Most research concerning epidemic structure recovery has been focused on Susceptible-nfeecter Removed (SIR) epidemic models, where each vertex can be infected only once before becoming inert. In SIR models, multiple infection instances, or cascades, are necessary to accurately infer the underlying network structure (Netra- palli & Sanghavi, 2012), with a common approach being maximum likelihood estimation (MLE) (Gomez-Rodriguer et al., 2012; Myers& & Leskovec, 2010; Gray et al., 2020).
We formally introduce the Vaccinating an Unknown Graph (VUG) problem, which aims to minimize the extinction time of an SIS process on an unknown graph through strategic vaccinations (Section 2).
In contrast, learning the network structure of an SIS model does not require multiple cascades since vertices can experi- ence repeated infections. This allows for the observation of more correlations between neighbors over time. However, the absence of a directional infection flow in SIS models introduces additional noise, complicating the learning.
We propose a novel inclusion-exclusion algorithm for learning the graph of an SIS epidemic, without making the restrictive assumption of the previous approach, and with learning guarantees (Section 3).
Leveraging the Spectral Radius Minimization problem as proxy for effective vaccination, we develop an ex- act dynamic programming- that runs in polynomial time for graphs with bounded treewidth. Additionally, we present simple, yet effee- tive, polynomial-time greedy heuristic (Section 4).
To the best of our knowledge, the only work on structure learning in SIS models is MLE-based approach by Bar- billon et al. (2020). Their approach can recover both likely edges and infection parameters, but comes without theoreti- cal guarantees and assumes a vertex is infected by only one neighbor at a time, which is a strong assumption in practice.
vaccination strategy
We conduct comprehensive experiments on real and synthetic data to evaluate the performance of our learn- ing and vaccination algorithms. Our results demon- strate significant improvements over existing baseline methods in terms of vaccination efficacy (Section 5).
We do not make this restrictive assumption in our work, and instead propose novel learning algorithm inspired by Ising model learning from Bresler (2015) that leverages the fact that stronger correlations occur between infection states of neighboring vertices than those of non-neighbors.
2. Problem Formulation
Vaccination Strategies. To suppress an undesirable SIS process, effective vaccination strategies are essential. Unlike SIR models, SIS processes allow for repeated infections, making them more challenging to eradicate. The extinction time of an SIS process is closely related to the spectral radius of the underlying graph (Ahn & Hassibi, 2014; Ruhi et al., 2016), leading to approaches that employ spectral radius
We first introduce the SIS model, followed by definition of vaccinations, and finally the problem of vaccinating vertices to minimize the extinction time of the SIS process.
SIS Infection Model. We consider a Susceptible-Infe Infectedd Susceptible (SIS) model of disease propagation, set on a
2

---

Structure Learning and Vaccination for Epidemic Control
graph G (V, E). We also use V(g) to denote the set of vertices of 9 when specificity is needed. The graph g is composed of n vertices V = [nx] == {1, (L....,,P) n representing individuals or entities, and a set of undirected edges E that capture the pathways through which the disease can spread. Given the edge (i.j) E E. we refer to vertices i and j as neighbors, and we use NN()== :- {i (t,j) E E} to denote the neighborhood of vertex j. We use A denote the maximum degree of the graph, i.e., A maxiev [i))) Finally, we denote by p(G) the spectral radius (i.e., largest eigenvalue) of the adjacency matrix of the graph G.
for all <> d'.
VUG Problem. The goal of the Vaccinating an Unknown Graph (VUG) problem is to select vertices to vaccinate in order to minimize the expected extinction time, while only observing the infection states Y, in each round f, i.e., the set of edges E is unknown.
Formally, let a: [T] x {0, 13"T - V denote a vaccination strategy, where (f,, Y,) Rg specifies the vertices to be vaccinated in round 1. The objective is then to minimize the expected extinction time, subject to vaccination bud- get of K: min, B[T₂] such that - |R I K, where T= represents the extinction time under strategy т. Note that the VUG problem is online: the agent observes the infec- tion states over time and must decide when and whom to vaccinate, subject to the global budget K.
We consider a discrete-time SIS model that proceeds over rounds (time steps) indexed by t E [T] = {1..... where each vertex can be in one of two states: suscep- tible or infected. The state of vertex i in round is denoted by r!!) E {0,1] 1} (1 for infected and 0 for susceptible). Fur- thermore, we use y E {0, 131s1 to denote the state vector the
of vertex set S S V. We denote by y = {{r(()]
3. Learning the Graph
S 1=1
state vector of all vertices in round t, and (+)) E {0) U [n] to denote the number of infected vertices in round f, i.e.,
First, we present our approach for learning the graph from the observed infection states and defer the discussion of our vaccination strategies to the next section.
Z - Y.1)
The SIS model is characterized by three key parameters: the seed probability Pmnat the infection probability Piat, and the recovery probability Pree In the initial round / = O, each vertex is infected independently with probability Pinit- As the infection progresses, an infected vertex transmits the disease to its susceptible neighbors with probability Pmnt- while each infected vertex recovers and becomes susceptible again with probability Prec. Below is table summarizing the conditional probabilities of the SIS model:
At a high-level, our learning approach makes use of the idea that the infection state of vertex at time is more likely to be influenced by the infection states of its neighbors at time / 1 than by the infection states of other vertices. We now formalize this idea.
3.1. Direct and Conditional Influence
Inspired by the work of Bresler (2015) on structure learning in Ising models, we introduce two measures of how vertex influences vertex j in round t: the direct influence (DI),
Event
Deseription
Probability
(2) 2gj and the conditional influence (CI), u ".a.ss Intuitively, DI captures the probability that directly infects j. while CI
(t)
y( =1 1 y/0)
1
remains infected
1 Pee
pite =0 0| 1
1
becomes susceptible
Pro
p 1 1
0
i becomes infected
-- [hexiggl- (1 Par y!0l)
measures how much i's infection state affects j's infection probability while conditioning on a set S S V {i. As we will show, if separates from j in the graph, then i's impact on j vanishes.
p(--1) =0 x:
remuins susceptible
[eevial -oor- 120l)
We say that an SIS infection is extinet at step if z(1) O.
We denote the extinction time, if it exists, by 7 == min(!= E [T] (t) = 0}, and oc, if otherwise.
Formally, we define
(t) = (yyytt==11 -1 x000 = =0, Y! =
Vaccination. In each round I, the vaccination strategy can vaccinate a subset of vertices Rg S V to lower their infec- tion probability. Formally, the strategy is given an overall budget K -- and can vaccinate at most K vertices in all rounds, i.c., Di= [Ry| < K. If a vertex i is vaccinated in round t', its infection probability is reduced by fac- tor of a E [0, 1] in all future rounds, i.c., if i E Re, then (t+1) = 1 Y = 0) = = -1 (1-apmr ()
and, for any Us E (0.
(c) sliss =
IP ((y(tt)) 1 ||,0) 0, v.(1) =1, =ys) -x(x(0t)=1) = - = 0, r 0, Y!! ys
'Note that neighbors infect each other independently and in- fected vertices heal independently of one another.
Using these quantities, we devise an inclusion based algorithm to learn the neighbors of a vertex j. More
3

---

Structure Learning and Vaccination for Epidemic Control
precisely, we first learn a superset of the neighbors of and then reject all non-neighbors. We explicitly explain both parts below, providing all missing proofs in Appendix D.3.
3.2. Estimation of Direct and Conditional Influence
For the purposes of theoretical analysis, including learning guarantees and estimation of DI and CI, we follow the ap- proach of Van De Bovenkamp & Van Mieghem (2014) and work with a modified ergodic Markov chain, (v((1) ( herr This chain has the same transition dynamics as the original SIS process (Y(*), }. except that upon reaching the all-zero (extinction) state, it immediately restarts from a predefined initial distribution (see Appendix D.1 for details).
Inclusion. If j is susceptible at time and its neighbor is infected, then infects j with probability Pint in the next round. Then, as j may have other infected neighbors, we get the following lower bound for Pyje"
(t)
Lemma 3.1. j E V are neighbors, then
(t) pile
Pinf
Vt E [T].
Crucially, the original SIS process (Y(1) and the modified chain { (v((t) } can be coupled up to the extinction time of (Y("). As a result, any analysis or estimation conducted on { ( before its first restart captures the behavior of the original process in the pre-extinction regime, which is precisely the regime relevant for the VUG problem.
We use this bound to construct a superset of the neighbors of j by including all vertices that satisfy U3] 2 Pint-
(t)
Exclusion. To reject non- -on-neighbors from a candidate neighbor set, observe that if & is not neighbor of j. then conditioning on any set S S V ki that separates k from forces the conditional influence of l on j to drop to zero. Intuitively, once we fix j's neighbors, j is isolated from k. Hence, applying the local Markov property, j transition probabilities in the next round only depends on its neighboring states, but not on
Stationary Assumption. The direct and conditional influ- ences introduced earlier are time-specific and thus cannot be reliably estimated from a single realization of either SIS process. However, empirical evidence suggests that the original process (Y()) quickly reaches a meta-stable state, which corresponds to the stationary distribution of the mod- ified process (1)(() } (Van De Bovenkamp & Van Mieghem, 2014).
We state and prove the above observation as lemma below.
( HEE used our estimations is drawn from the unique stationary distribution of the modified ergodic Markov chain (1)()))
Assumption 3.1.
The dataset D
Lemma 3.2. Let j,k E V be non-neighbors and let S C
V V ki,k) be superset of neighbors of j. ii.ie,,()) N()) C S. Then
As shown in Figure I and further discussed in Appendix A.I, our simulations demonstrate that the SIS process {Y(0) consistently enters a meta-stable regime within a few hun- dred rounds across a broad range of parameters. This obser- vation, along with the following remark, justifies both the stationarity assumption and the use of the modified process (V(() as a proxy for (Y(0)..
0 V [T], Us {0.1)
jikus
Finally, to ensure that using jiays to exclude non-neighbors does not mistakenly remove a neighbor, we show that a neighbor's 's CI on vertex j is bounded away from zero.
(1)
Lemma 3.3. Let i,j V be neighbors and let S C EVVU) be superset of neighbors of i.., N(G) S S. Then, for any (s) E 10.1) t [T]
Remark 3.1. Using the modified process (Tp(1) is natural in the context of the VUG problem: the SIS process {Y either converges to a meta-stable state, all the while coupled to process (1)(1),, }, or it goes extinct. The VUG problem is most challenging, and vaccinations critical, in the former scenario, where the infection persists and requires strategic vaccination for eradication.
(1) ()
2 Pmn(1=
Pint) A-1
We summarize the above lemmas in the following corollary.
{i} such that NG) C S, then for any E [T] and any (1) E
Corollary 3.1. Let i.j E V and S C V
The use of (T((1) and Assumption 3.1 will be further jus- tified in Section 5, where we do not artificially enforce ergodicity or stationarity, and yet our learning algorithm sufficiently recovers the graph.
{0, 1315--1
(EN( + Hiuree 2 (1n (1- Pmn) A-
While as a consequence of Assumption 3.1, DI and CI be-
(2) (t)
come stationary over time (i.e., for t, t' Tp. Pij Pgj
Proof. (+) By Lemma 3.3 and (+) by Lemma 3.2.
and (t) = (t') ). they still depend on a one-step tran- fli.us Jis
Next, we establish how we estimate the direct and condi- tional influence from observations.
sition between the conditioned and observed states. To
capture this, we will use ( and (((+1) denote a state

---

Structure Learning and Vaccination for Epidemic Control
Time steps to meta-stability 100
3.3. Learning Algorithm and Guarantee
50
150
200
250
We now present our learning algorithm, called SISLearn, with pseudocode given in Algorithm 1. SISLearn takes as imput the vertex set V, the dataset of infection state vectors D, estimator error thresholds K2 and Ky. infection proba- bility Pinf, and the maximum degree A of the underlying graph. Note that if Pint is not known, it can be estimated from observational data, like done in Kirkeby et al. (2017) via a mean- fann- approximation. Additionally, we will show in Appendix A.3 that our algorithm is robust to misspecifi- cation of Pinf and max degree A.
1.00
0.90
0.80
Infection probability (pint)
0.70
0.60
0.50
The algorithm then learns the neighbors of each vertex j via inclusion and exclusion. First, in lines 6-10, a super- set of (j). called S, is learned using Lemma 3.1. Next, in lines 11-15, SISLearn prunes S by excluding non- neighbors using Corollary 3.1. Notice that Corollary 3.1 holds for any configuration (s*(0), hence when applying it in Line 12, SISLearn selects the most data-rich config- uration that maximizes the minimum number of samples available for estimating the two conditional probabilities that constitute (V))) Formally, for a given vertex pair (i. and candidate neighbor set 2 N() for j. we define this configuration as (i,
0.40
0.30
0.20
0.10
(()) < Dree Pinf
0.00
0.00
0.10
0.20
0.30
0.40
0.50
0.60
0.70
0.80
0.90
1.00
Recovery probability (Pree)
Figure 1: Heatmap of the average time steps for an SIS pro- cess [Y(") to reach meta-stability on graphs from the aug- mented chn c20. 9.009..... flu.1. 1000 dataset (n = 40, p(9) A 3.9) as function of the infection (Piat) and recovery prob- ability (Prec). Meta-stability is determined using the con- vergence of the proportion of infected nodes. The white region at the bottom with no points indicates that no process reached meta-stability. The shaded gray area indicates the region where theory predicts rapid extinction (Theorem 4.1). Averaged over 100 runs.
arg max min (I(W))) = 0, w = 1, (()
s(()) = =,),
@Ef0,1)ie1-1
(( = 0, w = 0, u s v)
When clear from context, like in Line 12, we omit the de- pendence on and j, and simply write v...
Now, state the learning guarantee for SISLearn that combines a bound on the sample complexity with the cor- rectness of the algorithm.
Theorem 3.1. (Learning Guarantee.) Let Eys Evi S be positive constants, with Eu < Pon((1 (ang)
vector in a round and the state vector in the consecutive round, respectively.
and S 1. Suppose Assumption 3.1 holds. Further, assume that for all + j E V, all S VV {i, and all 1hs by E {0, 1}, and the respective (i.(i.)) the following inequality holds:
Now, given any vectors v E {0, 1318' and vis E {0, 1 1Ss) we can define the standard (unbiased) estimator
of P W (+)
w vss) using the dataset D as
T T( = - 1 = セい 4s = -V((1.))
2
S'
2
2n² + (1(1222)) 2n-1)
(1 - (1-0) (ennte/ee/2 1) log
P(
P( (++1)
ws NV (g) = +/s))
S
Σ I(vs)
1 {( ((+1)) =v/s/ }.
Then, with probubility at least 1 - S, Algorithm 1, when run with thresholds fer Ev and k2 = Ep. returns the correct edge set of the underlying graph: ED - E.
tEZ(Ws)
where -(Us)= - } denotes the set of time indices in the dataset where the vertices in set S take the values specified in vector s/s. and [(ws)) = [[ Subsequently, the estimators of DI and CL. denoted by Ayle and Uykk.ss can be computed as described above.
Remark 3.2. Note that 0, called the Markov contraction coefficient, is constant determined by the graph structure and the transition probabilities of the Markov chain { (g(())- It satisfies S 0 < and remains independent of the number of samples T drawn from the process.
5

---

Structure Learning and Vaccination for Epidemic Control
Algorithm 1 SISLearn: Learn SIS Graph from Data
Spectral Radius Minimization Problem. Given graph g (V, F.) with vertices and budget K, the SRM problem aims to find a subset of at most K vertices R C V whose removal minimizes the spectral radius. Formally, the SRM problem solves
1: Input: Vertex set V, data D, thresholds Ky: Ky, infec-
tion probability Pinf max degree A
2: Output: Learned graph edges Ep
3: ED <- 0
4: for j E V do
R arg min
pG[V RJ)-
(1)
5:
S+ 0
RC RCV.RRSK
6:
for i V do
Inclusion
7:
if Poje Pif Ky then
While the SRM problem is known to be NP-hard in general (Van Mieghem et al., 2011), 1), in what follows we present a polynomial- in-- optimal algorithm for graphs of bounded treewidth and a fast greedy heuristic for general graphs. In Appendix B, we provide an optimal algorithm for trees".
8:
end if 10: end for
9:
11: for i E do
D Exclusion
12:
if Vgli.
< Pinr(1 Pint) Ky then
13:
S 5 {
4.2. Vaccination Strategy for Graphs
14: end if
Here, we propose a vaccination strategy that is an optimal algorithm for the SRM problem. Our approach consists of a dynamic programming (DP) procedure performed on tree decomposition of the graph, allowing us prove polynomial-in-n time complexity for graphs of bounded treewidth. For readers unfamiliar with tree decomposition techniques, we detail simpler optimal algorithm for trees in Appendix B, which shares the core ideas of our main algorithm. Additionally, we provide a primer on tree decom- positions Appendix C to facilitate understanding.
15: end for
16: ED + ED U ((i.i)):es))
17:
end for
18:
return ED
4. Vaccination Strategies
Assuming we have learned the graph using SISLearn, we present two vaccination strategies inspired by the surrogate problem of Spectral Radius Minimization (SRM). We first establish theoretical result relating the extinction time of the SIS model to the spectral radius of the graph and the SRM problem.
Algorithm Overview. Our algorithm, pseudocode given in Algorithm 2, employs binary search strategy to identify the smallest possible spectral radius X3 achievable by re- moving at most K vertices from graph G, up to precision of & > O. The binary search is performed on [0, AJ, as A, the max degree of G, is a trivial upper bound for spectral radius (Van Mieghem et al., 2011).
4.1. Extinction Time
Below, we formally state (and provide proof in Ap- pendix 1.4.1) a sufficient condition for logarithmic extine- tion time that relates extinction time to the spectral radius of the graph. This result was first empirically established by Wang et al. (2003), and proven for this model by Ruhi et al. (2016).
For each candidate value of X during the binary search, we invoke feasibility check algorithm, pseudocode given in Algorithm 3, to determine whether there exists set of at most K vertices whose removal ensures that the spectral radius of the resulting graph does not exceed A. Below, we detail the feasibility check algorithm.
Theorem 4.1. The expected extinction time [E(T] upper bounded by Ollog n)) if p())= < Pree/ Pinf-
Given a graph g EV, with treewidth tw(g) S w, we first decompose the graph into nice tree decomposition g (T, (Xi (Xi)te(()), where T is a tree whose every node / is assigned a bag X, C V. To minimize ambiguity, we use vertex (vertices) when referring to elements of the graph G and node (nodes) when referring to elements of the tree decomposition T.
Theorem 4.1 establishes that rapid extinction hinges on the spectral radius of the graph, which leads to the natural ap- proach of reducing the graph's 's spectral radius through vac- cination or quarantining. modeled as the removal of vertices or edges. (Van Mieghem et al., 2011; Saha et al., 2015; Kiji et al., 2022). Building on this established approach, we fo- cus on the surrogate SRM problem through vertex removals. It is important to note that our setting remains general: vac- cinating a node does not remove it entirely unless a = 0. As will be demonstrated in Section 5, our vaccination strategies are highly effective in reducing the extinction time, further justifying the use of the spectral radius as a proxy for the extinction time.
We then perform a bottom-up dynamic programming algo- rithm the tree decomposition to find the optimal vacci- nation set for each node ( of the tree. First, define V22 as
Note that the SRM problem is NP-hard for general graphs and thus there exists no polynomial-time exact algorithm, unless P NP.
6

---

Structure Learning and Vaccination for Epidemic Control
the union of bags in the subtree T rooted including X,. Then, for every node i. V(T), every S _ Xx, and all CE {0,.. (O,.....4. K} define DP[t, S, c] as
Algorithm 2 DP algorithm for vaccination
Input: Graph G. treewidth upperbound tw(g) S w.
budget K, precision
2: Output: Set of vertices to vaccinate Rg
S.ct
3: low +- 0
R V2: = = 0. RJ) s 3..
4: high +-
> Use max. deg. as upper bound
5: R. + 0
In words, DPIt. S. c] stores the set of feasible removal sets of size from V, such that S is preserved and the spectral radius of the induced subgraph is at most X. Notice that if E ((T) is the root of T, then R E DPfr, 0, c) is feasible
9 + a nice tree decomposition of 9 with width S w
7: while high low > & do mid low+
9: (feasible, R) f- ALGORITHM 3(G, T, K, mid)
removal set with e celements that satisfies (V (V(G) R?)= < X. If no such set exists (i.e., DP[r 0, c] = 0), then there exists no feasible removal set of size at most c.
10: if feasible then
11:
high + mid
12:
Rg + R
13:
else
In what follows, we describe how Algorithm populates DP :. initialized to 0. for each node i of the tree in post- order, depending on the node's 's type (refer to Appendix C
14:
low <- mid
15: end if
16:
end while
for types).
17: Return Rg
Leaf node: If t is a leaf node, then X₂ = 0 and DP 0,0] {0).
Algorithm 3 Feasibility checker for graph vaccination
Introduce node: If is an introduce node with child node t', then, X, X₃ U {w) for some V(g). For every S S X, and for all 1 c S K, if v & S. then set S, (R' U [w): R' E DP(L',
1: Input: Graph G, nice tree decomposition I, budget K, threshold À
2: Output: Feasibility indicator and vaccination set R Initialize DP(1, S, < 0 for all of T, C X,, and
1]}.
o E S, then we need to verify if p(G[V, \ RT) S A for each R' E DP S\ d.. So, DP S. (R' E D SY (v),c): (GVVV \ RT) A}.
c C []]
4: To < nodes of T in post-order
5: r root of T
6: for node t E TTo do
Forget node: If / is forget node with child node f', then, X, Xy \ {w} for some E V(G) and thus V, Vv. Then, for every S _ X, and 0 S s K, set DP
7: for subset S C Xx do
8: for c E [0, Kj do
Update DP S, based on node type
DPIL' S, DP S (w]),c
end for 11: end for
10:
Join node: If is a join node with two children t and t2, then X, = X,, X,y- Then, for every S _ Xx, 0 S C2 S K, and R D R2 E DPftt,, S, c2). define R Rí U R2. Then, iteratively set (P = DP u (R) if [|| < K and ((G[V, \ RJ) S X.
12: end for
13: if DP(r, 0,c] = 0 for all c E [0, K] then
14: Return (False, 0)
15: else
16: c*+minfe E [0, K]: [r|r, 0, + 0}
Computational Complexity. We now state (and prove in Appendix D.4.3) the time complexity of Algorithm 2, showing that it is polynomial in the number of vertices n for graphs of bounded treewidth ws
17: Return (True, any R E DP(r, cl)
18:
end if
ing similar complexity, the decision version of the SRM problem cannot, the best of our knowledge, be expressed in monadic second-order logic, rendering Courcelle's 's theo- rem" inapplicable (Courcelle, 1990). Consequently, it was previously unknown whether a polynomial-in-1 time algo- rithm for SRM on bounded treewidth graphs existed.
Theorem 4.2. Given an imput gruph G with treewidth tw(G) S w. budget K. and precision e, Algorithm 2 has worst-case time complexity of O (1) (()))(())) log(A/=)).
The time complexity of our algorithm aligns with that of other NP-hard problems, such as the maximum independent set and Hamiltonian path, which are solvable in polynomial- in-n time on graphs with bounded treewidth using DP (Bod- laender et al., 2013). It should be noted that despite achiey-
Informally Courcelle's theorem states that any graph decision problem expressible in monadic second-order logic can be decided in linear time for graphs of bounded treewidth. We refer the reader to Chapter 7.4 Cygan al. (2015) for more details.

---

Structure Learning and Vaccination for Epidemic Control
Algorithm 4 Greedy vaccination algorithm
mance of our learning and vaccination algorithmss sepa- rately are presented in Appendix A. We provide the im- plementation of our algorithms as well as all baselines at https://githhe wwt.c/////cci/ee senn/eepehr788. 1earn2vac..
1: Input: Graph G, budget K
2: Output: Set of nodes R to vaccinate
3: R 40 0
4: g' +
5: while [R] < K do
Setting. We consider a contagion spreading on a real- world spreading network from OutbreakTrees (Taube et al., 2022), a database of infectious disease transmission trees compiled from real-world discase outbreaks. We utilize the chn 2009. flu. 1 00 dataset, representing the transmis- sion tree of the 2009 influenza A outbreak in Beijing, China, comprising n = 40 vertices. To simulate variability, we aug- ment the tree by adding edges between unconnected vertex pairs independently with a probability of 0.05, generating 40 distinct random graphs, with an average treewidth of
6:
v² f- + arg min ((C'I(()) (o)))
7: R
8:
g' -' f
9: end while
10: Return R
4.3. Heuristic Vaccination Strategy
Algorithm 2 exactly solves the NP-hard SRM problem as a surrogate for the vaccination problem. Although this al- gorithm is optimal and achieves the lowest spectral radius possible for given budget and thus the lowest extinction time, as will be verified in the experiments, it is computation- ally expensive for general graphs with unknown treewidth. To address this, we also propose a heuristic algorithm that is not only computationally efficient but also performs well in practice.
We simulate the SIS model on these graphs with parameters: Pint 0.3, Punt = 0.3, and Prec = 0.5. The vaccination bud- get is set to K = 7 with a 0.2, reflecting the 80% efficacy of the 2009 Beijing influenza vaccine (Wu et al., 2010). For each graph, we generate 40 random initial infection states and run the simulation for T = 2000 rounds.
Algorithms. Our approach involves two main steps: (I) learning the graph from the observed infection data of the first T/2 rounds using Algorithm 1, and (2) applying vaccination algorithms, DP (Algorithm 2) and Greedy (AI- gorithm 4) to the learned graph.
Algorithm Overview. Algorithm 4 iteratively removes the vertex that reduces the spectral radius the most.
Computational Complexity. The worst-case complexity of the algorithm is O (Kn*). The complexity arises from (i) K iterations in the outer loop; (ii) the spectral radius computation, which has complexity of O(n²) using the Lanczos algorithm for sparse graphs with (n) nonzero entries (Cullum & Donath, 1974); and (iii) sorting the ver- tices based on the reduction in spectral radius, which has complexity of On)).
It should be noted that we attempted to compare SISLearn with the MILE approach of Barbillon et al. (2020), the only work to-date on SIS structure learning, but they assume each vertex gets infected by only one neighbor at time, This assumption enforces lincar relationship between the number of infected neighbors and the probability of a vertex becoming infected. In our model, all infected neighbors attempt to infect a susceptible vertex simultaneously, lead- ing to an overall higher infection probability. This causes their method to always return a complete graph in our more general setting, making meaningful comparison infeasible.
4.4. Combined Learning and Vaccination
To solve the VUG problem, we first use SISLearn to infer the graph from data. Subsequently, we utilize the learned graph with either Algorithm 2 or Algorithm 4 to select K vertices for vaccination, depending on the graph's treewidth. Specifically, as supported by the empirical results in Ap- pendices A.8 and A.9, DP Algorithm 2 is computationally feasible for graphs with treewidth up to 15, enabling exact vaccination. For larger treewidths, we employ Greedy Algorithm 4.
For comparison, we evaluate the following baseline vacci- nation strategies on the learned graph:
Rand.: : vaccinate K random vertices.
LD: vaccinate K vertices with the largest degree.
PO (Scaman et al., 2016): vaccinate K vertices at the front of the priority order.
GW (Saha et al., 2015): vaccinate K vertices appearing in the most number of closed walks.
5. Experiments
The hyperparameters required by the above methods have been set as prescribed in the original papers. We set Ky = Ki = 0.01 for Algorithm I and use the positive- instance driven approach of Tamaki (2019) to compute the tree decomposition for Algorithm 2.
In this section, we present experiments using real-world graphs to evaluate the performance of our combined learn- ing and vaccination approach on the VUG problem. A comprehensive set of experiments analyzing the perfor-
8

---

Structure Learning and Vaccination for Epidemic Control
0.5
0.5
-No vac.
-No vac.
0.4
0.4
Proportion infected
Proportion infected
-PO
0.3
0.3
Rand
Rand.
DP (9100)
0.2
0.2
GW
DP (920n)
0.1
LD
0.1
DP (G100)
Greedy
DP (9
0.0
DP
0.0
DP (9)
0
250
500
750
1000
250
500
750
1000
Rounds after vaccination
Rounds after vaccination
Figure 2: Proportion of infected nodes versus rounds after vaccination using different strategies on learned graph from SISLearn. Shaded regions represent 99% confidence in- terval.
Figure 3: Proportion of infected nodes versus rounds after vaccination via Algorithm 2 on the learned graph (Gr)) from SISLearn using different numbers of rounds (7") for learning. Shaded regions represent 99% confidence interval.
Results. Figure 2 presents the average proportion of in- fected nodes over all runs against rounds following vacci- nation, comparing different vaceination strategies applied to the learned graph. Notably, all non-random vaccina- tion methods methots-except PO Po-outperform random vaccina- tion, demonstrating that our learning algorithm has effec- tively learned the graph. Our proposed algorithms, DP and Greedy, consistently outperform all baselines. Specif- ically, achieves the lowest infection rates across all rounds, with Greedy closely trailing behind. L. ranks third, demonstrating that while targeting high-degree nodes is effective, it does not match the performance of our algo- rithms. Notably, the PO strategy performs the worst, even underperforming the random vaccination baseline. This un- derperformance is likely because PO is designed for 'heal- ing' vertices in continuous-time SIS models (Scaman al., 2016), making it less suitable for our discrete-time simula- tion.
6. Conclusion
We introduced the VUG problem, combining structure learn- ing for SIS processes with strategic vaccination when the underlying contact network unknown. Our framework combines novel inclusion-exclusionn rithm supported by sample-complexity guarantees- wwth vaccination strategies aimed at minimizing the graph's 's spectral radius. In particular, the proposed dynamic pro- gramming approach achieves optimal results on graphs of bounded treewidth, while a simpler greedy heuristic scales effectively to general networks. Experimental results on real-world data confirm that our method significantly accel- erates epidemic extinction and reduces infection rates, when limited observations are available.
learning algo-
For future work, a promising direction involves examin- ing which aspects of the network structure are learned first, allowing us to optimize the balance between prolonged learning and timely vaccinations. Furthermore, establish- ing theoretical approximation guarantees for vaccination heuristics remains open problem.
Robustness Analysis. To assess the robustness of our combined approach, we vary the number of learning rounds used by SISLearn before applying Algorithm 2 for vacci- nation. We experiment with learning rounds ranging from 100 800 and illustrate the results in Figure 3. Our ap- proach consistently outperforms random vaceination even with few 100 learning rounds. Performance improves significantly as the number of learning rounds increases, eventually plateauing around 800 rounds. This indicates that our method remains effective across varying amounts of learning data. We provide additional robustness analysis using the other vaccination algorithms in Appendix A.4.
Acknowledgments
This work was partially supported by the SNF project 200021 204355 1, Causal Reasoning Beyond Markov Equivalencies.

---

Structure Learning and Vaccination for Epidemic Control
Impact Statement
Chen, N. and Fan, H. Credit risk contagion and opti- mal dual control-An SIS/R model. Mathematics and Computers in Simulation, 210:448-472, 2023. doi: 10.
This paper presents theoretical advances machine learning for epidemic modeling and outbreak control, with potential applications in public health. We defer discussion broader societal consequences to domain-specine implementations of our framework.
Courcelle, B.
The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. doi: https://doi.oor/10. (11600999-5400100)99444444
References
Abad Torres, J., Roy, S., and Wan, Y. Sparse resource allocation for linear network spread dynamics. IEEE Transactions on Automatic Control, 12144117,,-,728, 2017. doi: 10.1009/AAC22012259989)
Cullum, J. and Donath, W. A block lanezos algorithm for computing the algebraically largest eigenvalues and corresponding eigenspace of large, sparse, real symmetric matrices. In 1974 IEEE Conference on Decision and Con- trol including the 13th Symposium on Adaptive Processes, pp. 505-509, 1974. doi: 10.1 (0.1109/CDDC.1974.27700
Ahn, H. J. and Hassibi, B. On the mixing time of the SIS Markov chain model for epidemic spread. In 53rd IEEE Conference on Decision and Control, pp. 6221-6227, 2014. doi: 10.1 119/0ICC.201...770 77440644.
Cygan, M., Fomin, F. V., Kowalik, L.,, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipezuk, M., and Saurabh, S. Treewidth, pp. 151-244. Springer International Publish- ing, Cham, 2015. doi: (0.10007/97--333192222755
Ali, M., Debes, A. K., Luquero, F. J., Kim, D. R., Park, J. Y., Digilio, L., Manna, B., Kanungo, S., Dutta, S., Sur, D., Bhattacharya, S. K., and Sack, D. A. Potential for controlling cholera using a ring vaccination strategy: re- analysis of data from a randsmerraddomized clinical trial.
Cygan, M., Nederlof, J., Pilipezuk, M., Pilipezuk, M., Van Rooij, J. M. M., and Wojtaszczyk, J. O. Solving connectivity problems parameterized by treewidth in sin- gle exponential time. ACM Transactions on Algorithmss 18(2), 2022. doi: 10. 145/3506707.
PLOS medicine, (3(9)=e100212))) 2016.
Barbillon, P., Schwaller, I.., Robin, S., Flachs, A., and Stone, D. Epidemiologic network inference. Statis- tics and Computing, 30(1):61-75, 2020. doi: 10.1007/
Dong. S. and Huang, Y.-C. SIS Rumor Spreading Model With Population Dynamics in Online Social Networks. In 2018 International Conference on Wireless Communii- cations. Signal Processing and Networking (WiSPNET), pp. 1-5, 2018. doi: 10. 10/////NNET.201... 8.5388577
Barja, A., Martínez, A., Arenas, A., Fleurquin, P., Nin, J., Ramasco, J. J., and Tomás, E. Assessing the risk of default propagation in interconnected sectoral financial networks. EPJ Data Science, 8(1):32, 2019. doi: 10.
1140/epjds/s 3688--1---1-0--..
Drakopoulos, K., Ozdaglar, A., and Tsitsiklis. J. An efficient curing policy for epidemics on graphs. In 53rd IEEE Conference on Decision and Control, pp. 4447-4454, 2014. doi: 10.109/CDDC.22114440000333
Bodlaender, H. L., Cygan, M., Kratsch, S., and Nederlof, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In Fomin, F. V., Freivalds, R., Kwiatkowska, M., and Peleg, D. (eds.), Automata, Languages, and Programming, pp. 196-207, Berlin, Heidelberg, 2013. Springer. doi: 10. 17.
Gomez-Rodriguez, M., Leskovee, J., and Krause, A. Infer- ring Networks of Diffusion and Influence. ACM Trans- actions on Knowledge Discovery from Data, 5(4):21:1- 21:37, 2012. doi: 10. (0.1144//286777..88877411
1007/978-3-662--9929
Borse, R. H., Shrestha, S. S., Fiore, A. E., Atkins, C. Y., Singleton, J. A., Furlow, C., and Meltzer, M. Effects of vaccine program against pandemic influenza a(hinl) virus, united states, 2009-2010. Emerging Infectious Diseases, 19(3):439-444) March 2013. doi: 10.3201/ bid1903.12334.
Grandits, P., Kovacevie, R. M., and Veliov, V. M. Opti- mal control and the value of information for stochas- tic epidemiological sis-model. Journal of Mathematical Analysis and Applications, 476(2)6665-695, 2019. doi: http://doi.org// wtt.://og/....../...ooooo 1016//.jmaa....... 2019.04.009
Bresler, G. Efficiently learning ising models on arbitrary graphs. In Proceedings of the Ferty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, pp- 771-782, New York, NY, USA, 2015. Association for Computing Machinery, doi: 10. 10.1145/27465392274666
Gray, C., Mitchell, I.., and Roughan, M. Bayesian Inference of Network Structure From Information Cascades. IEEE Transactions on Signal and Information Processing over Networks, 6:371-381, 2020. doi: 10. 10.1109/TSIPN.200 2990276.
10

---

Structure Learning and Vaccination for Epidemic Control
Kiji, M., Hasibul Hasan, D. M., Segre, A. M., Pemmaraju, S. V., and Adhikari, B. Near-optimal spectral disease miti- gation in healthcare facilities. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 999-1004, 2022. doi: 10.1 109//CCD5548444202222000
Decision and Control (CDC), pp. 3560-3565, 2016. doi:
10.1 109/CICC2001..799888
Ryan, T. and Calderwood, S. B. Cholera vaccines. Clini- cal infectious diseases, 31(2):661 2000.
Saha, S., Adiga, A., Prakash, B. A., and Vullikanti, A. K. S. Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread. In Pro- ceedings of the 2015 SIAM International Conference on Data Mining (SDM), Proceedings, pp. 568-576. Soci- ety for Industrial and Applied Mathematics, 2015. doi: 10.11377/.77816111970000
Kirkeby, C., Halasa, T., Gussmann, M., Toft, N., and Græsbøll, K. Methods for estimating disease transmis- sion rates: Evaluating the precision of poisson regression and two novel methods. Scientific Reports, 7(1):9496, August 2017. doi: 10. (038//41598-007-09999
Kontorovich, L. A. and Ramanan, K. Concentration inequal- ities for dependent random variables via the martingale method. The Annals of Probability, 3666):2126-2158, November 2008.
Scaman, K., Kalogeratos, A., and Vayatis, N. Suppressing Epidemics in Networks Using Priority Planning. IEEE Transactions on Network Science and Engineering, 3(4): 271-285, 2016. doi: 10.1 N0.100//NNEE.20..22000 2600022.
Lokhov, A. Y. and Saad, D. Optimal deployment of resources for maximizing impact in spreading pro- cesses. Proceedings of the National Academy of Sci- ences, 114(39))88188-8888 2017. doi: 10.1073/pnas. 1614694114.
Tamaki, Positive-instance driven dynamic programming for treewidth. Journal of Combinatorial Optimization, 37 (4): 12):333311,,,, 2019.
doi: 10.1007/s10878- 0-10788-------------
Märtens, M., Asghari, H., van Ecten, M., and Van Mieghem, P. dime-dependent dis-model for long-term computer worm evolution. In 2016 IEEE Conference Communi- cations and Network Security (CNS), pp. 207-215. IEEE, 2016.
Taube, J. C.,, Miller, P. B., and Drake, J. M. An open- access database of infectious disease transmission trees explore superspreader epidemiology. PLOS Biology, 20(6):1-17, 2022. doi: 10.137
3001685.
Van De Bovenkamp, R. and Van Mieghem, P. Time to metastable state in sis epidemics on graphs. In 2014 Tenth International Conference on Signal-Image Technology and Internet-Based Systems, pp. 347-354, 2014. doi: 10.1 10110/9TSS..014.550
Muthukumar, S., Senthilkumar, M., and Veeramani, C. Op- timal Control of Computer Virus Spreading Model with Partial Immunization. Wireless Pers Commun, 134(4): 2287-2315 2024. doi: 00.1007/s11277-022 11013-6.
Myers, S. and Leskovee, J. On the convexity of latent social network inference. In Lafferty, J., Williams, C., Shawe- Taylor, J., Zemel, R., and Culotta, A. (eds.), Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
Van Mieghem, P., Stevanović, D., Kuipers, F., Li. C., van de Bovenkamp, R., Liu, D., and Wang, H. Decreasing the spectral radius of graph by link removals. Phys. Rev. 84(1):016101, 2011. 1. doi: 10.1 10.11195eeRe.1...000110001
Wang. Y., Chakrabarti, D., Wang, C., and Faloutsos, C. Epidemic spreading in real networks: an eigenvalue view- point. In 22nd International Symposium on Reliable Dis- tributed Systems, 2003. Proceedings. pp. 25-34, 2003, doi: 10. (109//ELDIS.2003.12233
Netrapalli, P. and Sanghavi, S. Learning the graph of epi- demic cascades. SIGMETRICS Performance Evaluation Review, 40(1):211-222, 2012. doi: 00.1145/2318855 2254783.
Nowzari, C., Preciado, M., and Pappas, G. Analysis and Control of Epidemics: A Survey of Spreading Processes on Complex Networks. IEEE Control Systems Magazine, 36(1):26646, 46, 2016. doi: 10.1 1090009/.SS.M S.I.CC........44. 2.155.0.0
Wu, J., Xu, F., Lu, L.., Lu, M., Miao, L.., Gao, T., Ji, W., Suo, L., Liu, D., Ma, R., Yu, R., Zhangzhu, J., Liu, W. Zeng. Y., Li, X., Zhang, X., Pang. X., and Deng, Y. Safety and effectiveness of 2009 hinl vaccine in beijing. New England Journal of Medicine, 263(25):24162443) 2010. doi: 10.1055/NEJMoa 100773
Rosenblatt, S. F., Smith, J. A., Gauthier, G. R., and Hébert- Dufresne, I. Immunization strategies in networks with missing data. PLOS Computational Biology, 16(7): c1007897, 2020. doi: 10.137 10.137 pcb.
Ruhi, N. A., Thrampoulidis, C., and Hassibi, B. Improved bounds on the epidemic threshold of exact sis models on complex networks. In 2016 IEEE 55th Conference on

---

Structure Learning and Vaccination for Epidemic Control
Fl score
0.0
0.2
0.4
0.6
0.8
1.0
1.00
0.90
Inpul infection probability (pint)
0.80
0.70
0.60
0.50
0.40
0.30
0.20
0.10
0.00
1
2
3
4 5
6
8
9
10 11 12 13 14
Input max degree (Å)
Figure 4: Heatmap of the average Fl score of SISLearn with 1000 rounds of learning on the augmented chn. 2009. flu. 1. 00 dataset (true Pint 0.3 and true A 10) function of the input infection probability (Pint) and input max degree (Å), Averaged over 100 runs.
A. Additional Experiments
In this appendix, we provide additional extensive experiments on the performance and robustness of our learning and vaccination algorithms. All experiments were conducted on a machine equipped with two Intel Xeon E5-2680 v3 CPUs, 256GB of RAM, and running Ubuntu 24.04.1 LTS. We used Python 3.11.11 and NetworkX 3.4.2 for graph manipulation and generation.
A.1. Time to Reach Meta-Stability
To investigate the time required for the SIS process to reach meta-stable state, we conducted simulations using the same augmented chn 2009. flu.1. 1. 00 graphs from the main experiments (Section 5). For these simulations, we systematically varied the infection probability (Pmr) and the recovery probability (Pre)) from 0 to Meta-stability was determined be reached when the proportion of infected nodes over moving window of recent time steps converged, indicating that the overall infection level had stabilized. We recorded the number of rounds (time steps) until this convergence criterion was met.
Results. Figure 1 displays a heatmap of the average number of time steps required for the SIS process reach meta- stability, function of the infection probability (Pint) and recovery probability (pre).. The average spectral radius of the graphs was p(G) R 3.9. The results demonstrate that, for wide range of parameter settings where the infection persists (i.c., does not quickly go extinct, indicated by the white region and the theoretically predicted extinction region shown in gray), meta-stability achieved relatively quickly. Even in the slowest-cone coneest-onverging scenarios (brighter regions in the heatmap), meta-stability is reached within 250 rounds. This rapid convergence to a quasi-stationary state provides empirical support for Assumption 3.1.
12

---

Structure Learning and Vaccination for Epidemic Control
1.0
1.0
0.8
0.8
FI score
0.6
SHRINIO
Fl score
0.6
0.4
0.4
0.2
Algorithm
0.2
Algorithm
SISLearn (Alg. 1)
SISLearn (Alg.
0.0
0.0
200
400
600
800 1000 1200 1400
400
800
1200
1600
2000
Number of learning rounds
Number of learning rounds
(a) Augmented chn. 2009. E flu.2 1. CC graphs
(b) Augmented usa. 2009. flu. 00 graphs
Figure 5: Average Fi-score of the learned graph from STSLearn versus number of learning rounds used on the augmented chn.200 2009. flu. 1. 00 and usa 2009. flu.1.l.00000 00 graphs. Shaded regions represent the 99% confidence interval.
A.2. Learning Performance of SISLearn
We investigate the performance SISLearn in learning the underlying graph of the SIS epidemic on real-world outbreak graphs. We consider two settings:
2009 flu outbreak in Beijing, China. This the same setting as the main experiments, using the chn. 2009, flu. 1 00 network with n 40 vertices, augmented with 5% additional edges, get a total of 40 graphs. We simulate the SIS model on these graphs with parameters: initial infection probability Puit 0.3, infection probability Piat 0.3, and recovery probability Pree = 0.5
2009 flu outbreak in Pennsylvania, USA. For this setting,
the much larger usa 2009. flu. 1.00 contact network, from the 2009 HINI influenza outbreak in Pennsylvania, USA, with 286 vertices (Taube et al., 2022). We augment the network with 1% additional edges to get a total of 40 graphs. We simulate the SIS model on these graphs with parameters: initial infection probability Pinic = 0.3, infection probability Piat 0.2, and recovery probability Pree = 0.5.
We present the average F F1-score of the learned graph from S SISLearn versus the number of learning rounds used in Figure We observe that for both settings, the Fi-score increases rapidly with the number of learning rounds at the start and eventually plateauing. Importantly, SISLearn able to achieve a high Fl-score (> 0.9) for both graphs with sufficient number of learning rounds.
Results.
A.3. Robusiness of SISLearn to Input Misspecification
evaluate the robustness of SISLearn to misspecification of its input parameters: the infection probability (Pur) and the maximum degree (A). The experimental setup mirrors that described in Section 5, using the augmented chn 2009. 9. flu. 1. 00 dataset. For data generation, the true SIS model parameters were an infection probability Piat = 0.3 and an actual maximum degree A = 10. SISLearn was then executed for 1000 learning rounds, with systemat- ically varied inputs for Pin (ranging from 0.01 to 1.00) and Á (ranging from to 15). After learning, we computed the Fl score of graph recovery, averaged over 100 independent simulation runs.
Results. Figure 4 presents a heatmap of the average Fl score achieved by SISLears rn as function of the input infection probability Pint (y-axis) and the input maximum degree Á (ı-axis). The heatmap clearly demonstrates that SISLearn exhibits considerable robustness to variations in these input parameters. Optimal performance, indicated by F1 scores approaching 1.0 (brightest regions), is observed when fmnt in the vicinity of the true value (c.g., approximately 0.2 to 0.4) and Å is sufficiently large (e-g.. â 2 7). Importantly, SISLear rn maintains high scores (often exceeding 0.8)
13

---

Structure Learning and Vaccination for Epidemic Control
even when Piot is moderately overestimated (e.g., up 0.5 0.6) when Å is underestimated (e.g., ... down 5 6). This robustness suggests that precise prior knowledge of Piat and A is not stringent requirement for achieving effective graph recovery with SISLearn.
A.4. Performance of SISLearn with Different Vaccination Strategies
Here, present results the robustness of our learning algorithm combined with other vaccination strategies. We use the same setting in Section 5 and vary the number of learning rounds from 100 to 800. We then apply separately apply Greedy, LD, and CW for vaccination.
Results. In Figure 6, we present the average fraction of infected nodes over time following vaccination using the different algorithms on the learned graph. We observe that Greedy is the only algorithm that outperforms random with only 100 rounds of learning. Greedy also performs the best with the most learning rounds, followed by LD and GW. Interestingly, LD performs better than Greedy when T = 200 and T" = 400, potentially indicating that our learning algorithm recovers high-degree vertices quickly.
A.5. Performance of Algorithm 2 and Algorithm 4
Here, we present results on the effectiveness of our proposed vaccination strategies, Algorithm 2 and Algorithm 4, on the real-world outbreak graphs. Unlike the main experiments, we do not used the learned graph and instead apply our algorithms and baselines directly on the original graphs.
2009 flu outbreak in Beijing, China. This is the same setting as the main experiments, using the chn. 2009. flu. 1. 00 network with n = 40 vertices, augmented with 5% additional edges, to get a total of 40 graphs. We simulate the SIS model on these graphs with parameters: initial infection probability Puit = 0.3, infection probability Puat = 0.3, and recovery probability pree = 0.5. We set the vaccination budget to K = with an efficacy of 80% (a = 0.2).
2009 flu outbreak in Pennsylvania, USA. For this setting, we use the much larger usa 2009. flu. 1.00 contact network, from the 2009 HIN1 influenza outbreak in Pennsylvania, USA, with n = 286 vertices. We augment the network with 1% additional edges to get a total of 40 graphs, with an average treewidth of 58. We simulate the SIS model on these graphs with initial infection probability Pinit = 0.3, infection probability Pint = 0.2, and recovery probability Prec 0.5. We set the vaceination budget K 50 with efficacy of 75% (a 0.25), reflecting the efficacy of the influenza vaccine in much larger than the 8), computing the tree decomposition for Algorithm 2 is computationally very expensive, and thus we only present results for Algorithm 4. Similarly, computing the priority order for PO is also infeasible as it is an NP-hard problem (Scaman et al., 2016), and thus we do not present results for this method.
the US in 2009 (Borse et al., 2013). As the treewidths
flu. 1 00 dataset (58 versus
Baselines. For convenience we restate the basclines used in the main paper:
Rand.: vaccinate K random vertices.
LD: vaccinate K vertices with the largest degree.
PO (Scaman et al., 2016): vaccinate K vertices at the front of the priority order.
GW (Saha et al., 2015): vaccinate K vertices appearing in the most number of closed walks.
We present the average proportion of infected nodes over time following vaccination using different strategies on the augmented chn. 2009.0... flu.1 1. 00 and usa 2009. flu. 1 00 graphs in Figure 7. We observe that Algorithm 2 consistently outperforms all baselines, followed by Greedy and LD (see Figure 7a). On the larger usa 2009. flu.1.00 graph in Figure 7b, Greedy performs the best, followed by LD and GW.
Results.
A.6. Impact of Epidemic Severity on Vaccination
We further evaluate our combined learning and vaccination approach under varying conditions of epidemic severity and available vaccination resources. The base experimental setting is identical to that described in Section 5 (augmented chn. chn.2009. 2009.000.220 flu. 1. 00 dataset, SISLearn for graph inference, followed by vaccination). We consider two specific scenarios:
14

---

Structure Learning and Vaccination for Epidemic Control
0.5
0.5
.No vac.
.No vac.
0.4
0.4
Proportion infected
Proportion infected
0.3
0.3
Rand.
Rand.
-LD (9100)
Greedy (9100)
0.2
Greedy (G200)
0.2
-LD (9200)
Greedy (G400)
LD (9400)
0.1
0.1
Greedy (g000)
LD (9500)
Greedy (g)
LLD (9)
0.0
0.0
250
500
750
1000
250
500
750
1000
Rounds after vaccination
Rounds after vaccination
(a) Greedy vaceination algorithm (Algorithm 4)
(b) LD vaccination algorithm
0.5
-No vac.
0.4
Proportion infected
GW (6100)
0.3
Rand.
GW (9200)
0.2
GW (Q4o0)
0.1
GW ($soo)
GW (g)
0.0
0
250
500
750
1000
Time step after vaccination
(c) GW vaccination algorithm
Figure 6: Proportion of infected nodes versus rounds after vaccination using different algorithms on the learned graph (GT.) from SISLears rn with varying numbers of learning rounds (T'). Shaded regions represent a 99% confidence interval.
Low Severity / Low Budget: The SIS model is simulated with lower infection probability Puf = 0.15. After learning the graph from the first T/2 rounds of this simulation, vaccination strategies are applied with a reduced budget of K = 3.
High Severity High Budget: The SIS model is simulated with a higher infection probability Paf = 0.80 and an increased budget of K 25.
All other parameters, including recovery probability Prec 0.5, vaccination efficacy a 0.2, and learning parameters for STSLearn, remain consistent with those in Section 5. Results averaged over 40 runs.
Results.
Figure illustrates the proportion of infected nodes following vaccination for the two described scenarios.
In the low severity scenario with low budget (Figure 8a), the epidemic inherently less aggressive. Even without vaccination, the infection level is considerably lower than in the main experiment. With small budget of = 3, our DP and Greedy strategies, applied the graph learned by sISLearn, rapidly reduce the infection to near extinction. While
15

---

Structure Learning and Vaccination for Epidemic Control
0.5
0.5
-No vac.
0.4
0.4
Proportion infected
Proportion infected
No vac.
PO
0.3
0.3
Randd
Rand.
0.2
0.2
GW
GW
0.1
LD
0.1
LD
Greedy
Greedy
0.0
DP
0.0
0
250
500
750
1000
500
1000
1500
Rounds after vaccination
Rounds after vaccination
(a) Augmented chn. 2009. flu. graphs
(b) Augmented usa 2009. flu. 1.00 graphs
Figure Proportion of infected nodes versus rounds after vaccination using different strategies on the augmented chn. 2009.0000000000 flu. 00 and 2009. flu. 00 graphs. Shaded regions represent the 99% confidence interval.
other strategies also show benefit, the targeted approaches achieve the most significant reduction, effectively controlling the mild outbreak with minimal resources.
Conversely, in the high severity scenario with high budget (Figure 8b), the "No vaccination" shows very high persistent infection level. Here, substantial vaccination effort is required. Our DP and Greedy algorithms again demonstrate superior performance, achieving a much more significant reduction in infection compared to baseline heuristics like LD and GV. This highlights the importance of optimized vaccination strategies when facing highly contagious outbreaks.
A.7. Empirical Running Time of SISLearn
Here, we empirically demonstrate that our SISLearn algorithm is computationally efficient and can scale to very large graphs. We generate connected Erdös-Rényi (ER) graphs with n E {1000,- 10000} vertices and edge probability = 1.1 log n n//n. We set the number learning rounds to = 2000 and run SISLearn to learn the underlying graph, measuring its running time. For each n, we generate random graphs and report the average running time.
Results. Figure shows the average running time of SISLearn across different number of vertices. As shown, SISLearn can easily handle graphs large 10000 vertices and x 50000 edges, taking only 9 minutes run, demonstrating that SISLearn is computationally efficient and can scale to very large graphs.
A.8. Empirical Running Time of DP
In this section, empirically demonstrate the superior performance of our DP Algorithm 2 in solving the SRM problem graphs with bounded and unbounded treewidth, compared with an exhaustive search algorithm.
Small Treewidth. We generate graphs of treewidth with n E {10,..., .8) vertices, and set the budget 0.2n. We then run our algorithm and an exhaustive search algorithm, which checks all (") subsets, to find the optimal vaccination set (i.e., solve the SRM problem), measuring their running time. Note that both approaches are exact algorithms and return the optimal solution. For each n, generate 40 random graphs and report the average running time.
Unbounded Treewidth. We generate connected Erdös-Rényi (ER) graphs with E {10,... ,.....,9)) 90} vertices and edge probability p = 1.1 logn/n n/n, which results in graphs with unbounded treewidth. We also set the budget K = 0.2n and run our DP algorithm and the exhaustive search algorithm to find the optimal vaccination set, measuring their running time. For each n, we also generate random graphs and report the average running time.
16

---

Structure Learning and Vaccination for Epidemic Control
0.8
0.8
No vac.
0.6
0.6
Proportion infected
Proportion infected
0.4
0.4
-No vac.
RRnnd
,WW
0.2
Rand.
0.2
LD
GW
LD
Greedy
Greedy
DP
0.0
DDP
0.0
250
500
750
1000
250
500
750
1000
Rounds after vaccination
Rounds after vaccination
(a) Low severity (Pur = 0.15) and low budget (K = 3).
(h) High severity (Pitt = 0.80) and high budget (K = 25).
Figure 8: Proportion of infected nodes versus rounds after vaccination using different strategies on the graph Iearned by SISLearn from the augmented chn. 2009. flu.l. 00 dataset with low and high severity. Shaded regions represent the 99% confidence interval, averaged over 40 runs.
10
SISLearn (Alg. I)
8
Time taken (min)
2
0
2000
4000
6000
8000
10000
Number vertices (n)
Figure 9: Running time (in minutes) of the SISLearn algorithm on connected ER graphs, plotted against the number of vertices. Shaded regions denote the 99% confidence interval, averaged over 10 runs.
Large Treewidth. We also conduct additional experiments on large graphs with treewidth 10, for which we only run DP algorithm, as the exhaustive search algorithm is computationally infeasible. We generate graphs with {20,... 2000} vertices and set the budget K = 0.2n. For each n, we generate 40 random graphs and report the average running time.
Results. In Figure 10, we compare the average running times and the exhaustive search algorithm across the small and unbounded treewidth settings. As shown, DP is orders of magnitude faster than exhaustive search for > 20. In the small treewidth setting (Figure 10a), the exhaustive search time grows exponentially with while DP exhibits polynomial growth, consistent with the theoretical guarantee in Theorem 4.2. In the unbounded treewidth setting (Figure 10b), DP also incurs exponential time, which is to be expected for the NP-hard SRM problem, but remains substantially faster than exhaustive search.
Figure 11 shows the average running time of DP on graphs with treewidth 10. As shown, DP exhibits polynomial growth in
17

---

Structure Learning and Vaccination for Epidemic Control
10
10a
10a
10
Time taken (min)
Time taken (min)
100
10
Seodle de Ap
10
10-2 2
10-2
Naive
Naive
10-3
10-3
DP (Alg. 2)
DP (Alg. 2)
20
40
80
100
20
40
60
80
Number of vertices (n)
Number vertices (n)
Graphs with treewidth 3
(b) ER graphs with p 1.1 log n/n
Figure 10: Log rumning time (in minutes) of naive exhaustive search and our DP Algorithm 2 for solving the SRM problem on threewidth-3 and connected ER graphs plotted against the number of vertices, n. Shaded regions denote the 99% confidence interval, averaged over 40 runs.
time complexity as n increases, demonstrating that can handle graphs with n 2000 vertices in about 20 minutes. This significant improvement over the exhaustive search algorithm, which is simply infeasible for such large graphs
A.9. Empirical Running Time Greedy
Here, we empirically demonstrate that our Greedy Algorithm is computationally efficient and can scale to large graphs. We generate connected Réndi (ER) graphs with {20..... 1000} vertices and edge probability p 1.1 log n/n. We the budget K 0.2n and run both our DP and Greedy algorithm solve the SRM problem, measuring their running time. For each n, we generate 40 random graphs and report the average running time.
Results. Figure 12 shows the average running times of DP and Greedy across different number of vertices. As shown, Greedy is significantly faster than DP, with polynomial growth in time complexity, while DP exhibits exponential growth. More importantly, Creedy is able to scale to graphs with n = 1000 vertices, taking only z 10 minutes to run.
10
DP (Alg. 2)
20
weleatteeeoo www.tteeaacrttto eaceeeae Geor TromLoie
Time taken (min)
Time taken (min)
100
15
10
10
10
5
DP (Alg. 2)
10-3
Greedy (Alg. 4)
0
500
1000
1500
2000
200
400
600
800
1000
Number of vertices (n)
Number vertices (n)
Figure 11: Running time (in minutes) of the DP algorithm on random graphs with treewidth tw = 10, plotted against the number of vertices. Shaded regions denote the 99% confidence interval, averaged over 40 runs.
Figure 12: Log running time (in minutes) of the DP and Greedy vaccination algorithms on connected ER graphs, plotted against the number of vertices. Shaded regions denote 99% confidence interval, averaged over 40 runs.
18

---

Structure Learning and Vaccination for Epidemic Control
Algorithm 5 Optimal vaccination for tree
Input: Tree = E). budget K, precision
2: Output: Set of vertices vaccinate R
3: Initialize L 4-0 0
4: Initialize high + 1
5: Initialize Rs= 9
6: while high -low > & do
7: mid &- towhh
8: (feasible, R) t ALGORITHM 6(T, K, =mid)
9: if feasible then
10:
high mid
11:
R₂ +- R
12: else
13:
low + mid
14: end if
end while
Return Rgg
B. Vaccination on Trees
In this section, we present a vaccination algorithm for trees that we prove to be optimal i.e., it reduces the spectral radius the most for given vaccination budget K. The algorithm is based on the observation that following removal (i.e.. vaceination) of any vertex of a tree, the resulting tree has least one new connected component.
Algorithm Overview. Our algorithm, pseudocode given in Algorithm 5, employs a binary search strategy to identify the smallest possible spectral radius A achievable by removing at most K vertices from a tree T, up to a precision of >> 0.
For each candidate value of during the binary search, we invoke a feasibility check algorithm, pseudocode given in Algorithm to determine whether there exists of most K vertices whose removal ensures that the spectral radius of the resulting forest (i.e., disjoint union of trees) does not exceed X. Algorithm 6 operates follows:
1. Depth-First Traversal: The algorithm picks arbitrary root and recursively explores each subtree in post-order (i.e., children before parent).
2. Vertex Removal: If a subtree's 's spectral radius exceeds X, root of that subtree marked removal (vaccination), effectively splitting the tree into smaller components.
3. Budget Verification: After the traversal, if the total number of removed vertices does not exceed K, the current À is considered feasible.
Using Algorithm 6, we can identify the smallest D via a binary search procedure conducted within the interval [0, vn 1]. leveraging the fact that the spectral radius of tree is bounded by vn (Van Mieghem et al., 2011). The binary search iteratively narrows the range of possible À values by selecting midpoint and using the feasibility check determine if the current À is achievable within the vaccination budget. As the domain of X is continuous, stop the binary search when the interval size is less than predefined threshold E.
Optimality Guarantee. Below, we formally state and prove the optimality Algorithm 5.
Theorem B.1. Given tree T and vaccination budget K, let X*
p(T(VV where It is the solution to the optimization problem given in Equation (1), and let X p(T(V) \ Rel), where Rg is the output of Algorithmm 5 with precision parameter E. Then, X- - del S E.
Proof. Proof follows from the correctness and completeness of Algorithm 6, as detailed in Appendix D.4.4.
19

---

Structure Learning and Vaccination for Epidemic Control
Algorithm 6 Feasibility checker for tree vaccination
Input: Tree = E). budget K, threshold À
2: Output: Feasibility and set of vertices to remove R
3: Choose an arbitrary root vertex V
4: Initialize R + 0
5: DFS(T, r, None, A, R)
6: if |R] I 1 then
7: Return True,
8: else
9: Return False, R
10: end if
1: function DFS(T, u, parent, A, R)
2: S+ 0
3: for E (u) do
4: if v * parent then
5:
S
u, U
6:
end
7: end for
8:
if ((T(S) > then
9: R + RU (u)
10:
return (
11: else
12: return S
13: end
end function
Computational Complexity. The worst-case complexity of the algorithm is O (n* log log(vn/s)). The complexity arises from (i) the binary search, which has a complexity of (log((/n/z)) (ii) the post-order traversal of the tree, which has a complexity of (n)) and (iii) the spectral radius computation, which has a complexity of (nn)) using the Lanczos algorithm for sparse graphs with (n) nonzero entries (Cullum & Donath, 1974).
C. Tree Decomposition
In this section, we provide brief introduction to treewidth, tree decompositions, and nice tree decompositions, For more details, we refer the reader to Cygan et al. (2015).
Tree decomposition. tree decomposition of a graph is a tree with bags of vertices as nodes that captures the connectivity and structure of the graph. Below, we provide formal definition of tree decomposition.
Definition C.1. (Tree Decomposition from Cygan et al. (2015)), A tree decomposition of G is pair T =TT, (T.AXeheevch)
where T is tree whose every node is assigned a vertex subset X; C VG), called a bag, such that the following three conditions hold:
UlEV(T) X, = V(g). other words, every vertex of G at least one bag.
For every u, E F(G), there exists node i Tf such that bag X, contains both and v.
For every u E V(G), the set T. {t V(T): u Xe), i.e., the set of nodes whose corresponding bags contain induces connected subtree T...
The width tree decomposition 7 equals max |x,| - 1, that is, the maximum size of its bag minus 1. Notice that a trivial tree decomposition is formed by a single node with the entire vertex set the graph as its bag, resulting in a width of
20

---

Structure Learning and Vaccination for Epidemic Control
Treewidth. Then, the treewidth of undirected graph g, denoted by tw(g), the minimum width of any tree decomposi- tion of G. Intuitively, the treewidth of undirected graph 9 is measure of its tree-likeness (treewidth of tree is 1, hence the minus in the definition). It is very important concept used in parametrized algorithms and complexity theory, where many NP-hard problems, such as the Hamiltomian path problem, Steiner tree problem, and many others (Cygan et al., 2022), become tractable on graphs of bounded treewidth.
For general graph, an upper bound on the treewidth is the number vertices. However, for many real- well-wrldd graphs, the treewidth much smaller than that, making it a useful parameter for designing efficient algorithms.
Nice tree decomposition. A nice tree decomposition is tree decomposition that is easy to write dynamic programming algorithms on. It is formally defined below.
Definition C.2. (Nice tree decomposition from Cygan al. (2015)). A rooted tree decomposition 9 - (T.,(xileeve) with rool T is nice if X, @ and every node of 'T is of one of the following four types:
Leaf node: a node t that has no children and has X, 00
Introduce node: a node with exactly one child such that X, Xy U {o} for some vertex v & Xe: we say that v introduced at
Forget node: node with exactly one child l' such that X, Xe Mu) for some vertex E Xy; say that is forgotten at t.
Join node: a node I with two children L1, 12 such that X, Xt, = X12
Working with nice tree decompositions simplifies the design of dynamic programming algorithms,, due to limited types of nodes. The following lemma shows that every tree decomposition can be converted a nice tree decomposition without increasing the width and in polynomial time.
Lemma C.1. (Lemma 7.4 of Cygan et al. (2015)). If graph 9 admits a tree decomposition of width at most w, then it also admits nice tree decomposition of width at most w. Moreover, given a tree decomposition (T. (Xihever)) of G of width at most wi, one can time ( has at most ( nodes.
compute a nice tree decomposition of G of width most that
D. Additional Proofs
D.I. Coupling between Processes (t) and (v(()
The transition probabilites of (+) hee,, are governed by the infection and recovery probabilities as described in Section 2. the chain is in the zero state, it will remain in that state forever; i.e., PP((()) = Q (t--1) = 0) 1.
For the modified SIS process (v(() fIETD, we define the transition probabilities as follows:
(P(Y()) = =05" ((((-) = v)) if + 0, (Pinit)ll -iini)n Pimi))m-ll"' otherwise,
(( /² ((1111) = 3')
where ||>||| = Ei. vi denote the number of 1-elements in a n-dimensional vector & E {0, 1)".
Clearly, the processes (Y) HET, and heTD can be coupled until the first time to when ((o) = (/(()) 0. at which point process Y goes extict and process restarts.
D.2. Concentration Inequality
Here we state the concentration inequality for the modified SIS Markov chain (1)()) that we use to provide error bounds on the learning algorithm.
21

---

Structure Learning and Vaccination for Epidemic Control
Lemma D.I. Let (VP()) HieTo be observations from the SIS process, where TD a of (not necessarily consecutive) time
indices and T (0, 13 Under Assumption 3.1, I, for any subset U C V, any state the {0, 1 13101, and any e, ó > the
following deviation bound holds for the unbiased estimator:
P ( =v) -P = wb)) 2 26) 20)=0. sō.
whenever (Tbl 2 2log(2/6) =11-0)2 where 0 < A < 1 is constant depending on the graph structure but independent of T.
Here, P ) denotes the true probability (e.g., under the stationary distribution), and P = =vv) = -u is the empirical estimate over T T= [Tb] samples.
Proof. Let S = (0, 13 be the state space of Markov chain {V()) } with transition probability p(v/"(//)) from state s/ S to state 6² E S. Let T = |T'l be the number of observations and let S be the product state space of these T observations. By definition, the process { heN has the Markov property in time, hence so does a sub-sequence ( We further define ypu : + R as
( ((T)
T Σ 1 = 1b
Notice that the function above is c-Lipschitz with respect to the Hamming metric d(U, W) = -E 110 + W()) on S", with Lipschitz constant c 1/TT.
We are now ready to apply Theorem 1.2 from Kontorovich & Ramanan (2008) for Markov chains. The theorem states that for a e-Lipschitz function y on S",
t²
Pile E [p]] 2 t & 2exp
2nc
M?
In our case, the sequence length (replacing n in the theorem) and c = 1/T. The relevant M,, term becomes My. The bound becomes
12
T12
PP(pU - E [pvl] 2 1) < 2exp
2T(1/T)2M3 = 2exp
2MM
where Mr = 01-00)((11 and is the Markov contraction coefficient given by
+0) lpp (')))))))) p. (l)
w EE
We have < because every configuration và can transfer into the all-zero configuration 0. Hence, for any states v', r² E S both p(o)x'') > 0 and p(Qlv") > 0 and the support of p(-lv)) (xb) and p(-lv") is not disjoint, which implies 0 < 1.
We write Mr < 1/(1- 0) and the probability bound becomes
TL -0
Plleu - E [pr]] 2 t S 2exp
To ensure this probability is at most ö for deviation t = we get
TE 0)-
2 2exp
S
2
Finally, solving for T yields the desired condition
2 2log(2/0) T
<2(1 - 0)
22

---

Structure Learning and Vaccination for Epidemic Control
D.3. Learning Results
Note that Lemma 3.1, 3.2, and 3.3 hold for both the original process {Y and the modified process (v as they depend only the transition probabilities outside the all-zero (extinction) state.
Lemma 3.1. if E V are neighbors, then
2 Pinf Vt E [T).
Proof. Consider an SIS process (Y-(9) EEN at an arbitrary time t with infection probability Pus and let i, E V be neighboring vertices. Let ||yl| = ===1 y E {0, 111 Then
-1
Yi denote the number of 1-elements (LV()) 1)-dimensional vector
"/ P
(yg (y(++)) =|y = 0, y, (,,0==1)
Σ
I ((ry(tt))= =11x, = =0, = =,
=1, -1,YN =y) P (Krona vixx"' 0,,,, =1)
vE(0,)]Wen-1
(0) IP (y = v/X,"' 0, r, =1) 2 Pinf
E
(1-
where (a) is obtained by the law of total probability and (b) by the definition of the SIS process. If the whole neighborhood of j and the state of j is known at time f, the transition probability of (1)) from state zero at time t to state one at f + 1, given by (1 - Ptnt) Pmm)) ||+l++11 That is, we know y = 0, y = 1 and yt NOM = y- Hence, the number of infected vertices ||y|| and contribute to the probability of vertex j being infected in the next round. Finally, (c) is obtained by lower bounding 1 - (1 Pin)) llv))l++ 2 Pint and by normalization:
Σ
PP P(NNOme = uix 0, y, =1) =1.
Lemma 3.2. Let j, & E V be nei-hbigs and let S _ V (j.k} be a superset of neighbors of i.e., N(j) S S. Then
(0) jlk.us
0 Vt E [T], Us (0.1)191.
Proof. Consider an arbitrary time L, vertices k E V. j and k non-neighbors, S C V ki,k) such that N/) C S and a vector ys E {0, 111. We note that 5 separates j and k, ie., any path between j and & passes through set S. Then by the local Markov property of the model (the probability of a vertex j transitioning from the zero state to the one state only depends on the state of j and its neighbors the previous round) the evolution of is conditionally independent of k and write explicitly:
Glkss = P ( (y(44)) 1|x,00) = 0, (0) = 1, us) PP (y -11, 0, Y, = =0, Us
IPC. (ysttt)) 11x 0, 111)
KNG),, y2(1) 1, Y (t)
SWG) (sS())
P (ys 11 0, 1 UN()), y/=== 00 0(1
SWN() -USWG)))
P (y 1| (1) 0. 10 = -UNG)) -P (y 11x,,0) -0, -MNG))
(2)
0,
where (2) follows from the aforementioned Markov property.
Lemma 3.3. Let j E V be neighbors and let SCV. {i} be superset of neighbors j. i.e. N(1) S S. Then, for any
() (0, 13 1S-- e [T]
(8)
2 Pon(1 - Pind A-1
23

---

Structure Learning and Vaccination for Epidemic Control
Proof of Lemma 3.3. Consider an SIS process (Y(*) kefty with infection probability Plat and maximum degree of the underlying graph A, i E V be neighboring vertices, S _ VV be a set such that (i) and (s E {0. 1 13181-1 an arbitrary vector of infection states set 5 \ {t). The conditional influence of on given S is defined as:
( = (x)++) 1
= 0, v,
1, L. syS =5 -P (y/ = 1|x ( o, Y.
0, Y sY Moy
As we assume N S and by the local Markov property of the process, Us and the state information on y contain all information for the transition probability of vertex from the zero state the state. Therefore write:
P
( ((t)) 1|,, = 0, y. = 1, r(t)
NOME )MO)))
( 1|x = 0, 0,
-11x,"==000
= =0, =0, =0,YoOM
NON0 BNOMN
(1 1 - Pint) -1-r)) | ( (11- Pint) (Ms))ll)))))
(1 Pint) (IN (1
Pinr))
2 Pinf
Pint)
A-1
where we used the definition of the infection probability and the fact that the degree of a vertex is upper bounded by A.
For the following lemmas, consider the modified SIS process (e()) described in Appendix D.I and data collected from its stationary distribution.
Lemma D.2. Under Assumption 3.1, let i + j V with m I(VV, 0, vr 1). If 210g(2/0)/(6211 -))) and 5, > 0, then
IP (1uge Agjs 2 8) S 8.
Proof. Let * j j,V,,, 8, O, under Assumption 3.1 let m I( = v, =1) with m 210g(2/6)/(E2(1 0) We will use Lemma D.1. First, set
I(V, 0, v 1) =)=
fIE LE w/ =0, 0, w = =1].
We construct a subsequence of the Markov chain [ (
/eepy which consists of all the time indices directly after an event in I: (w(r+1) : e I = 0, v = 0)}- Notice that Lemma D.I also holds for this Markov chain, since it is itself a Markov chain. Let Sm
Σ ( ((((+)) }} count the occurrence of v (r+1) following a time index satisfying
rEI(V, v.
( = 0 and w(!h) 1. Then, the expectation of this estimator is given by:
[Sm]] =
Σ -0,,
1(b(r+t)= = 1} @ mP (w//rt))= =110// = 0, (0) =1),
where (+) holds because the expectation taken over the random variable 1 1( = 1} conditioned on the event I = 0, Vi = 1) holding in the previous time step. Hence Sm/m / can serve as an estimator for T (r+1) 1/ 0, v.(") = =1). Applying Lemma D.I, we obtain that:
P P (g((+1)) = - = 0, (-)
= =1) / (++1) = =1 0, ( [0)=1] 2c)
= P
E [Sm]]
Sm 2 S 8.
m
24

---

Structure Learning and Vaccination for Epidemic Control
Lemma D.3. Under Assumption 3.1, lei f (V,,j) d, > 0, ths E {0, 10,11,11, and m = 0, V. 0, vbs) if min(m= m } 2 ना- log(2/5), then
m si=
I(V, - 0, V,V, 1, 1/)))
P (15ss - Pgli. 2 22s) S 28
Proof. We will once again use Lemma D.I. Under Assumption 3.1 let i + E V, C ( > 0, us E {0, 1315)
m* ( = 0, v. 1, Us). m
I[ = 0, V 0, ths), and min m + m } 2 م:- 1og(2/6). We define
1- = (w =1 = 0, w = 1, 5 vs) and 9 = IP (P///( (w)+ = 1 //// = 0, w = 0, w/) = =ws)
Then, let x- and & be their estimators, respectively. That is,
Φ+ == P v (wstt)) 1///// 0, u 1, 1 =vs)
Φ = P = =1)0
= 0, 1 0, 0. 1/5
Then, define 1 and Sm as
St Σ
11 = =13,
Sm Σ
1w (++)) 1}.
The expectation of the estimators is given by:
E [t m m+pp and E [5m]] 47
By application of Lemma D.I:
P (1yst - -3+1 =)
(3)
Similarly,
IP (1+0 - x 8. 8.
(4)
Now, writing Dylivis and Byyess using 5pt and , the triangle inequality implies that
Mylkos Eggi = 100 -------- - - -($* - 0-
S 100- - -6+1 + - -
Combining the above,
IP ( [1 1.0 - D3levbl < <2=)
2 P (10 *+1 | + 1/ - - 25)
> (1pp - +31 <E) -
- p <&})
(5)
2 1 - P (f/++ - ++1 2 2)) - P (f|@ - - 2 c))
(6)
21 1 25,
where in (5) we have used the intersection of events property, in (6) we have used the union bound, and in (7) we have used (3) and (4).
Finally, taking the complement, we get ((usiivs Dyn.vsl 2 2s) < 28 as desired.
25

---

Structure Learning and Vaccination for Epidemic Control
Lemmas D.2 and D.3 establish concentration for individual estimators Ayjs and Dyli,ss (for a specific configuration vhg). For learning algorithm STSLearn (Algorithm 1) to succeed, need these estimates to be accurate simultaneously across all relevant i, S, and respective configurations dgg. We thus define the event A(Ev, En) that captures this joint accuracy:
A(Ev)EN)=
(vi (VijjEVe e
Mais Agpel S Eq) and
vi V. (i,j) s.t. for each respective d3 [pgiing Pyla,v3 s sew) j.
where, as a reminder, (i, or V when clear from context, is defined
(0) (i.5) arg max min (I(W)) (1) 0, ! 1, syp (), 0, w/ O, s 15)). (E(0,1)181-1
The following lemma provides the sample complexity conditions under which this joint event A holds with given probability. Lemma D.4. Under Assumption 3.1, if for every * j E V, every S S VV (i.j), and every configuration this 4/ (0. 1}.
the number of observations I = t , = 3 s (i) is at least Mimin where
2
2n 2n²(11 (1+22 2"
Mymn
(1 - (min) 2,
log
then (((A(Ev))))) 21-5.
Proof. Under Assumption 3.1, assume that for all i + VV, (i.j). thes Uy E {0, 1}, and the respective (i,),,
log 2n 2n+(1
T(V; = vs, V,- = 4/ Vs = (i. 2 [1-0) 4 1)
Then, we write using a union bound
P (A(Eer sn))
= =1-P -
B(i,j} CV.SCVV [i,}} such that for vh. laglas Bylingg > Ev or Jayja Aapel > Ex
21-P
U
{131Ei03 B)1001 > soju U
{1mys - Aapeel > cne
ieEV SCVVAS
wev
21
Σ iJEV SCV\
P (PIJAN 2/11811 > >6 - Σ
P
(lage - A3pel > en)
IJEV
The number of pairs (i,j) in V be upper bounded by n² while the number all conditioning sets S C V (t,j) is equal to Σ (n-2) & 2n- Let m jv.s (T(V; the v = m. Vs = =g))). We obtain therefore from Lemma D.2 and Lemma D.3 that for m > (2ng///)))(0000)mmmmm//////aa//
P (AA(e)) Ex)) n²22=-2(2)) ((2) n²-5.
log 2n (1+2 we can substitute {=ôn2 + 2n-1),
Now, since we assumed m satisfies m 2 (1-0) (min F.
yielding P (A(sv;e 2 --
Theorem 3.1. (Learning Guarantee.) Let Eus S be positive constants, with Ey Ping(1 Ping) ) and S 1. Suppose Assumption 3.1 holds. Further, assume that for all i it j V, all S C V {i.5), and all Vi.d, {0, 1}, and the respective 4/' (i, the following inequality holds:
I I(V, 4 = Ug (b( 2
(1 - ()inmin (emnin(Ev//i (Ev/ (Ev/2, 22, log 2n + 2" 2"-1"
S
26

---

Structure Learning and Vaccination for Epidemic Control
Then, with probability least 1 C, Algorithm I, when run with thresholds Fi, Ey and Kip EY returns the correct edge set of the underlying graph: EDD = E.
Proof. Assume that for all i # E EV V. {155) v4 23 E {0,1}; and each respective (3 and under Assump- tion 3.1,
22 + (2n2(1++"-1) 2
2
T(V; v/4; 3 Ø3 V 4/5) (1 11-))mmnn (
log
and ou < Pinr(1 - Pint) Pint) 1/2 Then, by Lemma D.4, (A(ev, - Ç. For the remainder of the proof we will assume that A(Ev, eu) holds.
We will show that the algorithm learns the neighborhoods of all vertices correctly one after the other. As the outer for-loop (Line 4-17) iterates over all vertices in V, it suffices to show that the algorithm correctly learns the neighborhood of an arbitrary vertex j E V. To do so, we will show that after the inclusion for-loop (Line 6-10), S is a superset of the neighborhood j. and that in the exclusion for-loop (Line 11-15), all neighbors remain in S while all non-neighbors get removed.
Inclusion Loop. By Lemma 3.1, if i is a neighbor of j. then Maj 2 Pun- Hence, conditioned on A being true, Agp -Mjja| S Eg. and Agjs 2 Ep. Therefore, after the inclusion loop, the set S contains at least all neighbors of j.
i.e., S N()).
Exclusion Loop. We first establish that no neighboring vertex of j can be removed from S in the exclusion for-loop and next show that all non-neighboring vertices of j are removed from S.
Suppose, for the sake of contradiction, that at least one neighboring vertex j is removed in the exclusion for-loop, say i. As shown earlier, S 2 NN)), hence the conditions for Corollary 3.1 are satisfied. As we have also conditioned on A(s,, Ep), Corollary 3.1, which holds for any vhs yields
2 Pint(1 - Pint) A-mr))-1 Ev-
This inequality contradicts the exclusion criterion in Line 12 and thus i cannot be removed from S. Hence, neighboring vertex can be removed by the exclusion loop.
Finally, we know by Lemma 3.2 and A(Ev, En) that if N(),, then
D Sev.
We have assumed that E, < Pinr(1 Pint) A-12)-1/2
/2. Hence.
Daln S Pmn Plar) Epr
and so any non-neighboring vertex gets removed.
Thus, after the exclusion for-loop, we have = N()) and the algorithm correctly learns the neighborhood of j. Since the outer for-loop iterates over all vertices in V, conditioned on A, which occurs with probability at least 1 - C. the algorithm learss the neighborhood of every vertex in V correctly.
D.4. Vaccination Results
1. EXTINCTION TIME OF DISCRETE SIS PROCESS
In this section, we state and prove results relating the extinction time of a discrete SIS process to the spectral radius of the underlying graph. This result was first empirically established by Wang et al. (2003), and formally stated and proven for the discrete-time SIS model as defined Section 2 by Ruhi al. (2016).
Lemma D.5. Given a discrete SIS model with initial infection probability Pintt infection probability Pust recovery probability Prec. and spreading on graph & with n vertices and adjacency matrix A, we have that the expected number of infected vertices time t, denoted by E. ['),
] is upper bounded by Poate (1 Prec + Poop( (A)) n.
27

---

Structure Learning and Vaccination for Epidemic Control
Proof. Denoting the infection probability of vertex at time t + 1 by ((+1) = PP (x((+2) (x(+t))=1) =1),
we have
1(+1)= Pi
Prec) p. + B(Y))EN
(1-Pat Punt x2(1)) (1- (1-1f²)
(8)
JEN(()
where the first term of the sum the probability of staying infected, and the second term is the probability of getting infected. We then bound the product term by using the union bound get
II
(1- Pinf v((!))
Σ
X
Pint
JEN(()
(EN((()
Σ
Pint E
[
SEN()
Σ JEN(()
(1)
Pint Pj
Substituting this into Equation (8), we get
Pi s (1
((+1) Pree) pi + Pinf
Σ
Dj (2)
(1
(1- (1-p:-) (00).
JEN(()
Since 0 s (1 -pppp) p(0) S further bound the expression by:
pj (++1) < (1 Pree) Pj
(t) Pmn
Σ D
JEN(1)
Now, let p' = [pi, .g. [ represent the vector of infection probabilities at time f. The above inequality can be written in matrix form as
p²+1_ s (1 Prec) p + Pint Ap"
[[11 Pree 1 Pint p'
=Mp',
where I is the x n identity matrix and M = (1 - Prec) I + PintA is the transition matrix. Then, by recursively applying the inequality, we obtain
p' S M'p"
where pd the initial infection probability vector, given by pd Piintts Pinits ... Pinit) T. The spectral radius of matrix M, denoted by pMM), is given by:
(MM (1 Pree) + Pintp(A).
where p(A) is the spectral radius of the adjacency matrix A. Now. we can write the expected number of infected vertices at time as
E[7*]
B[Y
Σ p
1=1
l|p'll
s Vrlllp'l2
28

---

Structure Learning and Vaccination for Epidemic Control
where the last inequality follows from the Cauchy-Schwarz inequality. expression, we obtain
Substituting the bound on p' into the above
E|Z M''lMM''ll
S (n) |p'1l
where the last inequality follows from M being a symmetric matrix. Simplifying further and substituting in the value of P(M), we obtain B[Z²] v (1 - -Prec + Pintp( ThPinit, as desired.
Theorem 4.1. The expected extinction time E|T] is upper bounded by Ollog n) if P()) < Proc Pinf-
Proof. We first define t' := arginf,, inf, (El Σ 1/n} as the first round t such that E[Z"] S 1/n. Then, using the upper bound from Lemma D.5, and assuming that ((A) < Pree/Puuts we have that = [- log log() then
E B|Z") S p(M) rePinit S 1/n. Then, we can write the expected extinction time as
B|T] =
11 2 11
[=1
8
P(Z'21)
Σ P(' 2 21) + 2(1'21)
1=1
(=
st'
Σ P
t=
Now, we will show that the second term in the above expression goes zero asymptotically and we will be done. To do so, we will apply Markov's inequality and Lemma D.5 to obtain
Σ
(z' 2 1)
<
BiZ"|
t=
1=
PMn))((M))' n.
t= +1
Using the definition of f', we have that
Σ P (z'
> 1) 1
pl (M) 1¹ +k
(Pmmp((M) m) p(M))*
P(M)* &
P(M)
1 p(M)
where in the last line have used the fact that (p(M) < 1. Finally, we have that the expected extinction time is upper bounded by
log(pmin?))
1 ((M)
E
log(p(M)
n p(M)
Olog
29

---

Structure Learning and Vaccination for Epidemic Control
D.4.2. OPTIMALITY OF ALGORITHM 2
Here, we state and prove the optimality of Algorithm 2.
Theorem D.1. Given a graph G and vaccination budget K, let = p(g[V \ R²)), where R is the solution to the optimization problem given in Equation (I), and let X - p(g[V \ Re]), where Re the oulput of Algorithm 2 with precision parameter Then, X* d=l S
Proof. Proof follows from the correctness and completeness of Algorithm 3, stated and proven below.
Throughout the rest of the subsection, let G be undirected graph with nice tree decomposition 9 =(T, =T.,(xihevr)
K' E Z+ the vaccination budget, and À E IR+ the desired spectral radius threshold. Assume that Algorithm 3 is run with input G, J, K, and A.
Claim D.1 (Correctness of Algorithm 3). Algorithm 3 returns True and identifies set R of vertices to vaccinate, then
[R] < K and p(G(V R?) < X.
Proof. Assume that Algorithm 3 returns True with a set R. We will prove the correctness of the algorithm by proving the correctness of DP S,c] for each node type using induction i.e., we will prove that if DP o 0, then all R E DP(1, S,c] satisfy simultancously (i) R| = c, (ii) n R and (iii p( R) = A.
For the base case, notice that DP c 0 for all E V(T). S S X,, and 0 S c S K, so the hypothesis is trivially satisfied. Then, for the induction step, notice that the algorithm iterates through the tree's nodes in post-order and visits children before the parent. Thus, for each node we assume the correctness of its children's 's DP values (induction hypothesis). We will now prove the correctness of the node t, based on its type.
Leaf node. For a leaf node f, note that V2 = 0, and the algorithm sets the only It in DP 0, 0] as 0, which trivially satisfies (i) (ii), and (iii).
Introduce node. For an introduce node f with child node t', we have X, = Xy Uf) for some e E V(g). For all S S X, and S esa. K,
If v & S, then the algorithm sets DP S. c] = ( R' DPE 1]}. Thus, for any (2) = R e DP S, c). we have R
= R + 1= c and Sn (S (S = so (i) and (ïi) are satisfied. For (iii), notice that V. {o] Vr, so V R)) (( \ R() S X by the induction hypothesis.
If v E S, then the algorithm sets DP S,c] c| = (R' e DP \\ (u),c): P(G[V \ RR) < A}. Therefore, (iii) is satisfied by definition, and (i) and (ii) are satisfied by the induction hypothesis (|R' = c and Sn = 0).
Forget node. For a forget node i with child node f', we have X, = X₂ {w} for some w E (G)). Thus, V = Vv. For all S S X2 and 0 & c S K, the algorithm sets DP S, d = DP S. c] U DP SU (w),c] Let R E DPft. S.c.
If R DP[L', , S, c]. then |R| c, S R 0. and p([V \ R)) = p([V R)) À by the induction hypothesis.
If R E DP[L', S (w), c). then [Rt] = c and p( \ R)) < by the induction hypothesis, so (i) and (iii) are satisfied.
For (ii), notice that (SU (w)) R 0. by the induction hypothesis, implying S R
Join node. algorithm sets
For a join node t with child nodes t and t2, we have X, = Xx, X,,, For all S S X, and 0 s c S K, the
5,ct
0S0.02 Rí E D, R2 E DP|12, JR U R2l = p(G[V \ (R) U Ra)) < A }
Ri U R2
Conditions (i) and (iii) are satisfied by definition. Condition (ii) is also satisfied as Sn R₁ = S R = 0 by the induction hypothesis.
30

---

Structure Learning and Vaccination for Epidemic Control
We have shown that assuming the correctness node U's children's DP values, the correctness of l's DP values follows. This, combined with the base case, establishes the correctness of the algorithm through induction.
Claim D.2 (Completeness of Algorithm 3). If there exists set R' S (G) with [R'] S K such that ((G[V(() \ RT) S X then Algorithm 3 will return True along with set R C V with R S K such that p(G[V(G) \ RJ) S X.
Proof. Let R S (g) be any set of vertices with |R| s K for which (( \ R) I X. We show by (bottom-up) induction on the nodes of the tree decomposition T that R is recorded in the table DP|- ".. In particular, we will prove that for every node t E VT)),
R₁ RRRV V belongs DP (V R), [R.]].
Since X₁ n R = 0 is equivalent to X, n (V()) \ R) X,, we define the 'preserved set' S. == X, R so that RS never intersects S. As before, Vú denotes the union of all bags in the subtree of T rooted at t.
Base Case (Leaf node). If t is a leaf node, then Xx = and V = 0. Thus Rg = An 0 = 0. The algorithm sets DPft, 0,0] = {0} (and DPft, S, c] = otherwise). Clearly, R₂ = @ is indeed recorded in DPft, 0.
Induction Hypothesis.
Assume that for every child t' of t, Ry DP Sy, [Ryl] where Sy = Xe R. We now prove that R, DP(t, S,, Rell.
Introduce node. Suppose t is an introduce node with child I', and let v be the vertex introduced at so X, = X U {n). There are two cases:
Case 1: v E R. Then R₂ Re U {u} and S. = Se (since SD) By induction, we know Ry E DP(t', Sy. |Ry []. Because E Re, the DP update rule places Rg into DP(t, St, [Ra]] as R2 U (v).
Case 2: $ R. Then R₂ = Ry and S: = St. U {v). By induction, R E DPit', Sp Ub), [R The DP update rule copies Ry directly into (P S., [Re]] (and also checks p( \ R.]) S X, which holds by assumption).
Forget node. Suppose t is forget node with child t', and let be the vertex forgotten at t. so Xt Xx {w) and V, = Vg, We again have two cases:
Case I: w E R. Then R2 Ry and S. Sp \ [w]. By induction, Re E DP((', Se, [Rrl]. The DP update rule ensures Re appears in DPft, St, Rel]]
Case 2: w $ R. Then R2 = Rs and S. = Sy., By induction, Rg. E DP(L', Sv,, [Rel]. Again, Ry is copied into
DP(t, St, [Re]]-
Join node. Suppose t is join node with two children t and 12, where X, = X,, X12- Observe that R. = Re, U Re, and S. St, = St, By the induction hypothesis,
Re, E DP Sa,, [R and Re, E DP(t2, Sty, [Real].
The join node's DP rule unites these sets whenever they align on the same St and total size |Ral = |R,,1 R S K. By our feasibility assumption, VV \ (Re, RR,))) S X, so R, placed DP(r, St, [Re]].
We have shown that whenever the children of node have valid DP entries, the node will also have valid DP entry. Thus, by induction, the solution R' is recorded in the root node's DP table, and the algorithm returns True. More specifically, at the root node we have R E DP(r, 0, c] for some 0 < c < K. Therefore, DP(r, 0, c] * 0, which guarantees Algorithm 3 detects a feasible solution.
D.4.3. TIME COMPLEXITY OF ALGORITHM 2
Theorem 4.2. Given an input graph G with treewidth tw(g) S w, budget K, and precision e, Algorithm 2 has a worst-case time complexity of O (n. (01) (01))0(()) log(A/))).
Proof. The complexity arises from the binary search, building the DP table, node and spectral radius computation, each of which we analyze below.
31

---

Structure Learning and Vaccination for Epidemic Control
Binary search. The binary search is done on [0, A] and runs until high low E, thus taking Ologg( (A/))) time.
DP table. The DP table is indexed by t E V(T). S S X,, and c E , The number of nodes in the tree decomposition is upper bounded by (wn)) by Lemma C.1. Then, as size of each bag X2 is at most w + 1 by the definition of treewidth (see Appendix C), have that the total number of subsets is upper bounded by O(2++1). Thus, the total number of entries in the DP table is Owwn2*+1K)
Note that although the DP table is described in Section 4.2 as storing all feasible solutions per (t, S, c) tripict, this is not necessary. We only need to retain a representative solution for each state, and in particular only before a join node is reached in the post-order. other words, once a join node has been processed, it suffices to only keep one solution per tripler. This how we avoid (x) factor in the complexity. We still need to perform a search over K2 many values at each node join node, but this only adds (K32) factor to the complexity.
Spectral radius. The spectral radius computation complexity is at most Onn²) using the Lanczos algorithm for sparse graphs with O(n) nonzero entries (Cullum & Donath, 1974).
Combining the above, we have that the total time complexity is O
D.4.4. OPTIMALITY OF ALGORITHM 5
Here, we prove the optimality of Algorithm 5, which follows directly from the correctness and completeness of Algorithm 6, proven below.
Throughout the rest of this subsection, let T (V, E) be undirected tree, K Z the vaccination budget, and À R the desired spectral radius threshold. Assume that Algorithm 6 is run with input T', K, and X. Without loss of generality, order the vertices in the tree T by picking a random root and ordering the other vertices accordingly.
Lastly, define C(T) as the set of connected components of T, where T is a forest, and define a minimal offending subtree as a connected subtree& S C V where p(T(S) > A and for any proper connected subtree S' C S. p(T(S") S X.
Claim D.3 (Correctness). If Algorithm 6 returns True and identifies a set R of vertices to remove, then [R| S k and after removing R. from the tree T, p(T(V \ R)) S.
Proof. Assume that Algorithm 6 returns True with set R. First, observe that [R] S k. due to the if clause in line 6. Then, notice that the algorithm performs a post-order depth- first traversal of the tree. At each vertex u, it attempts to merge all child subtrees with u.
If the spectral radius (T[S)) S X, the subtree remains connected, and no cut is made. Otherwise, the algorithm adds u to R. effectively removing from its parent by not including u in the merged subtree, ensuring that the offending subtree rooted at does not propagate upwards.
Since the traversal is post-order, all descendants of any vertex have been processed before u itself. Therefore, when an offending subtree is detected at u, none of its descendants have subtrees with spectral radius larger than X. Consequently, when the final vertex in the post-order is reached, all subtrees rooted at all other vertices satisfy the spectral radius threshold.
Thus, after Algorithm 6 terminates, we have that for all connected components (i.e., subtrees) after removal of vertices in R, E C(T(V) \ R)), p(T[S) S X. Then, the desired claim follows from applying the equality relating the spectral radius of a graph to the maximum of the spectral radii of its connected components: P(T[V \ R)) maxsectriv (n)) ((T[S)) (Van Mieghem al., 2011).
Claim D.4 (Completeness). If there exists a set R' C V with |R' S K such that ((T(V) RR) S X, then Algorithm 6 will return True along with a set R C V with R < K such that &
Proof. Assume, for contradiction, that there exists a feasible solution R' with [R'| < K such that P(T[V Rt)) S X, but Algorithm 6 returns False, implying R > K, where R is the set constructed by Algorithm 6.
When the algorithm processes the tree in oodtr, it identifies and removes the root of each minimal offending subtree. Moreover, following each removal of a subtree root, that subtree is never visited again by the algorithm. Thus, each element of corresponds to removing exactly one vertex from a distinct minimal offending subtree.
32

---

Structure Learning and Vaccination for Epidemic Control
Now if [R] > K, this implies that there are more than K distinct minimal offending subtrees in T. However, since each such subtree requires least vertex removal and R' I K, it is impossible to cover all offending subtrees with K
removals. This is a contradiction and thus Algorithm 6 must return True, establishing the optimality of the algorithm. 0
33


Reviews:
[{"review_id": "KuNHyBhkNh", "reviewer": "Reviewer_Gdj4", "summary": "This paper is broadly about vaccinating the nodes of a network over time (subject to a total budget on the number of vaccinations) in order to minimize the expected extinction time of the epidemic. The SIS model is assumed, and interestingly, the network is not assumed to be known, but has to be learned. (SIS is a reasonable model where individuals can get infected repeatedly, such as with cholera.) The paper thus splits the task into two parts: (a) learning the network, and (b) vaccination. Theoretical results and experimental evidence are given.\n\n## update after rebuttal: I have increased my score to \"Weak Accept\" given the rebuttals.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review and their insightful questions. We respond to each of them in detail below.\n\n### Q1\nWe propose three vaccination strategies, all of which solve the Spectral Radius Minimization (SRM) problem:\n\n(1) An optimal polynomial-time algorithm for trees (Appendix B, Algorithm 5).\n\n(2) An optimal (DP) algorithm that solves SRM on arbitrary graphs (Section 4.2, Algorithm 2), with polynomial runtime on graphs of bounded treewidth.\n\n(3) A greedy polynomial-time heuristic (Section 4.3, Algorithm 4).\n\nThe abstract refers to the second method. By “optimal,” we mean that it exactly solves the SRM problem: given a budget $K$, it finds a subset of vertices of size $\\leq K$ whose removal minimizes the spectral radius. This is stated and proven in Theorem D.1.\n\n### Q2\nThe VUG problem is formulated as an online problem: the agent observes the infection states over time and must decide when and whom to vaccinate, subject to a global budget $K$ (Section 2). In particular, the agent is not required to vaccinate all $K$ nodes at once.\n\nThat said, our proposed method instantiates this framework in an offline fashion: we collect $T_D$ rounds of observations, learn the graph using SISLearn, and then vaccinate all $K$ nodes at time $t = T_D + 1$. This choice reflects that, assuming the graph is learned perfectly, vaccinating all at once is optimal for minimizing extinction time.\n\nExploring *adaptive* or *staggered* vaccination—where the agent begins intervening while still learning—is a compelling direction for future work.\n\n### Q3\nThis assumption is not essential for our approach or theoretical results. All our lemmas, theorems, and algorithmic results hold under different initial infection states, whether they involve a single infected vertex, an arbitrary deterministic or probabilistic subset, or any other initial configuration. We adopted the standard uniform-seed initialization solely because it is common in the SIS literature.\n\n### Q4\nThe only disease parameter SISLearn requires is the infection probability, $p_\\text{inf}$, which can be estimated from observational data, like done in Kirkeby et al. (2017) via a mean-field approximation. Importantly, SISLearn is robust to parameter misspecification, as evident by new experiments where the true infection probability was 0.3 but the input was set to 0.7, and SISLearn still achieved an F1 score of 0.80 (compared to 0.97 with the correct value). These new experiments are shown in new Figure 4 (see linked file below).\n\n### Q5\nWhile real-world social networks may not exhibit small treewidth, our work addresses this directly: our DP algorithm is ideal for graphs with small to moderate treewidth (e.g., up to ~10-20; see new Figure 1, and our response to Reviewer WHtL), while our fast and scalable greedy heuristic (Algorithm 4) performs well on general graphs—including those with high density (see new Figure 2).\n\n### Q6\nOur assumption of stationarity arises naturally from well-established theoretical results for SIS-type processes. It has been shown that if the infection parameters are above the epidemic threshold $\\rho(\\mathcal{G}) \\geq p_{\\text{rec}}/p_{\\text{inf}}$, the process may reach a meta-stable distribution, resembling a stationary distribution (see, among others, Schonmann 1985, Liggett 1999, and Mountford et al. 2013). Conversely, if the threshold condition is not satisfied, the infection dies out rapidly, trivially resolving the vaccination problem.\n\nMore formally, following the coupling argument of Cator and Van Mieghem (2013), the SIS process can be related to a modified Markov chain that excludes the absorbing all-zero state. This modified chain is ergodic and therefore has a proper stationary distribution. Thus, until extinction occurs, the original SIS process behaves like an ergodic Markov chain with a stationary distribution.\n\nIn other words, either the SIS process (quickly) reaches a meta-stable state where our assumption holds, or it dies out. The former is backed up by new experiments, given in new Figure 3, where the SIS process reached the meta-stable state in an average of 100 rounds.\n\nThus, the stationarity assumption, while seemingly strong, is both theoretically well-founded and empirically justified.\n\n### New figures: https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn\n### References\n\nKirkeby C, et al. Methods for estimating disease transmission rates: Evaluating the precision of Poisson regression and two novel methods. *Sci Rep*. 2017.\n\nCator E, et al. Susceptible-infected-susceptible epidemics on the complete graph and the star graph: Exact analysis. *Phys Rev E*. 2013.\n\nLiggett TM. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. *Springer*. 1999.\n\nMountford T, et al. Metastable densities for the contact process on power law random graphs. *Electronic Journal of Probability*. 2013.\n\nSchonmann RH. Metastability for the contact process. *J Stat Phys*. 1985.", "claims_and_evidence": "I find the following claims problematic/unclear: I ask the authors to clearly explain these.\n\n1. In what sense is the algorithm \"optimal\" as claimed in the abstract? If it is in the sense of \"if the underlying graph is a tree\" as in Appendix B, this would be a very weak claim as trees are not at all natural models for disease/communication spread. \n\n2. I assume the algorithm is not \"online\" in the sense that for each t, given the infection states up to time t, we have to immediately decide the set R_t of nodes to vaccinate at time t? That is, we assume the \"offline\" case where all the Y^t (for 1 <= t <= T) are given upfront? If so, why do the vaccination in multiple stages at all? \n\n3. It does not seem a reasonable assumption to make that all nodes independently get infected with the same probability at time t = 0: how flexible can this be made? \n\n4. I assume the disease parameters are known to the algorithm?\n\n5. Give references in the literature to where social networks seem to have small treewidth. \n\n6. Please justify the stationarity assumption: it appears strong to me.", "methods_and_evaluation_criteria": "The methods appear reasonable.", "theoretical_claims": "I have asked the authors to justify the stationarity assumption.", "experimental_designs_or_analyses": "The experimental analysis appears adequate.", "relation_to_broader_scientific_literature": "The connections to the existing literature look adequate to me.", "essential_references_not_discussed": "N/A to my knowledge.", "other_strengths_and_weaknesses": "Learning the network appears like a good problem to me. The vaccination model parametrized by alpha also looks good and reasonable.", "other_comments_or_suggestions": "Say *expected* in the initial discussion on extinction time as well, as you have done in defining the VUG problem. \n\nThe paper is well-written in general. One typo: \"combines network learning with strategic vaccination strategy\" -->  \"combines network learning with a strategic vaccination strategy\"", "questions_for_authors": "Please respond in detail to my modeling/other questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ennYHo73eD", "reviewer": "Reviewer_Hjpv", "summary": "This paper studies the SIS model on an unknown graph. The process runs in discrete time. Any infected node becomes infected/susceptible in the next round with prescribed probabilities (independently of the rest of the graph). Any susceptible node can become infected from one of its infected neighbors. The goal is to vaccinate K individuals in a way to minimize the expected extinction time of the illness. When a vertex is vaccinated, the probability that it gets infected by a neighbor is decreased by a factor of $\\alpha$ for all future rounds. Given a sequence of infection observations in discrete time, the authors propose an algorithm which first learns the graph and then decides which vertices to vaccinate. The graph learning step uses an inclusion-exclusion approach, first learning a superset of each vertex's neighbor set, and then paring it down using conditional independence properties of the infection process. The vaccination step solves a surrogate problem, namely Spectral Radius Minimization. The problem is solved in polynomial time for graphs with bounded treewidth. Experiments on a real dataset are included, comparing the proposed approach to several baselines.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their careful reading and attention to detail. The reviewer is absolutely right—Lemma D.1, as originally stated, was incorrect and developed too hastily. We have corrected the result below by applying Theorem 1.2 from Kontorovich & Ramanan (2008). We also address the reviewer's other concerns below.\n\n### Lemma D.1 (Replacement)\n\nGiven observations $\\\\{Y^{(t)}\\\\}_{t \\in T_D}$ from the SIS process where $T_D$ are not necessarily consecutive time indices and $Y^{(t)} \\in\\\\{0,1\\\\}^V$, under Assumption 3.1, for any subset $U \\subseteq V$, any state $y_U \\in \\\\{0,1\\\\}^{|U|}$, and any positive $\\varepsilon$ and $\\delta$, we have the following deviation bound on the unbiased estimator\n$$\n\\mathbb{P}\\left(\\left| \\mathbb{P}(Y_U = y_U) - \\hat{\\mathbb{P}}(Y_U = y_U) \\right| \\geq \\varepsilon \\right) \\leq\\delta,\n$$\nwhenever $|T_D| \\geq \\frac{2\\log(2 / \\delta)}{\\varepsilon^2 (1-\\theta)^2}$, where $0 < \\theta < 1$ is a constant depending on the graph structure and model parameters.\nHere, $\\mathbb{P}(Y_U = y_U)$ is the marginal probability of the vertices in $U$ being described by state vector $y_U$ and $\\hat{\\mathbb{P}}(Y_U = y_U) = \\varphi_U$ is the empirical estimate over $T = |T_D|$ samples.\n\nProof: \nLet $\\mathcal{S}$ be the state space of our Markov chain, i.e., $\\mathcal{S} = \\\\{0,1\\\\}^V$,  $T = |T_D|$ the number of observations, and $\\\\mathcal{S}^T$ be the product state space of $T$ observations. By definition, the process $\\\\{Y^{(t)}\\\\}\\_{t \\in \\mathbb{N}} $ has the Markov property in time, hence so does a sub-sequence $\\\\{Y^{(t)}\\\\}\\_{t \\in T_D}$.\nWe define $\\varphi_U:\\mathcal{S}^T \\rightarrow \\mathbb{R}$ as:\n$$\n\\varphi_U(Y^1, \\dots, Y^T) = \\frac{1}{T} \\sum_{t=1}^{T} \\mathbb{1} \\\\{Y_U^{(t)} = y_U\\\\},\n$$\nwhere $ \\mathbb{1} \\\\{\\cdot\\\\}$ is the indicator function.\n\nNotice that this function is $1/T$-Lipschitz with respect to the Hamming metric $d(X,Y) = \\sum_{t=1}^T \\mathbb{1} \\\\{X^{(t)} \\neq Y^{(t)}\\\\}$ on $\\mathcal{S}^T$.\n\nWe apply Thm. 1.2 by Kontorovich & Ramanan (2008) for Markov chains, stating that for a $c$-Lipschitz function $\\varphi$ on $\\mathcal{S}^n$,\n$$\n\\mathbb{P}\\\\{|\\varphi-\\mathbb{E} \\varphi| \\geq t\\\\} \\leq 2 \\exp \\left(-\\frac{t^2}{2 n c^2 M_n^2}\\right).\n$$\nIn our case, the sequence length is $T$ (replacing $n$ in the theorem), $c=1/T$, $M_n$ becomes $M_T$, and $t$ becomes $\\varepsilon$. The bound then becomes\n$$\n\\mathbb{P}\\\\{|\\varphi_U-\\mathbb{E} \\varphi_U| \\geq \\varepsilon\\\\} \\leq 2 \\exp \\left(-\\frac{\\varepsilon^2}{2 T (1/T)^2 M_T^2}\\right) = 2 \\exp \\left(-\\frac{T \\varepsilon^2}{2 M_T^2}\\right),\n$$\nwhere $M_T = (1-\\theta^T)/(1- \\theta)$ and $\\theta$ is the Markov contraction coefficient given by\n$$\n\\theta = \\sup\\_{\\\\{Y^{\\prime}, Y^{\\prime \\prime} \\in \\mathcal{S} \\\\}} \\left\\\\|p\\left(\\cdot \\mid Y^{\\prime}\\right)-p\\left(\\cdot \\mid Y^{\\prime \\prime}\\right)\\right\\\\|_{\\mathrm{TV}}.\n$$\nWe have $\\theta <1$ since every configuration $Y$ can transfer into the all-zero configuration $\\underline{0}$. Hence, for any two states $Y^{\\prime}, Y^{\\prime \\prime} \\in \\mathcal{S}$ both $p(\\underline{0}|Y^{\\prime})>0$ and $p(\\underline{0}|Y^{\\prime \\prime})>0$ and the support of $p(\\cdot|Y^{\\prime})$ and $p(\\cdot|Y^{\\prime \\prime})$ is not disjoint which implies $\\theta <1$.\n\nTherefore, $M_T <1/(1-\\theta)$ and the probability bound becomes:\n$$\n\\mathbb{P}\\\\{|\\varphi_U-\\mathbb{E} \\varphi_U| \\geq \\varepsilon\\\\} < 2 \\exp\\left(-\\frac{T \\varepsilon^2 (1-\\theta)^2}{2}\\right).\n$$\n\nFinally, setting the RHS to be $\\leq \\delta$ and solving for $T$ we get\n$$\nT \\geq \\frac{2\\log(2 / \\delta)}{\\varepsilon^2 (1-\\theta)^2}. \\quad \\square\n$$\n\nWe emphasize that Lemma D.1 is not a central result of our paper. It is used solely to derive concentration bounds for estimating the direct and conditional influence quantities, thereby enabling our sample complexity analysis. Crucially, the correctness of the SISLearn algorithm itself is unaffected by this lemma. With the corrected bound, all downstream results remain valid (modulo minor constant adjustments), and in fact, Lemmas D.2–D.4 become cleaner, as we can eliminate the $1/m$ term in favor of a dependence on the (constant) Markov contraction coefficient $\\theta$, which depends on the graph structure and the infection parameters.\n\n### Regarding rounds\nThe real-world interpretation of a \"round\" depends on the application. It may correspond to seconds in financial or communication networks, or days in epidemiological settings. The time to reach stationarity similarly depends on the timescale of the underlying process.\n\n### Regarding graph recovery\n\nWe provide experimental results on the learning performance of SISLearn in App. A.2. We also performed new experiments on the robustness of SISLearn, given in new Fig. 4 [here](https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn) (see Q4 of Reviewer Gdj4).\n\n### References\n\nKontorovich L., Ramanan K. Concentration inequalities for dependent random variables via the martingale method. *The Annals of Probability*. 2008.", "claims_and_evidence": "Theorem 3.1 claims that under certain assumptions on the dataset (namely, the number of samples satisfying certain conditions, as well as a stationarity assumption), the inclusion-exclusion approach identifies the correct graph. Algorithm 2 provides a DP algorithm which runs in polynomial time (as long as the graph has bounded treewidth) and returns a set of K vertices whose deletion yields a graph with minimal spectral radius. The authors argue that solving this auxiliary problem is a good substitute for minimizing the expected extinction time.", "methods_and_evaluation_criteria": "The datasets and benchmarks are reasonable. Additional experiments are found in the supplementary material.\nI found it hard to interpret the number of rounds in real-world terms. What would 2000 rounds correspond to in real time? If that is e.g. 100 years, then I don't find the stationarity assumption justified, since reducing the number of rounds significantly degrades the performance of the proposed algorithm (Figure 2). \nAlso, since the first step in the algorithm is estimating the graph, there should be an empirical verification of graph recovery.", "theoretical_claims": "Lemma D.1 is false. Consider the case where 0 < p <= 1/2. Suppose that X_1 = 0 with probability 1/2 and X_1 = 2p with probability 1/2. Suppose all the X_i's are equal. Then $p = \\frac{1}{n} \\mathbb{E}[S_n]$. Set $\\epsilon = p/2$ and $\\delta < 1/2$. Then $\\mathbb{P}\\left(\\left| \\frac{1}{n} S_n - p \\right| \\geq \\epsilon + \\frac{1}{n} \\right) = \\frac{1}{2}$ for $n$ sufficiently large, contradicting the claim.\nTheorem 1.8 of Pelekis and Ramon (2017; arXiv version) is false with the same counterexample. The journal version appears to be missing the corresponding result.\n\n(Update below in light of rebuttal; score increased accordingly)", "experimental_designs_or_analyses": "(See above concerns about the number of timesteps and the missing verification of graph estimation)", "relation_to_broader_scientific_literature": "Epidemic modeling is a popular topic in network science. I am not aware of other results that require learning the network, so this is an interesting direction.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well-written.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qZnn7e5a0Q", "reviewer": "Reviewer_WHtL", "summary": "The paper tackles the critical challenge of minimizing disease extinction time in Susceptible-Infected-Susceptible (SIS) models under unknown contact networks. The authors propose a two-stage framework:\n\n- Network Inference: A novel inclusion-exclusion learning algorithm with provable sample complexity bounds\n- Vaccination Optimization: (i) Optimal dynamic programming for bounded tree width graphs, (ii) Efficient greedy heuristic for general graphs\n\nExperimental validation on real-world influenza outbreak data demonstrates superior performance over baseline methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment and their questions. We answer them below.\n\n### Adaptivity\nOur learning algorithm, SISLearn, relies on data drawn from the meta-stable distribution of the SIS process, where the probabilities of configurations do not change anymore. However, it can accommodate time-varying infection probabilities, provided the changes are infrequent enough for the system to reach a new meta-stable state between shifts. As shown in Figure 3 of our additional experiments [here](https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn) (also see our response to Q6 of Reviewer Gdj4), the meta-stable state is reached in as few as 50 time steps depending on the SIS parameters.\n\nImportantly, since SISLearn sequentially learns each node’s neighborhood independently, even if the infection parameters shift mid-process, it suffices to re-estimate the new infection probabilities and allow the process to reach the new meta-stable state. Under these conditions, the theoretical guarantees would hold with minor changes. It should be noted that in practice, SISLearn performs well even without waiting for full stabilization. All experiments (main paper and appendix) use observations starting from the first round, and the algorithm still achieves high learning performance (see experiments in Appendix A.2).\n\nMoreover, SISLearn is robust to parameter misspecification. It only requires an estimate of the infection probability, and even if this input is significantly incorrect, the algorithm performs well in practice. In new experiments where the true infection probability was 0.3 but the input was set to 0.7, SISLearn still achieved an F1 score of 0.80 (compared to 0.97 with the correct value), showing graceful degradation under substantial misspecification. These new experiments are shown in Figure 4 [here](https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn).\n\n### Computational feasibility\nWe conducted two additional experiments to explicitly evaluate the computational feasibility of our DP algorithm. First, we measured runtime on graphs with fixed treewidth $\\omega = 10$ and increasing number of vertices (up to $n=2000$); results provided in Figure 1 [here](https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn). These confirm that DP scales cubically in $n$, consistent with our theoretical analysis (Section D.3.3), and remains practical even for graphs with as many as $2000$ vertices!\n\nSecond, we analyzed runtime on random Erdős–Rényi graphs with varying $n$ and naturally increasing treewidth; results provided in Figure 2 [here](https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn). This experiment highlights that while DP runtime grows exponentially with increasing treewidth, our proposed heuristic (Algorithm 4) remains computationally efficient (scaling cubically as shown in Section 4.3) and achieves vaccination performance close to DP, as demonstrated in Section 5.\n\nThus, in practice, for graphs with known small-to-moderate treewidth ($\\omega \\lesssim 20$), the DP method is recommended even for large graphs. Otherwise, the greedy heuristic is an effective and scalable alternative, offering near-optimal performance with significantly lower runtime.\n\n### Regarding GNNs\nWhile GNNs have shown success in epidemic modeling (Liu, 2024), to the best of our knowledge, no existing work directly employs GNNs for learning or vaccination strategies in SIS models. Developing such a GNN-based baseline would itself constitute a substantial research effort beyond a simple baseline comparison. However, if the reviewer is aware of specific GNN-based approaches applicable to our setting, we would gladly include them in our evaluation.\n\n\n**Link to new figures: https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn**\n\n### References\nLiu Z, Wan G, Prakash BA, Lau MSY, Jin W. A Review of Graph Neural Networks in Epidemic Modeling. *Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.* KDD ’24.", "claims_and_evidence": "•\tTheoretical Foundations:\n- Formal proofs for structure learning guarantees (Theorem 3.1)\n- Spectral radius-extinction time relationship analysis (Theorem 4.1)\n- Time complexity analysis of vaccination algorithms (Theorem 4.2)\n\n•\tEmpirical Validation:\n- Consistent outperformance on Beijing influenza transmission networks\n- Robustness tests with varying observation data sizes\n- Statistical significance analysis through confidence intervals", "methods_and_evaluation_criteria": "•\tProposed Methodology:\n- Structure Learning: Leverages infection state correlations via inclusion-exclusion principle\n- Vaccination Strategies: (1) Dynamic programming using tree decomposition (bounded treewidth) (2) Greedy vertex removal guided by spectral impact (general graphs)\n\n•\tEvaluation Framework:\n- Dataset: Augmented OutbreakTrees network with probabilistic edges\n- Metrics: Infection proportion dynamics, spectral radius reduction\n- Baselines: Comparative analysis against degree/random vaccination strategies", "theoretical_claims": "Key theoretical contributions:\n- Theorem 3.1: Establishes polynomial sample complexity for graph recovery\n- Theorem 4.1: Proves spectral radius directly impacts epidemic extinction time\n- Theorem 4.2: Demonstrates time complexity in treewidth size\n- Proofs employ established techniques from spectral graph theory and Markov processes, with detailed derivations in supplementary materials.", "experimental_designs_or_analyses": "Experimental Setup:\n- Simulated SIS dynamics on Beijing influenza contact network (2009)\n- Parameters calibrated to real-world transmission rates\n- Simulation on vaccination strategy\n\nKey Findings:\n- Proposed method reduces infection prevalence compared to degree centrality vaccination\n- Spectral radius reduction with only a low amount of node vaccination\n- Maintains performance stability across observation data sizes", "relation_to_broader_scientific_literature": "This work innovatively bridges two research domains:\n- Extends Ising model techniques to SIS dynamics\n- Epidemic Control: Advances spectral radius minimization (SRM) approaches by removing prior structural knowledge requirements\n- Distinct from existing SRM literature that assumes known networks, this study addresses realistic partial observation scenarios.", "essential_references_not_discussed": "While comprehensive, the paper could engage with Graph neural networks for epidemic modeling (e.g., GraphSAGE)", "other_strengths_and_weaknesses": "- Model Extensions: Incorporate SIR or SEIR dynamics and heterogeneous vaccination effects\n- Algorithm Enhancement: Explore graph neural networks for large-scale networks\n- Practical Considerations: Address implementation constraints (e.g., phased vaccination)", "other_comments_or_suggestions": "NA", "questions_for_authors": "- How does SIS Learn perform when infection vary over time? Could adaptively improve robustness to such changes?\n- For graphs with tree width ω = 10 and size n = 1000, does the DP approach remain computationally feasible? What are the practical runtime limits?\n- Given the success of graph neural networks (GNNs) in intervention strategies, why were they not included as baselines? Were there computational or methodological constraints?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JHEBHtoIyn", "reviewer": "Reviewer_kFRe", "summary": "The paper studies an important problem of picking nodes to vaccinate in a network,\nassuming an SIS model of epidemic spread. The authors assume the network is not known,\nand needs to be learned. This is an interesting extension, since most prior work assumes\nthe network is known. The authors present an algorithm for optimal vaccination set\nwhen the network has bounded treewidth. In their experiments, they use another algorithm\nwhich greedily reduces the spectral radius the most in each step. The authors show\ntheir algorithms have slightly better performance compared to many other baselines.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and thoughtful comments. We address each of the points raised below and will clarify them in the revised manuscript.\n\n### Stationarity\nWe refer the reviewer to our response to Q6 of Reviewer Gdj4 for a more detailed response. In short, either the process dies out quickly, in which case vaccination is unnecessary, or it enters a meta-stable regime where it behaves like a Markov chain with a stationary distribution, justifying Assumption 3.1.\n\n### Comparison with the SIR model and sample complexity\nWe thank the reviewer for this observation. Prior work on SIR-based structure learning relies on observing multiple independent cascades, such as Gomez-Rodriguez et al. 2012, since in SIR models each node can be infected at most once. As a result, interactions between nodes are limited within each cascade, and restarting the process is necessary to collect sufficient signal.\n\nIn contrast, the SIS model permits reinfection, enabling a single persistent cascade to generate rich temporal correlations over time. Our learning algorithm leverages this property and thus does not require multiple independent cascades. Consequently, our sample complexity guarantees given in Theorem 3.1 are expressed in terms of the number of times specific infection patterns (e.g., $I(Y_j = 0, Y_i = 1, Y_S = y_S)$) appear in the data, rather than the number of cascades. \n\nEmpirically, as shown in Figure 3 (Appendix A.2), SISLearn achieves an F1 score of 0.80 with just 400 rounds of observation, demonstrating strong learning performance.\n\n### Observation of edges vs infection states\nWe agree that combining partial edge and infection information is a realistic and important direction. We note that the setting of unknown edges but observed infection states is standard in prior work on SIR-based structure learning, like Gomez-Rodriguez et al., 2012 or Netrapalli & Sanghavi, 2012, which motivates exploring the analogous setup in the SIS setting.\n\nThat said, our approach is highly flexible. Since SISLearn learns the neighborhood of each vertex independently, it can easily incorporate partial edge knowledge. Similarly, it can tolerate missing infection data: as long as some infection history is observed for every vertex and pairs of consecutive observations (e.g., at times $t$ and $\\(t{+}1\\)$) are available, the algorithm remains effective, though naturally requiring more samples.\n\n### Specific parameters\nWe emphasize that our parameter choices were guided by the goal of evaluating non-trivial regimes of the SIS model—where vaccinations are both necessary and impactful. If the infection-to-recovery ratio is too low, the disease naturally dies out without intervention, making vaccination redundant. If it is too high, the process becomes effectively unstoppable without unrealistic levels of vaccination. The intermediate regime is where extinction dynamics are sensitive to targeted interventions—precisely the setting where intelligent strategies matter.\n\nTo demonstrate robustness beyond this regime, we conducted additional experiments on both low (Figure 5) and high (Figure 6) infection-to-recovery ratios; results are provided [here](https://drive.proton.me/urls/5N1PC0M6ZW#oCweKFODmBNn). As can be observed, our combined learning-and-vaccination approach still outperforms the other baselines. If the reviewer has a specific parameter regime in mind, we would be glad to run additional experiments.\n\n### Tree width of inferred networks\nThe China flu graphs (Sec. 5) and USA flu graphs (App. A) have treewidths of 8 and 58, respectively, computed exactly using the state-of-the-art treewidth solver from the PACE 2017 competition (Tamaki, 2019). For graphs with large treewidth (tw > 20), our proposed Greedy algorithm is preferable due to its polynomial-in-n complexity, making it significantly more efficient. Please also see our answer to the computational feasibility comment of Reviewer WHtL, where we discuss new experiments (new Figures 1 & 2).\n\n### Usage of data & observation horizon\nUnlike SIR-based inference methods that rely on multiple independent cascades, SISLearn uses infection data from a single, ongoing epidemic, needing only the infection states of the vertices over time—even this can be relaxed, as discussed above. While our theoretical guarantees require that the process has reached meta-stability, we show in Appendix A.2 that SISLearn achieves an F1 score of 0.80 with just 400 rounds of data, without needing to wait for meta-stability to be reached.\n\n### References\n\nGomez-Rodriguez M, Leskovec J, Krause A. Inferring Networks of Diffusion and Influence. *ACM Trans Knowl Discov Data*. 2012.\n\nNetrapalli P, Sanghavi S. Learning the graph of epidemic cascades. *SIGMETRICS Perform Eval Rev*. 2012.\n\nTamaki H. Positive-instance driven dynamic programming for treewidth. *J Comb Optim*. 2019.", "claims_and_evidence": "Seem ok", "methods_and_evaluation_criteria": "While it is ok to assume a meta-stable state, as in (Van De Bovenkamp & Van Mieghem, 2014),\nI am not sure it justifies the stationary distribution of the form stated in section 3.2,\nfrom which the authors are making assumption 3.1. This needs more discussion, and the response doesn't seem adequate. The graphs learned can have large treewidth, and the greedy algorithm is needed to ensure poly time", "theoretical_claims": "Seem ok, but haven't verified all the proofs in the appendix", "experimental_designs_or_analyses": "Seem ok. Prior work on network construction using SIR model gives bounds on\nthe sample complexity. The authors mention Theorem 3.1 bounds the sample complexity.\nThat is not clear, and it is not clear how this is done in the experiments.", "relation_to_broader_scientific_literature": "Prior work on vaccination strategies has assumed the network is known. So the setup here\nis interesting, though it is not clear how practical this is. It is assumed that all\ninfections are detected, but edges are not known. In practice (as during COVID), infection\nstates seem just as sensitive (or maybe more). So maybe a more realistic combination of\nobservations of edges and infection states is realistic", "essential_references_not_discussed": "Some others on network inference, e.g., (Abrahao et al., Trace Complexity of Network Inference,\n2013), and for characterization of the SIS model, e.g., (Ganesh et al., INFOCOM 2005)", "other_strengths_and_weaknesses": "The setup is interesting, since networks are not fully known. The results are promising.\n\nHowever, the seems limiting that the results are shown for very specific parameters.\nSo not sure how this works for the broader parameter regime.\n\nThe DP algorithm only works for treewidth bounded networks. What is the bound on the\ntreewidth of the inferred networks? The authors would need another step for finding the\ntreewidth, which can only be approximated.\n\nHow data is used in the network inference step is not very clear, unlike the other\nnetwork inference problems. Do you need to keep observing the infection states for\na long time?\n\nFinally, as mentioned above, assuming infection states are fully observed but not the edges doesn't seem any more realistic or practical, and needs better motivation", "other_comments_or_suggestions": "Please see above", "questions_for_authors": "Please address the weaknesses mentioned above:\n-- results are shown for very specific parameters, performance in other regimes\n-- treewidth of inferred network. Can it be large? If so, how will the DP algorithm be used?\n-- how long do you need to observe, sample complexity\n-- model of observation of infection states", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper is broadly about vaccinating the nodes of a network over time (subject to a total budget on the number of vaccinations) in order to minimize the expected extinction time of the epidemic. The Susceptible-Infected-Susceptible (SIS) model is assumed, and the network is not assumed to be known, but has to be learned. (SIS is a reasonable model where individuals can get infected repeatedly, such as with cholera.) The paper thus splits the task into two parts: (a) learning the network, and (b) vaccination. Theoretical results and experimental evidence are given.

Inferring the network is a nice and practical problem. 

The Spectral Radius Minimization (SRM) problem is NP-hard in general: the paper shows that it can be solved in polynomial time on networks with a bounded treewidth (the paper also suggests an alternative greedy heuristic in practice when the treewidth exceeds 20, say). While this is a reasonable theoretical contribution, several NP-hard graph problems become tractable when the treewidth is held constant---and hence I would not rate this as a primary major contribution of the paper. 

The authors say in a rebuttal “Either the process dies out quickly, in which case vaccination is unnecessary, or it enters a meta-stable regime where it behaves like a Markov chain with a stationary distribution, justifying Assumption 3.1.” While this seems reasonable, a meta-stability assumption seems very strong: e.g., what if the time to meta-stability is very long (e.g., if the dynamics don’t have a reasonable mixing time)? Parametrizing perhaps by time to reach a meta-stable regime will make the setting more realistic.
Decision: Accept (poster)