Bayesian inference of epidemics on networks via Belief Propagation

Fabrizio Altarelli; Alfredo Braunstein; Luca Dall'Asta; Alejandro Lage-Castellanos; Riccardo Zecchina

Source-linked AI summary

Bayesian inference of epidemics on networks via Belief Propagation

Fabrizio Altarelli, Alfredo Braunstein, Luca Dall'Asta, Alejandro Lage-Castellanos, Riccardo Zecchina

arXiv:1307.6786v2Jul 25, 2013q-bio.QMcond-mat.stat-mechcs.SI

TL;DR

The paper develops Belief Propagation equations for epidemic inference on networks, including posterior inference with general observations and multiple seeds. The equations are exact on tree factor graphs, while simulations report higher accuracy than Dynamic Message Passing in many settings, with convergence limitations for large epidemics.

Problem
Inference with multiple epidemic seeds makes exhaustive initial-state methods such as DMP combinatorially expensive.
Method
Belief Propagation computes posterior seed probabilities directly by tracing over initial conditions, avoiding exhaustive enumeration of seed subsets.
Results
BP is exact on tree factor graphs and remains more accurate than Restricted Dynamic Message Passing, although it can lose accuracy when large epidemics fail to converge.
Takeaways & Limitations
BP supports posterior inference for multiple seeds without the combinatorial explosion affecting exhaustive DMP generalizations.
Takeaways & Limitations
BP may not converge when epidemics become large relative to the supporting graph, a regime associated with reduced inference accuracy.

Abstract

from arXiv · show

We study several bayesian inference problems for irreversible stochastic epidemic models on networks from a statistical physics viewpoint. We derive equations which allow to accurately compute the posterior distribution of the time evolution of the state of each node given some observations. At difference with most existing methods, we allow very general observation models, including unobserved nodes, state observations made at different or unknown times, and observations of infection times, possibly mixed together. Our method, which is based on the Belief Propagation algorithm, is efficient, naturally distributed, and exact on trees. As a particular case, we consider the problem of finding the "zero patient" of a SIR or SI epidemic given a snapshot of the state of the network at a later unknown time. Numerical simulations show that our method outperforms previous ones on both synthetic and real networks, often by a very large margin.

Appendix A: Belief propagation equations

The appendix derives Belief Propagation equations for SIR posterior distributions and reformulates them so inference is exact on trees and computationally efficient.

Appendix A: Belief propagation equations: Belief Propagation equations approximate single-site posterior marginals by iterating distributions labeled by directed graph edges.At a fixed point, the equations also provide quantities such as the partition function.
Appendix A: Belief propagation equations: The general BP update equations use factors and variables connected through neighborhood sets, with normalization factors computed after the message terms.The appendix identifies ψi, φij, γi, ζi, and Gi as factors and explains the corresponding variable neighborhoods.
Appendix A: Belief propagation equations: Updates for φij, γi, ζi, and Gi involve only a constant number of variables, while the ψi update is derived in linear time in vertex degree.This avoids the generally exponential trace computation for the ψi factor.
Appendix A: Belief propagation equations: The efficient ψi update costs O(G · T · |∂i|), where G is the maximum allowed recovery delay.The appendix also states that a more efficient parametrization aggregates incoming distributions before updating ψi.
Appendix A: Belief propagation equations: The factor-graph representation is reorganized so its topology mirrors the original network, making SIR posterior marginals exact on tree graphs.Grouping activation-time pairs into shared variable nodes improves the BP approximation and preserves exactness on trees.

Appendix B: Bethe Free Energy

The appendix uses the Bethe approximation to estimate the model’s free energy from BP messages when exact calculation of the partition function is computationally hard.

Appendix B: Bethe Free Energy: The cavity scheme approximately computes the free energy f = −log Z from BP messages and their normalization factors.Because log Z is the log-likelihood of external parameters, the approximation can be used to estimate those parameters.

Appendix C: Convergence of the BP equations

BP convergence is not guaranteed in every setting, especially when observations provide insufficient information about the epidemic’s initial conditions.

Appendix C: Convergence of the BP equations: BP equations may fail to converge or require too many iterations when the observations contain insufficient information about the initial conditions.The authors report that this limitation is not showstopping because unconverged marginals often remain useful.
Appendix C: Convergence of the BP equations: Averaging origin probabilities across BP iterations, such as 100 iterations, gives excellent results in most cases.When the seed set is fixed, the equations seem to converge almost always, and BP free-energy estimates improve origin identification relative to DMP.

Appendix D: Dynamic Message Passing

Dynamic Message Passing estimates epidemic origins through factorized forward-propagation probabilities, but its approximation can fail even on trees. Restricted DMP improves in many situations, while BP is generally more accurate but can lose accuracy or convergence for nearly universal outbreaks.

Appendix D: Dynamic Message Passing: DMP estimates a candidate seed’s posterior probability from the likelihood of the observed epidemic under a factorized approximation.For each possible origin, forward equations produce state probabilities and an energy E(i) = −log P(xT|i); the lowest-energy node is selected.
Appendix D: Dynamic Message Passing: Figure 5 presents three incorrect-propagation examples under distinct transmission, recovery, and observation-time parameter settings.The settings are (a) λ = 0.5, µ = 0.3, T = 8; (b) λ = 0.4, µ = 0.1, T = 5; and (c) λ = 0.2, µ = 0.2, T = 8.
Appendix D: Dynamic Message Passing: Restricted Dynamic Message Passing (DMPr) limits message passing to infected, recovered, and unobserved nodes plus the relevant boundary.This focuses contributions on epidemic paths consistent with the observations and often improves estimates over standard DMP.
Appendix D: Dynamic Message Passing: BP remains less accurate than DMPr only in the region where large epidemics cause nonconvergence and reduce inference accuracy.For small observation times such as T = 5, the epidemic remains small and BP always converges; when the epidemic covers almost the entire graph, all algorithms perform worse.
Appendix D: Dynamic Message Passing: The DMP factorization can produce significant seed-location errors even on tree contact networks, where time-forward propagation is exact.In the illustrated case, DMP places the seed at node 2 although node 3 is most probable, because it incorrectly counts susceptible-leaf contributions conditioned on an uninfected node.

