Explaining Kernel Clustering via Decision Trees

We thank you for your review. We are glad that you enjoyed the paper, and we appreciate that you agree that the problem is both interesting and relevant. We now address the weaknesses mentioned in your review.

The dimension $d$ might be very large in real-world data sets.

We agree that the upper bounds can be loose for well-clustered data. This is not very surprising. Indeed, previous works on explainable $k$-means have also reported approximation ratios of close to $1$ in practice (for example, see Table 1 in [1]). In our case, the additional factor of order $d$ is a consequence of decoupling dimensions in the kernel function, which is necessary to obtain interpretable feature maps. It is likely that algorithms tailored to specific kernels allow for tighter bounds (much in the same way as for $k$-means, $k$-medians and higher $\|\cdot \|_p$-norms, distinct algorithms have emerged [2]). Moreover, better guarantees could possibly be given under assumptions on the underlying distribution. These are very interesting avenues to explore in the future. However, since explainable kernel clustering has not been studied prior to our work, this paper takes a broader perspective, proposing general methods that work for a large class of kernels, regardless of the underlying distribution.

[1] Laber, Eduardo S., and Lucas Murtinho. "On the price of explainability for some clustering problems." International Conference on Machine Learning. PMLR, 2021.

[2] Gamlath, Buddhima, et al. "Nearly-tight and oblivious algorithms for explainable clustering." Advances in Neural Information Processing Systems 34 (2021): 28929-28939.

It is unclear to me whether the improvement in the clustering cost in the experiments are due to the better kernel clustering or due to these generalized decision tree structure. Would this generalized threshold decision tree (with interval cut) significantly reduce the clustering cost since it partitions the space into more parts? It would be interesting to evaluate the effect of this tree structure change by converting it back to a regular threshold tree and comparing it with the expanded IMM with the same number of leaves.

While it is true that the proposed interval cuts allow for more refined partitions of the input space, let us briefly emphasize that they do this in a way that arguably does not harm interpretability at all (unlike a decision tree with twice the number of nodes). From a theoretical point of view, interval cuts are justified by Theorem 2. The improved performance of our methods (over those from explainable $k$-means) is primarily a consequence of us approximating partitions that more accurately reflect meaningful cluster structures. Unless the data exhibits linear cluster structures, standard explainable $k$-means is unable to identify the correct partitions, since it relies on the centers that $k$-means provides us with, and hence typically would inherit its deficiencies. Regarding the question raised by the reviewer: Kernel IMM (after unfolding it back to a tree with twice the number of nodes) is more restricted in its structure than Kernel Expand (which could, for example, access twice the number of distinct feature dimensions in all of its nodes).

We thank you for your review. We appreciate that you find the paper to be well-written and the problem to be novel and relevant. We will incorporate the additional references and minor comments in a revision. We address the weaknesses mentioned in the review below.

It would be nice to see a bit more elaborate experiments. Is it possible to compare to other works constructing interpretable models (not necessarily based on k-means or kernel k-means), for example in terms of accuracy or interpretability (nr. of rules, for example)? If not, how so?

A systematic empirical evaluation of different tree-based clustering algorithms is interesting, but would take considerable time and resources, and will not be possible within the timeline for these discussions. We will consider this in the future, and note that existing papers from this line of research (published at similar ML conferences) also restrict to a small set of experiments on standard clustering datasets.

Regarding the complexity of the decision trees: Kernel IMM always fits a tree with exactly $k$ leaves. On the synthetic clustering datasets (containing $k=3$, $k=7$ and $k=2$ clusters respectively), we refine the partitions of Kernel IMM using Kernel ExKMC and Kernel Expand, fitting $m = 6$, $m = 10$ and $m = 4$ leaves respectively. The price of explainability is included in Figure 4 (left plot). For the pathbased dataset, we have illustrated the suboptimal performance of Kernel IMM in Figure 3, as it was one of the primary reasons for us to explore the greedy algorithms derived in Section 5.

Thank you for the response. I read it. I keep my score as it is.

We thank you for your review, and we are glad that you found the paper to be well-written. We appreciate that you acknowledge our strategy of relaxing the notion of explainability, which enables us to derive kernelized variants of explainable clustering. We now address the concerns raised in the weaknesses.

No relation to $k$-median and $k$-center problem are given.

The $k$-median and $k$-center problem are significantly less studied in the kernel setting. On the other hand, kernel $k$-means is closely related to spectral clustering [1] as well as clustering of (Hilbert space embeddings of) distributions [2]. The $k$-median problem requires a $\|\cdot\|_1$ norm on the RKHS, making its analysis difficult.

[1] Dhillon, Inderjit S., Yuqiang Guan, and Brian Kulis. "Kernel k-means: spectral clustering and normalized cuts." Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. 2004.

