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

This paper studies graph matching under the correlated Erd s-R' e nyi (ER) graph pair model. This model first samples an ER(n, lambda over ns) base graph, whose edges are then independently subsampled twice with probability s to produce two correlated ER(n, lambda over n) graphs. We propose a graph matching algorithm that has n 2+o(1) time complexity and achieves almost exact recovery with high probability under the assumptions lambda=(n) alpha+o(1) for some alpha in(0,1) and s in(sqrt C Otter,1], where C Otter about 0.338 is Otter's tree-counting constant. This is the first algorithm with almost quadratic time complexity in this regime of lambda, while the best known result in this regime is the chandelier-counting algorithm with time complexity O(n c(s)), where c(s) to infinity as s approaches sqrt C Otter from above. The proposed algorithm is based on local tree correlation tests. It uses a rank-based algorithm to match the vertex pairs instead of threshold-based rules in the literature. This avoids the need of computing an explicit threshold, which is computationally difficult to obtain. To prove the almost exact recovery result, we establish a new analysis of tree correlation tests in the diverging-degree regime, where both the mean degree and the tree depth grow with n. Based on this new result, we establish the existence of a threshold for a threshold-based graph matching algorithm via local tree correlation tests. Finally, we couple the performance of the rank-based algorithm with the threshold-based algorithm to show almost exact recovery.