Research map / Learning theory and algorithms / Prediction and decision losses
Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DeltaZero, a differentiable method that optimizes a distance matrix with a smooth (log-sum-exp) Gromov hyperbolicity penalty plus an L2 fidelity term, using batched sampling and Floyd-Warshall projection, then embeds the result into a tree via Gromov's construction.
Problem
Approximating an arbitrary finite metric space by a tree metric with minimal l-infinity distortion, which is hard to do exactly and where existing heuristics lack guarantees or perform moderately.
Approach
Relax Gromov's delta-hyperbolicity with log-sum-exp smoothing and a batched two-level estimate so it becomes differentiable and tractable; jointly minimize distortion to the input metric plus this hyperbolicity penalty with Adam and Floyd-Warshall projections onto the metric cone, then apply Gromov's tree embedding.
Key results
- On C-ELEGAN, DeltaZero reaches l-infinity distortion 1.87 vs 2.97 for the second-best NJ (43.8% relative improvement).
- On Zeisel, DeltaZero achieves 0.24 vs 0.43 for Gromov (44.1% improvement).
- DeltaZero attains the lowest l-infinity distortion on all seven datasets, with the smallest gain on Cora (2.3%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DeltaZero instead of NeighborJoin | Tree metric fitting · C-ELEGAN | ℓ∞ distortion: 2.97 -> 1.87 \pm \text{ 0.08} | Helped |
| Use DeltaZero instead of Gromov | Tree metric fitting · CS PhD | ℓ∞ distortion: 13.28 \pm \text{ 0.61} -> 10.31 \pm \text{ 0.62} | Helped |
| Use DeltaZero instead of LayeringTree | Tree metric fitting · Cora | ℓ∞ distortion: 7.76 \pm \text{ 0.54} -> 7.59 \pm \text{ 0.38} | Helped |
| Use DeltaZero instead of LayeringTree | Tree metric fitting · Airport | ℓ∞ distortion: 2.97 \pm \text{ 0.26} -> 2.79 \pm \text{ 0.15} | Helped |
| Use DeltaZero instead of LayeringTree | Tree metric fitting · Wiki | ℓ∞ distortion: 4.08 \pm \text{ 0.27} -> 3.56 \pm \text{ 0.20} | Helped |
| Use DeltaZero instead of Gromov | Tree metric fitting · Zeisel | ℓ∞ distortion: 0.43 \pm \text{ 0.02} -> 0.24 \pm \text{ 0.00} | Helped |
| Use DeltaZero instead of NeighborJoin | Tree metric fitting · IBD | ℓ∞ distortion: 0.90 -> 0.70 \pm \text{ 0.03} | Helped |
Surprising findings
- Minimizing the l2 fidelity term can lower average distortion while increasing worst-case l-infinity distortion, as the paper notes.
- On the 4-by-4 grid graph in the appendix, LayeringTree performs best, not DeltaZero.
Limitations
- Batched sampling does not guarantee closeness to true hyperbolicity and may miss rare configurations that determine the global value.
- Random-metric convergence theory assumes independent distances, which is restrictive for real graphs.
- The l2 surrogate does not directly control l-infinity distortion; mu is tuned by grid search rather than set from theory.
Experimental setup
Datasets: C-ELEGAN CS PhD Cora Airport Wiki Zeisel IBD
Benchmarks: C-ELEGAN CS PhD Cora Airport Wiki Zeisel IBD
Metrics: l-infinity distortion l1 distortion clustering accuracy execution time
Baselines: NeighborJoin TreeRep HCCRootedTreeFit LayeringTree Gromov
Builds on: Gromov tree embedding Floyd-Warshall Adam TreeRep Neighbor Joining
Closest papers by meaning
- Fast Hyperboloid Decision Tree Algorithms (ICLR 2024 · similarity 0.86)
- Tree-Sliced Wasserstein Distance with Nonlinear Projection (ICML 2025 · similarity 0.86)
- Tree-Sliced Wasserstein Distance: A Geometric Perspective (ICML 2025 · similarity 0.85)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.85)
- Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.85)
- Spherical Tree-Sliced Wasserstein Distance (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.