Improved Error Bounds for Tree Representations of Metric Spaces
Estimating optimal phylogenetic trees or hierarchical clustering trees from metric data is an important problem in evolutionary biology and data analysis. Intuitively, the goodness-of-fit of a metric space to a tree depends on its inherent treeness, as well as other metric properties such as intrinsic dimension. Existing algorithms for embedding metric spaces into tree metrics provide distortion bounds depending on cardinality. Because cardinality is a simple property of any set, we argue that such bounds do not fully capture the rich structure endowed by the metric. We consider an embedding of a metric space into a tree proposed by Gromov. By proving a stability result, we obtain an improved additive distortion bound depending only on the hyperbolicity and doubling dimension of the metric. We observe that Gromov's method is dual to the well-known single linkage hierarchical clustering (SLHC) method. By means of this duality, we are able to transport our results to the setting of SLHC, where such additive distortion bounds were previously unknown.
that of finding an optimal ultrametric tree, can be solved in polynomial time [11]. An ultrametric tree is a rooted tree where every point is equidistant from the root-for example, ultrametric trees are the outputs of hierarchical clustering (HC) methods that show groupings in data across different resolutions. A known connection between HC and MDS is that the output ultrametric of single linkage hierarchical clustering (SLHC) is a 2-approximation to the optimal ultrametric tree embedding [16], thus providing a partial answer to the NTP. However, it appears that the existing line of work regarding NTP does not address the question of quantifying the ∞ distance between a metric (X, d X ) and its optimal tree metric, or even the optimal ultrametric. More specifically, we can ask: Question 1. Given a set X, a metric d X , and an optimal tree metric t opt X (or an optimal ultrametric u opt X ), can one find a nontrivial upper bound on d X − t opt X ∞ (X×X) (resp. d X − u opt X ∞ (X×X) ) depending on properties of the metric d X ?
The question of distortion bounds is treated from a different perspective in the discrete algorithms literature. In this domain, tree embeddings are typically described with multiplicative distortion bounds (described in §2) depending on the cardinality of the underlying metric space, along with (typically) pathological counterexamples showing that these bounds are tight [4,10]. We remark immediately that (1) multiplicative distortion is distinct from the additive distortion encountered in the NTP, and (2) these embeddings are rarely used in machine learning, where HC and MDS methods are the main workhorses. Moreover, such multiplicative distortion bounds do not take two considerations into account: (1) the ubiquitousness of very large data sets means that a bound dependent on cardinality is not desirable, and (2) "nice" properties such as low intrinsic dimensionality or treeness of real-world datasets are not exploited in cardinality bounds.
We prove novel additive distortion bounds for two methods of tree embeddings: one into general trees, and one into ultrametric trees. These additive distortion bounds take into account (1) whether the data is treelike, and (2) whether the data has low doubling dimension, which is a measure of its intrinsic dimension. Thus we prove an answer to Question 1 above, namely, that the approximation error made by an optimal tree metric (or optimal ultrametric) can be bounded nontrivially.
To see this, observe that any ultrametric is a tree, and that SLHC yields an ultrametric u X that is bounded above by d X .
An overview of our approach. A common measure of treeness is Gromov's δ-hyperbolicity, which is a local condition on 4-point subsets of a metric space. Hyperbolicity has been shown to be a useful statistic for evaluating the quality of trees in [7]. The starting point for our work is a method used by Gromov to embed metric spaces into trees, which we call Gromov's embedding [12]. A known result, which we call Gromov's embedding theorem, is that if every 4-point subset of an n-point metric space is δ-hyperbolic, then the metric space embeds into a tree with ∞ distortion bounded above by 2δ log 2 (2n). The proof proceeds by a linkage argument, i.e. by invoking the definition of hyperbolicity at different scales along chains of points. By virtue of the embedding theorem, one can argue that hyperbolicity is a measure of the "treeness" of a given metric space. It has been shown in [1,2] that various real-world data sets, such as Internet latencies and biological, social, and collaboration networks are inherently treelike, i.e. have low hyperbolicity. Thus, by Gromov's result, these real-world data sets can be embedded into trees with additive distortion controlled by their respective cardinalities. The cardinality bound might of course be undesirable, especially for very large data sets such as the Internet. However, it has been claimed without proof in [1] that Gromov's embedding can yield a 3-approximation to the NTP, independent of [3].
We note that the assumption of a metric input is not apparent in Gromov's embedding theorem. Moreover, the proof of the theorem does not utilize any metric property. This leads one to hope for bounds where the dependence on cardinality is replaced by a dependence on some metric notion. A natural candidate for such a metric notion is the doubling dimension of a space [15], which has already found applications in learning [17] and algorithm design [15]. In this paper, we present novel upper bounds on the additive distortion of a Gromov embedding, depending only on the hyperbolicity and doubling dimension of the metric space.
Our main tool is a stability theorem that we prove using a metric induced by a Voronoi partition. This result is then combined with the results of Gromov's linkage argument. Both the stability theorem and Gromov's theorem rely on the embedding satisfying a particular linkage condition, which can be described as follows: for any embedding f : (X, d X ) → (X, t X ), and any x, x ∈ X, we have
is a chain of points joining x to x and Ψ is some function of d X . A dual notion is to flip the order of the max, min operations. Interestingly, under the correct objective function Ψ, this leads to the well-studied notion of SLHC. By virtue of this duality, the arguments of both the stability theorem and the scaling theorem apply in the SLHC setting. We introduce a new metric space statistic that we call ultrametricity (analogous to hyperbolicity), and are then able to obtain novel lower bounds, depending only on doubling dimension and ultrametricity, for the distortion incurred by a metric space when embedding into an ultrametric tree via SLHC.
We remark that just by virtue of the duality between Gromov's embedding and the SLHC embedding, it is possible to obtain a distortion bound for SLHC depending on cardinality. We were unable to find such a bound in the existing HC literature, so it appears that even the knowledge of this duality, which bridges the domains of HC and MDS methods, is not prevalent in the community.
The paper is organized as follows. The main thrust of our work is explained in §1. In §2 we develop the context of our work by highlighting some of the surrounding literature. We provide all definitions and notation, including the Voronoi partition construction, in §3. In §4 we describe Gromov's embedding and present Gromov's distortion bound in Theorem 3. Our contributions begin with Theorem 4 in §4 and include all the results that follow: namely the stability results in §5, the improved distortion bounds in §6, and the proof of tightness in §7.
The supplementary material contains (1) an appendix with proofs omitted from the body, (2) a practical demonstration in §A where we apply Gromov's embedding to a bitmap image of a tree and show that our upper bounds perform better than the bounds suggested by Gromov's embedding theorem, and (3) Matlab .m files containing demos of Gromov's embedding being applied to various images of trees.
This paper provides new stability results and bounds on the distortion for the tree embedding of a metric space proposed by Gromov. It also exploits a duality between Gromov's embedding and the single linkage hierarchical clustering. As a consequence, stability and bounds are given for SLHC as well. The bounds are illustrated on simulations.
The paper is very interesting and provides good theoretical results. Such an analysis is welcome in the field. However, I think that it could be re-organized to improve its readibility and impact. There are repetitions which may hinder a smooth reading. (see examples below)  In particular, I believe that the proofs could be put in the supplementary materials (although short sketch proofs can stay and give the main idea and steps). The definitions could be restricted only to what is absolutely needed. There are long math developments which may not be integrated enough into the global reasoning: the reader does not necessarily know why he needs to read this.  This deletion/reorganization would give room for: (i) providing intuitive illustrations of metric spaces, trees, voronoi cells, doubling dimension; (ii) giving the intuition behind the theorems 5, 6, 7, 8 (intuition behind inegalities on D in Th.7,8?) and their importance; (iii) developing Section 7 to a page, (iv) providing more structure to the paper (subsections?), (v) write a short conclusion. For now, the intuition is given in "An overview of our approach" in the introduction, but not step by step in the core of the paper.  Examples of repetitions: - Additive distortion is defined twice, in Introduction and Section 2. - The trivial bound is given in Introduction and Section 4. The introduction is maybe too technical? - Gromov's embedding is a 3-approximation to the optimal tree representation in Introduction and Section 7  Examples of unecessary math background: - many details on multiplicative distortion even though not used. Eg: what is the point of the first paragraph of Introduction and last paragraph of Sec. 2? Could they be shortened? - pages 4 and 5 could be embedded in a global reasoning, to keep the reader interested?