The paper is well written and answers some interesting theoretical questions at the intersection of non-adaptive group testing and graph learning. The problem, thought connected to structured group testing, seems novel in this particular incarnation. While the algorithms proposed are not especially novel, the authors needed too perform some nuanced analysis, and I particularly appreciate Appendix H that outlines the difficulties. Overall, this is a strong paper with interesting results. I recommend its acceptance.

This kind of nonadaptive testing for graph recovery problem seems to arise in numerous settings and is therefore natural and important; the sparse Erdos-Renyi setting is perhaps the most basic for average-case analysis and so the focus there makes sense (there is a brief discussion of general graphs). Although I didn't check each proof, line-by-line, the high-level ideas of everything indicate correctness to me. The fact the simulations qualitatively line up is also suggestive. There is a lot of content in this paper, with several distinct achievable schemes (4 by my count), of which one is near-optimal, whereas the others have potentially interesting relationships among them. Although the writing is generally well-organized and clear, I wonder if so much material is perhaps ambitious for an 8-page conference paper. In particular, a significant part of the content, including pretty much all proofs are deferred to appendices. Although 1-sentence sketch of proofs are often given in text, a little more detail in the main text would have been nice, especially about the sublinear time decoding algorithm. Moreover, Appendix H on comparing standard group testing to this setting would have been appreciated in the main text, to help clarify novelty. I should say, there is certainly novelty. ADDENDUM: I have read through the other reviewer comments as well as the author rebuttal, and my scoring remains the same based on the theoretical contribution. I appreciate the authors will try to include more content by more concise formatting and the extra page; based on R4's comments as representative of broader readership, perhaps one should ignore my previous suggestion of reducing the scope of the experimental section. R4's suggestion of releasing code is also a good one, for reproducibility and greater usage of your algorithm.

This paper studies a learning task of Erdos-Renyi graph with edge detecting queries. Each query or test is given as a set of input (a set of nodes) X representing a set of nodes and output Y(X)=0 or 1 representing the absence or presence of at lease one edge in the node set X. The authors derive the theoretical and algorithmic bounds of the number of tests required for achieving the perfect reconstruction of the graph in the asymptotic limit where the number of nodes $n$ tends to be infinity, using three known algorithms: COMP, DD, and SSS. The derived analytic form is tight up to the asymptotic constant. A new algorithm is also invented based on GROTESQUE algorithm, achieving a sublinear computational time in the decoding step which is near optimal compared to the derived bounds. Originality: The task is new and the novelty of the contribution is clear. Quality: The submission is technically sound. All claims are proved by using standard bounding techniques (Chernoff, union) plus some more advanced techniques. Both the strong and weak points of the proposed methods are honestly pointed out. In this sense, the quality is high. Clarity: The paper is basically well organized, though I sometimes found some uneasy expressions. For example, at first sight, it is not easy to understand Figure 1, because the meaning of some parameters (e.g. \theta) and of the axes are not well explained up to the point where Figure 1 is first referred in the main text. Below I give the list of typos and uneasy expressions which I found: Line 4: hard the sense -> hard in the sense Line 22-24: The sentence ``Each node is ... in that query.'' is hard to understand. Line 663: then then -> then Significance: Both the derived bounds and the proposed algorithm are interesting and can be useful also for practical purposes. The significance thus is high. Additional comments after feedback: Given the author feedback and discussions with the other reviewers, I am convinced with the importance of this work. The score is increased accordingly. But still I think numerical experiments and codes are valuable, because for practical users they are more convincing and important.