Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a novel internal validation index for clustering, based on the differential entropy, named internal purity. The method is evaluated on different datasets, encoded with deep net representations, and compared with standard alternatives.
strength_and_weaknesses: Positive points:
- The topic is definitely interesting
- The paper is well written and easy to read
- The structure of the manuscript is clear
- The experimental evaluation is rather extensive


Negative points:

1) the computation of the index can be problematic.
The method is based on the estimation of the differential entropy of the clusters. The estimation of the entropy is based on the assumption that data follows multivariate normal distribution, which I consider a rather strong and problematic assumption:

- In many clustering problems data are not normally distributed
- There can be problems in estimating covariance matrices in such high dimensional spaces
- Better alternatives exist: for example, you can consider alternative non parametric bypass entropy estimators. Actually different studies have been conducted on estimating Entropies without making any assumption on the shape (which may be not realistic) and without a direct estimation of the density (which may be very problematic in high dimensional spaces). A starting example can be the non parametric bypass entropy estimator of the Renyi entropy proposed in:

D. Pal, B. Poczos, and C. Szepesvari, “Estimation of Rényi entropy and mutual information based on generalized nearest-neighbor graphs,” in Advances in Neural Information Processing Systems 23, 2010, pp. 1849-1857.


2) Some comments on the experimental part.

- All the experiments are based on text-images which are pre-encoded with deep net representations. Is this crucial for the applied method? In other words, how well this method could generalize to non-deep representations? What about the application on original representations of non-image and non-text datasets?
Moreover, in the paper I did not find mention to the size of the embedding, which I guess is high (please report it in the paper). How does the method work in moderately dimensional datasets? I’m sure that other methods would increase their performances. 
Finally: while for representation recent state-of-the-art methods have been used, for clustering only classic approaches have been considered, such as K-means, Dbscan, GMM and HC. What if we use more recent and better performing methods? Moreover, most of these methods are returning convex clusters (i.e. somehow following Gaussianity). 

Without considering these three aspects it is difficult to assess the general applicability of the proposed method


-  While the proposed criterion is meant to be used in internal validation, at the end the evaluation is based on external measures, i.e. accuracy and ARI. Of course it is a somehow standard and well established way, still it would be nice at least to discuss alternatives and (possibly) provide examples – like, for example, evaluation based on context knowledge, in the spirit of what is discussed in papers like: 
Ulrike von Luxburg, Robert C. Williamson, Isabelle Guyon: Clustering: Science or Art? ICML Unsupervised and Transfer Learning 2012: 65-80

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. One comment: authors qualitatively justify their approach using fig 1. I think that clusters of figure 1(b) are definitely not realistic: it is very rare that a clustering algorithm, given the data represented in figure, would output such clusters.

For what concerns novelty, maybe authors should refer and compare to other works in clustering evaluation which make use of Information theoretic concepts, like for example the (somehow old but just to give an idea):
Vinh, Epps, Bailey: Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance 
Journal of Machine Learning Research 11 (2010) 2837-2854 
summary_of_the_review: Somehow interesting paper dealing with a crucial problem. The approach can be better contextualized, some assumptions (like Gaussianity of Clusters) are rather strong, and better alternatives exists.

UPDATE AFTER REBUTTAL
I carefully read the responses, the clarifications, and the additional material, and I thank the authors for the significant efforts made in clarifying my doubts. Even if I consider that the paper has potential, I’ll maintain my score unchanged, since I still have some doubts, especially on the assumptions: even if I acknowledge the efforts made by the authors in improving this aspect in the rebuttal, I still consider that the Gaussianity assumption is rather strong, and that better alternatives exist.
------
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes an internal validation metric for model selection in clustering based on the average difference in differential entropy between each cluster and the cluster means when each cluster is treated as having a Gaussian distribution, as is the collection of cluster means.

Some experiments are included to show the practical performance in comparison with other internal metrics when data are clustered after being embedded with pre-trained neural networks.
strength_and_weaknesses: Unfortunately I do not see any substantial strengths in the paper. Although there is some evidence of practical relevance, the experiments are a bit contrived and furthermore the implementation of some other metrics, such as AIC and BIC, is incorrect. First, AIC and BIC in their basic formulations should not be applied to the solution based on a hard mixture, such as k-means. Furthermore, if the authors would like to use these then it is sensible to use the same parameter estimates for them as in the proposed method since AIC and BIC are applicable for GMMs, which is the "assumption" underlying the proposed method.

