[KDD 2022 | 论文简读] HyperAid:用于树拟合和层次聚类的双曲空间去噪

简读分享 | 龙文韬 编辑 | 王宇哲

论文题目

HyperAid: Denoising in Hyperbolic Spaces for Tree-fitting

and Hierarchical Clustering

论文摘要

由于在自然语言处理、系统发育、癌症基因组学和大量涉及分层聚类的问题领域的许多应用，用树形度量拟合距离的问题在理论计算机科学和机器学习界都得到了极大的关注。尽管存在几种可证明的精确算法，用于对本质上服从树形度量约束的数据进行树形度量拟合，但对于如何对结构与树形有适度（或大幅）差异的数据进行最佳的树形度量拟合，人们所知甚少。对于这种有噪声的数据，大多数可用的算法表现不佳，并且经常在代表树中产生负的边缘权重。此外，目前还不知道如何选择最合适的近似目标进行噪声拟合。作者的贡献如下：首先，作者提出了一种在双曲空间中进行树度量去噪的新方法（HyperAid），当以Gromov的δ双曲性来评价时，该方法将原始数据转化为更像树的数据。其次，作者进行了消融研究，涉及两种近似目标，ℓp范数和Dasgupta损失。第三，作者将HyperAid与强制非负边权的方案集成在一起。因此，无论是在合成数据还是在真实数据上，HyperAid平台都优于文献中现有的所有方法，包括Neighbor Joining（NJ）、TreeRep和T-REX。合成数据由边缘增强树和最短距离指标表示，而真实世界数据集包括Zoo、Iris、Glass、Segmentation和SpamBase；在这些数据集上，相对于NJ的平均改进为125.94%。

论文链接

https://dl.acm.org/doi/10.1145/3534678.3539378