Reconstructing Network Outbreaks under Group Surveillance

0555-03-01 · Source: cs.MA updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics, Social Network Analysis · Depth: Advanced, extended

Summary

This paper introduces the \probPoolMLE problem, which focuses on reconstructing disease cascades from partial observations under group surveillance, such as wastewater or aerosol monitoring. Unlike previous methods that assume individual testing (pool size one), \probPoolMLE accounts for pooled samples where a positive test indicates at least one infected individual within the group, adding combinatorial complexity. The authors demonstrate that \probPoolMLE is NP-hard under the Independent Cascade (IC) model and propose an approximation algorithm, ApproxCascade, based on a reduction to the Group Steiner Tree problem. They also analyze a one-hop variant, One-HopCascadeMLE, which is also NP-hard, and develop a method, RoundCascade, using linear programming relaxation and rounding. Experimental evaluations on synthetic and real contact networks, including a UVA Hospital ICU network, show that their methods significantly outperform baselines in missing infection recovery and prevalence estimation, especially under low diffusion probabilities.

Key takeaway

For AI Researchers and Public Health Analysts working on epidemic modeling, understanding the \probPoolMLE problem is crucial for accurate outbreak reconstruction from group surveillance data. Your current methods, often assuming individual testing, may be insufficient. Implement approximation algorithms like ApproxCascade or RoundCascade to improve missing infection recovery and prevalence estimation, especially when dealing with low diffusion rates or one-hop spread scenarios, but be mindful of increased pool sizes degrading performance.

Key insights

Reconstructing network outbreaks from pooled surveillance data is NP-hard, requiring approximation algorithms.

Principles

• Group surveillance adds combinatorial complexity to outbreak reconstruction.
• MLE solutions can differ significantly from ground truth under noisy testing.
• Overlapping tests may be more powerful for epidemic reconstruction.

Method

The \probPoolMLE problem is approximated by reducing it to the Group Steiner Tree problem. For One-HopCascadeMLE, a randomized rounding approach on an LP relaxation is used.

In practice

• Use ApproxCascade for low diffusion probability outbreaks.
• Consider RoundCascade for one-hop disease spread scenarios.
• Be aware of performance degradation with larger pool sizes.

Topics

• Cascade Reconstruction
• Group Surveillance
• Combinatorial Optimization
• Independent Cascade Model
• Approximation Algorithms

Best for: AI Researcher, AI Scientist, Research Scientist

Related on AIssential

• Amplifying Membership Signal Through Chained Regeneration — Chained regeneration amplifies membership signals in generative models, improving privacy auditing.
• Understanding Key Features of Time Series Foundation Models from Epidemic Forecasting — Heterogeneous pretrained representations improve epidemic forecasting, especially with aligned pretraining domains.
• Retrying vs Resampling in AI Control — Retrying protocols are vulnerable to exploitation via information leakage, whereas resampling offers cost-effective safety gains when optimized.
• Epidemiology of Model Collapse: Modeling Synthetic Data Contamination via Bilayer SIR Dynamics — AI model collapse from synthetic data cross-contamination can be modeled as a bilayer epidemic system with a quantifiable reproduction number R₀.
• A Zero-shot Generalized Graph Anomaly Detection Framework via Node Reconstruction — AlignGAD enables zero-shot graph anomaly detection across diverse domains by unifying features and leveraging reconstruction discrepancy.
• DEpiABS: Differentiable Epidemic Agent-Based Simulator — DEpiABS is a differentiable agent-based model that balances mechanistic detail, computational efficiency, and interpretability for epidemic simulation.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.MA updates on arXiv.org.