  In this paper, we consider the problem of learning an unknown graph via
queries on groups of nodes, with the result indicating whether or not at least
one edge is present among those nodes. While learning arbitrary graphs with $n$
nodes and $k$ edges is known to be hard in the sense of requiring $\Omega(
\min\{ k^2 \log n, n^2\})$ tests (even when a small probability of error is
allowed), we show that learning an Erd\H{o}s-R\'enyi random graph with an
average of $\bar{k}$ edges is much easier; namely, one can attain
asymptotically vanishing error probability with only $O(\bar{k}\log n)$ tests.
We establish such bounds for a variety of algorithms inspired by the group
testing problem, with explicit constant factors indicating a near-optimal
number of tests, and in some cases asymptotic optimality including constant
factors. In addition, we present an alternative design that permits a
near-optimal sublinear decoding time of $O(\bar{k} \log^2 \bar{k} + \bar{k}
\log n)$.
