Graph Reconstruction from Noisy Random Subgraphs
<|reference_start|>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/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$.<|reference_end|>
@article{mcgregor2024graph,
    title={Graph Reconstruction from Noisy Random Subgraphs},
    author={Andrew McGregor and Rik Sengupta},
    journal={arXiv preprint arXiv:2405.04261},
    year={2024},
    doi={10.1109/ISIT57864.2024.10619491},
    archivePrefix={arXiv},
    eprint={2405.04261},
    primaryClass={cs.IT cs.DS math.IT}
}