Inference in Spreading Processes with Neural-Network Priors

Abstract

Stochastic processes on graphs are a powerful tool for modelling complex dynamical systems such as epidemics. A recent line of work focused on the inference problem where one aims to estimate the state of every node at every time, starting from partial observation of a subset of nodes at a subset of times. In these works, the initial state of the process was assumed to be random i.i.d. over nodes. Such an assumption may not be realistic in practice, where one may have access to a set of covariate variables for every node that influence the initial state of the system. In this work, we will assume that the initial state of a node is an unknown function of such covariate variables. Given that functions can be represented by neural networks, we will study a model where the initial state is given by a simple neural network -- notably the single-layer perceptron acting on the known node-wise covariate variables. Within a Bayesian framework, we study how such neural-network prior information enhances the recovery of initial states and spreading trajectories. We derive a hybrid belief propagation and approximate message passing (BP-AMP) algorithm that handles both the spreading dynamics and the information included in the node covariates, and we assess its performance against the estimators that either use only the spreading information or use only the information from the covariate variables. We show that in some regimes, the model can exhibit first-order phase transitions when using a Rademacher distribution for the neural-network weights. These transitions create a statistical-to-computational gap where even the BP-AMP algorithm, despite the theoretical possibility of perfect recovery, fails to achieve it.

26 pages, 13 figures

References in corpus (19)

• The structure and function of complex networks
• Epidemic processes in complex networks
• Statistical physics of inference: Thresholds and algorithms
• Locating the Source of Diffusion in Large-Scale Networks
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Bayesian inference of epidemics on networks via Belief Propagation
• Identifying Infection Sources and Regions in Large Networks
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Entropy and mutual information in models of deep neural networks
• Information-theoretic thresholds from the cavity method
• The zero-patient problem with noisy observations
• Epidemic mitigation by statistical inference from contact tracing data
• Learning curves for the multi-class teacher-student perceptron
• Bayes-optimal inference for spreading processes on random networks
• Statistical Mechanics of Inference in Epidemic Spreading
• Equilibrium properties of disordered spin models with two scale interactions
• Neural-prior stochastic block model
• Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs