--- kind: concept slug: maximal-clique-search title: Maximal clique search summary: >- Filters noisy correspondences by finding groups of pairwise-compatible matches that cannot be extended, then fits a rigid pose to each group and keeps the best. MAC, the only variant so far, is training-free and reports 93.72% recall on 3DMatch with FCGF (author-reported). The main trade-off is cost: clique enumeration grows quickly with the number of matches. tags: [robustness, geometry, graph, registration, correspondence-filtering] papers: ["2305.10854"] related: [outlier-rejection, correspondence] status: draft updated_at: 2026-11-08 --- ## Overview Given putative correspondences with many wrong pairs, build a graph whose nodes are correspondences and whose edges join pairs that agree with each other. A group of nodes that are all joined to each other is a clique, and a clique that cannot grow by one more node is maximal [arxiv:2305.10854 §3.2] [arxiv:2305.10854 §3.3]. Every variant shares this idea: a maximal clique is a set of matches that are consistent with each other, so it is a candidate set of inliers. Variants differ in how the graph is weighted, which cliques are kept, and how each candidate is turned into a transform and scored. The compatibility test in the registration setting is a rigid-distance check. A pair of matches is compatible when the distance between their source points is close to the distance between their target points [arxiv:2305.10854 eq. 1]. ## Variants ### Maximal cliques with node-guided selection (MAC) Build a first-order graph from pairwise distance agreement, then a second-order graph that keeps an edge only when the two nodes also share compatible neighbours [arxiv:2305.10854 eq. 3]. Enumerate all maximal cliques of at least three nodes, weight each by the sum of its edge weights [arxiv:2305.10854 eq. 4], and keep for each node only its heaviest clique. Fit one rigid transform per kept clique by SVD with equal weights, and choose the best by a score; the paper names mean absolute error and inlier count as options [arxiv:2305.10854 §3.4]. Card: [3D Registration with Maximal Cliques](/papers/2305.10854). The paper argues against the older approach of searching for a single maximum clique, because one clique uses only the global consensus [arxiv:2305.10854 §3.3]. Its own ablation supports that choice on 3DMatch with FPFH: maximal cliques reach 83.86% recall and the maximum-clique row reaches 74.06% [arxiv:2305.10854 tab. 5]. ## When to use which | Situation | Use | Why | |---|---|---| | Two point clouds, correspondences from FPFH or FCGF, no training data | MAC | Training-free; author-reported recall of 84.10% (FPFH) and 93.72% (FCGF) on 3DMatch [arxiv:2305.10854 tab. 1] | | Low overlap or heavy noise, where the wrong-match rate is high | MAC, and check the score | Reported 40.88% (FPFH) and 59.85% (FCGF) on 3DLoMatch [arxiv:2305.10854 tab. 2]; hypothesis scoring, not clique search, limits accuracy, since a perfect judge gives 98.46% [arxiv:2305.10854 tab. 7] | | Already have a learned matcher and want a post-filter | MAC as a boost | Author-reported gains at 5000 matches: GeoTransformer 92.0 to 95.7 and FCGF 85.1 to 91.3 on 3DMatch [arxiv:2305.10854 tab. 3] | | Many matches (thousands) and a tight latency budget | Reduce the match count first, or pick a cheaper filter | Time per pair rises from 7.08 ms at 250 matches to 3265.42 ms at 5000, with clique search 48.37% of the 5000 case [arxiv:2305.10854 tab. 8] | | Memory-constrained device | MAC is reported as lighter than PointDSC and TEASER++ at 5000 matches [arxiv:2305.10854 tab. 13] | Measured on the authors' hardware (Intel 12700H CPU, 32 GB RAM, CPU only) [arxiv:2305.10854 §4.1] | | Datasets with unknown or different inlier thresholds | Set the threshold on validation data | The paper leaves the MAE inlier threshold tau unstated [arxiv:2305.10854 §3.4] | The paper does not compare MAC with every clique-based variant. Results come from its own benchmarks (3DMatch, 3DLoMatch, KITTI, U3M and ETH) and use its chosen baselines [arxiv:2305.10854 §4.1] [arxiv:2305.10854 §4.2]. Numbers from one benchmark should not be read as general speed or accuracy claims. ## Implementation sketch The common core, as the card describes it. Variants change the marked steps. ```pseudocode # Maximal-clique filtering then per-clique fit [arxiv:2305.10854 §3] # Input: src (N, 3), tgt (N, 3): N putative correspondences # Output: rigid transform (R, t) in SE(3) def clique_register(src, tgt, d_cmp, t_cmp): # Pairwise compatibility from distance agreement [eq. 1] [eq. 2] fog = compat_weights(src, tgt, d_cmp, t_cmp) # (N, N) # Second-order weights, the MAC default [eq. 3] sog = fog * (fog @ fog) # (N, N) # Every maximal clique with at least 3 nodes [§3.3] cliques = maximal_cliques(sog, min_size=3) # Clique weight: sum of pairwise edge weights [eq. 4] w = [clique_weight(c, sog) for c in cliques] # Keep the heaviest clique per node, drop duplicates [§3.3] kept = node_guided_select(cliques, w, num_nodes=N) # One rigid fit per kept clique, equal weights [§3.4] hyps = [svd_fit(src[c], tgt[c]) for c in kept] # Score each hypothesis; MAC uses MAE in the code [§3.4] return best_by_score(hyps, src, tgt) ``` Variants change the compatibility kernel (in the paper, a Gaussian of the distance mismatch), the order of the graph, the clique filter and the score. The card's Paper vs code section lists the settings the authors' repository uses. ## Contradictions - **Compatibility kernel.** The paper gives a Gaussian of the distance mismatch [arxiv:2305.10854 eq. 2]. The authors' repository uses a linear kernel for its KITTI path and its Python demos, and the Gaussian for the 3DMatch and 3DLoMatch C++ path. The card lists the file references [card: 2305.10854, Paper vs code]. - **Compatibility threshold.** The paper sets t_cmp to 0.99, rising to 0.999 above 5000 matches [arxiv:2305.10854 §4.1]. The repository uses other values per dataset and descriptor, for example 0.995 for FPFH on 3DMatch and 0.9 for FPFH on KITTI [card: 2305.10854, Paper vs code]. - **Timing.** At 5000 matches the paper gives 3265.42 ms in one table and 3259.38 ms in another [arxiv:2305.10854 tab. 8] [arxiv:2305.10854 tab. 12]. The paper does not explain the gap. - **Refinement.** The paper's text does not describe a post-refinement step. The repository runs one [card: 2305.10854, Paper vs code], so reported numbers may depend on code the paper does not describe. ## Papers - [3D Registration with Maximal Cliques](/papers/2305.10854): training-free point-cloud registration that enumerates maximal cliques of a second-order correspondence graph and keeps one clique per node by weight.