# Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control

arXiv: https://arxiv.org/abs/2506.15397 · HTML: https://mlsanity.com/paper/2506.15397/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 38 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 8 of 8)

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Analysis and Control of Epidemics: A survey of spreading processes on complex networks](https://mlsanity.com/paper/1505.00768/) (2015)
- [Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread](https://mlsanity.com/paper/1501.06614/) (2015)
- [Bayesian inference of network structure from information cascades](https://mlsanity.com/paper/1908.03318/) (2019)
- [Positive-instance driven dynamic programming for treewidth](https://mlsanity.com/paper/1704.05286/) (2017)
- [Optimal Deployment of Resources for Maximizing Impact in Spreading Processes](https://mlsanity.com/paper/1608.08278/) (2016)
- [An efficient curing policy for epidemics on graphs](https://mlsanity.com/paper/1407.2241/) (2014)
- [Improved Bounds on the Epidemic Threshold of Exact SIS Models on Complex Networks](https://mlsanity.com/paper/1603.05095/) (2016)

## Abstract (arXiv)

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.