# Balancing the Tradeoff Between Clustering Value and Interpretability

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2019.

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

- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Shallow decision trees for explainable k-means clustering](https://mlsanity.com/paper/2112.14718/) (2021)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Discord Questions: A Computational Approach To Diversity Analysis in News Coverage](https://mlsanity.com/paper/2211.05007/) (2022)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [Learning to Generate Fair Clusters from Demonstrations](https://mlsanity.com/paper/2102.03977/) (2021)
- [VitrAI -- Applying Explainable AI in the Real World](https://mlsanity.com/paper/2102.06518/) (2021)
- [Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms](https://mlsanity.com/paper/2209.09670/) (2022)
- [Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information](https://mlsanity.com/paper/2504.20846/) (2025)
- [An Explainable System for Offensive Content Detection in Nastaliq Urdu: Corpus Curation, Transformer Benchmarking, and Word-Level Attribution](https://mlsanity.com/paper/2610.15795/) (2026)

## Abstract (arXiv)

Graph clustering groups entities -- the vertices of a graph -- based on their similarity, typically using a complex distance function over a large number of features. Successful integration of clustering approaches in automated decision-support systems hinges on the interpretability of the resulting clusters. This paper addresses the problem of generating interpretable clusters, given features of interest that signify interpretability to an end-user, by optimizing interpretability in addition to common clustering objectives. We propose a β-interpretable clustering algorithm that ensures that at least β fraction of nodes in each cluster share the same feature value. The tunable parameter β is user-specified. We also present a more efficient algorithm for scenarios with β!=!1 and analyze the theoretical guarantees of the two algorithms. Finally, we empirically demonstrate the benefits of our approaches in generating interpretable clusters using four real-world datasets. The interpretability of the clusters is complemented by generating simple explanations denoting the feature values of the nodes in the clusters, using frequent pattern mining.