No time to waste: practical statistical contact tracing with few low-bit messages

Rob Romijnders, Yuki M. Asano, Christos Louizos, Max Welling

Abstract

Pandemics have a major impact on society and the economy. In the case of a new virus, such as COVID-19, high-grade tests and vaccines might be slow to develop and scarce in the crucial initial phase. With no time to waste and lock-downs being expensive, contact tracing is thus an essential tool for policymakers. In theory, statistical inference on a virus transmission model can provide an effective method for tracing infections. However, in practice, such algorithms need to run decentralized, rendering existing methods – that require hundreds or even thousands of daily messages per person – infeasible. In this paper, we develop an algorithm that (i) requires only a few (2-5) daily messages, (ii) works with extremely low bandwidths (3-5 bits) and (iii) enables quarantining and targeted testing that drastically reduces the peak and length of the pandemic. We compare the effectiveness of our algorithm using two agent-based simulators of realistic contact patterns and pandemic parameters and show that it performs well even with low bandwidth, imprecise tests, and incomplete population coverage.

Introduction

Contact tracing is a vital tool for managing pandemics without resorting to blunt, expensive lockdowns. Statistical contact tracing (SCT) improves upon traditional methods by using probabilistic models to estimate an individual's risk based on their entire contact history. However, SCT faces a significant "chatty" problem. To protect privacy, these algorithms must run decentralized on individual smartphones. Standard techniques like Gibbs sampling or Belief Propagation (BP) require hundreds or even thousands of daily message exchanges to converge, which is impractical for smartphone battery and data limits. This paper introduces Factorized Neighbors (FN), a decentralized inference algorithm designed to achieve superior pandemic suppression with minimal communication overhead.

Methodology

The authors model virus spread using a Probabilistic Graphical Model (PGM) where individuals transition through SEIR (Susceptible, Exposed, Infected, Recovered) states. The core contribution is the FN algorithm, which simplifies standard BP by assuming that the beliefs of neighboring nodes are independent (factored). This "shortcut" transforms computationally expensive operations into a stable product of expectations, particularly effective under communication constraints.

To optimize for real-world deployment, the authors employ:

  • Quantization: Compressing messages to 3–5 bits.
  • Message Pruning: Skipping "backward" messages (information sent back to potential infectors) as they are often uninformative in realistic scenarios.
  • Windowed Inference: Using a sliding 21-day window to reduce computation time with minimal accuracy loss.

The approach was evaluated using two simulators: CRISP (a stochastic block model) and OpenABM-Covid19 (a detailed agent-based model with over 150 parameters modeling UK dynamics).

Results and Discussion

A key finding is that FN's simplified approach is more robust than theoretically more accurate algorithms like BP in low-bandwidth regimes. While BP's messages become erratic under heavy quantization, FN’s expectations remain stable. Furthermore, Gibbs sampling was found to converge too slowly on the complex graphs of human contact to be practical.

Peak infection rates vs. communication load, highlighting FN's performance in practical settings.

In the "practical setting" of low communication load, FN achieved a significantly lower peak infection rate than Gibbs, BP, or random policies. On the complex OpenABM simulator, FN (using 5-bit messages) suppressed the infection rate by two orders of magnitude compared to a random policy, outperforming even unquantized versions of other state-of-the-art methods.

Infection rates over time on the OpenABM simulator (log scale), showing FN's significant suppression.

FN also demonstrated robustness against 50% device "staleness" and high test false-positive rates (up to 25%).

Conclusion

Factorized Neighbors offers a practical path for decentralized statistical contact tracing. While the study was limited to 10,000 agents and assumed accurate contact sensing, it proves that low-bit, infrequent messaging can effectively manage pandemic spread. Future work will focus on scaling to larger populations, addressing Bluetooth sensing noise, and integrating formal Differential Privacy to further enhance user security.

Summary updated

Abstract

Pandemics have a major impact on society and the economy. In the case of a new virus, such as COVID-19, high-grade tests and vaccines might be slow to develop and scarce in the crucial initial phase. With no time to waste and lock-downs being expensive, contact tracing is thus an essential tool for policymakers. In theory, statistical inference on a virus transmission model can provide an effective method for tracing infections. However, in practice, such algorithms need to run decentralized, rendering existing methods – that require hundreds or even thousands of daily messages per person – infeasible. In this paper, we develop an algorithm that (i) requires only a few (2-5) daily messages, (ii) works with extremely low bandwidths (3-5 bits) and (iii) enables quarantining and targeted testing that drastically reduces the peak and length of the pandemic. We compare the effectiveness of our algorithm using two agent-based simulators of realistic contact patterns and pandemic parameters and show that it performs well even with low bandwidth, imprecise tests, and incomplete population coverage.
BibTeX
@inproceedings{romijnders2023no,
  author = {Rob Romijnders and Yuki M. Asano and Christos Louizos and Max Welling},
  title = {{No time to waste: practical statistical contact tracing with few low-bit messages}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=ISmyyrcYNY},
}
Figure