Research map / Learning theory and algorithms / Clustering

Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees

ICML 2025 · Learning theory and algorithms › Clustering · approach: Correlation 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.

Proposes Metric Forest Completion, which takes a heuristic initial forest and connects its components via a subquadratic 2.62-approximation (MFC-Approx), with a learning-augmented (2γ+1)-approximation guarantee for metric MSTs.

Problem

Computing a minimum spanning tree over n points in an arbitrary metric space needs Omega(n^2) distance queries to even approximate, which is prohibitive for large datasets and expensive metrics.

Approach

Start from a cheap forest of partition spanning trees (from k-center or k-NN components), then connect components using a representative-based approximation of inter-component distances, yielding a subquadratic 2.62-approximation for the completion step and a learning-augmented guarantee that depends on the forest's gamma-overlap with an optimal MST.

Key results

• MFC-Approx achieves cost ratios close to 1 on real datasets, e.g., 1.040 to 1.089 on Cooking for t=16 to 256, with runtime ratios up to 15.6x.
• The gamma-overlap bound is typically small (about 1.0 to 3.1 across real datasets), and cost ratios stay well below the theoretical (2γ+1) bound.
• Theoretical guarantee: subquadratic 2.62-approximation for metric forest completion and a (2γ+1)-approximation for metric MST when the initial forest is γ-overlapping.

Measured effects reported in the paper

Surprising findings

• On high-dimensional uniform random data the gamma bound becomes large (close to 30 at d=256), yet cost ratios stay very close to 1, far below the theoretical bound.
• Cost ratios on clustered synthetic data are minimized when the number of components t roughly matches the number of true Gaussian clusters.

Limitations

• Optimal MFC requires Omega(n^2) queries; the approximation only holds in subquadratic time when the number of components t = o(n).
• The gamma-overlap is expensive to compute exactly and is only bounded in experiments by comparing against one exact MST, so it is not practically computable for large data.
• Gamma can be large for high-dimensional unstructured data (e.g., near 30 at d=256), weakening the theoretical guarantee.

Experimental setup

Datasets: Fashion-MNIST Cooking (What's Cooking Kaggle, parsed by Amburg et al.) MovieLens-10M Kosarak Name Dataset (US names) GreenGenes (unaligned and aligned) synthetic uniform random point clouds synthetic Gaussian mixtures

Benchmarks: Fashion-MNIST Cooking MovieLens-10M Kosarak Names-US GreenGenes-Unaligned GreenGenes-Aligned

Metrics: cost ratio runtime ratio gamma-overlap bound runtime (minutes)

Baselines: Exact MST via Kruskal's algorithm on full distance graph

Builds on: Kruskal's algorithm Boruvka's algorithm learning-augmented algorithms greedy k-center 2-approximation

Closest papers by meaning

• Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.86)
• Complete-Tree Space Favors Data-Efficient Link Prediction (ICML 2025 · similarity 0.86)
• New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.85)
• A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.85)
• UltraTWD: Optimizing Ultrametric Trees for Tree-Wasserstein Distance (ICML 2025 · similarity 0.85)
• Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.85)