Source-linked AI summary
A quantitative tree-likeness bound from average hyperbolicity
Joon-Hyeok Yim
TL;DR
Average hyperbolicity gives a qualitative guarantee of tree approximation, but the prior result did not provide useful quantitative bounds. This paper uses a direct probabilistic construction to obtain an explicit cube-root rate, while discussing the gap to the square-root scale and connections to ultrametric fitting.
Problem
The optimal dependence of tree approximation error on average hyperbolicity and the similarity range remains unsettled.
Source: §5 · p. 10Method
Results
With b = 1, Tree(s) = O(Hyp(s)^(1/3)); the discussion also rules out a universal bound with exponent greater than 1/2.
Source: §1 · p. 2, §5 · p. 11Takeaways & Limitations
The formulation connects direct mean-error control to hierarchical correlation clustering and ultrametric fitting under ℓ1 objectives.
Source: §1 · p. 2Whether adapting threshold levels and pivot sampling for finite inputs can improve the bounds remains open.
Source: §5 · p. 12
Abstract
from arXiv · showhide
Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemer\'edi's regularity lemma and does not yield explicit quantitative bounds. Here, we establish a tighter relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that $$\operatorname{Tree}(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \operatorname{Hyp}(s)} \leq 2.8512 \sqrt[3]{b^2 \operatorname{Hyp}(s)}.$$ The proof uses a simple pivoting construction inspired by \KwikCluster. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.
1. Introduction
This paper turns a qualitative connection between average hyperbolicity and tree approximation into an explicit rate for bounded similarities. It also places the problem in the context of metric tree-likeness and ultrametric fitting.
1. Introduction
- Gromov hyperbolicity measures tree-likeness: a geodesic metric space embeds isometrically in a real tree exactly when it is 0-hyperbolic.For similarity functions, average hyperbolicity measures expected violations of a three-point inequality, while tree-likeness is least mean approximation error.Source: §1 · p. 1
- Chatterjee and Sloman [5] established a qualitative guarantee but used a weighted regularity lemma, prompting the question of useful quantitative bounds without that proof tool.Their result applies to infinite spaces and nonuniform probability measures.Source: §1 · p. 1
- After normalizing b = 1, the tree approximation error is O(Hyp(s)^(1/3)), with an explicit rate that does not depend on the space’s cardinality.The rate depends on Hyp(s) and the similarity bound b.Source: §1 · p. 2
- Ultrametric fitting can be framed through threshold clustering, where consistency across thresholds is needed for a rooted-tree representation.The paper instead seeks to control mean approximation error directly from average hyperbolicity.Source: §1 · p. 2
2. Preliminaries
The preliminaries specify the probability-space setting, compatible tree representations, and how the approximation framework relates to ultrametric fitting. They also state a measurability condition needed for the tree quantities to be well-defined.
2. Preliminaries
- The framework assumes a symmetric measurable similarity s taking values in [0, b] on a countably generated probability space, which may have atoms.The average-hyperbolicity expression uses independent samples from the underlying measure.Source: §2 · p. 2
- A compatible rooted tree has leaf set S, finitely many internal vertices, and measurable descendant-leaf sets; its Gromov product records shared path length from the root.The product map must also be measurable.Source: §2 · p. 2
- Countable generation alone does not guarantee measurable Gromov products; the diagonal of S × S must also be measurable.The paper notes that standard Borel spaces satisfy this additional assumption.Source: §2 · p. 2
- The weighted-tree formulation has the same infimum as Chatterjee and Sloman’s unweighted-tree formulation with a global scaling factor.The paper establishes this by approximating weighted edge lengths with scaled, subdivided unweighted edges.Source: §2 · p. 3
- For finite metric spaces, Tree(s) measures the optimal mean ℓ1 error when approximating the distance by an ultrametric.The similarity is s(x, y) = b − d(x, y), and a fitted tree similarity yields the corresponding leaf-to-leaf ultrametric.Source: §2 · p. 3
3. The Pivot Construction
The pivot construction builds a hierarchy from threshold relations using one shared ordered sample of pivots. It refines pivot assignments across levels so that the resulting classes define a compatible rooted tree.
3. The Pivot Construction
- One ordered sample of pivots is reused at every threshold, and each point joins its first neighboring pivot at that level.The shared sample allows assignments to be tracked across levels.Source: §3 · p. 4
- The raw pivot-assignment relations need not be nested, so the construction refines them to ensure every higher-level class lies inside a class at the preceding level.The resulting nested classes form the hierarchy.Source: §3 · pp. 4–5
- Each nonempty class becomes an internal vertex connected to its containing class; points attach to their deepest active class, producing a finite compatible tree.Edges between levels have length h, and leaf edges have length ε.Source: §3 · p. 5
- The error analysis balances threshold mesh size against the expected pivot count, controlling discretization, accumulated disagreements, and uncovered pairs.Bad-triangle density integrated across thresholds equals average hyperbolicity; parameter choices yield the cube-root bound.Source: §3 · p. 5
4. Quantitative Bounds
The section constructs compatible tree approximations from shared pivot assignments and bounds their expected error. It connects the approximation analysis to average hyperbolicity through threshold bad-triangle densities.
4. Quantitative Bounds
- The construction reuses the same ordered pivots at every threshold, then hierarchically refines their assignments into nested relations K_j.Each point is assigned to its first neighboring pivot, if any.Source: §4 · p. 5, Figure 1 · p. 6
- The disagreement analysis separates false positives, false negatives caused by a separating pivot, and false negatives where both points remain unassigned.These are the three cases illustrated in Figure 2.Source: Figure 2 · p. 7, §4 · pp. 7–8
- Theorem 4.3 bounds expected tree-approximation error by h + λh(2L + 1), where L = floor(b/h), for a random compatible rooted tree.The mesh size h and expected pivot count λ expose the parameters of the bound.Source: §4 · p. 9
- For mesh size h, the sum of threshold bad-triangle densities is at most Hyp(s)/h, linking the pivot-disagreement analysis to average hyperbolicity.The bad-triangle event is a pair below threshold t whose two links to a third point are at least t.Source: §4 · pp. 6, 9
- The tree approximation also gives an ultrametric-fitting result by setting s = M − d for a uniformly distributed finite metric space.The ultrametric is defined from the tree similarity by d_U(x, y) = M − s_T(x, y) off the diagonal.Source: §4 · p. 10
- For finite data, removing repeated pivots yields a directly samplable ordered list, and clustering and refinement take polynomial time regardless of λ.The construction uses at most n pivots and at most n + 1 relevant similarity levels.Source: §4 · p. 10
5. Discussion
The discussion shows that the upper-bound exponent may not be optimal: a constructed family forces square-root-scale error, leaving a gap between exponents 1/3 and 1/2. It also compares the bound with ultrametric fitting guarantees and identifies open issues for finite inputs and algorithmic parameter selection.
Optimal dependence
- For the family in Proposition 5.1, no threshold clustering improves the approximation error, yielding the square-root obstruction to stronger dependence on average hyperbolicity.The construction uses an atomless space partitioned into equal-mass sets U_i and V_i, with s_m positive on paired sets and otherwise zero off the diagonal.Source: §5 · p. 11
- The constructed family shows that no universal bound Tree(s) ≤ Cb^(1−α)Hyp(s)^α can hold for α > 1/2, while the paper’s upper bound has exponent 1/3.The square-root lower bound leaves open whether the 1/2 exponent holds throughout the framework.Source: §5 · pp. 10–11
Limitations of common refinement
- The Figure 3 example shows common refinement can amplify threshold disagreement by an arbitrarily large factor, despite the raw partitions reuniting U and V at higher levels.Under the sampling scheme, the first pivot lies in W and a later pivot lies in U ∪ V with probability tending to one as p decreases to zero.Source: §5 · p. 11, Figure 3 · p. 12
Future directions
- For hierarchical correlation clustering, an LP-rounding approach remains a direction to explore, but it needs a bound connecting its fractional objective to average hyperbolicity.An approximation guarantee relative only to optimal fitting cost would not establish the desired structural estimate.Source: §5 · p. 11
Comparison with ultrametric fitting
- At fixed n and diameter M, HCCUltraFit’s linear estimate is stronger for sufficiently small AvgUM(d), while the paper’s cube-root estimate is stronger as AvgUM(d) increases.The comparison selects the better of the two outputs; M denotes diam(X, d).Source: §5 · p. 11
Finite inputs
- For finite inputs, there are only O(n^2) distinct threshold relations, but exploiting them requires retaining interval lengths as weights in the error analysis.Discarding repeated sampled pivots leaves at most n distinct pivots, but sampling without replacement would require modifying the analysis; adapting levels and sampling may or may not improve the bound.Source: §5 · pp. 11–12
Algorithmic implementation
- For large finite inputs, computing Hyp(s) exactly takes Θ(n^3) time, so sampling triples may be preferable.Reliable selection of h and λ from an estimate of Hyp(s), especially when Hyp(s) is small, and finding a suitable shift θ remain practical questions.Source: §5 · p. 12
Spin-glass connection
- For spin-glass applications, the authors suggest that additional model structure may permit improved bounds in terms of average hyperbolicity.The motivating application assumes asymptotic ultrametricity of overlaps, or of a bounded transformation of them.Source: §5 · p. 12