Weaknesses:
- The authors argue that compactness metrics based on variance are flawed, and yet they propose one which is based solely on the differences between the volumes of the covariance matrices of the clusters and the between class covariance. It is not clear why their proposal is not similarly flawed.
- There does not seem to be any theoretical underpinning for the proposed approach, whereas if the "assumption" is that the data are from a Gaussian mixture then there are well motivated alternatives with sound theoretical underpinnings, such as AIC and BIC.
- The presentation and notation is unclear.
- The authors report the performance in terms of ACC and ARI, however other external validation metrics may tell a very different story.

clarity,_quality,_novelty_and_reproducibility: The clarity, both in terms of the writing, and in terms of the arguments put forward in support of the proposed method requires improvement. Without a theoretical justification, or at least a strong heuristic justification for the proposed metric, the proposal overall is not of a quality high enough for publication in a top tier conference such as ICLR. Regarding novelty, it is possible that the proposal is entirely new, however its similarity with likelihood based criteria (the negative entropy is directly connected to the expected log-likelihood) means that it is more tangential to existing methods than the authors seem to have noticed. In terms of reproducibility, I have concerns about the way in which existing metrics were implemented and without absolute clarity it is not certain that the results are reproducible.
summary_of_the_review: Overall, while there is arguably some evidence for practical relevance, the experiments are a bit too thin and potentially contrived to suit the proposed method, and there are questions regarding the correctness of the implementation of other metrics, to warrant acceptance in a top tier conference. Furthermore, even if there were no issues with the experiments, the lack of a sound justification (either theoretical, or at least a well argued heuristic) for the proposed method means that its performance in general is questionable.

UPDATE:

After considering the authors' responses to my and other reviewers' comments, as well as the reviewers' comments themselves, I do not see a reason to adjust my initial score/assessment of the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new measure for internal clustering evaluation. To compute this measure, one first computes the differential entropy for each cluster (assuming that the elements are sampled from a multivariate normal distribution) and then subtracts the differential entropy for the cluster centers from the average entropy of individual clusters. Experimental results on several datasets with known cluster labels show the advantages of the new measure over existing ones.
strength_and_weaknesses: Strength:
- Experimental results show significant improvements on the considered datasets

Weaknesses:
- The assumption about the normal distribution is quite strong, and it is not clear how deviations from this assumption would affect the quality of the measure
- There is no theoretical or empirical analysis of the properties of the proposed measure

Detailed comments are below.

I am not very familiar with the literature on internal clustering evaluation measures, but there are works on theoretical analysis of such measures, for instance, papers discussing axioms desirable for these measures [1] or providing guarantees for convex clusters (Halkidi & Vazirgiannis, 2001). Then, an empirical evaluation was conducted by Liu et al. (2013), where the effect of noise, density, and shapes was analyzed. The current paper would benefit from more detailed related work where different approaches to comparing clustering measures are discussed.

Additionally, a more detailed analysis of the proposed measure would help to demonstrate its advantages. For instance, does this measure satisfy some desirable theoretical properties? Is it biased towards big or small clusters? (Such biases are formalized for external cluster evaluation measures, e.g., in [2].) How the measure performs for clusters with different levels of noise, different shapes, etc.? Such theoretical or empirical analysis can show the benefits and limitations of the proposed measure.

More details throughout the text can be helpful:
- The beginning of page 2: formalization of distance-based indices would help a reader to understand the motivating example.
- Formal definitions of the measures from Table 1 are needed to understand the existing measures and the differences between them and the proposed measure. (In Table 1, the intuition behind the measures is given.)
- More details on the information criterion are needed to understand the analogy at the beginning of page 6.
- Also, I could not get the main message of the paragraph “Effectiveness” in Section 4.2.
The detailed experimental setup can be moved to Appendix, which may give more space to explanations throughout the text.

Minor comments:
- Note that the differential entropy in equation (2) is for a one-dimensional case, while it is later used for d-dimensional vectors.
- To compute CP in equation (7), parameters of the multivariate normal have to be estimated, which needs to be mentioned in the text.
- The variable m (the number of samples in the k-th cluster) can be changed to reflect the dependency on k, e.g., m_k

