Epidemic mitigation by statistical inference from contact tracing data

Antoine Baker, Indaco Biazzo, Alfredo Braunstein, Giovanni Catania, Luca Dall’Asta, Alessandro Ingrosso, Florent Krząkała, Fabio Mazza, Marc Mézard, Anna Paola Muntoni, Maria Refinetti, Stefano Sarao Mannelli, Lenka Zdeborová

This paper, published in late 2020, presents a sophisticated statistical approach to a problem the world came to know all too well: how to stop a virus from spreading without locking everyone in their homes.

TL;DR

The authors propose using Bayesian inference—specifically Belief Propagation and Mean-Field algorithms—to transform digital contact tracing from a simple notification system into a powerful risk-estimation engine. By calculating the actual probability that an individual is infected based on their contact history, health authorities can prioritize testing and quarantine much more effectively than with standard "dumb" contact tracing, potentially containing outbreaks even with limited testing resources and imperfect data.

What Problem Does This Paper Address?

The standard "trace-test-isolate" strategy works well in the early stages of an epidemic. However, it breaks down when the virus spreads faster than manual tracers can make phone calls.

Digital contact tracing (apps using Bluetooth to log proximity) was proposed as a scalable solution, but most early implementations were "binary": if you were near a person who tested positive, you were notified. This approach ignores the "who-infected-whom" logic. For example, if you met person A (who later tested positive) before they were actually infectious, your risk is zero. If you met person B (who hasn't been tested but met five people who did), your risk might be very high. This paper addresses the need for a "smarter" tracing system that uses the full network of contacts to estimate individual risk levels.

Methods

The authors frame the epidemic as a stochastic process on a dynamic contact network. They introduce two primary algorithms for "Bayesian Epidemic Tracing":

  1. Belief Propagation (BP): A message-passing algorithm that estimates the marginal probability of infection for each person. It is highly accurate because it accounts for the causal chains of transmission (the "tree-like" structure of local infections). It can handle non-Markovian dynamics, such as the specific time-dependent infectiousness of COVID-19.
  2. Mean-Field (MF) Approximation: A simpler, computationally "lighter" version of the inference. It assumes that the infection status of neighbors is independent. While less accurate than BP, it requires much less data exchange between devices, making it more privacy-friendly and easier to implement on mobile hardware.

Crucially, both methods are distributed. Instead of a central government database knowing everyone's location, phones only need to exchange small "risk messages" with the devices they have actually been in contact with.

Datasets

The authors evaluate their methods using two different simulation environments:

  • Geometric Contact Model: A simplified 2D random graph where 500,000 individuals move and interact. This serves as a "controlled" environment where the underlying physics of the spread matches the inference model.
  • OpenABM-Covid19: A much more realistic, agent-based model developed by researchers at Oxford. It includes age-stratified populations, households, workplaces, and complex clinical pathways (asymptomatic vs. symptomatic, hospitalization, etc.). This is used to test if their "simple" SIR-based inference can still work in a messy, realistic world.

Key Insights and Ideas

  • Simple Priors, Complex Realities: One of the most important findings is that you don't need a perfect model of the virus to do good inference. The authors used a very simple "Susceptible-Infected-Recovered" (SIR) model as their mathematical "prior," and it still performed exceptionally well when tested against the highly complex OpenABM simulation.
  • Causality is King: Standard contact tracing only looks one step away from a positive test. Bayesian inference looks at the whole local neighborhood. It can identify "silent spreaders"—people who are likely infected but haven't been tested yet—by seeing that they are the common link between other infected individuals.
  • The Power of Ranking: Instead of quarantining everyone, the system ranks individuals by risk. Testing the top $N$ people on that list is vastly more efficient than random testing or even standard contact tracing.

Key Results

  • Containment: In the OpenABM simulations (500k people), BP-based tracing could stop an outbreak with just 1,000 to 1,500 tests per day. In the same scenario, standard contact tracing and random testing both failed to prevent the epidemic from exploding.
  • Robustness to Noise: The BP algorithm is remarkably resilient. It maintained its edge even when medical tests had a 30% false-negative rate.
  • Adoption Thresholds: While the system works best with high app adoption, the authors found that even at 60-70% adoption, the inference-based methods provided a significant delay in the epidemic peak compared to other strategies.
  • Early Intervention: Moving the start of the intervention from day 10 to day 7 of an outbreak allowed the epidemic to be controlled with 10x fewer tests.

Limitations and Future Work

  • Privacy vs. Performance: While the authors argue the methods are "compatible" with privacy standards, a full cryptographic implementation (e.g., integrating with the DP-3T protocol) was not detailed and remains a challenge for future engineering.
  • Computational Load: Belief Propagation is more CPU-intensive than simple contact logging. While the authors suggest it's manageable for modern smartphones, the battery impact of frequent "risk updates" would need real-world testing.
  • Human Behavior: The model assumes people actually follow the app's advice to quarantine. In reality, "quarantine fatigue" or lack of trust in the algorithm could degrade performance.

Summary updated

Abstract

Contact tracing is an essential tool to mitigate the impact of a pandemic, such as the COVID-19 pandemic. In order to achieve efficient and scalable contact tracing in real time, digital devices can play an important role. While a lot of attention has been paid to analyzing the privacy and ethical risks of the associated mobile applications, so far much less research has been devoted to optimizing their performance and assessing their impact on the mitigation of the epidemic. We develop Bayesian inference methods to estimate the risk that an individual is infected. This inference is based on the list of his recent contacts and their own risk levels, as well as personal information such as results of tests or presence of syndromes. We propose to use probabilistic risk estimation to optimize testing and quarantining strategies for the control of an epidemic. Our results show that in some range of epidemic spreading (typically when the manual tracing of all contacts of infected people becomes practically impossible but before the fraction of infected people reaches the scale where a lockdown becomes unavoidable), this inference of individuals at risk could be an efficient way to mitigate the epidemic. Our approaches translate into fully distributed algorithms that only require communication between individuals who have recently been in contact. Such communication may be encrypted and anonymized, and thus, it is compatible with privacy-preserving standards. We conclude that probabilistic risk estimation is capable of enhancing the performance of digital contact tracing and should be considered in the mobile applications.
BibTeX
@inproceedings{baker2021epidemic,
  author = {Antoine Baker and Indaco Biazzo and Alfredo Braunstein and Giovanni Catania and Luca Dall’Asta and Alessandro Ingrosso and Florent Krząkała and Fabio Mazza and Marc Mézard and Anna Paola Muntoni and Maria Refinetti and Stefano Sarao Mannelli and Lenka Zdeborová},
  title = {{Epidemic mitigation by statistical inference from contact tracing data}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2021},
  doi = {10.1073/pnas.2106548118},
}

Loading related content...

Figure