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{Erdo˝s-Reˊnyi}$ (ER) graph pair model. This model first samples an $\mathrm{ER}(n,\frac{\lambda }{ns})$ base graph, whose edges a…