SpEx: A Spectral Approach to Explainable Clustering
Authors: Tal Argov
Tal Wagner
Venue: NeurIPS 2025 poster ()
Keywords: explainable clustering
spectral clustering
interpretable clustering
cheeger
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We develop a new approach to explainable clustering as defined by Moshkovitz et al. (2020) based on spectral graph theory

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.

SPEX: A Spectral Approach to Explainable Clustering
Tal Argov Tel Aviv University talargovi @mail. tau. ac. il
Tal Wagner Tel Aviv University talwagStauex tau ac. il
Abstract
Explainable clustering by axis-aligned decision trees was introduced by [33] and has gained considerable interest. Prior work has focused minimizing the price of explainability for specific clustering objectives, lacking general method to 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 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 generalized framework due to [45] wherein cuts are optimized in two graphs simultaneously. Our experiments show the favorable performance of our method compared to baselines on range of datasets.
1
Introduction
As machine learning increasingly permeates daily life and forms the basis for consequential decision making in the real world, explaining its outputs in manner that is interpretable humans often becomes imperative. In a recent influential work, Moshkovitz al. [33] pro- posed a model of explainability in clustering. In their model, clustering of points ture space I is explainable if it is described by a binary decision tree, where each internal node corresponds to thresholding the points along single coordinate. Thus, the assign- ment of points to clusters can be described by sequence of individual feature thresholds, ar- guably making it easy to explain and interpret. See Figure for illustration.
x x
y y
fea-
2
Figure 1: Illustration of explainable clustering.
Clusters are generated from three gaussians. The dashed lines on the left and the decision tree on the right define the explainable clustering regions, with some points attributed the wrong cluster.
Moshkovitz et al. [33] presented the Iterative Mistake Minimization (IMM) algorithm, which takes as input an already computed k- k-medians or k-means clustering of the data, called the reference clustering. and "rounds" into an explainable clustering, It works by fitting the reference clustering with decision
that greedily minimizes wrong point-to-cluster assignments. They proved that the loss in clustering cost, called the price of explainability, can be bounded as function of k. This has led surge of theoretical work on bounding the price of explainability, culminating in tight bounds for k-medians and nearly tight bounds for k-means [26, 28, 30, 31, 32, 12, 7, 19, 20, 4, 27].
This voluminous body of work has far mostly focused on k-medians and k-means. These methods require the reference clustering to be endowed with centroids in order to work. This fails to capture widely used notions of clustering that do produce centroids, like kernel k-means or spectral clustering [40, 10, 47], which one might wish to use as the reference clustering. [15] recently took
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Figure 2: Left: The two-moons dataset admits an explainable clustering with small error. k-Means clustering will fail to capture the moons if used reference clustering. Kernel k-means and spectral clustering capture the moons correctly, and can be rounded to the optimal explainable clustering. Right: A 3-way clustering example from [33]. The horizontal cut leads error-free explainable clustering if chosen at the first step, but CART will select the error-heavy vertical cut first.
a first step in this direction, introducing the Kernel IMM algorithm, which extends IMM to handle kernel k-means the reference clustering, for certain types of kernels.
Ideally, one would want a generic explainable clustering method that can be composed over any given reference clustering, irrespective of how it was computed, whether it has centroids, any other constraint. The only such approach at present is through repurposing classical methods for supervised classification with decision trees, which predate the definition of explainable clustering by decades. CART [6, 37] is a method for decision tree learning over a labeled dataset,' which outputs a tree with nodes corresponding feature thresholds and leaves corresponding to class labels, with the aim of minimizing classification errors with respect to supervised labels. Thus, given any reference clustering, its cluster assignments can be viewed supervised labels, and CART can be used to round it into an explainable clustering.
L Limitations of current methods. As discussed above, explainable clustering methods that require centroid-baud bbased reference clustering, like k-means, are unable to handle cluster structures not captured by centroids. This was the motivation in [15], who gave the example of the classical "two moons" dataset, depicted in Figure 2 (left). Since k-means fails to capture the moon structure, any explainable clustering method built it as the reference will fail as well. On the other hand, kernel k k-mmans and spectral clustering capture the moons correctly, and can be rounded to the explainable rounding depicted in the figure, with small number of errors.
While the Kernel IMM algorithm does not require centroids, specific kernels, and varies by the specific kernel. Hence, it cannot be used as a generic method. Furthermore, the method is rather complex, and is evaluated in [15] on datasets of size only up to hundreds of points, leaving its scalability unclear. Our larger scale experiments indeed show that Kernel IMM becomes infeasible on bigger data.
limited to kernel k-means with
The CART algorithm, as mentioned above, can be repurposed for explainable clustering even though it is not designed for this task. To demonstrate its drawbacks, [33] gave toy example where CART fails to find simple error-free explainable clustering. It is shown in Figure 2 (right). and we revisit this example more detail in Section 3.3. There have been some questions whether this failure mode is representative of behavior on real data, or merely pathological case not encountered in practice." Preliminary small scale results in [15] implied that CART performs well empirically. However, our larger scale experiments will show that CART indeed suffers low performance on real data.
The upshot is that despite a large body of work, there no generic method for explainable clustering, which is oblivious to the type of reference clustering and robust across datasets. This is the gap that we address in this work.
Our results. We introduce a new approach to explainable clustering, based on spectral graph techniques. Cheeger's 's inequality relates the cigenvalues of graph to its optimal cut conductance, fundamental graph partitioning objective that yields high-quality cuts. This useful fact is widely used
!CART is fact family of algorithms for Classification And Regression Trees (hence its name). The specific form CART used in explainable clustering is detailed later, in Section 3.3. See also Section B. "See the peer review discussion for [15] https htttp:://openae /pwnrevieeeeeeeee net mett/ooummiddFAGttt

---

