LiDP: A Selective-and-Adaptive Framework for Distance-Based Random Graph Matching

Graph matching is an NP-hard problem of recovering vertex correspondences between correlated graphs. Degree-profile methods, which compare vertices based on their local statistics, are attractive due to their exact recovery guarantees and computational efficiency. However, these methods typically require computing distances between all pairs of vertices, and their performance may deteriorate in high-noise regimes. To address these challenges, we propose a two-stage framework for random graph matching. First, selective distance computation preserves the exact recovery guarantee of degree-profile matching while reducing the complexity from $O((n^2+n{d}^2)\log n)$ to $O(n^2+n{d}^2)$. When recovery fails under high noise, the computed distances warm-start a continuous optimization method with convergence guarantees. Under suitable assumptions, we establish exact recovery for stationary points with sufficiently small objective gaps to the ground truth. To the best of our knowledge, this is the first such guarantee for near-optimal stationary points in nonconvex doubly stochastic graph matching. Experiments on synthetic and real-world networks show $10\times$–$20\times$ speedups in low-noise regimes and substantially improved robustness under high noise.