Foundations of Comparison-Based Hierarchical Clustering
  We address the classical problem of hierarchical clustering, but in a
framework where one does not have access to a representation of the objects or
their pairwise similarities. Instead, we assume that only a set of comparisons
between objects is available, that is, statements of the form "objects $i$ and
$j$ are more similar than objects $k$ and $l$." Such a scenario is commonly
encountered in crowdsourcing applications. The focus of this work is to develop
comparison-based hierarchical clustering algorithms that do not rely on the
principles of ordinal embedding. We show that single and complete linkage are
inherently comparison-based and we develop variants of average linkage. We
provide statistical guarantees for the different methods under a planted
hierarchical partition model. We also empirically demonstrate the performance
of the proposed approaches on several datasets.
