Systematic Analysis of Cluster Similarity Indices: How to Validate Validation Measures
Authors: Martijn Gösgens
Liudmila Prokhorenkova
Aleksei Tikhonov
Venue:  (2021)
Keywords: cluster similarity indices
cluster validation
clustering
community detection
constant baseline

Abstract: There are many cluster similarity indices used to evaluate clustering algorithms, and choosing the best one for a particular task remains an open problem. We demonstrate that this problem is crucial: there are many disagreements among the indices, these disagreements do affect which algorithms are chosen in applications, and this can lead to degraded performance in real-world systems. We propose a theoretical solution to this problem: we develop a list of desirable properties and theoretically verify which indices satisfy them. This allows for making an informed choice: given a particular application, one can first make a selection of properties that are desirable for a given application and then identify indices satisfying these. We observe that many popular indices have significant drawbacks. Instead, we advocate using other ones that are not so widely adopted but have beneficial properties.

Under review as a conference paper at ICLR 2021
SYSTEMATIC ANALYSIS OF CLUSTER SIMILARITY INDICES: How TO VALIDATE VALIDATION MEASURES
Anonymous authors Paper under double-blind review
ABSTRACT
There many cluster similarity indices used to evaluate clustering algorithms, and choosing the best one for a particular task remains an open problem. We demonstrate that this problem is crucial: there are many disagreements among the indices, these disagreements do affect which algorithms are chosen in applications, and this can lead to degraded performance in real-world systems. We propose a theoretical solution to this problem: we develop list of desirable properties and theoretically verify which indices satisfy them. This allows for making an informed choice: given particular application, one can first select properties that are desirable for a given application and then identify indices satisfying these. We observe that many popular indices have significant drawbacks. Instead, we advocate using other ones that are not so widely adopted but have beneficial properties.
INTRODUCTION
Clustering is an unsupervised machine learning problem, where the task is to group objects that are similar each other. In network analysis, a related problem is called community detection, where grouping is based on relations between items (links), and the obtained clusters are expected to be densely interconnected. Clustering is used across various applications, including text mining, online
advertisement, anomaly detection, and many others (Allahyari et al. 2017 Xu & Tian 2015).
To measure the quality of a clustering algorithm, one can use either internal or external measures. Internal measures evaluate the consistency of the clustering result with the data being clustered, e.g., Silhouette, Hubert-Gamma, Dunn, and many other indices. Unfortunately, is unclear whether optimizing any of these measures would translate into improved quality in practical applications. External (cluster similarity) measures compare the candidate partition with a reference one (obtained, e.g., by human assessors). A comparison with such gold standard partition, when it is available, is more reliable. There are many tasks where external evaluation is applicable: text clustering (Amigó et al. 2009). topic modeling (Virtanen & Girolami] 2019). Web categorization (Wibowo & Williams 2002), face clustering (Wang et al. (2019), news aggregation (see Section 33, and others. Often, when there is reference partition available, it is possible to let group of experts annotate subset of items and compare the algorithms on this subset.
Dozens of cluster similarity measures exist and which one should be used a subject of debate (Lei et al., 2017). In this paper, we systematically analyze the problem of choosing the best cluster similarity index. We start with a series of experiments demonstrating the importance of the problem (Section 3). First, we construct simple examples showing the inconsistency of all pairs of different similarity indices. Then, we demonstrate that such disagreements often occur in practice when well-known clustering algorithms are applied to real datasets. Finally, we illustrate how an improper choice of a similarity index can affect the performance of production systems.
So, the question is: how to compare cluster similarity indices and choose the best one for particular application? Ideally, we would want to choose an index for which good similarity scores translate to good real-world performance. However, opportunities to experimentally perform such validation of validation indices are rare, typically expensive, and do not generalize to other applications. In contrast, suggest theoretical approach: we formally define properties that are desirable across various applications, discuss their importance, and formally analyze which similarity indices satisfy them (Section 4). This theoretical framework would allow practitioners to choose the best index

---

Under review as a conference paper at ICLR 2021
based relevant properties for their applications. In Section 5 advocate two indices that are expected to be suitable across various applications.
While many ideas discussed in the paper be applied to all similarity indices, also provide more in-depth theoretical characterization of pair-counting ones (c.g., Rand and Jaccard), which gives an analytical background for further studies of pair-counting indices. We formally prove that among dozens of known indices, only two have all the properties except for being a distance: Correlation Coefficient and Sokal & Sneath's 's first index (Lei et al. 2017). Surprisingly, both indices are rarely used for cluster evaluation. The correlation coefficient has an additional advantage of being easily convertible a distance measure via the arccosine function. The obtained index has all the properties except constant baseline, which is still satisfied asymptotically.
Constant baseline is a particular focus of the current research: this one of the most important and non-trivial properties. Informally, a sensible index should not prefer one candidate partition over another just because it has too large or too small clusters. To the best of our knowledge, we are the first to develop a rigorous theoretical framework for analyzing this property. In this respect, our work improves over the previous (mostly empirical) research on constant baseline of particular indices (Albatineh et al., |2066; Lei et al. 2017 Strehll 2002), Vinh et al. 2009; 2010) we refer to Appendix[AA a detailed comparison to related research.
2 CLUSTER SIMILARITY INDICES
We assume that there is set of elements V with size n [V], A clustering is a partition of V into disjoint subsets. Capital letters A, B, C' will be used to name the clusterings, and we will represent them as A = {Ai....; A&a elements v, w E V lie in the same cluster A, we refer to them as an intra-cluster pair of A, while inter-cluster pair will be used otherwise. The total number of pairs is denoted by N =()) The value that an index I assigns to the similarity between partitions A and B will be denoted by I(A, B). Let us now define some of the indices used throughout the paper. while a more comprehensive list, together with formal definitions, is given in Appendix B.1 and B.2
}. where A; is the set of elements belonging to i-th cluster. If a pair of
Pair-counting indices consider clusterings to be similar they agree on many pairs. Formally, let Á be the N-dimensional vector indexed by the set of element-pairs, where the entry corresponding to (u, w) equals if (v, w) is intra-cluster pair and 0 otherwise. Further, let MAB be the N x matrix that results from concatenating the two (column-) vectors Á and B. Each row of M is either 11, 10, 01, or 00. Let the poir-counts N11, Noo, No1, Noo denote the number of occurrences for each of these rows in MAB-
Definition 1. A pair-counting index is a similarity index that can be expressed as a function of the pair-counts N11, N1o, No1, Noo-
Some popular pair-counting indices are Rand and Jaccard:
Nn Noo
N1
R N11 - No0 + No1 + Noo
J Nu + Noo + No1
Adjusted Rand (AR) is linear transformation of Rand ensuring that for random B we have AR(A, B) = 0 in expectation. A less widely used index is the Pearson Correlation Coefficient (CC) between the binary incidence vectors A and B Another index, which we discuss further in more details, the Correlation Distance CD(A, B) = arccos CC(A, B). In Table 4 we formally define 27 known puir-counting indices and only mention ones of particular interest throughout the main text.
Information- theoretic indices consider clusterings similar if they share a lot of information, i.e., if little information is needed to transform one clustering into the other. Formally, let (AA) := H ((IA))) l/n......... [AR, l/n) be the Shannon entropy of the cluster-label distribution of A. Similarly, the joint entropy H (AA, B) defined as the entropy the distribution with probabilities (ptz) (e(e))s()))) (ekk)) where Pij AA ByI/n. Then, the mutual information of two clusterings can be defined as
'Note that Spearman and Pearson correlation are equal when comparing binary vectors. Kendall rank correlation for binary vectors coincides with the Hubert index, which is linearly equivalent Rand.
2

---

