PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-Constrained Group Testing

Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer, Venkatesh Saligrama

arXiv:1001.1445v2cs.DMcs.ITmath.IT

TL;DR

The paper formalizes group testing when pools must follow graph constraints, a setting motivated by applications such as network tomography and sensor networks. It develops random-walk-based test designs and proves disjunctness guarantees for specified graph classes, with measurement bounds depending on the design and graph parameters.

  • Problem

    The paper asks how to identify at most d defective vertices or edges when each measurement is restricted to items observed along a graph path.

    Source: §III · p. 5

  • Method

    The paper constructs graph-constrained tests from random walks, with each test row recording the vertices visited by a walk.

    Source: C. Infection Propagation · p. 3

  • Results

    For constant-gap D-regular expanders or G(n,D/n), four designs yield (d,e)-disjunct matrices with high probability using m1,m2 = O(d^2(log^3 n)/(1−η)^2), m3 = O(d^3(log^5 n)/(1−η)^2), and m4 = O(d^3D(log^5 n)/(1−η)^2) measurements.

    Source: §III · p. 7

  • Takeaways & Limitations

    The results establish test-design guarantees for identifying defective vertices or edges under graph-path constraints on the specified graph classes.

    Source: §III · pp. 5, 7

Abstract

from arXiv · show

Non-adaptive group testing involves grouping arbitrary subsets of $n$ items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most $d$ defective items. Motivated by applications in network tomography, sensor networks and infection propagation, a variation of group testing problems on graphs is formulated. Unlike conventional group testing problems, each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper, a test is associated with a random walk. In this context, conventional group testing corresponds to the special case of a complete graph on $n$ vertices. For interesting classes of graphs a rather surprising result is obtained, namely, that the number of tests required to identify $d$ defective items is substantially similar to what is required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph $G$, it is shown that with $m=O(d^2T^2(n)\log(n/d))$ non-adaptive tests, one can identify the defective items. Consequently, for the Erdos-Renyi random graph $G(n,p)$, as well as expander graphs with constant spectral gap, it follows that $m=O(d^2\log^3n)$ non-adaptive tests are sufficient to identify $d$ defective items. Next, a specific scenario is considered that arises in network tomography, for which it is shown that $m=O(d^3\log^3n)$ non-adaptive tests are sufficient to identify $d$ defective items. Noisy counterparts of the graph constrained group testing problem are considered, for which parallel results are developed. We also briefly discuss extensions to compressive sensing on graphs.

I. INTRODUCTION

The paper formalizes graph-constrained group testing, where pools must obey graph-imposed path constraints. This new test-design problem is motivated by applications including network tomography, sensor networks, and infection propagation.

I. INTRODUCTION

  • Network tomography, sensor networks, and infection propagation motivate the graph-constrained problem.The paper introduces the problem in response to these application settings.Source: §I · p. 1
  • Conventional group testing permits arbitrary test matrices, with best-known pooling using O(d^2 log(n/d)) rows and an almost-matching lower bound of Ω(d^2(log n)/(log d)).The optimal test size remains open.Source: §I · p. 1
  • The paper formalizes graph-constrained group testing, requiring each pool to form a path-connected vertex set or a path of links while identifying at most d defective items.The authors describe the problem as not previously addressed to their knowledge.Source: §I · p. 1

A. Network Tomography & Compressed Sensing over Graphs

Network tomography identifies congested links from end-to-end path measurements. The paper connects this task to graph-constrained group testing and notes implications for compressive sensing on graphs.

A. Network Tomography & Compressed Sensing over Graphs

  • A few congested links along a route may cause packet losses, and locating them is sufficient for most practical applications.The network is modeled as routers or hosts connected by communication links; routes must follow paths in that graph.Source: A. Network Tomography & Compressed… · p. 2
  • Because only routes that form paths in the given network are valid, the measurement question is how many are needed to identify congested links.End hosts send packets along assigned routes, and a central server receives the measurement results.Source: A. Network Tomography & Compressed… · p. 2
  • Random-walk paths produce a routing matrix that, for suitable choices of measurements and studied graphs, has expander-matrix properties and a suitable 1-RIP.These properties are sufficient for recovering sparse vectors with ℓ1 optimization, giving the results implications for compressive sensing on graphs.Source: A. Network Tomography & Compressed… · p. 2

B. Sensor Networks

Wireless sensor networks have changing routes constrained by an underlying network topology. Monitoring may be passive or active, with different ways of detecting and locating trouble spots.

