Answers are grounded in this paper and cite their sources.
For two unlabeled graphs G1, G2 independently sub-sampled from an Erdős–Rényi graph G(n,p) by keeping each edge with probability s, we aim to recover as many as possible of the corresponding vertex pairs. We establish a connection between the recoverability of vertex pairs and the balanced load allocation in the true intersection graph of G1 and G2. Using this connection, we analyze the partial recovery regime where p=n−α+o(1) for some α∈(0,1] and nps2=λ=O(1). We derive upper and lower bounds for the recoverable fraction in terms of α and the limiting load distribution μλ (as introduced in (Ann. Appl. Probab. 26 (2016) 305–327). These bounds coincide asymptotically whenever α−1 is not an atom of μλ. Therefore, for each fixed λ, our result characterizes the asymptotic optimal recovery fraction for all but countably many α∈(0,1].
No takes yet. Share an insight, caveat, or question.
Hang Du (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: