SpEx: A Spectral Approach to Explainable Clustering

Thank you for your valuable review and support!

It seems in Appendix Lemma A.10 you are actually also bounding the number of errors of a random cut. Can your analysis be used to say something about the price of Random Cut?

Yes, we illustrate this below; however, we preface it by noting that the Random Cut algorithm has been extensively studied in theory [11, 17, 18, 28. 30] and tight bounds for its price of explainability are already known, even up to the leading constant. Hence our techniques do not lead to new results for this algorithm, and we do not claim a contribution in this vein.

To illustrate how our analysis can be applied to Random Cut, we show it implies an $O(k)$ price-of-explainability bound for Random Cut, the same bound stated for IMM in Theorems A.7 and A.8. Consider Random Cut over the unweighted star graph for explainable $k$-medians. In a fixed node $u$, by a triangle inequality, a “mistake” (i.e., a point separated from its centroid) contributes at most an additive $\|b_u-a_u\|_1$ to the explainable clustering cost. In eq. (16) in Lemma A.10, the left-hand side is the expected number of mistakes of Random Cut and the right hand side is the reference clustering cost of centroids in $u$ divided by $\|b_u-a_u\|_1$. Hence, the expected additive loss in $u$ is at most the reference clustering cost of centroids in $u$. In each tree level the nodes induce a partition of the centroids, hence the expected additive loss of Random Cut per level is $O(cost_1(\mathcal C))$. Finally, summing over at most $k-1$ levels in the tree, the total additive loss in clustering cost is $O(k\cdot cost_1(\mathcal C))$.

What is the price of explainability for SPEX on k-means experiments?

We include it below. EMN as expected has the lower price of explainability for k-means on most datasets as it is tailored for this reference clustering.

Did the authors consider comparing against other practical explainable clustering algorithms [1,2]?

Thank you for the relevant references, we will include a discussion of [1] (while [2] is already referenced as [15]). Both papers use more relaxed notions of explainability than the algorithms we consider: [1] allows more generally shaped clusters (for example, the clustering in Fig. 2(a) in [1] is not expressible in the explainability model from [31]) and [2] extends the decision tree to more than [2] leaves. Nonetheless it is interesting to compare them to SpEx under a proper extension. Though we haven’t found an available implementation of [1], we include below a comparison to ExKMC [2] for explainable clustering with $\ell=2k$ leaves. The results suggest that ExKMC and SpEx-Clique are comparable in this regime, though ExKMC scores higher in ARI while SpEx-Clique scores higher in AMI.

Would it not be more reasonable in clustering to colour them according to some $k$-means partition?

This would be reasonable as well, and is what has been used in visualizations in many of the cited prior works. We chose a different notion of reference clustering than $k$-means in our visualization, since for $k$-means near-optimal explainable clustering algorithms were already known, and our focus is on extensions beyond $k$-means to general reference clusterings.

Thank you for your valuable review and support!

The paper claims that the proposed approach "has the flexibility to produce a tree T with any desired number of leaves, regardless of the number of clusters in the reference clustering” in contrast to approaches like IMM and EMN. It is not entirely clear to me why this is a benefit, as the other approaches can simply increase the number of clusters in the algorithm that produces the reference clustering.

We did not mean that this flexibility is necessarily beneficial (we will change the wording to correct this impression). Increasing the number of leaves to more than $k$ means modifying the notion of explanability to a weaker one since the same class would have multiple different explanations. Thus it prioritizes accuracy over explainability which is a use-case dependent decision.

What we meant to point out is that in SpEx this weaker explainability is possible by just partitioning more nodes with the same procedure. This is not possible with EMN for example, since its node partitioning procedure requires at least two reference centroids in the node, and is otherwise undefined (due to its score being divided by zero, see line 275).

Highly-related works are missing from both literature review and as baselines

Thank you for the highly relevant references, we will include an appropriate discussion. We note that [1,2,3] use different and more relaxed notions of explainability and are not directly comparable. [4] seems compatible with a kernel $k$-means reference; we have not been able to find an implementation of this method but we will look into this further. [5] allows more leaves than our methods, $\ell>k$; we include a comparison in the response to K9ow.

it would be very interesting to report both “the cost of interpretability” in the proposed approach

