Finding Patient Zero: Learning Contagion Source with Graph Neural Networks

Abstract

Locating the source of an epidemic, or patient zero (P0), can provide critical insights into the infection's transmission course and allow efficient resource allocation. Existing methods use graph-theoretic centrality measures and expensive message-passing algorithms, requiring knowledge of the underlying dynamics and its parameters. In this paper, we revisit this problem using graph neural networks (GNNs) to learn P0. We establish a theoretical limit for the identification of P0 in a class of epidemic models. We evaluate our method against different epidemic models on both synthetic and a real-world contact network considering a disease with history and characteristics of COVID-19. % We observe that GNNs can identify P0 close to the theoretical bound on accuracy, without explicit input of dynamics or its parameters. In addition, GNN is over 100 times faster than classic methods for inference on arbitrary graph topologies. Our theoretical bound also shows that the epidemic is like a ticking clock, emphasizing the importance of early contact-tracing. We find a maximum time after which accurate recovery of the source becomes impossible, regardless of the algorithm used.

References in corpus (20)

• Statistical mechanics of complex networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Epidemic spreading in scale-free networks
• Neural Message Passing for Quantum Chemistry
• Epidemic processes in complex networks
• Geometric deep learning: going beyond Euclidean data
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Random Geometric Graphs
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Neural Relational Inference for Interacting Systems
• Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation
• Benchmarking Graph Neural Networks
• Bayesian inference of epidemics on networks via Belief Propagation
• Deep Learning on Graphs: A Survey
• The Emergence of Consensus: A Primer
• Optimal Containment of Epidemics in Temporal and Adaptive Networks
• Identification of Patient Zero in Static and Temporal Networks - Robustness and Limitations
• Confidence Sets for the Source of a Diffusion in Regular Trees
• Learning Temporal Point Processes via Reinforcement Learning

Cited by in corpus (4)

• Sequential Attention Source Identification Based on Feature Representation
• Schemes of Propagation Models and Source Estimators for Rumor Source Detection in Online Social Networks: A Short Survey of a Decade of Research
• Geometric characterization of SARS-CoV-2 pandemic events
• Social Diffusion Sources Can Escape Detection