Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control
Sepehr Elahi, Paula Mürmann, Patrick Thiran · 2025
Read Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control by Sepehr Elahi, Paula Mürmann, Patrick Thiran (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-15397.txt.
Introduction
Sepehr Elahi, Paula Murmann, and Patrick Thiran wrote a 2025 paper on vaccination when the contact graph is unknown. A standard spread model tracks how a non immunizing disease moves on a graph. The best vaccine plan ties to a hard spectral problem, but past work assumed the graph was given.
Here only the infection state of each node is seen. The authors split the task: learn the graph, then vaccinate well. Their learning method rests on inclusion and exclusion counts, with a proven sample bound for graph recovery. For the vaccine step, they give an exact method that runs in polynomial time on graphs of bounded tree width, plus a greedy heuristic for any graph.
Catalog record
| CREATOR | Sepehr Elahi, Paula Mürmann, Patrick Thiran |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 113 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-15397
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control Sepehr Elahi, Paula Mürmann, Patrick Thiran 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. † † affiliationnotice: Equal contribution 1 Introduction Spreading models are essential frameworks for understanding how information, diseases, or behaviors propagate through networks ( Nowzari et al. 2016 ) . These models capture the complex interactions between agents, helping to predict dissemination patterns and devise strategies to control unwanted spread ( Lokhov & Saad 2017 ) . Among these models, the Susceptible-Infected-Susceptible (SIS) framework is particularly well-suited for representing scenarios where agents can undergo multiple cycles of infection and recovery. While simple in structure, the interactions between neighboring agents in an SIS model can give rise to complex behavior, which makes predicting and controlling its dynamics challenging. 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 vertex evolves probabilistically, influenced by the infection statuses of its neighboring vertices, allowing for multiple cycles of infection and recovery. In recent years, SIS models 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 et al. 2024 ) , vaccinations or quarantines of vertices (i.e., person or community), are designed 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 ) . We provide a motivating example in the field of epidemiology. 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. Motivating Example. Consider the spread of cholera ( Vibrio cholerae ), a highly contagious waterborne disease that individuals can contract multiple times, making it well-suited to the SIS model ( Ryan & Calderwood 2000 ) . In many regions, the exact network of human interactions and environmental 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 vaccinations to individuals to effectively reduce transmission rates and extinction time ( Ali et al. 2016 ) . In this paper, we focus on determining effective vaccination strategies for an SIS epidemic when the underlying graph is unknown and only infection data is observed. Inspired by real-world approaches like ring vaccination, our approach combines network learning with a targeted vaccination strategy to minimize disease extinction time and control contagion spread. Structure Learning. Most research concerning epidemic structure recovery has been focused on Susceptible-Infected-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 ( Netrapalli & Sanghavi 2012 ) , with a common approach being maximum likelihood estimation (MLE) ( Gomez-Rodriguez et al. 2012 ; Myers & Leskovec 2010 ; Gray et al. 2020 ) . In contrast, learning the network structure of an SIS model does not require multiple cascades since vertices can experience 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. To the best of our knowledge, the only work on structure learning in SIS models is an MLE-based approach by Barbillon et al. 2020 . Their approach can recover both likely edges and infection parameters, but comes without theoretical guarantees and assumes a vertex is infected by only one neighbor at a time, which is a strong assumption in practice. We do not make this restrictive assumption in our work, and instead propose a 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. 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 minimization as a vaccination heuristic ( Van Mieghem et al. 2011 ; Kiji et al. 2022 ) . However, these methods assume the complete removal of either the vaccinated vertices or a 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-time 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 simultaneous 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 is often more applicable in practice. Original Contributions. We address the challenge of devising effective vaccination strategies in an ongoing SIS process where the