This can be read in the REF column of Tables 2 and 3 (at least under one definition of cost of explainability – abbrev. CoE – as there are a few ways to define this for general reference clusterings). The REF column treats the reference clustering as the ground truth clustering, entirely ignoring the given labels of the datasets (as opposed the ARI and AMI columns as well as Figure 3, which all measure clustering quality with respect to the given labels). In each band of rows (spectral, $k$-means and kernel $k$-means), the REF column of the top row (which contains the reference clustering) equals 1 definitionally. The other rows list the ARI of each explainable clustering method with respect to the reference clustering as ground truth. This is the inverse CoE (higher is better).

The REF results show that for the spectral reference, SpEx-Clique has the best CoE (highest REF) overall (on all datasets except Ecoli and Cancer where it is slightly outperformed by CART). For the $k$-means reference, EMN has the best CoE – as expected, since EMN is tailored to the $k$-means reference and is provably near-optimal for it by [11]. Similarly, Kernel IMM often has the best CoE for kernel $k$-means, since it is tailored to it.

and also the suboptimality as a result of using a greedy optimization procedure

It is not clear how to measure this since there is no clear way to compute the best explainable clustering tree overall. We mention, however, that prior work [11,18] has proved that greedy algorithms are worst-case near-optimal for explainable $k$-means.

It would be very useful to report aggregate metrics across datasets like average ARI and AMI to better understand the performance across datasets, ideally with standard deviation

Thank you for the suggestion – we include aggregate metrics below. We report the median error across datasets with the [p25 ,p75] quantiles as confidence intervals rather than mean/std since our experimental setting is deterministic. The error is measured as the difference from the best reference clustering for each dataset to offset the different intrinsic clusterability across datasets. Lower is better.

Thank you for your thoughtful review and questions.

proposed model in the context of existing XAI methods, explanation or the interpretability

First, we reiterate that the explainability model we study is not proposed by us, but has been proposed by [31] and widely adopted since (see the references in line 35). Our contribution is in developing new algorithms and theoretical framework for it.

To position their model in XAI: Generally there are two main approaches in XAI for explaining an ML model $M^{\*}$. (i) “Intrinsic explainability”, where $M^{\*}$ is approximated by a different model $M’$ which has a strictly imposed explainable structure. This yields strong interpretability since $M’$ is structurally explainable, while introducing a compromise on accuracy since $M’$ may differ from $M^{\*}$ in its output predictions. (ii) “Post-hoc explainability”, which attempts to match explanations to $M^{\*}$ after the fact while viewing it as an unchanged black-box. This maintains full accuracy since model predictions are never changed, but significantly inhibits interpretability due to the inherent “just so” nature of post-hoc explanations – this approach is bound to force explanations even on unexplainable model outcomes.

The explainable clustering model of [31] belong to type (i) – it is an intrinsically explainable method, where $M^{\*}$ is the reference clustering, $M’$ is the coordinate-threshold decision tree, and the gap in accuracy between them is quantified as the “price of explainability". Explainability is defined as describing the points assigned to each cluster by a sequence of feature thresholds.

Could the authors provide a more robust justification for the greedy approach?

Prior work has established that greedy algorithms are worst-case near-optimal for explainable $k$-means clustering (in [11, 18]). Worst-case optimality here means that there is an instance where greedy outputs the best possible explainable clustering tree overall for that instance, so no loss is incurred due to the use of a greedy approach over the intrinsic cost of explainability. Together with the obvious efficiency benefits of greedy algorithms, it seems a natural approach for explainable clustering with other reference clusterings as well, even though it remains possible that the greedy approach is not optimal in general.

how the bound in Theorem 2.2 directly translates to explainable clustering

In summary, the bound shows that there exists a coordinate threshold cut whose conductance (left-hand side) is bounded by the clusterability of the point set (right-hand side). The intrinsic explainability model from [31] defines explainability by coordinate threshold cuts, and the conductance quantifies the loss in accuracy between $M^*$ and $M’$, hence the bound shows the existence of intrinsic explainability with bounded loss in accuracy.

why these specific embeddings were chosen

CLIP [34] and SentenceBERT [35] are standard, public and widely used methods for generating numerical embeddings for images and for text (respectively), currently used as standard across ML in research papers and applications, and were therefore a natural choice.

