Tree-Markov Gaussian Processes for Multi-Source Epidemic Localization

When an outbreak, a rumor or a cascading power failure has already spread across a network, investigators often have a few infection times from some of the affected nodes and want to know where it started. One strong line of work treats these arrival times as jointly Gaussian. Each edge adds a noisy delay, so two nodes whose transmission paths from the source overlap get correlated arrival times, and the source is the node under which the observed times are most likely. That model is a Gaussian process (a probability model that assigns a joint Gaussian to any set of measurements, with correlations given by a covariance function), here defined over the nodes of a graph. It works well in practice. It is also expensive: it uses dense covariance matrices that must be inverted once for every candidate source. And it handles several simultaneous sources only through a heuristic step that clusters the timestamps and guesses how many sources there are.

This proposal makes three claims. First, on a tree the covariance has a hidden structure: the arrival time at a node depends on the rest of the tree only through its parent. The exact likelihood for every candidate source can therefore be computed in time linear in the tree size, with two passes of message passing. Second, on loopy graphs, the scalable-GP idea of conditioning each observation only on a few nearby observations gives a controlled approximation to the same likelihood. Third, once the likelihood is cheap, multiple sources become a Bayesian model-comparison problem. The number of sources is chosen by marginal likelihood instead of a hand-set merging distance, and the method returns posterior credible sets over source locations rather than a single point guess.

Core Claim

The closest prior work is the Gromov-matrix approach of Estimating Infection Sources in Networks Using Partial Timestamps and On the Properties of Gromov Matrices and Their Applications in Network Inference. It models observed arrival times as

$$T \sim \mathcal{N}(\mu\, d_s,\ \sigma^2 M_s), \qquad (M_s)_{uv} = \tfrac{1}{2}\big(d(s,u) + d(s,v) - d(u,v)\big),$$

where $s$ is the candidate source, $d_s$ is the vector of hop distances from $s$ to the observed nodes, $\mu$ and $\sigma^2$ are the mean and variance of a single edge delay, and $M_s$ is the Gromov matrix. Each entry of $M_s$ is the length of the path from $s$ that two observed nodes share. Their single-source method (GSSI) searches over mixtures of spanning trees using dense matrix operations. Their multi-source method (SCCE) first clusters timestamps, then estimates how many sources each cluster holds, then runs GSSI locally. They report GSSI placing the source within 1.92 hops on Facebook using 20% of timestamps, and a detection improvement of up to 73.7% over a single breadth-first-search tree.

Our observation is that on a tree, $M_s$ is the covariance of Brownian motion on that tree. Arrival time at a child equals arrival time at its parent plus an independent Gaussian delay. The precision matrix over all tree nodes is therefore sparse along the tree edges. Unobserved nodes can be integrated out by Gaussian message passing in $O(n)$, where $n$ is the number of tree nodes. A second pass that re-roots the tree (the standard "all-roots" dynamic program, which only flips the sign of the mean delay along the path between old and new roots) returns the likelihood for every candidate source in $O(n)$ total, instead of a cubic inversion per candidate. The unknown start time is Gaussian-integrable in closed form, so each source's evidence is analytic given $\mu$ and $\sigma^2$.

What is new, relative to GSSI and SCCE, is threefold: an exact linear-time all-sources likelihood on trees, a local-conditioning approximation for loopy graphs, and evidence-based selection of the number of sources jointly with their locations.

Research Program

Single source on loopy graphs. We borrow the decoupling idea of Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression (GPnn). That paper estimates hyperparameters on a small subset, predicts each point from its nearest neighbors, and recalibrates variances afterwards. Our graph analogue works as follows. For a candidate source $s$, we order the observed nodes by timestamp and factor the joint density into one conditional per node, each conditioned only on its $q$ nearest earlier observers in graph distance. The required $q \times q$ blocks of $M_s$ are built from breadth-first-search distances.

Graph Gromov products need not form a valid (positive semi-definite) covariance off trees; this is exactly why Ji et al. project their mixtures back onto tree metrics. We therefore project each small block, which costs $O(q^3)$, rather than the whole matrix. The total per candidate is $O(|E| + kq^3)$, where $|E|$ is the number of edges and $k$ the number of observers. Following GPnn, $\mu$ and $\sigma^2$ are fitted once on a subsample of candidates, and predictive variances are recalibrated post hoc.

Pruning candidates with geometry. We reuse the Jordan-center results here. The Jordan center is the node minimizing the maximum distance to observed infected nodes. How to Identify an Infection Source With Limited Observations shows it is the most-likely-path source on trees. A robust information source estimator with sparse observations bounds its distance to the true source by a constant on infinite trees. We evaluate likelihoods only within a radius of the Jordan center or, for several sources, of the Jordan-cover centers. The Jordan cover is the set of $m$ nodes that jointly reach all infected observers within the smallest radius, from Catch'Em All. These papers supply the candidate generator; they are not the estimator.

Multiple sources. Identifying Infection Sources and Regions in Large Networks (MSEP) proves that on trees the optimal assignment of infected nodes to sources is a Voronoi partition, meaning each node goes to its nearest source. Under that partition the timestamp likelihood factors into independent per-region tree Gaussian processes, each with its own start time. For each $m$ from 1 to $m_{\max}$ we initialize source sets from the approximate Jordan cover (AJC) and refine them by local swap moves. Each move is cheap because only the two affected regions are re-evaluated. We then score $m$ by

