# Possibility results for graph clustering: A novel consistency axiom

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

## Key facts

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

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

- [Towards Continuous Consistency Axiom](https://mlsanity.com/paper/2202.06015/) (2022)
- [An Axiomatic Definition of Hierarchical Clustering](https://mlsanity.com/paper/2407.03574/) (2024)
- [How To Overcome Richness Axiom Fallacy](https://mlsanity.com/paper/2210.15507/) (2022)
- [High-Dimensional Wide Gap k-Means Versus Clustering Axioms](https://mlsanity.com/paper/2211.17036/) (2022)
- [Improving the Utility of Differentially Private Clustering through Dynamical Processing](https://mlsanity.com/paper/2304.13886/) (2023)
- [Wide Gaps and Clustering Axioms](https://mlsanity.com/paper/2308.03464/) (2023)

## Abstract (arXiv)

Kleinberg introduced three natural clustering properties, or axioms, and showed they cannot be simultaneously satisfied by any clustering algorithm. We present a new clustering property, Monotonic Consistency, which avoids the well-known problematic behaviour of Kleinberg's Consistency axiom, and the impossibility result. Namely, we describe a clustering algorithm, Morse Clustering, inspired by Morse Theory in Differential Topology, which satisfies Kleinberg's original axioms with Consistency replaced by Monotonic Consistency. Morse clustering uncovers the underlying flow structure on a set or graph and returns a partition into trees representing basins of attraction of critical vertices. We also generalise Kleinberg's axiomatic approach to sparse graphs, showing an impossibility result for Consistency, and a possibility result for Monotonic Consistency and Morse clustering.