Group Testing with Correlation under Edge-Faulty Graphs

We start by motivating the key attributes that we capture in our model through an example of testing for infections in a network of people (nodes). Consider the interaction network for the spread of an infectious disease (e.g. COVID-19) in a network of people/nodes. There is an edge between two nodes if the corresponding individuals are in physical proximity for a minimum amount of time each week. Such individuals are more likely to be in the same state than those who have been distant throughout. Thus, firstly, the probability of being in the same state decreases with increase in the length of paths (i.e., distance in interaction network) between nodes. Second, infection is more likely to spread from one node to another if there are many distinct paths between them. Thus, the probability that two nodes are in the same state increases with the increase in the number of distinct paths between them.

We capture correlation through a faulty-edge graph model. Consider a graph $G=(V,E)$ where the node set $V$, $|V|=n$, represents the items and the edge set $E$ represents connections/correlations between them. Suppose each edge is realized with probability $0\leq r\leq 1$. After the sampling, we have a random graph that we denote by $G_{r}$. Each node is either defective or non-defective. All nodes in the same component of $G_{r}$ are in the same state, rendering defectiveness a component property. We consider that each component is defective with probability (w.p.) $p$ independent of others. As an example, consider graph $G$ with five nodes and eight edges, and a sampled graph realization $G_{r}$ as shown in Figure 1 (left) and Figure 1 (right) respectively. When $r=1/3$, $G_{r}$ is realized w.p. $(\frac{1}{3})^{3}(\frac{2}{3})^{5}$. There are two components in $G_{r}$, namely, $v_{1},v_{4},v_{5}$ and $v_{2},v_{3}$; $v_{1},v_{4},v_{5}$ are in the same state, which is defective w.p. $p$, independent of the state of $v_{2},v_{3}.$

Two nodes are guaranteed to be in the same state in $G_{r}$ if there exists at least one path that connects them in $G_{r}$. The probability that a path in $G$ survives in $G_{r}$ increases with increase in $r$. Thus both the parameter $r$ and the graph $G$ determine the correlation between states of different nodes; the correlation is higher if $r$ is higher, states of all nodes are independent for $r=0$, while the correlation is the highest possible for a given $G$ for $r=1.$

This model importantly captures the two attributes we discussed: Clearly, a long path between two nodes in $G$ has a smaller chance of survival in $G_{r}$, compared to a short path, making the end nodes less likely to be in the same state as the length of the path in $G$ between them increases. Moreover, the probability that at least one path between two nodes survive in $G_{r}$ increases with increase in the number of distinct paths between them in $G$, so having distinct paths between a pair of nodes in $G$ makes them more likely to be in the same state.

We aim to find the minimum expected number of tests needed to find the defective items with at most $\epsilon n$ errors, where $\epsilon$ can potentially be of order $o(1)$. To be precise, let #ERR(H) be the number of nodes mispredicted by an algorithm on graph $H$. Then we require to have

where the expectation is taken over $G_{r}$ and possible randomization of the algorithm. We refer to it as the average error.

Methodologically, we relate the problem of group testing with correlation to that in a network with fewer nodes in which the states of nodes are independent. We obtain bounds on the number of group tests required in the former, to satisfy the constraints we consider on errors, in terms of known bounds in the latter. The relative quantification provides a basis for comparison and determination of the improvements that can be obtained by exploiting correlation.

The tests can not be designed with the knowledge of $G_{r}$, only the value of $r$ is known apriori. In the extreme case of $r=0$, the problem is reduced to the classic group testing with $|V|=n$ independent nodes. In the extreme case of $r=1$, all components of $G$ remain connected and have the same state and hence the problem is reduced to testing a single node. When $0<r<1$, the problem is non-trivial, because there can be multiple components, some with more than one node, and the number and composition of the components is apriori unknown. Thus, it is not apriori known which nodes will be in the same state. Our group testing strategies will seek to circumvent this challenge by identifying parts of $G$ that are connected enough so that they remain connected in $G_{r}$ with a high probability.

