提出可微方法将任意度量空间转化为近似树度量，提升结构表示精度。
Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
- 设计可微的Gromov超曲率替代函数，支持梯度优化
- 在合成与真实数据集上实现最优扭曲度（distortion）表现
- 适合需要结构化嵌入的图神经网络与聚类任务
树及其对应的最短路径树度量为数据中的层次与组合结构提供了强大表示框架。给定任意度量空间，其偏离树度量的程度可通过Gromov的δ-超曲率量化。然而，设计能将任意度量映射到最近树度量的算法仍是研究热点，因现有方法要么为启发式且无保证，要么性能一般。本文提出一种新型可微优化框架DeltaZero，解决该问题。方法利用Gromov δ-超曲率的平滑替代函数，实现基于梯度的优化，且计算复杂度可控。优化过程源自一个最坏情况保证优于现有边界的问题，并经统计验证。在合成与真实数据集上的实验表明，本方法在扭曲度上持续达到当前最优表现。
原文摘要 · Abstract (English)
Trees and the associated shortest-path tree metrics provide a powerful framework for representing hierarchical and combinatorial structures in data. Given an arbitrary metric space, its deviation from a tree metric can be quantified by Gromov's $δ$-hyperbolicity. Nonetheless, designing algorithms that bridge an arbitrary metric to its closest tree metric is still a vivid subject of interest, as most common approaches are either heuristical and lack guarantees, or perform moderately well. In this work, we introduce a novel differentiable optimization framework, coined DeltaZero, that solves this problem. Our method leverages a smooth surrogate for Gromov's $δ$-hyperbolicity which enables a gradient-based optimization, with a tractable complexity. The corresponding optimization procedure is derived from a problem with better worst case guarantees than existing bounds, and is justified statistically. Experiments on synthetic and real-world datasets demonstrate that our method consistently achieves state-of-the-art distortion.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。