Research map / Graph learning / Graph algorithms and clustering

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

ICML 2025 · Graph learning › Graph algorithms and clustering · approach: Continuous DAG structure learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Learns the unknown contact graph of an SIS epidemic from infection states via an inclusion-exclusion Ising-style algorithm with sample complexity guarantees, then vaccinates to minimize spectral radius using an exact treewidth DP or a greedy heuristic.

Problem

Minimizing the extinction time of a discrete-time SIS process by one-time vaccination when the contact graph is unknown and only infection states are observed.

Approach

An inclusion-exclusion structure learning algorithm (SISLearn) using direct and conditional influence estimated from SIS trajectories, without the single-infector assumption of prior MLE methods, paired with a polynomial-in-n DP for spectral radius minimization on bounded-treewidth graphs and a greedy heuristic.

Key results

• On augmented chn.2009.flu.1.00 graphs (n=40, K=7), DP achieves the lowest infection rates across all rounds, with Greedy closely trailing and LD third; random vaccination is outperformed by all methods except PO.
• SISLearn achieves average F1-score above 0.9 on both chn.2009.flu.1.00 and usa.2009.flu.1.00 graphs given sufficient learning rounds.
• The DP algorithm is exact for SRM on bounded-treewidth graphs in time polynomial in n, and Greedy scales to n=1000 in about 10 minutes.

Measured effects reported in the paper

Surprising findings

• The priority order (PO) baseline performs worse than random vaccination in the discrete-time SIS setting, likely because it was designed for continuous-time healing.
• The prior MLE-based SIS structure learning method always returned a complete graph in the general setting where multiple infected neighbors infect simultaneously.

Limitations

• SISLearn's guarantees rely on stationarity assumptions and the Markov contraction coefficient; theory assumes the SIS process is at a meta-stable state.
• DP is exponential in treewidth, so it is only feasible for treewidth up to about 15; general graphs need the greedy heuristic, which has no approximation guarantee.
• Experiments are on a small set of simulated SIS processes over real-world outbreak graphs with synthetic edge augmentation.

Experimental setup

Datasets: OutbreakTrees chn.2009.flu.1.00 OutbreakTrees usa.2009.flu.1.00 Synthetic Erdos-Renyi graphs

Benchmarks: Simulated SIS infection proportion on augmented chn.2009.flu.1.00 graphs Simulated SIS infection proportion on usa.2009.flu.1.00 graphs F1 score of learned graph

Metrics: proportion of infected nodes over rounds F1 score running time

Baselines: Random vaccination Largest degree (LD) Priority order (PO) Closed walks (GW) MLE-based SIS structure learning (Ren et al.)

Builds on: Ising model structure learning SRM / spectral radius minimization tree decomposition dynamic programming

Closest papers by meaning

• Controlling The Spread of Epidemics on Networks with Differential Privacy (NeurIPS 2025 · similarity 0.87)
• The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models (AAAI 2024 · similarity 0.83)
• A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models (AAAI 2025 · similarity 0.82)
• Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing (NeurIPS 2025 · similarity 0.82)
• Sample Complexity of Linear Regression Models for Opinion Formation in Networks (AAAI 2025 · similarity 0.81)
• Learning Diffusions under Uncertainty (AAAI 2024 · similarity 0.81)