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

Outlier rejection for correspondence-based point cloud registration confronts two fundamental challenges in real-world 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 accuracy-efficiency 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 multi-resolution graph layers while circumventing the high complexity of exhaustive global search. Finally, distribution-aware ranking jointly evaluates geometric consistency and spatial coverage to select well-distributed transformations from multiple hypotheses. Experiments on 3DMatch, 3DLoMatch, and KITTI demonstrate that our method significantly outperforms state-of-the-art methods in both low-overlap and large-scale scenarios.