Appendix E: Evolving networks

The method extends to time-dependent transmission probabilities by making transmission delays depend on infection time, while retaining the rest of the formalism. The benchmarks compare inference across observation times and recovery probabilities on random regular graphs.

Appendix E: Evolving networks: Time-dependent transmission probabilities are handled by conditioning transmission-delay probabilities on the infection time.The remaining inference formalism is unchanged.
Appendix E: Evolving networks: The simulations use time-stamped contact data aggregated into effective time steps and focus on the known initial-time scenario T0 = 0.Virtual epidemics are initiated by single random individuals.

1. Proximity contacts network

The proximity-contact experiment uses RFID-recorded face-to-face interactions to evaluate epidemics initiated before entry into the facilities. It simulates many random virtual epidemics under specified contagion and recovery parameters.

1. Proximity contacts network: The dataset records 20-second face-to-face contacts at an exhibition using RFID badges.The analysis selects the day with the largest number of individuals and contacts.
1. Proximity contacts network: The known initial-time scenario T0 = 0 represents a zero patient infected before entering the facilities.This makes the scenario particularly relevant for the proximity-contact setting.
1. Proximity contacts network: The experiment uses λ20s = 0.2, µ20s = 0.0014, and thousands of virtual epidemics initiated by random individuals.It simulates 5000 epidemics for ∆T = 20 and 2000 for ∆T = 30.

2. Sexual contacts network

The sexual-contact experiment analyzes a Brazilian database of self-reported client–escort encounters and summarizes inference results for the selected recent records. A temporal-correlation test compares the original and reshuffled networks.

2. Sexual contacts network: The second dataset contains self-reported sexual encounters between clients and escorts from a Brazilian website.The experiment fixes the transmission probability per contact and uses a recovery probability of µyear = 0.5.
2. Sexual contacts network: The analysis uses the last two years of records because older data are sparser, relatively incomplete, and produce very small epidemics.Results are summarized in Figure 10 and Table I.
2. Sexual contacts network: 437 ± 82 individuals were involved in original-network outbreaks versus 258 ± 58 after reshuffling, while correct-zero-patient inference was 93% ± 1% versus 94% ± 1%.These results come from 500 samples in the temporal-correlation analysis.

Appendix F: Inference with multiple seeds

For multiple infection seeds, exhaustive forward-propagation approaches face combinatorial growth, whereas BP traces over initial conditions directly. The resulting node-level seed probabilities support ROC-based evaluation.

Appendix F: Inference with multiple seeds: Exploring all subsets of k seeds in a graph with N vertices requires different forward propagations under a straightforward DMP generalization.This creates a combinatorial explosion as the number of seeds grows.
Appendix F: Inference with multiple seeds: BP avoids this multiple-seed enumeration by tracing over initial conditions within the inference framework.The method uses a finite, non-infinitesimal prior over seed states.
Appendix F: Inference with multiple seeds: The method returns each node's probability of belonging to a seed subset, which can be ranked and evaluated with a ROC curve.It does not provide the single subset with maximum posterior probability.

Appendix G: Inference of epidemic parameters with BP and DMP

BP and DMP can infer homogeneous epidemic parameters by comparing free energies, although both generally require transmission and recovery probabilities as inputs. The parameter posterior assumes a uniform prior.

BP and DMP generally require the contact network, transmission probabilities λij, and recovery probabilities µi.
Figure 9 plots the CDF of epidemic sizes for BP, DMPr, and DMP on the proximity-contacts temporal network.The figure covers 5,000 epidemics for T = 20 and 2,000 epidemics for T = 30.
For homogeneous parameters, BP and DMP can infer epidemic parameters by comparing energies or free energies across pairs (λ, µ).
The parameter posterior is computed assuming a uniform prior over (λ, µ).

Dynamic Message Passing

Dynamic Message Passing assigns each possible seed a probability for generating the observed epidemic and uses a free-energy estimate to assess parameter likelihood. Figure 10 compares epidemic-size distributions for BP, DMPr, and DMP.

DMP assigns a probability P(xT|i, λ, µ) to the observed epidemic for every possible seed i.
The DMP free energy provides an estimate of the negated log-likelihood of the epidemic parameters.
Lower free energy corresponds to more likely parameter values.
Figure 10 plots the CDF of epidemic sizes for 10,000 epidemics at each T on the sexual-contacts temporal network.

Belief Propagation

BP computes parameter posteriors by tracing over infection times, recovery delays, and zero-patient choices, then approximates the otherwise hard partition-function calculation. Figure 11 evaluates multiple-seed inference using ranking and ROC-based measures.

The posterior of epidemic parameters is computed by tracing over infection times, recovery delays, and zero-patient choices.
The desired parameter log-likelihood is obtained as the negated free energy of the model.
Figure 11 plots the average sum of true-seed rankings against the true number of seeds and the average normalized mean ranking, equal to ROC area.The evaluation uses 1,000 virtual epidemics with unknown observation times for inference.
Exact calculation of Z is computationally hard, so BP uses a Bethe approximation to estimate fBP(λ, µ).
A heat plot shows standardized fDMP(λ, µ) and fBP(λ, µ) over a discretized two-dimensional parameter space for an epidemic observed at T = 8.Each plotted point corresponds to a DMP and DMPr run with the associated parameters.