# Recovering Trees with Convex Clustering

arXiv: https://arxiv.org/abs/1806.11096 · HTML: https://mlsanity.com/paper/1806.11096/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2018.

## Built on by (most cited first, 11 of 11)

- [GraphMAD: Graph Mixup for Data Augmentation using Data-Driven Convex Clustering](https://mlsanity.com/paper/2210.15721/) (2022)
- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering](https://mlsanity.com/paper/2211.01877/) (2022)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [On Convex Clustering Solutions](https://mlsanity.com/paper/2105.08348/) (2021)
- [Optimization Models and Interpretations for Three Types of Adversarial Perturbations against Support Vector Machines](https://mlsanity.com/paper/2204.03154/) (2022)
- [Network Clustering for Latent State and Changepoint Detection](https://mlsanity.com/paper/2111.01273/) (2021)
- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [Simple and Scalable Algorithms for Cluster-Aware Precision Medicine](https://mlsanity.com/paper/2211.16553/) (2022)
- [A New Framework for Convex Clustering in Kernel Spaces: Finite Sample Bounds, Consistency and Performance Insights](https://mlsanity.com/paper/2511.05159/) (2025)
- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)

## Abstract (arXiv)

Convex clustering refers, for given leftx1, dots, xnright subset ℝp, to the minimization of begineqnarray* u(γ) & = & undersetu1, dots, un argmin;sumi=1nlVert xi - ui rVert2 + γ sumi,j=1nwij lVert ui - ujrVert, endeqnarray* where wij ≥ 0 is an affinity that quantifies the similarity between xi and xj. We prove that if the affinities wij reflect a tree structure in the leftx1, dots, xnright, then the convex clustering solution path reconstructs the tree exactly. The main technical ingredient implies the following combinatorial byproduct: for every set leftx1, dots, xn right subset ℝp of n ≥ 2 distinct points, there exist at least n/6 points with the property that for any of these points x there is a unit vector v ∈ ℝp such that, when viewed from x, `most' points lie in the direction v begineqnarray* frac1n-1sumi=1 atop xi neq xn leftlangle fracxi - xlVert xi - x rVert, v rightrangle & ≥ & frac14. endeqnarray*