Questions for the authors:
- Q1: The measure assumes that the elements within each cluster and cluster centers have multivariate normal distributions. In practice, this can be violated. What would happen in such cases? How sensitive is the measure to deviations from this assumption? Also, can we approximate the density and then approximate the integral (2) without this assumption?
- Q2: Could you please specify how accuracy is computed for clustering evaluation?

Some typos:
- “these implementation” (page 2, line 3)
- “the volume of two cluster vector space are the same” (page 2, line 8)
- “has also be used” (page 3, line 6)
- “the distance form the samples” (page 2, definition of I index)
- “are not good measure” (page 4)
- “ACC and ARI indicates” (page 6, line -7)
- “besults” (page 7, line -7)
- “CH obtain” (page 7, line -5)
- “Tabel” (page 7, line -5)
- Missing articles throughout the text

[1] Ben-David S., Ackerman M. Measures of clustering quality: A working set of axioms for clustering. NIPS 2008.

[2] Gösgens M., Tikhonov A., Prokhorenkova L. Systematic analysis of cluster similarity indices: How to validate validation measures. ICML 2021.
clarity,_quality,_novelty_and_reproducibility: Please, see the detailed comments above.

**Clarity** The paper is generally clearly written, but some background required for the understanding is not included.

**Novelty** To the best of my knowledge, the proposed measure is novel.

**Reproducibility** There are enough details to reproduce the experiments, but code is not provided.
summary_of_the_review: On the one hand, the experiments show significant superiority of the proposed measure over existing ones on the considered datasets. On the other hand, the properties of the proposed measure are not investigated theoretically or empirically. Thus, it is not clear how it will behave in other tasks. Additional analysis is needed to understand to which datasets the measure is applicable. Therefore, my current rating is borderline reject.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a internal cluster validation index that is based on the notion of 'differential entropy' to assess the compactness and separability of a clustering solution. It relies on the assumptions i) that each cluster can be modeled using a Gaussian distribution and ii) that clusters centers also follow a Gaussian distribution.  The proposed index is compared to several alternatives using embeddings obtained from deep neural networks pretrained on image and text datasets. 

strength_and_weaknesses: Strength
The paper is well-written and clearly explained.

Weaknesses
There is no significant technical contribution. Combining internal and external cluster separation is typical in most clustering quality indices.
Differential entropy depends on the determinant of the covariance matrix, a well-known measure of cluster variance. 
Gaussian assumption is made both for the data distribution inside a cluster and the distribution of cluster centers, which is actually too restrictive.
There is no sufficient intuitive justification on why the proposed index would perform better than existing ones.

clarity,_quality,_novelty_and_reproducibility: The method is simple and lacks in terms of originality and novelty. 
The paper is clearly written and the results seem to be easily reproducible (although no code is provided).

summary_of_the_review: The paper presents an internal cluster validation index that is based on the differential entropy of multidimensional normal distribution. 
Given a cluster i with data mean \mu_i and data covariance Σ_i its compactness is computed as the entropy of the normal distribution N(\mu_i, Σ_i). The dispersion among clusters is computed as the entropy of the set of cluster centers, assuming that they are Gaussian distributed.

Major concerns about the paper.
1) The Gaussian assumption is too restrictive.
2) Differential entropy is essentially the determinant of Σ, which is a well-known measure of cluster variance.  
3) Experiments focus on embeddings from pretrained deep networks. The method should be evaluated on synthetic datasets with clusters of various shapes and known ground truth. It should also be tested on typical low dimensional benchmark datasets (e.g. from the UCI repository).
4) There is no sufficient intuitive justification on why the proposed index would perform better than several existing ones also relying on separation and compactness.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposed an internal validation index for clustering based on differential entropy, which is calculated by using a gaussianity  assumption. 

All reviewers agree that the paper should not be published. Most reviewers believe that the gaussianity assumption is too strong, and that the paper makes limited contributions to the field.
justification_for_why_not_higher_score: All reviewers agree that the paper should not be published. Most reviewers believe that the gaussianity assumption is too strong, and that the paper makes limited contributions to the field.
Decision: Reject