the parameter $k$ for SPEX-kNN

The $k$ parameter in kNN graph construction is a long studied topic in ML. Very small $k$ may lead to bad or disconnected graphs due to too few edges, while very large $k$ may lead to connecting faraway and dissimilar points, and therefore intermediate values are recommended. The common guideline is to test values in the range 10-20 empirically with the “elbow method” that selects the value where performance plateaus before degrading. This is the procedure we followed except that we chose a single value across all datasets for methodological uniformity and soundness.

detailed time complexity analysis

Please see the response to eAyA for the time complexity analysis.

Thank you for your valuable review and support!

Can you provide more insight or analysis into the observed gap between low- and high-dimensional datasets?

The main source of the gap is the axis-aligned nature of explainable clustering: the number of coordinates that the decision tree reads from every point is at most the depth of the tree, hence if the number of clusters (and thus the depth of the tree) is much smaller than the dimension, the tree has to make clustering decisions based on only a small fraction of coordinates. This renders high-dimensional datasets more difficult to cluster with explainability.

Could you bring Tab. 1 and Tab. 2 into the main text paper?

Yes, we will add it.

Could you add further discussion on the complexity of the algorithms?

SpEx as well as the baselines share the following high-level structure. In each tree node $u$ with $n_u$ points, for each coordinate, they sort the points by that coordinate (time $O(n_u\log n_u)$) and compute a score for each of the $n_u-1$ possible prefix/suffix cuts (time $O(n_uS)$, where $S$ is the time to compute a cut score). Repeating this for all coordinates takes time $O(dn_u(\log n_u + S))$. In each tree level the sum of $n_u$s over the nodes $u$ in that level is $n$ for SpEx and CART, and $n+k\leq 2n$ for IMM and EMN, so the time per level in all of them is $O(dn(\log n + S))$. Summing over up to $k-1$ levels in the tree, the total time is $O(kdn(\log n + S))$.

Where the algorithms may differ is in the score they use and the time $S$ it takes to compute it. This requires analyzing each algorithm separately, since they use different scores, but it turns out that in all of them (IMM, EMN, CART, SpEx) the score can be computed in time $O(1)$ with a sweep-line procedure (more precisely, the score can be updated in time $O(1)$ as we iterate over prefix/suffix cuts). In the graph-theoretic lens from section 3, whether the score admits an efficient sweep-line procedure depends on the graphs $G,H$: generally if they are highly structured (like the clique, star, IS, etc) then such procedure is possible. Thus all algorithms have the same asymptotic time complexity $O(kdn\log n)$.

choice of the number of leaves $\ell$

discussion on the interpretability of decision trees with a large number of leaves (e.g., 100 leaves). Are large decision trees really interpretable?

These are important inter-connected points. The setting of $\ell$ relative to the number of reference clusters $k$ is a use-case dependent choice that governs how much the user prioritizes explanability versus accuracy. Viewing clustering as an unsupervised ML model, the number of reference clusters $k$ is the number of possible model outcomes, and the number of leaves $\ell$ in the explainable decision tree is the number of explanations. Since each outcome must have its own explanation, we must have $\ell\geq k$. The case $k=\ell$ is the most explainable since there is one explanation per outcome – e.g., “age in [range] and zip code in [range]” for assignments to public schools. As $\ell$ is increased, accuracy improves since a bigger tree is better able to approximate the reference clustering, however explainability degrades as now the same model outcome would have multiple different explanations (e.g., “age in [range] and zip code in [range] OR age in [range] and GPA above [bar]”). In the limit each point may have its own separate explanation, which is in a sense no explanation at all.

Thus, we agree that if the number of leaves is much larger than the number of reference clusters, the decision tree can no longer be considered truly explainable. This is why we focused on the most explainable case, $\ell=k$. In the response to K9ow we include additional experiments with $\ell=2k$ for reference.

What happens if I decide to prune the trees after finding them?

Since pruning decreases the number of leaves, it could help in pruning a tree constructed with $\ell>k$ leaves back to $k$ leaves (or to an intermediate value). Since pruning has the “benefit of hindsight” over greedy partitioning, it could potentially lead to better trees, depending on the pruning policy. This is an interesting direction to explore.