Under review as a conference paper at ICLR 2021
M( = H(A) + H()) [A, B).
There multiple ways of normalizing the mutual
information, the most widely used ones are:
M(A, B)
M B3)
NMI(A, B) = (H(()) + HBB))/2² NM (A, B) max (A)),, H(B)}
NMI is known to be biased towards smaller clusters, and several modifications try to mitigate this bias: Adjusted Mutual Information (A.I) and Standardized Mutual Information (SMI) subtract the expected mutual information from M (A, B) and normalize the obtained value (Vinh et al. 2009).
while Fair NMI (FNMI) multiplies NMI by a penalty factor e e-Ika-kal/kk (Amelio & Pizzuti 2015).
3 MOTIVATING EXPERIMENTS
As discussed in Section 2 many cluster similarity indices used by researchers and practitioners. A natural question is: how to choose the best one? Before trying to answer this question, it is important understand whether the problem is relevant. Indeed, if the indices are very similar to each other and agree in most practical applications, then one can safely take any index. In this section, we demonstrate that this is not the case, and the proper choice matters.
First, we illustrate the inconsistency of all indices. We say that two indices / and I2 are inconsistent for triplet of partitions (A, By, B2) if I (A, B1) > (A, (2) but [2(A, Bi) < I2(A, B2). We took 15 popular cluster similar- ity measures and constructed just four triplets such that each pair of indices inconsistent for at least one triplet. One example is shown in Figure D for this simple example, about half of the indices prefer the left candidate, while the others prefer the right one. Other examples can be found in Appendix [.I
(a) FNML R. J. W. FMeasure, BCubed
(b) NML NM VI. AMI, S&S, CC, CD
Figure 1: Inconsistency of indices: shapes denote the refer- ence partition, captions indicate indices favoring the candi- date.
Thus, we see that the indices differ. But can this affect conclusions obtained in experiments on real data? To check that, we ran 8 well-known clustering algo- rithms (Scikit-learn) 2020) on 16 real- world datasets (GitHub 2020). Each dataset, together with a pair of al- gorithms, gives triplet of partitions (A, B1, B2), where A is reference par- tition and B1, B2 are provided by two algorithms. For given pair of indices and all such triplets, look at whether the indices are consistent. Table the relative inconsistency for several indices (the extended table together with a detailed description of the experimental setup and more analysis is given in Appendix F.2. The inconsistency rate is significant: e.g., popular measures Adjusted Rand and Variation if Information disagree in almost 40% of the cases, which is huge. Interestingly, the best agreeing indices are S&S and CC, which satisfy most of our properties, as shown in the next section. In contrast, the Variation of Information very often disagrees with other indices.
Table 1: Inconsistency of indices on real-world clustering datasets, %
NMI
VI
AR
S&S1
CC
NMI
40.3
15.7
20.1
18.5
VI
37.6
36.0
37.2
AR
11.7
8.3
S&S1
3.6
CC
To show that the choice of similarity index may affect the final performance in real production scenario, we conducted an experiment within a major news aggregator system. The system groups news articles to events and shows the list of most important events users. For grouping, clustering algorithm is used, and the quality of this algorithm affects the user experience: merging different clusters may lead to not showing important event, while too much splitting may cause duplicate events. When comparing several candidate clustering algorithms, it is important to determine which one is the best for the system. Online experiments are expensive and can be used only for the best candidates. Thus, we need a tool for an offline comparison. For this purpose, we manually created reference partition small fraction of news articles. We use this partition evaluate the
3

---

Under review as a conference paper at ICLR 2021
candidates. We performed such offline comparison for two candidate algorithms and observed that different indices preferred different algorithms. Then, we launched an online user experiment and verified that one of the candidates is better for the system according to user preferences. Hence, it is important to be careful when choosing a similarity index for the offline comparison. See Appendix F3 for more detailed description of this experiment and quantitative analysis.
4 ANALYSIS OF CLUSTER SIMILARITY INDICES
In this section, we motivate and formally define properties that are desirable for cluster similarity indices. We start with simple and intuitive ones that can be useful in some applications but not always necessary. Then, we discuss more complicated properties, ending with constant baseline that is extremely important but least trivial. Tables 2 and indices of particular interest are listed along with the properties satisfied. In Appendix C we give the proofs for all entries of these tables.
For pair-counting indices we perform a more detailed analysis and define additional properties. For such indices, we interchangeably use the notation I (A, B) and [[N11, N10, NNo,,Noo) NNoo).
Some of the indices have slight variants that are essentially the same. For example, the Hubert Index (Hubert 1977) can be expressed as a linear transformation of the Rand index as H (AA, B3 2R(A, I. All the properties defined in this paper are invariant under linear transformations and interchanging A and B. Hence, define the following linear equivalence relation similarity indices and check the properties for at most one representative of each equivalence class.
Definition 2. Similarity indices In and Iz are linearly equivalent there exists a nonconstant linear function f such that either (A, B) = (A2 B)) or I (4, B) = (I),))
This allows to conveniently restrict to indices for which higher numerical values indicate higher similarity of partitions. Table 5 in the Appendix lists the equivalent indices.
4.1 PROPERTY I: MAXIMAL AGREEMENT
The numerical value that index assigns similarity must be easily interpretable. In partieular, it should be easy to see whether the candidate clustering is maximally similar to (i.e., coincides with) the reference clustering. Formally, we require that [AA, A) Cmax is constant and either a strict upper bound for I (A, B) for all A & B. The equivalence from Definition 2 allows us to assume that (A, A) is maximum w.l.o.g. This property easy to check, and it is satisfied by almost all indices, except for SMI and Wallace.
Property 1:: Minimal agreement The maximal agreement property makes the upper range of the index interpretable. Similarly, having numerical value for low agreement would make the lower range interpretable. A minimal agreement is not well defined for general partitions: it is not clear which partition would be most dissimilar to given one. However, referring to Lemma ii Appendix, pair-counting indices form a subclass of graph similarity indices. For given graph G (V, E). clear that the graph most dissimilar to G is its complement G (V, E). Comparing graph to its complement would result in pair-counts N11 = Noo = and No0 + No1 = N. This motivates the following definition:
Definition 3. A pair-counting index has the minimal agreement property if there exists a constant Cmin that (NN1, Min.Noo. Noo) Cmin with equality if and only if Ni Noo = 0.
This property is satisfied by Rand, Correlation Coefficient, and Sokal&Sneath, while it is violated by Jaccard, Wallace, and Dice. Adjusted Rand does not have this property since substituting N1 Noo gives the non-constant AR(O, N10, No1, 0) No
Non
4.2 PROPERTY 3: SYMMETRY
Similarity is intuitively understood as a symmetric concept. Therefore, a good similarity index is expected to be symmetric, i.e., I(A, B) = I(B,A) A) for all partitions A, B Tables 2 and
II some applications, A and B may have different roles (e.g., reference and candidate partitions), and an asymmetric index may be suitable if there different consequences of making false positives false negatives.
4

---

Under review as a conference paper at ICLR 2021
Table 2: Requirements for general simi-
Table 3: Requirements for pair-counting indices
larity indices
Strong monotonicity
As. const. bascline
Max. agreement
Lin. complexity
Const. haseline
Max. agreement
Min. agreement
Lin. complexity
Const. baseline
Monotonicity
Monotonicity
Type of bias
Symmetry
Symmetry
X Distance
Distance
NMI
XXXX XXXX* X
R PU DI
<
L.V. X
NMImax
AR
XXXXXXX
X
FNMI
XXxXXX
X
<
VI
SMI
CC
FMeasure BCubed
S&SI CD
AMI
show that most indices are symmetric. The asymmetric ones are precision and recall (Wallace) and
FNMI (Amelio & Pizzuti 2015). which a product of NMI and the asymmetric penalty factor.
4.3 PROPERTY 4: LINEAR COMPLEXITY
For clustering tasks on large datasets, running time is crucial, and algorithms with superlinear time can be infeasible. In these cases, validation index with superlinear running time would be significant bottleneck. Furthermore, computationally heavy indices also tend to be complicated and hard to interpret intuitively. We say that an index has linear complexity when its worst-case running time is O(n). In Appendix C.2 we prove that any pair-counting index has (n) complexity. Many general indices have this property as well, except for SMI and AMI.
4.4 PROPERTY 4. DISTANCE
For some applications, a distance-inteepretatiie of dissimilarity may be desirable: whenever A is similar to and B is similar C, then A should also be somewhat similar to C. For example, assume that we have the reference clustering that is approximation of the ground truth (e.g.. labeled by experts). In such situations, may be reasonable to argue that the reference clustering is at most distance from the true clustering, that the triangle inequality bounds the dissimilarity of the candidate clustering to the unknown true clustering.
A function d is distance metric if it satisfies three distance axioms: 1) symmetry (d(A, B) d(B, A)); 2) positive-definiteness (d(A, A, B) 2 with equality iff A = B); 3) the triangle inequality (d(A,C) C) I d(A, B) + d(B, C)). We say that I is linearly transformable to distance metric if there exists a linearly equivalent index that satisfies these three distance axioms. Note that all three axioms invariant under re-scaling of d. We have already imposed the symmetry as a separate property, and the positive-definitenee is equivalent to the maximal agreement property. Therefore, whenever has these two properties, satisfies the distance property iff d( B) = Cmax [(A, B) satisfies the triangle inequality. for Cmax as defined in Section 4.1
Examples of popular indices having this property are Variation of Information and the Mirkin metric. In Vinh et al. (2010). it is proved that when Mutual Information is normalized by the maximum of entropies, the resulting NMI is equivalent to a distance metric. A proof that the Jaceard index is equivalent to distance is given in Kosub (201)). See Appendix C.I for all the proofs.
Among all the considered indices, there are two pair-counting ones having all the properties except for being distance: Sokal&Sneath and Correlation Coefficient. However, the correlation coefficient can be transformed a distance metric via a non-linear transformation. We
Correlation Distance
All known pair-counting indices excluded from this table do not satisfy either constant baseline, symmetry. maximal agreement.
5

---

Under review as a conference paper at ICLR 2021
define Correlation Distance (CD) B) arccos CC(A, B), where CC is the Pearson correlation coefficient and the factor 1/~ scales the index to [0, 1]. To the best of our knowledge. this Correlation Distance has never before been used as similarity index for comparing clusterings throughout the literature.
Let us point out that the Correlation Distance is indeed distance. It follows from the fact that the correlation coefficient is obtained by first mapping the binary vectors A, B the unit sphere, and then taking their standard inner product. The arccosine of the inner product of two unit vectors corresponds their angle, which is indeed a distance metric. more detailed proof of this claim can be found in Appendix E.2) Further in this section, we show that the distance property of Correlation Distance is achieved at the cost of not having the exact constant baseline, which still satisfied asymptotically.
4.5 PROPERTY 5: MONOTONICITY
When one clustering changed such that it resembles the other clustering more, the similarity score ought to improve. Hence, require index to be monotone w.r.t. changes that increase the similarity. This can be formalized via the following definition.
Definition 4. For clusterings and B, we say that B' is an A-consistent improvement of iff B * B' and all pairs of elements agreeing in A and B also agree in A and B'.
This leads to the following monotonicity property.
Definition 5. An index I satisfies the monotonicity property for every two clusterings A, B and any B' that is an A-consistent improvement of B, it holds that T(A, B') > I(A, B).
To look at monotonicity from a different perspective, we define the following operations:
Perfect split: B' is a perfect split of B (w.rt. A) if B' is obtained from B by splitting single cluster B3 into two clusters B1, B3 such that no two elements of the same cluster of A are in different parts of this split, i.e., for all i, A; n B₁ is subset of either BJ B/z-
Perfect merge: We say that B' is perfect merge of B (w.r.t. A) there exists some A and B1, B2 C A, such that B' is obtained by merging B1, B₂ into B1.
The following theorem gives an alternative definition of monotonicity and is proven Appendix F. Theorem 1. B' is an A-consistent improvement of B iff B' can obtained from B by a sequence of perfect splits and perfect merges.
Note that this monotonicity is stronger form of the first two constraints defined in (Amigó et al. 2009): Cluster Homogeneity is a weaker form of our monotonicity w.r.t. perfect splits, while Cluster Equivalence is equivalent
monotonicity w.r.t. perfect merges.
Monotonicity a critical property that should be satisfied by any sensible index. Surprisingly. not all indices satisfy this: we have found counterexamples that prove that SMI, FNMI, and Wallace do not have the monotonicity property. Furthermore, for NMI, whether monotonicity is satisfied depends on the normalization: the normalization by the average of the entropies has monotonicity, while the normalization by the maximum of the entropies does not.
Property 5'. Strong monotonicity For pair-counting indices, we can define stronger monotonic- ity property terms of pair-counts.
Definition 6. A pair-counting index I satisfies strong monotonicity if it increases with Nu1, Noo and decreases with No1-
This property is stronger than monotonicity it additionally allows for comparing similarities across different settings: we could compare the similarity between A1, B1 on 71 elements with the similarity between Ag, B2 n2 elements, different numbers of elements is similar to the Few data points property of SMI (Romano et al. 2014) that allows its scale have similar interpretation across different settings.
when n, * n2. This ability compare similarity scores across

---

Under review as a conference paper at ICLR 2021
We found several examples of indices that have Property 5 while not satisfying Property 5', Jaccard and Dice indices are constant w.r.t. Noo. so they are not strongly monotone. A more interesting example is the Adjusted Rand index, which may become strictly larger if we only increase No0-
4.6 PROPERTY 6. CONSTANT BASELINE.
This property is arguably the most significant: it is less intuitive than the other ones and may lead to unexpected consequences in practice. Informally, a good similarity index should not give a preference to candidate clustering B over another clustering C' just because B has many or few clusters. This intuition can be formalized using random partitions: assume that we have some reference clustering A and two random partitions B and C. While intuitively both random guesses are equally bad approximations of A, it has been known throughout the literature (Albatinch et al. 2006: Romano et al. 2014. Vinh et al. 2010) that some indices tend give higher scores for random guesses with a larger number of clusters. Ideally, we want the similarity value of a random candidate w.r.t. the reference partition to have fixed expected value Chase (independent of A). We formalize this in the following way. Let S(B) denote the specification of the cluster sizes of the clustering B, i.e., SBB) [ Bkg ||. where [...] denotes a multiset. For cluster sizes specification 8, let C(s) be the uniform distribution over clusterings B with S(B) =
Definition 7. An index satisfies the constant baseline property if there exists a constant Chase so that EB~C(+) [(A, B)] Chase for any cluster-sizes specification and clustering A with 1 < KA < n.
Note that this property is symmetric since it does not matter whether we permute the labels of A while keeping B constant or vice versa. In the definition, we have excluded the cases where A is a trivial clustering consisting of either or n clusters. Including them would cause problems for s = (AA), as C(s) would be a constant distribution surely returning and any sensible index should have I (A, A) o Cbasc
Constant baseline is extremely important in many practical applications: an index violates this property, then its optimization may lead to undesirably biased results. For instance, if a biased index is used to choose the best algorithm among several candidates, then it is likely that the decision will be biased towards those who produce too large or too small clusters. This problem is often attributed to NMI (Romano et al.] 2014, Vinh et al.] (2100), but we found out that almost all indices suffer from it. The only indices that satisfy the constant baseline property Adjusted Rand index, Correlation Coefficient, SMI, and AMI with Crase = 0 and Sokal&Sneath with Chase 1/2. Interestingly, out of these five indices, three were specifically designed to satisfy this property, which made them less intuitive and resulted in other important properties being violated.
The only condition under which the constant bascline property can be safely ignored is knowing in advance all cluster sizes. In this case, bias towards particular cluster sizes would not affect decisions. However, we are not aware of any practical application where such an assumption can be made. Note that knowing only the number of clusters is insufficient. We illustrate this in Appendix [D.4] where we also show that the bias of indices violating the constant baseline is easy to identify empirically.
Property 6': Asymptotic constant baseline For pair-counting indices, a deeper analysis of the constant baseline property is possible. Let ma = Nn + Nio. my = Ni + No1 be the number of intra-cluster pairs of A and B, respectively. Note that A and mg constant as A is constant and B ~ Css), so that its cluster-sizes are constant. Furthermore, the pair-counts Nio, No1 Noo are functions of N, m,, m. N11. Hence, to find the expected value of the index, we need to inspect it as a function of a single random variable N11. For a random pair, the probability that it is an intra-cluster pair of both clusterings is mm 2 so the expected values of the pair-counts are
Nu
MAMB N
No
MA NI., No mg N11 Noo N mA mB + Nu1- (1)
We can use these values to define a weaker variant of constant baseline.
Definition 8. A pair-counting index has the asymptotic constant baseline property if there exists constant Chase so that I (N11, No1, Noo) Chuse for all A with < KA < n.
In contrast to Definition 7 asymptotic constant baseline is very easy to verify: one just has to
substitute the values from T to the index and check whether the obtained value is constant. Another important observation is that under mild assumptions 7 (N11, Nio, No1, Noo) converges in probability
7

