Cluster-Aware Matching via Laplacian Optimal Transport
Gabriel Samberg, YoonHaeng Hur, Yuehaw Khoo, Nir Sharon
stat.ML, cs.LG, math.NA, stat.ME
Submitted: 2026-07-17
License: http://creativecommons.org/licenses/by/4.0/
The gist: In many applications of matching, the point clouds to be matched are not merely unstructured sets of points but rather samples from distributions with an intrinsic cluster structure.
Terminology
Abstract
In many applications of matching, the point clouds to be matched are not merely unstructured sets of points but rather samples from distributions with an intrinsic cluster structure. In such cases, as individual points are often interchangeable within a coherent region, finding a robust region-to-region alignment is more desirable than establishing a precise point-to-point correspondence. To this end, we propose a novel approach for cluster-aware matching based on Laplacian Optimal Transport (LapOT). The key idea is to regularize the optimal transport problem with quadratic Laplacian terms constructed from similarity graphs of the point clouds, which encourages the optimal coupling to respect the cluster structure of both point sets. We also introduce Refined Simultaneous Clustering (RSC), a method that leverages the cluster-aware coupling obtained from LapOT to produce consistent partitions across the point sets, which can overcome the limitations of independent clustering and yield more stable and interpretable results. We demonstrate the effectiveness of our approach through theoretical analysis and empirical experiments, showing that LapOT indeed produces cluster-aware matching that leads to more consistent and meaningful alignments between point clouds.
Sources
- Gromov-Wasserstein Alignment of Word Embedding Spaces
- MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data
- A Convexified Matching Approach to Imputation and Individualized Inference
- Inference for Clustering: Conformal Sets for Cluster Labels
- Weighted Conformal Clustering
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Scalable Posterior Uncertainty for Flexible Density-Based Clustering
- A Transport Geometry of Benign Overfitting
- Efficient quadratic entropy with distance sketches