Inference in Spreading Processes with Neural-Network Priors

Davide Ghio, Fabrizio Boncoraglio, Lenka ZdeborováarXiv 2025 · DOI · arXiv

Introduction

Identifying the origin of a spreading process—often referred to as the "patient zero" problem—is a critical task in fields ranging from epidemiology to social network analysis. Whether tracking the start of a viral outbreak or the source of misinformation on social media, the goal is to infer the initial state of a network based on partial observations of its current state.

Traditionally, mathematical models for source inference have relied on the assumption that initial sources are distributed uniformly or randomly across the network. However, real-world data often provides additional context: node-specific features (covariates) such as age, profession, or mobility patterns significantly influence the likelihood of a node being a source. This paper introduces a framework to incorporate these features using a neural network prior, bridging the gap between network topology and individual node characteristics.

The Neural Sources Spreading (NSS) Model

The authors propose the Neural Sources Spreading (NSS) model, which integrates a generative neural network prior with a spreading process on a graph. In the specific case of the Perceptron Sources Spreading (PSS) model, the prior probability of a node $i$ being a source is determined by a single-layer perceptron acting on its feature vector $\xi_i$.

The spreading dynamics themselves follow standard compartmental models, such as Susceptible-Infected (SI) or Susceptible-Infected-Recovered (SIR). The challenge lies in the inference: given the final state of the network and the node features, how can we reconstruct the initial configuration?

Methodology: The BP-AMP Algorithm

To perform inference in this hybrid model, the authors develop a novel algorithm that combines two distinct message-passing techniques from statistical physics: Belief Propagation (BP) and Approximate Message Passing (AMP).

Factor graph representation of the BP-AMP algorithm, showing the interaction between the perceptron prior (red) and the spreading process (green).

As illustrated in Figure 1, the BP-AMP algorithm operates on a factor graph that splits the problem into two coupled components:

  1. The Spreading Component (BP): Belief Propagation is employed to handle the sparse graph structure of the spreading process. It calculates the likelihood of infection paths based on the network's topology.
  2. The Perceptron Component (AMP): Approximate Message Passing is used for the dense, fully connected weights of the neural network prior. AMP efficiently processes the node features to provide an initial "guess" or prior probability for each node's source status.

In this hybrid setup, the two algorithms exchange information iteratively. AMP provides prior probabilities to BP, which then refines these beliefs based on the observed spreading dynamics. These refined beliefs are fed back to AMP as effective likelihoods, allowing the algorithm to converge on a globally consistent solution.

Results and Phase Transitions

The authors evaluated the BP-AMP algorithm using synthetic data on Random Regular Graphs (RRGs) and Erdős-Rényi (ER) graphs. Their findings highlight several key insights into the nature of the inference problem:

Synergy of Information

The primary result is that combining graph topology with node features drastically improves inference accuracy. The "overlap" (a metric for how well the algorithm identifies true sources) is significantly higher for BP-AMP than for either BP (topology only) or AMP (features only) in isolation. This demonstrates that the two sources of information are complementary.

The Computational "Hard Phase"

A particularly striking discovery occurs when the neural network prior uses binary (Rademacher) weights rather than continuous Gaussian weights. In this scenario, the system exhibits a first-order phase transition. The authors identified a "hard phase"—a region where perfect recovery of the sources is information-theoretically possible given the data, but the BP-AMP algorithm fails to find the solution, getting trapped in a suboptimal state. This gap between the information-theoretic threshold ($\rho_{IT}$) and the algorithmic threshold ($\rho_c$) underscores the inherent computational complexity introduced by certain generative priors.

Conclusion and Future Directions

This work provides a robust theoretical and algorithmic foundation for incorporating neural network priors into spreading process inference. By leveraging the strengths of both BP and AMP, the authors have created a tool capable of handling the dual complexity of network dynamics and high-dimensional node features.

Future research may extend this framework to deep, multi-layer neural networks and address scenarios where spreading parameters (like transmission rates) are unknown and must be learned alongside the source locations. Additionally, providing rigorous mathematical proofs for the observed computational hardness in the binary weight regime remains an open challenge for the community.

Summary updated

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.
BibTeX
@misc{ghio2025inference,
  author = {Davide Ghio and Fabrizio Boncoraglio and Lenka Zdeborová},
  title = {{Inference in Spreading Processes with Neural-Network Priors}},
  year = {2025},
  eprint = {2509.02073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.02073},
}
Figure