Jiale Cheng

Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests

Jiale Cheng, Ziao Wang, Lei Ying

This paper studies graph matching under the correlated $\text{Erdős-Rényi}$ (ER) graph pair model. This model first samples an $\mathrm{ER}(n,\fracλ{ns})$ base graph, whose edges are then independently subsampled twice with probability $s$ to produce two correlated $\mathrm{ER}(n…Read more