Discrete distribution clustering (D2C) was often solved by Wasserstein
barycenter methods. These methods are under a common assumption that clusters
can be well represented by barycenters, which may not hold in many real
applications. In this work, we propose a simple yet effective framework based
on spectral clustering and distribution affinity measures (e.g., maximum mean
discrepancy and Wasserstein distance) for D2C. To improve the scalability, we
propose to use linear optimal transport to construct affinity matrices
efficiently on large datasets. We provide theoretical guarantees for the
success of the proposed methods in clustering distributions. Experiments on
synthetic and real data show that our methods outperform the baselines largely
in terms of both clustering accuracy and computational efficiency.

我们提出了一个基于谱聚类和分布相似度度量（如最大均值差异和 Wasserstein 距离）的简单而有效的框架用于离散分布聚类，并通过使用线性最优输运在大规模数据集上高效地构建相似矩阵，得到了较高的聚类准确率和计算效率。

离散分布的谱聚类

Spectral Clustering for Discrete Distributions

Matching a source to a target probability measure is often solved by
instantiating a linear optimal transport (OT) problem, parameterized by a
ground cost function that quantifies discrepancy between points. When these
measures live in the same metric space, the ground cost often defaults to its
distance. When instantiated across two different spaces, however, choosing that
cost in the absence of aligned data is a conundrum. As a result, practitioners
often resort to solving instead a quadratic Gromow-Wasserstein (GW) problem. We
exploit in this work a parallel between GW and cost-regularized OT, the
regularized minimization of a linear OT objective parameterized by a ground
cost. We use this cost-regularized formulation to match measures across two
different Euclidean spaces, where the cost is evaluated between transformed
source points and target points. We show that several quadratic OT problems
fall in this category, and consider enforcing structure in linear transform
(e.g. sparsity), by introducing structure-inducing regularizers. We provide a
proximal algorithm to extract such transforms from unaligned data, and
demonstrate its applicability to single-cell spatial transcriptomics/multiomics
matching tasks.

在这项工作中，我们利用了 Gromow-Wasserstein 和成本正则化的最小化线性最优传输目标之间的并行性质，参数化一种地面成本函数来匹配两个不同的欧氏空间中的测度，通过在转换后的源点和目标点之间计算成本。我们提供了一种近似算法，从不对齐的数据中提取这样的转换，并证明其适用于单细胞空间转录组学 / 多组学匹配任务。