提出新型切片融合吴生-瓦瑟斯坦距离，高效且保持几何不变性。
A Novel Sliced Fused Gromov-Wasserstein Distance
- 基于低维优化与分层配对，设计新切片方法
- 计算量显著降低，同时保持等距不变性
- 适合形状检索与图同构检测等场景
吴生-瓦瑟斯坦（GW）距离及其融合扩展（FGW）是对比异质数据的强大工具，但其计算困难，因二者均基于非凸的二次最优传输问题。已有基于一维最优传输的切片GW方法虽降低了计算负担，却仅限于欧几里得几何，且丧失等距不变性，严重限制实际应用。为此，我们提出一种新的切片技术，适用于GW与FGW，该方法基于合适的下界、分层最优传输及适用于一维问题的合适求积规则。所提新型切片FGW在保持等距不变性的同时，显著减少数值计算量，并可比较任意几何结构。我们证明该新距离在结构空间中构成伪度量，且从下方逼近FGW，并研究其在切片沃尔什距离与GW之间的插值性质。由于避免了原始的二次规划，该切片距离在数值上比原版更稳健可靠，尤其适用于形状检索与图同构测试。
原文摘要 · Abstract (English)
The Gromov--Wasserstein (GW) distance and its fused extension (FGW) are powerful tools for comparing heterogeneous data. Their computation is, however, challenging since both distances are based on non-convex, quadratic optimal transport (OT) problems. Leveraging 1D OT, a sliced version of GW has been proposed to lower the computational burden. Unfortunately, this sliced version is restricted to Euclidean geometry and loses invariance to isometries, strongly limiting its application in practice. To overcome these issues, we propose a novel slicing technique for GW as well as for FGW that is based on an appropriate lower bound, hierarchical OT, and suitable quadrature rules for the underlying 1D OT problems. Our novel sliced FGW significantly reduces the numerical effort while remaining invariant to isometric transformations and allowing the comparison of arbitrary geometries. We show that our new distance actually defines a pseudo-metric for structured spaces that bounds FGW from below and study its interpolation properties between sliced Wasserstein and GW. Since we avoid the underlying quadratic program, our sliced distance is numerically more robust and reliable than the original GW and FGW distance; especially in the context of shape retrieval and graph isomorphism testing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。