2021 IEEE International Conference on Acoustics, Speech and Signal Processing
6-11 June 2021 • Toronto, Ontario, Canada
Extracting Knowledge from Information
| Paper ID | SPTM-19.4 | ||
| Paper Title | Two-stage Graph-constrained Group Testing: Theory and Application | ||
| Authors | Saurabh Sihag, Ali Tajer, Rensselaer Polytechnic Institute, United States; Urbashi Mitra, University of Southern California, United States | ||
| Session | SPTM-19: Inference over Graphs | ||
| Location | Gather.Town | ||
| Session Time: | Friday, 11 June, 11:30 - 12:15 | ||
| Presentation Time: | Friday, 11 June, 11:30 - 12:15 | ||
| Presentation | Poster | ||
| Topic | Signal Processing Theory and Methods: [SIPG] Signal and Information Processing over Graphs | ||
| IEEE Xplore Open Preview | Click here to view in IEEE Xplore | ||
| 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 $\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. | ||