B. Sensor Networks

  • In passive monitoring, sensor nodes form a sink-directed routing tree that changes unpredictably while remaining consistent with the network connectivity.Large packet arrival times indicate at least one defective sensor node or congested link.Source: B. Sensor Networks · p. 2
  • Passive monitoring seeks to locate defective links or sensor nodes from packet arrival times at the sink.A test is positive when arrival time is significantly large.Source: B. Sensor Networks · p. 2
  • Active monitoring uses summarized network information, such as average or maximum energy, before invoking a more energy-consuming procedure to locate trouble spots.The lower-level procedure is used when high-level information indicates congested links.Source: B. Sensor Networks · p. 2

C. Infection Propagation

The paper frames infection propagation and network tomography as graph-constrained group testing, then analyzes pools generated by random walks. It gives test bounds for fixed-length and source-to-sink walks, alongside noisy variants.

C. Infection Propagation

  • In the infection-propagation model, agents contact people along a random geometric graph, and the goal is to identify infected individuals from the agents’ test outcomes.After contacting an infected person, an agent has a chance of becoming infected; the model constrains subsequent contacts to nearby people.Source: C. Infection Propagation · p. 2
  • For wireless sensor network tomography, changing routes are drawn from the connectivity graph, so repeated tests between a sensor and sink can provide new information.This contrasts with the wired setting, where fixed routing makes the test matrix deterministic and the question is whether it permits identification.Source: C. Infection Propagation · pp. 2–3
  • Each random-walk test uses the vertices visited by that walk as a pool, with walks starting at a random or arbitrary node and ending after a chosen number of steps.The walk length is optimized for the graph classes considered.Source: C. Infection Propagation · p. 3
  • m = O(d^2T^2(n) log(n/d)) tests suffice for fixed-length walks; Erdős-Rényi graphs with p = Ω((log^2 n)/n) and constant-spectral-gap expanders require O(d^2 log^3 n) tests.T(n) is the graph’s mixing time; the bound is described as similar to conventional group testing, with an additional graph-topology term.Source: C. Infection Propagation · p. 3
  • m = O(d^3 log^3 n) source-to-sink walk tests suffice, and the cubic dependence on d cannot be improved for complete graphs.The source and sink may be arbitrary or uniformly random.Source: C. Infection Propagation · p. 3
  • Noisy graph-constrained tests also have parallel results when measurement outcomes are independently flipped with probability q < 1/2, with similar scaling for the dilution model.In the dilution model, an item may be diluted in each test with a known probability.Source: C. Infection Propagation · p. 3

II. DEFINITIONS AND NOTATION

The section establishes notation for boolean-vector operations, graph-consistent test matrices, and random walks. It also defines the graph properties and mixing-time quantities used in the paper’s analysis.

II. DEFINITIONS AND NOTATION

  • Boolean-vector notation uses element-wise OR, subtraction, and Hamming weight; vectors can also be read as characteristic vectors of sets.S \ T has a 1 where S has a 1 and T has a 0.Source: §II · p. 4
  • A d-disjunct matrix gives each column a row where it is 1 while any chosen d other columns are 0; (d,e)-disjunct matrices separate outcomes in at least e+1 positions.The latter notion supports noisy settings and tolerates up to floor((e−1)/2) incorrect outcomes without confusion.Source: §II · p. 4
  • A test matrix is vertex-consistent or edge-consistent when each row exactly represents vertices visited or edges traversed by a walk on the graph.A row may correspond to more than one walk, and a walk may revisit vertices or edges.Source: §II · p. 4
  • A graph is (D,c)-uniform when every vertex degree lies between D and cD; the paper also specializes results to Erdős-Rényi graphs and expander families with constant edge expansion.When c = 1, the graph is D-regular.Source: §II · pp. 4–5
  • Two distributions are δ-close when their point-wise distance is at most δ.The paper uses point-wise distance for its mixing-time definition.Source: §II · p. 4
  • T(n) is the δ-mixing time: after t steps, every walk starting at any vertex is within δ = (1/2cn)^2 of stationarity in point-wise ℓ∞ distance.The definition requires this closeness for all walk lengths τ ≥ t.Source: §II · pp. 4–5
  • For a walk, π_v and π_e denote the probabilities of passing a vertex or edge; related quantities track passing one while avoiding a specified set.The same kinds of probabilities are defined for walks that continue until reaching a fixed endpoint.Source: §II · p. 5

III. PROBLEM SETTING AND MAIN RESULTS

The section formalizes vertex and edge group testing with path-constrained measurements and presents random-walk designs. For expanders and Erdős–Rényi graphs, these designs attain the stated noisy disjunctness bounds.

