Two-Stage Graph-Constrained Group Testing: Theory And Application

This paper formalizes a graph-constrained group testing (GT) framework for isolating up to $k$ defective items from a population of $p$. In contrast to traditional group testing approaches, an underlying graphical model imposes constraints on how the items can be grouped for testing. The existing theories on graph-constrained GT consider one-stage, non-adaptive frameworks that can isolate the defective items perfectly with $\Theta(k^2M^2\log (p/k))$ tests, where $M$ is the mixing time associated with the graph. This paper, in contrast, formalizes an {\em adaptive}, {\em two-stage} framework that requires $\Theta(kM^2\log (p/k))$ tests, that is, a factor $k$ smaller than that of the one-stage (non-adaptive) frameworks. The theoretical results established for the two-stage framework are also evaluated empirically. Furthermore, this framework is extended to address the problem of anomaly detection in the network, where \s{based on the samples from probability distributions conforming to a location-scale family}, the decision rules for detecting a defective vertex are characterized.