# Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 70 references that are in the map.
- First posted on arXiv 13 Sep 2022.

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

- [Time Series Clustering via Community Detection in Networks](https://mlsanity.com/paper/1508.04757/) (2015)

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

- [A framework for benchmarking clustering algorithms](https://mlsanity.com/paper/2209.09493/) (2022)
- [Clustering with minimum spanning trees: How good can it be?](https://mlsanity.com/paper/2303.05679/) (2023)
- [On the Use of Relative Validity Indices for Comparing Clustering Approaches](https://mlsanity.com/paper/2404.10351/) (2024)
- [Hierarchical clustering with OWA-based linkages, the Lance-Williams formula, and dendrogram inversions](https://mlsanity.com/paper/2303.05683/) (2023)
- [Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering](https://mlsanity.com/paper/2303.12212/) (2023)
- [PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU](https://mlsanity.com/paper/2401.06089/) (2024)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)
- [Local Cluster Cardinality Estimation for Adaptive Mean Shift](https://mlsanity.com/paper/2508.12450/) (2025)
- [Lumbermark: Resistant Clustering by Chopping Up Mutual Reachability Minimum Spanning Trees](https://mlsanity.com/paper/2604.07143/) (2026)
- [G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation](https://mlsanity.com/paper/2609.24823/) (2026)

## Abstract (arXiv)

The time needed to apply a hierarchical clustering algorithm is most often dominated by the number of computations of a pairwise dissimilarity measure. Such a constraint, for larger data sets, puts at a disadvantage the use of all the classical linkage criteria but the single linkage one. However, it is known that the single linkage clustering algorithm is very sensitive to outliers, produces highly skewed dendrograms, and therefore usually does not reflect the true underlying data structure -- unless the clusters are well-separated. To overcome its limitations, we propose a new hierarchical clustering linkage criterion called Genie. Namely, our algorithm links two clusters in such a way that a chosen economic inequity measure (e.g., the Gini- or Bonferroni-index) of the cluster sizes does not drastically increase above a given threshold. The presented benchmarks indicate a high practical usefulness of the introduced method: it most often outperforms the Ward or average linkage in terms of the clustering quality while retaining the single linkage's speed. The Genie algorithm is easily parallelizable and thus may be run on multiple threads to speed up its execution even further. Its memory overhead is small: there is no need to precompute the complete distance matrix to perform the computations in order to obtain a desired clustering. It can be applied on arbitrary spaces equipped with a dissimilarity measure, e.g., on real vectors, DNA or protein sequences, images, rankings, informetric data, etc. A reference implementation of the algorithm has been included in the open source 'genie' package for R. See also https://genieclust.gagolewski.com for a new implementation (genieclust) -- available for both R and Python.