Designs and guarantees

  • Each pool follows a graph path: the designs form measurement-matrix rows from vertices or edges visited by random walks.Designs may use fixed-length walks or walks that continue until reaching a sink.Source: §III · pp. 5–6
  • Random-walk Designs 1 and 3 produce vertex-consistent matrices, while Designs 2 and 4 produce edge-consistent matrices; their results include noiseless and noisy disjunctness guarantees.Designs 1 and 3 exclude designated-vertex columns, and Design 3 also excludes the sink, before asserting disjunctness.Source: §III · pp. 6–7

Qualification

  • Designs 1 and 3 require designated vertices to be nondefective, since their columns must be removed to ensure disjunctness.Without that restriction, a designated vertex may force an all-ones column and prevent even 1-disjunctness.Source: §III · p. 7

Main results

  • For constant-gap expanders and G(n,D/n), m1,m2=O(d^2 log^3 n/(1-η)^2), m3=O(d^3 log^5 n/(1-η)^2), and m4=O(d^3D log^5 n/(1-η)^2).Theorem 16 assumes D=Ω(d log^2 n) and gives (d,e)-disjunct matrices with e=Ω(ηd log n).Source: §III · p. 7

Fixed-input case

  • With fewer measurements, a matrix can distinguish a fixed d-sparse input from alternatives with high probability, but this does not guarantee worst-case separation of all sparse vectors.The paper describes the reduced count as almost a factor d smaller than the worst-case requirement.Source: §III · p. 7

Network tomography example

  • For source-based network tomography, Design 2 can identify congested links from packet routes, even when some outcomes are false if the measurement count is increased appropriately.The packet scheme chooses a hop count and can account for false outcomes by estimating the noise parameter and increasing measurements.Source: §III · p. 8

IV. PROOF OF THEOREMS 13 AND 17

This section develops random-walk probability bounds for disjunctness proofs and uses witness tuples to separate distinct candidate sets while establishing a measurement bound with vanishing failure probability. It also uses complete-graph examples to show limitations on improving the resulting bounds.

Preliminary propositions

  • The proof tools bound conditional unions, give 1/(cn)≤μ(v)≤c/n for non-bipartite uniform graphs [17], control repeated or early visits, and show near-independence after T(n) steps.Proposition 18 supplies the conditional-union bound; the walk controls include limits on repeated visits and early visits to non-designated vertices.Source: §IV · p. 8

Lemmas 24–25

  • For D=Ω(c^2dT^2(n)), Design 1 gives π_v,A=Ω(1/(c^4dT^2(n))); Design 2 has a corresponding edge bound with t2=O(nD/(c^3dT(n))).The vertex bound uses t1=O(n/(c^3dT(n))).Source: §IV · pp. 8, 10, 11

Lemmas 26–27

  • In Designs 3 and 4, D0=O(c^2dT^2(n)) suffices for lower bounds built from first-hit events that reach a target before the sink while avoiding the forbidden set.The vertex proof stages visits to v and then u before hitting A; the edge proof stages an edge visit and then a sink visit while avoiding B.Source: §IV · p. 10

Remarks 28–29

  • On the complete graph, π_v,A=O(1/d^2), so the quadratic dependence on d in Lemma 26 cannot generally be improved; the edge case likewise retains degree dependence.The vertex argument considers the ordering of first visits to A∪{u,v}; the edge argument considers first visits among B∪{e} and edges incident to the sink.Source: §IV · p. 11

Proof of Theorem 13

  • Independent random-walk rows and a union bound show that M is d-disjunct with overwhelming probability.The proof uses a per-row success probability π_v,A = Ω(1/(c^4dT^2(n))).Source: §IV · p. 11

Proof of Theorem 17

  • Theorem 17 follows the Theorem 13 proof except that its final union bound enumerates at most n choices of (v,A).For Design 1, the enumerated set is B={(v,A): v∈V\{s1,…,sr}, A=S\{v}}.Source: §IV · p. 11

IV. PROOF OF THEOREMS 13 AND 17

  • Witness tuples separate distinct candidate sets by giving rows where one set’s outcome is positive and the other’s is zero.The matrix has enough rows with v = 1 and all entries for A equal to zero, guaranteed with overwhelming probability by a union bound; witnesses are chosen from the set difference in either containment case.Source: §IV · pp. 11–12
  • ˜m = O(γm′_1) measurements ensure pf = o(1), a factor γ fewer than required by Theorem 13.The estimate is improved using the preceding separation argument.Source: §IV · p. 12

V. PROOF OF THEOREM 16

This section establishes mixing-time bounds for random graphs and expanders, using a theorem that relates a random walk’s distribution to the graph’s stationary distribution.

