Where the Hardness Lives in Clique-Based Registration

Many robust 3D registration systems align two point clouds in a particular way. They first throw away rotation and translation by comparing distances between pairs of matched points, since distances are unchanged by any rigid motion. They then build a "consistency graph," in which two candidate matches are linked if they preserve their mutual distance. Finally they search this graph for its largest clique, a set of matches that are all pairwise consistent, and treat that clique as the inliers. This step makes pipelines like TEASER++ and CLIPPER+ robust to 99% wrong matches. It also swaps a low-dimensional geometric problem, finding the one rigid motion that agrees with the most matches, for maximum clique. In parameterized complexity, maximum clique is among the hardest problems to approximate even when the running time may grow exponentially in the answer size $k$. This note asks whether that swap really imports the hardness.

Our claim is that it does not, except in a narrow way we can name. In three dimensions, a set of matches that are all pairwise distance-consistent within tolerance $\epsilon$ must, we conjecture, agree with a single rigid motion or its mirror image to within a larger tolerance $\delta$. The value of $\delta$ depends on $\epsilon$ and on how well-spread the clique's points are. If this holds, clique on these graphs has a polynomial-time bicriteria approximation: it recovers at least as many matches as the optimal clique, while loosening the tolerance from $\epsilon$ to $\delta$. Any fixed-parameter inapproximability can then only live in two places, the exact-tolerance version and nearly degenerate geometry such as flat or collinear scenes. We propose to prove the positive side, try to prove the negative side by a reduction, and build and test the algorithm the positive side implies.

Background and the Gap

The first direction is rotation-translation decoupling. TEASER removes translation by differencing pairs of correspondences and removes rotation by taking norms. It then solves scale, rotation, and translation in a cascade, after pruning outliers with Max Clique Inlier Selection on the pairwise consistency graph. Two other systems supply the clique solvers. CLIPPER+ finds a maximal clique by greedy search guided by core numbers followed by a continuous relaxation, and gives no bound on how far that clique falls short of the maximum. PMC is an exact branch-and-bound solver, fast on scans with up to 5000 correspondences but exponential in the worst case. All three motivate this work, because all three treat the consistency graph as an arbitrary graph.

The second direction is fixed-parameter inapproximability, which studies how well a problem can be approximated in time $f(k)\cdot n^{O(1)}$, where $n$ is the input size and $k$ the size of the answer. It constrains us. Under the Gap Exponential Time Hypothesis, $k$-Clique has no $o(\mathrm{OPT})$ approximation in such time (From Gap-ETH to FPT-Inapproximability). Under the weaker assumption $W[1]\neq FPT$ there is still no $k^{o(1)}$ approximation (Simple Combinatorial Construction of the k^o(1) Lower Bound). Taken at face value, these results say the clique step in registration should be hopeless in the worst case, yet the solvers above report near-perfect inlier recovery. The research file frames this tension as open.

The closest positive-side work does not settle it. Provably Approximated Point Cloud Registration gives a $(1+\sqrt2)^d$ approximation, but for correspondence-free alignment under moderate (20–50%) outliers. Deterministic Approximate Methods for Maximum Consensus converges to local optimality conditions without any bound on how many inliers it finds. Neither analyzes the consistency graph.

A counting argument shows the gap is real and not just unexplored. With $n$ correspondences in $\mathbb{R}^3$, the graph is fixed by $6n$ real coordinates through degree-bounded polynomial comparisons. Standard bounds on the number of sign patterns of polynomials therefore allow only $n^{O(n)}$ distinct consistency graphs, against $2^{\Theta(n^2)}$ graphs in total. So consistency graphs are a thin, semi-algebraic family, and the general-graph hardness proofs, which rely on dense products and random compression, need not apply to them.

Core Claim

Call a set $S$ of correspondences $(p_i,q_i)$ $\epsilon$-consistent if every pair satisfies

$$\big|\,\|p_i-p_j\|-\|q_i-q_j\|\,\big|\le\epsilon .$$

The stability conjecture is that there is an isometry $T$ (a rotation plus translation, possibly composed with a reflection) such that every $i\in S$ satisfies $\|T p_i - q_i\|\le \delta(\epsilon,\kappa,D)$. Here $D$ is the diameter of $S$ and $\kappa$ measures how far the best-spread triple of points in $S$ is from collinear. For well-spread sets we expect $\delta = O(\kappa\,\epsilon)$. For arbitrary finite sets we expect the weaker $O(\sqrt{\epsilon D})$ scaling that is typical of approximate-isometry stability on bounded subsets. That square-root form comes from the second-order way distance errors trade against lateral displacement.

Two consequences follow. First, every triangle of a clique (three mutually consistent matches) determines a candidate motion. Trying all triangles of the consistency graph, and counting matches consistent with each candidate at tolerance $\delta$, returns a consensus set at least as large as the maximum $\epsilon$-clique, in polynomial time. The converse is trivial: a consensus set at $\epsilon/2$ is a $\epsilon$-clique. Second, distances cannot tell a motion from its mirror image, so a pure distance clique can mix matches from the two. This is a concrete way the decoupling step loses information, and the algorithm resolves it for free.

Research Program

The theory has two halves. On the positive side we will prove the stability lemma with explicit constants in $\mathbb{R}^3$. We will then show that triangle enumeration gives a bicriteria $(1, \delta/\epsilon)$ approximation. The cost is the number of triangles in the consistency graph, which is far below $n^3$ at high outlier rates because outlier edges are sparse.

