When an outbreak, rumor, or cascading power failure is noticed, we usually see only a snapshot: which nodes of a network are currently affected. The question is which nodes started it. A long line of work answers this geometrically, and the answer holds up well. The source is estimated as the Jordan center of the infected region, meaning the node whose farthest infected node is as close as possible. This estimate needs no knowledge of transmission or recovery rates. When there are several sources, the natural extension is a Jordan cover: a small set of nodes whose shortest-path balls jointly contain the infection. These methods rest on a rigid picture, though. Every source is assumed to grow a ball of the same radius. Every infected node is assumed visible. Any irregularity in the infection's shape is treated as if it did not exist. Real cascades break all three assumptions. Sources start at different times, so their regions differ in size. Recovered nodes look healthy in the snapshot. And infections run ahead along some corridors of a loopy graph while lagging along others.
We propose to keep the Jordan geometry as the core of the model and add a statistical account of how real infections depart from it. Each source gets its own radius. The spatially correlated bulges and dents of the infection boundary are modelled by a Gaussian process defined on the graph itself. A Gaussian process (GP) is a prior over functions whose correlations come from a kernel; here the kernel is the graph Matérn kernel built from the graph Laplacian. The result is a likelihood over source sets that needs no training corpus. From it we get three things: a marginal likelihood for choosing the number of sources, posterior samples over source sets that yield calibrated candidate sets, and a principled way to name a source that is currently labelled "uninfected" because it has already recovered. Scalability comes from the sparse precision structure of integer-smoothness graph Matérn GPs. The GP only needs to live on the infected region and a thin boundary shell around it.
Core Claim
The snapshot is modelled as a noisy, spatially correlated thresholding of a multi-radius Jordan cover. For a candidate source set $S=\{s_1,\dots,s_m\}$ with radii $r_1,\dots,r_m$, let $d(s,v)$ be the shortest-path hop distance. Let $g$ be a zero-mean graph Matérn GP with covariance $K_\nu$, and let $\epsilon_v$ be independent Gaussian noise. Node $v$ is predicted infected when
$$ \max_{k\le m}\big(r_k - d(s_k,v)\big) + g(v) + \epsilon_v > 0 . $$
The first term is exactly the geometry of a Jordan cover with unequal radii. Unequal radii allow staggered start times. The GP term $g$ absorbs boundary irregularity that is correlated across neighbouring nodes, which is precisely what makes equal-radius balls misfit on loopy graphs. For SIR-type snapshots, an observed "uninfected" label inside a ball is modelled as a mixture: the node was either never reached, or reached and recovered with a learned probability $\rho$.
Sources are parameters of the mean function, not peaks of the observed labels. A recovered source can therefore still be selected. The claim is that this single model beats both pure geometry and pure smoothing on three tasks: recovering source sets under staggered timing, recovering sources after recovery has occurred, and estimating the number of sources. It does so without simulated training data, and it produces candidate sets whose coverage can be checked and calibrated.
Where This Sits in Prior Work
The geometric line supplies the mean function. Identifying Infection Sources and Regions in Large Networks proves that optimal partitioning of infected nodes among sources on trees under the susceptible–infected (SI) model is a Voronoi partition. Its algorithm, MSEP, estimates both the sources and their number by merging clusters under a distance threshold. Catch'Em All defines the Optimal-Jordan-Cover, a minimum-radius cover by $m$ nodes with a fixed $m$, and proves asymptotic exact recovery on Erdős–Rényi graphs. Persistence of the Jordan center in Random Growing Trees and the loopy-graph epicenter of Epicenter of random epidemic spanning trees on finite graphs strengthen the case that geometric centers are stable, meaningful targets.
We inherit their parameter-free geometry but change what they leave rigid. A single shared radius cannot represent staggered timing. A fixed $m$ or a hand-set merge threshold cannot represent uncertainty about the count. And none of these methods gives a probability that a node is a source.
The smoothing line both motivates the proposal and threatens it. LPSI, from Multiple Source Detection without Knowing the Underlying Propagation Model, spreads $\pm1$ labels through the normalized adjacency matrix and declares local maxima to be sources. Algebraically, this is close to the posterior mean of a GP with a regularized-Laplacian kernel. So "put a graph GP on the snapshot and pick peaks" would largely reproduce LPSI. It would also inherit LPSI's recovered blind spot, since a recovered source labelled $-1$ can never become a peak. This is why we do not propose GP classification as the method. We keep it as an ablation instead.
Matérn Gaussian Processes on Graphs supplies the residual prior and its computational trick. For integer smoothness, the precision matrix is a sparse polynomial in the Laplacian, so standard sparse solvers apply. That work was tested only on traffic regression and Cora classification. Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression motivates one design choice: we fit hyperparameters coarsely once and reuse them across the source search, and we recalibrate predictive variance with a single scale factor. Approximation-Aware Bayesian Optimization argues that approximation capacity should go where the decision lies rather than everywhere. We apply that argument by restricting the GP to the infected region plus an $h$-hop boundary shell. The uninfected interior of a large graph carries almost no information about source identity.
The learned line defines the accuracy bar and the calibration comparison. An Invertible Graph Diffusion Neural Network for Source Localization (IVGD) and Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems (SL-VAE) train on large sets of simulated cascades. Conformal Prediction for Multi-Source Detection on a Network wraps a graph neural network backbone with conformal scores. These scores guarantee a target source recall with high probability, given exchangeable calibration data. We reuse its set-valued conformal scores on top of our posterior. The difference is where the backbone comes from: ours is a training-free likelihood rather than a trained network.
Research Program
The work has four components.
The first is the observation model. It covers the probit threshold above, the recovered/never-reached mixture for SIR and SIS snapshots, and an optional partial-observation mask, where unobserved nodes simply drop out of the likelihood.
The second is inference for a fixed source set. Given $S$ and radii, the mean function is known. The posterior over $g$ on the infected region plus its shell is then an ordinary GP probit problem. We solve it with a Laplace approximation using a sparse Cholesky factorization of the Matérn precision with $\nu\in\{1,2\}$. This yields an approximate marginal likelihood $\hat p(y\mid S,r)$. We profile out each radius $r_k$ by one-dimensional search over the eccentricity of that source's assigned nodes.
The third is search over source sets. Initial candidates come from the infected-neighbour filter of Catch'Em All. We then run Metropolis moves that add, remove, or swap a source. A swap requires one breadth-first search from the new node plus an incremental re-solve, so a move costs roughly one pass over the local edges plus a sparse factorization update. The number of sources $m$ is chosen by the Laplace marginal likelihood with a per-source penalty, with no threshold $\tau$ and no externally supplied $m$.
The fourth is uncertainty. Posterior samples give per-node source probabilities. These probabilities serve as the non-conformity score inside the conformal procedure of Jian et al. That gives two variants to report: a Bayesian credible set, and a conformalized set with a finite-sample recall guarantee.
We will also analyse one theoretical point. On trees under SI with equal start times and $g\equiv0$, the maximum-likelihood source set should reduce to a Jordan cover. That result would tie the model back to the guarantees of Catch'Em All and Identifying Infection Sources and Regions in Large Networks. We will state and prove this reduction rather than assume it.
Baselines
The naive reference points are degree and closeness centrality restricted to infected nodes, with the top-$m$ nodes chosen using the true $m$. Catch'Em All reports that its covers significantly outperform both. Our method must clear this bar by a wide margin, or something is broken.
The strongest geometric competitor is the Optimal- or Approximate-Jordan-Cover from Catch'Em All, run through GraphSL. We give it the true $m$, which is an advantage our method does not receive. It is the right comparison because our model is its probabilistic generalization. The file reports runtime rather than accuracy for it: 3 seconds on a 5,000-node Erdős–Rényi graph with candidate selection. On that axis, beating it means matching its F1 with ground-truth $m$ under equal start times while staying within an order of magnitude of its runtime, and exceeding its F1 under staggered starts and SIR.
For estimating the number of sources, the competitor is MSEP from Identifying Infection Sources and Regions in Large Networks. It reports correct source counts over 93% of the time on geometric trees and over 71% on regular trees. We run it on the same synthetic trees and on the real graphs, with its threshold tuned on held-out cascades using the same number of tuning cascades our penalty receives.
The strongest learned method is IVGD. An Invertible Graph Diffusion Neural Network for Source Localization reports an F1 of 0.9546 on the Western States Power Grid, against 0.8624 for LPSI. SL-VAE reports roughly 20% ROC-AUC and 10% F1 average gains over LPSI. We rerun both inside GraphSL on identical cascades, rather than copying numbers whose simulation settings we cannot match. Each learned model is trained on cascades from one diffusion model and tested both in distribution and under a shift in dynamics. We do not expect to beat IVGD in distribution on the Power Grid; matching it within a few F1 points without any training would already matter. Beating it means higher F1 and lower hop error under dynamics shift, staggered starts, or SIR recovery.
For calibrated sets, the comparison is the conformal method of Conformal Prediction for Multi-Source Detection on a Network on highSchool, bkFratB, and sfhh, with the same $\alpha,\beta$ and calibration split. The file gives no reported numeric set sizes, only that the method achieves target recall with smaller sets than ArbiTree. Beating it means equal empirical recall with smaller average sets.
Three ablations isolate the key ingredients. The first removes the geometric mean function, leaving graph GP classification with peak picking, which is essentially a kernelized LPSI. The second replaces the GP residual with independent noise, which gives a probabilistic multi-radius Jordan cover. The third forces all radii to be equal. The second ablation is the decisive one for the GP's role.
Why not just…?
Why not just put a graph Matérn GP on the labels and take peaks? As argued above, the posterior mean would behave much like LPSI with a better-motivated kernel. It would keep the recovered blind spot, because peaks come from observed labels. This is ablation one. If it matches the full model under SIR, our claim about the mean function is wrong.
Why not just solve a robust multi-radius covering problem with outlier slack and pick $m$ by an elbow? This is the most serious threat. It captures staggered timing and label noise with no GP at all. Ablation two is essentially this method with a proper likelihood. If independent noise matches correlated noise, especially on the loopy Power Grid and Ego-Facebook graphs where corridor effects should appear, we will report that the GP is unnecessary and publish the simpler probabilistic cover. The GP's case rests on boundary deviations being spatially correlated. We will measure this directly by computing the autocorrelation of cover residuals across graph neighbours on simulated cascades before building anything else.
Why not just train a graph neural network and conformalize it? IVGD's in-distribution accuracy is strong. But it needs simulated cascades from the right dynamics, and on the roughly 50,000-node Deezer graph its training took about half a day according to its authors. The shift-of-dynamics experiment tests whether the training dependence costs accuracy. The calibrated-set comparison tests whether a likelihood-based score yields tighter conformal sets.
Why not just use MSEP for unknown $m$? Its merge threshold is hand-set, and its accuracy degrades from trees to less favourable topologies. Its two-source routine is quadratic in the number of nodes. Our count-estimation experiment compares both methods directly, and in that comparison MSEP gets its best tuned threshold.
Proposed Experiments
We simulate cascades with GraphSL's generators for independent cascade and linear threshold spread, plus our own SI and SIR simulations. The graphs are Karate, Dolphins, Jazz, Network Science, Cora-ML, and Power Grid, all from GraphSL, together with Ego-Facebook, Deezer for scale, synthetic trees and Erdős–Rényi graphs, and the three contact networks for calibration. We vary the number of sources from 1 to 8, the spread of start times from zero to half the cascade duration, the recovery rate, and the observed fraction from 10% to 100%. Metrics are GraphSL's F1 and AUC, mean hop distance from each true source to its nearest estimate, accuracy of the source count, empirical recall and average size of prediction sets, and wall-clock time as a function of infected-region size.
Three checks decide the proposal.
The first is staggered timing. With a spread of start times, the shared-radius ablation and the Jordan cover should lose F1 while the full model does not. If the gap does not appear, per-source radii are not doing the claimed work.
The second is recovered sources. Under SIR, we measure the fraction of true sources labelled uninfected that each method recovers. LPSI and GP classification can recover none of them by construction. The full model should recover a substantial fraction.
The third is correlated versus independent noise, measured on loopy graphs. It determines whether the Gaussian process belongs in the model at all.
A scaling run on Deezer, timing inference against infected-region size with the boundary shell fixed, tests the claim that cost follows the infected region rather than the whole graph.
References
- Identifying Infection Sources and Regions in Large Networks
- Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations
- Persistence of the Jordan Center in Random Growing Trees
- Epicenter of random epidemic spanning trees on finite graphs
- Multiple Source Detection without Knowing the Underlying Propagation Model
- Matérn Gaussian Processes on Graphs
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Approximation-Aware Bayesian Optimization
- An Invertible Graph Diffusion Neural Network for Source Localization
- Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems
- Conformal Prediction for Multi-Source Detection on a Network
- GraphSL: An Open-Source Library for Graph Source Localization Approaches and Benchmark Datasets