Research map / Learning theory and algorithms / Optimal transport
UltraTWD: Optimizing Ultrametric Trees for Tree-Wasserstein Distance
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 UltraTWD, an unsupervised method that jointly optimizes ultrametric tree structure and edge weights (via MST, iterative projection, or gradient descent) to better approximate Wasserstein distance with tree-Wasserstein distance.
Problem
Tree-Wasserstein distance (TWD) offers linear-time approximation of the 1-Wasserstein distance, but existing TWD methods use suboptimal tree structures and edge weights, or require labeled supervision to learn trees.
Approach
Formulates ultrametric nearness problems (l-infinity and Frobenius norm) over the cost matrix and solves them with three unsupervised algorithms, so that tree structure and edge weights are optimized together without training data.
Key results
- UltraTWD-IP reduces RE-W on BBCSport to 0.014 versus 0.022 for supervised UltraTree and 0.116 for cTWD.
- UltraTWD-IP achieves the highest document retrieval precision on all four datasets, e.g., 0.885 on BBCSport versus 0.863 for Sliced-cTWD.
- UltraTWD-GD learns trees in 15-72 seconds, up to 43x faster than UltraTree while being more accurate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use UltraTWD-IP instead of the strongest reported baseline | Tree-Wasserstein distance estimation · BBCSport, Reuters, Ohsumed, Recipe | RE-W: BBCSport: 0.022±0.001 -> 0.014±0.000; Reuters: 0.041±0.003 -> 0.033±0.001; Ohsumed: 0.038±0.001 -> 0.036±0.001; Recipe: | Helped |
| use UltraTWD-IP instead of the strongest reported baseline | Document retrieval · BBCSport, Reuters, Ohsumed, Recipe | Precision: BBCSport: 0.863±0.002 -> 0.885±0.002; Reuters: 0.849±0.002 -> 0.876±0.003; Ohsumed: 0.749±0.003 -> 0.788±0.005; Recipe: | Helped |
| use UltraTWD-IP instead of the strongest reported baseline | Document ranking · BBCSport, Reuters, Ohsumed, Recipe | MRR: BBCSport: 0.890±0.009 -> 0.924±0.011; Reuters: 0.887±0.005 -> 0.913±0.005; Ohsumed: 0.831±0.010 -> 0.863±0.005; Recipe: | Helped |
| use UltraTWD-IP instead of the strongest reported baseline | Document classification · BBCSport, Reuters, Ohsumed, Recipe | Accuracy: BBCSport: 0.826±0.017 -> 0.839±0.017; Reuters: 0.902±0.009 -> 0.905±0.010; Ohsumed: 0.416±0.023 -> 0.428±0.020; Recipe: | Mixed |
| increase UltraTree training-distribution sparsity from 1% to 2% (ablation) | UltraTree · Reuters and Ohsumed | RE-W: Reuters: 0.041±0.003 -> 0.061±0.002; Ohsumed: 0.038±0.001 -> 0.069±0.001 | Hurt |
| increase UltraTree training-distribution sparsity from 1% to 2% (ablation) | UltraTree · Reuters and Ohsumed | RE-D: Reuters: 0.113±0.001 -> 0.130±0.000; Ohsumed: 0.123±0.001 -> 0.147±0.000 | Hurt |
| increase UltraTree training-distribution sparsity from 1% to 10% (ablation) | UltraTree · Reuters and Ohsumed | RE-W: Reuters: 0.041±0.003 -> 0.127±0.003; Ohsumed: 0.038±0.001 -> 0.119±0.001 | Hurt |
Surprising findings
- The supervised UltraTree degrades sharply when test sparsity differs from its training sparsity (RE-W on Reuters rises from 0.041 to 0.127 at 10% sparsity).
Limitations
- Frobenius-norm ultrametric nearness is NP-hard, so the iterative projection and gradient descent methods lack convergence guarantees.
- UltraTWD-IP scales as O(n^3) and its learning time grows large for big vocabularies (up to 4583 s on Ohsumed).
- Evaluated only on four text datasets with Euclidean word-embedding costs.
Experimental setup
Datasets: BBCSport Reuters Ohsumed Recipe
Benchmarks: BBCSport Reuters Ohsumed Recipe
Metrics: RE-W Precision MRR Accuracy RE-D runtime
Baselines: Sinkhorn QuadTree ClusterTree qTWD cTWD Sliced-QuadTree Sliced-ClusterTree UltraTree
Builds on: tree-Wasserstein distance UltraTree Word Mover's Distance HLWB projection
Closest papers by meaning
- Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy (ICLR 2025 · similarity 0.90)
- Joint Hierarchical Representation Learning of Samples and Features via Informed Tree-Wasserstein Distance (NeurIPS 2025 · similarity 0.87)
- Fast unsupervised ground metric learning with tree-Wasserstein distance (ICLR 2025 · similarity 0.87)
- Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.86)
- A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.86)
- A (1+?)-Approximation for Ultrametric Embedding in Subquadratic Time (AAAI 2025 · similarity 0.86)
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.