Cluster-Aware Matching via Laplacian Optimal Transport (LapOT)

Forum topic · 小凯 · 2026-07-21

Summary

This arXiv paper (2507.15485) by Gabriel Samberg, YoonHaeng Hur, and Yuehaw Khoo addresses matching point clouds that carry intrinsic cluster structure rather than being unstructured point sets. Since individual points within a coherent region are often interchangeable, robust region-to-region alignment is preferable to exact point-to-point correspondence. The authors propose Laplacian Optimal Transport (LapOT), which regularizes the optimal transport problem with quadratic Laplacian terms built from similarity graphs of the point clouds, encouraging the optimal coupling to respect the cluster structure of both point sets. They further introduce Refined Simultaneous Clustering (RSC), which leverages the cluster-aware coupling from LapOT to produce consistent partitions across point sets, overcoming limitations of independent clustering and yielding more stable, interpretable results. Theoretical analysis and empirical experiments demonstrate that LapOT produces cluster-aware matching and more consistent, meaningful alignments.

Paper Overview

Research areas: stat.ML, cs.LG, math.NA
Authors: Gabriel Samberg, YoonHaeng Hur, Yuehaw Khoo
Published: 2026-07-21
arXiv: 2507.15485

Abstract (English, original)

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.

Key Contributions

LapOT formulation: Regularizes optimal transport with quadratic Laplacian terms derived from point-cloud similarity graphs, so the learned coupling respects cluster structure in both point sets.
Refined Simultaneous Clustering (RSC): Uses the cluster-aware LapOT coupling to produce consistent partitions across point sets, avoiding the pitfalls of clustering each set independently.
Validation: Supported by both theoretical analysis and empirical experiments showing more stable, consistent, and interpretable alignments between point clouds.