Research map / Learning theory and algorithms / Clustering
Learning-Augmented Hierarchical Clustering
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.
Shows that a noisy triplet "splitting oracle" lets hierarchical clustering beat known hardness barriers: O(1)-approximation for Dasgupta's cost and (1-o(1))-approximation for Moseley-Wang revenue, plus streaming and PRAM variants.
Problem
Hierarchical clustering under Dasgupta's cost and Moseley-Wang revenue objectives is hard to approximate in polynomial time under standard hypotheses (Small Set Expansion, UGC), so the paper asks whether auxiliary information from an erroneous oracle can overcome these barriers.
Approach
Introduces a stochastic triplet splitting oracle (correct with probability p=9/10, fixed per triplet) and builds strongly and weakly consistent "partial HC trees" whose leaves are super-vertices of size O(log n), which can be built regardless of the objective and then refined locally with sparsest cut or arbitrary partitions.
Key results
- Polynomial-time O(1)-approximation to Dasgupta's objective with O(n^3) oracle queries (w.h.p.), with a very large polynomial exponent (O(n^50002) runtime).
- O(sqrt(log log n))-approximation to Dasgupta's objective in O(n^3 log n) time and O(n^3) queries.
- (1-o(1))-approximation to Moseley-Wang revenue in O(n^2 polylog n) time and O(n^2) queries, matching a near-linear time bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a splitting oracle with exact recursive sparsest cuts on super-vertices | Hierarchical clustering for the Dasgupta objective · Dasgupta objective | approximation ratio: O(\sqrt{\log n}) -> O(1) | Helped |
| Use a splitting oracle and approximate recursive sparsest cuts on super-vertices | Hierarchical clustering for the Dasgupta objective · Dasgupta objective | approximation ratio: O(\sqrt{\log n}) -> O(\sqrt{\log\log{n}}) | Helped |
| Use a splitting oracle and weakly consistent partial HC trees | Hierarchical clustering for the Moseley-Wang objective · Moseley-Wang objective | approximation ratio: 1/3 -> (1-o(1)) | Helped |
| Use a splitting oracle in a single-pass dynamic streaming algorithm | Hierarchical clustering for the Dasgupta objective · Dynamic graph streaming | approximation ratio | Helped |
| Use a splitting oracle and weakly consistent partial HC trees in PRAM | Hierarchical clustering for the Moseley-Wang objective · PRAM | approximation ratio | Helped |
Surprising findings
- Under adversarial errors, the oracle must be correct with probability at least roughly 3/4 for meaningful results in the root-cut example; success probability 1/2+epsilon is insufficient in general.
- Repeated queries on the same triplet return the same answer, so simple majority-vote boosting is ruled out by design.
Limitations
- Dasgupta O(1)-approximation runs in O(n^50002) time, which is impractical; practical variant only gives O(sqrt(log log n)).
- Weakly consistent construction relies on the oracle answering with the optimal tree; extending to oracles built from approximately optimal trees is open.
- Requires oracle correctness probability well above 1/2 (assumed p=9/10) due to error propagation through the hierarchy.
Experimental setup
Metrics: Dasgupta cost approximation factor Moseley-Wang revenue approximation factor running time number of oracle queries
Baselines: average-linkage recursive sparsest cut with O(sqrt(log n)) approximation semi-streaming HC algorithms
Builds on: Dasgupta objective Moseley-Wang objective recursive sparsest cut Small Set Expansion hypothesis
Closest papers by meaning
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.89)
- Expected Probabilistic Hierarchies (NeurIPS 2024 · similarity 0.88)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.87)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.86)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.86)
- From Logits to Hierarchies: Hierarchical Clustering made Simple (ICML 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.