💻 computer science

Reconstructing Network Outbreaks under Group Surveillance

This paper introduces the NP-hard POOLCASCADEMLE problem for reconstructing disease outbreaks from group surveillance data, proves its computational hardness even in restricted settings, and proposes approximation algorithms based on Group Steiner Tree and linear programming that outperform existing individual-testing baselines.

Original authors: Ritwick Mishra, Abhijin Adiga, Anil Vullikanti

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ritwick Mishra, Abhijin Adiga, Anil Vullikanti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Who got sick, and how did the sickness spread?

Usually, detectives have a list of suspects (the infected people) and try to draw lines between them to see who infected whom. But in the real world, we rarely have a perfect list. We often only have clues.

This paper introduces a new kind of clue: Group Testing.

The "Pooled Soup" Analogy

Imagine you are testing a large group of people for a virus. Instead of testing Person A, then Person B, then Person C individually (which takes a lot of time and money), you mix their samples together into one big bowl of "soup" and test that bowl.

If the soup tastes bad (Positive): You know someone in that bowl is sick. But you don't know who. It could be Person A, Person B, or both.
If the soup tastes good (Negative): You know everyone in that bowl is healthy. You can clear the whole group at once!

This is how Group Surveillance works (like testing wastewater from a whole neighborhood or a school). It's efficient, but it creates a puzzle: If the soup is bad, which specific people in the bowl are the culprits?

The Big Problem

The authors ask: How do we reconstruct the entire "chain of infection" (the cascade) when we only have these group clues?

In the past, scientists assumed they knew exactly who was sick (like testing one person at a time). They used math to find the "most likely" path the virus took. But when you have group clues, the math gets incredibly messy. It's like trying to solve a maze where you only know that "a monster is in one of these three rooms," but you don't know which one.

The paper proves that solving this perfectly is mathematically impossible for computers to do quickly (it's "NP-hard"). It's like trying to find the perfect combination for a safe with a billion dials; you'd have to wait until the sun burns out to check every possibility.

The Solution: The "Smart Detective"

Since they can't find the perfect answer, the authors built two "smart detective" algorithms (approximation methods) that find a very good answer quickly.

ApproxCascade (The Network Mapper):
- How it works: Imagine the virus spreading through a city. This algorithm looks at the "positive soup" bowls and asks, "What is the cheapest, most logical way to connect the starting point to at least one person in every bad soup bowl?"
- The Trick: It treats the problem like connecting dots on a map. It ignores the people who are definitely healthy (negative soup) and tries to build a bridge to the sick people using the fewest "steps" (infections) possible.
- Result: It does a much better job than just guessing randomly or assuming everyone in a bad soup bowl is sick.
RoundCascade (The One-Step Guess):
- How it works: This is for a simpler scenario where the virus only spreads one step (like a parent infecting their kids in a single day).
- The Trick: It uses a technique called "Randomized Rounding." Imagine you have a list of probabilities (e.g., "There's a 70% chance Person A is sick"). Instead of making a hard yes/no decision, the algorithm rolls a virtual die. If the die roll is lower than 70%, it marks them as sick. It does this in a way that ensures the math stays balanced.
- Result: It's surprisingly accurate at finding the hidden sick people even with noisy data.

Why Does This Matter?

The authors tested their methods on real-world data, including a network of patients in a hospital ICU and a simulated small city.

The Good News: Their methods found the hidden sick people much better than the old "guess one person" methods.
The Catch: If the virus spreads very fast (like a wildfire), the "group soup" becomes so full of sick people that the algorithm gets confused and might miss some details. But for most realistic scenarios, it works great.

The "Noise" Warning

The paper also warns about Noisy Data. Imagine if your soup test sometimes says "Bad" when it's actually "Good" (a false alarm).

The Lesson: Even a tiny bit of noise can completely change the detective's conclusion. The algorithm might point to a completely different path of infection than what actually happened. This shows that while group testing is powerful, we need to be very careful about how accurate our tests are.

In a Nutshell

This paper teaches us how to solve a massive "Where's Waldo?" puzzle when we only have blurry group photos. By using clever math tricks (Group Steiner Trees and Linear Programming), the authors created a system that can look at a few group test results and reconstruct the likely path of an outbreak much better than previous methods. It's a vital tool for public health, helping us understand how diseases spread without needing to test every single person in the world.

1. Problem Definition

The paper addresses the challenge of reconstructing disease transmission cascades (outbreaks) on a network when only group surveillance data is available, rather than individual test results.

Context: In scenarios like wastewater monitoring, bioaerosol sampling, or pooled testing, samples from multiple individuals (a "pool") are tested together.
- A negative result clears all individuals in that pool.
- A positive result indicates at least one individual in the pool is infected, but does not identify which one(s).
The Gap: Previous work on cascade reconstruction (Maximum Likelihood Estimation or MLE) assumed individual testing (pool size = 1). This paper generalizes the problem to arbitrary pool sizes.
Formal Problem (PoolCascadeMLE): Given an undirected network $G$ $G$ , a known seed node (or unknown seeds in the one-hop case), and a set of pools $\Gamma$ $Γ$ with binary outcomes ( $\Gamma_1$ $Γ_{1}$ = positive, $\Gamma_0$ $Γ_{0}$ = negative), find a cascade subgraph $T_r$ $T_{r}$ rooted at the seed that:
1. Consistency: Contains no nodes from negative pools ( $\Gamma_0$ ) and at least one node from every positive pool ( $\Gamma_1$ ).
2. Optimality: Maximizes the likelihood of the observed data under the Independent Cascade (IC) disease model. This is equivalent to minimizing a specific cost function derived from edge transmission probabilities and non-infection probabilities.

2. Methodology

The authors propose algorithms for two variations of the problem: the general multi-step spread and a restricted one-step spread.

A. Hardness Results

PoolCascadeMLE: Proven to be NP-hard to approximate within a factor of $O(\log^{2-\epsilon} k)$ , where $k$ is the number of positive pools. This is a significant increase in hardness compared to the individual testing case (which allows $O(\log k)$ approximation).
One-HopCascadeMLE: Proven to be NP-hard to approximate within $O(\log k)$ , reduced from the Minimum Set Cover problem.

B. Algorithm for General Case: `ApproxCascade`

To solve the general PoolCascadeMLE problem, the authors reduce it to the Group Steiner Tree (GST) problem.

Transformation: They construct a weighted graph $G'$ $G^{'}$ from the original network.
- Nodes are assigned weights based on the cost of not infecting neighbors (derived from $-\log(1-p_e)$ ).
- Edges are assigned weights based on the cost of transmission ( $-\log p_e$ ).
- Nodes in negative pools are removed.
Reduction: The problem becomes finding a minimum weight tree in $G'$ that connects the seed to at least one node in each positive pool group.
Approximation: They utilize the best-known approximation algorithm for the Directed Steiner Tree problem (via Charikar et al.) to solve the GST instance.
Performance: The algorithm achieves an approximation ratio of $O(k^\epsilon)$ with a time complexity of $O(k n^{1/\epsilon})$ .

