This paper studies average-case performance of learning Erdos-Renyi random graphs via non-adaptive edge-detecting queries. The main contributions are threefold: - An algorithm-independent probabilistic lower bound of the number of non-adaptive tests is given via Fano's inequality (Theorem 1). - Three existing algorithms for standard group testing, COMP, DD, and SSS, are extended to the graph learning problem. Under the Bernoulli testing, upper bounds are provided for COMP (Theorem 2) and DD (Theorem 3), and a lower bound is provided for SSS (Theorem 4). These in particular show that DD is asymptotically optimal under the Bernoulli testing when \theta>1/2. - A sublinear-time algorithm based on the GROTESQUE algorithm for group testing is proposed, and bounds on the number of tests and on decoding time are given for that algorithm (Theorem 5). Although the three review scores exhibited a relatively large split in the initial round of review, after the authors' rebuttal as well as discussion among the reviewers, all the three reviewers have become positive ratings. I would thus like to recommend acceptance of this paper. Minor point: Line 204: unless one moves (bound -> beyond?) Bernoulli test designs.