arXiv:2411.02198math.MGcs.LG2024-11被引 2

提出更鲁棒的局部Gromov-Wasserstein距离,解决原始方法对异常值敏感和不支持部分匹配的问题。

Metric properties of partial and robust Gromov-Wasserstein distances

  • 通过松弛优化问题,引入对异常值和局部匹配更鲁棒的新距离定义
  • 新距离满足度量公理,且与原始GW距离诱导相同拓扑
  • 适用于存在噪声或不完整数据的网络分析、几何处理场景

Gromov-Wasserstein(GW)距离是一类基于最优传输思想的度量,可用于比较定义在不同度量空间上的概率测度,在网络分析和几何处理中尤为有用。尽管其在机器学习中有广泛应用,但已知其对异常值敏感且无法处理部分匹配。本文聚焦于Chapel等人提出的自然松弛版本,从度量几何视角研究其理论性质。该松弛问题虽不构成度量,但可精确刻画其违背非退化性与三角不等式的程度。据此,我们受Prokhorov、Ky Fan及Raghvendra等人工作启发,提出一类新距离,满足度量公理,诱导与原始GW距离相同的拓扑,并具备更强抗扰动能力。这些结果为在含异常值或部分匹配的应用中使用鲁棒局部GW距离提供了数学严谨基础。

原文摘要 · Abstract (English)

The Gromov-Wasserstein (GW) distances define a family of metrics, based on ideas from optimal transport, which enable comparisons between probability measures defined on distinct metric spaces. They are particularly useful in areas such as network analysis and geometry processing, as computation of a GW distance involves solving for registration between the objects which minimizes geometric distortion. Although GW distances have proven useful for various applications in the recent machine learning literature, it has been observed that they are inherently sensitive to outlier noise and cannot accommodate partial matching. This has been addressed by various constructions building on the GW framework; in this article, we focus specifically on a natural relaxation of the GW optimization problem, introduced by Chapel et al., which is aimed at addressing exactly these shortcomings. Our goal is to understand the theoretical properties of this relaxed optimization problem, from the viewpoint of metric geometry. While the relaxed problem fails to induce a metric, we derive precise characterizations of how it fails the axioms of non-degeneracy and triangle inequality. These observations lead us to define a novel family of distances, whose construction is inspired by the Prokhorov and Ky Fan distances, as well as by the recent work of Raghvendra et al.\ on robust versions of classical Wasserstein distance. We show that our new distances define true metrics, that they induce the same topology as the GW distances, and that they enjoy additional robustness to perturbations. These results provide a mathematically rigorous basis for using our robust partial GW distances in applications where outliers and partial matching are concerns.

度量学习最优传输鲁棒性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。