Inference in Spreading Processes with Neural-Network Priors

Davide Ghio, Fabrizio Boncoraglio, Lenka Zdeborová · 2025

Read Inference in Spreading Processes with Neural-Network Priors by Davide Ghio, Fabrizio Boncoraglio, Lenka Zdeborová (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02073.txt.

Introduction

Davide Ghio, Fabrizio Boncoraglio, and Lenka Zdeborova infer spreading processes on graphs when starting states depend on node covariates. Spreading models cover epidemics and other dynamics where each node changes state over time. Observers see only some nodes at some times and must reconstruct the rest. Past work assumed random starting states, ignoring side data that shape them.

Here a single layer neural network maps covariates to each node starting state inside a Bayesian frame. A hybrid belief propagation and message passing algorithm handles dynamics and covariate data together. It beats estimators that use only spread data or only covariates. In some regimes, first order phase transitions create gaps where perfect recovery is possible in theory yet the algorithm fails. The gap highlights hard inference zones.

Catalog record

CREATORDavide Ghio, Fabrizio Boncoraglio, Lenka Zdeborová
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-02073

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Inference in Spreading Processes with Neural-Network Priors Davide Ghio, Fabrizio Boncoraglio, Lenka Zdeborová 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. I Introduction Spreading dynamics on networks model many important systems, such as information diffusion in social networks Vespignani 2012 , epidemic processes Pastor-Satorras et al. 2015 ; Keeling and Eames 2005 , and gene regulatory networks Karlebach and Shamir 2008 . There are many studies in the literature that tackle the interplay between the network topology and the dynamical process which takes place on top of it Hwang 2006 . In this work we study Bayesian inference for this class of models, aiming to recover some information about a realisation of the dynamics from partial observations. In such Bayesian setting, this problem reduces to computing posterior expectations, where the spreading process itself defines the prior and observations form the likelihood. Statistical physics has yielded several inference algorithms for spreading models on random sparse graphs, including dynamic message passing (DMP) Lokhov et al. 2014 and belief propagation (BP) Altarelli et al. 2014a . Our work builds on the BP formulation to derive a new algorithm. Spreading models often assume a separable prior over initial sources, ignoring node-specific information. However, node features are often available in practice and can enhance inference. To leverage such data, recent work in signal processing uses generative priors, often based on neural networks that map features to problem variables Aubin et al. 2019 ; Aubin et al. 2020 . We introduce the Neural Sources Spreading (NSS) model, where the unknown initial state of the spreading process is given by the output of a neural network with unknown weights acting on known node-wise variables. The NSS model’s posterior corresponds to a hybrid factor graph. It combines a sparse graph on which the spreading dynamics takes place - suited for BP on locally tree-like structures Altarelli et al. 2014a ; Mezard and Montanari 2009 - with a dense graph for the neural-network prior, which is effectively handled by approximate message passing (AMP) in high dimensions Zdeborová and Krzakala 2016 ; Barbier et al. 2019 . Using the cavity method, we merge these components to derive a hybrid BP-AMP algorithm that handles both the sparse spreading interactions and the dense Neural-Network prior Manoel et al. 2017 ; Duranthon and Zdeborová 2023 . This paper is structured as follows. Section II defines the NSS model. Section III details the Bayesian inference framework and performance metrics. Section IV presents the cavity equations and our BP-AMP algorithm. We then analyse its performance in a setting showing evidence of Bayes-optimality (Sec. V ) and another exhibiting a statistical-to-computational gap (Sec. VI ). The code to reproduce all results is available in a dedicated GitHub repository 1 1 1 https://github.com/IdePHICS/NeuralSpreadingInference . I.1 Related works This study is situated within the field of spreading processes on graphs, which examines how these dynamics relate to the underlying graph structure, particularly in domains such as epidemiology Newman 2003 ; Kiss et al. 2017 . Building on established compartmental models Kermack et al. 1932 ; Paré et al. 2020 , we focus on the algorithmic challenges of inference, such as identifying the initial sources of an epidemic or recovering entire infection trajectories. A large body of work in different scientific domains have studied the problem of inference of spreading processes on graphs. Probably the most important example is the one of source detection, or equivalently of finding the patient-zero of the epidemic, which has attracted many researchers after the seminal papers Shah and Zaman 2010a ; Shah and Zaman 2011 , where the authors, restricting to the SI model, showed rigorous results for regular trees using the concept of rumour centrality as maximum likelihood estimator. Later, in Antulov-Fantulin et al. 2014 the authors extended the study to general trees, and in Dong et al. 2013 the SIR model was considered, in both cases choosing as partial information a snapshot of the epidemic, i.e. the state of all the nodes at a particular time. At the same time in Pinto et al. 2012a the authors moved to consider localised observations, or sensors, as source of information and described the optimal maximum likelihood estimator for trees. In Karrer and Newman 2010 for the first time a message-passing approach was introduced to analyse epidemic models, enabling the computation of average properties on arbitrary random graphs ensembles. Later, two different works were able to design a message-passing algorithm operating on single graphs: in Lokhov et al. 2014 the authors introduced a “Dynamical Message Passing” (DMP) algorithm, which is exact on trees but gives results for a fixed initial condition, while in Altarelli et al. 2014b the “Belief Propagation” (BP) equations for this problem were derived for the first time, and were used to infer the origin of epidemics with multiple patients zero and various types of partial information. These techniques were later used for other related problems, as the reconstruction of the model’s parameters Lokhov 2016 or epidemic mitigation studies Baker et al. 2021 . The methodology we employ connects to the idea of merging graphical models, an approach that was formulated in Manoel et al. 2017 ; Gabrié et al. 2018 to extend single-layer AMP to multiple layers. Closer to the present setting, Duranthon and Zdeborová 2023 derived a BP-AMP algorithm for community detection with a neural network prior on node attributes. Finally, we note a recent line of work conjecturing the existence of replica symmetry breaking in spreading processes at very low source densities Braunstein et al. 2023 ; Braunstein et al. 2025 . This paper, in contrast, focuses on scenarios with higher source

Read the complete text