Aligning two 3D scans usually starts by guessing which points in one scan match which points in the other. Most of these guessed matches are wrong. The most robust current methods throw out bad matches by building a "compatibility graph": each candidate match is a node, and two nodes are joined by an edge if the pair preserves distances the way a rigid motion must. The correct matches should then form a clique, a group in which every pair is connected. The trouble is sensor noise. Every pairwise test has some chance of wrongly rejecting two correct matches. As the set of correct matches grows, the chance that all of their pairwise tests pass shrinks exponentially, so the true clique breaks into pieces. Loosening the test tolerance repairs the clique but lets wrong matches in.
We propose to stop demanding a perfect clique. Instead, each correct match is allowed a small, individually computed number of missing edges, sized from how uncertain that particular point's position is. The resulting structure is a generalized k-plex: a group in which each member may miss a few connections to other members. Each point's positional uncertainty comes from a cheap local Gaussian-process fit to its neighborhood. We then search for the largest such group with an exact branch-and-bound method. That method first branches on "saturated" candidates, the ones that have already used up their missing-edge allowance, adapted here so that the allowance differs from candidate to candidate. In short, probabilistic point modeling sets the tolerance, and combinatorial search enforces it exactly.
Core Claim
The core claim is that the false rejections caused by noise in compatibility graphs follow a predictable pattern, and a cohesive-subgraph model can absorb them exactly. Consider a correct match $i$ among $n$ correct matches. Let $p_{ij}$ be the probability that the distance-preservation test between $i$ and $j$ fails because of noise alone. This probability is computable once each keypoint carries a positional covariance. The number of edges $i$ loses, $M_i = \sum_{j} B_{ij}$ with $B_{ij} \sim \text{Bernoulli}(p_{ij})$, has mean $\sum_j p_{ij}$. That mean grows linearly in $n$. The probability that the full correct set survives as a clique behaves like
$$ P(\text{clique intact}) \approx \prod_{i<j} (1 - p_{ij}) \approx \exp\!\left(-\tfrac{1}{2} n^2 \bar p\right), $$
where $\bar p$ is the average pairwise false-rejection rate. This approximation treats the pairwise failures as independent. No single tolerance setting escapes this: shrinking $\bar p$ requires loosening the test, which admits outliers.
We therefore give each match a budget $k_i = 1 + Q_{1-\delta}(M_i)$, where $Q_{1-\delta}$ is the $(1-\delta)$ quantile of the predicted miss count and $\delta$ is a user-chosen failure rate. We then search for the largest set $S$ in which every member $i$ misses at most $k_i - 1$ others in $S$. Uniform k-plexes are the special case $k_i = k$. Cliques are the case $k_i = 1$.
The claim is new in two ways. Existing registration methods use either cliques with a fixed threshold or polynomial-time relaxations that are blind to uncertainty. Existing k-plex solvers use only uniform budgets on unweighted social graphs.
Relation to Prior Work
Three registration methods motivate this proposal by showing that cohesive-subgraph search is the most robust way to reject outliers.
CLIPPER+ finds maximal cliques on a binary compatibility graph. It first runs a greedy search that visits vertices in degeneracy order, then prunes vertices by core number, then refines with a continuous relaxation. It reports success at over 99% outlier associations. PointMC enumerates maximal cliques with Bron–Kerbosch on a second-order compatibility graph to separate multiple object instances. PointTruss replaces cliques with k-trusses, groups in which every edge sits in at least $k-2$ triangles, which can be found in polynomial time. All three binarize compatibility with a threshold that does not depend on the points involved.
PointTruss already relaxes the clique, which makes it our most direct competitor. However, its relaxation is per-edge and uniform. It does not encode the fact that a match on a noisy, grazing-angle surface patch should be forgiven more misses than a match on a sharp corner.
The search method comes from Efficient Enumeration of Large Maximal k-Plexes. That work contributes three ingredients. It branches first on saturated vertices. It proves that, under degeneracy ordering, any k-plex of size at least $2k-1$ lies within a 2-hop neighborhood. It adds vertex-pair pruning rules (R1, R2) that alone gave up to a 7x speedup. Its setting is static, unweighted web and social graphs with a single $k$. Our contribution is to carry these ingredients over to per-vertex budgets.
The uncertainty estimate comes from GPnn. GPnn makes Gaussian-process regression scale by fitting hyperparameters once on a subset and then predicting from only the $m$ nearest neighbors. It adds a calibration step so that predicted variance matches actual squared error. That "weak calibration" is exactly what we need, because our budgets depend on the mean miss count rather than on full distributional shape.
Probabilistic registration constrains the design. MMD-Reg treats clouds as distributions and aligns them by minimizing maximum mean discrepancy, a kernel distance between distributions, computed in linear time. It tolerates 80% outliers, but it needs a learned coarse initializer for large rotations. That is evidence that density matching is a local refiner, not a global outlier rejector. We therefore use it only as the downstream refinement step and not as a competitor for global rejection. GiNGR also uses Gaussian processes in registration, but it uses them as a prior over non-rigid deformation. We use them for per-keypoint localization uncertainty.
Research Program
The first component is the uncertainty front end. For each keypoint, we take its $m$ nearest neighbors in the raw cloud. We fit a GPnn-style local Gaussian process that models the surface as a height field in the keypoint's tangent frame, with hyperparameters shared across the scan, and apply GPnn's calibration step. The posterior variance along the surface normal, combined with a sensor range-noise model, gives a 3D covariance for each keypoint. Propagating the two covariances through the distance difference $\big|\|x_i-x_j\| - \|y_i-y_j\|\big|$ to first order gives $p_{ij}$ in closed form. The cost is one small Gaussian-process solve per keypoint plus one scalar evaluation per graph edge. This front end should be negligible next to descriptor computation.
The second component is the budgeted-plex solver. Saturation becomes per-vertex: candidate $i$ is saturated once it misses $k_i - 1$ members of the partial solution. The uniform-case argument for the 2-hop bound shows that two non-adjacent members must share a neighbor. We expect it to carry over with $2k$ replaced by $k_u + k_v$ for the specific pair, giving pair-specific confinement to 2-hop neighborhoods. Rules R1 and R2 generalize in the same way. Proving these bounds and verifying them on adversarial small graphs is a concrete theoretical deliverable.
Following CLIPPER+, we seed the search with a greedy, degeneracy-ordered solution and use its size as a lower bound. This allows aggressive core-number pruning before the exact search begins. Rigid registration needs only the single largest budgeted plex. Multi-instance registration in the style of PointMC needs all large maximal ones, so we run the enumeration version for that case.
The third component, secondary in scope, is a streaming extension for LiDAR odometry. Consecutive frames share most of their keypoints, and no work in the file maintains k-plexes under edge changes. Maintenance work such as FreshVamana preserves only routing connectivity. We will test whether keeping the previous frame's plex and per-vertex miss counts, and repairing them locally, beats re-solving from scratch. We treat this as a measurable engineering question rather than a headline claim.
Baselines
The naive reference is a plain clique with a single tuned threshold: CLIPPER+'s maximal-clique pipeline on the same correspondences, threshold chosen by grid search on a held-out split. It is also the strongest existing exact-structure method. CLIPPER+ reports surviving over 99% outliers on Bunny-style data and roughly 2x runtime gains over its optimization-only variant on 7-Scenes, Sun3D, and ETH. The file gives no reported Bunny recall or rotation error. Beating it means higher registration recall at matched runtime in the high-noise, moderate-outlier regime, with no loss at 99% outliers.
The strongest relaxed-structure competitor is PointTruss. It reports 43.96% registration recall on 3DLoMatch, and 99.64% recall at 0.21 s on KITTI. We will rerun it on identical correspondence sets with the same descriptor front end. Its truss parameter gets the same tuning budget as our $\delta$. Beating it means exceeding 43.96% on 3DLoMatch with those shared inputs. KITTI is near ceiling, so there we only require matching recall at comparable latency.
For multi-instance registration, the baseline is PointMC. It reports 94.85% recall and 99.76% precision on its multi-instance ModelNet40 benchmark, and a 27.4% recall gain on Scan2CAD over multi-model fitting. Beating it means higher Scan2CAD recall with the same pose-clustering stage.
Three ablations isolate the key ingredient. The first is a uniform k-plex with the best single $k$ chosen per dataset. The second is per-pair adaptive thresholds (Mahalanobis tests using the same covariances) followed by a plain clique. The third keeps the budgeted plex but replaces the Gaussian-process covariances with local-PCA covariances, computed from the spread of each keypoint's neighbors in the manner of normal-distributions-transform (NDT) cells. All variants share correspondences, solver code, hardware, and tuning budget. Solver runtime will also be compared against the uniform-$k$ enumerator from Efficient Enumeration of Large Maximal k-Plexes on SNAP graphs. That paper reports up to 5x sequential speedup over ListPlex, and our generalization should cost little when all budgets are equal.
Why not just…?
Why not just loosen the clique threshold? A looser threshold lowers every $p_{ij}$, but the clique-survival probability still decays like $\exp(-n^2\bar p/2)$. Meanwhile, every increase in tolerance admits more outlier edges. This is precisely why CLIPPER+-style pipelines must pick thresholds carefully. The tuned-threshold baseline settles the question empirically. If its best grid-searched setting matches us on 3DLoMatch and on high-noise Bunny, the core claim fails.
Why not just use per-pair adaptive thresholds with the same uncertainty? This is the most serious alternative, because it uses the same covariance information with no new solver. It still has a nonzero miss rate $\alpha$ per pair, though, so each correct match expects to lose $\alpha(n-1)$ edges, and large correct sets still fragment. Adaptive thresholds calibrate which edges exist, while budgets forgive the misses that calibration cannot prevent. The two are complementary, and our method uses calibrated tests inside the plex. The ablation shows how much of the gain is due to the budget rather than the calibration. If the gap is negligible once $n$ is large, we will report that the cheaper method suffices.
Why not just use PointTruss, which already tolerates missing edges in polynomial time? A k-truss requires each edge to sit in enough triangles. That constraint limits missing edges only indirectly and uniformly, and it can admit outlier clusters that are densely triangulated among themselves. We expect the advantage to appear where uncertainty varies most within a scene: low-overlap indoor pairs and sparse outdoor scans. If PointTruss matches us there at lower cost, the exactness of budgeted search is not paying for itself.
Why not just use local PCA instead of a Gaussian process? It may well be enough. The PCA-covariance ablation decides this directly. If it matches the Gaussian-process front end on calibration (predicted versus observed miss counts) and on recall, we drop the Gaussian process.
Proposed Experiments
The first decisive check is calibration. On 3DMatch pairs with ground-truth poses, we compare each true match's predicted miss count $\sum_j p_{ij}$ to its observed miss count in the actual graph. Pairwise failures are correlated because they share points, so we will measure the correlation and widen the quantile if the predicted counts underestimate the observed ones.
The second check is a controlled sweep on the Stanford Bunny. We cross additive noise levels with outlier ratios from 50% to 99% and plot registration recall and rotation error for all baselines and ablations. The prediction is that our advantage grows with noise and with inlier count, and vanishes in the low-noise, 99%-outlier corner where true cliques are small and survive intact.
The third check covers real data: 3DMatch, 3DLoMatch, and KITTI with shared descriptors, plus Scan2CAD and multi-instance ModelNet40 for the enumeration variant. Every recovered pose is refined by MMD-Reg so that differences come from correspondence selection alone. We report registration recall, rotation and translation error, precision and recall of the selected inlier set, and wall-clock time split into front end and solver.
The fourth check is solver scaling. We record runtime against graph size and budget spread, and test on SNAP graphs with uniform budgets to confirm the generalized pruning rules lose nothing relative to the original enumerator.
Finally, the streaming check runs on KITTI odometry sequences. It compares incremental plex repair against per-frame re-solving on latency and on agreement with the exact per-frame optimum.
References
- CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration
- PointMC: Multi-instance Point Cloud Registration based on Maximal Cliques
- PointTruss: K-Truss for Point Cloud Registration
- Efficient Enumeration of Large Maximal k-Plexes
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Scalable and Differentiable Point-Cloud Registration Using Maximum Mean Discrepancy
- GiNGR: Generalized Iterative Non-Rigid Point Cloud and Surface Registration Using Gaussian Process Regression
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search