in algorithms. A geometric consequence of it, stated in Theorem 2.2, relates coordinate cuts in I' to cut conductances in the graph, provided that the graph usefully captures geometric relations between the data points in Rd. This hints at relevance to explainable clustering.
We this connection in ways:
SPEx-Clique:
We may describe any given reference clustering with a graph that contains clique over each cluster. Applying the spectral result iteratively to this graph leads to an algorithm that can round any given reference clustering, without limitations, into an explainable clustering.
SPEX-KNN: We may also use the spectral result on graph built directly on the dataset in R like the k-nearest neighbor graph. This leads to a "reference-free algorithm, which computes an explainable clustering directly from the data, without using reference clustering at all.
To gain more insight into existing methods and their relation ours, we show they are captured by generalized graph partitioning framework of non-uniform sparse cuts [45], allowing us to view them through a unified analytic lens. Namely, prior methods can be seen as different choices of graphs to describe the reference clustering.
Our experiments on range of datasets and baseline shed light on the empirical performance of explainable clustering methods and showcases the advantage of our approach.
1.1 Related Work
Much work has focused on proving multiplicatiie bounds on the price of explainability for k-medians and k-means. In deterministic algorithms, IMM [33] achieved ((k) for k-medians and O(k2) for k-means. [12] improved the k-means bound to O(k log k), with algorithm we will call EMN.
Randomized methods have enabled better bounds. For k-medians, sequence of works analyzed a natural randomized procedure and ultimately obtained tight bound of (1 + o(1) In & [30, 32, 12, 19, 20]. For k-means, [20] achieved O in In k), which tight up to the In In l term. Some works have also shown better bounds in the oow-dimesiional data regime [26, 12, 7], and studied the computational complexity of approximating the optimal explainable clustering [4, 20, 27].
Some works have used modified or extended definitions of tree-based explainable clustering [16, 18, 25, 41, 46, 35]. In particular, [18] generalized the definition far beyond [33], allowing oblique (hyperplanc) cuts that involve multiple coordinates rather than just single coordinate cuts. This greatly increases the expressive capacity of the resulting clustering-in fact, [18] show can exactly capture any reference k-means clustering, without any "price of explainability" tthough arguably at the price of rendering the clustering less explainable. While defining explainability in clustering remains an open-ended question, in this work we focus on the original explainability model of [33].
In the broader context of explainable machine learning, the model of [33] is example of an intrinsically explainability method, where the given model (in this case, the reference clustering) is approximated by different model (in this case, the explainable clustering tree) on which structural explainability constraints are imposed. This is in contrast with post-hoc explainability methods, which aim to endow the given reference model with explanations without modifying it.
2 Spectral Explainable Clustering
We begin with some necessary background and notation on graph partitioning. Let G(X, E, w) be undirected graph. Given strict non-empty subset 5 X, let (S, (S) denote the sum of edge weights crossing between S and X \ S. and let (Sl denote the sum of weighted degrees of nodes in 5 (called the volume of 5).
There are two standard notions for quantifying the outer connectivity within G (see [47]):
(c(S) = (S : (G(()) = (G, ())
|S|
vola(S)
(G(S) is called the sparsity of S, while (S) is called the conductance of S. Both notions have analogues for considering S and its complement X \ as two-way cut:
(S) CG X \S)
es(S, X 5)
SS] X S ; PG(S)=
(2)
volo vola(S) volo (S)
[X
3

---

(S) is sometimes called the ratio cut objective [48], while ( is called the normalized cur objective [42]. These objectives sometimes appear in the literature slightly differently, with 1 same as Equation (2) up to a factor of since 2 min (s, n 8} S 88 (n 8) S min(s, n
min[|S]. X } and min(vol((S). vola (X) S)} as their respective denominators. These are the
for all () < < which applies here with = |X], [S] in (c()), and with = (X)a(X),
5 (S) in (S))
2.1 The Spectral Approach
Our approach is grounded in the following theorem, which is generalization of a theorem given in [11], based on framework developed by [2. 3]. in the context of nearest neighbor search. It relates coordinate cuts in I' to the Cheeger inequality [1. 8], fundamental result in spectral graph theory with myriad of algorithmic implications. While they stated the theorem specifically for the nearest neighbor graph of point set in Rdd, it holds for general weighted graphs over points in R. as we now state. We provide a proof in Section A.
Definition 2.1. Let X C Rd. The coordinate cut given by coordinate j {l...., d) and threshold T E R is S,, (X) = { E X : I T). The cut valid if S (X) + and S (X) X.
Theorem 2.2. Ler X C Rd be a set of points, where x E X has coordinates x = (II...., T.). G(X, EXK,E,u E, be graph with vertex set X. Consider distributions over pairs of points in X:
Let
Dadj is the distribution over adjacent pairs in G, where a pair y E sampled with probability proportional to the edge weight between them.
Dan is the distribution over all pairs y E X, where x and y are sampled independently. each with probability proportional to its weighted degree in G.
Then, there is a valid coordinate cul J.T such that
EasyDaaill |
3/12
V Va (x)) $
Ex.gr yll
Intuitively, the theorem draws connection between combinatorial graph cuts and geometric proper- ties of the set of points: if the graph nodes graph are associated with embeddings in Rd, then there is "good quality" graph cut, whose conductance is upper-bounded in terms of the squared Euclidean distances between the node embeddings. Furthermore, that cut is coordinate cut.
The conductance bound is governed by the ratio of expected squared distances in X according to two distributions over pairs of points: the numerator samples pairs of points adjacent in G. while the denominator samples any pair of points. Thus, the ratio (and hence the cut conductance) is smaller when G captures a geometrically meaningful structure in the dataset, wherein adjacent pairs of points expected to be nearer to each other than general pairs of points.
This implies an approach explainable clustering. Given a reference elustering, we can describe it with suitable graph G, and iteratively look for the coordinate cut with minimum conductance in each node of the decision tree. the reference clustering is of good quality, in the sense that a pair of points are expected to be nearer to each other if they are clustered together, then Theorem 2.2 guarantees the existence of low-conductance cut. At the same time, since the nearness of points in the same cluster is "soft" requirement (it only needs to hold in expectation). it renders the theorem robust to various types of clustering, allowing for unconstrained cluster shapes, outliers, etc.
Another possibility that arises is to dispense with the reference clustering, and construct a graph that captures ncarness/farness directly from the dataset. In Section 2.2 we describe the explainable tree construction with general graph, and in Section 2.3 we discuss graph selection.
2.2 Iterative Tree Construction
Given graph G(X, E, w) over the dataset X Rd our task is to construct explainable clustering decision tree T. Let > 0 be the desired number leaves.
An explainable clustering tree is a decision tree in which every internal node is associated with coordinate j. E (1....,() d) and a threshold TU E R. inducing the condition Ty, S To given a point E R. The coordinate thresholds associate subset X, C. X with each node v: the root is associated

---

with X, and every non-root e with parent a is associated with X, = Sjurt (Xu) if v is the left child of u, or X X, ja, (X,,) if it e the right child of u.
Let L(T) denote the set of leaves in T. They induce partition of X into clusters, X X.. We measure the quality of by a generalization of the normalized cut objective to multi-way partitions [47]:
Algorithm SPEX
input: Dataset X F graph G E, w), target number of clusters f
output: Decision tree T where every internal node is associated with coordinate j and threshold r
CT(
Σ vo((X.) vEC(T)
BUI.DTREE( X, G,
T mitiialize tree with a single node v
J. T argminj,- " CUTSCORF( j,
The smaller (T),,, the better the partition induced by its leaves. Note this generalizes the
Q <- initialize a maximum priority for the tree leaves, with priorities given by LEAFSCORE
two-way cut objective ( (Equation (2)),
Q push(r, j.J
since ( (S) + 1 (X) ())
while T has less than E leaves do
To build the tree, we start with T' containing only a root. As long as I" does not yet have the requisite number of leaves l, choose the leaf to split next to greedily minimize (T) Splitting a leaf y with a cut S C X2 replaces the summand (X,,. in Equation (3) with the +/o S)) and thus is chosen to maximize the reduction in (G) its split would yield, which is
U, Ju To + Q.pop() Associate e with the cut j.
Split into two new leaves UL, UR Xu, f S S1..T. (Xx) Xol X, Xuz
JL, arrgmmnn,, CUTSCORR(X P
ja, Tn arrgmin,,, Degninn,CUTSSCREEE (X
Xo. Q.push X.n..unn X TR)
t/a (x.) - min (#a(5) + (x \ ()), (4)
return T
CUTSCORE X ; j): if (X) 9 or S X then return 0c return ()a(S),((X)) + vo(X, (X))((())
where S ranges over all valid coordinate cuts. We associate v with the Je, Tu corresponding the minimizer S, split v into two new leaves along this cut, and repeat. See Algorithm 1.
Note that Algorithm 1 has the flexibility to produce a tree 7 with any desired number of leaves, regardless of the number of clusters in the reference clustering. In contrast, centroid- based methods like IMM, EMN and Kernel IMM are bound produce the same number of leaves in I' as the number of centroids in the reference k-median or (kernel) k-means clustering, and increasing the number of leaves requires separate techniques [17, 31, 15]. Increasing the number of leaves is helpful for attaining smaller price of explainability due to the increased expressivity of T, albeit at the expense of being less explainable due its bigger size. We discuss this further in Appendix Our main evaluation will focus on producing trees with the same number of leaves as clusters in the reference clustering.
LEAFSCORE(1: Xv, jj.): return (X') - CUTSCORE(X".) (...)
2.3 SPEx-Clique and SPEX-kNN
To capture given reference clustering with a graph, there are several natural choices:
Clique graph: points are adjacent if and only if they are in the same cluster (thus, every cluster becomes clique).
Star graph: if the reference clustering is endowed with centroids, each point can be made adjacent to its cluster centroid (thus, every cluster becomes star).
Independent set (IS) graph: points are adjacent if and only if they are not in the same cluster (thus, every cluster becomes an independent set). This is the complement of the clique graph. Here, of course, one would wish to maximize rather than minimize the cut objective.
The clique graph may seem like the most natural choice, and this is indeed the one we make. Perhaps surprisingly, as we will show in Section 3, when previous methods (IMM, EMN, CART) are interpreted through this graphical lens, they turn out to correspond to either the star graph or the IS graph. This directly relates to their limitations, like requiring centroids (in the case of the star graph) or failing the toy example from Figure (in the case of the IS graph).
5

---

Given any reference clustering, using the clique graph as G in Algorithm yields the algorithm we call SPEX- We also consider an variant that uses no reference clustering, by constructing the nearest neighbor graph directly on the points in X. This yields the algorithm we call SPEX-kNN.
2.4
Computational Efficiency
SPEx as well as the baselines we consider share the following high-level structure. In each tree node with nu points, for each coordinate, they sort the points by that coordinate (time O(n., log n..) and perform a sweep-line procedure that iterates over the nh -1 prefix/suffix cuts by moving nodes from the suffix to the prefix one at a time. As each node is moved, the cut score is updated accordingly (let S denote the time it takes to update), and eventually the cut with the overall optimal score is selected. Repeating this for all coordinates takes time (dd,,, (log n + S)). In each tree level, the sum >n, uu. n for SPEx and CART and n + < 2n for IMM and EMN, therefore the time per level is O(d (log + S)). Summing over up to k levels in the tree, the total time is O(kdn (log n + S)).
The algorithms may differ the time S it takes update cut scores during sweep-line. In SpEx-Clique, we need not store the entire clique graph; rather, we only store point-cluster assignments (O(n) memory). During sweep-line, we maintain two cluster histograms for the prefix and the suffix (O(k) memory), from which the cut score can be updated in S = ((1) time. In SPEX-kNN, letting k denote the number of neighbors per node (note that this is different parameter than the number of clusters k), we can store the KNN graph in (πx) memory and update cut scores in S = (()) time.
3 Lens: Non-Uniform Sparse Cuts
While our spectral approach to explainable clustering may seem rather different from previous methods, in this section we show a generalized graph partitioning framework that captures them in unified way. It is based on non-uniform sparse cuts as defined by Trevisan [45], where cuts are optimized simultancously in two graphs that share the same set of nodes.
Trevisan [45] defined the Non- Uniform Sparsest Cut problem as follows. Let G(X, Ec, we) and (X,, Eh Wx) be two graphs on the same set of nodes X. The (G. -Spsprsitty of cut (S, X ()) is defined as the (normalized) ratio of edges cut in G to edges cut in H:
VG (S) (X) (G S)
[X] eH (S, X ()
The goal in the Non-Uniform Sparsest Cut problem is to find the cut with the smallest V (S).
In [45] it is observed that this generalized graph partitioning problem captures several classical problems defined on single graph G as special cases:
The classical ("uniform") Sparsest Cut problem, of minimizing (G(S) from Equation (2), is the case of G, (S) where H is an unweighted clique over X.
The Normalized Cut problem, of minimizing (S) from Equation (2), is the case of V (S) where H is the G-degree weighted clique over X, in which the edge weight in H between every pair x. y.yyC E X is the product of their weighted degrees in G.
The Minimum st-Cut problem is the case of VG.H( where H contains a single edge between a "distinguished" pair s, E X.
Here, further observe that this framework is useful in capturing prior methods for explainable clustering (or close variants of those methods), as they in fact produce coordinate cuts that minimize I Vo,n(( (5) with partieular choices of graphs G and H, even though neither method is originally given in terms of graphical sparse cut terms.
IMM [33] corresponds to G being the star graph over given reference clustering endowed with centroids, and H containing single edge that connects a pair diametrical (furthest) centroids. EMN [12] also corresponds to G being the star graph, but with H being an unweighted clique over the k cluster centroids.
CART closely corresponds to H being the independent set (IS) graph over the reference clustering (see Section 2.3), and G being the H-degree weighted clique.
We now discuss each algorithm in turn, and highlight useful implications of this graph-theortic lens.

---

3.1 IMM as Non-Uniform Sparse Cut
Given a reference clustering C (CI,..., Ck) endowed with cluster centroids M (ull) ,...,,... ) the IMM algorithm builds decision tree which every node u is associated with subset X C X U M of points and centroids. In each node, it chooses the coordinate cut that minimizes the number of "mistakes", i.e., of points placed different side of the cut than their centroid, while separating at least one pair of centroids. Formally, for z E X. let (u(z) denote the centroid of the cluster containing x. The cut S C Xx in a node u is chosen by IMM to minimize,
mis, = 1 E S: ((x) E X, X. (SJUff Xa SS: p(x) E));
among all coordinate cuts S that satisfy μ(() E S and (((0) E X \ S for at least one pair vl() (,01), E M O Xu- The construction terminates when each leaf in the tree contains exactly one centroid.
To cast this as non-uniform sparse cut, consider a slightly modified variant of IMM. For each node u, Let "e" E X,, be a pair of centroids at maximal distance among the centroids in M n X,. Choose the coordinate cut S C X,, that minimizes mis,, among those that separate , "."..T This is a subset of the cuts in the original IMM. For this variant, let G be the star graph over the reference clustering, and G, = G[Xu] be its restriction to the subset X,, C X U M associated with each tree node u. Then mis, (S) = eG. (8, X \ S), since each cut edge marks a point separated from its centroid. Let Hu be the single edge graph over Xx, that contains only an edge connecting μ and μ". Then we have, CH Xu \S) = 1 if the cut (S, X,, \ SS) separates p²","" and CH., (S, X \S)
otherwise.
Thus, minimizing (S) subject to a cut separating μ p² is equivalent to minimizing the ratio ea. (S, Xx, \ SS/EH,.(. (S, X, S). This is equal (up to normalization) HH, (S). Even though this modified IMM considers less cuts than the original IMM, it attains the same price of explainability for k-medians, by a different proof based on graph partitioning, that avoids the intricate potential function analysis in [33]. We show this in Section A.3.
the non-uniform cut sparsity,
3.2 EMN Non-Uniform Sparse Cut
The EMN algorithm [12] is an improvement of IMM by the following modification: in every tree node instead of minimizing (S), it chooses the threshold coordinate cut S C X2 that minimizes the ratio mis,, (S),f(()) where [12] define (S) = min n (X,, \ 5) n MI)- As with IMM, letting G2 be the star graph over the reference clustering when restricted to X., have mis,, (S) = eg.. (S. Xx, \ AS). Let Ha be the graph with vertex set X,, whose edges form an unweighted clique over M ( X,, (the rest of the vertices in X, are isolated in H.). Then,
en., (S, X,, \S IS M) 1Xx, (S) M).
Recall from Section 2 that ff)( |MXXI eH., (S, A) < fu(S). Thus, minimizing the ratio mis, (S)) is equivalent, up to a factor of 2, to minimizing the ratio eg. (S, X,, \ S)/en, Xn, (). This is equivalent to minimizing the non-uniform cut sparsity VG,,HH (S).
3.3 CART as Non-Uniform Sparse Cut
We first review the CART algorithm in the form used in explainable clustering. The Gini impurity of a distribution (Pi....,Pay Pk) over & elements is defined as v(p) = =E p1(1- - pt). Given a point set X C Rd, a reference clustering C = {C1, ..., C2), and subset S C X, we may define a distribution (S) over the clusters as (e() = |srci] |snCal
[SnCk] [S] [S| ..... [S] which corresponds to sampling a uniformly random point from S and returning its cluster ID. The impurity of S is defined as vc(( (SP), and the impurity of (8,X) \ S) as a two-way cut as,
|S| X
vc(S) + |X \ S) |X]
Ye(S, X ()
ve(X S).
The CART algorithm builds a decision tree starting with a root node associated with all of X. It then iteratively chooses a leaf node whose associated subset X' maximizes score(X') = (X') minsex x (S(S, X' \ 5), where S ranges over all coordinates threshold cuts, and splits that leaf across that cut. The score captures the impurity reduction gained by splitting X' along its best cut. Note how this is analogous to Equation (4) in SPEX.
7

---

Table 1: Datasets. Training set only.
'Embedded with CLIP [38].
'Embedded with SBERT [39].
CIFAR-10" 20Newsgroups"
MNIST
Caltech 101
Bcans
Breast Cancer
Ecoli
Iris
Points
50,000
11.314
60,000
8677
13,611
569
336
150
Dimensions
512
7681
512
512
16
30
7
Classes
10
20
10
101
2
8
Reference
[24]
[5]
[29]
[13]
[23]
[44]
[21]
[14]
Now, we show that a small modification CART equivalent case of non-uniform sparsest cut. Let H be the independent set graph over the reference clustering C (see Section 2.3). For subset C X, Let or (S)) denote the sum of edge weights with both endpoints in S. We can now interpret the impurity (S) of a subset S C X as,
UC(()) = Σ
*
ssnc S
1
S C = |S|
Σ
(| - (Sn 2 2.
[S]
|S|
Thus, the two-way cut impurity becomes
(H) |||
a (X \15)) X X S
Tc(s, X 5)
(5)
X
To proceed, we make the modification of replacing set cardinalities with their volumes in H, as in the transition from sparsity to conductance in Equations (1) and (2). We get the modified two-way cut impurity, instead of Equation (5):
2
H (S)
ax { x ())
Tc(S, X () voln(())
This is precisely (up to normalization terms) the Nassoc graph cut objective defined in [42, eq. (3)).² As they observed, it is directly related to the normalized cut objective, i.c., to the cut conductance:
V H (S) = volx(X)
2
Thus, finding a coordinate cut S that minimizes our modified impurity T is equivalent to maximizing the usual cut conductance ! n (S) in H. This, turn. equivalent to maximizing the non- uniform cut sparsity V (S)), where H is the independent set graph and G is the H H-degree weighted clique over X, since (as observed in [45] and mentioned in the beginning this section), for this choice of graphs it holds that V (.)((S) V W (S), up to normalization. Finally, since V (S) = H by definition, this is equivalentt minimizing the non non-uniform cut sparsity (S))
This point of view clarifies the failure of CART in Figure 2. The IS graph over a reference clustering incentivizes cuts that separate pairs of points residing in different clusters, but has no incentive to not separate points residing in the same cluster, since they are not connected with any edges and hence have no effect on the cut value. Since CART maximizes number of edges between the bottom clusters (vertical cut) over the smaller number of edges between the top cluster and each the bottom clusters (horizontal cut), which is incompatible with clustering.
conductance, opts to cut the larger
4 Experimental Evaluation
We evaluate our methods compared to baselines, on eight public real-world datasets of various sizes and dimensions, detailed in Table Our code available online.*
Our algorithms. We focus on two instantiations of our method: SpEx-Clique with spectral clustering the reference, and SPEx-kNNWhere the k-NN graph is constructed with k = 20. Section B includes additional results for SPEx-Clique with k-means and kernel k-means as the reference clustering, and for SPEX-KNN with other values of k.
Baselines. We evaluate the following baselines:
PIn notation [42], ou (S) = aSsoc((, S) and vol = assoc(S, X).
chtttp::/githha www.//oo/aaaaeeeeea com/tallrgv//pEx.
8

---

Breast Cancer, ARI
Breast Cancer, AMI AMI
Ecoli, ARI
Ecoli,
Iris, AMI
Beans, ARI
Beans, AMI
50
86
$0
12
CIFAR-10, 10, ARI
CIFAR-10, AMI
Caltech-101, ARI
Caltech-101, AMI
30
44
60
MNIST, ARI
MNIST, AMI
20newsgroups, ARI
20newsgroups, AMI
3.0
10-
1.
1.0
SpEx-Clique (ours)
SpEx-kNN (ours)
EMN
00
CART-k-means
CART-spectral
Kernel-IMM
Figure 3: Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI), higher is better.
EMN [12], the state of the art for explainable clustering with k-means as the reference clustering. Note that EMN cannot work with spectral or kernel k-means reference clustering, its operation requires the reference clustering to have centroids.
CART, with both k-means and spectral clustering the reference clustering.
Kernel IMM [15], which uses kernel k-means as the reference clustering.
Our experiments indicated that Kernel IMM does not scale well, failing to run on the larger scale datasets. We therefore report its results only for the three smaller scale datasets (Breast Cancer, Bcoli, Iris), which are the ones used in [15]. See more in Section B.
Evaluation measures. The classes of each dataset are used as groundtruth clusters. To evaluate each method, we report two standard (and incomparable) measures of clustering agreement between two clusterings of the same data: Adjusted Rand Index (ART) [22] and Adjusted Mutual Information (AMI) [34]. Each is explainable clustering is evaluated for its agreement with the groundtruth clustering through these measures.
4.1 Results
Main results are reported in Figure 3. Tables 2 and 3 augment them with additional choices of reference clustering for 3PEx-Clique and CART and list ARIs with respect to the reference clustering. They also contain synthetic small-scale datasets, R15 and Pathbased, used in [15]. Appendix B includes additional results.
The results show that ApEx-Clique is the most consistently nigh-performing algorithm. It outperforms each baseline in most cases in both evaluation measures, and never exceeded by more than one baseline at the same time. SPEX-KNN is highly effective particularly on the low dimensional datasets

---

Table 2: Results on smaller datasets. Rows are grouped by reference clustering, shown as the first row in each group. The REF column lists the ARI with respect to the reference clustering (rather than the ground truth as in ARI column). Best scores per reference clustering are in bold.
R15
Pathbased
Ecoli
Iris
Cancer
Algoritim
ARI
AMI
REF
ARI
AMI
REF
ARI
AMI
REF
ARI
AMI
REF
ARI
AMI
REF
REF: Spectral
-526
.570
.711
.653
1.
.630
.661
.26
SPEX-KNN
982
-987
989
332
.410
.55
.679
.642
863
450
.647
450
.507
.400
.562
SpEX-Clique
.966
.411
.517
.824
662
.621
847
.576
.787
.785
CART
.96
.989
.993
441
.517
.824
.672
.618
.886
.576
.69
.787
683
360
.811
REF: 6-means EMN Clique
.611
.489
.609
.966
.989
.993
.461
.543
1.
.466
.559
.873
.576
.629
.772
.491
.664
1.
.543
.466
.559
.873
CART
.986
.989
.993
.421
.507
.897
.454
.543
.440
.576
.629
.772
.491
.464
1.
REF: Kernel k-means
.908
.967
919
.888
.538
.612
1.
.731
.767
.116
.228
Kernel IMM
.904
.962
.986
.614
.614
.583
.522
.560
.448
.732
.788
.924
.127
.241
.93
SPEX-Clique
.94]
.951
.479
.553
.450
.529
.573
.851
.732
.788
.924
.414
.511
CART
.682
.876
.759
.479
.553
.450
.500
.558
.824
.732
.788
.944
.406
.414
.511
Table 3: Results on larger datasets.
MNIST
Caltech 101
Newsgroups
Beans
Cifar
Algoridum
ARI
AMI
REF
ARI
AMI
REF
ARI
AMI
REF
ARI
AMI
REF
ARI
AMI
REF
REF: Spectral
.745
.820
.563
.859
1.
.431
.671
1.
.586
.677
1.
.712
.801
SpEx-KNN
.092
.338
.150
.121
.497
.168
.042
.170
.574
.690
.649
.342
.434
.373
SPEX SPEx-Clique
.217
.384
.282
.247
.521
.303
.078
.223
.189
.564
.671
.743
.320
.438
.394
CART
.027
.148
.030
-010
.008
.078
-013
.542
.036
.169
.035
REF: k-means
.364
.481
.405
.822
.502
.660
.572
.689
.636
.738
EMN
.25
.342
.42
.249
.548
.416
.115
.219
.163
.563
.688
.780
.314
.402
.387
SPEX-Clique
.209
.336
.403
.122
.495
.195
.098
.249
.128
.562
.687
.773
.288
.410
.370
CART
.124
.299
.229
-017
.082
.003
.005
.092
.006
.536
.669
.757
.045
.180
.037
(Beans, Ecoli and Iris).² On these datasets, it outperforms all baselines as well as SPEX-Clique, with the exception of Kernel IMM Iris."
CART performs well on the smaller datasets (confirming similar results reported in [15]), however, performs poorly on the larger datasets. Recall that CART is not originally intended for explainable clustering, but can be repurposed for it since it produces a structurally compatible output (a binary decision tree with coordinate cuts). In Sections 1 and 3.3, discussed toy example from [33] that demonstrates a failure mode of CART for explainable clustering due to its incompatible objective. Our experimental results indicate this incompatibility may also impede its performance real data.
Conclusion and limitations. Prior work on explainable clustering has focused on a few specific reference objectives, allowing to prove worst-case approximation bounds tailored to them (cf. Sec- tion 1.1). SPEX, on the other hand, fills the gap of a generic, referencc-obllivoous method, currently lacking in the literature. Thus, while theoretically well-grounded (Theorem 2.2, Section 3), it cannot offer such bounds. Other methods may be better choices for some specific reference objectives - e.g., EMN known to be near-optimal for k-means, and Tables and indeed show that generally better than SPEX for that reference objective. SPEx is better for data where objectives already well-studied explainable clustering (like k-means) fall short, and more versatile objectives (like spectral clustering) are needed. As future work, it would be interesting to explore if the theoretical framework we develop can yet lead to formal approximation bounds for some of these objectives.
'These datasets are of dimension up to 16. The other datasets have dimension at least 30.
'On Iris, kernel k-means significantly outperforms spectral and k-means as the reference clustering. In Figure 3, only Kernel IMM uses it a reference. When SPEX- SPEX-Clique or CART are run on the same kernel k-means reference, the results they yield are identical Kernel IMM. These results are included in Section B.
10

---

Acknowledgements
This work was supported by Len Blavatnik and the Blavatnik Family foundation and by an Alon Scholarship of the Israeli Council for Higher Education. TW is also with Amazon; this work is not associated with Amazon.
References
[1] Noga Alon and Vitali D Milman. A1, isoperimetric inequalities for graphs, and superconcentra- tors. Journal of Combinatorial Theory, Series B, 38(1):73 -8, 1985.
[2] Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, llya Razenshteyn, and Erik Waingarten. Data-dependent hashing via nonlinear spectral gaps. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 787-800, 2018.
[3] Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. Hölder homeomorphisms and approximate nearest neighbors. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 169-166. IEEE, 2018.
[4] Sayan Bandyapadhyay, Fedor V Fomin, Petr A Golovach, William Lochet, Nidhi Purohit, and Kirill Simonov. How to find a good explanation for clustering? Artificial Intelligence, 322:103948, 2023.
[5] Stephen D Bay, Dennis Kibler, Michael Pazzani, and Padhraic Smyth. The uci kdd archive of large data sets for data mining research and experimentation. ACM SIGKDD explorations newsletter, 2(2):81-83, 2000.
[6] L Breiman, JH Friedman, R Olshen, and CJ Stone. Classification and regression trees. 1984.
[7] Moses Charikar and Lunjia Hu. Near-optimal explainable k-means for all dimensions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2580-2606. SIAM, 2022.
[8] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[9] Eldan Cohen. Interpretable clustering via soft clustering trees. In International Conference Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 281-298. Springer, 2023.
[10] Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference Knowledge discovery and data mining, pages 551-556, 2004.
[11] Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2020.
[12] Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Almost tight approximation algorithms for explainable clustering. In Proceedings of the 2022 ACM--l Symposium on Discrete Algorithmss (SODA), pages 2641-2663. SIAM, 2022.
[13] Li Fei-Fei, Rob Fergus, and Pietro Perona. One-shot learning of object categories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28:594-611, 2006.
[14] Rory A. Fisher. The of multiple measurements in taxonomic problems. Annals of Human Genetics, 7:179-188, 1936.
[15] Maximilian Fleissner, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Explaining kernel clustering via decision trees. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
[16] Ricardo Fraiman, Badih Ghattas, and Marcela Svare. Interpretable clustering using unsupervised binary trees. Advances in Data Analysis and Classification, 125):125-145, 2013.

---

[17] Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian Exkme: Expanding explainable k-means clustering. arXiv preprint 02tx22006.02399, 2020.
[18] Magzhan Gabidolla and Miguel Á Parreira-Perpinan. Optimal interpretable clustering using oblique decision trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 400-410, 2022.
[19] Buddhima Gamlath, Xinrui Jia, Adam Polak, and Ola Svensson. Nearly-tight and oblivious algorithms for explainable clustering. Advances in Neural Information Processing Systems, 34:28929-28939, 2021.
[20] Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, and Rachel Yuan. The price of explainability for clustering. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1131-1148, IEEE, 2023.
[21] Paul Horton and Kenta Nakai. A probabilistic classification system for predicting the cellular localization sites of proteins. Proceedings. International Conference Intelligent Systems for Molecular Biology, 4:109-15, 1996.
[22] Lawrence J. Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2:193-218, 1985.
[23] Murat Koklu and Ilker Ali Özkan. Multiclass classification of dry beans using computer vision and machine learning techniques. Comput. Electron. Agric., 174: 2020.
[24] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[25] Eduardo Laber, Lucas Murtinho, and Felipe Oliveira. Shallow decision trees for explainable k-means clustering. Pattern Recognition, 137:109239, 2023.
[26] Eduardo S Laber and Lucas Murtinho. On the price of explainability for some clustering problems. In International Conference on Machine Learning, pages 5915-5925. PMLR, 2021.
[27] Eduardo Sany Laber. The computational complexity of some explainable clustering problems. Information Processing Letters, 184: 106417,, 2024.
[28] Eduardo Sany Laber and Lucas Saadi Murtinho. Nearly tight bounds on the price of explain- ability for the k-center and the maximum srannnnnspaaigggg clustering problems. Theoretical Computer Science, 949:113744, 2023.
[29] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86:2278-2324 1998.
[30] Konstantin Makarychev and Liren Shan. Near-optimal algorithms for explainable k-medians and k-means. In International Conference Machine Learning, pages 7358-7367. PMLR. 2021.
[31] Konstantin Makarychev and Liren Shan. Explainable k-means: don't 't be greedy, plant bigger trees! In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. pages 1629-1642, 2022.
[32] Konstantin Makarychev and Liren Shan. Random cuts are optimal for explainable k-medians. Advances in Neural Information Processing Systems, 36, 2024.
[33] Michal Moshkovitz, Sanjoy Dasgupta, Cyrus Rashtchian, and Nave Frost. Explainable k-means and k-medians clustering. In International conference on machine learning, pages 7055-7065 PMLR, 2020.
[34] Xuan Vinh Nguyen, Julien Epps, and James Bailey. Information theoretic measures for cluster- ings comparison: Variants, properties, normalization and correction for chance. J. Mach. Learn. Res., 11:2837-2854, 2010.
[35] Louis Ohi, Kernel kmeans clustering splits for end-to-end unsupervised decision trees. arXiv preprint 122. 2024.
Mattei, Mickaël Leclercq, Arnaud Droit, and Frédéric Precioso.
12

---

[36] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
[37] Ross Quinlan. Induction of decision trees. Machine learning, 1:81-106, 1986.
[38] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Interna- lional Conference on Machine Learning. 2021.
[39] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguisties, 11 2019.
[40] Schölkopf, AJ Smola, and KR Müller. Nonlinear component analysis kernel eigenvalue problem. 1996.
[41] Pouya Shati, Eldan Cohen, and Sheila Mcllraith. Optimal decision trees for interpretable clustering with constraints (extended version). arXiv preprint 1rXi: 2023.
[42] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. JEEE Transactions on pattern analysis and machine intelligence, 22(8):888-905 2000.
[43] Daniel Spielman. Spectral and Algebraic Graph Theory. Textbook draft available online, 2025.
[44] William Nick Street, William H. Wolberg, and Olvi L. Mangasarian. Nuclear feature extraction for breast tumor diagnosis. Electronic imaging, 1993.
[45] Luca Trevisan. Is cheeger-type approximation possible for nonuniform sparsest cut? arXiv preprint arXiv:1303.27300 2013.
[46] Nakul Upadhya and Eldan Cohen. Neurcam: Interpretable neural clustering via additive models. arXiv preprini arXiv:2408. 13361, 2024.
[47] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395 2007.
[48] Yen-Chuen Wei and Chung-Kuan Cheng. Towards efficient hierarchical designs by ratio cut partitioning, In 1989 IEEE International Conference on Computer-Aided Design. Digest of Technical Pupers, pages 298-301, IEEE, 1989.
13

---

Impact Statement
This paper is concerned with fitting interpretable explanations decisions made by machine learning algorithms, in this case, grouping of individual points into clusters. While explainability in Al is intended promote safe and ethical use in machine learning, any deployment of automated systems in settings consequential to human individuals may have unforeseen consequences. While our work is not associated with any particular outstanding or new risks, every real-world use of an explainability mechanism in AI should be used with caution and incorporate human oversight, testing, and other use case specific safeguards mitigate any associated risks.
A Proofs
In Section A.I, we provide a proof of Theorem 2.2. In Section A.2, as concrete demonstration, we show an application of it that directly relates the k-means reference clustering cost to the graph conductance in a certain graph that describes the reference clustering. In Section A.3, we provide the modified IMM analysis discussed in Section 3.1.
A.1 Proof of Theorem 2.2
We restate the theorem:
Theorem A.1 (Theorem 2.2, restated). Let X C Bdd be of points, where X has coordinates x = (x1,-..,Ta)) Ra)- Let G(X, E, w) be a graph with vertex set X. Consider the following two distributions over pairs in of points in X:
Dadj is the distribution over adjacent pairs in G, where a pair x, E is sampled with probability proportional to the edge weight between them.
Dan is the distribution over all pairs y E X, where x and y are sampled independently, each with probability proportional to its weighted degree in G.
Then, there is valid coordinate cul j.T such that
Ez.y || 112
Le (o(S),(X)) S
Ex y/
The proof uses arguments that are standard in spectral graph theory, and follows [11] in generalized form (with an arbitrary graph). We include it here for completeness and clarity.
Recall the following standard useful fact,
Fact A.2. Let 01,...; On 0 and b b bn such that E,b; bs Then
a,
Σ, ai
min
<
<
max
bi
Σ, bi
bi
Using it we have,
Er a.y Dadj | 311
F
Pr.yD-Dai
nd
si
1 - Vi ?
E Ex
81/
E Bx,gyDD All i==
5
|r: Di 2
Ex Drr.ynDDan.. Dan [2s Mi 2
Σ Ex,gen Dan [s - yil2
Erayy l0--- y/- 12
min *'(I....d)
(6)
En Dan 22p
2/a
Let |XX be the number of nodes in G. For convenience arbitrarily label them 1,... can index the entries a vector E R by points in X, so the coordinates of z are (z(x)) We do so similarly for matrices in Rax..
Recall that wr(r, u) is the edge weight between x and y G. Let do(x) denote the weighted degree of in G. Let AG En, w(2, y) be the sum of all edge weights. Let Ag E ggnx be its
14

---

weighted adjacency matrix, Ac(r, y) w(z, y). Let DG E R be its diagonal matrix of degrees, Do(2 x) dz).). Let Lg DG Ag Laplacian matrix. standard fact in spectral graph theory is the identity 2" T. En,, w( =))= = for every E IR...
Let 2, R" be the vector with entries defined by z. (x) = I where i" E {l..... d) is the minimizer from Equation (6). Recalling that Dadj is the distribution over pairs z, y with probability
w(x.)) we have
mass Ag
w(1 1)
yn [1:.- Vi-12
Σ
83.-
yE-
Å
2.4
w(x, 11)
(2o(x) - -2o
AG
2.M
2, LGz+
(7)
AG
Let H be a weighted clique over in which the edge weight between every pair 2, y E X is
wH (z. y) do(x) do(())
2Åg
This is the G-degree weighted clique over X mentioned in Section 3, except we scale all weights down by 2 The weighted degree of in H
(x)
Σ wH wH(w,
dc(x)
Σ dc(v)
Ac
da(x)
(2Ac dc(x))
since AG
w(xxz) Σ
1
Σ do(v) yEX
2Ag
= dd(r (da(x))²
2Ac
Let An, DH and Ta DH Ah be the weighted adjacency matrix of H, its diagonal degree matrix, and its Laplacian matrix, respectively. Let uG E R be the vector of weighted degrees G, scaled down by v2Ag:
va(x)= = do(x)
22AG'
Observe that, by Equations (8) and (9),
Dn( dd((x) (da(2))²
if x = and An(x,
0
if
2Ac
(z)
if a +
if
+
2AG
Therefore.
LH = DH - A# = DG vooe
(10)
Now, recall that Dail the distribution over pairs x, y, where a and y ii.d., each with probability proportional to its degree in G. Hence,
de dx(
do(())
Err [0-- yi- 2 2= Σ
| - yi-
2AG
2AG
J.y
WH (z., 12)22 22)12
by Equation (8)
2
3.8
x LH
(11)
2Ag
15

---

Plugging Equations (7) and (11) into Equation (6), we have obtained.
D || y 1
x La
(12)
R | vll
=. I.
Finally, let and denote the all-O and all-1 vectors in R Let ya be the constant "ao 1/2z/11 1 Letting
= -
we have
u0 et
= = v2(22. - 161) = 2
UG 1 O.
(13)
is a standard fact that every graph Laplacian L satisfies L1 = 0. Therefore,
Laz. Lo(2 + ral) = L,²
and, using Equations (10) and (13),
LH LH (3 + 7a1) T, (Da - vGu DGž.
Plugging these into Equation (12), obtain
E Da x v12
ET L.
2
(14)
Ex Dan | - y11
27 DG
Now can state the Cheeger inequality for graphs, or rather, a somewhat more general and useful form of it (see, e.g., [43, Theorem 21.1.3]))
Theorem A.3. Let G(X, E, w) be an undirected weighted graph with n nodes. Let Ag be its weighted adjacency matrix, oG the vector weighted degrees, De the diagonal matrix of weighted degrees, and LG = DG - Ag the Laplacian.
Suppose we huve vector ā E R that satisfies ZFVG = O. Then, there is threshold 7 E RR such that if we consider the cul S = {a X :((x) S f) il satisfies S # 4 X, and
TLG DD
( s $V2
(15)
Theorem A.3 together with Equation (14) imply with conductance
VG(S)= s Ex x 811
Ex v/
given by thresholding the coordinates of 2 at f. Recalling that for every E X it holds that
a(x) =. (x) TG
YG,
the cut S can be equivalently descrihed as S = (x E X I..- 7 Therefore, is a coordinate with coordinate i' and threshold 7 Yg. and Theorem 2.2 proven.
Remark A.4. For context, relate Theorem A.3 the more familiar form of Cheeger's inequality.
Let LG D D 1/2 be the normalized Laplacian matrix G. It is positive semi-de semi-defiitte and its smallest eigenvalue is O. Let AG be its second smallest eigenvalue, and 2G a corresponding eigenvector. It can be shown that the quotient right- hand side of Equation (15) is minimized by choosing غ = DD-/2zgg zG. and that the minimal value takes is Ag. Hence the more standard form of Cheeger's inequality, ( & /2Ag.
A.2 k-Means Example of Theorem 2.2
As a demonstrative example, let us show a special cases of Theorem 2.2, in which a reference k-means clustering is described by suitable graph, and observe the conductance bounds it yields.
Let C (CI...., C be partition of X into & clusters with corresponding centroids ( .....
16

---

In k-means, the centroids are given by cluster means, v Σxec, 2. Denote the cost of cluster
C by cost(C:) = Exec; || 13 and the total reference clustering cost by
x - cost(C) = Σ cost((;) = Σ
10-11111 11
1=1 DEC,
We instantiate Theorem 2.2 with clique graph with edge weights inversely proportional to their cluster sizes.
Corollary A.5. In the weighted clique graph where every edge connecting z.y E C2 has weight 1/([C/ - 1). there is a coordinate cut with conductance at most
COst(C)
2
L 2112
The proof uses the following fact which can be verified by direct substitution. Fact A.6. For every of points C with mean μr
- Exeo V
Σ 1 3
Σ
|| v1l..
C
REC
#NEEC
Proof. Denote the weighted clique graph by G(X, X2, w). For this graph:
C.-II Biz,yeC,
w(x v)
0
else
(Note that if |C&| = 1 then the only node in Cs has no incident edges, thus the above setting of edge weights is well-defined.) Thus, it holds that:
vi, C ; dolx) Σ
=1
C,
VEC.
Hence, Theorem 2.2 implies the existence of coordinate cut for which the conductance is at most
Ex Ex | y/ 2
w(229) En.Ex Exwex w/z' .y)
|
y|
V
E Ex,yDDau
da(x)da(1) EnNEx Enwex (x(2)))())
|
yl
1 E C.I-
Σ
1e-vlí
[X]
xzy 2,DEC,
IXP= ExpEx | v11
1 IC Exec,
|| 11
i=l C.
Theorem A.6
X Ex.vex
| v112
2. 2i=1 Exec, || - 11(1)) 13
X En.Ex x | |x- w112
cost(C)
X Ex.ex | 1x--// 11
Note that the denominator term JX] En 1|z-5ll3 fixed size for the dataset and is independent of the reference clustering C. Thus, with an appropriate choice of graph to describe the reference clustering. Theorem 2.2 yields coordinate cuts with conductance directly related to the reference clustering cost.
17

---

A.3 IMM Alternative Analysis
In this section we focus on k-medians clustering the norm, For every subset C RR, denote its median by
med(C) min Σ1 y111- 2ER ZEC
Let C = Ci,..., Cj be reference k-medians clustering of X with respective cluster centroids ( me)(C The k-medians clustering cost of is defined as
cost1
1
11.
i=1 aEC
Let (C) be the explainable clustering tree returned by IMM algorithm. [33] proved the following theorem:
Theorem A.7. For every reference clustering C. with centroids, cost (TiMM(C)) O(k) coots (C).
In the terminology from Section 1, the "price of explainability" of k-medians clustering is O(k). This remains the best bound to date for deterministic algorithm.?
In this section we prove the same theorem for our slightly modified variant from Section 3.1, where was cast in terms of minimizing the non-uniform cut sparsity. The goal is demonstrate how the graph partitioning framework can be used analytically. and present an alternative and arguably simpler proof for the same price of explainability upper bound. Let TCMM(C) denote the tree returned by our modified IMM.
Theorem A.8. For every reference clustering C with centroids, cost, (TIMM(()) O(k) cost, (C).
For the proof, we introduce some notation aligned with [33] for better comparison and readability. Recall that the IMM algorithm builds an explainable decision tree on both the points X and the centroids M {1(T) ... ((()), J. such that each tree leaf contains exactly one centroid, and partition of into the & leaves forms the explainable clustering. For every æ X, denote by p(x) E its centroid in the reference clustering C. For every tree node let X C X and M C M be the subsets of points and centroids, respectively, contained u, and let Y = X" U M A mistake pair X", c(x) M" that are separated by the threshold coordinate cut in Let t" denote the number of mistakes in u. Also, recall the in our modified IMM, in each node u we fix a pair of centroids p/a P" at maximal distance among the centroids in
min I| ='ll i.j.p' EME
!| j7
The proof of Theorem A.8 has two steps, analogous to the proof of Theorem A.7. The first step is straightforward consequence of the triangle inequality. The detailed proof appears in [33] and is omitted here.
Lemma A.9 (Lemma 5.5 in [33]).
cost (C)MM(C)) < cost, (C)
Σ
tu llka p"ll1
(ETiMa((C)
The second step is the more involved part of the proof, and the part where the graph-based analysis presented here departs from [33].
Lemma A.10 (Lemma 5.6 in [33]). Let H be the height of (C)ma(C). Then,
Σ
bu 11l4 (illi < H cost, (T))
NETV IMM (C)
Since (C) has & leaves, its height most k; thus Theorems A.9 and A.10 together immediately imply Theorem A.8.
As mentioned in Section 1.1. for randomized algorithms, tight bound of (1 + o(1)) log & is known.
18

---

Proof of Theorem A. Fix a node a in (C). Let xz=ıla;, bjl all of ya. Define the following distribution D over coordinate cuts J. T: first, pick j E {1, d}
b.) be a bounding box containing
with probability proportional to by a²1: then, pick r uniformly random (ay, b.)
Let G(Y F)) be any undirected graph over y The probability that an edge vy E E is cut by (i. is
[zj Vj
|
y/ 1 az
ba a 11
169 a')
and therefore,
B (ea(S j.r. Yu [S
Σ ZYE
|1 u11
(16)
lbb"
anIl
Let S, be the of coordinate cuts (j. 7) that satisfy T E [aj. by]- Let m. m, denote the number of mistakes that a cut j. makes (i.e., the number of points in X such that c(x) E MM, but the cut separates v and c(x)). Recall that our modified IMM chooses the cut Jus Tu the node among the cuts in S,, that separate the pair pw M" and I,- m,,(ju, Tu).
Let "TY",EG) be the star graph on Y". where each x E X is adjacent c(x) c(x) M", and is an isolated node otherwise. Observe that (,,īT) = (a(S) i Yu \ Sg,r). Let H(Y", EH) be the graph that contains an single edge between u'u pM Observe that eạ j,r. Y, )
1 if the cut j,T separates pla P" and O otherwise. We denote this as eØ (5 (S jr. Yu (5),) =
1 (((,7) separates Pu M.. Therefore.
tu = mulJui
min J.rESu: (i.r) separates pl a
mu(ii
min
T((,T) separates pla Pn) J.rES.
ca(S Yu S -min J.rES, ez (S Yu ((,))
B(iT)/ [ Yu S
Theorem A.2
EIJ,Y (en((5p) Yu \ {
Σ ExveBo |x y||
Equation (16)
ExyeB, En ||. y|l
Exexul | c(x)]l
definition of G and H.
114 PMlla
Rearranging, bu ||,4 UXI S ExExx11> c(x) |1. Since in each level L in the tree the clusters
(Xu Tue E L.J form partition of X, we get
Σ 1l, +ill S Σ Σ
1 (x-e(x)]1 c(x)]1 = Σ 1| c(x) = cost (C).
REL
WEL
*Ex
Summing again over the H levels in the tree yields the lemma.
Note that the ratio -c(8,-.X,15) that arises in the proof is the non-uniform cut sparsity V. (S),7)
ex .Y...........
from Section 3.
B Additional Experimental Results
Running times. Table 4 contains running time measurements. For reference- based methods (EMN, CART and SPEx-Clique) measure the reference clustering step and tree construction step separately. For SPEx-kNN, we measure the k--N graph construction step and the tree construction step separately.
In our experiments, Kernel IMM proved feasible to run only on the smaller datasets (R15, Pathbased, Iris, Ecoli, Breast Cancer). Each algorithm was allotted three hours run each dataset. On the
19

---

Table Runtime comparison of the non kernel k-means based algorithms. Presented times are median runtime across five runs. For the Clique and CART algorithms, performance was measured based on spectral reference.
Algorithm
Beans
Iris CIFAR Caltech 101
RI5 Pathbased
Ecoli
Cancer Newsgroups
MNIST
Spectral reference
1.8s mm.
1m12s
7.6s
91.6ms
29ms 34.2ms 34.1ms
8.54s
1min53s
k-means reference 86.4ms 4.2
2.69s
2.18
10.4ms
4.16ms
5,39ms 7.01ms
1.04s
5.16s
k-NN graph build
1.87s 7.01ms
1m55s
2.23s
19ms
3.57ms 9.31ms 8.03ms
5.79s 2min59s
SPEX-ENN
3.69s 27ms
5m53s
Im48s
93.4ms
22.8ms 85.3ms
90.8ms
2min27s 2min52s
SPEX UPEx-Clique
203ms 8.36ms
28.2s
Iml2s
17ms
9.65ms
13.3ms 16.3ms
13.2s
39.4s
EMN CART
13.5s
6.51ms
5m13s
15m40s
101ms
13.3ms 20.9ms 184ms
7min56s 5min20s
349ms 14.8ms
32.2s
8min51s
72.7ms
9.4ms 33.9ms 31.9ms
39.2s
30s
Table 5: Performance of SPEX-KNN for different & values. The reference compared in the REF
column is the reference with the same & applied.
Ecoli
Cancer
k
ARI
AMI
REF
RS
AMI
REF
ARI
AMI
REF
2
.594
.571
.006
.287
.370
.020
.681
.603
-001
.594
.589
.640
.450
.647
.895
.594
.546
.688
10
.622
.648
.828
.450
.647
.514
.507
.490
.547
15
.682
.648
.854
.450
.647
.445
.507
.490
.567
20
.679
.642
.863
.450
.647
.450
.507
.490
.562
50
.679
.638
.593
.600
.642
.756
.507
.490
.532
larger datasets, Kernel IMM either ran out of memory, or failed complete running within the allotted time. All other methods finished rumning within up to 16 minutes (see Table 4). Therefore, we report results for Kernel IMM only for the smaller datasets.
kNN graph parameters. Table includes additional results for SPEx-kNN, showing how its performance changes as k (the parameter of the k-NN graph) varies on the Ecoli, Iris and Breast Cancer datasets.
Number of leaves. As mentioned in Section 2, SPEX produce tree with any desired number of leaves f. Our evaluation so far has focused on the setting l = k. i.e., the number leaves in the output tree is equal to the number of clusters in the reference clustering. To clarify the relation between i and f, viewing the reference clustering as a trained model, A: its number of outcomes and l is the number of explanations have its own separate explanation, we must have & 2 k; thus f= k the "most explainable" setting. As & increases, the expressiveness of the explainable clustering tree grows and it is better able to approximate the reference clustering, albeit at the cost of explainability, since now some model outcomes would have multiple different explanations.
explainability method can yield. Since each outcome must
Table 6 includes result with L = 2k for SPEx-Clique, CART-Spectral, CART-k-means, and ExKMC [17], which is extension of IMM support more leaves (which IMM does not naturally support, due to its reliance on reference clustering centroids; the same goes for EMN). The results do not point to clearly superior method.
B.1 Weighted CART
The implementation of CART in Seikit-Learn [36] contains weighted variant different from the standard one described in Section 3.3. It has modified selection rule for the next leaf to split. When the stopping condition is pre-specified number of leaves the default mode. It performs significantly better than usual CART on some datasets. As we find this noteworthy, the results are reported here. A similar modification can be applied to SPEx-Clique, and is reported too. The results are in Tables 7 and 8.
20

---

Table 6: Results with l leaves.
Ecoli
Iris
Cancer
MNIST
Caltech 101
Newsgroups
Beans
Cilar
Algorithm
ART
AMI
ART
AMI
AM1
ART
AMI
ART
SPÉX-Clique
.469
.589
.716
.739
.491
.464
.197
.317
.203
-565
.058
.811
-370
.512
.309
.484
EsKMC
458
.582
-730
.755
.491
.464
.224
.328
.249
546
.096
.263
-370
.512
.323
.467
CAKT-f-means
.477
.573
.716
.739
.491
.444
.031
.177
0
208
.026
.148
-370
.512
.144
.371
CAKT-Spectral
.93
.610
.648
.210
214
.006
.104
.608
.381
Table 7: Results on smaller datasets.
R15
Pathbased
Ecoli
Iris
Cancer
Algorithm
AMI
ARI
AMI
REF
ARI
AMI
AMI
REF: Spectral
.933
.994
.526
.570
.711
.653
1.
.630
.661
.743
.626
SPEx KNN
.982
.987
-989
.332
.100
.551
.679
.642
.633
A500
.647
.450
.007
.490
.562
SPEX Clique
.966
.989
.993
.441
.517
.824
.662
.621
.847
.576
.629
.787
.694
.588
.785
SpEx-Clique-odiine
.986
.989
.993
.441
.517
.824
.672
.618
.866
.576
.629
.787
.560
.811
CART
.866
9899
.933
.441
.517
.824
.672
.618
.866
.576
.629
.787
.683
.560
.811
CART-modified
.986
.441
.517
.824
.672
.618
.866
.576
.629
.787
.683
.560
8811
REF: k-mcans
.93
489
.609
.64
EMN
.966
.989
.993
.461
.543
.566
.559
.733
.576
.629
.772
.911
.664
SPEX Clique
.986
.989
.993
461
.543
.456
.559
.873
.576
.629
.772
.491
.464
SpEx-Clique-moiiffe
.986
.989
.993
.461
.543
456
.589
.873
.576
.629
.772
.911
.464
CART
.986
.989
.993
.421
-507
897
.454
.54.
840
.576
.629
.772
.491
.464
CART-modified
.866
.989
.933
.461
.543
.456
.589
.873
.576
.629
.772
.491
.464
Kernel k-means
Kornel IMM
.944
.962
.986
.614
.614
.583
.522
550
848
.732
.788
.924
.127
.241
.930
SPEx-Clique
.529
.573
SpÉx-Clique-modiiise
.822
.944
.954
.479
.53
.40
.529
.573
.811
.732
.788
.924
.406
.414
.516
CART-medified
.800
.444
.95
.799
.53
450
.500
.38
824
.732
.788
.944
.466
.414
.516
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Can be verified by reading the manuscript
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The main limitation of our work compared to prior works the lack of worst- case approximation bounds, due to targeting reference-obliiiour approach unlike prior work which was tailored a handful of specific references. is discussed in the "conclusions and limitations" section in the main text.
Justification:
Guidelines:
21

---

Table 8: Results on larger datasets.
MNIST
Caltech 101
Newsgroups
Beans
Cifar
Algorithm
AMI
REF
ART
ART
AMI
REF
ARI
AMI
REF
ART
REF; Spectall
.445
.200
1.
.563
.859
.431
.671
1.
.586
.677
1.
.712
.801
SyEX-KNN
.338
.150
.121
.042
.170
.090
.574
.690
.649
.342
.444
.73
SPEX-Clique
.217
.384
.282
.247
.521
.303
.078
.223
.189
.564
.671
.743
.320
438
.394
SoEx-Cliqu-mmdiiied
.155
.040
.006
330
.032
001
.173
.021
.152
.374
.200
.152
.374
.000
CART
.027
148
000
-010
166
005
008
077
-011
.036
166
005
.036
.169
035
CART modified
.106
.244
.418
REF: k-means
364
.481
1.
.405
.22
.502
.600
1.
.572
689
.636
.738
EMN
.342
.115
.219
.163
.563
.688
SPEX Clique
.209
.336
.403
.122
.495
.195
.098
.249
.128
.562
.687
.773
.288
.410
.370
-Fs-Ciiquemmodiiie
.284
092
.170
.341
.000
CART
.124
.299
.229
.017
0882
.003
.005
.99
.006
004
.180
003
044
180
.037
CAKF-modified
.244
433
.72
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic upproximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Full rigorous proofs are provided in the appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
22

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All information needed for reproducibility included in the paper; experimen- tal code is also enclosed in supplementary material
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets used are publicly available and clearly referenced. Our code is included in the supplementary and will be made available online with the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.ce
for more details.
23

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. cctppblcc////cccccccccccccccclct /ttec/ggiidee/eeeeuuniiiiiiiiiii wwweeesummisiioooooooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All parameter settings are described in the text.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: All methods evaluated in this paper (both our methods and the baseline) are deterministic algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
24

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments are run on a standard regular free-tier cloud CPU machine (Google Colab) and can be reproduced any similar machine; our methods and experiments do not require special computational resources. No additional compute beyond what described in the paper was used in the course of preparing this paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:://eerrii..cpobbbit///ttttt
Answer: [Yes]
Justification:
Code of Ethics was fully observed.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: An impact statement included as part of the manuscript with an appropriate discussion of potential broader impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
25

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No new data or models are released with the paper; the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All uses of existing assets (datasets, as well as images reproduced based on prior works) are fully and properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo//aaaaaaa com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
26

---

Answer:
[NA]
Justification: No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
27

---

Justification: the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https:/ bttps://neurte tweurips.cc/Confeeeeee /t////offeeeccee/22////1// for what should or should not be described.
28


Reviews:
[{"review_id": "qxcEF4z1E3", "reviewer": "Reviewer_eAyA", "summary": "The paper introduces SpEx, a method to explain clusters of points in $\\mathbb{R}^d$ using decision trees. SpEx is part of the literature that aims to explain clusters of points using binary decision trees. The main advantage of SpEx is its generality in handling input clusters. While previous methods mostly work for centroid-based clustering methods (e.g., k-means and k-median), SpEx aims to generate binary decision tree-based explanations for generic input clusters. Based on a theoretical observation, the paper proposes two instantiations of SpEx (SpEx-Clique and SpEx-kNN). The paper also performs experimental evaluations of their method against other baselines on a range of datasets.", "questions": "* How sensitive is SpEx’s performance to the choice of the number of leaves $\\ell$? Do the authors have any principled guidelines (empirical or theoretical) for selecting $\\ell$ beyond simply matching the number of clusters?\n\n* What happens if I decide to prune the trees after finding them? Pruning may help with the interpretability of the tree.\n\n* Can you provide more insight or analysis into the observed gap between low- and high-dimensional datasets? In particular, is this some sort of “curse of dimensionality” effect?\n\n* Could you bring Tab. 1 and Tab. 2 into the main text paper?\n\n* Could you add further discussion on the complexity of the algorithms? Perhaps list the theoretical (experimental) complexities in a comparison table?", "limitations": "The authors discuss the limitations of their approach. My only suggestion is the addition of a discussion on the interpretability of decision trees with a large number of leaves (e.g., 100 leaves). Are large decision trees really interpretable?", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n* The paper proposes a solution to the interesting problem of explaining clusters using decision trees without strong assumptions about the cluster structure. \n\n* The authors propose a theoretical framework to describe other explainability methods through a similar lens as SpEx. This is an interesting contribution to this literature.\n\n* The paper makes a thorough performance comparison across datasets, but some of the results are in the appendix.\n\n* The paper is well organized and does a good job of introducing the problem of cluster explainability to unfamiliar readers. \n\n### Weaknesses\n\n* The provided instantiations of SpEx don’t have strong performance in scenarios where other methods perform well. This is expected, since SpEx makes fewer assumptions about the problem’s structure, hence not a major weakness. \n\n* There is no discussion on how to select the number of leaves. The proposed algorithms introduce one more parameter, the number of leaves $\\ell$, which the authors set to the number of clusters. Although other methods in the literature employ a similar choice, the generality of SpEx raises questions about whether this is the optimal choice for the number of leaves. The paper presents no experimental or theoretical evidence to support their design choice.  \n\n* Important experiments only appear in the appendix (Tab. 2 and Tab. 3). These are important observations, which are relevant to the main conclusion of the paper, and hence should be brought to the main paper.\n\n* There seems to be a gap in performance in low and high-dimensional input spaces. The authors do not discuss this interesting finding enough in the paper. Is there an explanation for this finding on the style of “the curse of dimensionality”?", "was_revised": true, "final_justification": "I recommend the paper be accepted. \n\nThe problem solved by the authors is of interest to part of the interpretability community, especially the sub-group of researchers that are interested in \"white-box\" model explanations for clustering. \n\nIn addition, my comments and those of most other reviewers are minor changes in the paper that mainly improve the clarity of the presented results and enhance the presentation of the main contributions.\n\nFinally, I believe that this paper will be appreciated by the NeurIPS interpretability community and may have a significant impact after the authors implement the changes we (all reviewers) suggested.", "rebuttal": "Thank you for your valuable review and support!\n\n> Can you provide more insight or analysis into the observed gap between low- and high-dimensional datasets?\n\nThe 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.\n\n> Could you bring Tab. 1 and Tab. 2 into the main text paper?\n\nYes, we will add it.\n\n> Could you add further discussion on the complexity of the algorithms?\n\nSpEx 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))$. \n\nWhere 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)$.\n\n> choice of the number of leaves $\\ell$\n\n> discussion on the interpretability of decision trees with a large number of leaves (e.g., 100 leaves). Are large decision trees really interpretable?\n\nThese 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.\n\nThus, 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.\n\n> What happens if I decide to prune the trees after finding them?\n\nSince 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."}, {"review_id": "W3yRiXAqHQ", "reviewer": "Reviewer_A43H", "summary": "This paper proposes a spectral graph partitioning-based explainable clustering method to overcome the limitations of previous decision tree-based explainable clustering approaches. It primarily introduces two methods: SPEX-Clique and SPEX-kNN. The paper conducts experiments comparing these methods against EMN, CART, and Kernel IMM, and analyzes the implications of the results.", "questions": "- Please clarify the explainability of the proposed model in the context of existing XAI methods.\n- The paper primarily evaluates performance using standard clustering metrics (ARI, AMI). While these measure agreement with ground truth, they don't directly assess the quality of the explanation or the interpretability of the generated trees. Please provide a deeper analysis for the explainability.\n- Could the authors provide a more robust justification for the greedy approach?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The paper clearly analyzes the limitations of past research and effectively highlights the significant importance of explainability.\n\n- It attempts to overcome the limitations of previous studies by basing its approach on spectral graph partitioning.\n\n- The paper presents experimental results across nine datasets, analyzing the strengths and weaknesses of the proposed methods.\n\n\n## Weaknesses\n- The paper does not sufficiently cover explainability aspects from past research. More recent studies on explainable unsupervised learning could be discussed to provide a broader context.\n\n- The explainability of the proposed model is not clearly understood. The paper's discussion of prior limitations is too broad, making it difficult to clearly discern the specific contributions of this work. For instance, it is challenging to understand how the bound in Theorem 2.2 directly translates to explainable clustering.\n\n- The experimental design and analysis regarding explainability are insufficient. A deeper consideration and analysis of the benefits are needed. Currently, the performance results in Figure 3 show mixed outcomes.\n\n- A detailed time complexity analysis is missing. While the efficiency of storing graphs and the sweep-line procedure are mentioned, a formal analysis of the overall time complexity for the proposed algorithms (SPEX-Clique and SPEX-kNN) would enhance the paper.\n\n- The greedy approach used for building the decision tree could be further justified. A discussion on its potential trade-offs or any theoretical guarantees (even if not strict optimality) would be beneficial.\n\n- The paper mentions that some datasets are \"Embedded with CLIP\" or \"Embedded with SBERT\". This crucial information warrants a brief discussion in the experimental setup to explain why these specific embeddings were chosen and their potential impact on the results.\n\n- The impact of the parameter $k$ for SPEX-kNN could be discussed in a more comprehensive manner. While additional results are in Appendix B, a summary of the sensitivity and optimal selection process in the main text would be valuable.", "was_revised": true, "final_justification": "The authors addressed my concerns well about the justification of the greedy approach and time complexity.", "rebuttal": "Thank you for your thoughtful review and questions.\n\n> proposed model in the context of existing XAI methods, explanation or the interpretability\n\nFirst, 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. \n\nTo 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. \n\nThe 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. \n\n> Could the authors provide a more robust justification for the greedy approach?\n\nPrior 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. \n\n> how the bound in Theorem 2.2 directly translates to explainable clustering\n\nIn 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.\n\n> why these specific embeddings were chosen\n\nCLIP [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. \n\n> the parameter $k$ for SPEX-kNN\n\nThe $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. \n\n> detailed time complexity analysis\n\nPlease see the response to eAyA for the time complexity analysis."}, {"review_id": "nGKep3aGHF", "reviewer": "Reviewer_K9ow", "summary": "This paper suggests a new approach to explainable clustering with decision trees, based on spectral graph theory. Concretely, the authors propose SPEX, an algorithm that constructs a decision tree based on a graph $G(X,E,w)$. The tree is constructed by iteratively choosing a leaf and an axis-aligned cut that maximize the decrease in conductance at that leaf. The goal is to greedily find a tree $T$ that minimizes a quantity $\\bar{\\Psi}_G(T)$ that can be viewed as a normalized cut objective for multi-way partitions. The paper justifies this choice of objective by adapting a theorem that, broadly speaking, asserts that axis-aligned cuts with low conductance exist if points that are connected in the graph through an edge are on average closer than random points. The SPEX algorithm can be used for any graph, in particular for the clique graph in which points from the same (reference) cluster are connected. Alternatively, one may also directly use the kNN graph as input. Building on this graph characterization of explainable clustering, the paper shows that previous algorithms based on reference clusters (slightly adapted variant of IMM, EMN, CART) can be viewed as minimizing different non-uniform sparse cuts. The paper also includes a set of experiments that measure Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI) between different explainable clustering methods and ground truth clusters (corresponding to labels).", "questions": "- 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?\n\n- What is the price of explainability for SPEX on k-means experiments? (I am mainly asking this because I feel it should be included, given that the methods you compare against aim to minimize that quantity).\n\n- Did the authors consider comparing against other practical explainable clustering algorithms [1,2]?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThis paper is a useful contribution to the literature on explainable clustering via decision trees. Most recent works restrict themselves to studying theoretical approximation guarantees for decision trees in k-means and k-medians (with an extension to kernel k-means with certain kernels). Posing the question in a graph framework is a new perspective. It generalizes some of the previous works, allows insights into what distinguishes some algorithms from others (Section 3 is interesting), and gives a solid motivation for the proposed algorithm. The method can take any graph as input, including kNN which in some applications is more meaningful than e.g. reference cluster centers obtained via k-means. Overall, the paper is written well.\n\n**Weaknesses**\n\nWhile the method itself is theoretically motivated (Theorem 2.2.), the authors do not use this result to give guarantees for their explainable clustering algorithm (beyond a small k-means derivation in Appendix A.2). It should also be noted that there are several papers on clustering with decision trees beyond theoretical studies on price of explainability, some of which also do not need reference centers, and CART is just one of them. For example, see [1,2 and references therein].\n\nMinor comments and typos:\n- The first figure seems to label the points according to the Gaussian they came from. Would it not be more reasonable in clustering to colour them according to some k-means partition?\n- $e_G$ and $vol_G$ not defined.\n- Line 249: graph-theortic\n\n[1] Fraiman, Ricardo, Badih Ghattas, and Marcela Svarc. \"Interpretable clustering using unsupervised binary trees.\" Advances in Data Analysis and Classification 7 (2013): 125-145.\n\n[2] Frost, Nave, Michal Moshkovitz, and Cyrus Rashtchian. \"ExKMC: Expanding Explainable $ k $-Means Clustering.\" arXiv preprint arXiv:2006.02399 (2020).", "was_revised": true, "final_justification": "After the author's response, I remain positive about the paper. To summarize, I feel this paper provides a valuable contribution to the line of work on explainable clustering. Further contextualizing the paper by adding some of the experiments from their rebuttal would strengthen the paper.", "rebuttal": "Thank you for your valuable review and support!\n\n> 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?\n\nYes, 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.\n\nTo 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))$. \n\n> What is the price of explainability for SPEX on k-means experiments?\n\nWe 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.\n\n|  | Ecoli | Iris | Cancer | MNIST | Caltech | Newsgroups | Beans | Cifar |\n|---|---|---|---|---|---|---|---|---|\n| SpEx-$k$-means | 1.052 | 1.044 | 1 | 1.176 | 1.595 | 1.209 | 1.005 | 1.259 |\n| EMN-$k$-means | 1.05 | 1.044 | 1 | 1.178 | 1.575 | 1.229 | 1.004 | 1.237 |\n| CART-$k$-means | 1.058 | 1.044 | 1 | 1.512 | 2.588 | 1.29 | 1.004 | 1.419\n\n> Did the authors consider comparing against other practical explainable clustering algorithms [1,2]?\n\nThank 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.\n\n| _ARI_ | Ecoli | Iris | Cancer | MNIST | Caltech-101 | 20Newsgroups | Beans | CIFAR |\n|---|---|---|---|---|---|---|---|---|\n| SpEx-Clique | 0.469 | 0.716 | 0.491 | 0.197 | 0.203 | 0.088 | 0.37 | 0.309 |\n| ExKMC | 0.458 | 0.73 | 0.491 | 0.224 | 0.249 | 0.096 | 0.37 | 0.323 |\n| CART-k-means | 0.447 | 0.716 | 0.491 | 0.031 | 0 | 0.026 | 0.37 | 0.144 |\n| CART-spectral | 0.434 | 0.61 | 0.749 | 0.08 | 0 | 0.006 | 0.608 | 0.135 |\n\n| _AMI_ | Ecoli | Iris | Cancer | MNIST | Caltech-101 | 20Newsgroups | Beans | CIFAR |\n|---|---|---|---|---|---|---|---|---|\n| SpEx-Clique | 0.589 | 0.739 | 0.464 | 0.317 | 0.565 | 0.281 | 0.512 | 0.484 |\n| ExKMC | 0.582 | 0.755 | 0.464 | 0.328 | 0.546 | 0.263 | 0.512 | 0.467 |\n| CART-k-means | 0.573 | 0.739 | 0.464 | 0.177 | 0.208 | 0.148 | 0.512 | 0.371 |\n| CART-spectral | 0.493 | 0.648 | 0.631 | 0.21 | 0.214 | 0.104 | 0.695 | 0.381 |\n\n> Would it not be more reasonable in clustering to colour them according to some $k$-means partition?\n\nThis 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."}, {"review_id": "wuJxgxFF2B", "reviewer": "Reviewer_cfLS", "summary": "The paper presents SpEx, an explainable approach for spectral clustering. Specifically, the paper considers a generic approach that is based on spectral graph clustering paired with an iterative tree construction algorithm. The paper investigates two variants of the approach: SpEx-Clique that can represent any reference clustering using a clique graph and SpEx-kNN that does not require a reference clustering and is based on the nearest neighbours in the dataset. Experiments on eight datasets show that SpEx-Clique outperforms the interpretable baselines.", "questions": "Please see my main concerns above. No further questions.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Interesting topic that has received significant attention recently\n- Strong theoretical basis including Theorem 2.2 and the generalized framework based on non-uniform sparse cuts\n- Experiments show the proposed approach (specifically, SpEx-Clique) outperforms the baselines\n\n----\n\nWeaknesses:\n- 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. In contrast, my understanding of the proposed approach is that it still suffers from the main limitation of IMM and EMN where one leaf corresponds to one cluster hence, adding additional leaves forces the use of additional clusters in the resulting partition.\n\n- Highly-related works are missing from both literature review and as baselines:\n\t* There are existing works highly-related to spectral clustering that are not mentioned or considered as baselines. Specifically, [1] is an optimization-based approach that can support various clustering objectives and includes experiments with both kernel and spectral objectives, [2] which is cited, includes a generic approach that can be used with non-Euclidean objectives and was used Spherical K-Means objective in [2] and with spectral objective in [3]; [3] focused on interpretable clustering with alternative interpretable model (generalized additive model) and has been tested with SpectralNet embeddings; [4] is an interpretable Kernel K-Means approach (based on decision trees) that does not require centroids.\n\t* The widely used ExKMC algorithm [5] (that can utilize multiple leaves per cluster) is cited but is not used as a baseline.\n\n- Experimental results:\n\t* Experiments only compare the approach to the baselines in terms of external evaluation (ARI and AMI are based on labels), however it would be very interesting to report both “the cost of interpretability” in the proposed approach and also the suboptimality as a result of using a greedy optimization procedure.\n\t* 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.\n\t* While results show that SpEx-Clique outperforms the baselines, the gains seem somewhat limited and varies across datasets.\n\n- Minor:\n- Line 141: “graph nodes graph”\n- what distance metric is used for the kNN graph?\n\n----\n\n[1] Cohen, E. (2023, May). Interpretable clustering via soft clustering trees. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (pp. 281-298). Cham: Springer Nature Switzerland.\n\n[2] Gabidolla, M., & Carreira-Perpiñán, M. Á. (2022, August). Optimal interpretable clustering using oblique decision trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 400-410).\n\n[3] Upadhya, N., & Cohen, E. (2024, January). NeurCAM: Interpretable Neural Clustering via Additive Models. In ECAI.\n\n[4] Ohl, L., Mattei, P. A., Leclercq, M., Droit, A., & Precioso, F. (2024). Kernel KMeans clustering splits for end-to-end unsupervised decision trees. arXiv preprint arXiv:2402.12232.\n\n[5] Frost, N., Moshkovitz, M., & Rashtchian, C. (2020). ExKMC: Expanding Explainable $ k $-Means Clustering. arXiv preprint arXiv:2006.02399.", "was_revised": true, "final_justification": "As I noted in my review there are highly-related works are missing from both literature review and as baselines (including one that seems directly comparable). I think the paper would significantly benefit from extended literature review covering related works and comparison with relevant baselines. I will therefore maintain my borderline accept score.", "rebuttal": "Thank you for your valuable review and support!\n\n> 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.\n\nWe 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. \n\nWhat 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). \n\n> Highly-related works are missing from both literature review and as baselines\n\nThank 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.\n\n> it would be very interesting to report both “the cost of interpretability” in the proposed approach \n\nThis 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). \n\nThe 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. \n\n> and also the suboptimality as a result of using a greedy optimization procedure\n\nIt 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.\n\n> 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\n\nThank 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. \n\n| | SpEx-Clique | SpEx-kNN | EMN | CART-k-means | CART-spectral |\n|---|---|---|---|---|---|\n| ARI error | $\\mathbf{0.190}_{[\\mathbf{.049},.4]}$ | $0.303_{[.151,.446]}$ | $0.284_{[.205,\\mathbf{.390}]}$ | $0.377_{[.205,.577]}$ | $0.279_{[.056,.591]}$ |\n| AMI error | $\\mathbf{0.187}_{[\\mathbf{.036},\\mathbf{.381}]}$ | $0.247_{[.192,.396]}$ | $0.235_{[.080,.412]}$ | $0.341_{[.092,.589]}$ | $0.330_{[.039,.642]}$ |"}]

Author rebuttal:

Meta-review: This paper makes a nice contribution to the literature of explainable clustering by tying explainability to natural structures in an associated graph (existing explainability framework actually considers decision tree representation). The vertices of the graph are identified with the d-dimensional data points. The main tool is a theorem that shows that the conductance of a coordinate cut (subset of vertices with a specific coordinate smaller than some value) is upper bounded by a quantity "proportional" to some "average distance" between adjacent vertices of the graph. From such a graph then a decision tree is constructed where every internal node is associated with a coordinate and threshold (thus guaranteeing explainability in the usual sense).

This is a novel approach to explainable clustering that is useful and interesting in my reading.

The reviews are positive about the contribution; the reviewers are also satisfied with the comments made during the rebuttal phase. I recommend acceptance.
Decision: Accept (poster)