As a fundamental problem in computer vision, 3D point cloud registration (PCR) aims to seek the optimal pose to align a point cloud pair. In this paper, we present a 3D registration method with maximal cliques (MAC). The key insight is to loosen the previous maximum clique constraint, and mine more local consensus information in a graph for accurate pose hypotheses generation: 1) A compatibility graph is constructed to render the affinity relationship between initial correspondences. 2) We search for maximal cliques in the graph, each of which represents a consensus set. We perform node-guided clique selection then, where each node corresponds to the maximal clique with the greatest graph weight. 3) Transformation hypotheses are computed for the selected cliques by the SVD algorithm and the best hypothesis is used to perform registration. Extensive experiments on U3M, 3DMatch, 3DLoMatch and KITTI demonstrate that MAC effectively increases registration accuracy, outperforms various state-of-the-art methods and boosts the performance of deep-learned methods. MAC combined with deep-learned methods achieves state-of-the-art registration recall of 95.7% / 78.9% on 3DMatch / 3DLoMatch.

Point cloud registration (PCR) is an important and fundamental problem in 3D computer vision, with applications in localization, 3D object detection, and reconstruction. Given a pair of partially overlapping point clouds, the goal is to estimate a rigid transformation (rotation and translation) that aligns them in a common coordinate frame. A typical pipeline first extracts local or global features to establish an initial set of putative correspondences, which usually contains a significant number of outliers (incorrect matches). The registration problem then reduces to robustly estimating the transformation from this noisy correspondence set.

Existing methods for robust correspondence-based registration can be broadly classified into two categories. RANSAC and its variants adopt a hypothesize-and-verify paradigm: they repeatedly sample minimal subsets, compute candidate transformations, and select the best one by consensus. However, their performance is highly vulnerable when the outlier rate increases, and they require a large number of iterations to obtain acceptable results. Branch-and-bound (BnB) methods seek globally optimal solutions by systematically exploring the transformation space, but their main weakness is the high computational complexity, especially when the correspondence set is of a large magnitude and has an extremely high outlier rate. More recently, graph-theoretic approaches model correspondences as nodes and their geometric compatibility as edges. The maximum clique in the resulting compatibility graph represents the largest mutually consistent correspondence set. However, the maximum clique is a very tight constraint that only focuses on the global consensus information in a graph, potentially missing valuable local consensus structures.

In this paper, we present MAC — 3D Registration with Maximal Cliques. Our key insight is that by relaxing from the maximum clique to maximal cliques, we can mine richer local consensus information from the compatibility graph. A maximal clique is a clique that cannot be extended by adding any adjacent vertex — it need not be the largest clique in the graph. This relaxation yields multiple consensus sets of varying sizes, each capturing different local geometric agreements among correspondences. We introduce a node-guided clique selection strategy that retains the most representative clique for each node, followed by SVD-based hypothesis generation and evaluation. Our main contributions are: (1) We introduce MAC as a hypothesis generation method able to mine more local information in a graph compared with the maximum clique constraint. (2) Based on MAC, we present a novel PCR method that achieves state-of-the-art performance on U3M, 3DMatch, 3DLoMatch and KITTI. MAC can also be inserted as a module into deep-learned frameworks to boost their performance. (3) We demonstrate that MAC combined with GeoTransformer achieves registration recall of 95.7% / 78.9% on 3DMatch / 3DLoMatch.

Geometric-only PCR methods do not require training data and rely solely on geometric constraints. RANSAC remains the most widely used baseline due to its simplicity. Numerous variants have been proposed to improve efficiency and robustness, including FGR which employs a graduated non-convexity optimization, TEASER++ which uses truncated least-squares estimation with certifiable optimality, and SC²-PCR which builds second-order spatial consistency. Graph-theoretic methods construct a compatibility graph and search for cliques or maximum cliques to identify geometrically consistent correspondence subsets. However, finding the maximum clique is NP-hard, and existing solvers become impractical when the graph is large. Moreover, a single maximum clique may not capture all useful consensus structures present in the graph.

Deep-learned PCR methods leverage neural networks to learn feature descriptors, correspondence filtering, or end-to-end pose estimation. 3DMatch pioneered learning-based 3D local descriptors, followed by improvements such as FCGF (fully convolutional geometric features) and Predator for overlap-aware matching. PointDSC introduces a differentiable spatial consistency module for correspondence pruning. GeoTransformer uses geometric transformers for superpoint matching and local-to-global registration. While these methods achieve impressive results, they require a large amount of data for training and usually lack generalization on different datasets. Importantly, MAC is complementary to these learning-based methods — it can be inserted as a plug-in module to replace RANSAC in existing deep-learned pipelines, yielding consistent performance gains.

