# Tree-Guided L1-Convex Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 31 Mar 2025.

## Builds on (most cited first, 16 of 16)

- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [Statistical Properties of Convex Clustering](https://mlsanity.com/paper/1503.08340/) (2015)
- [Scalable Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2010.11821/) (2020)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [Convex Biclustering](https://mlsanity.com/paper/1408.0856/) (2014)
- [Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization](https://mlsanity.com/paper/1901.01477/) (2019)
- [Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm](https://mlsanity.com/paper/2209.05757/) (2022)
- [Convex clustering via ℓ1 fusion penalization](https://mlsanity.com/paper/1412.0753/) (2014)
- [Biconvex Clustering](https://mlsanity.com/paper/2008.01760/) (2020)
- [An Efficient Semismooth Newton Based Algorithm for Convex Clustering](https://mlsanity.com/paper/1802.07091/) (2018)
- [Total variation on a tree](https://mlsanity.com/paper/1502.07770/) (2015)
- [Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering](https://mlsanity.com/paper/2211.01877/) (2022)
- [Supervised Convex Clustering](https://mlsanity.com/paper/2005.12198/) (2020)
- [Pursuit of the Cluster Structure of Network Lasso: Recovery Condition and Non-convex Extension](https://mlsanity.com/paper/2012.07491/) (2020)

## Abstract (arXiv)

Convex clustering is a modern clustering framework that guarantees globally optimal solutions and performs comparably to other advanced clustering methods. However, obtaining a complete dendrogram (clusterpath) for large-scale datasets remains computationally challenging due to the extensive costs associated with iterative optimization approaches. To address this limitation, we develop a novel convex clustering algorithm called Tree-Guided L1-Convex Clustering (TGCC). We first focus on the fact that the loss function of L1-convex clustering with tree-structured weights can be efficiently optimized using a dynamic programming approach. We then develop an efficient cluster fusion algorithm that utilizes the tree structure of the weights to accelerate the optimization process and eliminate the issue of cluster splits commonly observed in convex clustering. By combining the dynamic programming approach with the cluster fusion algorithm, the TGCC algorithm achieves superior computational efficiency without sacrificing clustering performance. Remarkably, our TGCC algorithm can construct a complete clusterpath for 106 points in ℝ2 within 15 seconds on a standard laptop without the need for parallel or distributed computing frameworks. Moreover, we extend the TGCC algorithm to develop biclustering and sparse convex clustering algorithms.