We obtain upper and lower bounds on the number of group tests needed to determine the states, defective or otherwise, of individual nodes in a large class of interaction graphs in the presence of correlation among the states of nodes. We progressively consider 1) cycles and trees (about $n$ links), 2) $d-$regular graphs (about $dn/2$ links) and 3) stochastic block models or SBM (with potentially $\Theta(n^{2})$ links). The correlation is captured by the factor $r$ (see Section 1.1). The bounds are obtained in terms of the number of tests needed when the states are independent, and help us quantify the efficiency brought forth by group testing in terms of $r.$ In particular, our group testing strategies exploit correlation and build upon classical group testing strategies, but with fewer number of nodes. The ratio between this number and the total number of nodes ($n$) determines the benefits of correlation in our strategies and we refer to it as the (multiplicative) improvement factor. Note that this is not the ratio between the number of tests that are needed, but the ratio between the number of nodes that a classical group testing algorithm gets as input. As such, our results are valid for any group testing algorithm, and they can be translated to the ratio between the total number of tests, accordingly, as needed.

For trees and cycles, we prove an upper bound on the optimal number of tests in terms of the number of group tests when there are $n\log(1/r)$ independent nodes. Note that one can trivially determine the states of each node by disregarding correlation and testing among $n$ nodes (e.g. using classic group testing techniques). Our upper bound therefore shows that group testing can reduce the tests. The (multiplicative) improvement factor of $\log(1/r)$ is meaningful (less than 1) when $r>1/2$. As $r$ approaches $1$ the multiplicative factor reduces even further implying even greater benefits due to group testing. Our lower bound, on the other hand, shows an improvement factor $(1-r)$.

For $d-$regular graphs, we prove new results for the distribution of components. This leads to a lower bound that is expressed as a sum series depending on $r$ and $n$. We further prove an upper bound for a specific $4-$regular graph, namely grid, in terms of the number of group tests when there are $n{(1-r)\log(1/r)}$ independent items. Thus, the improvement factor is ${(1-r)\log(1/r)}$, as opposed to only $\log(1/r)$ for trees; this hints us that group testing gets drastically more efficient for denser graphs.

The stochastic block model divides the network into communities such that nodes in the same community are more connected than nodes in different communities. We show that the reduction in the test count due to group testing can be classified into three regimes: 1) strong intra-community connectivity but sparse inter-community connectivity, which reduces the effective number of independent nodes to the number of communities, 2) strong connectivity leading to an (almost) fully connected graph, in which case all nodes have the same state and one independent test is representative 3) sparse connectivity leading to many isolated nodes, in which case the states of all nodes are independent. The first case reduces to independent group testing with the number of nodes equal to the number of communities, second regime needs a constant number of tests, and finally the third regime reduces to independent group testing with $n$ nodes. The tight upper and lower bounds that are known in the literature for the independent group testing subsequently apply for the first and third cases; for the second case, the analysis is rather simple as there is only a constant number of tests needed.

We now briefly describe the mathematical techniques that we follow to obtain the bounds. The techniques constitute a contribution in themselves as a graphical structure was not investigated earlier for group testing except under significant restrictions as described earlier. For the upper bound for a cycle, we divide the cycle $G$ into subgraphs of size $l$ ($l$ nodes) where $l$ is a parameter. The subgraphs are connected in $G$, but need not be connected in $G_{r}$ which we do not know apriori. For every subgraph, we select a node which we consider as representative of the subgraph and determine the states of the representatives of all the subgraphs using group testing strategies deployed when states of nodes are independent (ie, we do not exploit possible correlation between the representatives). We consider the state of each node in each subgraph as that of the representative; this is indeed the case if each subgraph is connected, otherwise the state of some nodes are determined in error. The probability of each subgraph being connected decreases with increase in $l$, thus the expected number of errors, which can be computed as a function of $r,l,n$, increases with increase in $l.$ The number of representatives and therefore the number of nodes subjected to group tests described above is $n/l$. Thus the number of group tests is non-increasing with $l.$ Thus $l$ represents a tradeoff between the expected number of errors and the number of group tests, and $l$ is selected appropriately to ensure a low number of group tests subject to ensuring that the expected number of errors does not exceed the specified limit. The number of group tests for the $l$ that satisfies the specified error constraints provides the upper bound on the number of tests for a cycle.

The upper bound for an arbitrary tree can be obtained similarly, with the additional significant complication that for an arbitrary tree $G$ and an $l$ that satisfies constraints on error one may not be able to obtain subgraphs in $G$ of size $l$ that are connected in $G$ (in contrast when $G$ is a cycle, a path of size $l$ constitutes such a subgraph). Refer to Figure 2 for an illustration of this challenge. We get around this challenge by using subgraphs that are not connected in $G$ by themselves, but become connected in $G$ through at most $l$ additional nodes in $G$ (which are not in the subgraph). Construction of such subgraphs is not apriori clear and constitutes an innovation needed for upper bounding the number of tests needed for trees, above and beyond the overall methodology. Each such subgraph is connected in $G_{r}$ if the links in $G$ among these $2l$ nodes survive in $G_{r}$, the probability of this event can again be expressed as a function of $l,r$, and as before this probability decreases with increase in $l.$ The rest of the methodology is similar to for cycles.

