Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
Authors: Pierre Houédry
Nicolas Courty
Florestan Martin-Baillon
Laetitia Chapel
Titouan Vayer
Venue: NeurIPS 2025 poster ()
Keywords: tree metric learning
delta-hyperbolicity
geometrical machine learning
differentiation
Primary area: general_machine_learning
TL;DR: A new method to compute a Tree metric from an Arbitrary metric, based on a soft and differentiable version of Gromov Hyperbolicity

Abstract: 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 $\delta$-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 $\delta$-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.

Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
Pierre Houedry Université Bretagne Sud IRISA, UMR 6074, CNRS pierre houedry@irisa.ff fr
Nicolas Courty Université Bretagne Sud IRISA, UMR 6074, CNRS courty@univ-ubs.fi fr
Florestan Martin-Baillon Université de Rennes IRMAR, UMR 6625, CNRS
Laetitia Chapel L'Inttitut Agro Rennes-Angers IRISA, UMR 6074, CNRS lastitia. cha.iiaiiaa@eiii....c.
florestan FLorestan.martin-baat. www.:arrnnnaaaannnniioioeoeaaee ..r fr
Titouan Vayer
INRIA, ENS de Lyon, CNRS, Université Claude Bernard Lyon
LIP, UMR 5668
titouan. vayorinnaayrrriria..rrr
Abstract
Trees and the associated shortest-pale path tree metries provide a powerful framework for representing hierarchical and combinatorial structures in data. Given an arbitrary metric space, its deviation from tree metric can be quantified by Gromov's 's Ó- hyperbolicity. Nonetheless, designing algorithms that bridge an arbitrary metric to its closest tree metric still 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 smooth surrogate for Gromov's 9-hyperbolicity which enables gradient-base optimization, with tractable complexity. The corresponding optimization procedure is derived from problem with better worst case guarantees than existing bounds, and is justified statistically. Experiments synthetic and real-world datasets demonstrate that method consistently achieves state-of- state-of-the-are the-art distortion.
Introduction
The notion of ö-hyperbolic metric spaces, introduced by (1). captures large-scale analog of negative curvature and has found significant applications in both mathematics and computer science. prominent example in machine learning is the success of representation learning in hyperbolic spaces (7), which leverages their natural ability to learn on data with hierarchical structure. A key measure of characterizing how well hyperbolic space fits given dataset is the Gromov hyperbolicity, which quantifies the extent to which metric space (X, dx) deviates from tree metric, with tree structures achieving value zero. As such, has often been used as a proxy for graph dataset suitability to hyperbolic space embedding (e.g. [ 40). which has also been recently analyzed in (33
Metrics that be exactly realized shortest-patt distances in tree play central role in many domains: hierarchical clustering in machine learning (28), phylogenetic tree construction in bioin- formatics [14. and modeling real-world networks 34 to cite few. When data is not exactly
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

treesstructured, a natural problem arises: how to approximate an arbitrary metric as faithfully as possible with a tree metric?
Formally, a metric dx on a finite set X is called a free metric if there exists a tree metric (T, dr) and an embedding $ X + T such that
dx(x,y) dr (0(x), p(y) for all 2, E X.
(1.1)
That is, pairwise distances in X can be exactly represented as shortest-pate pratesstppahhhee distances in a tree. When such a representation is not possible, one seeks a tree metric that approximates dx as closely as possible under some distortion measure.
This gives rise to the following problem:
Problem 1.1 (Minimum Distortion Tree Metric Approximation). Given a finite metric space (X, dx). goal is to construct an embedding & X T into metric tree dT, such that the tree metric dr closely approximates the original metric dx. We aim to solve
argmin ||dx - dr = argmin max [dx(x, v) - dr(6(x), (T,dr)ET
(T,dr)ET 2.EX
where T denotes the set of finite tree metrics.
Tree metries embedding methods. In response, several methods have been developed to embed data into tree-like metrics with minimal distortion, e.g. [9] 36 33). Among them, the Neighbor Joining algorithm (NJ) [36] has long been a standard algorithm for constructing tree metrics from distance data, which proceeds by iteratively joining neighboring nodes. An alternative, the TREEREP algorithm (39, offers improved scalability. Despite their algorithmic efficiency and empirical success, both methods lack theoretical guarantees regarding the distortion incurred during the embedding process. This limitation affects their reliability in applications where preserving metric fidelity is critical. In contrast, based on theoretical characterization of the distortion, the GROMOV algorithm (21), described in more details later in the paper, constructs a tree metric by iteratively selecting pairs of points. It serves as a key component of our approach. Restricted to unweighted graph, the LAYERING method [ first chooses a root node, then join iteratively neighbors with TREEFIT algorithm [45] starts by centering the distance matrix around chosen root, then fits an ultrametric distance to the centered distance, minimizing an average ε -idiistoriion. However, its accuracy is generally lower than that of the methods presented above and remains sensitive to the choice of root. Those various approaches illustrated in Figure 1 along with our new method described subsequently. Additional illustrations on toy graphs are also provided in Appendix A with details on how the figure is generated. Related works in hyperbolic embeddings (e.g.. g.. 30 37 also aim to capture hierarchical structure, albeit from a different modeling perspective, generally based on contrastive losses that preserve relationships. In contrast, we operate directly on pairwise distances and focus learning surrogate metric that can be explicitly embedded into a tree with worst-case distortion guarantees. This metric-centri view differs from position/relation based hyperbolic embeddings, but we see them as highly complementary.
bounded additive distortion. The more recent HCCROOTED' EECCROOTEDRREFFT
Contributions. In this paper, we propose DELTAZERO, distortion tree metric approximation problem. It formulates the problem as a constrained optimization task, where the objective is to minimize the distortion between the input metric and surrogate metric space (X', ), while enforcing that the resulting space is close to a true tree metric, as quantified by low Gromov hyperbolicity. This surrogate is eventually embedded into an actual tree (T, d. One additional key feature of DELTAAERO is its differentiable formulation: it leverages smooth approximations both the Gromov hyperbolicity and the distortion to enable gradient- based optimization. Computing the exact Gromov hyperbolicity for a dataset of even moderate size is computationally demanding, both in terms of time and memory consumption. The best known theoretical algorithm operates in 3 time [17), which is impractical for large graphs. Although faster empirical approximations have been proposed, such as [10], scalability remains a bottleneck. To address this, we propose an alternative strategy based on batch-wise sampling. Rather than analyzing the entire dataset at once, DELTAZERO estimates hyperbolicity and distortion on subsets of the distance matrix, which significantly reduces computational overhead while preserving accuracy. We demonstrate that this mini-batching approach enables scalable Gromov hyperbolicity approximation without sacrificing fidelity to the exact value.
method for solving the minimum
2

---

Original Graph
LayeringTres Tree
TreeRep
Gromov
HCC
Neighbor Joining
DeltaZera (ours)
Distanzes
Distortion: 2.00
Distortion: 3.00
Distortion: 1.00
Distortion:
1.00
Distortion: 0.47
Distortion: 0.42
Figure 1: Illustration of the tree metric embedding problem (best viewed with colors). Given an original graph (first column) and the corresponding shortest path distances between nodes (represented on the bottom row as a lower-triangular matrix), we aim finding a tree and the corresponding tree metric that best approximates the original distances. Competing state-of-the-e methods and our method DELTAZERO results are presented along with the corresponding distortion.
The rest of the paper is organized follows. Section introduces the notion of 8- and Gromov hyperbolicity and gives intuition on its geometric interpretation. In Section 3 we formulate our optimization problem and show how improves the worst-case distortion of Gromov. We then provide a differentiable and efficient algorithm to solve the problem. In the experimental Section 4 we first evaluate DELTAZERO clusters. We then measure its ability to generate low distortion tree metric approximations in two contexts, where unweighted and weighted graphs are at stake. Finally, we draw some conclusions and perspectives.
controlled setting assess its ability provide hicrarchical
2 Background on š-hyperbolicity
At the heart of our approach lies the concept of o-hyperbolicity. In this section, we present the foundational principles of this notion and offer intuitive insights into its geometric interpretation. We also discuss relevant computational aspects.
2.1 From Gromov product to 6-hyperbolicity
key concept used to define d-hyperbolicity is the Gromov product, denoted (xly) which intuitively measures the overlap between geodesic paths from base point w the points and y. It is defined as follows.
Definition 2.1 (Gromov Product). Let (X, dx) be metric space and let x, y, X. The Gromov product x and with respect to the basepoint w is defined as
1 (aly) m (dx(x, + dx w) dx(x,))).
With the Gromov product hand, we now define 9-hyperbolicity.
Definition 2.2 (6- (6-hyperbolicity and Gromov hyperbolicity). A metric space (X, dx) is said to be 5 S-hyperbolic if there exists 2 such that for all x, , 2, w E X, the Gromov product satisfies
(z|z) 2 min (<rly) (vl=)w) 6.
The Gromov hyperbolicity, denoted by 8x, is the smallest value of that satisfies the above property. Consequently, every finite metric space (X, dx) has Gromov hyperbolicity equal to
8x max K.E.E.EEX..
(min (<)y)) (yl=) ())
(2.1)
The concept of of d-hyperbolicity may initially appear abstract, but it has deep and elegant connections to tree metrics. fact, metric dx is a tree metric if and only if, for every four points x, y, 2, w E X, two largest among the following three sums
dx(x,y) + dx(2,w), w), dx(x, 2) + dx(u, w), dx(a, w) + dx (x,
are equal [
3

---

The d-hyperbolicity generalizes this condition by allowing a bounded deviation. Specifically, a metric space (X, dx) is d-hyperbolic for all z, y. 2, w X. the following inequality holds
dx (x, y) +x (2, w) & max {dx (z, 2) dx (v. w) (x, w) + dx (v. +2)
This is known as the four-point condition. It offers an alternative characteriza- tion of d-hyperbolicity (see [19 Ch. 2,) providing a quantitative measure of how far given metric deviates from being tree metric, and thereby cap- turing an intrinsic notion of negative curvature in the space. An alternative and more geometrically intuitive way to understand 9-hyperbolicity is through the concept of ő-slim geodesic triangles. In this perspective, a geodesic metric X is
Figure 2: d-slim tri- angle.
space (X, dx) d-hyperbolic if and only if every geodesic triangle 5-slim (up to multiplicative constant on 6, see [19 Ch.2, $3, Proposition 21]), meaning that each side of the triangle contained within the 5-neighbourhood of the union of the two other sides (see Figure
This captures the idea that geodesic triangles in hyperbolic spaces are "thin", more closely resembling tripods than the broad, wide-angled triangles characteristic of Euclidean geometry. In this sense, Gromov hyperbolicity quantifies the extent which the space deviates from tree-like behaviour: the smaller the value of 6, the more the geodesic triangles resemble those in a tree, where all three sides reduce to a union of two overlapping segments. Thus, the d-slim triangle condition offers a compelling geometric counterpart to the more algebraic formulations via the Gromov product or the four-point condition.
Computing the Gromov hyperbolicity. Computing the Gromov hyperbolicity of a discrete metric space is computationally demanding, as it requires examining all quadruples of points to evaluate the four-point condition. The naive brute-force approach runs in On**) time for space with n points, making it impractical for large-scale applications. Then, several works have addressed the computational bottlenecks inherent in computing Gromov hyperbolicity. Notably, Fournier al. [I7 show that the computation of hyperbolicity from fixed base-poine can be reduced to a (max, min) matrix product. Leveraging the fast algorithm for this class of matrix products, leads an overall (n.3.69 time complexity.
In graph settings, the notion of sar-apart vertex pairs plays key role in accelerating hyperbolicity computation. This concept underpins a structural result [10] stating that certain far-apart pairs suffice to witness the maximum in the definition of Gromov hyperbolicity. Consequently, one can avoid exhaustive examination of all quadruples and focus on a carefully selected subset; this leads to pruning approach that significantly reduces computational cost
Contrary to these approaches, which aim to accelerate the exact computation of Gromov hyperbolicity, take different route: introduce smooth, differentiable surrogate of the hyperbolicity function. This relaxation enables gradient-based optimization, and we further propose a batched approximation scheme make the computation tractable and independent of the size of the graph.
2.2 Embedding of a 5-hyperbolic space into a tree
The ō-hyperbolicity can play significant theoretical role in establishing guarantees for embedding arbitrary metric spaces into trees. Indeed, a result by Gromov [21] shows that any ò-hyperbolic metric space on points admits tree-metric approximation with additive distortion O(ā log n), and that this embedding can be computed in (n time.
Theorem 2.3 (199 Ch.2, $2, Theorem 12]). Let (X, dx) be a finite 5-hyperbolic metric space over n. points. For every w X. there exists a finite metric tree (T, dr), and a map & X T such that
1. The distance to the basepoint is preserved: dr(((x), (ww)) dx(x, w) for all x E X,
2. dx (z, 25 (o - 2) S dd ( (())) S dx (x, v) for aol x,y X.
The approximation of distances provided in the previous theorem is particularly notable due to the non-expansiveness the mapping, meaning that the embedded distances in the tree never exceed the original graph distances. This ensures that the distortion introduced is purely additive and one-sided,

---

which is a stronger guarantee than general metric embeddings. In 45 Yim et al. provide an argument illustrate the asymptotic sharpness of the result, using construction in the Poincaré disk.
For a practical and efficient computational procedure to obtain Gromov's tree embedding of a discrete metric space, one can leverage the Single Linkage Hierarchical Clustering (SLHC) algorithm [3I. The SLHC algorithm incrementally merges clusters based on minimal pairwise distances, implicitly constructing an ultrametric tree. While originally developed for clustering tasks, this procedure can be naturally adapted to construct the Gromov's 's embedding. Further details are provided in Appendix B
While this result is notable, it provides worst-case, coarse approximation that does not seek to minimize the actual distortion for a specific input metric. In contrast, our work focuses on directly learning a like metrie that is optimally close to the original space, potentially achieving significantly lower distortion in practice, as shown in the experiments, see Section
3 DELTAZERO
We present below our approach to the Minimum Distortion Tree Metric Approximation problem. In this work, we consider discrete metric spaces and we denote by M, the set of finite metric spaces over points, and fix (X, dx) ) E M,.. Our algorithm is inspired by Theorem 2.3 which states that (X, dx) can be isometrically embedded into a tree and only if its Gromov hyperbolicity is O. Building on this result, we introduce the following optimization problem, parametrized by μ > 0,
min (X' dx Sxx
Lx (x((X', dx)), = plldx - dx + 5xx-
(3.1)
By minimizing Cx, we seek a discrete metric space that is both close to (X, dx) and exhibits low hyperbolicity. This objective balances two competing goals: proximity to the original metric (via the fo distortion term) and tree-likeness (quantified by 8x The parameter μ governs the trade-off between these terms. The constraint dxx S dx accounts for the con-expansiveness of the metric, as in Theorem 2.3 for the Gromov embedding. Importantly, the minimization of Lx leads to improved worst-case guarantees when followed by the Gromov tree embedding procedure, as described below.
Theorem 3.1. Let (X",dx ) be any metric space minimizing Lx((X', dxx) ), μ),, and let (T" dr-) ) be a tree metric obtained by applying a Gromov tree embedding denoted by to (Xx,xx)), Then
dx (x. y) Cx I dr- (I(z), (y)) S dx y) for all x. E X.
with Cx,, 26x 1ogg 2n 2 log2(n - 2)μ² I|dx-dx-lle booo In particular, if 2 (nog the distortion of the finul free embedding smaller than the worst-case bound achieved by applying the Gromov embedding directly to X.
The proof of all theorems are given in App. C Theorem 3.1 suggests that improved lor distortions can be achieved by minimizing Lx. Our solution, which we describe below, adopts this principle.
3.1 Smooth Relaxation and Batched Gromov Hyperbolicity
We propose differentiable loss function that allows to optimize the metric so that it closely aligns with the original metric while maintaining a small Gromov hyperbolicity. The primary challenge lies in the dinddfferrentibbliity of ōx, as it involves max and min operators, rendering it unsuitable for gradient-based optimization. To address this, we introduce a smoothing of Gromov hyperbolicity based on the log-sum-exp function defined as LSEx (x)
1 log (E; AA.) for vector and > 0. As done in many contexts, LSF can be used as a differentiable surrogate for max and min recovering both À - co. We define a smooth version of the 6-hyperbolicity as
12
18 25
((2) = LSEA (LLSE>(((I))) (vlz)w) - (x.
1
(3.2)
log
A(rly) -(yls)))
(x.
The rationale behind this formulation is to replace the min in 2.1 with soft-minimum LSE- and the max with a soft-maximum LSEş, which boils down to computing the last quantity. Interestingly, we have the following bounds between the Gromov hyperbolicity and its smoothed counterpart (2)
5

---

Proposition 3.2. Let dx) be finite metric space over n. points, for X > 0 we have
1og(2)
4log(n)
6x
S (A) 8x
While the smoothed version x alleviates the non on-diffierentiabiiity of the classical Gromov hyperbol- icity, it still requires evaluating all quadruples of nodes in X, resulting in a computational complexity of O(n²). This remains prohibitive for large number of points. To address this, we introduce a batched approximation of the Gromov hyperbolicity. We sample K independent subsets (without replacement within a subset and no constraint across subsets) X x,...., X C X, each containing m X within each batch. Since dx is defined as the maximum over all quadruples in X, and each 6x2 approximates the maximum over quadruples in smaller subset X C X. aggregate these local estimates using another log-sum-exp obtain a differentiable approximation of the global maximum
points, and compute the local smooth hyperbolicity ((A)
(50)) X1
X.K.m LSEA
(3.3)
This two-level smoothing approach allows to preserve differentiability while reducing the com- putational complexity from O(n)) to O(K m²), making the estimation of Gromov hyperbolicity tractable.
important note that this sampling strategy does not, in general, guarantee closeness to the true Gromov hyperbolicity. For example, one may construct metric space composed of a large tree with four additional points connected far from the main structure, although these few points may determine the global hyperbolicity, they are unlikely appear in small random subsets. Thus, rare yet impactful configurations may be missed, leading to underestimation. Nonetheless, we find that in practice, the batched approximation performs well across a variety of graph instances (see Appendix D.3). In particular, we can show that for some random graph models, our estimator closely tracks the true Gromov hyperbolicity, formalized below.
We say that random metric space (X, dx) E Mn is uniform if the random distances dx (x 23)) are i.i.d. with some law f, called the law of distances (see precise Definition C.2
Theorem 3.3. Let l be probability measure on R+. Let (X, dx) be uniform metric space with with law of distances given by E. the regime K log(m) ~ log(n) and X e log(n) we have
6xx -
(A) K.K.m
Se 2
22 n3
This result establishes that, the asymptotic regime where n oc, our batch estimate closely aligns with the true Gromov hyperbolicity, provided that the number of batches times the logarithm of their size, as well as the smoothing parameter, depend logarithmically on n. The assumptions about metric spaces imply independent distances, which can be restrictive. As shown in Appendix C.3 random graph model satisfying these assumptions is one where shortest-path distances are randomly drawn from distribution over (r....,2r or within a certain regime of Erdös graphs. In practice, however, some of our datasets exhibit log-normal distance distributions (see Appendix C.3 suggesting that these assumptions are not overly restrictive. Future work will aim to extend these results to encompass a broader class of random metrics.
3.2 Final Optimization Objective
To formalize our algorithm, we start by noting that the set of discrete metries over n points can be identified with the following subset of nR
D, : [D (Dig) RTX* D D S. Dik Dzj, Da Vi,j, (1........) [L.....,,]].
Each E Dr encodes the pairwise distances of a metric space over n points, in particular, any metric dx on set X {zI...., } } of size n is fully described by its matrix representation Dx = (dx(,,,,))) E D,,- Note that D. forms a closed, convex, polyhedral cone generated by the half-spaces imposed by the triangle inequalities.

---

Algorithm DELTAZERO
Require: A finite metric space (X, dx), designated root w E X. learning rate > 0, number of
batches K, batch size m, log-sum-exp scale 0, regularization parameter y > 0, number of
steps T
Initialize Do = Dx
2: for t = 0 to T 1 do
3: Randomly pick K batches of points and compute KD.,K.m Kmm
4: Compute gradient: G. VLx
5: Optimization step: D++1 ADAM (TE Gr,c)
6: Projection step: D FLOYD- (DR4)
7: end for
8: return GROMOv(D,,.) w)
In practice, find a tree-like approximation of (X, dx), we search for matrix D Dn that is close to Dx while exhibiting low Gromov hyperbolicityy. Since Gromov hyperbolicity depends only on the metric, we write dD to emphasize this dependence. Our final optimization objective is
min DED
Lx(D) = ID DI2 (A) D.K.m
(3.4)
where A < B means Y(i,j), A.y S B.y. The first term preserves fidelity to the input metric, acting as smooth counterpart the lo norm. Our choice of the squared & norm stems from its smoothness and differentiabilityy which make it well-suited to gradient-based optimization. Moreover, among the common lp norms, l provides natural balance: it is closer &oo than E as captured by the classical inequality in finiteddimensional spaces,
| S |x S |x|oo for all x E R"
(3.5)
The second term promotes low-stretch, hierarchical structure using our smooth log-sum-exp ap- proximation of Gromov hyperbolicity. The constraint D E D, account for the metric requirement. Note that we do not require anymore the con-exxansivveess of the metric. While the objective (3.4) includes convex fidelity term, the hyperbolicity penalty introduces non-convexity. This comes from the structure of the Gromov hyperbolicity functional.
Proposition 3.4. The Gromov hyperbolicity êp seen as a functional over Dn is piecewise affine but nof convex.
Thus, we expect our smooth surrogate Km to also inherits this non-convexity, making the overall objective in (3.4) non-convex.
To tackle this optimization problem, draw inspiration from Projected Gradient Descent (PGD). Specifically, we alternate between taking plain gradient step Lx using ADAM (24] (only over
the upper- trianglr entries of D. due to symmetry and zero diagonal), and projecting the result back onto D,,. Each projection step solves
DD (D) = argmin
D
D' DDE,
This projection corresponds to metric nearness problem, which we tackle using the FLOYD- WARSHALLL algorithm [16]. This algorithm computes all-pairs shortest paths in a graph with edge weights given by D, and as shown in 3 Lemma 4.1], this is equivalent to finding the closest valid metric matrix no greater than in each entry (see Section C.5 for detailed discussion). The projection runs in O(n²) time and can be interpreted iteratively "repairing" triangle inequality violations to reach the nearest point in the metric cone with entrywise smaller values.
At the end of the PGD iterations, we obtain refined metric D To complete the tree approximation, we apply the Gromov tree embedding to D*, producing tree metric. The full procedure, which we refer to as DELTAZERO, is summarized in Algorithm
Computational complexity. Each gradient step incurs a computational cost of O + n²), where the O term arises from the use of the BLOYD-WARSHANE algorithm. Consequently, the
7

---

Original Distance
Optimized Distance
Original Distance
Optimized Distance
(b) Dendrograms from original and opti-(c) t-SNE plots from original and opti- (a) All pairs Shortest- Shortest-Paths mized distance matrices distance matrix
mized distance matrices
Figure 3: Illustration of the impact of optimizing the distance matrix on simple Stochastic Block
Model with 5 communities (best viewed in colors).
overall complexity of the optimization procedure over T iterations is O + n²)). In practice, the computation is typically dominated by the KLOYD-WARSHALL component, as we operate under the condition Km < 12.. We emphasize that the optimization is carried out in the space of distance matrices, so that the cubic cost of the projection is not disproportionate relative the size of the object being optimized (with n² entries). Several methods have been proposed for metric nearness (e.g., 26 20),, often relying on iterative schemes. Although these approaches may enjoy lower theoretical complexity, they tend to be slower in practice. This is because FLOYD- BOOYD-WARSH WARSWAALHHLL despite its O(n²) complexity, admits efficient GPU parallelization, leading to substantial speed-ups compared to iterative alternatives.
Experiments
We provide in this Section experiments conducted on synthetic dataset to assess the quality of the optimization method, and on real datasets to measure the distortion obtained by DELTAZERO.
Synthetic Stochastic Block Models dataset. We consider the setting of Hierarchical Clustering (HC) which iteratively merges clusters based on pairwise dissimilarities. The resulting tree-like structure known as a dendrogram and encodes a hierarchy of nested groupings. Our first objective qualitatively and guantitatively analyse the impact of the optimization problem of Eq. (3.4) on HC within the context of simple stochastic block model (SBM) graph with varying number of communities.
In such a probabilistic model of graph structure, we set the intra- and inter-communities connection probabili- ties to Pin. 0.6 and Pout 0.2. Sizes of communities fixed 50. This yields shortest path distance ma- trix depicted in Figure a SBM with 5 communities. We then follow the distance optimization procedure de- scribed in Section 3 to obtain a new distance matrix (parameters are μ and À 100). This yields two different dendrograms, shown in Figure 3b) both com- puted using Ward's 's method [4 as implemented by the linkage function of Scipy 43 The color threshold is manually adjusted to magnify 5 clusters. At this point, we can see that the dendrogram corresponding to the optimized distance exhibit better, more balanced, hi- erarchical structure with a clear separation between the clusters. This point also illustrated Figure [c] where t-SNE [41] is computed from the distance ma- trices with similar perplexity (set to 30). One can observe stronger clustering effect from the optimized distance.
Accuracy of Hierarchical Clustering
8
Acourecy
Original Distance Opámized Distance
Communilies
Figure 4: Performances of Hierarchical clus- tering with varying number of communities

---

We then compute accuracy scores by comparing the true labels with the optimal permutation of predicted labels, using the fcluster function of Scipy. This evaluation is conducted under varying number of communities (3, 5 and 7), introducing increasing levels of difficulty. For each setting, 30 repetitions are performed. The results are summarized as boxplots in Figure [ As one can observe, our optimization strategy increases drastically the performances in terms of accuracy on this simple example. It suggests that our optimization produces a metric which effectively homogenizes intra- and inter- cluster distances.
Distortions on real datasets. We evaluate the ability of our method, DELTAZERO, to embed finite metric spaces into tree metrics with low distortion. Our benchmark includes both unweighted graph datasets and general metric datasets to showcase the versatility of our approach. We consider five standard unweighted graphs: C-ELEGAN, CS PHD from [35. CORA, AIRPORT from [38] and WIKI [15]. For graphs with multiple connected components, extract the largest connected component. We then compute the shortest-pati distance matrix, which serves as input to all tree metric fitting algorithms.
To evaluate DELTAZERO beyond graph-induced metrics, we also include two datasets: ZEISEL [46 and IBD [32.. These datasets are not naturally represented as graphs but instead as high-dimensional feature matrices. We construct a pairwise dissimilarity matrix using cosine distance, a standard choice in bioinformatics. Despite its name, cosine distance is not a true metric, as it fails to satisfy the triangle inequality, but it still provides a meaningful basis from which to search for the closest tree metric. Note that LAYERINGTREE (9) which requires unweighted graph as input, is not applicable in this setting. We compare DELTAZERO against the following tree fitting methods: TREEKEP (TR) [39]] NEiGHBORJOIN (NJ) 36 HCCROOTEDTREEFII (HCC) [45) LAYERINGTREE (LT) ( and the classical GROMOV (see Algorithm
2) Among these, HCC, LT, and GROMOV are pivot- based methods: for given distance matrix, they require selecting a root node. We report the average and standard deviation of distortion over 100 runs using the same randomly sampled roots across methods. TREEREP does not require a root but incorporates stochastic elements; we therefore report mean and standard deviation over 100 independent runs For C-ELEGAN, CS PHD, CORA, and A AIRPORT, we report the values of (5). In contrast, NEIGHBORJOIN deterministic that neither requires a root nor involves stochasticity, and is thus evaluated once per dataset.
For DELTAZERO, we perform grid search over the following hyperparameters: learning rate 0.01, 0,0,,.00,00000 0.001), distance regularization coefficient μ E {0.1, 0.01,.107 and ô-scaling parameter E (0.01, 1.0, 10.0). We fix the number of training epochs to T 1000, batch size m 32, and vary the number of batches K E {100, 500, 1000, 3000, 50003. For each setting, we select the best configuration which leads the minimal distortion. Note that Theorem 3.1 offers theoretical guidance on worst-case distortion guarantees, suggesting 2 1/ //logg (n 2). In practice, however, we treat f tunable hyperparameter, reflecting the fact that we optimize smooth surrogates rather than enforce exact hard constraints.
To ensure stability, we apply carly stopping with a patience of 50 epochs and retain the model with the best training loss. In practice, our method converges in a reasonable number of iterations; detailed early stopping statisties reported in Appendix D.I
Final results are reported in Table In addition to worst-case distortion defined in equation we evaluate the average embedding quality using the & distance between the original and tree-fitted distance matrices. We also report the execution time of each method to assess their computational efficiency. Results are presented in Appendix [.2] Note that, as highlighted by equation (3.5). in mnite-dimensional spaces, minimizing the &/ norm offers no direct control over the lo norm, which can lead, during optimization, to lower average distortion but potentially higher worst-case distortion. We also provide an analysis of its robustness and stability with respect to hyperparameter in Appendix D.3
All implementations details are given in Appendix E
Table demonstrates that DELTAZERO consistently achieves the lowest lor distortion across all datasets, both for unweighted graphs and general metric spaces. Notably, the largest relative improve- ments are observed on C-ELEGAN and ZEISEL, with reductions in distortion of 13.8% and 44. 1 % respectively, compared to the second-best methods. On CORA A the improvement is more modest (2.3%), yet DELTAZERO still outperforms all baselines. This suggests that while our approach is robust across datasets, gains vary depending on the geometry of the input metric space. Overall, the
9

---

Table foc error (lower better). Best result in bold. The last row reports the relative improvement (%) of DELTAZERO over the second-best method (underlined) for each dataset.
Unweighted graphs
Non-graph metrics
Datasets
C-ELEGAN
CS PHD
CORA
AIRPORT
WIKI
ZEISEL
IBD
452
1025
2485
3158
2357
3005
396
Diameter
7
28
19
12
9
0.87
0.99
6x
1.5
2.5
0.19
0.41
2.97
16.81
13.42
4.18
6.32
0.90
5.90 + 0.72
21.01
= 3.34
16.86
= 2.11
10.00
1.02
9.97 + 0:33
0.66 0.10
1.60
HCC
4.31
23.35
12.28
7.71
7.20
0.53
1,25
TreeringTree
5.07 + 0.25
25.48
0.60
7.76
+ 0.54
2.97 + 0.26
4.08
+ 0:27
Gromov
3.33
+ 0.45
13.28
+ 0.61
9.34
+ 0.59
4.08
+ 0.27
5.54
+ 0.49
0.43 + 0.02
1.01 + 0.44
DELTAZERO
1.87 1: 0.08
10.31
0.62
7.59
1: 0.38
2.79
11 0.15
3.56
1: 0.20
0.24 1: 0.00
0.70 1: 0.00
Improvement (%)
43.8%
22.3%
2.3%
6.0%
12.7%
44.1 %6
22.2%
results validate the effectiveness of our optimization- based method in producing low-distortion tree metric embeddings.
Conclusion and Discussion
While our primary focus has been on distance approximation, believe our method has strong potential for standard graph-representation tasks. By producing a surrogate distance metric that captures global and hierarchical structure differentiable, geometry-aware manner, our framework provides rich structural signal that can be exploited across multiple settings. For example, one could embed our optimized metric into hyperbolic spaces to obtain high- high-quality node embeddings, or feed it directly to downstream neural models.
In node classification, the tree-like structures induced by method may uncover latent hierarchies or community structure, an intuition validated by our experiments on stochastic block models, where DELTAZERO helps accurately recovering the underlying partitions. Beyond synthetic settings, this makes our approach especially well-suited for real-world discovery tasks such as biological taxonomies, document hierarchies, social networks. Extending our method such domains would be natural continuation of the present work.
Our framework can also be integrated pre- preeppocessing step regularizer in graph neural networks, where it provides additional structural bias. This particularly relevant for addressing the over- squashing phenomenon: Gromov hyperbolicity is tied negative sectional curvature, while over- squashing has been linked to negative Ollivier-Ricci curvature [29]. By bridging these notions of curvature, method could offer a principled avenue to investigate, and potentially mitigate such effects, opening the door to curvature-aware re-wiring procedures and architectural design.
Acknowledgements
This project supported by the ANR project OTTOPIA ANR-20-CHIA-0030. The authors declare no competing financial interests.
References
[1] Muad Abu-Ata and Feodor Dragan. Metric tree-like structures in real-world networks: An empirical study. 67(1):49-68, 2016.
[2] Béla Bollobás. Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2001.
[3] Justin Brickell, Inderjit S. Dhillon, Suvrit Sra, and Joel A. Tropp. The metric nearness problem. 30(1):375-33) 1975,,99,,.1 January 2008.
[4] Justin Brickell, Inderjit S. Dhillon, Suvrit Sra, and Joel Tropp. The metric nearness problem. 30(1):375-396, April 2008
10

---

[5] Martin R. Bridson and André Haefliger. Metric Spaces of Non-Positive Curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften. Springer, 1999.
[6] Peter Buneman. The recovery of trees from measures dissimilarity. In Mathematics in the Archueological and Historical Sciences, pages 387-395. Edinburgh University Press, 1971.
[7] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. 32, 2019.
(8] Weize Chen, Xu Han, Yankai Lin, Hexu Zhao, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou, Fully hyperbolic neural networks. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pages 5672-5686, 2022.
[9] Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, Yann Vaxès, and Yang Xiang. Additive spanners and distance and routing labeling schemes for hyperbolic graphs. 62 (3-4):713-732, April 2012.
[10] Nathann Cohen, David Coudert, and Aurélien Lancin. On computing the gromov hyperbolicity.
20, August 2015.
[11] David Coudert, André Nusser, and Laurent Viennot. Enumeration far-apart pairs by decreas- ing distance for faster hyperbolicity computation. 27, December 2022.
[12] Marco Cuturi and Mathieu Blondel. Soft-dtw: A differentiable loss function for time-series. In Proceedings of the 34th International Conference on Machine Learning, pages 894-903. PMLR, 2017.
[13] William Dudarov, Noah Feinberg, Raymond Guo, Ansel Goh, Andrea Ottolini, Alicia Stepin, Raghavenda Tripathi, and Joia Zhang. On the image of graph distance matrices, 2023.
[14] Joseph Felsenstein. Inferring phylogenies. In Inferring Phylogenies, pages
2004.
[15] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. 2019.
[16] Robert W. Floyd. Algorithm 97: Shortest path. 5(6):345, June 1962.
[17] Hervé Fournier, Anas Ismail, and Antoine Vigneron. Computing the gromov hyperbolicity of a discrete metric space. 175-6):576-57, 2015.
[18] Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. 2017.
[19] Etienne Ghys, Pierre De La Harpe. J. Oesterlé, and A. Weinstein. Sur Les Groupes Hyper- boliques d' d'apéés Mikhael Gromov, volume 83 of Progress in Mathematics. Birkhäuser Boston, 1990.
[20] Anna C. Gilbert and Lalit Jain. it ain't broke, don't fix it: Sparse metric repair. In Proceedings of the 55th Annual Allerton Conference on Communication, Control, and Computing, pages 612-619. IEEE, 2017.
[21] M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in Group Theory, pages 75-263. Springer New York, 1987.
[22] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 1-15,, 2008
[23] Isay Katsman and Anna Gilbert. Shedding light on problems with hyperbolic graph learning. 2025.
[24] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. 2014.
[25] Alan A Lahoud, Erik Schaffernicht, and Johannes Stork. Datasp: differential all-to-all
shortest path algorithm for learning costs and predicting paths with context. 2024.
11

---

[26] Wenye Li, Fangchen Yu, and Zichen Ma. Metric nearness made practical. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 37, pages 8648- 8656, 2023.
[27] Dhruv Mubayi and Caroline Terry. Discrete metric spaces: Structure, enumeration, and 0-1 laws. 84(4):1293-133) 2019.
[28] Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: An overview. 2(1):
86-97, 2012.
[29] Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors. Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 25956-25979. PMLR, 23-29 Jul 2023.
[30] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. In Advances in Neural Information Processing Systems, volume 30, 2017.
[31] Frank Nielsen and Frank Nielsen. Hierarchical clustering. pages 195-211, 2016.
[32] H. Bjørn Nielsen, Mathieu Almeida, Agnieszka S. Juncker, Simon Rasmussen, Junhua Li, Shinichi Sunagawa, Damian R. Plichta, Laurent Gautier, Anders G. Pedersen, Emmanuelle Le Chatelier, Eric Pelletier, Ida Bonde, Trine Nielsen, Chaysavanh Manichanh, Manimozhiyan Arumugam, Jean-Michel Batto, Maria Beatriz Quintanilha Dos Santos, Nikolaj Blom, Natalia Borruel, Kristoffer S. Burgdorf, Foudil Boumezbeur, Francese Casellas, Joël Doré, Piotr Dworzynski, Francisco Guarner, Torben Hansen, Falk Hildebrand, Rolf S. Kaas, Sean Kennedy, Karsten Kristiansen, Jens R. Kultima, Pierre Léonard, Florence Levenez, Ole Lund, Brahim Moumen, Denis Le Paslier, Nicolas Pons, Oluf Pedersen, Edi Prifti, Junjie Qin. Jeroen Raes, Søren Sørensen, Julien Tap, Sebastian Tims, David W. Ussery, Takuji Yamada, Pierre Renault, Thomas Sicheritz- Pontén, Peer Bork, Jun Wang. Søren Brunak, Stanislas D. Ehrlich, and MetaHIT Consortium. Identification and assembly of genomes and genetic elements in complex metagenomic samples without using reference genomes. 32(8):822-82) August 2014. Epub 2014 Jul
[33] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach De Vito, Martin Raison, Alykhan Tejani. Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019.
[34] Erzsebet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks. 6222)102611,, 2003.
[35] Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. 29(1), March 2015.
[36] N Saitou and M. Nei. The neighbor-joining method: A new method for reconstructing phyloge- netic trees. 4(4):406-425, 425, 07 1987.
[37] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoffs for hyperbolic embeddings. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4460 4469. PMLR, 10-15 Jul 2018.
[38] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification in network data. 29(3):93-106 106.
[39] Rishi Sonthalia and Anna Gilbert. Tree! am no tree! am a low dimensional hyperbolic embedding. In Advances in Neural Information Processing Systems, volume 33, pages 845-856. Curran Associates, Inc., 2020.
[40] Alexandru Tifrea, Gary Becigneul, and Octavian-Fugen Ganea. Poincaré glove: Hyperbolic word embeddings. In International Conference Learning Representations, 2018.
12

---

[41] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. 9(11), 2008.
[42] Max van Spengler and Pascal Mettes. Low-distortion and gpu-compatible tree embeddings in hyperbolic space, Proceedings of the 42nd International Conference on Machine Learning (ICML 2025), 2025. Published 2025-05-01; last modified 2025-08-11.
[43] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Couraapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C. J. Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental algorithms for scientific computing in python. 17:261-272, 2020.
[44] Joe H. Ward. Hierarchical grouping to optimize an objective function.
1963.
[45]
Joon-Hyeok Yim and Anna Gilbert. Fitting trees to é fi-hyperbolic distances. In Advances in Neural Information Processing Systems, volume 36, pages 7263-7288, 2023.
[46] Amit Zeisel, Ana B Muñoz-Manchadoo Simone Codeluppi. Peter Lönnerberg, Gioele La Manno, Anna Juréus, Sofia Marques, Hermany Munguba, Lin He, Christer Betsholtz, Cecilia Rolny, Goncalo Eastelo-Branco Jens Hjerling-Leffee and Sten Linnarsson. Cell types in the mouse cortex and hippocampus revealed by single-cell ma-seq. 347(6226): 142, 2015. doi: 10.1 126/siinne aaa 1934.
13

---

A Complementary qualitative and visual results
We provide in Figure compleenttty qualitative results obtained on simple unweighted graphs, and details about the generation procedure. The original graph is an unweighted graph, with constant unit edge weights, generated following different graph models: Figures 5a and 5b correspond to random connected Erdös-Rény. graph with 10 nodes, Figure Tigure[5clis is stochastic block model graph with communities and 40 nodes, generated with an intra- catra-commuity probability of 0.5 and an inter- community probability of 0.05, and finally Figure 5d is (4, 4)-grid graph, with a total of 16 nodes. The original nodes are depicted in orange in the figures, whereas additional nodes, when provided by the method, are depicted in blue. The root node used for generating the corresponding tree is depicted in pink, and is set to be the same for all the methods. In every visualizations, the original nodes positions are kept fixed, and the added nodes positions computed using the SPRINGLAYOUT from the NetworkX package [22]
In terms of distortion, our method gives the best results in 3 out of 4 cases, and ranks second in the wrid-like graph case, where LAYERINGTRES performs best.
B Gromov's embedding
The tree metric dr, obtained by the embedding & given by Theorem 2 is characterized via Gromov products with respect to a basepoint w, which we denote by
(ælv)), (d()))))) + dr (r ((w)) (r()
This yields the identity
dT(((s), p(y)) = (Ir|=) + (wlw) 2(xly)
Gromov's argument [1 Page 156] further shows that the Gromov product (alw),, can be expressed as
(xlv)), = max mine 11+1)
gEP=.v
where Pa.y denotes the set of finite sequences y = (y...... we) in X with é 2 2, x = y1. and ye- It is important to note that in Gromov's 's construction, the resulting tree metric space (I,, dr) may include intermediate points that are not present in the original set X, but are introduced the tree to satisfy the metric constraints and preserve approximate distances (see Figure 6). These points serve as internal branching nodes that allow better approximation of the original distances under the tree metric.
To approximate an optimal ultrametric tree embedding of a finite metric space (X,d), one can leverage the single linkage hierarchical clustering (SLHC) algorithm, which is known to yield 2-approximation to the optimal ultrametric tree embedding [3T]. The SLHC algorithm returns a new metric ux on X, defined for all x, y E X by:
max max d(yk. )
ux (x( v) = min
yer
where Pz.g denotes the set of finite sequences ÿ (B1...., me) such that y1 = 2. y, and y X for all i. To relate this tree embedding via Gromov products. fix a base point E X, and define
max d(x,w). xeX
Then the function do X X given by
do(x, v) = m (xly) if + y,
otheewiie
defines a valid metric on X. Applying SLHC to the metric space (X, d.) yields an ultrametric space (X, ux). Finally, we define the tree metric as
dr(x, y) - dd
14

---

Original Graph
TryeringTres
TreeRop
Gromov
HCC
Neighbar Joining DeltaZera (ours)
Distances
Distortion: 2.00
Distortion: 4.00
Distortion: 2.00
Distortion: 4.00
Distortion: 2.18
Distortion: 1.34
(a) Connected Erdós Rénis graph with nodes
Original Graph
TryeringTres
TreeRop
Gromov
HCC
Neighbor Joining
DeltaZera (ours)
Distances
Distortion: 2.00
Distortion: 3.00
Distortion: 2.00
Distortion: 4.00
Distortion: 1.80
Distortion: 1.45
(b) Another connected Erdös Rénsii graph with nodes
Original Graph
LayeringTres
TreeRop
Gromov
HCC
Neighbar Joining DeltaZera (ours)
Distances
Distortion: 2.00
Distortion: 4.00
Distortion: 2.00
Distortion: 2.00
Distortion: 1.56
Distortion: 1.27
(c) Stochastic block model with components and nodes
Original Graph
Layering Tree
TreeRep
Gromov
HCC
Neighbor Joining
DeltaZera (ours)
Distances
Distortion: 2.00
Distortion: 6.00
Distortion: 4.00
Distortion: 4.00
Distortion: 2.38
Distortion: 2.30
(d) (4, 4) grid graph
Figure 5: Visual illustration of the different methods different graphs.
15

---

(ww)
(all)
@ (3)
(z)
Figure 6: Gromov tree embedding of the points in Euclidean space: (1,0), y (-1,0). and
w = (0,3). A intermediate node is introduced at a position such that lies at distance (xly) w from
w.
One can easily check that this procedure gives the same tree metric than the embedding given by Gromov.
Algorithm 2 GROMOV
Require: Finite metric space (X, d), base point X
Ensure: Tree metric dr on
1: Compute Gromov products: (xry) 1/2 (d(x, w) d(y, d(x, v))
2: Set m + m d(x,, w)
3: Define do (zx, y) + m (aly) mr if x + y. otherwise
4: Apply SLHC to (X, da) to obtain an ultrametric ux
5: Define metrie: dr, y)
ux(x,
6: return dr
Once the tree metric has been obtained through this procedure, one may then invoke the method deseribed in (6] to reconstruct tree spanning the set X. This reconstruction yields both the intermediate nodes and the leaves, the latter corresponding to all elements X except the designated root.
C Proofs of Theoretical Results
C.1 Proof of Theorem
For fixed p. let (X", dx:) be minimizer of 33. We have, for any (X,dx) dx).
plldx dx 11s0 + 5x- 5x.
Applying the Gromov tree embedding to (X*, dx.) and denoting the resulting metric tree by (I" dr-) get the following bound using Theorem 2.3
dx- (z, -2) (8x pl|dx dx- =o
s (4(2), ((y)) & dx- (x for all x, y. X.
Combining this with the triangle inequality yields
||dx dr- Il < |dx - dx- 10 + ||dx- dr~
< |dx dx- 11x0 2 (ōx al|dx dx- |1)))) logg(n 2)
s 28x log, 2) + (1 2 2l0gg - 2) ||dx dx- 11,0
Thus, we have
dx(x,2) (26x logo(n 2) (1 (1- 2og - 2) I|dx dx- (1x)) S dr- ( k(y)).
For the second inequality, we have Var y. ( ()))) < dx- (α, v) < dx v). The first inequality true by Gromov theorem and the second due the constraints the optimization problem 3.1..
16

---

As long as 2 1 directly to X is improved.
(n-22) the worst-case distortion achieved by applying the Gromov embedding
C.2 Proof of Proposition 3.2
To control the approximation error introduced by the smooth maximum operator, we first state standard inequality satisfied by the LSE, function.
Proposition C.1. For O, the function satisfies the following inequalities
max & LSEx(x) & maxx + log(n)
A
log(n)
min X
LSE->(X) S min x.
Proof. Let m = .max; Ti. Then we have
n
Am Σ Axi S nm
Taking the logarithm and dividing by X > 0, we obtain
S (X) m log(n)
A
We ready this bound to control the smooth approximation of Gromov's four-point condition and prove proposition 3.2
In X, there are n' ordered 4-tuples of points with replacement. By proposition C.I x, y: 2, W. we have
for any fixed
min((xly) (ul=) - (x)2) log(2) I (LSE- (vlz) (x]12)
and
4 4log(n)
(TSEE_x ((rly) (yl=) (arl)) S (62)) s 56x
max 2.
Combining those inequalities, we obtain the desired result.
C33 Proof of Theorem 3.3
For every N, let X .......; zn be fixed re-point set.
We consider a random metric space on n points. This means we fix a probability measure v on Mns the set of all metric spaces over points.
Since metric space on n points completely determined by the distances between each pair of points, we can think of metric conditions (non-negativity. symmetry, triangle inequality, and zero diagonal).
probability law on the set of all possible distance matrices that satisfy
So, when we say that random variable X has law v, we mean that we are choosing the distances between the n points random, according v. In this way, the law is law on the distances between the points.
Definition C.2. We say that random metric space (X, d) (with law v) is uniform if the random variables d(a;, .ry) for F4 Fy X are independent and identically distributed, following common law f. We say that is the law of distances of the uniform random metric space.
In this class of random metric spaces, we have the following asymptotics for 5(A)
Proposition C.3. Let be a probability measure on R2 (with compact support). Let Un be probability measure on Mn, such that the associated random metric space is uniform, with law of
17

---

distances given by L. Let (X, d) be random metric following the law Vn- Then, when n goes to infinity and X (logg)) n), we have
10x
(1og μ + log m) 26) e2n11o(1))
where μ depends on the law l and but on and
Proof of Proposition C.3 We use the standard convention that the letter C denotes universal constant, whose precise value may change from line line.
Recall from 3.2) that ((A)
can be written explicitly as
X
1
log
Σ
(-\()))) + e-Al))))
(S.U.2,,)EE4
where the Gromov product are taken with respect to the metric d. We denote by (1r, Mr R, w) the term
M e -(xll) + (=)(()))
We start by preliminary estimate on We introduce some notations. We note
82.0.2.0 min((1) y) (g12)w) (xl2)
We say that quadruple 9 (z, y, 2, w) E X is generic if the elements æ, y, 2, w are pairwise distinct. Observe that if @ı and 22 are both generic, then f(1)) and f(42) are identically distributed. In partieular,
B[S(a))] ([f()))),
and we denote this common expectation by μ.
Lemma C.4. For every p N, we have the following asymptotics when À goes infinity
B[f(g) emmax by (A))
and
E(S()) & ve)
Proof. Recall that
f(x, y, 2, w) e A(z/y)e + t ((a1))) = exp ((1l)) (x)2)
hence by Proposition C.I
log )) < f(I, 2, S exp (A6m.)...))
exp
We conclude that for universal constants C1, Cz. We recall the classical limit
Cie < f(g) s Cze
lim E [x max
A
which holds for a positive, bounded random variable, which we can rewrite
E
{ (max o(A)
Applying that to ePS, we obtain
E [ Apdo]] ) c² max (()) ((A)
18

---

and thus
( = e
= maxx
Observe that the law of the random variable 6G for (ar, y, 2, w), depends only of the configuration of which z, y, 2, are equal between them. In particular, there is finite number of possibilities for max og (which depend only on the law E). is tedious but easy check that max 6g is maximum when is generic. Recalling that is a notation for EE [f(g]] when g is generic, we conclude that:
(B [f()))] < peal))
We now study the sum
S
Σ f(z,y. v.
If the terms of the sum were independent random variables, could directly apply standard limit theorems. However, this is not the case: each term f(x, y, 2, w) depends only on the pairwise distances between the four points x, V, 2, w. In particular, two terms f(z, Us w) and f( V 2', ,,,,,,'' w() are not independent whenever the sets their arguments intersect, i.e.,
{-. y, w n {ar 3/ "',,"' + 0.
To formalize this, for two 4-tules @1 = (Ir, y, 2, w² and Q2 = (x',v's 2', w() in X2. we write qi g2 to denote that they are disjoint
{a, v. 2, w n {2' V/ d' w') 0.
Despite the dependencies, the situation remains favorable. The number of dependent pairs,
{l9 92) (x*)² Q1 L 92}:
is bounded by Cn?, while the total number of pairs in (x*)² is n.. Thus, most of the terms are approximately independent, which allows for concentration techniques and asymptotic analysis.
We adapt the classical proof of the weak law of large numbers to this weakly dependent setting using Chebyshev's inequality. To that end, we compute the variance of the
S
Σ
(12,9,2000 w.
(B.
It is convenient to consider the centered version
nn =
Σ
f(x, y, w), where f(x,y,2,0 2, = f(x.fll.2... y. w) B[f(2, y, 2, w)].
(x)
so that [[S.] = O. The variance then
E|SA
Σ
B[f(a))[(12)]
(g) (E)*))
Σ [lf()))(()))+++ + Σ Elf()))((>)))
41 Lo2
91 91
Since Q1 1 22 implies independence and [E(f(a))) 0. the first sum vanishes. Thus, are left with
E| = Σ Elf(a))((o)))
an Æ4z
By Cauchy-Schward inequality we have
E [(()))((22) = (E [f(x)) [f(2)))))
and by the triangle inequality
(E [f [(f(g)
+ + +Ef(()
19

---

Applying the Lemma, both terms on the right hand side are bounded by pee(A), hence
(E [f(())]) ((a)
Using that the number of pairs with qı L q2 is bounded by On² we finally obtain the variance bound
E[ S p² p
We recall Chebyshev's 's classical inequality:
P( - 2 E[(X
28)5
Applying this inequality to X Sn and e' = =n' we get
S
P [[[Sp] 2 n²E) v
E2
and using our previous estimate
1
12(c(A))
112
P
Sn
2E
n2
E2n
E² 1211-011)
which we can rewrite as We now compute the term
2
P
Sn.
B[Sn|
2
n2
n
22n1-o(11
# Egexs [.)( We can write:
[[Sn]
1
Σ
B[f(a)]
n
nd
X
Σ OEX
[[((a)+
Σ
B[f(a)
n
O
Moreover, the number non-generic quadruples (i.e., q E X where at least two the entries coincide) most On for some constant C O. By the Lemma, E. [4)) bounded by (A) Combining these observations, we obtain
1 B[S (1 (1-0
01-0 (2) 1 (A)
11 (1 (1 (1+ nI-o(1)
n
which implies that [[S]]
-
We can now look at (A) = 1 log Sn. We recall the elementary inequality
bl
llgg - log bl <
b
If |S, - E[S.]] S née then
Sn TESM.]
ne
< E[Sp]
E[Sm]
Since B[Sa] ~ n1,,, we have for large
2
<
E S.
n μ
Hence, for n large enough,
S.S. E[Sm
log S, - log [[S
<
E.Sa]
20

---

Therefore, the oeg-dffereence is controlled by the relative deviation scaled by μ p= We conclude that when is large enough,
2c
1 Sn
1
P
[log S.. log E[S]]
N
P
B[Sm]
26)
p.
n
n
32n1-o(1
which implies
1
log Sn - log [[[sm]]
2
222=)1-011)
82n1-o(1)
Using that n1= BSr ~ H4, when n is large enough we then have:
1 P ( log S, (log + 4log n) 22) - =2n21o(11)
We can finally state the result that justify the batching method used compute the delta.
Given a random metric space on n points, distributed according to a law V, we can define a random metric space
S points by restriction. Let (X, d' be random metric space drawn from and let Xm C X be a subset size m, chosen uniformly at random. We equip X,, with the metric dix,,, induced by d. We can iterate this process k-times, choosing the subsets of size disjoint from each other, and we obtain a sequence of random metric space X , X each one uniform with law of distances f.
Theorem C.5. Let E be probability measure on R4. Let v be probability measure on Mn, such that the associated random metric space is uniform, with law of distances given by f. In the regime K n and e-1 log we have
(A) Ji,
(2)
22K (3kk-oo111)
Proof. For a uniform random metric space (X, d) and sequence of random subpaces (X...... X K constructed above, each (X², dix;, is still uniform random metric space with the same law of distances. Because m K n and Ollog n) we have Ollog m).. We apply the Proposition C.3 to get
(A)
(log μ + 4logn)
2 S e2n !=!1-
IP
I (log e + 4
2 $ "2nl-o(1)
X
The (Yr)) are independent random variables hence
P
Vi
s K,
(A)
(log p + 4logm) 50)
X
2k mkk-(()
which means that
TP
7 S K,
(1) x:
1
(log e + 4log m) se 21
22k -o(l)
3knl-o(1)
When
((A)
x2
#log 44og-+4ogm 41og
Se,
and
(log μ + 4log n)
S..
Thus,
8(2)
((A) X!
1
D +
log < 3z.
x
m
21

---

We can conclude that ii
P
x
x
TP
Vi, ((A)
{(A)
2 8
IP
(A)
1
(log μ + logg)
26
2 e2K n!-o(1)"
Corollary C.6. Let be a probability measure on R.. Let v be a probability measure on Mn, the metric spaces points, such that the associated random metric space is uniform (see definition C.2 with law of distances given by f. In the regime m ~ n and X ~ g- log n. we have
8xx
((A) Km
S
22 n 110
Proof. This follows directly from triangular inequality, definition of (A) Proposition 3.2
K,K.m (see equation (3.3 and
Models of uniform random metric spaces. We now describe several models of random metric spaces that are (aproximatively) uniform.
In [27] the authors study a model of discrete random metrie spaces. For an integer r > 2, consider the finite subset D C. Dn, of metric spaces for which the distance function takes values in {0, I.... 2r}. Let V, be the uniform probability on this finite set. Let C% C Dr the subset of metric spaces whose distance function takes values in the interval fr....,2r) 2r). Observe that any collection of numbers
in fr...., }r} satisfy the triangle inequality, hence C. = fr, 2r) and the restriction of the measure vi to C is simply a product measure. In other words, the random metric space conditioned to be in C, is uniform. The authors prove that, when is large, the measure V,,, is exponentialy concentrated on C%
Theorem C.7. There exists 3 > 0 such that for large enough we have
(C()
1 - - An
In other words, the uniform random metric space with integer valued distances and diameter bounded by 2r is (approximatively) uniform.
Let G(n. p) denote the Erdós Erdós-Rényi random graph: graph on n vertices where each edge between pair of vertices is included independently with probability p E [o, 1].
In the regime
p²n - 2log - 00.
n² - p) 0o.
the graph G(n, p) asymptotically almost surely has diameter 2, that is, any pair of vertices is either directly connected by an edge or shares a common neighbor, by [2]. According to [3] $4], conditionnaly to the diameter being 2, the distance matrix of this graph function of the incidence matrix; in particular, the associated random metric space is uniform.
We also evaluate the distribution of distances on real datasets as shown in Figure 7 approximately these distributions are log- normal, suggesting that they could satisfy the hypothesis of our theorem.
We can see that
C.4 Proof of Proposition 3.4
Following Bridson and Haefliger (5). the four points condition given in (2. can be seen in the following way: Let E Dn,, for i, (I,....n), n., , let 4, and la be defined by
4 = Dij + Dui
11 Dik + Dz1
(3 = Da + Djk
22

---

celoggt
airrort
620
Oslane
Figure 7: Distribution of the distances of the unweighted datasets of our benchmark.
and Mj and M2 the two largest values among 4, 12, and la. We define
ji, k. M1 M2
and the Gromov hyperholicity dD of the metric space is the maximum of ji,,j, over all possible 4-tuples (i. k, 1) divided by 2. That is,
max 6D (.
8(1, k.
The function 6D. viewed as function over D,, maximum of piecewise affine functions, and is therefore itself piecewise affine.
We can interpret oD geometrically as follows. Each 4-tuple (i, 1) determines three quantities li, 12, and 43. The differences between these quantities partition the plane into regions corresponding which of 2,, 12:45 f3 is largest, second largest, and smallest (see Figure K)
To demonstrate the non-convexity the set in question, it suffices to exhibit a single counterexample. We do so by constructing two metric spaces, each defined over four points, and represented via their respective distance matrices. These examples are deliberately simple to allow for full transparency of the argument and ease of verification.
While we restrict ourselves here to the case n the same construction strategy can generalized without difficulty to any number of points 2 4. The underlying mechanism responsible for the failure of convexity not peculiar to this specific dimension.
Let us consider
0
1.1
1
1.2
0
1.2
0
1
1
0
1.1
D
and D2
0
Computing the associated triples (4,, 12, (a) for each space, find
L (2.1,2.2,2) for D1, L = (2,2,2,2.1 for D2.
Now consider the interpolation between D and D2 defined by t E [0, (D) + (1 t)D2 with associated triple (1, (t), (t).
Since the values of l2 are identical for D, and D2, the interpolation affects only / and 43. Thus, along this interpolation 8 behave like
t
(t)
which is concave and negates that dp is a convex function over D4,
23

---

1 -1118
1 >3>>
1/ - 1
1 l2 1> >>>>>
3>
D2
3> 2>1
2> 1 > 3 1 - 4
13
Di
2> 3 12 13
Figure 8: In the diagram, the plane is divided into six sectors, each labeled according to the ordering of 12,1 (e.g., >>>>>>>>> 2 > means 4 is largest, then l,, then 1z). The labels inside each sector indicate the expression that represents 8(1, k, 1) in that region.
C.5 Floyd-Ward Warshall as a projection
This section mainly rewrites results described in 3. Let W E R be the matrix of non-negain -egaatiee edge weights of (possibly directed) graph with n nodes. Let SP SP (W) denote the matrix of shortest path distances between all node pairs. We use the notation A < B to mean that Aij S B,j for all (i,j), and recall that D, denotes the set of distance matrices (i.e., matrices that satisfy properties of metric).
We aim show that
SP(W) E argmin
| - WlIps
DEP. DSW
for any bp norm with p 0.
Note that SP(W) W since the shortest path between two nodes is always less than equal the direct edge weight (if it exists). Hence, SP(W) is feasible candidate for the minimization problem.
Suppose the following property holds:
VD E D., D W = D s SP(W).
Under this assumption, the optimality SP(W) follows immediately. Indeed, for any such D, we have:
0 W. - SP(W)) 4 I Wi - Dij = Dij - Wayl.
for all (i,j), using the facts that SP(W) < W. D < SP(W). and S W. Therefore,
|SP(W); Wo < Dij Wil.
which implies
||S((W) w < |D W
We now prove the property. Assume for contradiction that there exists (i,j) such that Dij > SP W) Consider the lex smallest such pair under the total ordering induced by increasing values of (P(W))a That is, sort all node pairs so that:
SP(W) Jn S
S. .... SP(W) iar
and let (i,j) be the first pair for which Dij SP(W)
There are two possibilities: (1) (W), Wiy. Then Dij WTj. which contradicts the assumption D W. (2) There exists some node à such that
k = SP(WPP(WW) + +PP(W)
Since D is metrie, it satisfies the triangle inequality:
Dij < Dis Dkj-
24

---

Table 2: Epochs until early stopping for each dataset.
Unweighted graphs
Non-graph metrics
Datasets
C-BLEGAN
CS PHD
CORA
AIRPORT
WIKI
ZEISEL.
IBD
Epochs until Early Stopping
166
402
474
877
1000
456
122
But by minimality of (i.j) in the sorted list, we know:
Du S SP(W)
Dey S SP(W)
Therefore,
Dij Dik + DRY (P(W)& SP(W)ks SP(W)
which contradicts the assumption that Dij > SP(W);g-
This contradiction implies that no such (i.j) exists, and thus S SP(W), completing the proof.
D Complementary experimental results
D.1
Convergence of the method
In this section, we examine the numerical convergence of our method 2 the number of epochs for which it has reached the early stopping criterion. These results show that convergence typically occurs well before early stopping (defined as iterations without improvement of the objective) well before the maximum of 1000 epochs, except in the WIKI dataset, suggesting that the optimization process is generally stable and effective. We also show in Figure@the evolution of the objective function and its components over training, using the best hyperparameters for each dataset.
D.2 Average & error and Runtime Efficiency
In this section, we complement the Loo distortion results (Table [ with an analysis of the average embedding quality using { error. Table 3 reports the mean & distortion (lld - dr || ([))/((())))))))(( between the input distance matrix and the distance matrix induced by the fitted captures the average deviation rather than the worst-case distortion, providing a different perspective on the fidelity of the embedding. The experimental setup is identical that used for Table including the selection of hyperparameters (based on lowest & error) and root sampling strategy.
metric. This metric
As shown in Table NEIGHBORJOIN (NJ) achieves the lowest average distortion across all datasets, including both graph-based and non-graph metrics. This is expected, as NJ is a greedy algorithm designed to minimize additive tree reconstruction emror from distance matrix. However, it does not guarantee low worst-case distortion, and its performance in terms of too error is less consistent (see Table IT.
By contrast, our method, DELTAZERO, not designed to minimize average error directly but rather optimizes distortion-awant loss function. Despite this, it performs competitively in & distortion, especially on datasets such as C-ELEGAN and ZEISEL. However, on larger datasets like CORA and AIRPORT, it yields higher average distortion than NJ, suggesting that there may be off between minimizing foo and ε error in practice.
Table reports the average runtime (in seconds) over 10 runs for each method and dataset. For ZERO, we report the runtime of the optimization step only, using the best-performing hyperpa- rameter configuration (as selected in Table D.. For NJ and TREEREP, the reported times exclude the Onn²) time required to construct a full pairwise distance matrix, as these methods operate directly produce tree structure.
As expected, DELTAZERO incurs higher computational cost than the baselines, particularly on large datasets such as ZEISEL and CORA, where optimization can take several thousand seconds. This is price of our optimization method althought as highlighted in Section 3.2, the major bottleneck comes from the usage of FL,YYD- WARSHALL algorithm at each step of our proposed gradient descent. Lightweight methods such as GROMOV and HCC run much faster, though they offer less accuracy in both lo and é metrics.
25

---

C-ELEGAN (Ir=0.1, 1=0.1, A=10.0)
Kmm
DL212
220
230
2113
31
522
CS-PHD (Ir=0.1, p=0.01, A=1.0)
Kmm
[DX- DI2222
314
23.4
211
CORA (Ir=0.01, p=0.01, 1=1.0)
6,4)D,K,m
1. X(DI
DX 21,2
16.74
15.14
AIRPORT (Ir=0.01, p=0.01, A=1.0)
6m
L_X(D
[DX DI,212
17.01
3.5
13
17.03
311
13
17.00
500
17.00
WIKI (Ir=0.01, 0=0.01, 1=1.0)
Km.
L_K(D
[DX DI2222
17.0
6.10
3.13
17:00
5.75
ZEISEL 0.00, p=0.1, A-10,0)
X/DI
DX D2
2014
1422
1.75
2002
1100
1.40
440
304
300
1/5
275
150
300
120
35
IBD (Ir=0.01, 0=0.0,, x=1.0)
6..)DKK.
X/DI
DXX 2
16:40
0.75
3.17
14.40
21.15
3.15
01
185
120
Figure 9: Training metrics over epochs for each dataset.
26

---

Table 3: & average enror (ldd -d111
/ /G).
Best result in bold (lower is better).
Unweighted graphs
Non-graph metries
Data set
C-ELEGAN
CS PHDD
CORA
AIRPORT
WIKI
ZEISEL.
IBD
NJ
0.30
1.35
1.06
0.49
0.51
0.04
0.09
TR
0.83 +: 0.16
2.55
+: 134
2.91
0.6
1.28
= 0.21
1.85 +: 0,26
0.11 + 002
0.13 001
HCC
0.88 1 0.22
2.59
+
2,44
0.43
1.10
- 0.13
1.53 - 0.17
0.08 + 000
0.27 0.0
Layering Tree
0.73 + 0,03
4.90
+ 0.0
3.68
0.23
0.62
= 0.06
0.83 - 0.04
Gromov
1.13 + 0.01
2.80
+ 0.36
3.34
0.12 0.12
1,55
= 0.08
2.12 - 0.04
0.10 + 0.1
0.39 + 0.2
DELTAZERO
0.42 + 0:01
2.71
+: 0.8
3.20
4: 0.09
1.31 = 0.03
1.26 - 0.00
0.08 + 0.00
0.36 + 0.0
Table 4: Average running time in seconds over 10 runs.
Unweighted graphs
Non-graph metrics
Data set
C-BLEGAN
CS PHD
CORA
AIRPORT
WIKI
ZEISEL
IBD
NJ
0.34
3,42
103.81
244.93
81.89
207.91
0.25
TR
0.78
2.64
25.64
36.37
24.43
94.02
1.23
HCC
0.67
3.54
19.54
31.15
18.28
36.21
0.52
LayeringTree
0.86
8.81
156.54
344.43
140.11
Gromov
0.03
0.23
1.47
2.20
24.43
2.20
0.02
DELTAZERO 51.00
134.28
3612.35
2268.72
819.90
5664.40
289.07
These results highlight a key trade-off: DELTAZERO offers superior worst-case distortion, but at the cost of increased runtime.
Remark D.I. Note that do not report other metrics such as Mean Average Precision (MAP) score (see 42 Equation 33] for the formula), as does not measure metric fidelity (e.g., uniform rescaling preserves MAP), but only local neighborhood preservation. In our setting, optimal tree can induce a markedly different neighborhood structure from the original graph (c.g., embedding a grid into tree). Moreover, MAP is only meaningful when all methods embed into the same target space, which is not the case here. Finally, MAP can only be computed when the metric arises from underlying graph structure, which is not true for all datasets consider.
30
D.3 Sensitivity analysis
In this section, we provide a sensitivity analysis on the parameters of DELTAZERO, namely the number of batches K, the batch size m, the temperature parameter (ef. eq 3.2) and the distance regularization coefficient on the norm (cf. eq (.4)).
Evaluation of the approximation (()) D, of the Gromov hyperbolicity. We first provide
numerical study of the approximation D.K,m (see eq.33.3 (3.3) of the actual 5-hyperbolicity. We consider the CS-PHD dataset, which has an exact value of 8 6.5 that can be computed exactly as too large. We evaluate the quality of our approximation with respect to this ground truth.
Figure 10a illustrates the influence of two key hyperparameters: the number of batches and the batch size m. fixing À 1000. Figure 10b illustrates the influence of the regularization parameter and the batch size m, fixing K 50. Both figures also report the true ó. Fach point represents the average over independent runs.
We observe that batch size m plays a critical role in the quality of the estimation. When m is very 4), the estimated values significantly biased and far from the true 8. As increases, the estimates become more stable and converge toward the ground truth, even with a moderate number of batches. This pattern is consistent across both panels of the figure. In contrast, the effect of is less pronounced once reaches a sufficient seale, beyond which the estimates flatten out near the true d value. These results highlight that batch size is the dominant factor influencing the accuracy of our smoothed estimator (() k, Indeed, computing the exact requires evaluating all possible quadruples of nodes, which amounts (*) O(n²) operations. In our
small (e.g.,
27

---

batched approximation, we instead sample K batches of size m, resulting in a total of K (*) sampled quadruples. Since (*)) O(m²), the number of evaluated quadruples scales O(K m highlighting that m has a higher-order impact than K on the estimator's fidelity. This explains why increasing the batch size leads to more accurate and stable ó estimates, even with relatively small number of batches.
m
10a
== 16
D, Olog scale)
m = 32
m = 48 True
10a
10a
10a
10"2
10-1
10t
10
10
10a
K (lug scale)
A (lug scale)
(A) (a) Evolution of the mean D. as a function of the number of batches K, with À = 1000.
(b) Estimation of (A)
D.K. as a function of A, with
K = 50.
Figure 10: Approximation A K.K.m computed on the CS-PHD dataset for different batch sizes m.
Km
Sensitivity to parameters on the distortion. We now consider the C-ELEGAN dataset and study the impact of the parameter tuning for μ,, À and m. We vary one hyperparameter at time, while fixing the others to their optimal values obtained from the grid search. We evaluate the mean distortion over repeated across 5 independent runs and
100 randomly sampled root nodes. This procedure plot the mean and standard deviation of the & distortion across these repetitions.
We first study the influence of the regularization coefficient l the fox distortion in Figure 1a One can notice that, for the lowest μ values, the distortion is high, indicating that the solution is insufficiently driven by the data; for the highest values, the distortion is also high, which suggest that the tree-likeness of the solution lost. For a good tradeoff between proximity to the original metric and tree-likeness of the solution, optimum is reached. This further showcases the interest of introducing a term related to the Gromov hyperbolicity into the tree metric approximation problem.
We then study the impact of the À parameter in Figure 11b for different batch sizes. Results suggest that a good trade-off between large values (that provide an estimate close to the actual value but at the price of sharp optimization landscape) and small ones (that provides smooth estimate easy to optimize) should be found to reach the best performances.
Finally, in Figure Tic we study the impact of the batch size m, for various À parameters. One can note that, for moderate values of X, an optimal performance reached for a moderate size of batch size, which suggests that m could be set with a relatively low value, enhancing the ability of DELTAZERO tackle moderated-size datasets.
E
Implementation details
Our optimization procedure was implemented in Python using PyTorch (33] for automatic differenti- ation and gradient-based optimization. All experiments were run using PyTorch's GPU backend with CUDA acceleration when available. We leveraged the Adam optimizer and parallelized computations over batches.
The training objective minimizes regularized combination of the 5-hyperbolicity loss and the reconstruction error of the distance matrix. The optimization is performed over the upper-triangular weights of complete undirected graph, which are projected onto shortest-pait path distances using the Floyd-Warshall algorithm at each iteration. This projection is implemented using a GPU-compatible variant of the algorithm.
28

---

5
3.5
3.6
3
3
J-100
J-500
Num32
2
7o:40
1-1000
10
10
10-2
10
107
1ot
15 20
(a) Effect of the distance regulariza- (b) Impact of the log-sum-exp scale (c) Impact of the batch size m on tion coefficient on &oo distortion. À on &oo error across various batch &oo error for multiple À values sizes m.
Figure 11: Sensitivity analysis of optimization hyperparameters on the C-ELEGAN dataset. each to their optimal values from prior grid search. Results
plot, non-varied hyperparameters averaged over 5 runs, and distortion values averaged over 100 root samples per run.
To efficiently approximate Gromov hyperbolicity objective, we randomly sample K batches of quadruples and accumulate gradients across 32 sub-batches in each outer iteration. This simulates larger batch size while remaining within GPU memory constraints. Gradient accumulation performed manually by computing the backward pass over each sub-batch before the optimizer step.
Training includes early stopping based on the total loss, with patience of 50 epochs. We store and return the best-perfone best-performing weights (in terms of the objective loss (3.4) encountered during the optimization.
To ensure reproducibility, we provide all code and experiments at varraboottr/bfffeeeeroabbeelllod
com/
E.1 Hardware setup
All experiments were conducted using a single NVIDIA TITAN RTX GPU with 24 GB of VRAM. The implementation was written in Python 3.11 and executed machine running Ubuntu 22.04. No distributed or multi-GPU training was used.
E.2 Datasets
For C-ELEGAN and CS PHD,, we relied on the pre-computed distance matrices provided at https 7/github. con//rsotthel//reeee The C-ELEGAN dataset captures the neural connectivity of the Caenorhabditis elegans roundworm, widely studied model organism in neuroscience. The CS PHDD dataset represents a co-authorship network among computer science PhD holders, reflecting patterns of academic collaboration. For CORA and AIRPORT, we used the graph data from https and computed the shortest-path distance matrices on the largest connected components. CORA is citation network of machine learning publications, while AIRPORT models air traffic routes between airports. The WIKI dataset, representing a hyperlink graph between Wikipedia pages, was obtained from the torch, sarch__eemetrree library (15). ZEISEL. is a single-cell RNA sequencing dataset describing the transcriptomic profiles mouse cortex and hippocampus cells, commonly used study cell type organization in neurobiology. It was obtained from httph:::///// //ttts://github..
//github. www.///////eeeeeee htwpHHHeeeeeerchhhgggeeeee
wwwoovvilarrsseeeeeeeeae phhhon The IBD dataset (Inflammatory Bowel Disease) contains 396 metagenomic samples across 606 expressed microbial species. The dataset is publicly available via BioProject accession number PRJEB 1220.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims stated in the abstract and introduction are supported by both the theoretical developments and the experimental results in the paper. Specifically, the paper claims introduce a differentiable framework for tree metric approximation via smoothed Gromov hyperbolicityy and shows empirically that the method outperforms existing baselines in several benchmark datasets. The claims are matched by rigorous formulations and a novel algorithm (DELTAZERO) with empirical validation.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper discusses limitations both scalability and approximation tightness. Specifically, it acknowledges the computational cost of approximating ó- f-hyperbolicity (even with smoothing and batching). also notes that the method introduces additional hyperpa- rameters, and its performance is sensitive to those. Moreover, the empirical evaluation is primarily conducted on graph-based metrics, generalization to other types of metric spaces may require further study.
Justification:
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
The paper provides formal definitions, clear theoretical formulations, and justi- fies its optimization objective through a relaxed, smoothed surrogate of the o-hyperbolicity and distortion. Key propositions (c.g., smooth approximation bounds in Proposition 4.3) are stated precisely, and their implications are discussed both in the main text and in the appendix. All theoretical claims are supported by appropriate references, which are carefully and comprehensively cited to situate the contributions within the broader literature on metric embeddings, hyperbolicity, and optimization.
Justification:
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
The paper includes algorithm descriptions, theoretical foundations, experi- mental setup details (e.g.. hyperparameter grids), and references code/data sources. The methods used are based on widely adopted optimization and graph processing techniques.
Justification:
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We intend to publicly release the full implementation our method, along with scripts to reproduce all the experiments presented in the paper. This will include instructions for installing dependencies, running the optimization pipeline, reproducing the results across datasets, and generating the figures and tables. The code will also contain links to download all datasets used in the experiments, along with preprocessing scripts needed. An anonymized repository is available in the supplemental material.
6. Experimental setting/details
30

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
The paper provides detailed experimental settings, including the datasets used, preprocessing steps (e.g., keeping only the largest connected component), evaluation protocols, and distortion metrics. It outlines the hyperparameter grid search for learning rate, regularization strength, smoothing parameter, batch size, and number of batches. The optimizer (projected gradient descent) is described clearly, with details about the projection method FFlyddWaarhhe number of iterations, early stopping strategy, and model selection criteria. Additional implementation details and runtime comparisons are provided in the appendix.
Justification:
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports mean and standard deviation of distortion metrics across 100 random root samples for all relevant methods, as shown in Tables and These error bars reflect variability due to random selection of root nodes in methods like GROMOV, HCCROOTEDT TREEFIT, and DELTAZERO, which depend on a pivot. For each configuration, the standard deviation is computed over multiple runs, and the paper explains how these statistics are obtained (e.g., independent repetitions, fixed random seeds, and early stopping strategies).
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Experiments were performed single GPU (NVIDIA TITAN RTX), with reasonable training times reported. The computational cost of each method is benchmarked, and complexity analyses provided.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::/ps//aaaaa...co/o////////a
Answer: [Yes]
The research adheres to the NeurIPS Code of Ethics. It does not involve human subjects, sensitive data, or applications with foresecable societal risks. All datasets used publicly available and appropriately cited.
Justification:
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This a methodological paper focusing on algorithmic improvements metric learning and geometric representations. It does not present applications with immediate ethical, environmental, or socictal risks. Nonetheless, improved tree embeddings could be indirectly used in systems related to phylogenetics, recommendation, hierarchical classification, which may carry downstream implications.
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
31

---

Justification:
The work does not involve pretrained models, generative systems, scraped datasets that pose high risk misuse. proposes method for metric space approxima- tion and hierarchical embedding based on standard graph datasets commonly used in the literature.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The paper uses publicly available datasets. Appropriate citations are provided in the paper. The license terms for these datasets respected they are freely distributed for academic use under open licenses (c.g.. CC-BY or similar). No proprietary data, scraped web data, third-party pretrained models are used.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
16. Declaration LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
32


Reviews:
[{"review_id": "cba5Mf1qUx", "reviewer": "Reviewer_ndmd", "summary": "This paper introduces DELTAZERO, a novel differentiable optimization framework for approximating arbitrary metric spaces with tree metrics by leveraging a smooth surrogate for Gromov's $\\delta$-hyperbolicity. The method is evaluated on both synthetic and real-world datasets, demonstrating state-of-the-art performance in minimizing distortion.", "questions": "1. Why use $\\ell_\\infty$ norm instead of Frobenius norm $||D_X-D||_F^2$ like metric nearness problems [1,2]?\n\n2. Are there any other tree embedding method can be combined instead of Gromov’s method?\n\n3. Is it possible to directly use the four-point conditions as the optimization constraints?\n\n[1] \"The metric nearness problem.\" SIAM Journal on Matrix Analysis and Applications, 2008.\n\n[2] \"Metric nearness made practical.\" AAAI, 2023.", "limitations": "The primary limitations concern scalability and computational efficiency.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The method addresses a fundamental problem in hierarchical representation learning.\n\n2. The work provides theoretical foundations, including Proposition 3.2 bounding the approximation error, and Theorem 3.1 showing improved distortion guarantees.\n\n---\n\n**Weaknesses**\n\n1. The method feels like it's combining existing techniques (projected gradient descent + Floyd-Warshall) rather than introducing something fundamentally new.\n\n2. The $O(Km^4 + n^3)$ runtime seems pretty heavy - especially that $n^3$ part. For real-world use, we'd need to know how this scales with bigger graphs. Some scalability tests would really help show if this is practical.\n\n3. Runtime performance is concerning - the method takes over 5600 seconds to process just 3005 nodes (Table 3 in Appendix D.1). This makes it impractical for real-world applications where we typically need to handle much larger graphs.\n\n4. The paper doesn't discuss how quickly the method converges. It would be helpful to see how the solution quality improves with more iterations (T). Some analysis here would give users better intuition about tuning this parameter.", "was_revised": true, "final_justification": "**Final Justification for Score:** 4 (Borderline accept)​\n\n**Resolved Issues:**\n\n- The authors clarified their key innovation (optimizing $\\delta$-hyperbolicity via gradient descent), resolving my initial concern.\n\n- While still time-consuming, their justification (accuracy/runtime trade-off, GPU parallelization) and future plans (hyperbolic embeddings) make this acceptable.\n\n- Early-stopping results show practical convergence; adding training curves would further strengthen the paper.\n\n- The $\\ell_\\infty$/$\\ell_2$ distinction and four-point condition discussion were helpful. Suggest including these in the paper/code.\n\n**​​Recommendation​​:** Strengths outweigh limitations.", "rebuttal": "## Reponses to weaknesses\n\n>The method feels like it's combining existing techniques (projected gradient descent + Floyd-Warshall) rather than introducing something fundamentally new.\n\nWe respectfully disagree with the reviewer on this point. While it is true that our optimization method builds on existing components, the core novelty of our work lies in optimizing the $\\delta$-hyperbolicity through a soft approximation. In previous works, the $\\delta$-hyperbolicity only appears to quantify how close a graph/dataset is to tree structure. Up to our knowledge, we are the first to propose optimizing it through gradient descent, and we expect that this idea has broader implications than the sole  Minimum Distortion Tree Metric Approximation problem which is the problem targeted in this paper. \n\n> Runtime performance is concerning - the method takes over 5600 seconds to process just 3005 nodes (Table 3 in Appendix D.1). This makes it impractical for real-world applications where we typically need to handle much larger graphs. \n\nYou are absolutely right: our method has a complexity of $O(n^3)$, which makes it impractical for very large graphs. We would like to comment on few aspects:\n- We operate in the space of $n \\times n$ distance matrices, meaning the per-step projection, though cubic, is not disproportionate relative to the size of the object being optimized ($n^2$ entries).\n- Several methods have been proposed to solve metric nearness (e.g. [1,2,3]), often relying on iterative procedures. While these methods may have lower theoretical complexity than Floyd–Warshall, they tend to be slower in practice. This is because Floyd–Warshall, despite its $O(n^3)$ complexity, can be efficiently parallelized on GPUs, offering significant practical speed-ups over iterative alternatives.\n- While being more computationally demanding than all competitors, it outperform baseline methods in terms of worst-case distortion, which is the central objective of our framework. It then provide a deliberate trade-off between computational cost and quality of approximation. \n- Many well-established methods in machine learning have similar complexities. It is nevertheless true that we still have room for improvement regarding the implementation of DeltaZero to make it run faster.\n- Lastly, to further improve scalability, a promising and natural direction we are exploring is to optimize over point embeddings in hyperbolic space instead of distance matrices. This would enforce metric validity by construction and eliminate the need for explicit projection steps, leveraging the efficiency of geometric optimization in continuous spaces. \n\nWe firmly believe that this paper would constitute the first necessary cornerstone before exploring variants and optimized implementations for algorithms based on the idea of optimizing hyperbolicity.  \n\n> The paper doesn't discuss how quickly the method converges. It would be helpful to see how the solution quality improves with more iterations (T). Some analysis here would give users better intuition about tuning this parameter.\n\nThank you for your suggestion: in practive we observe that our method converges in a reasonable number of iterations. The following table gives for each dataset (with the hyper parameters choosed as in the paper i.e for the best obtained distortion) the number of epochs for which it has reached an early stopping criterion (defined as 50 consecutive gradient steps without improvement in the loss).\n    \nThese results show that convergence typically occurs well before the maximum of 1000 epochs, except in the WIKI dataset, suggesting that the optimization process is generally stable and effective. If the paper is accepted, we would be happy to include training loss curves in the supplementary material to illustrate empirical convergence across datasets.\n| **Dataset** | C-ELEGAN | CS-PHD | CORA | AIRPORT | WIKI | ZEISEL | IBD |\n| ------------------------------- | -------- | ------ | ---- | ------- | ----| ------ | --- |\n| **Epochs until Early Stopping** | 166      | 402    | 474  | 877     | 1000 | 456    | 122 |\n\n\n## Responses to questions\n\n> Why use the $\\ell_\\infty$ norm instead of the Frobenius norm, like in metric nearness problems [1,2]?\n\nThis is a relevant question. To clarify: we use $\\ell_\\infty$ only for theory and $\\ell_2$ for practice.\nPrecisely, our current definition of \"Minimum Distortion Tree Metric Approximation\" is grounded in Gromov’s theory, which uses  the $\\ell_\\infty$ norm, as it directly aligns with the worst-case distortion framework. That said, we recognize the value of alternative formulations, in particular under $\\ell_p$ norms (e.g., $\\ell_2$ or $\\ell_1$) which relates to the metric nearness literature [1,2] as mentionned. \nIn support of this, our experiments show that minimizing distortion in the $\\ell_2$ norm also results in low distortion under $\\ell_\\infty$. We believe it would be interesting future work to leverage Gromov hyperbolicity to derive theoretical guarantees for tree metric approximations under general $\\ell_p$ norms. \n\n>Are there any other tree embedding method can be combined instead of Gromov’s method?\n\nThank you for this question, it's an important point that we can clarify. In principle, **any tree embedding method could be applied** to the metric obtained after our optimization step. We chose to apply the Gromov embedding because of its strong theoretical connection to Gromov hyperbolicity. In particular, Theorem 2.3 provides guarantees on the distortion based on the hyperbolicity constant, which aligns closely with the objective we optimize. This connection justifies our choice both theoretically and practically.\n\n>Is it possible to directly use the four-point conditions as the optimization constraints?\n\nThis is an excellent remark. It is indeed possible to use a smooth version of the four-point condition as an optimization constraint. This requires implementing a smooth approximation of a sorting operation (see for instance [4]), since the four-point condition involves identifying the maximum among three sums of distances. In our work, we chose to formulate the constraint via the Gromov product instead, using the log-sum-exp function to approximate both the max and min. We had implemented both and they gave similar results.\n\n[1] \"The metric nearness problem.\" SIAM Journal on Matrix Analysis and Applications, 2008.\n\n[2] \"Metric nearness made practical.\" AAAI, 2023.\n\n[3] \"If it ain't broke, don't fix it: Sparse metric repair\". IEEE, 2017.\n\n[4] \"Fast Differentiable Sorting and Ranking.\" ICML, 2020."}, {"review_id": "Lvj6tt1UHr", "reviewer": "Reviewer_LGFS", "summary": "The paper addresses the minimum-distortion tree metric approximation problem: given a finite arbitrary metric space $(X, d_X)$, the goal is to approximate it via a tree metric $d_T$ (with embedding $\\Phi : X \\to T$) that minimizes the worst-case distortion\n\\[\n\\max_{x,y} \\bigl| d_X(x,y) - d_T\\bigl(\\Phi(x), \\Phi(y)\\bigr)\\bigr|.\n\\]\nThis is motivated by the fact that tree metrics capture hierarchical structure, and any deviation from a tree metric can be measured by Gromov’s $\\delta$-hyperbolicity (which is zero if and only if the metric is tree-like).\n\nIn this paper, the authors propose DELTAZERO, a differentiable optimization approach that ensures theoretical distortion guarantees over prior methods (for example, Neighbor-Joining, TreeRep, LayeringTree). It is a two-step process that jointly adjusts the metric to remain close to the original while enforcing small hyperbolicity (the trade-off between tree-likeness and fidelity to the original metric is governed by a regularization parameter $\\mu$). In the first step, they introduce a surrogate metric space $\\left(X', d_{X'}\\right)$ and solve the optimization problem:\n\\[\n\\min_{d_{X'} \\le d_X} \\quad \\mu \\,\\|d_X - d_{X'}\\|_\\infty \\;+\\; \\delta\\left( d_{X'} \\right).\n\\]\nTo make this solvable by gradient-based methods, the authors replace the max/min definitions of $\\delta$ with smooth log-sum-exp approximations and further approximate global hyperbolicity via batch sampling of point subsets. In practice, they optimize the distance matrix $D$ (subject to metric constraints) by projected gradient descent: each step uses ADAM, followed by projection onto the space of valid metrics via Floyd–Warshall. Finally, in the last step, the optimized metric $D^*$ is converted to a tree metric (for example, via a single-linkage hierarchical clustering procedure).\n\nThe paper is generally well-written and organized. Formal definitions are provided, which helps orient the reader. However, the content is mathematically heavy, and a reader may need a background in hyperbolic metrics to follow all the details.\n\nThe paper addresses a relevant problem important in several fields such as hierarchical clustering, phylogenetics, and network modeling. The approach of linking Gromov hyperbolicity to differentiable optimization is new and indicates high potential significance. Provided the experimental results hold up, the contribution has clear practical value.\n\nThe submission contains some original ideas as well as effective use of established techniques, combining them to achieve the results.", "questions": "1) Please explain the choice of parameters.\n\n\n2) How do you ensure the $\\mu\\geq 1/(2\\log(n-2))$ criterion holds?\n\n\n3) How do you tackle the non-convexity of Gromov hyperbolicity $\\delta_D$?", "limitations": "The submission does not specify the scheme of choosing optimal parameters, and how the non-convexity is tackled is not clear. Also, it doesn’t claim to perform well in general settings.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The submission seems to be technically sound overall.  The definitions and background are clearly stated, and proofs are deferred to appendices, indicating mathematical care. However, I have a few questions regarding some of the claims made.\n\n\nStrengths:\n\n1) The paper introduces a fresh perspective by combining Gromov hyperbolicity with differentiable optimization. Formulating the tree-approximation as a smooth optimization is innovative. The use of a log-sum-exp surrogate for hyperbolicity to make it differentiable for enabling gradient descent is an elegant idea. Unlike previous heuristics, this approach provides a framework that directly ties the distortion objective to a geometric measure (hyperbolicity). \n\n\n2) The experimental results (as provided by the author(s) substantiate the claims. DELTAZERO consistently outperforms the standard algorithms currently in practice.\n\n\n3) It does have some diverse and important future work potential.\n\n\nWeakness:\n\n1) Proposition 3.4 states that $\\delta(D)$ is piecewise-affine but non-convex, so the smoothed surrogate remains non-convex. As a result, gradient descent may get stuck in local minima. The paper does not discuss initialization or how sensitive the results are to local optima. It uses ADAM and early stopping, but there is no guarantee the global optimum of the metric loss is found. \n\n\n2) The method introduces several hyperparameters (batch size $m$, number of batches $K$, smoothing $\\lambda$, tradeoff $\\mu$, learning rate, etc.) Tuning these is nontrivial. The paper uses grid-search to find the best settings for each dataset. It is unclear how performance goes down if these are not optimally tuned. This reliance on manual hyperparameter search may lead to some limitations. Additionally, the condition in Theorem 3.1 for improved distortion ($\\mu\\geq 1/(2\\log(n-2))$) may not be satisfied in practice, and its role is not deeply discussed.\n\n\n3) While the method is compared against several baselines, the discussion of limitations of existing methods is brief. For instance, it is claimed that NJ, TREEREP, etc., “lack theoretical guarantees”. which is true for worst-case distortion but somewhat overstated in practical terms. Also, some baselines (like HCCROOTEDTREEFIT) depend heavily on root choice, but no analysis is given on how robust DELTAZERO is to analogous choices (e.g. the choice of basepoint $w$ in the final embedding). The “classical GROMOV” method mentioned is not fully explained in the main text (only in an appendix), making it unclear whether comparisons are fully fair.\n\n\n4) The paper states that the surrogate metric is “eventually embedded into an actual tree” and mentions single-linkage clustering. However, details on the final embedding step (and its complexity) are omitted.This part invokes a variant of Gromov’s algorithm, but this area is only briefly sketched.\n\n\n5) Though the current best known bound for computing Gromov hyperbolicity (which is $n^{3.69}$) is beaten, still each projected gradient step requires an $O(n^3)$ Floyd–Warshall projection to enforce triangle inequalities. While mini-batching reduces the cost of hyperbolicity estimation, “scalability to very large graphs” is still constrained by the cubic projection cost.\n\n\n6) In some cases the improvements are small. For example, on the CORA graph DELTAZERO’s worst-case distortion (7.59) is only slightly better than the second-best (7.76 by LayeringTree), a 2.3% gain. This suggests that when the input metric is already very hyperbolic (small diameter relative to $n$), room for improvement might be limited. Also, In grid-like graph cases DELTAZERO is outperformed by LAYERINGTREE. The variability across datasets hints that in some regimes  the benefit may not be substantial.", "was_revised": true, "final_justification": "I am not convinced about the practicality of their approach and will therefore stick to my original score.", "rebuttal": "## Responses to weaknesses\n\n1. You are absolutely right, since our optimization problem is non‑convex, we cannot guarantee convergence to a global minimum. As shown in the paper (Algorithm 1) we always initialize with the original distance matrix, which is a theoretically motivated choice. Specifically, Theorem 3.1 ensures that if we could successfully minimize the distortion and Gromov hyperbolicity, the resulting tree metric will have a better distortion bound than the one obtained by directly applying the Gromov embedding.\n\n   Moreover, we empirically observe that our method produces consistent results across multiple runs, with only minor variations due to batch sampling. It is striking to notice that, in Table 1 and among all competitors, we have most of the time the lowest deviations observed across run.\n\n2. We thank the reviewer for highlighting this important aspect. In Appendix D.2 of our submission (Figure 10), we provide a sensitivity analysis of the hyperparameters on the C-ELEGAN dataset. This analysis examines the impact of varying each parameter, namely $\\mu$, $\\lambda$ and K, individually, while keeping the others fixed at the values found through grid search. Our findings show that DELTAZERO exhibits stable performance under moderate deviations from the optimal settings, alleviating the concern that the method is overly sensitive to precise hyperparameter tuning.\n\n    The parameter $\\mu$ is a chosen parameter that balances fidelity to the original metric against tree-likeness. Theorem 3.1 provides a theoretical condition on $\\mu$, namely, $\\mu \\geq \\frac{1}{2} \\log(n-2)$ , under which, in the ideal case (i.e., if we were able to minimize both the $\\ell\\_\\infty$ norm and Gromov hyperbolicity), the resulting tree embedding would guarantee a lower worst-case distortion than the classical Gromov embedding. \n\n    In practice **we do not have to enforce this constraint** strictly, since our optimization is performed over smooth surrogates of both objectives. Instead, $\\mu$ is treated as a tunable hyperparameter, and its value is selected through grid search to empirically optimize distortion. We found that values below the theoretical threshold can still perform well in practice due to the regularizing effect of the smooth approximation.\n\n3. Thank you for these thoughtful remarks. We agree that the practical performance of heuristic methods like NJ and TreeRep is often strong, and our statement about their lack of theoretical guarantees could have been more precisely worded. What we intended to emphasize is that, to the best of our knowledge, **these methods do not offer provable worst-case distortion bounds** of the kind established in Theorem 3.1 of our paper. \nThat said, we acknowledge their practical utility and will revise our discussion to more accurately reflect their strengths. \n\n    For DeltaZero, the choice of basepoint only comes into play **after the optimization procedure**: we first optimize the distance matrix, and then apply the Gromov embedding to the optimized metric using 100 randomly selected basepoints. The reported average distortion is computed by averaging over these 100 embeddings (row 292/293). For fairness, we use the same set of 100 roots across all methods that require a basepoint (e.g., DELTAZERO, HCCRootedTreeFit, and Classical Gromov). This ensures a consistent and unbiased comparison, and helps reduce variability due to basepoint selection. We propose to add a discussion about this point in the revised version of the manuscript. We will also include more details about the Gromov-embedding procedure.\n\n4. Thank you for pointing this out. We provided a more complete description in Appendix B, but we are happy to clarify it here. The Gromov embedding algorithm transforms a metric space into a tree metric using Gromov products with respect to a fixed base point $w$. For each pair $(x, y)$, it computes the Gromov product: \n    $$(x|y)\\_w = \\frac{1}{2} \\bigl[d(x, w) + d(y, w) - d(x, y)\\bigr],$$ \n    then defines a transformed metric:\n    $$d\\_G(x, y) = m - (x|y)\\_w,$$ \n    where $m = \\max_{x \\in X} d(x, w)$. This transformation is designed to encode ultrametric structure. Next, it uses single-linkage hierarchical clustering (SLHC) on $d_G$ to obtain an ultrametric $u_X$. The final tree metric is then recovered by inverting the transformation: $$d_T(x, y) = m - u_X(x, y).$$\n    The complexity is $O(n^2)$ as mentioned in row 140. We will clarify this in the main text.\n    \n5. You are absolutely right: our method has a complexity of $O(n^3)$, which makes it impractical for very large graphs. We would like to comment on few aspects:\n    - We operate in the space of $n \\times n$ distance matrices, meaning the per-step projection, though cubic, is not disproportionate relative to the size of the object being optimized ($n^2$ entries).\n    - Several methods have been proposed to solve metric nearness (e.g. [1,2,3]), often relying on iterative procedures. While these methods may have lower theoretical complexity than Floyd–Warshall, they tend to be slower in practice. This is because Floyd–Warshall, despite its $O(n^3)$ complexity, can be efficiently parallelized on GPUs, offering significant practical speed-ups over iterative alternatives.\n    - While being more computationally demanding than all competitors, it outperform baseline methods in terms of worst-case distortion, which is the central objective of our framework. It then provide a deliberate trade-off between computational cost and quality of approximation. \n    - Many well-established methods in machine learning have similar complexities. It is nevertheless true that we still have room for improvement regarding the implementation of DeltaZero to make it run faster.\n    - Lastly, to further improve scalability, a promising and natural direction we are exploring is to optimize over point embeddings in hyperbolic space instead of distance matrices. This would enforce metric validity by construction and eliminate the need for explicit projection steps, leveraging the efficiency of geometric optimization in continuous spaces. \n\n    We firmly believe that this paper would constitute the first necessary cornerstone before exploring variants and optimized implementations for algorithms based on the idea of optimizing hyperbolicity.  \n\n6. In our experiments on real datasets, we report the gains over the second-best competitor. Those gains are always positive, meaning that we are **consistently** better than the competitors. We concur that there are regimes where this gain might be limited, but using DeltaZero systematically proved to be benefitial. \n\n[1] \"The metric nearness problem.\" SIAM Journal on Matrix Analysis and Applications, 2008.\n\n[2] \"Metric nearness made practical.\" AAAI, 2023.\n\n[3] \"If it ain't broke, don't fix it: Sparse metric repair\". IEEE, 2017.\n     \n## Responses to questions\n\n>Please explain the choice of parameters.\n\nThe parameters in our method fall into three main categories:\n\n- Optimization parameters (e.g., learning rate, number of epochs, batch size): These were chosen using standard practices. The learning rate was selected via grid search from a fixed set of candidates.\n  \n- Smoothing parameters (e.g., $\\lambda$ in the log-sum-exp approximation): These control the smoothness of the surrogate for the max/min operations in the Gromov hyperbolicity. We selected these via grid search to balance approximation accuracy and numerical stability.\n\n- Trade-off parameter $\\mu$: This parameter balances fidelity to the original metric (measured via $\\ell_\\infty$ norm) and tree-likeness (measured via smooth Gromov hyperbolicity). Theoretical guidance from Theorem 3.1 suggests setting $\\mu ≥ 1/2 \\log(n - 2)$ for worst-case distortion guarantees, but in practice we treated μ as a tunable hyperparameter and selected it via grid search. This choice reflects the fact that we optimize smooth surrogates rather than the exact hard constraints.\n\n    To ensure fairness and robustness, we applied the same grid search strategy for all datasets and reported the best-performing configuration for each case. Additionally, we include a sensitivity analysis in Appendix D.2, which shows that performance is generally stable across a reasonable range of hyperparameter values. \n    \n>How do you ensure $\\mu ≥ 1/2 \\log(n - 2)$ the criterion holds?\n\nWe believe we addressed this point in our response above.\n\n>How do you tackle the non-convexity of Gromov hyperbolicity $\\delta_D$ ?\n\nWe believe we addressed this point in our response above."}, {"review_id": "zMx4eWVREt", "reviewer": "Reviewer_FcsZ", "summary": "This paper is motivated by the problem of finding a tree metric space embedding of a given arbitrary finite metric space that preserves the original pairwise distances. To this end, the authors propose an algorithm that consists of two major steps: 1) finding a surrogate finite metric space that best preserves the original distance and meanwhile has as close to a tree structure as possible; 2) embedding this surrogate into an actual tree using the existing Gromov’s tree embedding. The main contribution is in the first step. \"preserving the original distances\" is enforced by $l^\\infty$ norm (in implementation $l^2$ norm is used for smoothness) and closeness to a tree is measured by Gromov hyperbolicity, which is not smooth by the min and max function in the definition. The authors formulate this problem as a constrained optimization problem with an objective as a balanced sum of these two loss components, where the Gromov hyperbolicity is replaced by a smooth version using the log-sum-exp operator and minibatch to alleviate the computation burden. Then the loss is differentiable and the optimization can be solved using projected gradient descent. The experiments show the benefit of this method in hierarchical clustering, and the quality of the embedding itself.", "questions": "1. In the batch sampling, the author mentioned the K subsets need to be independent, can you clarify what the independence here means? In Algorithm 1, the sampling seems just to be random, how is the independence enforced?\n2. Can the authors explain what the blue vertices in the optimized tree of DeltaZero denote? Based on my understanding, the method preserves the number of points as the original input. I wonder why it would give rise to additional nodes.\n3. Can the authors provide more discussion on why as all equivalent norms, minimizing the $l^2$ norm would yield better $l^\\infty$ distortion but worse $l^1$ distortion? Also, how does using $l^2$ norm in implementations affect Theorem 3.1, if not, why don't you use $l^2$ norm in Equation (3) from the start?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. This paper is well motivated. The embedding of an arbitrary metric into a tree is an interesting problem that is important in revealing the hierarchical structures of data, enabling fast tree algorithms, etc.\n2. It reads very well, and I love that the authors care to give intuitive explanations to definitions, algorithms.\n3. The smoothed version of Gromov hyperbolicity is novel.\n4. Theoretical bounds are given for each approximation step of the Gromov hyperbolicity. The authors also provide critical analysis of the bounds, e.g. the restrictiveness of the assumptions. \n5. Experiments show significantly improved accuracy of hierarchical clustering in synthetic data, and superior quality of the tree embedding of the proposed method over baselines. Sensitivity analysis is provided for better understanding of the parameters.\n\n\nWeaknesses:\n1. Although the optimization scheme may provide better worst-case bounds that give theoretical guarantees, in real-world applications the average-case bound is more relevant, and as shown in Table 2, the proposed method is not doing well.\n2. Even after applying the batched approximation to reduce the computation complexity, the proposed algorithm takes ten to a hundred times longer than the baselines (Table 3). This hinders the application in large-scale data.\n3. It would be better if the authors could show the applications such as hierarchical clustering in real datasets. But the experiments are sufficient in their current form.", "was_revised": false, "final_justification": "", "rebuttal": "## Reponses to weaknesses\n\n>Even after applying the batched approximation to reduce the computation complexity, the proposed algorithm takes ten to a hundred times longer than the baselines (Table 3). This hinders the application in large-scale data.\n\nYou are absolutely right: our method has a complexity of $O(n^3)$, which makes it impractical for very large graphs. We would like to comment on few aspects:\n- We operate in the space of $n \\times n$ distance matrices, meaning the per-step projection, though cubic, is not disproportionate relative to the size of the object being optimized ($n^2$ entries).\n- Several methods have been proposed to solve metric nearness (e.g. [1,2,3]), often relying on iterative procedures. While these methods may have lower theoretical complexity than Floyd–Warshall, they tend to be slower in practice. This is because Floyd–Warshall, despite its $O(n^3)$ complexity, can be efficiently parallelized on GPUs, offering significant practical speed-ups over iterative alternatives.\n- While being more computationally demanding than all competitors, it outperform baseline methods in terms of worst-case distortion, which is the central objective of our framework. It then provide a deliberate trade-off between computational cost and quality of approximation. \n- Many well-established methods in machine learning have similar complexities. It is nevertheless true that we still have room for improvement regarding the implementation of DeltaZero to make it run faster.\n- Lastly, to further improve scalability, a promising and natural direction we are exploring is to optimize over point embeddings in hyperbolic space instead of distance matrices. This would enforce metric validity by construction and eliminate the need for explicit projection steps, leveraging the efficiency of geometric optimization in continuous spaces. \n\nWe firmly believe that this paper would constitute the first necessary cornerstone before exploring variants and optimized implementations for algorithms based on the idea of optimizing hyperbolicity.  \n\n>It would be better if the authors could show the applications such as hierarchical clustering in real datasets. But the experiments are sufficient in their current form.\n\nThank you for the suggestion. Exploring applications of our method on real-world hierarchical clustering tasks is indeed a direction we intend to pursue in future work. While our current focus was on controlled synthetic settings to clearly demonstrate the benefits of our optimization strategy, we believe that extending the method to practical use cases, such as biological taxonomies, document hierarchies, or social networks, is both promising and feasible. We see this as a natural continuation of the present work.\n\n[1] \"The metric nearness problem.\" SIAM Journal on Matrix Analysis and Applications, 2008.\n\n[2] \"Metric nearness made practical.\" AAAI, 2023.\n\n[3] \"If it ain't broke, don't fix it: Sparse metric repair\". IEEE, 2017.\n\n## Responses to questions\n\n>In the batch sampling, the author mentioned the K subsets need to be independent, can you clarify what the independence here means? In Algorithm 1, the sampling seems just to be random, how is the independence enforced?\n\nIn our setting, “independent” refers to the way batches are sampled during optimization:\n\n- Across batches: Each batch is sampled independently from the full dataset, meaning there is no dependence in how one batch affects the selection of the next.\n- Within a batch: Points are sampled without replacement, so each batch contains unique points (no duplicates within a batch).\n- Between batches: There is no enforced disjointness across batches, some overlap may occur, but the sampling process itself is statistically independent. \n    \nWe will clarify this in the final version to avoid ambiguity. Thank you for pointing this out.\n\n>Can the authors explain what the blue vertices in the optimized tree of DeltaZero denote? Based on my understanding, the method preserves the number of points as the original input. I wonder why it would give rise to additional nodes.\n\nThe blue nodes represent additional points introduced by the Gromov embedding at the end of our optimization procedure. Although our method optimizes a metric over the original set of $n$ points, the final tree produced by the Gromov embedding of the optimized distance may include extra internal nodes in order to faithfully approximate the pairwise distances. This is a standard feature of Gromov’s construction: to embed a triplet of points $(x, y, w)$ into a tree, the algorithm may introduce an intermediate node $s$ located at distance $(x|y)_w$ from the base point $w$. This construction is illustrated in Figure 6 of the paper, where a three-point configuration is embedded into a tree with four nodes.\n\n>Can the authors provide more discussion on why, although all norms are equivalent in finite dimension, minimizing the $\\ell\\_2$ norm would yield better $\\ell\\_\\infty$ distortion but worse $\\ell\\_1$ distortion? \n\nThis is an excellent question. Our choice of the squared $\\ell_2$ norm stems from its smoothness and differentiability, which make it more amenable to gradient-based optimization. Moreover, among common $p$-norms, $\\lVert x\\rVert\\_2$ provides a good balance. It is closer to $\\lVert x\\rVert\\_\\infty$ than $\\lVert x\\rVert\\_1$, as captured by the classical inequality in finite dimensional spaces:\n$$\n\\lVert x\\rVert\\_{\\infty} \\leq \\lVert x\\rVert\\_2 \\leq \\lVert x\\rVert\\_1,\n$$ \nThis inequality highlights that minimizing the $\\ell_2$ norm offers no direct control over the $\\ell\\_1$ norm, which can result, during optimization, in lower $\\ell\\_\\infty$ distortion but higher $\\ell_1$ distortion.\n\n>Also, how does using the $\\ell_2$ norm in implementations affect Theorem 3.1? If it does not, why don't you use the $\\ell_2$ norm in Equation (3) from the start?\n\nImportantly, Theorem 3.1 is derived from the classical Gromov tree approximation theorem (Theorem 2.3), which is fundamentally stated in terms of the $\\ell_\\infty$ norm. Consequently, the worst-case distortion guarantee in Theorem 3.1 holds only when distortion is measured using the $\\ell_\\infty$ norm. An interesting direction for future work would be to explore whether variants of the Gromov tree approximation theorem could be formulated under $\\ell_p$ norms.\n\nIt is worth noting that, in principle, we could have used a smoothed approximation of the $\\ell_\\infty$ norm using the same log-sum-exp technique employed for the Gromov hyperbolicity. However, in our experiments, this alternative resulted in poorer optimization behavior and less stable outcomes. This observation further supports our use of the squared $\\ell_2$ norm."}, {"review_id": "FJXI5FPSdO", "reviewer": "Reviewer_XSQu", "summary": "This paper proposes a tree metric learning method based on Gromov hyperbolicity. The authors begin by formulating the problem as minimum distortion tree metric approximation under the $\\ell_\\infty$ norm. Then, they introduce a smooth relaxation using the log-sum-exp function, along with a batched version of Gromov hyperbolicity for differentiable and efficient computation. The method is evaluated on five unweighted graph datasets and two non-graph metric datasets, with results reported in terms of $\\ell_\\infty$ error.", "questions": "- Mean Average Precision (MAP) is a widely used evaluation metric in representation learning, especially for measuring tree and hyperbolic embedding quality. Could you report the MAP performance of your method compared to baselines?\n- What are the δ-hyperbolicity or Gromov hyperbolicity values of the datasets used in your experiments? This would help contextualize how suitable these datasets are for tree-based representations.\n- In Table 1, the LayeringTree method has missing entries (marked as “–”) for the ZEISEL and IBD datasets. Could you explain why these results are not reported?\n- Are there any assumptions made about how data points are mapped to the tree? For instance, are points always assumed to be the leaves of the tree, or can they also include internal nodes?\n- Is the resulting tree and its associated tree metric unique, given a distance matrix, or is the solution dependent on initialization or optimization variability?\n- Beyond distance approximation, do you see your method being applicable to standard graph representation tasks such as node classification or link prediction? If so, how might your approach contribute to improved performance in those settings?", "limitations": "The author discuss the scalability issue for the proposed method in Section 5.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strength\n\nTree and tree metric learning is a specific form of hierarchical representation learning, which plays an important role in many machine learning tasks, especially given the prevalence of hierarchical structure in real-world data. The problem addressed in this paper is relevant to both the representation learning and hyperbolic geometry communities. The paper is clearly written and easy to follow. A key strength is the theoretical guarantee provided in Theorem 3.3, which shows that the proposed batched formulation asymptotically approximates Gromov hyperbolicity. I believe the theoretical contribution is solid and should be appreciated.\n \n## Weakness\n- In the formulation of the Minimum Distortion Tree Metric Approximation problem (line 35), the choice of using the $\\|\\|\\cdot||\\_\\infty$  norm is not clearly justified. Many hyperbolic representation learning methods measure distortion using average distortion rather than worst-case. Since the proposed differentiable approximation of Gromov hyperbolicity is built upon the $\\|\\|\\cdot||\\_\\infty$ norm, it would be important to explain why alternative norms (e.g., average distortion) are not suitable or less appropriate for this setting.\n- The Gromov tree embedding referenced in Theorem 3.1 is not defined. Specifically, the construction of the mapping Φ is not described, which makes it difficult to follow the basis of the theorem.\n- The optimization problem in Equation 3 and the Minimum Distortion Tree Metric Approximation problem (line 35) are based on the $\\|\\|\\cdot||\\_\\infty$  norm, which motivates the use of a smooth relaxation due to the max and min operations. However, the final optimization objective in Equation 6 switches to using $\\|\\|\\cdot||\\_2\\^2$, and the paper does not clarify this shift. If the initial motivation was centered around $\\|\\|\\cdot||\\_\\infty$, the rationale for optimizing under a different norm should be made explicit.\n- In Table 2, the $\\ell_1$ average error is reported, but this metric is not formally defined in the paper. Moreover, based on this metric, the NJ method performs best and significantly outperforms the proposed method. Although NJ does not guarantee low worst-case distortion, the paper would benefit from a discussion or example where minimizing worst-case distortion (as targeted by the proposed method) is practically important.\n- While the proposed approach focuses on tree metric learning, it is based on hyperbolicity, and the paper does not engage with related work in hyperbolic representation learning. Some prior methods also construct trees using hyperbolic space, and some prior hyperbolic representation learning methods can be trained in a differentiable manner. A discussion of these approaches and a comparison with relevant baselines would strengthen the paper and better position its contributions within the broader literature.", "was_revised": true, "final_justification": "During the rebuttal and discussion period, the authors addressed my comments. I believe the work is important for tree metric learning and hierarchical representation communities.. The theoretical analysis is sound (Theorem 3.3), and should be appreciated. Therefore, I lean towards accepting the paper.", "rebuttal": "## Responses to weaknesses\n\n1. Several works have investigated the metric nearness problem under the $\\ell_\\infty$ norm (e.g., [1,2,3,4]). Our choice is also motivated by Gromov’s theory of hyperbolicity, where the embedding theorem (Theorem 2.3 in our paper) is naturally formulated in terms of the $\\ell_\\infty$ norm. This makes $\\ell_\\infty$ the most consistent choice for linking distortion to guarantees linked to Gromov hyperbolicity. That said, we recognize the importance of alternative formulations in particular, Tree Metric Approximation under $\\ell_p$ norms.\n   Our experiments suggest that using $\\ell_2$ also leads to very good distorsion for $\\ell_\\infty$ norm.\n\n2. Thank you for pointing this out. Appendix B provides full details; here is a concise summary.  \nThe Gromov embedding converts the input metric $d$ into\n$d\\_G(x,y)=m-(x|y)\\_w$, where $m=\\max_{x} d(x,w)$.  \nWe then apply SLHC on $d_G$ to obtain an ultrametric\n$u_X$, and map back via $d_T(x,y)=m-u_X(x,y)$.  \nThe whole procedure costs $O(n^2)$ (see row 140). We will clarify this in the\nmain text.\n\n3. This is an excellent question. Our choice of the squared $\\ell_2$ norm stems from its smoothness and differentiability, which make it more amenable to gradient-based optimization. Moreover, among common $p$-norms, $\\lVert x\\rVert\\_2$ provides a good balance. It is closer to $\\lVert x\\rVert\\_\\infty$ than $\\lVert x\\rVert\\_1$, as captured by the classical inequality in finite dimensional spaces:\n$$\n\\lVert x\\rVert_{\\infty} \\leq \\lVert x\\rVert_2 \\leq \\lVert x\\rVert_1,\n$$ \nThis inequality highlights that minimizing the $\\ell_2$ norm offers no direct control over the $\\ell_1$ norm, which can result, during optimization, in lower $\\ell_\\infty$ distortion but higher $\\ell_1$ distortion.\n\n   Importantly, Theorem 3.1 is derived from the classical Gromov tree approximation theorem (Theorem 2.3), which is fundamentally stated in terms of the $\\ell_\\infty$ norm. Consequently, the worst-case distortion guarantee in Theorem 3.1 holds only when distortion is measured using the $\\ell_\\infty$ norm. An interesting direction for future work would be to explore whether variants of the Gromov tree approximation theorem could be formulated under $\\ell_p$ norms.\n\n   It is worth noting that, in principle, we could have used a smoothed approximation of the $\\ell_\\infty$ norm using the same log-sum-exp technique employed for the Gromov hyperbolicity. However, in our experiments, this alternative resulted in poorer optimization behavior and less stable outcomes. This observation further supports our use of the squared $\\ell_2$ norm.\n\n4. Thank you for raising this important point. We will add a formal definition of mean $\\ell_1$ distortion (the average absolute error over all pairwise distances between the original and tree metrics). Although NJ performs well on this average error, it offers no control over the worst‑case distortion. Our method explicitly targets the $\\ell_\\infty$ norm, crucial when\n\n   - a single long edge can reshape a dendrogram,\n\n   - a bad estimate makes a network route unacceptably long, or\n\n   - one large error dominates a hierarchy’s visual interpretation.\n    \n   We see our approach as complementary to NJ and other heuristics: while they perform well on average, they do not optimize or provide guarantees on the worst-case error.\n\n5. We appreciate this observation and agree that our work could benefit from deeper engagement with the literature on hyperbolic representation learning. However, let us point **major differences between our work and hyperbolic embedding approaches**. Our method is rooted in Gromov hyperbolicity, a geometric property of metric spaces, and focuses on producing tree metrics. Related works in hyperbolic embeddings (e.g., Nickel & Kiela, 2017; Chamberlain et al., 2017) also aim to capture hierarchical structure, albeit from a different modeling perspective, generally based on contrastive losses that preserve relationships. In contrast, we operate directly on pairwise distances and focus on learning a surrogate metric that can be explicitly embedded into a tree with worst-case distortion guarantees. This metric-centric view differs from position/relation-based hyperbolic embeddings, but we see them as highly complementary. As we have noted in earlier responses, a promising direction for future work would be to optimize over point embeddings in hyperbolic space instead of full distance matrices. This could eliminate the need for explicit metric projection (via Floyd–Warshall) and would allow our method to tap into the rich literature and tools developed in the hyperbolic representation learning community.\n\n[1] \"The metric nearness problem.\" SIAM Journal on Matrix Analysis and Applications, 2008.\n\n[2] \"Metric nearness made practical.\" AAAI, 2023.\n\n[3] \"Improved Error Bounds for Tree Representations of Metric Spaces.\" NIPS, 2016.\n\n[4] \"UltraTWD: Optimizing Ultrametric Trees for Tree-Wasserstein Distance.\" ICML, 2025.\n\n\n## Responses to questions\n\n1. We thank the reviewer for this question, which echoes our previous answer on the relations with hyperbolic embedding approaches. In this specific context, where one aims at embedding graphs or trees in hyperbolic spaces, the MAP is a meaningful metric which measures how the relationships between neighbors is locally preserved through the embedding in a specific target space. **Recalling our objective is to find a tree which metric preserves at best a given input arbitrary metric**, we argue that the MAP does not necessarily measure the efficiency of our method nor the competitors for the following reasons:\n   - MAP does not measure how distances are preserved through the embedding (e.g. scaling uniformly the distances would yield the same MAP); It is only relevant on the preservation of local neighboring relations, and one could have simultaneously an arbitrary bad distortion with a perfect MAP score;  \n   - An optimal tree, in the sense of our problem, can have a significantly different neighboring structure than an original graph (e.g. embedding a grid into a tree, which is an extreme case, illustrated in Figure 5 in the appendices);   \n   - The embedding space should be the same for all the methods for the MAP score to be meaningful. Here, our methods and the competitors ones are embedding a metric into different tree structures (i.e. different spaces). As such, we can not directly compare the scores, as the target embedding spaces are different.  \n\n   For those reasons, we decided to not compute the MAP score as demanded by the reviewer.  Nonetheless, if the reviewer still believes it can be a relevant metric to compare the methods, or at least give some insights, we will be happy to provide those scores.  \n\n2. We computed the hyperbolicity using the implementation provided in the SageMath library.\n\n   | Dataset  | Gromov hyperbolicity |\n   | -------- | ------ |\n   | C-ELEGAN | 1.5    |\n   | CS PHD   | 6.5    |\n   | CORA     | 4     |\n   | AIRPORT  | 1     |\n   | WIKI     | 2.5       |\n   | ZEISEL   |      0.19  |\n   | IBD      |  0.41      |\n\n3. Thank you for the question. As briefly noted in line 287, the LayeringTree method is designed specifically for unweighted graphs and is not applicable to general metric datasets, such as ZEISEL and IBD. These datasets are based on pairwise dissimilarities derived from high-dimensional feature spaces and do not correspond to unweighted graphs with unit-length edges. As a result, LayeringTree cannot be applied in those settings, which explains the missing entries in Table 1.\n\n4. We thank the reviewer for their question. There is indeed no assumption imposed on how data points are mapped to the tree. As illustrated in the visualizations provided in Figure 5, this mapping varies across methods:\n   - For example, HCC and NJ map all data points to the leaves of the constructed tree, which is standard for agglomerative methods.\n\n   - In contrast, our \"Gromov embedding\" approach allows data points to be mapped to internal nodes when this better captures the underlying geometry of the original space under the tree metric constraint (see Figure 6 for an example).\n\n5. Empirically, we observe that our method produces consistent results across multiple runs, with only minor variations due to batch sampling. These variations have a limited impact on the final distortion, suggesting that our optimization is relatively stable in practice.\n\n6. This is an excellent question. While our primary focus is on distance approximation, we believe our method has strong potential for standard graph‑representation tasks.\n\n   Our approach yields a surrogate distance metric that captures global and hierarchical structure in a differentiable, geometry‑aware manner. This enriched structural signal could be leveraged to produce high‑quality node embeddings, for instance, by embedding our optimized metric into hyperbolic spaces, or by providing it as input to downstream neural models.\n\n   In node classification, the tree‑like structure induced by our method may reflect latent class hierarchies or community structure. This intuition is supported by our experiments on stochastic block models (SBMs), where DELTAZERO helps to accurately recovers the underlying communities.\n\n   Furthermore, our method can be integrated as a pre‑processing step or regularizer in graph neural networks (GNNs), providing additional structural bias. This is especially relevant for addressing the well‑known over‑squashing phenomenon. Since Gromov hyperbolicity is tied to negative sectional curvature and over‑squashing has been linked to negative Ollivier–Ricci curvature [1], our framework offers a principled avenue to investigate, and potentially mitigate, such effects.\n\n   Exploring these directions is part of our ongoing and future work.\n\n[1] \"Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature.\" ICML 2023."}]

Author rebuttal:

Meta-review: This paper introduces DeltaZero, which optimizes deviations from a tree metric through a smooth differntiable surrogate of Gromov's delta-hyperbolicity. Experiments on several graph datasets shows that DeltaZero consistently improves over baseline embedding algorithms. After the review and discussion phase, all reviewers provide recommendations above the acceptance threshold (5, 4, 4, 4). The reviewers find the approach novel and well motivated, while the paper is also clearly presented. There were also multiple concerns, shared by (nearly) all reviewers. Notable are the concerns regarding computational complexity, convergence, and choice of norms (specifically, Linf). The authors provide a clear and elaborate rebuttal, agreeing on the computational complexity and motivating the choice of norms. The AC agrees with the reviewers that these issues remain an open question, especially when it comes to large-scale real-world settings. However, the paper has sufficient novelty and empirical impact to warrant acceptance. The AC follows the reviewer recommendations and votes for acceptance.
Decision: Accept (poster)