# Clustering with minimum spanning trees: How good can it be?

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 114 references that are in the map.
- First posted on arXiv 10 Mar 2023.

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

- [Are Cluster Validity Measures (In)valid?](https://mlsanity.com/paper/2208.01261/) (2022)
- [A framework for benchmarking clustering algorithms](https://mlsanity.com/paper/2209.09493/) (2022)
- [Validation of cluster analysis results on validation data: A systematic framework](https://mlsanity.com/paper/2103.01281/) (2021)
- [Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm](https://mlsanity.com/paper/2209.05757/) (2022)
- [The Area Under the ROC Curve as a Measure of Clustering Quality](https://mlsanity.com/paper/2009.02400/) (2020)

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

- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)
- [Lumbermark: Resistant Clustering by Chopping Up Mutual Reachability Minimum Spanning Trees](https://mlsanity.com/paper/2604.07143/) (2026)
- [A new classification method based on Minimum Spanning Trees](https://mlsanity.com/paper/2606.21639/) (2026)
- [Spook the Machine: Gamified Exploration of Human Imagination of Machine Fear](https://mlsanity.com/paper/2609.15472/) (2026)

## Abstract (arXiv)

Minimum spanning trees (MSTs) provide a convenient representation of datasets in numerous pattern recognition activities. Moreover, they are relatively fast to compute. In this paper, we quantify the extent to which they are meaningful in low-dimensional partitional data clustering tasks. By identifying the upper bounds for the agreement between the best (oracle) algorithm and the expert labels from a large battery of benchmark data, we discover that MST methods can be very competitive. Next, we review, study, extend, and generalise a few existing, state-of-the-art MST-based partitioning schemes. This leads to some new noteworthy approaches. Overall, the Genie and the information-theoretic methods often outperform the non-MST algorithms such as K-means, Gaussian mixtures, spectral clustering, Birch, density-based, and classical hierarchical agglomerative procedures. Nevertheless, we identify that there is still some room for improvement, and thus the development of novel algorithms is encouraged.