  We consider the problem of reconstructing an undirected graph $G$ on $n$
vertices given multiple random noisy subgraphs or "traces". Specifically, a
trace is generated by sampling each vertex with probability $p_v$, then taking
the resulting induced subgraph on the sampled vertices, and then adding noise
in the form of either (a) deleting each edge in the subgraph with probability
$1-p_e$, or (b) deleting each edge with probability $f_e$ and transforming a
non-edge into an edge with probability $f_e$. We show that, under mild
assumptions on $p_v$, $p_e$ and $f_e$, if $G$ is selected uniformly at random,
then $O(p_e^{-1} p_v^{-2} \log n)$ or $O((f_e-1/2)^{-2} p_v^{-2} \log n)$
traces suffice to reconstruct $G$ with high probability. In contrast, if $G$ is
arbitrary, then $\exp(\Omega(n))$ traces are necessary even when $p_v=1,
p_e=1/2$.