The distinction between maximum cliques and maximal cliques is central to this work. A maximum clique is the clique with the most vertices in the entire graph — there may be multiple maximum cliques of equal size but finding even one is NP-hard. A maximal clique is any clique that cannot be extended by including one more adjacent vertex — it is locally maximal but not necessarily globally largest. Every maximum clique is a maximal clique, but the set of all maximal cliques is far richer, capturing diverse local consensus patterns that a single maximum clique may miss. Previous graph-based registration methods primarily relied on a single or a few maximum cliques, discarding the abundant local information contained in smaller maximal cliques.

Given a source point cloud P^s and a target point cloud P^t, the goal of point cloud registration is to estimate a 6-DoF rigid transformation consisting of a rotation matrix R ∈ SO(3) and a translation vector t ∈ R³. An initial correspondence set C_initial = {c_i = (p_i^s, p_i^t)}_i=1^N is established through feature matching (e.g., using FPFH or FCGF descriptors), where p_i^s ∈ P^s and p_i^t ∈ P^t are paired 3D points. This set typically has a high outlier ratio (often exceeding 95%), making robust estimation essential.

We construct a compatibility graph G = (V, E) where each node v_i ∈ V corresponds to an initial correspondence c_i, and edges encode pairwise geometric compatibility. For the First Order Graph (FOG), we exploit the rigid distance constraint: under a rigid transformation, the Euclidean distance between any two points is preserved. The compatibility score between correspondences c_i and c_j is defined as S_cmp(c_i, c_j) = exp(-S_dist(c_i, c_j)² / 2d_cmp²), where S_dist(c_i, c_j) = | ||p_i^s - p_j^s|| - ||p_i^t - p_j^t|| | measures the distance discrepancy. An edge exists between nodes v_i and v_j when S_cmp exceeds a threshold t_cmp.

To obtain stricter compatibility conditions, we further introduce the Second Order Graph (SOG). The adjacency matrix of SOG is computed as W_SOG = W_FOG ⊙ (W_FOG × W_FOG), where ⊙ represents the element-wise product between two matrices. Intuitively, two correspondences are connected in the SOG only if they are directly compatible (FOG edge) and also share at least one common compatible neighbor. This second-order constraint provides a higher degree of compatibility — edges in the SOG survive only when supported by triangular consistency patterns. Moreover, the SOG is sparser than the FOG, which facilitates a more rapid search of cliques. The increased sparsity also helps suppress false edges caused by coincidental distance preservation among outlier correspondences.

We employ the igraph library's maximal clique enumeration function, which implements a modified Bron-Kerbosch algorithm. This algorithm systematically explores all maximal cliques with worst-case time complexity O(d(n-d)3^d/3), where d is the degeneracy of the graph and n is the number of vertices. The degeneracy-based ordering significantly improves practical efficiency compared to the naive exponential bound. In practice, because the compatibility graph (especially the SOG) is sparse, the number of maximal cliques is manageable. We additionally apply normal consistency filtering to remove cliques where the angular difference |sin(α_ij^s) - sin(α_ij^t)| < t_α is violated, as surface normals should be consistently transformed under a rigid motion.

The initial set of maximal cliques may be large. We introduce node-guided clique selection to reduce it to a manageable and representative subset. The key idea is: a node may be included by multiple maximal cliques, and we only retain the one with the greatest weight for that node. The weight of a maximal clique is defined as the sum of edge weights within the clique. After this selection, duplicated cliques are removed, obtaining the selected set MAC_selected. A crucial property is that the number of selected cliques |MAC_selected| will not exceed |V| — the number of initial correspondences. This guarantees a linear upper bound on the number of hypotheses, ensuring computational efficiency. We further apply clique ranking by sorting the selected cliques by their total weight and retaining only the Top-K cliques to control computational cost.

For each selected maximal clique, we compute a transformation hypothesis using the Singular Value Decomposition (SVD) algorithm. Two variants are considered. Instance-equal SVD treats all correspondences in the clique equally, computing the least-squares solution where the weights of all correspondences are equal. Weighted SVD assigns differentiated importance to correspondences: the correspondence weights are derived from the primary eigenvalues of W_SOG, reflecting their centrality in the compatibility graph. The weighted variant allows correspondences with stronger graph support to contribute more to the transformation estimate.

After generating transformation hypotheses from all selected cliques, we evaluate each hypothesis against the full initial correspondence set to identify the best one. We consider several RANSAC-family evaluation metrics: Mean Average Error (MAE), which computes the average residual distance; Mean Square Error (MSE), which squares the residuals giving more penalty to large errors; and Inlier Count, which counts correspondences whose residual is below a threshold. Experiments show that MAE provides the best overall performance, as it balances sensitivity to outliers with robustness to minor perturbations. The hypothesis with the lowest MAE (or highest inlier count, depending on the metric) is selected as the final registration result.

