论文标题
正交Gromov-Wasserstein差异和有效的下限
Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound
论文作者
论文摘要
比较可能不同的度量度量空间中的结构化数据是机器学习中的一项基本任务，例如应用程序分类。 Gromov-Wasserstein（GW）差异基于最佳运输，在结构化数据之间制定了耦合，从而通过对齐估计的内部几何形状来解决不同结构之间的无与伦比。尽管有效\ emph {local}求解器（例如条件梯度和sindhorn）可用，但固有的非固定性仍然可以防止可拖动的评估，并且现有的下限不足以进行实际使用。为了解决这个问题，我们从与二次任务问题的联系中汲取灵感，并提出正交的Gromov-Wasserstein（OGW）差异作为GW的代理。它承认具有$ \ mathcal {o}（n^3）$复杂性的有效和\ emph {封闭形式}下限，并直接延伸到Fused Gromov-Wasserstein（fgw）距离，将节点特征结合到耦合中。在合成数据集和现实世界数据集上进行的广泛实验表明了我们的下限的紧密度，并且OGW及其下限都有效地提供了准确的预测和满足图集的Barycenters。
Comparing structured data from possibly different metric-measure spaces is a fundamental task in machine learning, with applications in, e.g., graph classification. The Gromov-Wasserstein (GW) discrepancy formulates a coupling between the structured data based on optimal transportation, tackling the incomparability between different structures by aligning the intra-relational geometries. Although efficient \emph{local} solvers such as conditional gradient and Sinkhorn are available, the inherent non-convexity still prevents a tractable evaluation, and the existing lower bounds are not tight enough for practical use. To address this issue, we take inspiration from the connection with the quadratic assignment problem, and propose the orthogonal Gromov-Wasserstein (OGW) discrepancy as a surrogate of GW. It admits an efficient and \emph{closed-form} lower bound with $\mathcal{O}(n^3)$ complexity, and directly extends to the fused Gromov-Wasserstein (FGW) distance, incorporating node features into the coupling. Extensive experiments on both the synthetic and real-world datasets show the tightness of our lower bounds, and both OGW and its lower bounds efficiently deliver accurate predictions and satisfactory barycenters for graph sets.
