Title: Permutation Tests for Infection Graphs,
Abstract: We formulate and analyze a novel hypothesis testing problem for inferring the
edge structure of an infection graph. In our model, a disease spreads over a
network via contagion or random infection, where the random variables governing
the rates of contracting the disease from neighbors or random infection are
independent exponential random variables with unknown rate parameters. A subset
of nodes is also censored uniformly at random. Given the statuses of nodes in
the network, the goal is to determine the underlying graph. We present a
procedure based on permutation testing, and we derive sufficient conditions for
the validity of our test in terms of automorphism groups of the graphs
corresponding to the null and alternative hypotheses. Further, the test is
valid more generally for infection processes satisfying a basic symmetry
condition. Our test is easy to compute and does not involve estimating unknown
parameters governing the process. We also derive risk bounds for our
permutation test in a variety of settings, and motivate our test statistic in
terms of approximate equivalence to likelihood ratio testing and maximin tests.
We conclude with an application to real data from an HIV infection network.