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).
As illustrated in Figure 1, the BP-AMP algorithm operates on a factor graph that splits the problem into two coupled components:
- 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.
- 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