$$\log p(T \mid m) \approx \log \sum_{S:\,|S|=m} p(T \mid S, \hat\mu, \hat\sigma^2)\, p(S),$$

where $S$ is a source set, $p(S)$ is a uniform prior over the pruned candidate sets, and the sum is approximated over the sets visited by the search. The extra start times penalize superfluous sources automatically. The same weights give posterior marginals per node, from which we form credible sets.

As a calibration check, we feed these posterior scores into the conformal procedure of Conformal Prediction for Multi-Source Detection on a Network. That paper builds distribution-free prediction sets over a graph neural network backbone; here the backbone is replaced by a likelihood.

Robustness to delay distribution. Gaussian delays are an assumption. We will test exponential delays (the SI model, where a node once infected stays infected), heavy-tailed delays, and SIR dynamics (where infected nodes later recover). The point is to measure how fast the Gaussian likelihood degrades relative to the parameter-free Jordan estimators.

Baselines

Naive reference. The naive reference point is the earliest-timestamped observer, alongside the plain Jordan center, or the Jordan cover when there are several sources. These are what a practitioner would compute in seconds. Beating them is necessary but not interesting.

Strongest single-source competitor. This is GSSI, run with the authors' tree-mixture and shrinkage settings on the same graphs, the same observer fractions and the same simulated cascades. It is the strongest because it uses the same Gaussian model with the full dense covariance. Its reported result is 1.92 hops average error on the Facebook malware experiment with 20% of timestamps Estimating Infection Sources in Networks Using Partial Timestamps. Success means matching that error within 0.2 hops while running at least an order of magnitude faster, and continuing to run on graphs where GSSI exhausts memory or time. Both methods get the same CPU budget and the same hyperparameter-search budget for $\mu$ and $\sigma^2$.

Strongest multi-source competitors.

Beating them means higher source-count accuracy than MSEP on the same trees and graphs, and lower matched error distance than all four.

Ablations. Three ablations isolate the ingredients:

  • Exact tree likelihood on a single breadth-first-search tree versus local conditioning, which isolates the loopy approximation.
  • Evidence-based selection of $m$ versus our own likelihood paired with SCCE's clustering-and-count step, which isolates the cardinality mechanism.
  • Credible sets with and without conformal recalibration.

Why not just…?

Why not just run GSSI on a pruned candidate set around the Jordan center? This captures part of the speedup and is a real threat on graphs of a few thousand nodes. But each candidate still costs a cubic inversion in the number of observers. It also does nothing for multiple sources, where the search visits many source sets. The scaling experiment below reports GSSI-with-pruning as its own curve. If it matches our runtime at $10^5$ nodes with 10% observers, the scalability claim fails, and the contribution reduces to cardinality selection.

Why not just bolt an information criterion onto SCCE's clusters? This is the simplest route to choosing $m$ without a threshold, and we include it as an ablation rather than dismiss it. Our argument is that SCCE fixes the partition before scoring. Merged cascades are precisely where clustering of timestamps fails, because waves from different sources overlap, as Wang et al. describe. Joint search over Voronoi partitions should therefore help most when sources are close together. We will stratify results by inter-source distance. If SCCE-plus-criterion matches us at every distance, we will say so.

Why not just use the Jordan cover, which needs no delay model at all? It is parameter-free and provably consistent on Erdős–Rényi graphs. But it discards timestamps, needs $m$ given, and returns no uncertainty. The delay-misspecification experiments decide when timing information outweighs model error. If the Jordan cover wins under heavy-tailed delays, that defines the method's scope.

Why not just use dynamic message passing? It is Bayes-optimal on random graphs when parameters are known Bayes-optimal inference for spreading processes on random networks. However, Zhu and Ying report it at 57% within seven hops versus 71% for the Jordan-based estimator, and over 229 seconds versus 0.57 seconds on the Power Grid A robust information source estimator with sparse observations. We include it only on the Power Grid for reference.

Proposed Experiments

First check: exactness and scaling. On random trees up to $10^6$ nodes, the linear-time likelihood must equal the dense Gaussian likelihood to numerical precision. Wall-clock time must scale linearly while GSSI scales cubically.

Second check: real graphs and fidelity of the loopy approximation. We use cascades on Ego-Facebook, Enron, the Western U.S. Power Grid (4,941 nodes), Internet Autonomous Systems (10,670 nodes), the highSchool contact network, and Higgs Twitter cascades. We sweep observer fractions over 5%, 10%, 20% and 50%, and neighbor counts $q$ over 2, 5, 10 and 20. We report average error distance and top-k detection against GSSI. The kill criterion is a degradation of more than 0.5 hops at $q = 10$ on Facebook relative to GSSI; that would mean local conditioning loses too much of the graph's loop structure.

Third check: multiple sources. We plant 1 to 6 sources on Power Grid, Facebook and synthetic Barabási–Albert graphs, with controlled inter-source distance. We report source-count accuracy, a matched error distance (Hungarian matching of estimated to true sources), F-score, and credible-set coverage and size. Coverage of the 90% credible sets should be within a few points of nominal under Gaussian delays. We will also report how coverage drifts under exponential delays and under SIR dynamics with hidden recovered nodes.

Fourth check: scale. On synthetic Erdős–Rényi and Barabási–Albert graphs of $10^5$ to $10^6$ nodes, where GSSI and SCCE cannot run, we compare against the Jordan cover and LPSI. This shows whether timing information still pays at a scale no Gaussian method has reached.