[2] Vankadara, Leena C., et al. "Recovery guarantees for kernel-based clustering under non-parametric mixture models." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

No discussion on lower bound is involved.

Of course, lower bounds from the linear setting extend to the kernel setting (under a linear kernel). Nonetheless, we agree that the paper leaves some open questions (such as lower bounds for more specific classes of kernels such as distance-based product kernels, or other related kernel clustering problems). However, this is natural because (i) no prior works on explainable kernel clustering exist, and (ii) kernelizing existing methods is not possible directly, as Theorems 1 and 2 show, and we must hence take a broader perspective on the problem in Sections 3 and 4. This broader perspective allows us to derive rather general results and methods that are applicable to several practically relevant kernels.

Thank you for pointing out additional related work, which we will add. To your question on the $O(k^2)$ bounds: We believe that improved versions of IMM (such as those obtaining $O(k \log k)$ bounds [3]) can also be applied to surrogate features.

The Rand Index measures the agreement between two clustering partitions. Code will be available to the public.

[3] Esfandiari, Hossein, Vahab Mirrokni, and Shyam Narayanan. "Almost tight approximation algorithms for explainable clustering." Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2022.

We thank you for your review. We appreciate that you have acknowledged the novelty of the problem and our contributions to interpretable approximations of kernel functions. We hope to resolve your remaining concerns in our response.

Kernel $k$-means is not used as frequently in practice, spectral clustering or DBSCAN are preferred.

Spectral clustering is equivalent to weighted kernel $k$-means [1]. Moreover, kernel $k$-means is closely related to clustering of distributions in the RKHS [2], which connects it to DBSCAN. Understanding its explainability is therefore not only important in its own right, but also a first step to extend the existing literature on interpretable clustering to more flexible methods.

[1] Dhillon, Inderjit S., Yuqiang Guan, and Brian Kulis. "Kernel k-means: spectral clustering and normalized cuts." Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. 2004.

[2] Vankadara, Leena C., et al. "Recovery guarantees for kernel-based clustering under non-parametric mixture models." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

One should jointly optimize clustering cost with the decision tree.

The recent works on explainable clustering show a clear preference towards first finding the partition, and then fitting a decision tree (for two recent analysis, see [3] and [4]). Our paper demonstrates when and how worst-case guarantees can be leveraged to the kernel setting. Joint optimization of clustering cost and decision tree is a different principle. We believe it is beyond the scope of this paper.

[3] Charikar, Moses, and Lunjia Hu. "Near-optimal explainable k-means for all dimensions." Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2022.

[4] Esfandiari, Hossein, Vahab Mirrokni, and Shyam Narayanan. "Almost tight approximation algorithms for explainable clustering." Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2022.

The paper completely discards the approach of fitting a tree on the kernel k-means clustering labels as a supervised problem.

The (Kernel) IMM algorithm is supervised, it minimizes the number of mistakes at every iteration. Similarly, the Kernel Expand algorithm can also be run on an empty tree, choosing threshold cuts that minimize the number of points assigned to a wrong cluster. For completeness, we compared CART to Kernel IMM on three clustering datasets (checking Laplace and Gaussian kernel, as well as Taylor and kernel matrix features as in the experiments). Both are similar in terms of price of explainability.

Decision tree algorithms such as CART may perform well in practice. However, we do not know of any theoretical guarantees in the clustering regime. This is precisely what has motivated the extensive works on explainable $k$-means that this paper builds on.

The theoretical bounds on the price of explainability seem to be quite high and not really helpful in practice. For example, does the bound of mean that say for MNIST the tree will do worse by (784 * 100) times than the unconstrained kernel k-means?

Using explainable clustering directly on images (such as MNIST) may not be meaningful because pixel values are typically not interpretable. We agree that experiments indicate that the worst-case upper bounds can be loose. It is however actually a strength of worst-case approximation guarantees that they hold for all possible data, in spite of being potentially loose for well-behaved data. Previous works on explainable $k$-means have also reported approximation ratios close to $1$ in practice (for example, see Table 1 in [5]). It is likely that algorithms tailored to specific kernels allow for tighter bounds (much in the same way as for different $\|\cdot \|_p$-norms, distinct algorithms have emerged [6]). Better guarantees could possibly be given under assumptions on the distribution, and these are interesting avenues to explore in the future. Since explainable kernel clustering has not been studied prior to our work, this paper takes a broader perspective, proposing general methods that work for a large class of kernels, regardless of the distribution.

[5] Laber, Eduardo S., and Lucas Murtinho. "On the price of explainability for some clustering problems." International Conference on Machine Learning. PMLR, 2021.

[6] Gamlath, Buddhima, et al. "Nearly-tight and oblivious algorithms for explainable clustering." Advances in Neural Information Processing Systems 34 (2021): 28929-28939.