We evaluate MAC on four benchmark datasets: U3M (496 object-scale pairs with RMSE metric), 3DMatch (1,623 indoor scene pairs), 3DLoMatch (1,781 low-overlap pairs with 10%-30% overlap), and KITTI (555 outdoor LiDAR scan pairs). For 3DMatch and 3DLoMatch, we use standard evaluation criteria: Registration Recall (RR) with RE ≤ 15° and TE ≤ 30cm. We test MAC with two types of feature descriptors: the handcrafted FPFH and the learned FCGF. We compare against representative methods from both geometric-only and deep-learned categories, including RANSAC, FGR, TEASER++, SC²-PCR, PointDSC, and CG-SAC.

On 3DMatch, MAC achieves 93.72% registration recall with FCGF features, with RE=1.89° and TE=6.03cm, surpassing all compared methods. With handcrafted FPFH features, MAC attains 84.10% recall, outperforming SC²-PCR (83.73%), PointDSC (72.95%), and CG-SAC (78.00%). On 3DLoMatch, the more challenging low-overlap benchmark, MAC reaches 59.85% recall with FCGF (RE=3.50°, TE=9.75cm), and 40.88% with FPFH, consistently leading competitors. The performance gap is more pronounced on 3DLoMatch, where the higher outlier ratio makes robust consensus mining critical. When integrated with GeoTransformer, MAC achieves state-of-the-art registration recall of 95.7% on 3DMatch and 78.9% on 3DLoMatch, with improvements ranging from 3.1% to 14.2% across different sample counts.

On the KITTI outdoor driving dataset, MAC achieves 99.46% registration recall with FPFH and 97.84% with FCGF, matching or exceeding all baselines. SC²-PCR achieves comparable results (99.28% / 97.84%), while PointDSC reaches 98.92% / 97.84%. The relatively small performance gaps on KITTI reflect the lower difficulty of outdoor point cloud registration due to larger overlap and more structured environments. Nevertheless, MAC maintains top performance, demonstrating its generalization across diverse scene types — from object-scale (U3M) through indoor (3DMatch) to outdoor (KITTI).

Ablation studies validate the key design choices in MAC. Comparing maximal cliques vs. maximum cliques: the maximal clique approach outperforms by 9.8% (FPFH) and 5.55% (FCGF) on 3DMatch, confirming that mining multiple local consensus sets is superior to relying on a single global maximum clique. Comparing SOG vs. FOG: SOG outperforms FOG by 1.6% (FPFH) and 0.06% (FCGF) on 3DMatch, demonstrating the benefit of second-order compatibility. Among evaluation metrics, MAE achieves 0.24% improvement over inlier count with FPFH on 3DMatch. For clique ranking, Top-100 achieves 82.01% (FPFH) and 93.41% (FCGF) on 3DMatch, providing the best balance of accuracy and efficiency.

A particularly revealing analysis compares the hypothesis quality of MAC versus RANSAC. Given the same number of hypotheses (e.g., 500), MAC generates substantially more correct hypotheses than RANSAC — for instance, 51.74 correct hypotheses compared to RANSAC's 3.68 on 3DMatch with FCGF. This demonstrates that MAC's clique-based consensus mining produces far higher-quality pose hypotheses than random sampling. Furthermore, an analysis of MAC's performance upper bound reveals that MAC-1 (selecting the single best hypothesis with an oracle) achieves registration recalls of 98.46% / 91.24% on 3DMatch / 3DLoMatch. The gap between MAC-1 and the actual MAC performance (93.72% / 59.85%) indicates that the hypothesis evaluation step is the main bottleneck, and better evaluation strategies could unlock significant additional performance gains.

Regarding computational efficiency, MAC's runtime depends on the correspondence set size and graph density. For typical settings on 3DMatch with FCGF features (~5,000 correspondences), MAC requires approximately 3.26 seconds, which includes graph construction, maximal clique search, selection, and hypothesis evaluation. While this is slower than single-iteration RANSAC, MAC provides far more reliable results, especially under high outlier rates. The efficiency can be further improved by limiting the correspondence set size or using faster graph algorithms. When integrated as a module into deep-learned pipelines where the correspondence set is typically smaller and of higher quality, MAC adds minimal overhead while consistently improving registration accuracy.

In this paper, we have presented MAC, a 3D point cloud registration method based on maximal cliques. By loosening the maximum clique constraint to maximal cliques, our method mines richer local consensus information from the compatibility graph, generating more accurate and diverse pose hypotheses. The node-guided clique selection strategy ensures computational efficiency with a linear upper bound on hypothesis count. Extensive experiments on U3M, 3DMatch, 3DLoMatch, and KITTI demonstrate that MAC achieves state-of-the-art performance across all tested datasets and is compatible with deep-learned frameworks as a plug-in module.

A noted limitation is that MAC produces accurate hypotheses but may fail to find them — the hypothesis evaluation step remains the bottleneck. The upper-bound analysis (MAC-1 achieving 98.46% / 91.24%) reveals substantial room for improvement. In the future, we plan to develop a more convincing hypothesis evaluation technique utilizing semantic information, which could bridge the gap between hypothesis generation quality and final registration performance. We also envision extending MAC to non-rigid registration and multi-view alignment scenarios, broadening its applicability in real-world 3D vision systems.