| 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 |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| 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. |
