# CLIPPER: A Graph-Theoretic Framework for Robust Data Association

arXiv: https://arxiv.org/abs/2011.10202 · HTML: https://mlsanity.com/paper/2011.10202/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2020.

## Built on by (most cited first, 28 of 28)

- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [TurboReg: TurboClique for Robust and Efficient Point Cloud Registration](https://mlsanity.com/paper/2507.01439/) (2025)
- [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023)
- [A New Outlier Removal Strategy Based on Reliability of Correspondence Graph for Fast Point Cloud Registration](https://mlsanity.com/paper/2205.07404/) (2022)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [RANSAC Back to SOTA: A Two-stage Consensus Filtering for Real-time 3D Registration](https://mlsanity.com/paper/2410.15682/) (2024)
- [Pyramid Semantic Graph-based Global Point Cloud Registration with Low Overlap](https://mlsanity.com/paper/2307.12116/) (2023)
- [CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration](https://mlsanity.com/paper/2402.15464/) (2024)
- [GraffMatch: Global Matching of 3D Lines and Planes for Wide Baseline LiDAR Registration](https://mlsanity.com/paper/2212.12745/) (2022)
- [Graph-based Global Robot Localization Informing Situational Graphs with Architectural Graphs](https://mlsanity.com/paper/2303.02076/) (2023)
- [SOS-Match: Segmentation for Open-Set Robust Correspondence Search and Robot Localization in Unstructured Environments](https://mlsanity.com/paper/2401.04791/) (2024)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [Robust Self-Tuning Data Association for Geo-Referencing Using Lane Markings](https://mlsanity.com/paper/2207.14042/) (2022)
- [View-Invariant Localization using Semantic Objects in Changing Environments](https://mlsanity.com/paper/2209.14426/) (2022)
- [3D Registration in 30 Years: A Survey](https://mlsanity.com/paper/2412.13735/) (2024)
- [DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming](https://mlsanity.com/paper/2603.25442/) (2026)
- [MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities](https://mlsanity.com/paper/2210.08360/) (2022)
- [Open-Set Semantic Uncertainty Aware Metric-Semantic Graph Matching](https://mlsanity.com/paper/2409.11555/) (2024)
- [QuadricsReg: Large-Scale Point Cloud Registration using Quadric Primitives](https://mlsanity.com/paper/2412.02998/) (2024)
- [LunarLoc: Segment-Based Global Localization on the Moon](https://mlsanity.com/paper/2506.16940/) (2025)
- [Single-Shot Global Localization via Graph-Theoretic Correspondence Matching](https://mlsanity.com/paper/2306.03641/) (2023)
- [Sight View Constraint for Robust Point Cloud Registration](https://mlsanity.com/paper/2409.05065/) (2024)
- [VISTA: Monocular Segmentation-Based Mapping for Appearance and View-Invariant Global Localization](https://mlsanity.com/paper/2507.11653/) (2025)
- [DualReg: Dual-Space Filtering and Reinforcement for Rigid Registration](https://mlsanity.com/paper/2508.17034/) (2025)
- [DTIF: Robust Loop Closure Detection via Delaunay Triangle Topology in Complex Forests](https://mlsanity.com/paper/2607.21138/) (2026)
- [PARTE: Plane-Assisted Robust Transformation Estimation for Point Cloud Registration](https://mlsanity.com/paper/2609.25375/) (2026)

## Abstract (arXiv)

We present CLIPPER (Consistent LInking, Pruning, and Pairwise Error Rectification), a framework for robust data association in the presence of noise and outliers. We formulate the problem in a graph-theoretic framework using the notion of geometric consistency. State-of-the-art techniques that use this framework utilize either combinatorial optimization techniques that do not scale well to large-sized problems, or use heuristic approximations that yield low accuracy in high-noise, high-outlier regimes. In contrast, CLIPPER uses a relaxation of the combinatorial problem and returns solutions that are guaranteed to correspond to the optima of the original problem. Low time complexity is achieved with an efficient projected gradient ascent approach. Experiments indicate that CLIPPER maintains a consistently low runtime of 15 ms where exact methods can require up to 24 s at their peak, even on small-sized problems with 200 associations. When evaluated on noisy point cloud registration problems, CLIPPER achieves 100% precision and 98% recall in 90% outlier regimes while competing algorithms begin degrading by 70% outliers. In an instance of associating noisy points of the Stanford Bunny with 990 outlier associations and only 10 inlier associations, CLIPPER successfully returns 8 inlier associations with 100% precision in 138 ms. Code is available at https://mit-acl.github.io/clipper.