Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Cluster Similarity Indices (CSIs) take as input two clusterings A, B and assign a similarity score for the given pair of clusterings. The index calculates a score based on the number of pairs of elements that clustered together on both clustering (N++), those that are not clustered together in non of A,B (N--), those that are clustered together in A but not in B (N+-), and vice versa (N-+). CSIs can be used to evaluate clusterings produced by different algorithms with respect to some reliable reference clustering on a single instance, and choose the one that is the closest to the reference clustering (indicated by the CSIs). The selected clustering algorithm can be then applied to different instances of the same kind where we do not have a reference clustering. 

The authors motivate their problems in two ways. First, they consider a set of clusterings on different instances (that also contain a reference clustering) and show that the different indices disagree in the ranking of the clusterings, showing that it is not straight-forward to choose a good clustering index for an application. Then, they conduct a live experiment where they want to replace an existing clustering with one of two new available clusterings in an application, and show that the clustering that was preferred by most indices was the one that indeed showed better performance for the specific application.

The focus of this paper is to provide a way of comparing different similarity indices. In particular they provide a set of desirable properties to characterise a CSI and show which of the considered CSIs respect have those properties. The properties that the authors consider follow an intuitive sense of a good clustering. Among the properties that the authors consider they emphasize on what they call Constant Baseline. Roughly speaking, Constant Baseline requires that if one compares a clustering A to any random partitioning of the elements into clusters B, then the index should assign a minimal similarity score between A and B. Notice that the random partitioning might have any distribution of cluster sizes.
Several indices are considered and analysed with respect to the defined properties, and the authors advocate the use of two specific indices that satisfy all but one of the properties that they define (namely, the metric property).

===== 

PROS
+ Well motivated problem and relevant to the ML community
+ The authors conduct a live experiment verifying the importance of CSIs in real-world applications. 
+ The authors formulate a property that deals with a previously observed bias of CSIs toward clusterings with high-cardinality clusters.

CONS
- This is potentially an incremental work. The characterization of CSIs with respect to some set of desired properties is not new, see e.g., [1] (some of the properties are shared). 

Given the plethora of the clustering algorithms that exist out there it is important to have a systematic way of choosing which clustering algorithm one should choose. In general, I think that the problem is well-motivated.

This is not the first time that properties of CSIs are considered for the selection of a clustering algorithm. E.g., [1] did a similar study. From the discussion in Appendix A, the authors mention "In the current research, we give a more comprehensive list of constraints and focus on those that are desirable in a wide range of applications". Are there some applications where the axioms from [1] are not applicable? What is the added value compared to [1], and compared to other similar studies? Do they have properties/axioms that deal with the reported bias of many indices to clusterings with higher cardinality clusters? I would like to understand these differences to assess more properly the novelty of this paper.

One experiment that would make the claim for the significance of the Constant Baseline stronger would be to compare the reference clusterings from the second experiments in Section 3 to two randomly generated partitions, one with higher cardinality clustering than the other, and show that indeed, the CSIs that satisfy the Constant Baseline property have a more-or-less equal score to the two clustering, while the CSIs that do not satisfy it tend to prefer the clustering with larger clusters. Such an experiment would suggest that this is not just a theoretic property that is nice to have, but it also makes a significant difference in practice.

Overall, the paper is nicely written and easy to follow. I tend to be positive. My main concern is on the comparison with related work and the novelty of the paper, that I don't fully understand.

[1] Enrique Amigo, Julio Gonzalo, Javier Artiles, and Felisa Verdejo. A comparison of extrinsic ´clustering evaluation metrics based on formal constraints. Information retrieval, 12(4):461–486,2009.
review_title: Nice paper that is of interest to the community. However, the novelty of the paper is not clear.

final_score: rating: 6: Marginally above acceptance threshold
review_content: *Summary*

This papers presents a systematic analysis of clustering validation measures. Authors present evidences that validation measures for clustering can disagree; then they present a set of desirable properties that a validation measure should satisfy; finally, for a quite large number of literature measures, they show which are the properties satisfied by each of them.



*Positive points*

-> Validation of clustering is still an open issue which deserves attention by researchers
-> Authors show with synthetic and real examples that different validation measures may prefer different solutions
-> The analysis of the properties is interesting
->The paper is well written and easy to follow



*Negative points/questions/suggestions*

-> While the topic of cluster validation is worth to be investigated, the study is focused only on external validation, namely on the validation of clustering techniques when the true clustering is known. Even if being interesting, this does not represent the true challenge of cluster validation in real scenarios, which, in my opinion, is represented by the internal validation: given a true clustering problem (i.e. without the ground truth), how can I choose a clustering algorithm?
Even if authors provide an example of the real utility of this analysis (major news aggregator system), I think that external validation remains mainly used to compare algorithms.  I would suggest authors to include more comments on the practical usability of this analysis, maybe listing some other scenarios in which it can have a practical impact.


