Pairwise Adjusted Mutual Information
Authors: Denys Lazarenko
Thomas Bonald
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Clustering
Metrics
Information Theory.

Abstract: A well-known metric for quantifying the similarity between two clusterings is the adjusted mutual information. Compared to mutual information, a corrective term based on random permutations of the labels is introduced, preventing two clusterings being similar by chance. Unfortunately, this adjustment makes the metric computationally expensive. In this paper, we propose a novel adjustment based on pairwise label permutations instead of full label permutations. Specifically, we consider permutations where only two samples, selected uniformly at random, exchange their labels. We show that the corresponding adjusted metric, which can be expressed explicitly, behaves similarly to the standard adjusted mutual information for assessing the quality of a clustering, while having a much lower time complexity. Both metrics are compared in terms of quality and performance on experiments based on synthetic and real data.

29 permutations where only two samples, selected uniformly random, exchange their labels. We show that the corresponding adjusted metric, we refer to as pairwise adjusted mutual information, Pairwise Adjusted Mutual Information
Anonymous Author(s)
Affiliation Address
email
Abstract
A well-known metric for quantifying the similarity between two clusterings the adjusted mutual information. Compared to mutual information, corrective term based on random permutations of the labels is introduced, preventing two clusterings being similar by chance. Unfortunately, this adjustment makes the metric computationally expensive. In this paper, we propose a novel adjustment based pairwise label permutations instead of full label permutations. Specifically, we consider permutations where only two samples, selected uniformly at random, exchange their labels. We show that the corresponding adjusted metric, which can be expressed explicitly, behaves similarly to the standard adjusted mutual information for assessing the quality of clustering, while having much lower time complexity. Both metrics are compared in terms of quality and performance on experiments based synthetic and real data.
3
5
7
10
11
12
Introduction
13
14 A well-known metric for quantifying the similarity between two clusterings of the same data is
15 the adjusted mutual information (Nguyen et al., 2009; |inh er al., [010]. Compared to mutual
16 information, this metric is adjusted against chance, meaning that the similarity cannot be due to
17 randomness but only to the structure the dataset, appearing both clusterings. This the reason
18 why this metric is widely used in unsupervised learning, see (Zhang ef al.) 2013 Thirion el al. 2014 Taha and Hanbury 2015) Yang et al. 2016 Wang et al.) [017] for various applications.
19
20
The standard way of adjusting mutual information against chance is through random label permuta- tions of one of the clusterings (Vinh al. 2010). Unfortunately, this adjustment makes the metric computationally expensive. Specifically, the time complexity of the metric is in Of (mmax(( (k, 7))). where k. are the numbers of clusters in each clustering and n the number of samples [Romano er
21
22
23
24
al. 2014). As comparison, the time complexity of mutual information is equal to O(kl) given the contingency matrix of the clusterings, i.e., the matrix counting the number of samples in each pair of clusters, one per clustering. The additional computational effort required by adjustment is significant as the number of samples n. is typically much larger than the numbers of clusters k, l.
25
26
27
28 In this paper, we propose novel adjustment based on pairwise permutations. That is, we consider
30
31 efficient as adjusted mutual information for assessing the quality of clustering, with much
32 lower time complexity. In particular, the time complexity is the same as that of mutual information.
33 The gain in complexity is significant, as the computation time is now independent of the number of samples n, given the contingency matrix.
34
The rest of the paper organized follows. We first provide the definition and key properties of adjusted mutual information in the general setting of information theory. We then introduce mutual information with pairwise adjustement and explain why the exact same properties satisfied by
36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

38 this new notion of adjusted mutual information. The application of both notions of adjustment to 39 clustering, including the explicit expressions of the corresponding metries, is presented section I Experiments on both synthetic and real data are presented in section 5 Section 6 concludes the paper.
41 2 Adjusted mutual information
42 Let P be the uniform probability measure on {I..... n). for some positive integer n. Let X, Y
43 be random variables on the probability space (St P). Without any loss of generality, we assume that
44 X and Y are mapping from sets consisting of consecutive integers, starting from Denoting by
45 H the entropy, the mutual information between X and Y is defined by (Cover and Thomas, 1991 ::
Y(X = ((X) + H(Y) H(X,Y)
(1)
This is the information shared by X and Y, which is equal to 0 if X and Y are independent. A distance between X and Y can then be defined by:
d(X,Y) = H) (( = H + X(
46 This distance, known as the variation of information, is metric in the quotient space of random
47 variables under the equivalence relation X Y if and only if there is some bijection yp such that
48
X (Y) Meilä 2003
The adjusted mutual information between X and Y, corresponding 50 to the mutual information between X and Y adjusted against chance, defined by:
Ad Adjusted mutual information.
AT(X, = T(X,Y) - E(T(X,, Y.)):
(2)
51 where Yo is the random variable Y o a for any permutation of n.). and the expectation is
52 taken over all permutations a, chosen uniformly random.
53 Remark (Normalization). It is frequent to also normalize adjusted mutual information, so to
54 get a score between 0 and [Vinh et al. 2010; Romano et al. 2014). In this paper, we only focus on
55 the adjustment step. Note that normalization can be equally applied to both considered notions of
56
adjustment and thus be studied separately.
57 We have the equivalent definition:
AI(X,Y) E(H(X, - HX,,Y,,
2 (F(d(X Y.)) - ((X,)))
(3)
58 This equivalence follows from Proposition and the fact that the definition is symmetric in X and Y. All proofs are available in the supplementary material.
60 Proposition 1. We have for any random variables X and Y:
H(X) = E(H(X.)),
E(H(X,, E(H(X,, Y)), (()(XYY)) = E(I(X,,Y)),
61 In view of (3). we expect AT(X, Y) to be positive if X and Y share information, as X is expected to be closer to Y (for the distance d) than to Y, randomized version Y. There specific cases
83 where ( Y) O, as stated in Proposition 2 these cases will be interpreted in terms of clustering
64 in section
85 Proposition 2. We have AI(X, Y) = 0 whenever Y (or X, by symmetry) is constant or equal to
86 some permutation of ,I....,m.
Adjusted entropy.
Observing that HXX) = I(X, we define similarly the adjusted entropy of AH(X) = A(XX, X) = ((X)= - E(T(X,
X by:
By get:
( = E( x.)) H(X) ( (id(X,X,))
(4)
Since d is metric, this shows that the adjusted entropy of X is non-negative.

---

69
Proposition 3. We have ( = 0 if and only if X is constant or equal to some permutation of (n].
70
71 Proposition 3 characterizes random variables with zero adjusted entropy. Again, this result will be interpreted terms of clustering section
72
Pairwise adjustment
73
In this section, introduce pairwise adjusted mutual information. The definition is the same as 75 adjusted mutual information, except that the permutation a is now restricted to the set of pairwise permutations. Specifically,
consider permutations for which there exists i, E {I,.... n) 77 such that (ii) = j and a(j) i, whereas (t)) = for all t + i,j. We consider the set of such permutations where the samples j are drawn uniformly random in the set {1...., nn.. We 79 denote by dp such a random permutation. Observe that op is the identity with probability 1/n (the
80 probability that j).
We define the pairwise adjusted mutual information as: Pairwise adjusted mutual information.
((I(X, )),)).
81 This is exactly the same definition as the adjusted mutual information, except for the considered
82 permutations pp It can readily verified that the same properties apply, with the exact same proofs,
83 key property being that the random permutations dp and op -1 have the same distributions. In
84 particular, we have the analogue of B
Ap I Y) = E(H(X, - -(X,)),,
(5)
85
Moreover, (X) whenever X or Y is constant or equal some permutation of n2].
Pairwise adjusted entropy. We also define the pairwise adjusted entropy as:
Hx)( = A, = H(X) - B(I(X, Xo,)).
86
We have (X) 2 0, with equality and only is constant or equal to some permutation of {1. n..
4 Application to clustering
89 Let = (Ai...., As} and B =
= BI...... Bi} be two partitions of some finite set (I...., n2 into and clusters, respectively. Let 52 {1, ,1,..., n) and P be the uniform probability measure over Q. 91 Consider the random variables and defined on (S, P) by X- X = A, for all =, 1,...,, k and Y (j) B, for all 1....,I. L. Note that X (w) and Y (w) can be interpreted the labels and of sample w in clusterings A and B, for each w E r...........
88
94
|A;1 the size of cluster A, by bj |Byl the size of cluster Bj, and by 95 ny = A, n B the number of samples both in cluster A, and cluster By, for all = 1,..., & and j ...., The matrix (mg))sssk,,1s 155 is known the contingency matrix. Note that a, and by
We denote by
97 are the sums of row and column j of the contingency matrix, respectively.
Adjusted mutual information. A well-known metric for assessing the similarity s(A, B) between 99 clusterings A and is the adjusted mutual informatior i AT(X, between the corresponding random variables X and Y. In words, this is the common information shared by clusterings A and B not due to randomness.
101
By Proposition 2 we have (A, B) () whenever clustering A (or B, by symmetry) is trivial, that is. consists of single cluster of clusters (one per sample). This a key property, showing the interest of the adjustment.
102
103
104
Recall that don't normalize the metric, see Remark
3

---

105
It is known that Vinh et al.
2010
naj log
nij
s (A, =
(6)
miu(as.b))
agb, (n a.) b,)! nlcl(a nlc(aa= cb((b) c)!(n o; by c)! log
Σ
i=1 j= (a: (ba -b)
with the notation (-)+ max(-,00 0). The time complexity of this formula, which is dominated by the
107
second term, is in (mmax(k: 1)n) Romano et al. 2014 In particular, it linear in the number of samples n.
109
Interestingly, we can similarly assess the quantity of information ((A) contained in clustering A through the adjusted entropy (H( of the corresponding random variable X. This is the information contained in A due to randomness. We have ((A) 2 0 and, by Proposition 3
111
112
((A) = 0 if and only if clustering is trivial, that is, it consists of single cluster or of n clusters
113
(one per sample).
114
Since (AA = s(A, A), it follows from
r6 that:
K Σ
min(ar,ay)
a,la,1(n a;)1(n a,)! nlcl(a, c).(a, - c)l(n - a; aj + k3!
((1)
log
Σ
log
72
n
TJ=Le=(a, -o)
115
The time complexity of this formula, also dominated by the second term, is in O(k)). Again, this complexity is linear in the number of samples n.
116
117
Pairwise adjusted mutual information. The main contribution of the paper the following new measure of similarity sp (A, B) between clusterings A and B, based on the pairwise adjusted mutual information Ap TX, Y) between the corresponding random variables and Y. We have explicit
118
119
expression for this similarity:
121
Theorem 1. We have for any clusterings A, B:
(p(A,
k
Tay (n - a, by + niy))
[24j
log
T4j
log
Rij 1
112
i=1
(a: n4 n4j)(bb n4y)
May +
Maj
+ 2
log
log
n2
n1
122
The time complexity of this formula is in Ok!), like mutual information. It independent of the number of samples n. given the contingency matrix. Corollary shows that the time complexity reduces to (m)) where m is the number of non-zero entries of the contingency matrix, provided the latter is stored in sparse format.
123
124
125
Corollary 1. We have for any clusterings A, B:
Rn aj bj + n4j)
Thjj
R4j
8p (A. B) 2
log
log
n2
(a: - (b, niy))
nij
Uij
Maj
T4j
+2 2
log
log
+
log
n²
71
1 0
k
2
2
6 +
Σ
niy
1
log
1 n
n
j=1
5.jmyy30
Similarly, we can define the quantity of information (A) in clustering A through the pairwise
128 adjusted entropy (X) of the corresponding random variable X. Again, 9p (A) 2 O, with (A) if and only if clustering A is trivial.

---

log 130 Corollary 2. We have for any clustering A:
(p(A) an(n as)
04 72 n n
04
0;
1 n
log
log
n
n
131 Note that the time complexity of this formula in O(k). It only depends on the number clusters k. and not the number of samples
Experiments
133
134
In this section, we compare both notions of adjusted mutual information through experiments involving synthetic and real data. The experiments are run computer equipped with an AMD
135
136
Ryzen Threadripper 1950X 16-Core Processor and 32 GB of RAM, with Debian 10 OS. All codes and datasets used in the experiments are available in the supplementary material.
137
138
Synthetic data. We start with the simple case of = 100 samples with clusters of even sizes, consisting consecutive samples. Specifically, we consider the set of clusterings A(*), consisting of clusters of size (except possibly the last one), for 1,2,.... 100. In particular, both ( and A (100) are trivial clusterings while A consists of 20 clusters of size 5.
139
140
141
Figure gives the similarity between clusterings (10) and A with respect to in terms of adjusted mutual information, for both notions of adjustment, i.e., s(A(10), 1(*)) and (p((1))), A(*)). We observe very close behaviors, suggesting that both notions of adjustment tend to capture the same patterns in the clusterings. Note that the maximum similarity is attained for 10 in both cases, as expected. The similarity equal to 0 for s {1, 100} for both cases, in agreement with Proposition We also observe local peaks at
144
145
146
20, 30, 90, which can be interpreted by the fact that clustering A (10) is a refinement of clustering ( for these values of s; similarly, the local peak at may be interpreted by the fact that clustering (5) is a refinement of clustering (10), The Spearman correlation between both metrics over all values of equal 0.99.
148
149
Mutual informatin
Information
0.02
80
100
Cluster size
(a) Full adjustment
(b) Pairwise adjustment
Figure 1: Comparison of metrics on synthetic data (n 100).
150
We now consider random clusterings. Specifically, we assign samples to k clusters independently at random, according to some probability distribution = (pı....,) PP). which is itself drawn at random" Consider three such random clusterings A, B, C' (with the same parameters and k. but different probability distributions p). We would like to know whether A "closer" to or to C. In particular, are interested in testing whether both notions of adjusted mutual information give the same ordering in the sense that:
152
154
156
(s B) - ((A, (,,,
(p,A 2. 0.
Namely, U where U = (Ui,.... ......,,A, Uk) is vector of k i.i.d. random variables uniformly distributed over
00, I..
5

---

157 We compute the average precision score (fraction of triplets A, B, C' for which 7 is true) over 100 independent samples of A. B, C. for different values of and k. We repeat the experiment 100 times to get the mean and standard deviation. The results are given in Table [ We observe very high precision score, always higher than 93%, showing that both notions of adjusted mutual information tend to give the same ordering of these random clusterings.
158
180
7
k
Precision score
100
2
0.972 + 0.004
100
5
0.952 + 0.007
100
10
0.943 + 0.006
100
20
0.955 + 0.008
500
20
0.936 + 0.007
1000
20
0.933 + 0.006
1000
50
0.949 + 0.008
Table 1: Precision score (mean + standard deviation)
162
For the performance gain, we compare the computation times both versions of adjusted mutual information for the similarity between clusterings A and B, where A consists of 10 clusters of same size and B is a random clustering, drawn as in the previous experiment. Both versions of adjusted mutual information
164
165
coded in Python, with the standard version imported from scikit-learn) Figure 2 shows the computation time when the number of samples n grows from 102 to 10', The
186
187
performance gain brought by pairwise adjustement is significant. particular, the computation time
188
becomes independent of the number of samples.
Full adjustement
Painwise adjustement
30a
Computation time 14)
10-1
102
10P
10
10
10F
107
Number samples
Figure 2: Computation time with respect to (mean + standard deviation).
Real data. We first consider the 79 datasets of the benchmark suite Gagolewski 2020 to each dataset each of the following clustering algorithms:
We apply
170
k e-maans
Affinity propagation
Mean shift
174
Spectral clustering
175
Ward
176
Agglomerative clustering
177
DBSCAN
178
OPTICS
179
Birch
180
Gaussian Mixture
See https//gthhbbbommaaallewwddsdsnn benchmarks vl

---

We use the scikit-leart implementation of these algorithms, with the corresponding default param- eters" We get 10 clusterings per dataset. The quality of each clustering is assessed through the similarity with the available ground-truth labels, using adjusted mutual information with either full adjustment pairwise adjustment. We then compute the Spearman correlation of the corresponding similarities, a value of meaning the exact same ordering of the 10 clusterings with full adjustment and pairwise adjustment. The results are shown in Figure together with the speed-up in computation time due pairwise adjustment. In both cases, the 79 datasets are ordered by the number of samples, ranging from 105 to 105 600 [Gagolewski 2020].
182
184
186
188
20
0.8
Spaarman correation
30-
0.2
0.0
Dataset
Datisset
(a) Spearman correlation.
(b) Speed-up of pairwise adjustment.
Figure Comparison metrics on the Gagolewski benchmark.
189
We first observe that the correlation very high, suggesting again that both notions of adjusted mutual information tend to provide the same results. For 65 datasets among 79, the Spearman correlation is higher than 95%. As for the computation time, observe significant performance gain, by one order of magnitude for the largest datasets.
190
192
We have conducted the same experiments with OpenML Vanschoren et al. 2013 We selected all datasets with at least 1,000 but no more than 50,000 samples, at most 100 features (all numerical), no missing data and ground-truth truth labels forming clusters of at least 5 samples are shown in Figure for the resulting 34 datasets. Again, the datasets are ordered by the number of samples, here ranging from 1.188 to 45,918. The conclusions similar. In particular, the Spearman correlation is higher than 95% for 30 datasets among 34, and the performance gain exceeds 25 for the largest datasets.
194
average. The results
196
198
50
5poa corraation
30
0.8
0.4
20
0.2
0.0
10
20
25
30
35
Dataset
Dataset:
(a) Spearman correlation.
(b) Speed-up of pairwise adjustment.
Figure 4: Comparison of metrics on OpenML. datascts.
hnttp://ssciiit-eee learn.
DDmeenioon reduction is applied to the MNIST datasets, consisting 000 images size 28 each. sec supplementary material for details.
hbttss//www.ppenll.ogg

---

6
Conclusion
200
201
We have proposed another way of adjusting mutual information against chance, through pairwise label permutations. The novel metric, whose explicit expression is given in Theorem has a much lower complexity than the usual adjusted mutual information. Interestingly, both metrics can also be
202
203
used to assess the quantity of information contained in clustering, which the common property of being equal to if and only if the clustering is trivial, as stated in Proposition] 3 again, the pairwise adjusted entropy, given in Corollary 2 has much lower complexity. Experiments on synthetic and real data show that pairwise adjusted mutual information tends to provide the same results as the usual adjusted mutual information for comparing clusterings, while involving much less computations.
204
205
207
209
For future work, we plan to extend this idea to other similarity metries. While the practical interest is less obvious for the Adjusted Rand Index (Hubert and Arabie 1985], due to the fact that the
210
211
time complexity of this metric is already independent of the number of samples, would be worth
212
considering other versions of information theoretic measures, as those studied in [Romano et al.
213
2016).
214 References
Thomas M Cover and Joy A Thomas. Elements of Information Theory. Wiley, 1991.
216
Marek Gagolewski. Benchmark suite for clustering algorithms version 1, 2020.
217
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-218
218
1985.
219
Marina Meilä. Comparing clusterings by the variation of information. In Learning theory and kernel machines, pages 173-187. Springer, 2003.
220
221
Xuan Vinh Nguyen, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: is a correction for chance necessary? In ICMI, 2009.
222
223
Simone Romano, James Bailey, Vinh Nguyen, and Karin Verspoor. Standardized mutual information for clustering comparisons: one step further in adjustment for chance. International Conference on Machine Learning, pages 1 1143-1151, 2014.
224
Simone Romano, Nguyen Xuan Vinh, James Bailey, and Karin Verspoor. Adjusting for chance clustering comparison measures. The Journal of Machine Learning Reseurch, 17(1):4635-46) 2016.
227
Abdel Aziz Taha and Allan Hanbury. Metries for evaluating 3d medical image segmentation: analysis, selection, and tool. BMC medical imaging, 15(1):29, 2015.
230
231
Bertrand Thirion, Gaël Varoquaux, Elvis Dohmatob, and Jean- Jean-Bapiin Baptiste Poline. Which fmri clustering gives good brain parcellations? Frontiers in neuroscience, 8:167, 2014.
232
233
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. Openml: Networked science in machine learning. SIGKDD Explorations, 15(2):49-60, 2013.
234
235
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research, 11 11:2837-2854, 2010.
236
237
238
Bo Wang, Junjie Zhu, Emma Pierson, Daniele Ramazzotti, and Serafim Batzoglou. Visualization and analysis of single-cell ma-seq data by kernel-based similarity learning. Nature methods, 14(4):414 416, 2017.
239
240
Zhao Yang, René Algesheimer, and Claudio J Tessone. A comparative analysis of community detection algorithms on artificial networks. Scientific reports, 6:30750, 2016.
242
243
Jiajie Zhang, Paschalia Kapli, Pavlos Pavlidis, and Alexandros Stamatakis. A general species delimitation method with applications to phylogenetic placements. Bioinformatics, 29(22):2869
244
245
2876, 2013.
8

---

Checklist
248
247
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
240
contributions and scope? [Yes] A variant of adjusted mutual information.
250
(b) Did you describe the limitations of your work? [Yes] Pairwise adjustement only applied
251
to mutual information in the present work, see Section 6
252
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
253
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
255
2. If you are including theoretical results...
256
(a) Did you state the full set of assumptions of all theoretical results? [Yes] No specific assumption is required. Theorem 1, Corollary and 3 give explicit expressions using notations defined at the beginning of Section 4.
257
258
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplementary material.
260
261
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See the Jupyter notebooks in the supplementary material.
263
285
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A] This is a metric for unsupervised learning. No data split required, no hyperparameter.
286
267
288
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [Yes] See Table I and Figure 2 (not applicable to other experiments).
270
271
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See the running times provided in the Figures; the resources used are detailed at the beginning of section 5.
272
273
274
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
275
(a) If your work uses existing assets, did you cite the creators? [Yes] See the references for the datasets.
(b) Did you mention the license of the assets? [N/A]
278
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
279
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
281
282
(e) Did you discuss whether the data you are using/curating contains personally identifiable
283
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
285
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
286
287
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
290
9


Reviews:
[{"review_id": "tX4WAg21FLP", "reviewer": "Reviewer_bn5i", "summary": "This paper studies an adaptation of a well-known form of metric used to measure the similarity between two clusterings. The adjusted mutual information (AMI) rates the mutual information of two clusterings by using the expected mutual information obtained by randomly permuting the labels as the \"benchmark\". AMI has high computational cost (linear in the size of dataset). This work then proposes a new way of adjusting the mutual information that is much easier to compute and behaves similar to AMI in practice.", "questions": "", "limitations": "", "rating": 5, "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": "Originality: Most of the techniques (especially those used in the theoretical arguments) are old in this paper. The main novelty lies in the authors' observations that AMI is developed by considering the mutual information by using fully random permutations.\n\nQuality: The work has some interesting insights, but I'm not sure if this venue would be the best place for receiving it. The key insight that replacing full permutations with partial (pairwise here) permutations can lead to significant savings in computing time is cute and has values. It adds to our understanding of clustering metrics. However, the work done in this paper, both theoretically and empirically, does not fully justify the claim that it is the perfect substitute for AMI. Also, I'm not sure about how significant the improvement is in computing efficiency (see more detailed comments below). \n\nClarity: The paper is clearly written and explained the main discoveries well. However, I would have liked it more if the authors could elaborate a bit more on the (theoretical) connection between the new metric and original AMI, especially since there is much space left. Right now the main body only contains the proposed new metric and the derivation of the terms, which does not provide enough insights.\n\nSignificance: I'm not very confinced about the significance of the findings. The proposed metric design twiddles the original full permutation in a nice way. However, I have difficulty understanding whether there is any guarantee than connects this new metric to the original one, as taking the expectation based on pairwise permutations can be very different from full permutation. It is intriguing that they seem to have close performance in the numerical experiments. However, the methods used to measure the similarity between these two metrics are also limited (mostly precision score and correlation) and indirect. The claim is broad and the datasets already tested do not seem to be sufficient. \n\nI'm also concerned about the assumption that the contingency matrix is known. It seems to me that given any two clustering, the time spent on constructing the two clustering and computing the contingency matrix (all $n_{ij} = |A_i \\cup B_j|$'s) might be dominating, so even if computing the pairwise AMI is cheap, it might result in marginal gain in overall time complexity. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed limitations and societal impact as far as I'm concerned.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hrs"}, "extra_text": {}}, {"review_id": "fX8TtpjH5JT", "reviewer": "Reviewer_n7gR", "summary": "This paper proposes a new efficient measure, called the pairwise adjusted mutual information, to quantify the similarity between two partitions of a dataset. The proposed measure is a simplified version of well known adjusted mutual information and hence it is easy to compute. In particular, the time complexity is independent of the number of data points, while that of the standard fully adjusted mutual information is linear with respect to the number of data points. The proposal is empirically shown to be more efficient than the adjusted mutual information.", "questions": "", "limitations": "", "rating": 4, "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": "### Originality\n\nThe originality of this paper is just one idea: reducing the full adjustment of the mutual information into the pairwise adjustment. Although combining a pairwise permutation to the adjustment of mutual information seems to be a new idea, the technique of pairwise permutation itself is often used in the context of statistical testing (pairwise permutation test). Therefore, I feel that the overall originality is not high enough compared to the standard of NeurIPS.\n\n### Quality\n\nThe quality of this paper is not high as there is no theoretical analysis of the proposed approach. Hence the effectiveness of the pairwise adjustment is unfortunately not clear. Although its effectiveness is empirically evaluated, it is not convincing. In experiments in real-world datasets, the Spearman correlation is observed to compare the pairwise adjustment and the full adjustment, while this is not enough to empirically examine the effectiveness of the proposal. For example, it would be interesting to see the correlation between the proposal and other well known clustering measures such as adjusted Rand index and normalized mutual information.\n\n### Clarity\n\nThis paper is overall clearly written. However, there are many parts that describe already known results (e.g. \"adjusted mutual information\" part in Section 4) and the overall length of the paper is just over 7 pages (maximum is 9 pages), hence I believe that much more contents can be put in this paper to increase its quality.\n\n### Significance\n\nAlthough I understand that the proposed pairwise adjustment is much faster than the full adjustment, the full adjustment is still as fast as (or faster than) the clustering process itself as its complexity is linear to the number of data points. Together with the fact that the Spearman correlation can be small depending on datasets shown in Figure 3, in a practical situation, I think there is no positive reason to employ the proposed pairwise adjustment and one can simply use the full adjustment. Therefore the significance of this paper is not high.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although the authors argue that the limitation is described, it is vague and the limitation of the proposed approach is not properly discussed. For example, it is important to discuss when it fails in finding of better clustering and what is the negative impact of the proposal if such a situation occurs.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "CEI79Jb8ndi", "reviewer": "Reviewer_xPxc", "summary": "In this paper authors propose an efficient version of adjusted mutual information, termed pairwise adjusted mutual information, for cluster similarity evaluation. The topic is attractive and the results on both synthetic and real-world datasets demonstrate the effectiveness of the algorithm. However, the expression of the paper needs to be finely improved. Also, the depth of the theoretical analysis needs to be further improved. More analysis should be given.", "questions": "", "limitations": "", "rating": 5, "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": "There are grammar mistakes in the paper. It makes the paper relatively harder to understand. Here are some examples.\n\" Compared to mutual information, this metric is adjusted against chance, meaning that the similarity cannot be due to randomness but only to the structure of the dataset, appearing in both clusterings.\"\n\"As a comparison, the time complexity of mutual information is equal to O(kl) given the  contingency matrix of the clusterings, i.e., the matrix counting the number of samples in each pair of clusters, one per clustering.\"\n\"The gain in complexity is significant\", do you mean the complexity decrease is significant?\nTo name just a few. The paper should be carefully polished before publishing.\n\nThe theoretical analysis of the paper is not thorough enough.\nWhat is the theoretical relationship the adjusted mutual information and pairwise adjusted mutual information. What is the influence of introducing the restricted constraint? What is the gap between the two criteria? Similar conclusion of the proposed  pairwise adjusted mutual information is expected? How many pairwise permutations should be made to achieve good performance?\n\nTo the experimental part\nMore comprehensive experiments should be made to evaluate the stability of the proposed criterion.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please check the main review part.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "27MbBaCDZu_", "reviewer": "Reviewer_tfHx", "summary": "This paper provides a new adjustment for the normalized mutual information, based on pairwise permutations to make the computation more efficient.  It shows that the new index correlates well with the original index in different experiments, while providing significant speedup. \n", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Where do you get definition 2? Similarly, I am not able to verify proposition 1. Can you show how these are derived from the permutations?\n\nHow do you account for having fixed-sized clusters which is the assumption in the original AMI paper?\n\nThe contingency matrix computation is linear in n, so any computation on top that is also linear in n will not add to the overall complexity of measuring agreement between clusterings. The reason for AMI being expensive is that it is not linear in n, it is factorial!\n\nThe main issue with NMI is that it is sensitive to the number of clusters, that is random clusters with more clusters will get a better agreement with the ground truth. This is one of the key reasons for the need for an adjusted index. In most experiments, the number of clusters is fixed which doesn't allow for testing this. The sizes of the clusters are also an important factor in the adjustment for chance, which is overlooked by assuming even size clusters. Overall the experiments are limited and not convincing. The theory is not well explained. The related work is non-present.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper suggests a new method for comparing clusterings, namely pairwise adjusted mutual information, which is related to the previously defined “adjusted mutual information”, except that the averaging is done over permutations swapping only two elements.  This allows faster computation.

All reviewers seem to be more or less in favor of rejection.  While I do not agree with all reviewers comments (for example: I actually do think the paper is clearly written) I do agree that this paper offers a nice definition but with little significance in both theory and practice, especially in the context of a venue like NeurIPS.  One possible direction to strengthen this paper could be, for example, to give a theoretical explanation to the results of the synthetic experiments.

Decision: Reject