---

Under review as a conference paper at ICLR 2021
to I (N11, N1o, No1, Noo as grows which justifies the usage of the name asymptotic constant baseline, see Appendix D.2 for more details.
Note that the non- non-linear transformation of Correlation Coefficient to Correlation Distance makes the latter one violate the constant baseline property. CD does, however, still have the asymptotic constant baseline at 1/2 and value. To the best of our knowledge, there does not exist a cluster similarity index that is a distance while having the exact constant baseline.
prove in Appendix E.3 that the expectation in Definition 7 is very close to this
Biases of cluster similarity indices Given the fact that there are so many biased indices, one may be interested in what kind of candidates they favor. While it is unclear how to formalize this concept for general validation indices, we can do this for pair-counting ones by analyzing them in terms of a single variable.
While there are previous attempts to characterize types of biases (Lei et al. 2017), they mostly rely on an analysis based on the number of clusters. However, we argue that the number of clusters not a good measure of the granularity of a clustering. Instead, we show that the number of inter-cluster pairs should be analysed to determine the biases of pair-counting indices. We formally define and analyze two types of biases: NPdec and NPinc, where NP stands for Number of inter-cluster Pairs.
Definition 9. Let I be a pair-counting index and define 1 [(s) (mA, mB) (Ni1, Nio. Noo) for the expected pair-counts as defined in (T). We define the following biases:
(i) 1 suffers from NPdec bias if there are A,, mB E (0,N) such that
d (0) (mA, mB) > 0.
dmn
(ii) I suffers from NPine bias if there are mA, mg (0, N) such that
[(s) (mA, mB) 0.
g
Applying this definition to Jaccard (++ mB) A(m m mmmg and Rand R (m PB)
1 - a + mB)/N + 2m N2 immediately shows that Jaccard suffers from NPdec bias and Rand suffers from both biases, confirming the findings Lei al. (2017). Furthermore, the direction of the monotonicity for the bias of Rand is now determined by the condition 2m > N instead of the more complicated but equivalent condition on the quadratic entropy of A that is given in Lei et al.) (017). Performing the same for Wallace and Dice shows that both suffer from NPdec bias. Note that an index satisfying the asymptotic constant baseline property will not have any of these biases as ((0) (m mB)
Cbasc.
5 DISCUSSION AND CONCLUSION
At this point, we better understand the theoretical properties of cluster similarity indices, so it is time to answer the question: which index is the best? Unfortunately, there is no simple answer, but we can make an informed decision. In this section, we sum up what we have learned, argue that there are indices that are strictly better alternatives than some widely used ones, and give practical advice on how to choose suitable index for a given application.
Among all properties discussed in this paper, monotonicity is the most crucial one. Violating this property is a fatal problem: such indices can prefer candidates which are strictly worse than others. Hence, we cannot advise using the well-known NMImaz. FMeasure, FNMI, and SMI indices.
The constant baseline property is much less trivial but is equally important: it addresses the problem of preferring some partitions only because they have small or large clusters. This property is essential unless you know all cluster sizes. Since we are not aware of practical applications where all cluster sizes are known, below we assume that this is not the case This requirement is satisfied by just a few indices, we are only left with AMI, Adjusted Rand (AR), Correlation Coefficient (CC), and Sneal&Sneath (S&S). Additionally, Correlation Distance (CD) satisfies constant baseline asymptotically and deviations from the exact constant baseline are extremely small (see Section
E.3
Let us note that among the remaining indices, AR is strictly dominated by CC and S&S since it does not have the minimum agreement and strong monotonicity. Also, similarly AMI, AR is specifically
However, in applications where such assumption holds, it can be reasonable to use, e.g., BCuhed, Variation of Information, and NMI.
8

---

Under review as a conference paper at ICLR 2021
created to have a constant baseline, which made this index more complex and less intuitive than other pair-counting indices. Hence, we are only left with four indices: AMI, S&S, CC, and CD.
According to their theoretical properties, all these indices are good, and any of them can be chosen. Figure 2 illustrates how a final decision can be made. First, one can decide whether the distance property is needed. For example, suppose one wants to cluster the algorithms by comparing the partitions provided by them. In that case, the metric property of a similar- ity index allows the use of metric clustering algorithms. In this case, distance property is desirable, and CD is the best choice: it has all properties except for the exact constant base- line, which is still satisfied asymptotically. Next, it is important to decide whether computa- tion time is of the essence. Linear computation time is essential for large-scale applications. For instance, assume that there is a pro- duction system that groups news articles or user photos. There a candidate al- gorithm, and we want to compare it with the currently used one to avoid major changes. In this case, we have to com- pare huge partitions, and time is of the essence. Another example is multiple comparisons: choosing the best algo- rithm among many candidates (differ- ing, c.g., by parameter value). If this the case, then AMI is not proper choice, and one has to choose between CC and S&S. Otherwise, all three in- dices are suitable according to our for- mal constraints.
Do need metric properties of scores?
Do you need computation"
Use CD3
No
small dusters
Une OC 585
Hore
Use CC sas
Use AM1
Figure 2: Example of how can make a decision among good cluster similarity indices.
Let us discuss an (informal) criterion that may help to choose between AMI and pair-counting alternatives. Different indices may favor a different balance between errors in small and large clusters. In particular, all pair-counting indices give larger weights to errors in large clusters; misclassifying one element in a cluster of size costs k- --1 incorrect pairs. It is known (empirically) that information- theoretic indices do not have this property and give higher weight to small clusters (Amigó et al.) 2 4 Amigó et al. (2009) argue that for their particular application (text clustering), is desirable not to give a higher weight to large clusters. In contrast, there are applications where the opposite may hold. For instance, consider a system that groups user photos based on identity and shows these clusters to user as ranked list. In this case, a user is likely to investigate the largest clusters consisting of known people and would rarely spot an error in a small cluster. The same applies to any system that ranks the clusters, e.g., to news aggregators. Based on what is desirable for particular application, one can choose between AMI and pair-counting CC and S&S.
The final decision between CC and S&S is hard to make since they are equally good in terms of their theoretical properties. Interestingly, although some works (Choi et al. 2010 Lei et al.) (017) list Pearson correlation as a cluster similarity index, it has not received attention that our results suggest it deserves, similarly to S&S. First, both indices are interpretable. CC is a correlation between the two incidence vectors, which is a very natural concept. S&S is the average of precision and recall (for binary classification of pairs) plus their inverted counterparts, which can also be intuitively understood. Also, CC and S&S usually agree in practice: in Tables [ and [6) we can see that they have the largest agreement. Hence, one can take any of these indices. Another option would be to check whether there are situations where these indices disagree and, if this happens, perform an experiment similar what we did in Section for news aggregation.
Finally, while some properties listed in Tables 2 and are not mentioned in the discussion above, they can be important for particular applications. For instance, maximum and minimum agreements are useful for interpretability, but they can also be essential if some operations are performed over the index values: e.g., averaging the scores of different algorithms. Symmetry can be necessary if there is no "gold standard" partition, but algorithms are compared only to each other.
'This is an interesting aspect that has not received much attention in our research since we believe that the desired halance hetween large and small clusters may differ per application and we are not aware of proper formalization of this "level of halance" in a general form.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ahmed N. Albatineh, Magdalena Niewiadomska-Buge and Daniel Mihalko. On similarity in- dices and correction for chance agreement. Journal of Classification, 23(2):01-313,, Sep 2006. ISSN 1432-1343, doi: 10. N0.10077/00035700000000111 URL httttts:///oo..rr////
500357- 0017-2
Mchdi Allahyari, Seyedamin Pouriyeh, Mehdi Assefi, Saied Safaei, Elizabeth D Trippe, Juan B Gutierrez, and Krys Kochut. A brief survey text mining: Classification, clustering and extraction techniques. arXiv preprint arXiv: (eXXxx:707.02911 2017.
Alessia Amelio and Clara Pizzuti. Is normalized mutual information a fair measure for comparing community detection methods? In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015, pp. 1584-1585. ACM, 2015.
Enrique Amigó, Julio Gonzalo, Javier Artiles, and Felisa Verdejo. A comparison of extrinsic clustering evaluation metrics based on formal constraints. Information retrieval, 12(4))461 -466, 2009.
Vladimir Batagelj and Matevz Bren. Comparing resemblance measures, Journal of Classification, 12 (1):73-900, Mar 1995. ISSN 1432-1343. doi: 10.1007/BF011202668, URL https: htttht://ddoooooo
Shai Ben-David and Margareta Ackerman. Measures of clustering quality: A working set of axioms for clustering. Advances in neural information processing systems, 21:121-128, 2008.
Shai Ben-David and Margareta Ackerman. Measures of clustering quality: A working set of axioms for clustering. In Advances in neural information processing systems, pp. 121-128, 2009.
Seung-Seok Choi, Sung-Hyul Cha, and Charles C Taappert. A survey of binary similarity and distance measures. Journal of Systemics, Cybernetics and Informatics, 8(1):43-48, 2010.
Claire Donnat and Susan Holmes. Tracking network dynamics: a survey of distances and similarity metrics, 2018.
GitHub. Clustering datasets. 2020.
Lawrence Hubert. Nominal scale response agreement as a generalized correlation. British Journal
of Mathematical and Statistical Psychology, 30(1) 30(1):98-103) 1977. doi: 10. 10.1111/.2044-3117 1977.bb00728.x. ttt hot.tttpps///nnnieiiiiirrrae 2044-8313 (0007228..77.....
waatrrary..llleee wiley. caat..com//aee wwt.coocmoccccccoccoooooca /tcmm//dd//dff/1.11110
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-218 1985.
Jon Kleinberg. An impossibility theorem for clustering, Advances in neural information processing systems, 15:463-455 47663-470.15 2002.
Sven Kosub. A note on the triangle inequality for the jaccard distance. Pattern Recogni-
tion Letters, 120:36 38, 2019. ISSN 0167-8655. doi: https///tb.orr///..0006/.....
20.8.12.007. URL http: www. www.:eeccneeieet..ooooooo///e/ee wwt. com.//cceeecc///rtiicce/////
S0 011676655880911
Yang Lei, James C. Bezdek, Simone Romano, Nguyen Xuan Vinh, Jeffrey Chan, and James Bailey. Ground truth bias external cluster validity indices. Pattern Recognition, 65:58 70, 2017. ISSN 0031-3203. doi: http:///tii.ngg///oooooiiigggagg
URL http:
http://wc......ccc..oooccoooeoea www. www.scciencedirec.... http:/rwww..cccceeeereeeeeeeeeee
Marina Meilä. Comparing clusteringsan information based distance. Journal of multivariate analysis, 98(5):873 2tt.://////ttts////o..eeeeeeeede pi / /t01:/0007779900000
10

---

Under review as a conference paper at ICLR 2021
Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):26613, 2004.
S Romano, Bailey, Nguyen the vinh, and Karin Verspoor. Standardized mutual information for clustering comparisons: One step further in adjustment for chance. 31st International Conference on Machine Learning, ICML 2014, 4:2873-2882, 01 2014.
Simone Romano, Nguyen Xuan Vinh, James Bailey, and Karin Verspoor. Adjusting for chance clustering comparison measures. The Journal of Machine Learning Research, 17(1):66354466,
2016.
Scikit-learn. Clustering algorithms.
lss
c slustering.hta 2020.
Alexander Strehl. Relationship-based clustering and cluster ensembles for high-dimensional data mining. PhD thesis, 2002.
Stijn Van Dongen and Anton J Enright. Metric distances derived from cosine similarity and pearson and spearman correlations. arXiv preprint 1XXv:3200..115 2012.
Twan Van Laarhoven and Elena Marchiori. Axioms for graph clustering quality functions. The Journal of Machine Learning Research, 15(1):193-215 2014.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: is a correction for chance necessary? In Proceedings of the 26th annual international conference on machine learning, pp. 1073-1080. ACM, 2009.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties. normalization and correction for chance. Journal of Machine Learning Research, 1((0c)):8377-2554 2010.
Seppo Virtanen and Mark Girolami. Precision-recall balanced topic modelling. In Advances in Neural Information Processing Systems, pp. 6750-6759, 2019.
Zhongdao Wang, Liang Zheng, Yali Li, and Shengjin Wang. Linkage based face clustering via graph convolution network. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1117-1125, 2019.
Wahyu Wibowo and Hugh E Williams. Strategies for minimising errors in hierarchical web categori- sation. In Proceedings of the eleventh international conference on Information and knowledge management, pp. 525-531, 2002.
Dongkuan Xu and Yingjie Tian. A comprehensive survey of clustering algorithms. Annals of Data Science, 2(2):165-193, 2015.
A FURTHER RELATED WORK
Several attempts the comparative analysis of cluster similarity indices have been made in the literature, both in machine learning and complex networks communities. In particular, the problem of indices favoring clusterings with smaller or larger clusters has been identified (Albatineh et al. 2006 Lei et al. 2017 Vinh et al., 2009 2010). The most popular approach to resolving the bias of an index subtract its expected value and normalize the resulting quantity to obtain an index that satisfies the maximum agreement property. This approach has let to 'adjjstedd indices such as AR (Hubert &
Arabie 1985) and AMI (Vinh al. 2009).. In Albatineh et al. (2006), the family of pair-counting indices C is introduced for which adjusted forms can be computed casily. This family corresponds to
the set of all pair-counting indices that are linear functions of Nu for fixed N1 + +No N11 +No1. A generalization of information- -hhooreti indices by Tsallis e-etrropy is given in Romano et al. (2016) and is shown to correspond to these generalized indices for chance.
indices for = 2. Formulas are provided for adjusting
disadvantage of this adjustment scheme is that an index can be normalized in many ways, while is difficult grasp the differences between these normalizations intuitively. For example, three

---

Under review as a conference paper at ICLR 2021
variants of AMI have been introduced (Vinh et al. 2009), and we show that normalization by the maximum entropies results in an index that fails monotonicity. [Romano et al. (2014) go one step further by standardizing mutual information, while Amelio & (ezzz multiply NMI with penalty factor that decreases with the difference in the number of clusters.
In summary, all these works take popular biased index and 'patch' it to get rid of this bias. This approach has two disadvantages: firstly, these patches often introduce new problems (e.g.. FNMI and SMI fail monotonicity), and secondly, the resulting index is usually less interpretable than the original. We have taken a different approach in our work: instead of patching existing indices, we analyze previously introduced indices to see whether they satisfy more properties. Our analysis shows that ARI is dominated by Pearson correlation, which was introduced more than 100 years before ARI. Therefore, there was no need to construct ART from Rand in the first place.
In Lei et al. (2017), the biases of pair-counting indices are characterized. They define these biases as a preference towards either few or many clusters. They prove that the direction of Rand's bias depends on the Havrda-Charvat entropy of the reference clustering. In the present work, we show that the number of clusters not an adequate quantity for expressing these biases. We introduce methods to easily analyze the bias of any pair-counting index and simplify the condition for the direction of Rand's ' bias to A < N/2.
A paper closely related to the current research (Amigó et al. 2009) formulates several constraints (axioms) for cluster similarity indices. Their cluster homogeneity is a weaker analog of our mono- tonicity w.r.t. perfect splits while their cluster equivalence is equivalent to our monotonicity w.r.t. perfect merges. The third rag bag constraint is motivated by a subjective claim that "introducing disorder into disordered cluster is less harmful than introducing disorder into a clean cluster". While this is important for their particular application (text clustering), we found no other work that deemed this constraint necessary; hence, we disregarded this constraint in the current research. The last constraint by Amigó et al. (2009) concerns the balance between making errors in large and small clusters. Though this is an interesting aspect that has not received much attention in our research, this constraint poses particular balance while we believe that the desired balance may differ per application. Hence, this property seems to be non-binary and we are not aware of proper formalization of this "level of balance" in general form. Hence, we do not include this in our list of formal properties. The most principal difference of our work compared to Amigó et al. (2009) is the constant baseline which was not analyzed in their work. We find this property extremely important while is failed by most of the widely used indices including their BCubed. To conclude, our research gives a more comprehensive list of constraints and focuses those that are desirable in a wide range of applications. We also cover all similarity indices often used in the literature and give formal proofs for all index-property combinations.
A property similar to our monotonicity property is also given in Meilä (2007), where the similarity between clusterings A and B is upper-bounded by the similarity between A and A @ B (as defined in Section C.4.. One can show that this property is implied by our monotonicity but not vice versa, i.e., the variant proposed by Meilä (2007) is weaker. Our analysis of monotonicity generalizes and unifies previous approaches to this problem, see Theorem | that relates consistent improvements to perfect splits and merges.
While we focus on external cluster similarity indices that compare a candidate partition with a reference one, there are also internal similarity measures that estimate the quality of partitions with respect to internal structure of data (e.g., Silhouette, Hubert-Gamma, Dunn, and many other indices). Kleinberg (002) used an axiomatic approach for internal measures and proved an impossibility theorem: there are three simple and natural constraints such that no internal clustering measure can satisfy all of them. More work in this direction can be found in, c.g., BBen-David & Ackerman (2008). In network analysis, internal measures compare candidate partition with the underlying graph structure. They quantify how well a community structure (given by a partition) fits the graph and are often referred to goodness or quality measures. The most well-known example is modularity (Newman & Girvan 2004). Axioms that these measures ought to satisfy are given in (Ben-David & Ackerman 2009 Van Laarhoven & Marchiori 2014). Note that all pair-counting indices discussed in this paper can also be used for graph- partition similarity, as we discuss in
Section B3
12

---

Under review as a conference paper at ICLR 2021
B CLUSTER SIMILARITY INDICES
B.1 GENERAL INDICES
Here we give the definitions of the indices listed in T We define the contingency variables as nij |A, n Byl. We note that all indices discussed in this paper can be expressed functions of these contingency variables.
The F-Measure is defined the harmonic mean of recall and precision. Recall is defined
kA
r(A B)
max {nihh
jE(Ba]
and precision is its symmetric counterpart rB,
Amigó et al. 2009), recall is redefined as
kg
1
r' (A, (A, B)
2
A
Rij
and BCubed is defined as the harmonic mean of (AA, B) and r' (B, A).
The remainder of the indices are cnormatiiontthooretee and require some additional definitions. Let P1.....3 P Pt be discrete distribution (i.e., all values are nonnegative and sum to 1). The Shannon entropy is then defined as
H pc): = Σ Pi log(p.).
The entropy of clustering is defined the entropy of the cluster-lahel distribution of random item, iee,
== =
and similarly for (B). The joint entropy H(A, B) is then defined as the entropy of the distribution with probabilities (ps))se(kallJElaa) where Ptj = niz/n.
Variation of Information (Meila 2007) is defined
VI(A, 2 B) H(A) H(B).
Mutual information is defined as
(A, H() H()
The mutual information between A and B is upper-bounded by H(A) and H(B), which gives multi- ple possibilities to normalize the mutual information. In this paper, we discuss two normalizations: normalization by the average of the entropies } (H()) + H(B)). and normalization by the maximum of entropies (A), H (B)). We will refer to the corresponding indices as NMI and NMI respectively:
M(A, B)
NMT(A, B) (H(A) + H(B))/2
M(A, B)
NMI (aaiaaxxAAA () max{ (A), H(B)
Fair NMI a variant of NMI that includes factor that penalizes large differences in the number of clusters (Amelio & Pizzuti 2015). It is given by
FNMI( (AMI(A,AU B) = e - kal //kA / B).
In this definition, NMI may be normalized in various ways. We note that a different normalization would not result in properties being satisfied.
13

---

Under review as a conference paper at ICLR 2021
Adjusted Mutual Information addresses for the bias of NMI by subtracting the expected mutual information Vinh et al. (2009). It is given by
M(A, B) (M B')
AMI(A, B)
V (A(A) H(B) ( (A,, B']]
Here, a normalization by the geometric mean of the entropies used, while other normalizations are also used (Vinh et al.) 2009).
Standardized Mutual Information standardizes the mutual information w.r.t. random permutations of the items (Romano et al. 2014), i.c.,
M(A, B) - E EBr-C B*))
SMI(A, B)
(M, B)))
where a denotes the standard deviation. Calculating the expected value and standard deviation the mutual information is nontrivial and requires significantly more computation power than other indices. For this, we refer to the original paper (Romano et al. 2014). Note that this index is symmetric since it does not matter whether we keep A constant while randomly permuting B or keep B constant while randomly permuting A.
B.2 CAU-CCONN INDICES AND THEIR EQUIVALENCES
Pair-counting similarity indices are defined in Table 4 Table 5 lists linearly equivalent indices (see Definition 2). Note that our linear equivalence differs from the less restrictive monotonous equivalence given in (Batagelj & Bren 1995). In the current work, have to restrict to linear equivalence as the constant baseline property is not invariant to non-linear transformations.
B.3 DEFINING THE SUBCLASS OF CAR-COUNTING INDICES
From Definition of the main text, it follows that pair-counting index function of two binary vectors Ā, B of length N. Note that this binary-vector representation has some redundancy: whenever u, and w form intra-cluster pairs, we know that u, w must also be an intra-cluster pair. Hence, not every binary vector of length N represents a clustering. The class of N-dimensional binary vectors is, however, isomorphic to the class of undirected graphs indices are also able to measure the similarity between graphs For example, for an undirected
vertices. Therefore, pair-counting
graph G = (V, E), one can consider its incidence vector G (1f w) E E)),, Hence, pair- counting indices can be used to measure the similarity between two graphs between a graph and clustering. So, one may see a connection between graph and cluster similarity indices. For example, the Mirkin metric is pair-counting index that coincides with the Hamming distance between the edge-sets of two graphs (Donnat & Holmes] 2018). Another example is the Jaccard graph distance, which turns out to more appropriate for comparing sparse graphs (Donnat & Holmes 2018). Thus, all pair-counting indices and their properties discussed in the current paper can also be applied to graph-graph and graph-partitte
similarities.
In this section, we show that the subclass of pair-counting similarity indices can be uniquely defined by the property of being pair-synmn maim-yymmttic.
For two graphs G1 and G2 let MG.G, denote the N x 2 matrix that is obtained by concatenating their adjacency vectors. Let us write [( (MG, G.) for the similarity between two graphs G1, G2 according to some graph similarity index 7(G), We will now characterize all pair-counting similarity indices subclass of the class of similarity indices between undirected graphs
Definition 10. We define graph similarity index 1 (G) (MGig2) to be pair-symmetric interchanging two rows of MG.G,, leaves the index unchanged.
We give the following result.
Lemma 1. The class of pair-symmetric graph similarity indices coincides with the class of pair- counting cluster similarity indices.
Throughout the literature, the Mirkin metric is defined as 2(N10 No1). but we use this variant it satisfies the scale-invariance.
14

---

Under review as a conference paper at ICLR 2021
Table 4:
A selection of pair-counting indices. Most of these indices are taken from Lei al. 2017
Index (Abbreviation)
Expression
Rand (It)
MNp N11 + No0 Not Noo
(N 1N10 t-Woo
Adjusted Rand (AR)
M1 (N
1100
Jaccard (J)
Nu
N11 +
Jaccard Distance (JD)
Nin +N
N11 N1o
Wallacel (W)
N11
N
Wallace2
N11
N11
Dice
2N11
2N 2No
Correlation Coefficient (CC)
Nac NooNoi
(NN NNol(An (N Noo No1)
Correlation Distance (CD)
arccos
Nog No0
MIN Not (Noo Noo No1
Sokal&Sneath- (S&S)))
N11
No NIttNo1
Noo
Noo +o1
Minkowski
Nint-Nu
Mi1+ Ni0
Hubert (IT)
N11 + Non No1-No1
Noo
Folkes&Mallow
N1
V(N.+ NiollNoooNN11- (N No1
AN1
Sokal&&Scath-II
1 +Not
Normalized Mirkir
Nio+Nni No1
Noo+No++No Nai +No0
Kulczynski
Nu
No
Ni No
Ni. NRa-Na
McConnaughey
Yule
N11 Non N1c
N10 M10 No1 Not Noo
Baulieu-I
(M, N.a Noj +N No1 No
Russell&Rao
N11 N
Fager&MeGowan
Ni
+ -N1) Mii Noo (aoo--ioo Nin
2/N1++N10
Peirce
(M NNo Nip)
Baulicu-11
Nu Noo Noo
t 2
Sokal&Sneath-III
Ni
Gower&l.egendre
4
Ni1+ 1 (N1)+NNN))+
Rogens&Tanimoto
N11 4oo
N11 No
Goodman& Koodman&KKuskal
Ni Nog -Xn
No1
Proof. A matrix is ordered list of its rows. An unordered list is multiset. Hence, when disregard the ordering the matrix MAB, we get a multiset of the rows. This multiset contains at most four distinct elements, each corresponding to one of the pair-counts. Therefore, each I(C) (MAB) that is symmetric w.r.t. interchanging rows is equivalently a function of the poir-counts of and B.
15

---

Under review as a conference paper at ICLR 2021
Table 5: Equivalent pair-counting indices
Representative Index
Equivalent indices
Rand
Normalized Mirkin Metric, Hubert Jaccard Distance
Jaccard
Wallace1
Wallace2 McConnaughey
Kulczynski
C CHECKING PROPERTIES FOR INDICES
In this section, we check non-trivial properties for all indices. The properties of symmetry, maxi- mal/minimal agreement and asymptotic constant baseline can trivially be tested by simply checking
I(B, A) ((A,B) [(A, A) Cmax. I(0, N20, No1, 0) = Cmin and [(P) (PAPB. P.A PB) respectively.
Coase
C.I DISTANCE
C.1.1 POSITIVE CASES
NMI and VI. In (Vnn et al. 2010) it is proven that for max-nommalization NMI is a distance, while Meilä 2007 it is proven that VI is a distance.
Rand. The Mirkin metric 1 R corresponds rescaled version of the size of the symmetric difference between the sets of intra-cluster pairs. The symmetric difference known to distance metric.
Jaccard.
Kosub 2019 it is proven that the Jaccard distance 1- - J is indeed a distance.
Correlation Distance. In Theorem
E.2 it is proven that Correlation Distance is indeed distance.
C.1.2 NEGATIVE CASES
To prove that an index that satisfies symmetry and maximal agreement not linearly transformable to distance metric, only need to disprove the triangle inequality for one instance of its equivalence class that is nonnegative and equals zero for maximal agreement.
FNMI and Wallace. These indices cannot be transformed to distances as they not symmetric.
SMI. SMI does not satisfy the maximal agreement property (Romano et 2014), so cannot be transformed to metric.
FMeasure and BCubed. We will use a simple counter-example, where [ 3, = 1,kB
kc 3. Let denote the FMeasure and BCubed by FM, BC respectively. We get
1 FM(A, C) = 1 - 0.5 (1 - 0.8) + (1 0.8) = =(1 FM-FFM(A,)) B)) FM(B,C) C))
and
-) - 0.5 (1 - 0.71) + (1- 0.8) ~ (1 BC(A + +(1 BC(B,C)), so that both indices violate the triangle inequality in this case.
Adjusted Rand, Dice, Correlation Coefficient, Sokal&Sneath and AMI. For these indices, the following counter-example: Let A {{0,, 1). (2), {3)) B {{0, 1). {2, 3]}, C {[O}. {1}, (2, 3)). Then PAB = PBC = 1/6 and PAC = 0 while PA = PC = 1/6 and pB = 1/3. By substituting these variables, one can sce that
1 7(p) (pAC, PA,PC) (1 7 (PAB, PA. PB)) (1 7(0) (PBC, PB, pC));
holds for each these indices, contradicting the triangle inequality. The same A, and also form counter-example for AMI.
16

---

Under review as a conference paper at ICLR 2021
C.2 LINEAR COMPLEXITY
We will frequently make use of the following lemma:
Lemma 2. The nonzero values nij
nuj can be computed in O
Proof. We will store these nonzero values in a hash-table that maps the pairs (i,j) to their value negi These values obtained by iterating through all items and incrementing the corresponding value of Rij- For tashe, searches and insertions are known to have amortized complexity complexity O(1), meaning that any sequence of such actions has worst-case running time of (n)). from which the result follows.
C.2.1 POSITIVE CASES
NMI, FNMI and VI. Given the positive values of nay. it is clear that the joint and marginal entropy values be computed in (n)) From these values, the indices be computed in constant time, leading to a worst-case running time of Onn).
FMeasure and BCubed. Note that in the expressions of recall and precision as defined by these indices, only the positive values of ni contribute. Furthermore, all of the variables ai, by and naj appear at most once, so that these can indeed be computed in O(n).
Pair-counting indices. Note that Nn = Em,,> >0
(Tey) can obviously be computed in Onn). Sim- ilarly, ma = Ete (c) and m. can be computed in akka), O(kg) respectively. The other pair- counts are then obtained by Nio mA - N11. No1 mg Ni and Noo N mm mg + N11-
C.2.2 AMI AND SMI.
Both of these require the computation of the expected mutual information. It has been known Romano ct al. (2016) that this has a worst-case running time of (n max(ka, kB}) while max(k A can be (z).
C.3 STRONG MONOTONICITY
C.3.1 POSITIVE CASES
Correlation Coefficient. This index has the property that inverting one of the binary vectors results in the index flipping sign. Furthermore, the index is symmetric. Therefore, we only need to prove that this index is increasing in N11. We take the derivative and omit the constant factor ((No + N1o) + N)
Noo
NN1 N1oNNo1 (2N, + Ni0 + No1) [(Nn + Nio) No 1.
V(N + (N1 + No1) $. N (N10 + No1) + Noo
No + N + No1)
> 0. [NN + NNo + +N:))]
[(Nn + (No) + N.
Correlation Distance. The correlation distance satisfies strong monotonicity as is a monotone transformation of the correlation coefficient, which meets the property.
Soeal&SSeeah. All four fractions are nondecreasing N11, Noo and nonincreasing in N10- No1 while for each of the variables there is one fraction that satisfies the monotonicity strictly so that the index is strongly monotonous.
Rand Index. For the Rand index, it can be easily seen from the form of the index that it is increasing in Nu, Non and decreasing in Nio, Noi that it meets the property.
17

---

Under review as a conference paper at ICLR 2021
C.3.2 NEGATIVE CASES
Jaccard, Wallace, Dice. All these three indices are constant w.r.t Noo- Therefore, these indices do not satisfy strong monotonicity.
Adjusted Rand. It holds that
A A 2,1,,,1,0) < AR(1,3,1,0) so that the index does not meet the strong monotonicity property.
C.4 MONOTONICITY
C.4.1 POSITIVE CASES
Rand, Correlation Coefficient, Sokal&Sneath,, Correlation Distance. Strong monotonicity im- plies monotonicity. Therefore, these pair-counting indices satisfy the monotonicity property.
Jaccard and Dice. It can be easily seen that these indices are increasing in Ni while decreasing in Nio, No1- For Noo. we note that whenever Noo gets increased, either Nio No1 must decrease, resulting in an increase of the index. Therefore, these indices satisfy monotonicity.
ad Adjusted Rand. Note that for b, b + 0, holds that
+ c b d
For Adjusted Rand, we have
Nu1 N (Ni Nio) No1), b= a 5 No1).
Because of this, when we increment either Nn or Noo while decrementing either Nio or No1, we get d = C Hence, we need to prove >> a(c 1)/b, equivalently
(N (N1) + No1) - Nu1
a
e
2(b a)
Nio + No1
For simplicity we rewrite this to
PAB PAPB
PA + PB 2PAB 0,
where PA = = + (N1 + Noo) E (0,1) and Pa = * + No1) E (0, 1). If we increment Noo while decrementing either Nio No1. then
1 (N11 + No1)
(Nu + N1o), N
{PA.
The symmetry of AR allows us to w.l.o.g. assume that PA. We write
PAB PAPB
p3 + (1 2pA)pAB
PA +
PA + PB 2pAB
PA PB 2PAB
When PA < then this is clearly positive. For the case PA > 1. we bound PAB PA and bound the numerator by
P + (1 2pa)PA (1- P-)PA > 0.
This proves the monotonicity for increasing Noo. When incrementing Nn while decrementing either N10 or No1, we get e [1 PA. PB). Again, we assume w.l.o.g. that PA and write
PAB PAPB
Pa(1 PA) (1 2pA)(PB PAB)
1- PA
PA + pn 2pan
PA + 2pA8
This is clearly positive whenever PA < 1. When PA > 2, we bound PAB 2 PA +B - and rewrite the numerator
PA(1 p() (1 (1- -1-21ppp0 2P - 1) (1 (1)-AA) -1) >
This proves monotonicity for increasing N11. Hence, the monotonicity property is met.
18

---

Under review as a conference paper at ICLR 2021
NMI and VI. Let B' be obtained by perfect split of cluster B₁ into B1, B/j. Note that this increases the entropy of the candidate while keeping the joint entropy constant. Let us denote this increase in the candidate entropy by the conditional entropy H [) = H ( (B) > O. Now, for NMI, the numerator increases by H B) while the denominator increases by at most H (B) (dependent on (AA) and the specific normalization that is used). Therefore, NMI increases. Similarly, VI decreases by H [3 (B) Concluding, both NMI and VI are monotonous w.r.t. perfect splits. Now let 3" be obtained by perfect merge of B B2 into By. This results in difference of the entropy of the candidate H (B") H (B) = - BB) < O. The joint entropy decreases by the same amount, so that the mutual information remains unchanged. Therefore, the numerator of NMI remains unchanged while the denominator may may not change, depending on the normalization. For min- or max-normalization, it may remain unchanged while for any other average increases. Hence, NMI does not satisfy monotonicity w.r.t. perfect merges for min- and max- normaaaaliziioonn but does satisfy this for corage-normaaization For VI, the distance will decrease by H (BIB") so that indeed satisfies monotonicity w.r.t perfect merges.
Let B' be obtained by splitting a cluster B₁ into Bi, B'z. This split increases the mutual information by (B) (AA @ B'I @ B). Recall the definition of the meet A @ B from C.4 and note that the joint entropy equals H & B). For perfect split we have H(A @ B² & B The expected mutual information changes with
AMI.
EA [M (A', BB) - (A', B] = (B (A @ B*) - H (A's @ B)}
where we choose randomize A instead of B' and B for simplicity. Note that for all A',
( & B) - (A' & B') = H(A' & B)
with equality if and only if the split is a perfect split w.r.t. A'. Unless A consists exclusively of singleton clusters, there is a positive probability that this split is not perfect, so that the expected value positive. Furthermore, for the normalization term, we have / (B))) (A) +
(BBBB). Combining this, we get AMI(A,
M(A, B)- (M( B)] + EAI-C(SIA) (H @ A' & B)] (B)A) - H(B(B) E (N-CCSCAjIAMAAA B)] + EA--C(S(A)) (A'' & B'A & B)]
M(A, B) - EA'-Cis(a)) (M'A', B)] + E (I @ A' @ B)]
(B) E. A C(S(A)) (M B)] + EA (H A' @ B)]
M(A, B) - E CC (M B)]
AM)(A,
(B(A)H(B) - E A A)) (M', B)]
This proves that AMI satisfies monotonicity w.r.t. perfect splits.
Now let 8" be obtained by a perfect merge of B1, B2 into B". Again, we have H(B") - HB)
H (B) B" < 0) and (A, B") (A, B). Let A' C(S(A)) (again, randomizing A instead of B and B" for simplicity), then H(A' & B") 2 (AA @ B)- H(B B") with equality if and only if B" is a perfect merge w.r.t. A' which happens with probability strictly less than (unless consists of a single cluster). Therefore, long as KA > 1. the expected mutual information decreases. For the normalization, we have (H(A)H(B") < / (B)). Hence,
AMI(A,B") = MA,, B²) - E (L B"]]
(H(A) - E (A (A', B")
M(A, B) E EC (A',
VH(A) ( (B") E EAIAC(S(AI) [M('', B")]
M(A, B) E EX (A',,, B)]
/ (B"))((B") E (()C(((AA) [M B)]
M(A, B) E EAAAC(((AA) (M (A', B)]
(B(A) EX [M (A',B)
AMT(A, B).
19

---

Under review as a conference paper at ICLR 2021
BCubed. Note that perfect merge increases BCubed recall while leaving BCubed precision unchanged and that perfect split increases precision while leaving recall unchanged. Hence, the harmonic mean increases.
C.4.2 NEGATIVE CASES
FMeasure. We give a numerical counter-example: consider A = () {{0, 1, 3), (4,5), {6}} and merge the last clusters obtain 3' (4,, Then, the FMeasure remains unchanged and equal to 0.73, violating monotonicity w.r.t perfect merges.
FNMI We will give the following numerical counter-example: Consider A {{0, (2) (
{10), (1}. [2.33} and merge the first two clusters obtain B' = [10, This results in
FN, B) 0.67 0.57 FNMI(A, B').
This non-monotonicity is caused by the penalty factor that equals 1 for the pair A, B and equals exp(-1/3) 2 0.72 for A, B'.
SMI. For this numerical counter-example rely on the Matlab-immplementatien of the index by its original authors (Romano et al. 2014). Let A = (0......44, and consider merging the two clusters resulting in B' = ((0.1,2,3) (4), (5)). The index remains unchanged and equals before and after the merge.
4), (,)). {10, 1}. (2,3), (4), (5))
Wallace. Let A and let kB 1. Then any merge of B is perfect merge, but increase occurs since (1AA, B) = 1.
C.5 CONSTANT BASELINE
C.5.1 POSITIVE CASES
AMI and SMI. Both of these indices satisfy the constant baseline by construction since the expected mutual information is subtracted from the actual mutual information in the numerator.
Adjusted Rand, Correlation Coefficient and Soeal&Sneath. These indices all satisfy ACB while being PaB-linear for fixed PA. PB- Therefore, the expected value equals the asymptotic constant.
C.5.2 NEGATIVE CASES
For all the following indices, will analyse the following counter Let [V| n, ka kB = n - 1. For each index, we will compute the expected value and show that it not constant. All of these indices satisfy the maximal agreement property and maximal agreement is achieved with probability 1/N (the probability that the single intra-pair of A coincides with the single intra-pair of B). Furthermore, each case where the intra-pairs do coincide will result in the same contingency variables and hence the same value of the index. We will refer to this value as c, (f). Therefore, the expected value will only have be taken over two values and will be given by
N
[iA B)] N Cmax +
N Cn (I).
For each of these indices we will conclude that this is non-constant function n so that the index does not satisfy the constant baseline property.
Jaccard and Dice. For both these indices we have Cmax = 1 and (f) = (as N11 = whenever the intra-pairs do not coincide). Hence, E[T(A, B)] N. which is not constant.
Rand and Wallace. As both functions are linear in Nu for fixed ma = Nn + Nuo. mg = N11 No1. compute the expected value by simply substituting Nı mAmp//V /N This will result in expected values 1 2/N + 2/N² and I/N for Rand and Wallace respectively, which are both non-constant.
20

---

Under review as a conference paper at ICLR 2021
Correlation distance.
Here Cmax 0 and
0 1/N2
C, Cx(CD)
arccos
(N 1)/N2
so that the expected value will be given by
-
(AC B)] = NT
arecos
N
This is non-constant (it evaluates 0.44, 0.47 for 3, 4 respectively). Note that this expected value converges to 2 for n + oc, which is indeed the asymptotic baseline of the index.
FNMI and NML. Note that in this case A kg that the penalty term of FNMI will equal and FNMI will coincide with NMI. Again Cmax 1. For the case where the intra-pait do not coincide, the joint entropy will equal H (A, B) In(n) while each of the marginal entropies will equal
n In(n) +
2 In(n/2) = In(n) 2 In(2).
=(A)=H(I)
=
n n
n
This results in
c. (NI (A) H(A
2ln(n)
((A)
nln(n) 2 (2))
and the expected value will be given by the non-constant
E[NMI(A, = - 2 ln))
N n nnn(n) ln())
Note that as (AA) H (B), all normalizations of MI will be equal so that this counter-example proves that none of the variants of (F)NMI satisfy the constant baseline property.
Variation of Information. In this case Cmax = 0. We will use the entropies from the NMI- computations conclude that
N
N 14
E[VI(A, = N (2H(A,B) H(A) H(B)) = N In(2),
which is again non-constant.
F-measure. Here Craxx = 1. In the case where the intra-pairs do not coincide, all contingency that both recall and precision will equal 1 1/n so that
variables will be either (FMM = 1/n. This results in the following non-constant expected value
N 11 N n
E (F B)] =
Note that because recall equals precision in both cases, this counter-example also works for other averages than the harmonic average.
BCubed. Again Cmax = 1. In the other case, the recall and precision will again be equal. Because for BCubed, the contribution of cluster is given by 1 n. max(ng | the contributions of the one- and two-clusters will be given by +. 2n respectively. Hence, c, (BC) get the non-constant
n-2
3 and
2n
2n
E[BC(A, = N
N
2n
We note that again, this counter-example can be extended to non non-harmonic averages of the BCubed recall and precision.
21

---

We will show that Var(NN1) o(n*). To compute the variance, we first inspect the second moment. c V are in the same cluster Under review as a conference paper at ICLR 2021
D FUTHER ANALYSIS OF CONSTANT BASELINE PROPERTY
D.I ANALYSIS EXACT CONSTANT BASELINE PROPERTY
Let us show that the definition of the constant baseline applies not only uniform (within given sizes specification) distribution but also to all symmetric distributions over clusterings.
Definition 11. We say that a distribution over clusterings B is clement-symmetric if every two clusterings B and B' that have the same cluster-sizes, B returns and B' with equal probabilities.
let A be a clustering with A and let B be an seoment-symmetrcc distribution. Then E B-BB (A, B)]
Lemma 3. Let 1 be an index with a constant baseline as defined in Definition 7
Chase
Proof. We write
EB-B(T(A, B)]
Σ PBBB(S(BB) = E)-(( (A, s]
Σ PBBB((S(B) EB~C(a) (AA, B)]
PP BBBB(S(B)) =) Cnuse Chase
where the sum ranges over cluster-sizes of elements.
D.2 ANALYSIS OF ASYMPTOTIC CONSTANT BASELINE PROPERTY
Definition 12.
An index I is said to be scale-invariant, if it can be expressed as a continuous functionn of the three variables Pa == mA /N, pn == mn/N and pAr == NuINN
All indices in Table scale-invariant. For such indices, we will write / (PP (PA PA.PB. Note that when B ~ C(s) for some s, the values PA. Pg are constants while PAB is a random variable. Therefore, further write PAB stress that this is random variable.
Theorem 2. Let be
pair-countiin index, and consider sequence of clusterings A and cluster-size specifications s(n). Let N7(w)) Niln) N((R) N(l) be the corresponding pair- counts. Then, for any as + 00,
11 10
P(4 (Nin) N An N - (N(T) [ N Nvin) >E) 0.
Proof. We prove the equivalent statement
f(P) (p(n) (/
P PE I(P)
(n)
(n) 50.
We first prove that p(n) (n) (a)
PA PAPB 5 so that the above follows from the continuous mapping
theorem. Chebychev's inequality gives
P
(IP.M)
PA PB
(n) (a)
Var (N(m)) -
The last step follows from the fact that Var(N = o(n as we will prove the remainder of this section. Even though in the definition, A is fixed while B is randomly permuted, it is convenient to equivalently consider both clusterings are randomly permuted for this proof.
Let A(S) denote the indicator function of the event that all elements in A. Define (SS) similarly and let AB(S) B(S) Let e, 61, e2 range over subsets of V of
22

---

Under review as a conference paper at ICLR 2021
size 2. We write
N =
Σ
AB(e)
AB(e))AB(e2)
Σ AB(e))AB(e2) +
Σ + + E AB(ei)AB(e2)
12
leinez|=1
1
=Nn+ +
Σ Ae())
Σ AB(c))
lei
e
We take the expectation
12 E[Ni E[Ni]] + E[AB((U) U2, 0g4ii +
(5
2
B[AB(c))AB(c2))
2
where v U2, vg E V distinct and e1 N e2 0. The first terms obviously onn²). We inspect the last term
n 2
B[AB(e))A((e)))
2
2
(3)
P(e C CANB)) x (n-2) B[AB(e))les c CAn.B)))
Σ
=
2
Now rewrite 2 to
E|N11 =
11
ΣE
n2 EP(e P(e A,) (n) B[AB(e2)]
Note that (²) bounded by
E[AB(e2)] > > E[AB(e2) so that the difference between 3 and E[Nn] can be
- 2)
C Σ P(el C C.DB)) -
2
2
As (1))
(n-
O(n*), what remains to be proven is
E C B)))).. (E[AB(e2)ler C 4, n -[AB(e(((((]]]) = o(1)
1.
Note that is sufficient to prove that
E E[)B(ea)le A.n By] - o(1),
for all i, Note that E[AB(e2)] MAmB/N2 NN2, while
E E[AB(e2)]e A, n By] (ma
(2a; - 3)) (2bg 3))
(N - (2n -3))2
Hence, the difference will be given by
(MA- (2a; - (m (26, - 3))
MAMB
(N (2n- 3))2
N2
(m (2a, -3)) - -(bb - -3) (N (2n- - (2)) m)
Nº(N (2n (2n -3))2
N2 -(nn 3))²
N²((2a= 3)bb - 3) (2b. -3) - -mm(2a; - -3)) + mAMB (2N - 3) - (2n 3)
N2 (2n - 3))²
N2 -(2n 3))²
((2a: -2)( 3) m2bbb 3) -m (2a; 3))
MAMB (2N(2n - 3) (2n 3)²)
(N (2n - 3)
N2
(N (2n 10--) 3))
Onn3)
O
+ MAMB
(N -(2n - 3)
N2 N2 - (2n - 3))2
=0(1);
23

---

Under review as a conference paper at ICLR 2021
required.
D.3 STATISTICAL TESTS FOR CONSTANT BASELINE
In this section, we provide two statistical tests: one test to check whether an index / satisfies the constant baseline property and another to check whether has a selection bias towards certain cluster sizes.
Checking constant baseline. Given a reference clustering A and a number of cluster sizes specifi- cations $ 8k, we test the null hypothesis that
EB-C(+,) (T(A, B)]
is constant i 1,..., ,, k. We do so by using one-way Analysis Of Variance (ANOVA). For each cluster sizes specification, generate clusterings. Although ANOVA assumes the data to be normally distributed, it is known to be robust for sufficiently large groups (i.e., large r).
Checking selection bias. In (Romano al. 2014 is observed that some indices with constant baseline do have a selection bias; when we have a pool of random clusterings of various sizes and select the one that has the highest score w.r.t. reference clustering, there a bias of selecting certain cluster sizes. We test this bias in the following way: given reference clustering A and cluster sizes specifications $1,... Sg. we repeatedly generate B1 ~ C(s1), ... By ~ C(ss). The null-hypothesis will be that each of these clusterings B; has an equal chance of maximizing [(4, B:). We test this hypothesis by generating r pools and using the Chi- Chi-squared test.
We emphasize that these statistical tests cannot prove whether an index satisfies the property or has bias. Both will return a confidence level p with which the null hypothesis can be rejected. Furthermore, for an index to not have these biases, the null hypothesis should be true for all choices of A, s Sk. which is impossible to verify statistically.
The statistical tests have been implemented in Python and the code supplements the submission. We applied the tests to the indices of Tables and We chose n = 50, 100, 150, 1000 and r = 500. For the cluster sizes, for l clusters of which n - k * |n/k: clusters have size [n/ while the remainder have size [n/k]
define the balanced cluster sizes BS (n. k) to be the cluster-size specification
Then we choose (n) to be a clustering with sizes (S,n, [n.55] [] and consider candidates with sizes s(m) = Bn,, [ [), $2
(m) [S,,, In I), s5(h) BS(n, [n J). For each the statistical
test returns a p-vuuue. We use Fisher's ss method to combine these p-values into one single p-value and then reject the constant baseline if p 0.05. The obtained results agree with Tables and except
for Correlation Distance, which is so close to having a constant baseline that the tests are unable to
detect it.
D.4 ILLUSTRATING SIGNIFICANCE OF CONSTANT BASELINE
In this section, we conduct two experiments illustrating the biases of various indices. We perform two experiments that allow us to identify the direction of the bias in different situations. Our reference clustering corresponds to the expert-annotated clustering of the production experiment described in Section and Appendix F3 where n 924 items are grouped into A 431 clusters (305 of them consist of single element).
In the first experiment, we randomly cluster the items into i approximately equally sized clusters for various k. Figure shows the averages and 90% confidence bands for each index. It can be seen that some indices (e.g., NMI and Rand) have clear increasing baseline while others (e.g., Jaccard and VT) have a decreasing bascline. In contrast, all unbiased indices have constant baseline.
In Section 4.6 we argued that these biases could not described in terms the number clusters alone. Our second experiment illustrates that the bias also heavily depends on the sizes of the clusters. In this case, items are randomly clustered into 32 clusters, 31 of which are "small" clusters of size while one cluster has size 31 where is varied between and 28, We that the biases clearly visible. This shows that, even when fixing the number of clusters, biased indices may heavily distort experiment's outcome.
24

---

B/ Under review as a conference paper at ICLR 2021
Finally, recall that we have proven that the baseline of CD is only asymptotically constant. Figures and show that for practical purposes its baseline can be considered constant.
E ADDITIONAL RESULTS
E.1 PROOF OF THEOREM 1
Let B' be an A-consistent improvement of B. We define
B B' [B, B, B, E B, n *0}
and show that @ B' can obtained from B by a sequence of perfect splits, while B' can be obtained from B B' by sequence of perfect merges. Indeed, the assumption that B' does not introduce new disagreeing pairs guarantees that any Bj E B can be split into Byn Bi...., B3 Bi....,,y. without splitting over any intra-cluster pairs of A. Let us prove that B' can be obtained from B @ B' by perfect merges. Suppose there are two By, B E @ B' such that both are subsets of some Byy. Assume that this merge is not perfect, then there must be E By in different clusters of A. As u, B @ B' that v, w must in different clusters of B. Hence, v, w is an inter-cluster pair in both A and B, while it is an intra-cluster pair of B', contradicting the assumption that B' is an A-consistent improvement of B. This concludes the proof.
BV such that u, are in the same cluster of B', it follows from the definition of
E.2 CORRELATION DISTANCE IS A DISTANCE
Theorem. The Correlation Distance is indeed a distance.
Proof. A proof this is given in Van Dongen & Enright (012)) We give an alternative proof that allows for geometric interpretation. First we map each partition A to N-dimensional vector the unit sphere by
1
kA 1,
VN
i(A)= =
A-PAL
if KA < n,
| PAll
kf =
VN
where 1 is the N-dimensional all-one vector and Á is the binary vector representation of partition introduced in Section Straightforward computation gives I| Pall = / /Npa(1 -PA), and standard inner product
(Ā (A-PAl,E -PB1) N(PAB PAPB),
so that indeed
2A-AA1,B pB1) (pAn.PPA))
11-A11 PB1l
is a well-known fact that the inner product of vectors of unit length corresponds the cosine of their angle. Hence, taking the arccosine gives us the angle. The angle between unit vectors corresponds the distance along the unit sphere. As il an injection from the of partitions to points on the unit sphere, we may conclude that this index is indeed a distance on the set of partitions.
E.3 DEVIATION OF CD FROM CONSTANT BASELINE
Theorem. Given ground truth A with a number of clusters' < KA < n, a cluster-size specification and random partition B C(s), the expected difference between Correlation Distance and its baseline is given by
(2%)
(BB.ci))CC(AA, EB (CC(A, 2)
EB-C(,) CD(A,B)
2
22R (k!)2
2k +
25

---

Under review as a conference paper at ICLR 2021
077
0.7
0.0
0.5
0.5
0.4
0.3
03
0.2
0.3
6.1
3.1.0
5.5
6.5
2.015
5.-
09130
4.5
20325
4.5
10200
-2022
0.2
220075
Scueed
0.002
0.5
0.000
0.7
0.8
0.1
-0.02
0.5
0.0050
0.4
0.006
0.3
0.0125
0.344
0.0075
0.2
0.005
0.2
565
2.022
3,032
550025
0.553
2.022
6 50000
3.002
2. 449975
0.496
-3.003
4.6950
-20032
8.40323
360
202
400
160
200
302
530
200
320
503
F3 (n 924 and KA 431) is compared to random clusterings. Each clustering consists of l approximately equally-sized clusters, where varied between 2 and 512. For each k. 200 random clusterings are generated. For each index, we plot the average score, along with a 90% confidence band.
Figure 3: The reference clustering of Appendix
26

---

Under review as a conference paper at ICLR 2021
N11
PWM
0.55
0.4
3.30
9.25
0.135
3.20
0.100
0.015
2.20
0.050
3.55
0.025
AM
9.15
0.100
3.35
0.155
2,022
0.150
3.05
0.44
-1.22
0.340
bibbal
0.004
AB
3.066
6.8-
0.863
2.044
0.6
2.02
0.000
-.000
2000
1.0
0.024
5.8-
0.022
3.10
0.020
2.03
3.09
3.07
0.014
3.55
0.356
0.503
2505
0.033
0.591
0.00
2/22
0.409
010
3.35
0.456
Small dualit
Small dhaler
Small claccer
Figure 4: The reference clustering of Appendix F3 (n 924 and k, 431) is compared to random clusterings. Each clustering consists of 31 "small" clusters of size while the last cluster has size 924 31 s, where 5 is varied between 1 and 28. For each s, 200 random clusterings are generated. For each index, we plot the average score, along with 90% confidence band.
27

---

Under review as a conference paper at ICLR 2021
Proof. We take the Taylor expansion of the arccosine around CC(A, B) and get
(2k)
CC(A, B)ak+1
CD B) 2
(RA)
2k
k=
We take the expectation of both sides and note that the first moment of CC equals zero, so the starting index is k =
For B ~ C(s) and large n. the value CC B) will be concentrated around 0. This explains that in practice, the mean tends to be very close to the asymptotic baseline.
E.4 COMPARISON WITH LEI ET AL.. (2017
Lei et al. (2077) describe the following biases for cluster similarity indices: NCinc - the average value for a random guess increases monotonically with the Number of Clusters (NC) of the candidate; NCdec - the average value for random guess decreases monotonically with the number of clusters, and GTbias the reference partition. In particular, the authors conclude from numerical experiments that Jaccard suffers from NCdec and analytically prove that Rand suffers from GTbias, where the direction the bias depends on the quadratic entropy of the ground truth clustering. Here we argue that these biases are not well defined, suggest replacing them by well-defined analogs, and show how our analysis allows to easily test indices on these biases.
the direction of the monotonicity depends on the specific Ground Truth (GT), i.c., on
We argue that the quantity interest should not be the number of clusters, but the number of intra- cluster pairs of the candidate. Theorem 2 shows that the asymptotic value of the index depends the number of intra-cluster pairs both clusterings. The key insight that more clusters do not necessarily imply fewer intra-cluster pairs. For example, let denote cluster-sizes specification for 3 clusters each of size & > 2. Now let be the cluster-sizes specification for one cluster of size 2 and & clusters of size 1. Then, any B ~ C(s) will have 3 clusters and 3()) intra-cluster pairs while any B' C(s') will have L + 1 3 clusters and (20 3()) intra-cluster pairs. For any ground truth A with cluster-sizes we have E J(A, B)] < [[A B']] because of larger amount of intra-cluster pairs In contrast, et al. (217)) classifies Jaccard as an NCdee index, so that the expected value should increase. contradicting the definition of NCdec. The NPine and NPdec biases that are defined in Definition D Mre sound versions of these NCine and NCdec biases because they depend on the expected number of agreeing pairs. This allows analytically determine which bias given pair-counting index has.
F EXPERIMENT
F.1 SYNTHETIC EXPERIMENT
In this experiment, we construct several simple examples to illustrate the inconsistency among the indices. Recall that two indices I and 1g are inconsistent for triplet partitions (A, B1, B₂) (A, B1) > T (A, B2) but T2 (A, B1) T2(A,B2)
We take all indices from Tables 2 and and construct several triplets of partitions to distinguish them all. Let us note that the pairs Dice vs Jaccard and CC vs CD cannot be inconsistent since they are monotonically transformable to each other. Also, we do not compare with SMI since is much more computationally complex than all other indices. Thus, we end up with 13 indices and are looking for simple inconsistency examples.
The theoretical minimum of examples needed to find inconsistency for all pairs of 13 indices is 4. We were able to find such four examples, see Figure 5 In this figure, we show four inconsistency triplets. For each triplet, the shapes (triangle, square, etc.) denote the reference partition A. Left and right figures show candidate partitions B2 and By. In the caption, we specify which similarity indices favor this candidate partition over the other one.
is easy to see that for each pair of indices, there is a simple example where they disagree. For example, NMI and NMI max inconsistent for triplets 3. Also, know that Jaccard in general
28

---

Under review as a conference paper at ICLR 2021
(Ia) FNML, Rand, AdjRand, Jac- card, Dice, Wallace, FMeasure, BCubed
(lb) NMI, NMImass VI, AMI. S&S, CC, CD
(2a) NMI, NMLms, FNMI, Rand, FMcasure, BCubed
(2b) VI, AMI, AdiRand, Jaccard, Dice, Wallace, S&S, CC, CD
(3a) NM Rand, AdjRand, Jaccard, Dice, S&S, CC. CD, FMeasure
(3b) NMI, VI, FNMI, AMI, Wal- lace, BCubed
(4a) NMI, NM FNML, AMI, Rand, AdjRand, CC, CD
(4b) VI, Jaccard, Dice, Wallace, S&S, FMeasure, BCubed
Figure 5: Inconsistency of indices: each row corresponds to a triplct of partitions, shapes denote the reference partitions, the captions indicate which indices favor the corresponding candidate.
29

---

Under review as a conference paper at ICLR 2021
Table 6: Inconsistency of indices real-world clustering datasets, %
NMI
NM
FNMI
AR
S&S
CC
FMsss
BCub
17.3
9.2
13.4
35.2
31.7
32.0
NMlms
41.1
16.5
13.2
12.5
14.1
34.3
68
21.1
18.9
30.3
32.4
34.7
41.8
43.2
37.6
17.1
28.5
36 0
37.2
18.1
13.6
FNMI
23.3
24.0
19.0
29.9
57.0
26.7
23.8
27.5
26.7
AMI
21.1
17.3
33.3
61.3
15.1
13.6
35.0
34.4
21.1
35.8
AR
23.5
59.4
11.7
8.3
25.3
28.1
35.9
23
23.8
10.7
9.7
w
53.5
51.8
40.7
37.4
S&S
3.6
26.2
27.8
CC
27.0
28.8
FMeas
7.7
BCuh
favors larger clusters, while Rand and NMI often prefer smaller ones. Hence, they often disagree in this way (see the triplets 2 and 4).
F.2 EXPERIMENTS ON REAL DATASETS
In this section, we test whether the inconsistency affects conclusions obtained in experiments on real data.
For that, we used 16 real-world datasets (itHHb there and removed the ones with categorial features or without the explicit target class field defined. The values of the "target class" field were used as reference partition. We end up with the following real-world datasets: arrhythmia, balance-scale, ecoli, heart-statlog, letter, segment, vehicle, wdbc, wine, wisc, cpu, iono, iris, sonar, thy, zoo.
2020). We took all real-world datasets available
KMeans, Affini- tyPropagation, MeanShift, AgglomeraiiveClustenng DBSCAN, OPTICS, Birch, GaussianMixture. For AgglomerativeCllsteringg we used 4 different linkage types ('ward', 'average', "complete' 'single'). For GaussianMixture, used 4 different covariance types ('spherical', 'diag', 'tied', 'full'). For methods requiring the number of clusters as parameter (KMeans, Birch, AgglomerativeClus tering, Mixture) we took up 4 different values (less than 4 if some of them are equal): 2, ref-clusters, max (effeefllssserr/// 22,, min(items, 2-ref-clusters), where ref-clusters is the number of clusters in the reference partition and items the number of elements in the dataset. For MeanShift, we used the option cluster all = True. All other settings were default or taken from examples in sklearn manual.
On these datasets, we ran 8 well-known clustering algorithms (Scikit-learn, 2020):
For all datasets, we calculated all the partitions for all methods described above. We removed all partitions having only one cluster or which raised any calculation error. Then, we considered all possible triplets A, B1, B2, where A is reference partition and B1 and Bg are candidates obtained with two different algorithms. We have 8688 such triplets in total. For each triplet, we check whether the indices consistent. The inconsistency frequency is shown in Table 6 Note that Wallace is highly asymmetrical and does not satisfy most of the properties, so is not surprising that it is in general very inconsistent with others. However, the inconsistency rates significant even for widely used pairs of indices such as, e.g., Variation Information vs NMI (40.3%, which is an extremely high disagreement). Interestingly, the best agreeing indices are S&S and CC which satisfy most of our properties. This means that conclusions made with these indices are likely to be similar.
Actually, one can show that all indices are inconsistent using only one dataset. This holds for 11 of 16 datasets: heart-statlog, iris, segment, thy, arrhythmia, vehicle, zoo, ecoli, balance-scale, letter, wine. We do not present statisties for individual datasets since we found the aggregated Table to be more useful.
Finally, to illustrate the biases of indices, we compare two KMeans algorithms with k 2 and k 2-ref-clusters. The comparison is performed on 10 datasets (where both algorithms are successfully completed). The results are shown in Table 7 In this table, biases and inconsistency are clearly
The code supplements the submission.
30

---

Under review as a conference paper at ICLR 2021
Table 7: Algorithms preferred by different indices
NMI
NM
FNMI
AMI
AR J
S&S1
CC
PMcas
BCub
9
0
& = 2 ref
9
1
8
6 4 0
7
3
3
Table 8: Similarity of candidate partitions to the reference one. In bold are the inconsistently ranked pairs of partitions. Some indices are taken with "_" sign, so larger values correspond better agreement.
Aprod
A
Aa
NMI
0,9326
0.9479
0,9482
NMI
0.8928
0.9457
0.9298
FNMI
0.7551
0.9304
0.8722
AMI
0.6710
0.7815
0.7533
-0.6996
-0.5662
-0,5533
FMeasure
0.8675
0.8782
0.8852
BCubed
0.8302
0.8431
0.8543
R
0.9827
0.9915
0.9901
AR
0.4911
0.5999
0.6213
0,3320
0.4329
0.4556
W
0.8323
0.6287
0.8010
D
0.4985
0.6042
0.6260
S&S
0.7926
0.8004
0,8262
CC
0.5376
0.6004
0.6371
CD
-0.3193
-0.2950
-0,2802
seen. We see that NMI and NMImax almost always prefer the larger number of clusters. In contrast, Variation of Information and Rand usually prefer & = 2 (Rand prefers k = 2 in all cases).
F.3 PRODUCTION EXPERIMENT
To show that the choice of similarity index may have an effect on the final quality of production algorithm, we conducted an experiment within major news aggregator system. The system aggre- gates all news articles events and shows the list of most important events users. For grouping, clustering algorithm is used and the quality of this algorithm affects the user experience: merging different clusters may lead to not showing an important event, while too much splitting may cause the presence of duplicate events.
There an algorithm Aprod currently used production and two alternative algorithms Ai and A2- To decide which alternative is better for the system, need to compare them. For that, it is possible to either perform an online experiment or make an offline comparison, which is much cheaper and allows us compare more alternatives. For the offline comparison, we manually grouped IK news articles about volleyball, collected during period of three days, into events. Then, we compared the obtained reference partition with partitions Aprods A1, and Ag obtained by Aprod- A1, and Az, respectively (see Table(8). (8). According to most of the indices, A2 is closer to the reference partition than A,, and A₁ is closer than Aprod- However, according some indices, including the well-known NMImax. NMI, and Rand, A₁ better corresponds to the reference partition than Ay. As result, we see that in practical application different similarity indices may differently rank the algorithms.
To further see which algorithm better agrees with user preferences, we launched the following online experiment. During one week we compared Aprod and AA and during another - Aprod and A (it not technically possible to compare A1 and A₂ simultaneously). In the first experiment, Ai gave +0.75% clicks on events shown to users; in the second, A gave 2.77%, which clearly confirms that these algorithms have different effects user experience and A2 is better alternative than Ai. Most similarity indices having nice properties, including CC, CD, and S&S, are in agreement with user preferences. In contrast, AMI ranks Aj higher than Az. This can be explained by the fact that AMI gives more weight to small clusters compared to pair-counting indices, which can be undesirable for this partieular application, discuss in Section
31


Reviews:
[{"review_id": "q7Tk3VzWQw_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\n\nThis 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.\n\n\n\n*Positive points*\n\n-> Validation of clustering is still an open issue which deserves attention by researchers\n-> Authors show with synthetic and real examples that different validation measures may prefer different solutions\n-> The analysis of the properties is interesting\n->The paper is well written and easy to follow\n\n\n\n*Negative points/questions/suggestions*\n\n-> 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?\nEven 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.\n\n\n-> 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.\n\n-> 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.\n\n-> 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.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "lh-_ahisZ55", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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.\n\nThe 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.\nSeveral 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).\n\n===== \n\nPROS\n+ Well motivated problem and relevant to the ML community\n+ The authors conduct a live experiment verifying the importance of CSIs in real-world applications. \n+ The authors formulate a property that deals with a previously observed bias of CSIs toward clusterings with high-cardinality clusters.\n\nCONS\n- 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). \n\nGiven 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.\n\nThis 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.\n\nOne 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.\n\nOverall, 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.\n\n[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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JVLm1M9Uo0h", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \nThe 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. \n\nPros:\n- authors detect critical issues affecting many indices\n- not-so-popular indices are suggested as interesting and valid alternatives to more widespread approaches\n- analysis is mathematically sound and thorough\n\nCons:\n- 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.\n- 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.\n- 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "IqYyFmZA2d", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\nThis 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.\n\n\n##########################################################################\nReasons for score: \nMy 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. \n \n##########################################################################Pros: \n \n1. 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. \n2. 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. \n3. This paper can also serve as an excellent “survey paper” on the clustering algorithms and similarity indices.\n \n##########################################################################\nCons: \n \n1. 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.\n2. I am not sure whether this kind of answer can be provided without a thorough discussion section, which is currently very short. \n3. 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). \n \n##########################################################################\nQuestions during the rebuttal period: \n \nThe 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. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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