SpEx: A Spectral Approach to Explainable Clustering

AI summary

Overview

Research area: Explainable machine learning, specifically explainable clustering via axis-aligned decision trees; also draws on spectral graph theory and graph partitioning.

Technical level: Intermediate. The paper assumes familiarity with clustering objectives, decision trees, and basic spectral graph concepts (conductance, Cheeger's inequality), though the core ideas can be grasped with less background.

Scope: The paper proposes a spectral-graph-based framework for fitting an explainable decision-tree clustering to any reference clustering — or directly to the data — and evaluates it against prior explainable clustering methods on eight real-world datasets.

What This Paper Is About

Explainable clustering asks for a clustering that can be described by simple, human-readable rules — specifically, a binary decision tree where each internal node thresholds a single feature coordinate. Prior work (most notably the IMM algorithm of Moshkovitz et al.) mostly requires the reference clustering to come with centroids (like k-means or k-medians), which rules out centroid-free clusterings such as spectral clustering or kernel k-means. This paper's goal is a single, generic method that can round any given clustering — regardless of how it was produced, or whether it has centroids — into an explainable one, while remaining accurate and scalable.

Key Contributions

1. A spectral framework for explainable clustering. The authors connect coordinate cuts in ℝ^d to Cheeger-style graph conductance bounds (Theorem 2.2), showing that a low-conductance coordinate cut exists when a graph captures geometric nearness among points.

2. Two concrete algorithms. SpEx-Clique builds a clique graph over each cluster of a given reference clustering and rounds it into an explainable tree; SpEx-kNN skips the reference clustering entirely and builds a k-nearest-neighbor graph directly on the dataset.

3. A unifying reinterpretation of prior methods. Using Trevisan's non-uniform sparse cuts framework (cuts optimized in two graphs simultaneously), the authors show that IMM corresponds to a star graph plus a single edge between diametrical centroids, EMN corresponds to a star graph plus an unweighted clique over centroids, and CART corresponds to the independent-set graph plus an H-degree weighted clique.

4. An empirical comparison at larger scale than prior work. Experiments on eight public datasets show favorable performance versus EMN, CART, and Kernel IMM, and indicate that CART underperforms on real data while Kernel IMM fails to scale.

Main Findings

• Prior methods are special cases of a two-graph cut framework. IMM, EMN, and CART can each be expressed as minimizing or maximizing the non-uniform sparsity Ψ_{G,H}(S) for particular graph pairs, even though none of them was originally described in graph-cut terms.

• The graph choice explains the failure modes. IMM and EMN use the star graph, which is why they require centroids. CART effectively uses the independent-set (IS) graph, which rewards separating points in different clusters but gives no credit for keeping same-cluster points together — this explains why CART picks the error-heavy vertical cut in the authors' toy example.

• SpEx-Clique is unrestricted. It can round any reference clustering, including centroid-free ones like spectral clustering, and can produce trees with any desired number of leaves (unlike centroid-based methods, which are tied to the number of centroids).

• SpEx-kNN is reference-free. A k-NN graph with k = 20 is used to construct an explainable clustering directly from data, with no reference clustering at all.

• Kernel IMM does not scale. The authors report that Kernel IMM failed to run on the larger datasets, so its results are reported only for the three smaller datasets (Breast Cancer, Ecoli, Iris) — the same ones used in the original Kernel IMM paper.

• CART's failure is not merely pathological. While preliminary small-scale results in prior work suggested CART performs well, the authors' larger-scale experiments indicate CART suffers low performance on real data.

• Computational complexity. SpEx runs in O(kdn(log n + S)) total time. For SpEx-Clique, score updates take S = O(1) time, using O(n) memory for point-cluster assignments plus O(k) for histograms. For SpEx-kNN, letting κ be the number of neighbors per node, the graph uses O(nκ) memory and score updates take S = O(κ).

• Reported quantitative results. The paper reports ARI (Adjusted Rand Index) and AMI (Adjusted Mutual Information) in Figure 3 and mentions Tables 2 and 3 as augmenting them, but the numeric values of those results are not included in the available text; the stated outcome is favorable performance of SpEx compared to baselines across the datasets.

Methodology in Plain English

The core idea is to turn clustering into a graph problem. Given a set of points and some notion of which points "belong together," build a graph where connected points are ones you'd expect to be near each other in space. A classical result (Cheeger's inequality) says such graphs contain a cut with low conductance — a cheap way to separate the graph. The paper's Theorem 2.2 extends this: if the graph meaningfully captures geometric relationships, then the low-conductance cut can be realized as a coordinate cut (a threshold on a single feature). That is exactly the kind of cut a decision tree node makes.

So the algorithm builds a decision tree greedily: at each step, it picks the leaf whose best coordinate cut would reduce total conductance the most, splits it, and repeats until it has the desired number of leaves. How you build the graph determines the flavor: a clique over each reference cluster gives SpEx-Clique; a k-NN graph on the raw data gives SpEx-kNN. To understand why older methods behave differently, the authors map them onto the same picture but with different graph pairs — star graphs (requiring centroids) or independent-set graphs (rewarding cutting across clusters without protecting within-cluster cohesion).

Why This Matters

Impact on research. The paper offers a general theoretical lens — non-uniform sparse cuts — that unifies most existing explainable clustering algorithms and reveals why each has its specific limitations. It also shows how to attach explainability to clustering families (spectral, kernel) that prior methods could not handle, which broadens the applicability of explainable clustering beyond k-means and k-medians.

Real-world applications:

• Healthcare and clinical decision support, where patient cohorts produced by non-centroid methods need to be described with simple threshold rules.
• Customer segmentation, where marketers want interpretable rules over demographic or behavioral features.
• Document and image organization, where embeddings from models like CLIP and SBERT are clustered and users need to understand why items were grouped.
• Regulated decision-making (credit, hiring, insurance), where an explanation such as "assigned to group B because feature 7 ≤ 3.2" is required for accountability.

Industry relevance. Because SpEx runs in O(kdn(log n + S)) time and avoids storing large dense graphs, it is practical on datasets with tens of thousands of points and hundreds of dimensions — the scale the paper tests on (MNIST, CIFAR-10, 20Newsgroups). This makes it a plausible drop-in for production pipelines that already cluster with spectral methods or embeddings and need an interpretable layer on top.

Future Directions

• Beyond axis-aligned cuts. The paper deliberately restricts itself to the original single-coordinate threshold model; extending the spectral framework to oblique (hyperplane) cuts, which would raise expressive power at the cost of interpretability, is an open direction.
• Choice of graph. SpEx-Clique and SpEx-kNN are two natural instantiations, but the framework allows other graph constructions; which graph best serves which data regime is not settled.
• Scaling the kernel approach. Kernel IMM fails on larger datasets; whether the spectral lens can yield a scalable, generic substitute for other centroid-free clustering families remains to be shown.
• Tunable number of leaves. The algorithm can produce trees with any number of leaves, trading explainability for accuracy; how to select that number optimally is left as an open practical question.

Target Audience

This paper is most useful for machine learning researchers working on interpretability and clustering, especially those interested in spectral methods and graph partitioning. It also suits practitioners who need explainable groupings over embedding-based data at moderate scale. A reader without background in graph cuts will find the theoretical sections demanding, but the introductory framing and the plain descriptions of the algorithms make the overall contribution accessible.

Authors’ abstract

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.