Testing Infection Graphs

We study the following problem: given two graphs G_0 and G_1 defined on a common set of n vertices and a single observation of the statuses of these vertices, i.e. either infected, uninfected, or censored, did the infection spread on G_0 or G_1? Modern instances of such ``infections'' include diseases such as HIV, behaviors such as smoking, or information such as online news articles. For particular stochastic spreading mechanisms, we give algorithms for this testing problem based on hypothesis discretization and permutation-invariance. Additionally, these methods also lead to confidence sets for parameters that also govern the spread of infection and for the graphs on which the infection spread.