The overall methodology for obtaining the upper bound for grids is the same as that for cycles. The subgraphs in question constitute sub-grids of $l$ nodes. We determine the probability that each such sub-grid is connected in $G_{r}$ through a recursive decomposition which is not apriori obvious.

The characterization of lower bound on the number of tests needed for cycle or trees constitutes another innovation. To obtain the lower bound one can assume the knowledge of the components of $G_{r}$, which one does not know in reality. Nodes in each component of $G_{r}$ have the same state, which is independent of those of the states of nodes in other components. Thus each component can be considered a super-node and the states of the super-nodes are independent of each other. Thus, one needs at least as many tests as that when there are $C(G_{r})$ nodes whose states are independent, where $C(G_{r})$ is the number of components of $G_{r}$. A lower bound can now be obtained if the random variable $C(G_{r})$ can be bounded. We accomplish this objective by observing that number of components in a stochastic graph constitutes an edge-exposure martingale and the value of this random variable is concentrated around its expectation, courtesy of Azuma’s inequality which holds for such martingales.

We initially present the above results for constraints on the expected number of errors. We subsequently generalize them for a stronger constraint, that on the number of errors with a high probability (rather than expectation thereof), for cycle and trees. Lower bounds can be obtained following the same methodology as before, except that lower bounds on the number of tests needed for independent nodes for this stronger constraint do not exist in the literature. We derive the latter lower bound first, adapting some existing proof techniques relying on Information-theoretic inequalities. We show that the lower bounds can be improved for some specific structures of $G$, such as when $G$ is a star. This stronger notion of error allows us to include the structure of $G$ more heavily and directly in this proof, rather than going via an analysis for the number of components. We have resorted to the latter in obtaining the lower bounds for cycle, tree for the weaker constraint on errors. The upper bound can be obtained following the same broad structure, though some additional technical challenges arise. The number of errors over all subgraphs can be bounded with high probability using Hoeffding’s inequality if the number of errors in different subgraphs are independent. This happens for cycle the subgraphs are non-overlapping paths and the events that they remain connected in $G_{r}$ are independent. Nonetheless, this does not happen for trees because nodes in one subgraph may be connected through those in other subgraphs. We surmount this technical challenge by invoking an innovative exposure of nodes of the tree such that the number of connected subgraphs constitutes a node exposure Martingale which satisfies the requisite Lipschitz condition for Azuma’s inequality to hold. The high probability bound on the number of errors over all subgraphs now follow via Azuma’s inequality.

Note that the number of components $C(G)$ is edge Lipschitz, as when two graphs differ in only one edge, they either have the same number of components, or the graph with one less edge has one additional component. One can define a node Lipschitz condition by replacing edge with node [AS16].

We then have Azuma’s inequality.

Lemma 2.1 provides a lower bound on CrltOPT in terms of IndepOPT. Indeed, any lower bound on the latter leads to a lower bound on the former. We now review some useful lower and upper bounds on $\textsc{IndepOPT}(G,r,p,\epsilon)$ next.

In the probabilistic group testing of [LCH⁺14], there are $n$ individuals and every individual $i$ is independently defective with probability $p_{i}$. Let $\mathbf{X}$ be the indicator vector of the items’ defectiveness and $H(\mathbf{X})=\sum_{i}p_{i}\log\frac{1}{p_{i}}$ be the entropy of $\mathbf{X}$. The testing can be adaptive or non-adaptive, meaning the testing at each step can depend on the results of the previous tests, or not, respectively. [LCH⁺14] proves the following lower bound on the required number of tests (for both adaptive and non-adaptive scenarios)

For the upper bounds in this paper, roughly speaking, we partition the graph into groups of nodes and assume that the state of nodes in different groups are independent. Subsequently we obtain bounds for group testing on the original graph in terms of those when state of nodes are independent. We therefore utilize the existing bounds for smaller networks in our context. Below, we summarize the probabilistic group testing results of [LCH⁺14] for upper bounds on number of tests needed when items are independent.

