MHopReg: Efficient Hierarchical Multi-Hop Graph Search for Point Cloud Registration

Outlier rejection for correspondence-based point cloud registration confronts two fundamental challenges in realworld scenarios. First, low-overlap regions yield sparse and fragmented inlier distributions that are difficult to discover using conventional one-step global search strategies. Second, large-scale scenes present dense correspondence inputs that impose stringent requirements on the accuracyefficiency trade-off of search algorithms. To this end, we propose a hierarchical multi-hop graph search framework that progressively refines correspondences to address these challenges. Our method constructs a compatibility graph with transformation-invariant embeddings to predict correspondence confidence, establishing the foundation for cluster-balanced seed sampling that ensures comprehensive coverage across fragmented regions. These strategically selected seeds subsequently drive hierarchical multi-hop expansion, progressively discovering inliers through multiresolution graph layers while circumventing the high complexity of exhaustive global search. Finally, distributionaware ranking jointly evaluates geometric consistency and spatial coverage to select well-distributed transformations from multiple hypotheses. Experiments on 3DMatch, 3DLo-Match, and KITTI demonstrate that our method achieves highly competitive performance compared to existing methods in both low-overlap and large-scale scenarios.