# Quickest Inference of Network Cascades with Noisy Information

arXiv: https://arxiv.org/abs/2110.08115 · HTML: https://mlsanity.com/paper/2110.08115/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2021.

## Built on by (most cited first, 1 of 1)

- [Decentralized Adversarial Training over Graphs](https://mlsanity.com/paper/2303.13326/) (2023)

## Abstract (arXiv)

We study the problem of estimating the source of a network cascade given a time series of noisy information about the spread. Initially, there is a single vertex affected by the cascade (the source) and the cascade spreads in discrete time steps across the network. The cascade evolution is hidden, but one can observe a time series of noisy signals from each vertex. The time series of a vertex is assumed to be a sequence of i.i.d. samples from a pre-change distribution Q0 before the cascade affects the vertex, and the time series is a sequence of i.i.d. samples from a post-change distribution Q1 once the cascade has affected the vertex. Given the time series of noisy signals, which can be viewed as a noisy measurement of the cascade evolution, we aim to devise a procedure to reliably estimate the cascade source as fast as possible. We investigate Bayesian and minimax formulations of the source estimation problem, and derive near-optimal estimators for simple cascade dynamics and network topologies. In the Bayesian setting, an estimator which observes samples until the error of the Bayes-optimal estimator falls below a threshold achieves optimal performance. In the minimax setting, optimal performance is achieved by designing a novel multi-hypothesis sequential probability ratio test (MSPRT). We find that these optimal estimators require log log n / log (k - 1) observations of the noisy time series when the network topology is a k-regular tree, and (log n)^frac1ℓ + 1 observations are required for ℓ-dimensional lattices. Finally, we discuss how our methods may be extended to cascades on arbitrary graphs.