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

Saurabh Sihag, Ali Tajer, Urbashi MitraICASSP 2021 · OpenReview

Abstract

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 Θ(k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log(p/k)) tests, where M is the mixing time associated with the graph. This paper, in contrast, formalizes an adaptive, two-stage framework that requires Θ(kM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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 based on the samples from probability distributions conforming to a location-scale family, the decision rules for detecting a defective vertex are characterized.
BibTeX
@inproceedings{sihag2021two,
  author = {Saurabh Sihag and Ali Tajer and Urbashi Mitra},
  title = {{Two-Stage Graph-Constrained Group Testing: Theory and Application}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=Cod6npUfGzQ},
}

Loading related content...

Figure