By Corollary 2.6, if we know the expected number of components in a graph, we would be able to lower bound the minimum number of tests needed by Lemma 2.1. The following theorem proves a lower bound for cycle and trees.

The above proof also works for any graph with $n+c$ edges, where $c$ is a constant. In other words, when the number of edges is less than $n+c$, a lower bound on the number of tests needed for almost $(1-r)n$ independent nodes is also a lower bound on the number of tests needed under our model with correlation $r$.

In this section, we provide algorithms to find the defective set and provide theoretical bounds. We start by considering that $G$ is a simple cycle, and subsequently generalize the ideas to arbitrary trees. Note that after having an algorithm for trees, we would have an algorithm for general graphs, by just considering a tree spanning it. But the algorithm might be far from optimal.

The general idea is to partition the graph $G$ into subgraphs that will remain connected in $G_{r}$ with high probability. The nodes in those connected subgraphs will thus have the same states. We can then select a candidate node for each subgraph to be tested. By knowing the probability of each subgraph being connected and the probability of error in classic group testing, we can estimate the error in our problem as a function of the size of the subgraphs and design the subgraphs accordingly.

First, we provide our results for when $G$ is a cycle.

We now generalize the ideas to derive an upper bound when $G$ is a tree. We partition $G$ into $\lceil n/l\rceil$ subgraphs (which we sometimes refer to as groups) of $l$ nodes, find the probability of each subgraph being connected in a random realization, and then optimize it by choosing $l$. At a high level, we partition $G$ such that the nodes within a subgraph have small paths among each other. This is because shorter paths remain connected in $G_{r}$ with higher probability, maximizing the probability of the nodes being in the same state. Finding the probability of error is not straightforward here, because the subgraphs we form may not necessarily be connected in the original graph $G$ but could be connected through realization of other edges/nodes.

We first give a definition to formalize the number of nodes needed to make a subset of nodes connected.

Note that if $G$ is a tree, then every connected subgraph of $G$ is also a tree. And the number of links in the induced graph over $S\cup S^{\prime}$ is one less than the number of nodes in it.

Now we provide a partition of nodes for trees such that for each subgraph, only a few additional nodes and thereby additional links will make them connected. Formally:

Now we are ready to prove the upper bound for trees.

We first formally define a grid. A grid with $n$ nodes and side length $\sqrt{n}$ is a graph where nodes are in the form of $(a,b):1\leq a,b\leq\sqrt{n}$. Node $(a,b)$ is connected to its four close neighbors (if exist), namely $(a-1,b),(a+1,b),(a,b+1),(a,b-1)$. Border nodes (with $a\in\{1,\sqrt{n}\}$ or $b\in\{1,\sqrt{n}\}$) might have three or two neighbors. Note that the side length is defined by number of nodes on the side.

In order to derive a lower bound, we need to know the expected number of components in $G_{r}$ and equivalently the expected component size that nodes belong to [AS16, Goe97]. To find the expected component size, we describe a random process that forms the components and analyze the expected stopping time. While this is well-known for ER graphs, to the best of our knowledge there are no bounds when the graph is not complete. We derive a lower bound on the expected number of components in a grid by analyzing the problem for 3-regular infinite trees. This approach can be generalized for any $d$-regular graph.

Consider the following process. Pick a node $v\in V(G)$, mark it as processed, and let it be the root of a tree. For each $u\in V(G)$ that is not processed and is a neighbor of $v$, $uv$ is realized with probability $r$ and added as a child of $v$. The same process is repeated for each realized $u$ in a Breath First Search (BFS) order. When the process ends, there is a tree with root $v$, and the expected size of the tree is the expected size of the component that $v$ ends up in.

An example of this proecss is shown in Figure 4. Node $v_{11}$ is the root (colored in blue), the children that are realized are marked in green, and the children that are not realized are marked in red. The component would be $\{v_{11},v_{12},v_{7},v_{2}\}$.

By repeating the process for each node that is not processed yet, we get a spanning forest. The expected number of components in the forest is the expected number of components in the original random graph.

Here, the challenge is that we don’t know the number of available (unprocessed) neighbors of a node. It highly depends on the previously chosen nodes, especially when $d$ is small, like in the grid. Note that this is more complicated than the process for ER graphs, as the number of unprocessed neighbors in an ER graph is independent of the previously processed nodes (due to its homogeneous nature). We circumvent this issue by analyzing an infinite regular tree process that effectively corresponds to a more connected graph and therefore leads to a lower bound on the expected number of connected components for the grid.