REVIEW 4 cited by
Optimal recovery of correlated Erd\H{o}s-R\'enyi graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
For two unlabeled graphs $G_1,G_2$ independently sub-sampled from an Erd\H{o}s-R\'enyi graph $\mathbf G(n,p)$ by keeping each edge with probability $s$, we aim to recover \emph{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 $ G_1 $ and $ G_2 $. Using this connection, we analyze the partial recovery regime where $ p = n^{-\alpha + o(1)} $ for some $ \alpha \in (0, 1] $ and $ nps^2 = \lambda = O(1) $. We derive upper and lower bounds for the recoverable fraction in terms of $ \alpha $ and the limiting load distribution $ \mu_\lambda $ (as introduced in \cite{AS16}). These bounds coincide asymptotically whenever $ \alpha^{-1} $ is not an atom of $ \mu_\lambda $. Therefore, for each fixed $ \lambda $, our result characterizes the asymptotic optimal recovery fraction for all but countably many $ \alpha \in (0, 1] $.
Forward citations
Cited by 4 Pith papers
-
Graph alignment in sparse inhomogeneous models via self-overlap
Partial graph alignment is feasible exactly on vertices whose balanced load in the intersection graph exceeds the self-overlap of the union graph, giving sharp thresholds for Chung–Lu and stochastic block-model graphs.
-
Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests
A rank-based local tree correlation test almost exactly matches vertices of correlated Erdős-Rényi graphs in n^{2+o(1)} time when average degree is polylog and edge correlation exceeds Otter's constant.
-
Strong Detection Threshold for Correlated Erd\H{o}s-R\'enyi Graphs with Constant Average Degree
For correlated Erdős-Rényi graphs with constant average degree, strong detection is information-theoretically possible if and only if the subsampling probability s exceeds min{1/√λ, √α}, with α≈0.338.
-
Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm
An approximate message passing algorithm provably recovers the latent matching between correlated Gaussian matrices under adversarial principal-minor corruption of size n/(log n)^20.
Discussion (0). Continue with ORCID to comment.