HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering
The problem of fitting distances by tree-metrics has received significant
attention in the theoretical computer science and machine learning communities
alike, due to many applications in natural language processing, phylogeny,
cancer genomics and a myriad of problem areas that involve hierarchical
clustering. Despite the existence of several provably exact algorithms for
tree-metric fitting of data that inherently obeys tree-metric constraints, much
less is known about how to best fit tree-metrics for data whose structure
moderately (or substantially) differs from a tree. For such noisy data, most
available algorithms perform poorly and often produce negative edge weights in
representative trees. Furthermore, it is currently not known how to choose the
most suitable approximation objective for noisy fitting. Our contributions are
as follows. First, we propose a new approach to tree-metric denoising
(HyperAid) in hyperbolic spaces which transforms the original data into data
that is ``more'' tree-like, when evaluated in terms of Gromov's $\delta$
hyperbolicity. Second, we perform an ablation study involving two choices for
the approximation objective, $\ell_p$ norms and the Dasgupta loss. Third, we
integrate HyperAid with schemes for enforcing nonnegative edge-weights. As a
result, the HyperAid platform outperforms all other existing methods in the
literature, including Neighbor Joining (NJ), TreeRep and T-REX, both on
synthetic and real-world data. Synthetic data is represented by edge-augmented
trees and shortest-distance metrics while the real-world datasets include Zoo,
Iris, Glass, Segmentation and SpamBase; on these datasets, the average
improvement with respect to NJ is $125.94\%$.