On the negative side we will attempt parameter-preserving reductions from $k$-Clique to exact-tolerance consistency clique. Parameter-preserving means the new answer size depends only on $k$. We will use the combinatorial construction of Chen et al. as the source instance and try to embed it in two regimes where the conjecture predicts room for hardness: nearly collinear point sets, where $\kappa$ is unbounded, and dimension $d$ growing with $k$. A reduction of either kind would show that the geometric parameter $\kappa$, or the dimension, is exactly where the $W[1]$ barrier sits. Either outcome is informative. A proof that no such reduction exists in fixed dimension with bounded $\kappa$ would be equally valuable.

The engineering half builds the triangle-enumeration solver as a drop-in replacement for the clique step in TEASER++. The theory will also be used adversarially. The reduction gadgets and the mirror-mixing construction will generate registration instances meant to force CLIPPER+ and greedy maximal-clique search away from the maximum.

Baselines

The naive reference is three-point RANSAC. It samples correspondence triples, fits a motion, and counts inliers. It is the do-nothing option because it ignores the graph entirely. It will run on the same correspondences with the same inlier threshold. We report it both at equal wall-clock time and at the iteration count its standard stopping rule prescribes. The best reported number on the file's benchmarks is 66.8% registration recall on 3DMatch, for 3DMatch descriptors combined with RANSAC (3DMatch).

The strongest existing system is TEASER++, whose clique-based pruning followed by certifiable rotation estimation is reported to reach a 98.6% success rate on 3DMatch scan matching (TEASER). We will swap only its clique step and keep its rotation and translation stages, correspondences, and threshold fixed. Beating it on 3DMatch means matching 98.6% within noise. It does not mean exceeding it, because we do not expect gains on benign data. The real target is higher success on the adversarial and near-degenerate splits at comparable runtime.

CLIPPER+ is the strongest heuristic clique solver. The file quotes no numeric registration score for it on 7-Scenes, SUN3D, or ETH, only "highest accuracy." We will therefore run the released method ourselves under identical graphs.

PMC is the exact reference. For $N\le 5000$ it gives the true maximum clique, against which we measure every method's clique-size ratio. We will match its time budget and report cases where it times out.

Two ablations isolate the key ingredient. The first uses exhaustive triangle enumeration at the strict tolerance $\epsilon$ rather than $\delta$, which tests whether the tolerance slack is doing the work. The second samples triangles at random from the graph rather than enumerating them. This "graph-guided RANSAC" tests whether determinism and exhaustiveness matter or only the restriction to graph triangles. A third ablation drops the mirror-image check.

Why not just…?

Why not just run RANSAC, since triangle enumeration is RANSAC made exhaustive? This is the most serious threat, and we say so plainly. The algorithm differs in only two ways: it enumerates only triangles of the consistency graph, and it comes with a guarantee relative to the maximum clique. At 99% outliers, an all-inlier random triple has probability about $10^{-6}$. That is why TEASER++ is reported to beat optimized RANSAC on 3DMatch while running faster (TEASER), and why PMC is reported up to an order of magnitude faster than RANSAC at over 90% outliers (PMC). The graph-guided random-triangle ablation settles whether exhaustiveness adds anything beyond restricting samples to graph triangles. If it does not, the contribution reduces to the theory, and we will report it that way.

Why not just run PMC, since exact clique is already fast on real scans? On benign scans PMC's runtime is acceptable, but it has no polynomial worst-case bound. PMC also solves the relaxed problem exactly, including cliques that mix mirror-image matches or drift over long, thin structures. Comparing PMC's clique with the best single-motion consensus set on the adversarial split shows how often the exact maximum clique is the wrong inlier set.

Why not just trust CLIPPER+, which is "often the maximum in practice"? Its authors state that it returns a maximal clique without guarantee (CLIPPER+). Evidence that it succeeds on 7-Scenes, SUN3D, and ETH says nothing about instances built to defeat it. The adversarial generator tests exactly this. If CLIPPER+ still finds the maximum there, that itself is evidence for our structural claim.

Why not skip graphs and run maximum consensus over rotation and translation directly? Branch-and-bound over the motion parameters is exact but reported to be orders of magnitude slower than TEASER++ (TEASER). Penalty methods give no bound on inlier count (Deterministic Approximate Methods). Our proposal is in effect a bridge: it uses the graph only to generate candidate motions and then scores true consensus.

Proposed Experiments

On the Stanford 3D Scanning Repository models, we will inject outliers from 50% to 99%, add noise, and use $N\in\{1000,3000,5000\}$ as in PMC. We report the ratio of recovered clique or consensus size to PMC's maximum, rotation error in degrees, translation error, and runtime. On 3DMatch we report registration recall at 15° and 30 cm, with correspondences from the 3DMatch descriptor. On Mian's dataset and SUN3D we test cluttered and partial-overlap scenes.

The decisive checks come from three constructed splits. The first contains near-planar and near-collinear scenes, such as corridors and floors, with controlled $\kappa$. The second contains symmetric objects with mirror-consistent outlier matches injected. The third contains instances generated from the attempted $k$-Clique reduction.

The conjecture makes four falsifiable predictions. The empirical $\delta$ needed to capture a clique should grow as $\kappa$ worsens, following the predicted $\kappa\epsilon$ or $\sqrt{\epsilon D}$ law. Heuristic clique solvers should fail first on the low-$\kappa$ and mirror splits. The exhaustive enumerator should stay within its bicriteria bound everywhere. Its triangle count should scale far below $n^3$ as outlier rate rises. If well-conditioned cliques ever require $\delta$ growing faster than linearly in $\epsilon$, the stability conjecture is wrong and the hardness story shifts back to general graphs.