Research map / Graph learning / Graph algorithms and clustering
SpEx: A Spectral Approach to Explainable Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SpEx, a spectral graph-partitioning method that fits an explainable coordinate-cut tree to any reference clustering (or directly to data via kNN graph), and unifies prior methods (IMM, EMN, CART) as non-uniform sparse cut instances.
Problem
Explainable clustering with axis-aligned decision trees: existing methods need centroid-based reference clusterings or are tied to specific objectives, and CART is not designed for this task, so there is no generic, reference-oblivious method that is robust across datasets.
Approach
Relates coordinate cuts to graph conductance via a Cheeger-type theorem over a graph describing the reference clustering (clique graph) or the data (kNN graph), then greedily splits leaves to minimize the sum of multiway normalized-cut conductances; shows IMM, EMN and CART are special cases of non-uniform sparsest cut with specific graph pairs.
Key results
- SpEx-Clique is the most consistently high-performing method, outperforming each baseline in most cases on ARI/AMI against ground truth.
- On Beans, SpEx-kNN achieves ARI .574 versus .542 for CART and .563 for EMN; SpEx-kNN is highly effective on low-dimensional datasets (Beans, Ecoli, Iris).
- CART performs poorly on larger datasets, e.g. MNIST ARI .027 versus SpEx-Clique .217 (spectral reference) and CIFAR ARI .036 versus .320.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SpEx-Clique instead of Kernel IMM | explainable clustering with Kernel k-means reference · Cancer | ARI: .127 -> .406 | Helped |
| Use SpEx-kNN instead of CART | explainable clustering · Ecoli | ARI: .672 -> .679 | Helped |
| Use SpEx-kNN instead of EMN | explainable clustering · Beans | ARI: .563 -> .574 | Helped |
| Use SpEx-kNN instead of EMN | explainable clustering · CIFAR-10 | ARI: .314 -> .342 | Helped |
| Use SpEx-Clique instead of EMN | explainable clustering with k-means reference · MNIST | ARI: .25 -> .209 | Hurt |
| Use SpEx-Clique instead of EMN | explainable clustering with k-means reference · Caltech 101 | ARI: .249 -> .122 | Hurt |
| Use SpEx-Clique instead of EMN | explainable clustering with k-means reference · 20Newsgroups | ARI: .115 -> .098 | Hurt |
| Use SpEx-Clique instead of CART | explainable clustering with spectral reference · R15 | ARI: .986 -> .986 | No clear effect |
| Use SpEx-Clique instead of CART | explainable clustering with spectral reference · Pathbased | ARI: .441 -> .441 | No clear effect |
Surprising findings
- CART performs well on the smaller datasets but collapses on larger real datasets such as MNIST, Caltech 101 and 20Newsgroups, where its ARI is near zero.
- Kernel IMM does not scale and could only be run on the smaller datasets.
Limitations
- SpEx provides no formal approximation bounds on price of explainability, unlike IMM/EMN for k-medians/k-means.
- EMN is better than SpEx for k-means reference clustering, so SpEx is not uniformly best.
- Kernel IMM does not scale beyond small datasets and SpEx-kNN performance drops on high-dimensional data.
Experimental setup
Datasets: CIFAR-10 20Newsgroups MNIST Caltech 101 Beans Breast Cancer Ecoli Iris R15 Pathbased
Benchmarks: CIFAR-10 20Newsgroups MNIST Caltech 101 Beans Breast Cancer Ecoli Iris R15 Pathbased
Metrics: ARI AMI
Baselines: EMN CART Kernel IMM ExKMC
Builds on: IMM EMN CART Kernel IMM Trevisan non-uniform sparsest cut
Closest papers by meaning
- XClusters: Explainability-First Clustering (AAAI 2023 · similarity 0.91)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · similarity 0.89)
- Explaining Kernel Clustering via Decision Trees (ICLR 2024 · similarity 0.89)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.86)
- THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (AAAI 2025 · similarity 0.85)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.