-> The whole analysis is done by assuming that the number of clusters can vary: authors use techniques which i) select automatically the number of clusters or ii) receive in input different cluster numbers. What would be the conclusions if the number of clusters is kept fixed (and equal to the true number)? Would the disagreements be so large also in this case? Knowing the number of clusters is a classical assumption in many different practical scenarios.

-> Concerning the properties, I think they are all reasonable (especially the “constant baseline” one), except the symmetry. As recognized also by authors, typically these measures are used to compare the result of a clustering algorithm to the ground truth, so being naturally asymmetric. Please consider to remove this property from the list of desirable properties.

-> Finally, I think that the last section can be largely improved. Actually Section 5 contains a summary of the findings, i.e. a summary of the properties fulfilled by the different validation measures. Some practical suggestions on how to choose a given measure given the specific applications (with practical examples) would increase the value of the work.  
review_title: Interesting paper on the challenging cluster evaluation problem

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################
Summary:
This paper aims to answer a very important and difficult question, i.e., given a clustering application what are the desirable qualities (i.e., similarity indices) to have. This work argues that there are so many clustering similarity indices with (sometimes) disagreements among them. The authors run experiments on 16 real-world datasets and 8 well-known clustering algorithms and provide a theoretical solution and a list of desirable properties that can help practitioners make informed decisions. Moreover, the authors also discuss the important pros and cons of the similarity indices in the context of the applications.


##########################################################################
Reasons for score: 
My vote for this paper is that it is marginally above the acceptance threshold. The main reasons for decisions are i) this work tries to answer a very important question especially for practical applications because there are so many clustering algorithms and similarity indices, and oftentimes, it is not known what is best for the given application. ii) Although the paper does provide a theoretical solution and pros and cons of the algorithms and indices, yet it fails to answer the primary question, i.e., what is best for a given application. 
 
##########################################################################Pros: 
 
1. This work tries to answer a very important question especially for practical applications because there are so many clustering algorithms and similarity indices, and oftentimes, it is not known what is best for the given application. 
2. It provides insights (i.e., pros and cons) into the similarity indices based on the experiments on 16 real-world datasets and 8 well-known clustering algorithms. 
3. This paper can also serve as an excellent “survey paper” on the clustering algorithms and similarity indices.
 
##########################################################################
Cons: 
 
1. This work fails to answer the primary question, i.e.; What are the best similarity indices for a given application. I understand that there is no clear answer to this question, which makes this work interesting. But, the authors should have concluded the answer. For example, authors could have provided with a flow chart, i.e., if A is more desirable than B in the application, choose C, and so on. It is just an idea, the authors can come up with some more interesting way to communicate their findings that potentially answers the key question.
2. I am not sure whether this kind of answer can be provided without a thorough discussion section, which is currently very short. 
3. Other than the above, the length of the paper (27 pages) is a strength (i.e., a standalone paper and a great survey paper), and weakness at the same time (i.e., so much redundant information that is readable otherwise). 
 
##########################################################################
Questions during the rebuttal period: 
 
The authors can respond to all the concerns. But, my major concern is #1 in the cons section. Moreover, I feel it is a very strong survey paper, but I'm not sure whether ICLR accepts survey papers. 

review_title: This paper aims to answer a very important and difficult question ....

final_score: rating: 7: Good paper, accept
review_content: The authors propose a comparative review of cluster similarity indices through a theoretical approach prescribing in advance the required mathematical properties for a given application. 
The problem is clearly stated, as well as motivation and impact, and reference list is rich and up-to-date. Overall I vote for acceptance, with a couple of remarks I list hereafter. 

Pros:
- authors detect critical issues affecting many indices
- not-so-popular indices are suggested as interesting and valid alternatives to more widespread approaches
- analysis is mathematically sound and thorough

Cons:
- the main motivating question remain unsolved: although the landscape of measures is well described, the discussion should be clearer in helping the working researcher in choosing the right metric for his problem.
- the benchmark datasets, even the real world ones, are still somehow “artificial” and not really representative of the different situations that can be met nowadays; I would strongly recommend testing the studied algorithms on more complex data such as -omics datasets (e.g. from GEO, or single-cell sequencing), or weather radar data, or particle physics data, to greatly add value to the manuscript.
- there is no real novel material introduced here, and somehow no real learning involved: however, the analysis is clear and accurate, and, as a review, indeed interesting.


review_title: Interesting comparative review

Meta-review: The paper goes over a long list of proposed clustering similarity indices and attempts
to provide a taxonomy of those by their different approaches and the extent by which they
satisfy a list of "desired properties" proposed by the authors.
This is very much in the spirit of earleir work on clustering similaritie by [Meila 2007]
and on clustering quality measures [Ackerman, Ben-David 2008, 2009].

While there may be some interest in such a compendium, there is no much novelty in this paper
and it relevance to practice is also unclear.
Decision: Reject