REVIEW 3 major objections 5 minor 18 references
Group Testing with General Correlation Using Hypergraphs
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read A greedy adaptive algorithm identifies the infected hyperedge in O(H(X)+μ) tests in expectation, and the bound is order-optimal for several random hypergraph families.
desk verdict A sound, genuinely useful generalization of correlated group testing; the central O(H+mu) bound is well supported, but the abstract overclaims and the exact-knowledge-of-D assumption deserves more prominence. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the edge-weight function w(S), the total posterior probability of hyperedges fully contained in S. Because a test of V \ S is positive exactly when the target hyperedge lies outside E(S), either outcome lets the algorithm delete a known probability block—E(S) on a positive result, its complement on a negative result. Lemma 4.3 shows that deleting the ruled-out block and scaling the remaining probabilities is the true posterior update, which is what makes the greedy removal rule valid. The algorithm greedily shrinks S until c ≤ w(S) ≤ 1-c, so every informative test removes a constant fraction of the remaining mass and the elimination count is bounded by entropy.
What would settle it
Allow the infected set to be a union of two disjoint hyperedges drawn independently while keeping everything else identical. Then the key equivalence fails: a positive test of V \ S no longer implies the target edge lies outside E(S), so the deletion rule can remove a truly infected edge; running Algorithm 1 on this two-infection variant and observing the wrong edge survive would isolate exactly which assumption the entropy-based guarantee rests on.
Extended reading notes
Core claim
Under the model, exactly one hyperedge e is drawn from a known distribution D and all nodes in e are infected. Algorithm 1 repeatedly builds a candidate set S of still-possible nodes, tests its complement, and updates the posterior by deleting the ruled-out edge class and renormalizing the rest; Lemma 4.3 proves this deletion-and-scale step is the exact Bayesian update. Each informative test removes at least a constant fraction c of the remaining probability mass, so the expected number of such tests is at most H(X)/log(1/(1-c)). When no such test remains, the surviving nodes are almost surely infected and individual testing costs at most the posterior expected infection count divided by 1-2c, giving the O(H(X)+u) guarantee when u stochastically upper-bounds the infected-edge size. The paper also proves the (1-ε)H(X) information-theoretic lower bound, and it gives families of hypergraphs where the algorithm is order-optimal and others where entropy is not a tight lower bound.
Load-bearing premise
The whole guarantee depends on the infection being exactly one hyperedge drawn from a probability distribution the algorithm knows exactly; if several disjoint subsets can be infected at once, or if the supplied distribution is wrong, the rule that discards ruled-out subsets no longer yields correct updated odds and the O(H+u) bound collapses.
Editorial extensions
If this is right
- Independent probabilistic group testing is recovered as a special case: with concentrated infection counts, Algorithm 1 matches the prior O(H(X)+μ) adaptive bound up to constants.
- For the family-community model of [NSG+21a], the expected test count drops from O(Fq(log F + M) + nqp log n) to O(F(h2(q) - w h2((1-q)/w)) + nq(h2(p)+p)) in the large-F, large-n regime.
- For uniform set-systems with |E| candidate subsets of size d, the algorithm uses O(log |E| + d) tests, improving the earlier O(log |E| + d log^2 d) guarantee.
- The entropy H(X) is not a tight lower bound under correlation: some n-node hypergraphs have H(X)=O(log n) while any algorithm with constant success probability needs Ω(n) tests.
- On dense d-regular random hypergraphs the algorithm is order-optimal, and a modified version is order-optimal on sparse d-regular random hypergraphs, using O(H(X)) tests when d is o(n).
Reading between the lines
- Beyond the paper: because the algorithm only needs a stochastic upper bound u rather than the exact mean, it is robust to approximate estimates of μ; one could run it with a plug-in empirical distribution and expect graceful degradation, though the paper does not quantify the misspecification cost.
- Beyond the paper: the posterior-removal rule is a general Bayesian search primitive, so the same O(H+u) analysis should carry over to other sequential identification problems with one hidden object and noisy subset queries, not just infection testing.
- Beyond the paper: the n/log n adaptive-to-non-adaptive gap suggests that finding hypergraph families where non-adaptive designs match adaptive performance would be the natural next target; the paper leaves this open.
- Beyond the paper: the noisy-testing bound improves on simple repetition by updating posteriors with the flip probability, implying that in high-entropy regimes the noise penalty is additive rather than multiplicative; a direct comparison with majority-vote repetition is given in Remark 8.2.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a hypergraph-based model for group testing under arbitrary statistical correlation: a hyperedge (a subset of nodes) is sampled from a known distribution D, and the infected set is exactly that hyperedge. The authors propose an adaptive greedy algorithm that maintains a posterior over hyperedges, performs informative tests that remove a constant fraction of the probability mass, and then tests remaining uncertain nodes individually. They upper bound the expected number of tests by O(H(X)+µ) under edge-size assumptions and by O(H(X)+u) when a stochastic upper bound u on the infected-set size is known (Theorem 4.11 and Corollary 4.12). They claim to recover or improve prior correlated group testing results, provide examples showing when entropy is a loose lower bound, establish order optimality for dense and sparse random d-regular hypergraphs, and extend the framework to semi-non-adaptive and noisy group testing.
Significance. If the main results hold, the paper is a valuable unifying treatment of group testing with correlated infection patterns. The adaptive noiseless analysis is attractive: Lemma 4.3 derives the correct Bayes update for the single-edge model, Lemma 4.4 gives a clean informative-test counting argument, and Corollary 4.12 provides a bound depending only on H(X) and a stochastic size bound u. The lower-bound examples in Section 6 are concrete and informative, and the random-hypergraph optimality results in Section 6.4 are nontrivial. The main caveats are the exact-knowledge assumption on D, the informal nature of the noisy-section analysis, and some overstated comparison claims in Section 5 and the abstract.
major comments (3)
- [§2.3, Theorem 2.2] The lower bound L ≥ (1−ε)H(X) is false as stated. Fano's inequality gives L ≥ H(X) − h(ε) − ε log(|E|−1), and the omitted terms can be non-negligible. A concrete counterexample: take three singleton hyperedges with uniform probabilities, so H(X)=log 3. One test of the first node recovers the edge with error probability 1/6 (if the test is negative, output the second edge; error occurs only when the third edge is true). Thus L=1 and ε=1/6, but (1−ε)H(X)=(5/6)log 3 > 1, contradicting the theorem. Since Theorem 2.2 is used in Section 6 to support order-optimality claims, the statement needs to be corrected, for example by adding the standard entropy-error terms, or by proving the bound only under conditions where those terms are o(H(X)) when ε→0.
- [§8, Theorem 8.1 proof, paragraph 'Upper bound'] The proof does not provide a valid stopping-time argument for the number of line-6 tests. The displayed lower bound q(e*) ≥ p(e*) c'^M cannot be used to conclude that the algorithm 'must have fewer than' M tests, because q(e*) is a probability and can never exceed 1; a lower bound exceeding 1 only indicates that the bound is too crude. Moreover, in the noisy modification no edge is ever eliminated and the algorithm does not stop when q(e*) reaches 1; the transition from line 6 to Stage 2 is governed by the greedy condition c ≤ w(S) ≤ 1−c. A rigorous bound on the random number of line-6 tests is needed, for example via a potential function or a martingale argument that couples the posterior growth with the actual stopping rule. As written, the proof does not establish the first term of Theorem 8.1's bound.
- [§5, comparison with [NSG+21a]] The claimed improvement over [NSG+21a] relies on the assertion that if F≫1 and M≫1, then the number of infections is concentrated around its mean, so that Corollary 4.12 applies with u=O(µ). This is not true for arbitrary q and p in the family model: for example, with q=O(F^{-2}), M=F, and p=1/2, the mean number of infected nodes is O(1) and the fluctuations are not vanishing relative to the mean, so a stochastic upper bound u=O(µ) need not hold. The comparison should be stated under explicit concentration conditions, and the abstract's claim to 'recover or improve all previously known results' should be correspondingly qualified.
minor comments (5)
- [§3.2 after Figure 1] There is a typo: 'proabilities' should be 'probabilities'.
- [§2, Figure 1 caption] 'Figure 1 show' should be 'Figure 1 shows'.
- [§8, Theorem 8.1 statement] The error-probability expression '1 − O(1/ min(n, g(n))' is missing a closing parenthesis; it should read '1 − O(1/min(n, g(n)))'.
- [§8, condition in Theorem 8.1] The condition c > 1 − (1−δ)^{1−δ}δ^δ together with c < 1/2 restricts δ away from 1/2; this limitation should be stated explicitly, since the theorem does not cover noise levels near the symmetric capacity limit.
- [§5, comparison with [GLS22]] The statement that Theorem 4.9 'slightly improves' the [GLS22] bound should be phrased as a comparison for the probabilistic uniform-edge model, not as an improvement of the worst-case combinatorial bound in [GLS22], since the two settings are not identical.
Circularity Check
No significant circularity: the test-count bounds are functionals of the known distribution D and rely on an external entropy lower bound.
full rationale
The derivation chain is self-contained against the model inputs. Algorithm 1's guarantees in Lemma 4.1, Theorem 4.9, Theorem 4.11, and Corollary 4.12 are expressed directly in terms of H(X) and mu computed from the given distribution D; no parameter is fitted to the quantity being predicted. Lemma 4.3 derives the posterior update from the definition of a test outcome via Lemma 4.2, rather than assuming it, and Lemma 4.4 is standard entropy accounting: each informative test removes at least a c-fraction of the remaining probability mass, so at most log(1/p(e))/log(1/(1-c)) informative tests are needed for edge e, giving expectation H(X)/log(1/(1-c)). The epsilon slack in Theorem 4.11 comes from Markov's inequality applied to |e*|, not from a fitted constant. The entropy lower bound in Theorem 2.2 is an externally established information-theoretic bound, stated as an extension of [LCH+14], and is not an imported uniqueness claim by the present authors. The only self-citation, [NKC+22], is used as a special-case model translation in Section 2.2 and Appendix A and does not support any theorem needed for the main bounds. Section 5's phrase "recovers or improves upon all previously known results" is broader than the detailed comparisons, which do not give an explicit quantitative comparison for [NKC+22] and [AU23], and the exact-knowledge-of-D assumption is a real modeling limitation; these are correctness/presentation caveats, not circularity. The paper also openly states in Section 9 that general optimality remains open. No load-bearing step reduces by construction to its own input.
Assumptions & free parameters
assumptions (5)
- domain assumption The infected state is exactly one hyperedge e drawn from the probability distribution D over the edge set E.
- domain assumption The algorithm knows the distribution D and can compute posterior probabilities q_e exactly after each test.
- domain assumption Tests are OR tests: a group tests positive iff it contains at least one infected node; noise, when present, is symmetric bit flips.
- domain assumption In Corollary 4.12 and Theorem 7.1, the size of the infected set is stochastically bounded by u with P(|e*|>u)=o(1), and u is known to the algorithm.
- standard math The entropy lower bound L >= (1-epsilon)H(X) from [LCH+14] is valid and is used as an external benchmark.
Cite this review
Pith. "Pith review of Group Testing with General Correlation Using Hypergraphs." pith.science (2026). https://pith.science/paper/JO3ECZOZ
@misc{pith2026241217751,
author = {Pith},
title = {Pith review of: Group Testing with General Correlation Using Hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/JO3ECZOZ}},
note = {Machine review of arXiv:2412.17751}
}
read the original abstract
Group testing, a problem with diverse applications across multiple disciplines, traditionally assumes independence across nodes' states. Recent research, however, focuses on real-world scenarios that often involve correlations among nodes, challenging the simplifying assumptions made in existing models. In this work, we consider a comprehensive model for arbitrary statistical correlation among nodes' states. To capture and leverage these correlations effectively, we model the problem by hypergraphs, inspired by [GLS22], augmented by a probability mass function on the hyper-edges. Using this model, we first design a novel greedy adaptive algorithm capable of conducting informative tests and dynamically updating the distribution. Performance analysis provides upper bounds on the number of tests required, which depend solely on the entropy of the underlying probability distribution and the average number of infections. We demonstrate that the algorithm recovers or improves upon all previously known results for group testing settings with correlation. Additionally, we provide families of graphs where the algorithm is order-wise optimal and give examples where the algorithm or its analysis is not tight. We then generalize the proposed framework of group testing with general correlation in two directions, namely noisy group testing and semi-non-adaptive group testing. In both settings, we provide novel theoretical bounds on the number of tests required.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[6]
Improved algorithms for non- adaptive group testing with consecutive positives
[BCN21] Thach V Bui, Mahdi Cheraghchi, and Thuc D Nguyen. Improved algorithms for non- adaptive group testing with consecutive positives. In 2021 IEEE International Symposium on Information Theory (ISIT) , pages 1961–1966. IEEE,
work page 2021
-
[11]
Group testing with prior statistics
[LCH+14] Tongxin Li, Chun Lam Chan, Wenhao Huang, Tarik Kaced, and Sidharth Jaggi. Group testing with prior statistics. In 2014 IEEE International Symposium on Information The- ory, pages 2346–2350. IEEE,
work page 2014
-
[13]
Group Testing with Correlation under Edge-Faulty Graphs
[NKC+22] Hesam Nikpey, Jungyeol Kim, Xingran Chen, Saswati Sarkar, and Shirin Saeedi Bidokhti. Group testing with correlation under edge-faulty graphs. arXiv preprint arXiv:2202.02467,
-
[16]
Quantitative group testing with tunable adaptation
[SJ24b] Mahdi Soleymani and Tara Javidi. Quantitative group testing with tunable adaptation. In 2024 IEEE International Symposium on Information Theory (ISIT) , pages 3017–3022. IEEE,
work page 2024
-
[17]
[WGG23] Hsin-Po Wang, Ryan Gabrys, and Venkatesan Guruswami. Quickly-decodable group test- ing with fewer tests: Price-scarlett’s nonadaptive splitting with explicit scalars. In IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023, pages 1609–1614. IEEE,
work page 2023
-
[18]
[WGG24] Hsin-Po Wang, Ryan Gabrys, and Venkatesan Guruswami. Quickly-decodable group test- ing with fewer tests: Price-scarlett and cheraghchi-nakos’s nonadaptive splitting with ex- plicit scalars. arXiv preprint arXiv:2405.16370 ,
-
[1980]
Grotesque: noisy group testing (quick and efficient)
[CJBJ13] Sheng Cai, Mohammad Jahangoshahi, Mayank Bakshi, and Sidharth Jaggi. Grotesque: noisy group testing (quick and efficient). In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 1234–1241. IEEE,
work page 2013
-
[1986]
Improved group testing rates with constant column weight designs
[AJS16] Matthew Aldridge, Oliver Johnson, and Jonathan Scarlett. Improved group testing rates with constant column weight designs. In 2016 IEEE International Symposium on Infor- mation Theory (ISIT) , pages 1381–1385. Ieee,
work page 2016
Show all 18 references
-
[1998]
On acceler- ated testing for covid-19 using group testing
[NHL20] Krishna R Narayanan, Anoosheh Heidarzadeh, and Ramanan Laxminarayan. On acceler- ated testing for covid-19 using group testing. arXiv preprint arXiv:2004.04785 ,
2004 arXiv
-
[2014]
Adaptive group testing on networks with community structure
[ACO21] Surin Ahn, Wei-Ning Chen, and Ayfer Ozgur. Adaptive group testing on networks with community structure. arXiv preprint arXiv:2101.02405 ,
-
[2016]
Group testing: an information theory perspective
40 [AJS19] Matthew Aldridge, Oliver Johnson, and Jonathan Scarlett. Group testing: an information theory perspective. arXiv preprint arXiv:1902.06002 ,
1902 arXiv
-
[2017]
Power grid vulnerability to geographically correlated failures—analysis and control implications
[BBH+14] Andrey Bernstein, Daniel Bienstock, David Hay, Meric Uzunoglu, and Gil Zussman. Power grid vulnerability to geographically correlated failures—analysis and control implications. In IEEE INFOCOm 2014-IEEE conference on computer communications , pages 2634–
2014
-
[2018]
An efficient algorithm for capacity-approaching noisy adaptive group testing
[Sca19] Jonathan Scarlett. An efficient algorithm for capacity-approaching noisy adaptive group testing. In 2019 IEEE International Symposium on Information Theory (ISIT) , pages 2679–2683. IEEE,
2019
-
[2019]
Graph and cluster formation based group testing
[AU21] Batuhan Arasli and Sennur Ulukus. Graph and cluster formation based group testing. In 2021 IEEE International Symposium on Information Theory (ISIT) , pages 1236–1241. IEEE,
2021
-
[2020]
Group testing on general set-systems
[GLS22] Mira Gonen, Michael Langberg, and Alex Sprintson. Group testing on general set-systems. In 2022 IEEE International Symposium on Information Theory (ISIT) , pages 874–879. IEEE,
2022
-
[2021]
Group testing for overlapping communities
[NSG+21b] Pavlos Nikolopoulos, Sundara Rajan Srinivasavaradhan, Tao Guo, Christina Fragouli, and Suhas Diggavi. Group testing for overlapping communities. In ICC 2021-IEEE Interna- tional Conference on Communications , pages 1–7. IEEE,
2021
-
[2023]
Sparsity-constrained community- based group testing
[JCM24] Sarthak Jain, Martina Cardone, and Soheil Mohajer. Sparsity-constrained community- based group testing. arXiv preprint arXiv:2403.12419 ,
-
[2024]
Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms
[CCJS11] Chun Lam Chan, Pak Hou Che, Sidharth Jaggi, and Venkatesh Saligrama. Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Alle...
2011
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.