V. PROOF OF THEOREM 16

  • The section aims to show that both random graphs and constant-spectral-gap expanders have mixing time O(log n), then apply Theorem 13.The stated random-graph result holds with probability 1 − o(1).Source: §V · p. 12
  • The proof uses a theorem bounding the distance between a graph’s stationary distribution and the distribution after t random-walk steps.The walk may start at any node of an undirected graph.Source: §V · p. 12
  • The mixing bound’s stated graph parameters include the minimum and maximum degrees and conductance Φ(G).The theorem uses the graph’s stationary distribution as well.Source: §V · p. 12

A. The Erd˝os-R´enyi random graph

For sufficiently dense Erdős–Rényi random graphs, the section bounds conductance and uses it to establish logarithmic mixing time.

A. The Erd˝os-R´enyi random graph

  • When np ≥ (2/ϵ²) ln n, G(n, p) is (np(1 − ϵ), (1 + ϵ)/(1 − ϵ))-uniform with probability 1 − o(1).This supplies degree concentration used in the conductance argument.Source: A. The Erd˝os-R´enyi random graph · p. 12
  • For every ϕ < 1/2, choosing α sufficiently large gives Φ(G) ≥ ϕ for G(n, p) with p ≥ α ln n/n, with probability 1 − o(1).The section combines this conductance bound with a random-walk mixing theorem.Source: A. The Erd˝os-R´enyi random graph · p. 12
  • The conductance proof restricts attention to vertex subsets of size at most ηn and uses a union bound over candidate sets.The proof chooses α to make the probability bound for a fixed set at most n^-2i.Source: A. The Erd˝os-R´enyi random graph · p. 12
  • O(log n) is the δ-mixing time of G(n, p) for p ≥ α ln n/n, with probability 1 − o(1).For the specified δ, the section concludes T(n) = O(log n).Source: A. The Erd˝os-R´enyi random graph · p. 12

B. Expander Graphs with Constant Spectral Gap

A constant spectral gap yields logarithmic mixing time for expanders, while a separate technical argument bounds repeated counting in a probability sum.

B. Expander Graphs with Constant Spectral Gap

  • T(n) = O(log n) for an expander whose normalized second-largest eigenvalue is bounded away from 1 by a constant.The proof uses the connection between spectral gap, expansion, and conductance for regular graphs.Source: B. Expander Graphs with Constant… · p. 13
  • Theorem 16 follows by combining Theorem 13, Proposition 31, Corollary 33, and Lemma 34.Lemma 34 provides the expander mixing-time bound.Source: B. Expander Graphs with Constant… · p. 13

A. Proof of Proposition 18

  • If each sample-space element belongs to at most k of the sets B_i, the sum of their probabilities counts each element of B at most k times.This bounds the probability sum in the proof of Proposition 18.Source: A. Proof of Proposition 18 · p. 13

B. Proof of Proposition 19

The proof uses two properties of the graph: non-bipartite random walks converge to a stationary distribution, and uniform graphs have bounded degrees.

B. Proof of Proposition 19

C. Proof of Proposition 20

The proof samples a random walk at intervals of the graph’s mixing time. This yields a lower bound on the probability that the walk visits a given vertex.

C. Proof of Proposition 20

D. Proof of Proposition 21

These proofs bound walk visits and conditional probabilities using mixing and graph-degree properties. They also establish degree concentration and a mixing-time bound for the stated graph setting.

D. Proof of Proposition 21

  • The probability that the walk visits v at least k := (1 + αc^2)T(n) times is at most π_v/4 for sufficiently large constant α.The proof bounds the tail of the visit count using Markov’s inequality and Proposition 20.Source: D. Proof of Proposition 21 · p. 14

E. Proof of Proposition 22

  • For a non-designated vertex v, each walk step visits v with probability at most 1/D, and a union bound gives the stated claim.The initial-step bound uses uniform random initialization; subsequent steps use that each vertex has at least D neighbors.Source: E. Proof of Proposition 22 · p. 14

F. Proof of Proposition 23

  • Mixing bounds the change in the conditional probability of v_j = v by 2δ, yielding a bound of 2δ/Pr[v_j = v | E] on the conditional probability difference for v_i = u.Source: F. Proof of Proposition 23 · p. 14

G. Proof of Proposition 31

  • With probability at least 1 − 2/n, every vertex degree in G(n,p) lies between np(1 − ϵ) and np(1 + ϵ).The proof applies a Chernoff bound to each vertex and then a union bound.Source: G. Proof of Proposition 31 · p. 14

H. Proof of Corollary 33

  • For the graph setting obtained using Proposition 31 and Lemma 32, t = O(log(1/δ)) suffices for ∥µ′ − µ∥∞ ≤ δ.The proof chooses the degree parameter so the graph is uniform and has Φ(G) = Ω(1), then applies Theorem 30.Source: H. Proof of Corollary 33 · p. 14
Loading 1001.1445v2…