# SpEx: A Spectral Approach to Explainable Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 2 Nov 2025.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [ExKMC: Expanding Explainable k-Means Clustering](https://mlsanity.com/paper/2006.02399/) (2020)
- [On the price of explainability for some clustering problems](https://mlsanity.com/paper/2101.01576/) (2021)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (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)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Random Cuts are Optimal for Explainable k-Medians](https://mlsanity.com/paper/2304.09113/) (2023)
- [The Price of Explainability for Clustering](https://mlsanity.com/paper/2304.09743/) (2023)
- [The computational complexity of some explainable clustering problems](https://mlsanity.com/paper/2208.09643/) (2022)
- [Kernel KMeans clustering splits for end-to-end unsupervised decision trees](https://mlsanity.com/paper/2402.12232/) (2024)
- [Optimal Decision Trees For Interpretable Clustering with Constraints (Extended Version)](https://mlsanity.com/paper/2301.12671/) (2023)
- [NeurCAM: Interpretable Neural Clustering via Additive Models](https://mlsanity.com/paper/2408.13361/) (2024)
- [Explaining Kernel Clustering via Decision Trees](https://mlsanity.com/paper/2402.09881/) (2024)
- [Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?](https://mlsanity.com/paper/1303.2730/) (2013)

## Abstract (arXiv)

Explainable clustering by axis-aligned decision trees was introduced by Moshkovitz et al. (2020) and has gained considerable interest. Prior work has focused on minimizing the price of explainability for specific clustering objectives, lacking a general method to fit an explanation tree to any given clustering, without restrictions. In this work, we propose a new and generic approach to explainable clustering, based on spectral graph partitioning. With it, we design an explainable clustering algorithm that can fit an explanation tree to any given non-explainable clustering, or directly to the dataset itself. Moreover, we show that prior algorithms can also be interpreted as graph partitioning, through a generalized framework due to Trevisan (2013) wherein cuts are optimized in two graphs simultaneously. Our experiments show the favorable performance of our method compared to baselines on a range of datasets.