C. Algorithm for One-Hop Case: `RoundCascade`

For the restricted case where the disease spreads only one time step (motivated by wastewater monitoring where mixing happens over a short period), they use Linear Programming (LP) relaxation and randomized rounding.

Integer Program: Formulate the problem with variables for seeding nodes and edge transmissions.
LP Relaxation: Relax binary constraints to continuous values $[0, 1]$ .
Randomized Rounding: Use a randomized rounding scheme (Algorithm 2) to convert fractional LP solutions back to binary decisions.
Performance: This yields a randomized $(2 + 2 \ln k)$ -approximation algorithm.

3. Key Contributions

Problem Formulation: Introduced PoolCascadeMLE, the first formal framework for MLE-based cascade reconstruction under group surveillance (pooled testing).
Theoretical Bounds: Established that the problem is significantly harder to approximate than the individual testing case due to the combinatorial layer of selecting which node in a positive pool is infected.
Algorithms:
- Developed ApproxCascade, a reduction-based approximation algorithm for general spread.
- Developed RoundCascade, an LP-based randomized rounding algorithm for one-hop spread.
Noise Analysis: Investigated the impact of noisy tests (false positives/negatives), showing that even small amounts of noise can drastically alter the MLE solution, potentially leading to solutions that share almost no overlap with the ground truth.

4. Experimental Results

The authors evaluated their methods on synthetic networks (Barabási-Albert, Erdős-Rényi) and real-world networks (UVA Hospital ICU contact network, a small city digital twin).

Metrics:
- Missing Infection Recovery: Measured via F1-score (comparing reconstructed nodes vs. ground truth).
- Prevalence Estimation: Measured via relative error in outbreak size.
Findings:
- Superiority: Both ApproxCascade and RoundCascade significantly outperformed baselines that reduced pools to size 1 (either by random selection or assuming all pool members are infected).
- Diffusion Probability: The proposed methods excelled in low-diffusion probability regimes. In high-diffusion regimes, the "All" baseline (assuming everyone in a positive pool is infected) sometimes performed better because the true cascade was large, but the proposed method still remained competitive.
- Pool Size: Performance degraded as pool size increased (expected due to exponential growth in possible subsets), but the proposed method maintained a clear advantage over baselines across various pool sizes.
- Prevalence: The methods generally underestimated outbreak size (typical for MLE) but remained within a reasonable error margin ( $[-0.5, 0.5]$ ), whereas baselines often massively overestimated.

5. Significance and Limitations

Significance: This work bridges the gap between theoretical epidemiology and practical public health surveillance. As wastewater and pooled testing become standard for monitoring outbreaks (e.g., COVID-19, H5N1), this paper provides the first rigorous mathematical tools to infer the underlying transmission network from such coarse-grained data.
Limitations:
- MLE Sensitivity: The paper demonstrates that MLE solutions can be highly unstable under noise; a single false negative in a pool can force the algorithm to choose a completely different, high-cost path to satisfy constraints.
- Pool Design: The current work assumes pools are given. A future direction identified is the co-optimization of pool design (which nodes to group) to maximize inference accuracy, rather than just reconstructing from fixed pools.

In summary, the paper establishes that reconstructing outbreaks from pooled data is computationally hard but solvable with approximation algorithms that significantly outperform naive strategies, offering a vital tool for modern, resource-constrained disease surveillance.