Graph Reconstruction from Noisy Random Subgraphs

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\mathrm{/}2{)}^{-2}{p}_v^{-2}\log n)$ traces suffice to reconstruct $G$ with high probability. In contrast, if $G$ is arbitrary, then $\exp (\mathrm{\Omega }(n))$ traces are necessary even when $p_v=1,p_e=1\mathrm{/}2$.