$p$-value Adjustment for Monotonous, Unbiased, and Fast Clustering Comparison
Authors: Kai Klede
Thomas Altstidl
Dario Zanca
Bjoern Eskofier
Venue: NeurIPS 2023 poster (2023)
Keywords: Clustering
(Other) Machine Learning Topics
TL;DR: We present a monotonous, unbiased, fast alternative to the Standardized Mutual information for clustering comparison and external validation.

Abstract: Popular metrics for clustering comparison, like the Adjusted Rand Index and the Adjusted Mutual Information, are type II biased. The Standardized Mutual Information removes this bias but suffers from counterintuitive non-monotonicity and poor computational efficiency. We introduce the $p$-value adjusted Rand Index ($\operatorname{PMI}_2$), the first cluster comparison method that is type II unbiased and provably monotonous. The $\operatorname{PMI}_2$ has fast approximations that outperform the Standardized Mutual information. We demonstrate its unbiased clustering selection, approximation quality, and runtime efficiency on synthetic benchmarks. In experiments on image and social network datasets, we show how the $\operatorname{PMI}_2$ can help practitioners choose better clustering and community detection algorithms.

p-value Adjustment for Monotonous, Unbiased, and Fast Clustering Comparison
Kai Klede
Thomas Altstid! Dario Zanea'
Björn Eskofier
Machine Learning and Data Analytics (MaD) Lab Friedrich-Alexande Universität Hllange--Nürnbery
Translational Digital Health Group Institute of Al for Health, Helmholtz Zentrum München
kkede thomas. r altstidl; dario. zanca; bjoern. eskofier)ffau.
Abstract
Popular metrics for clustering comparison, like the Adjusted Rand Index and the Adjusted Mutual Information, are type biased. The Standardized Mutual In- formation removes this bias but suffers from counterintuitive non-monotonicity and poor computational efficiency. We introduce the p-value adjusted Rand Index (PMI2), the first cluster comparison method that is type II unbiased and provably monotonous. The PMT2 has fast approximations that outperform the Standardized Mutual information. We demonstrate its unbiased clustering selection, approxima- tion quality, and runtime efficiency on synthetic benchmarks. experiments on image and social network datasets, show how the PMI2 can help practitioners choose better clustering and community detection algorithms.
Introduction
Clustering is fundamental to unsupervised learning, and practitioners can choose from many algo- rithms to partition dataset into homogeneous clusters. Therefore it is common to annotate parts of an otherwise unlabeled dataset and select the clustering algorithm that best reproduces the annotations the clustering comparison method, like the Mutual Information (MI) [25) or the Rand Index (RI) [39]. The importance of the comparison method further increases with the advent of deep learning methods for applications such as community detection, in which they serve as components of loss functions during network training (TO. 12 [33] Some
[I]. A good selection crucially depends
use cases admit multiple clustering solutions [23] [38, and clustering comparison can help identify
qualitatively different clustering solutions for a single dataset. Other applications of clustering comparison include categorical feature selection consensus clustering [7].
The MI and RI are biased towards clusterings with particular cluster size distributions 19 (type I bias). For example, the MI favors larger clusters for any reference clustering (24). The Adjusted Rand Index (ARI) [I]] and Adjusted Mutual Information (AMI) 25 achieve a constant baseline value by subtracting the expected value under random permutation of the cluster labels. However, they still exhibit bias when multiple clusterings are compared via a fixed ground truth (type bias) random clusterings with each other. This type scenario typically arises when selecting the best algorithm for a given task on a labeled subset of the data.
(2), opposed comparing
Romano et al. [30] showed via the Tsallis entropy, that the AMI and ARI special cases of general- ized information- -tteoorttttthoeiiiccco clustering comparison measures AMI, and proposed standardization to resolve both types of biases. However, the runtime for standardization generally exhibits substantial time complexity
O(N max(k kB)) 30), where N represents the number data points and kA and kg denote the respective number of clusters. This complexity is prohibitive for many applications 15 Gösgens et al. 9 found that the Standardized Mutual Information (SMI) does not
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

a; N increase monotonically as one clustering is adjusted to match a reference and therefore reject the SMI entirely.
This work presents the p-value of the MI, (denoted ,MT,) as a provably monotonous type II bias correction. We formally define type II bias and prove that the PMI, does not suffer from it. For the SMI.. there is only empirical evidence [29 301. We show that the PMI, is monotonous for q 2 2. This includes the p-value of the RI, but for the MI, the p-value is not monotonous. When normalized with the normal CDE, the SMI, approximates the PMI.. which we confirm via Monte Carlo simulation. We reduce the runtime of the SMI, from (( max(k kn)) to much more practical ((k)k)) by a reformulation of the variance term. We demonstrate the impact of type II unbiased algorithm selection for community detection on social network dataset and clustering on images of handwritten digits and human faces.
2 Generalized information theoretic clustering comparison measures
clustering of N data points a partition of the set {I,..., N} into disjoint subsets A {Ai...., AkA J. A, denotes the set of points in the i-th cluster of size a, == | and ką is the number of clusters in A. Clustering comparison measures quantify the similarity between two clusterings A and B, and can be expressed function of the contingency table (Table
Table Contingency table for clusterings A, B with A and kB clusters respectively. Lower case da and by denote the cluster size of the i-th and j-th clusters in A and B, while niy represents the size of their overlap. Clustering comparison measures can be expressed in terms of the elements this contingency table.
B
bj
bka
11kB
A
nig
Ok Tkka1
9. many well-known methods like the Variation of Information, Mirkin Index, or Rand Index belong to the family of generalized information -theorettcc clustering comparison measures [30 31.. When adjusted for chance, these measures reduce to the mutual information with Tsallis q-entropy [55, which will be the focus of this work.
While many clustering comparison methods exist in the literature 2
Definition 2.1 (Tsallis g-entropy). Let y E R.,, and A be a clustering. Then, the Tsallis q-entropy is
(A( = ag
Σ
logg
1=1
with the q-logarithm log, (v) (y'-9- 1)/(1 where z log, (I) for = O.
if F 1 and the natural logarithm for q 1,
The generalized mutual information is defined in analogy to the mutual information but with Tsallis q-entropy replacing the Shannon entropy.
Definition 2.2 (Generalized mutual information). Let A, B be two clusterings of the set (1...., N) and E R4, then the generalized mutual information is
(I, B) = H2 + H₃( H,(A, B). Here H HA B) denotes the joint q-entropy H2 n B, A, E AA B3 B)).
3 Adjustment for chance
The bare MI, has limited value as clustering comparison measure. When comparing two clusterings directly with one another, it is biased towards larger smaller clusters, depending the value of

---

q (type I bias) [9, 25]. But even after adjusting for type bias, there is another, more subtle bias when multiple clusterings are compared via a single ground truth (29] (Figure Tp. In Section 3.2 we
introduce the p-value as an adjustment to the latter type II bias.
3.1 Type I bias
It is well known throughout the literature that the MI, is biased towards smaller clusters in direct clustering comparisons [19 25 To make this precise, Gösgens et al. [9] defined family of clustering distributions for which the expected similarity to reference clustering should be constant:
Definition 3.1 (Eleeret-symmmerric distribution), A distribution over clusterings B is element- symmetric if every two clusterings B and B' with the same cluster sizes have the same probability.
An example of an element-syme symmetri distribution is the uniform distribution over all clusterings of N elements into i clusters. If the clustering is random, a comparison measure should not favor one particular & over another. it does, we call it type biased [
Definition 3.2 (Type unbiased). A clustering measure V is type I unbiased if there is constant such that for any clustering with 1 < kA < N and every element-symmetric distribution the expected value BB (A, B)] = c is constant.
In other words, type unbiased means that when comparing a fixed clustering A to all permutations of any clustering B, the average metric value is the same for all A. As the MI, has this type bias, is commonly adjusted by subtracting its expected value under random permutation, yielding a type I unbiased measure 33).
(A, B)- Eo MI, (A, or (B)) (4, + (B) Eo (A, (B))
(A
Sy denotes the symmetric group and 1 (A) + (B)) is an upper bound the MI, such that the
AMI, is normalized to = 0 for random clusterings and upper bounded by 1 (25) (3). Adjustments
with respect to other random models are possible [8] [8]. However, the random permutation model
remains the most popular and is the focus of this work. Due to the generalization using Tsallis
entropy, the AMI2 corresponds to the Adjusted Rand Index [1 30
3.2 Type II bias
However, in typical external validation scenario, a single absolute value of the AMI, is of little help. While it is easy to understand that an AMI, of zero means a clustering algorithm is no better than random and value of one means optimal agreement, the scale of the range in between is unclear. Therefore, the A.I,, values of multiple candidate solutions with a reference are typically compared against each other to find the best algorithm for a given dataset.
As a toy model for this scenario, we uniformly generate 5000 clusterings of N = 500 elements for each number of clusters kB {2, 6, 10, 14, 18, 22} [29]. We compare them fixed clustering A with A = 10 evenly sized clusters and plot the selection probabilities for the RI, MT, and AMT, for q E (1,2) (Figures 1, b. d and e). The bare MI and RI and their adjusted variants AMI, biased towards certain values of kB.
We generalize and formalize this observation by demanding clustering comparison measure to favor no element-symmetre distribution over another.
Definition 3.3 (Type II unbiased). Let V be a clustering comparison measure and B, B be element- symmetric clustering distributions. V is type II unbiased if
EB - 2
(4)
for any clustering A with kA N, where 0 denotes the Heaviside step function with 0(0) 1/2.
Intuitively, Type bias means that certain cluster sizes receive higher metric values. Type II bias, on the other hand, gives a higher relative rank to certain cluster sizes when multiple clusterings are compared with ground truth.
3

---

a)
b)
c)
MI
AMI
PMT
0.2
0.2
0.75
0.50
0.1
0.1
Selection probability
0.25
0.00
0.0
0.0
d)
e)
f)
RI
AMI2
PMIz
0.2
0.2
0.75
0.50
0.1
0.1
0.25
0.00
0.0
0.0
2
6
10
14
18
22
2
6
10
14
18
22
2
6
10
14
18
22
Selected number of clusters
Figure 1: We compare fixed reference clustering with Ka 10 even clusters, to random clusterings
with kg E {2, 6, 10, 14, 18, 22} clusters. The plot shows the selection probabilities of each k for the MI and RI and its adjusted (AMI,) and our p-value adjusted (PMIg) variants after 5000 repetitions. The RI, MI, and AMI, are type biased, while our PMI, selects each cluster size with equal probability.
Romano et al. 29 introduced standardization to correct for type bias MI, (A, B) Eosss (AI, (B))]
SM, B)
(5)
VIEOESy (A, Egesw [MI, (A, (B))²
They observed in numerical simulations that in the toy model above (Figure M. the SMI, selects each kB with approximately equal probability [30]
However, the MI, is not normally distributed under random permutation (Figure 2), and standardiza- tion is only an approximation the true p-value (Figure 2p). The p-value quantifies what percentage of all permutations the data would have led to higher mutual information, and we propose to use for clustering comparison.
Definition 3.4 (p-value adjusted, generalized mutual information). Let A, B be two partitions of the set (1,.... ......... NN. q R4. Assuming the random permutation model, the p-value adjusted, generalized mutual information is
PMI, =EEEEs (A, B) (o,
(6)
Note that as the marginal entropies are PMI, = EveSy (o B) (A, B))]. For q 1, this the p-value of the mu- tual information and the variation of information by definition. For & 1 the PMI, further simplifies to Egesy (0(n') - n for q > 1 and EErEsy [0(n n n²1,)] for < with n'y being the elements of the contingency table for (A), B. sense, the details of the generalized mutual information don't matter under p-value adjustment, except the exponent of the contingency matrix elements. In fact, the p-value of the Rand Index is equivalent to the PMI, by a very similar argument.
independent of the permutation,
In the experiment in Figure I we observe that the PMI, and PMI, select each kn with approximately equal probability.
Proposition 3.1. The PMI, is type I and type II unbiased.
We formally prove this result in Appendix

---

probability density
PMI2 - -D (SMM))
50
0.04
100
probability
2MI
(SMM12)
200
0.03
500
1000
0.02
0.2
0.3
0.4
MI2
M12
min 1 2M12]
Figure 2: The probability of obtaining particular MI₂ under random permutation for fixed clusterings A, B each of 100 elements. Our PMT, (blue bars in a)) takes the true distribution of the MT, into account, whereas the SMI, (shaded blue region in b)) based normal approximation. However, when normalized with the normal CDF 4, the SMI, is a good approximation of the PMI2 as shown in Figure Here, sampled 1000 pairs of clusterings uniformly at random for different numbers of elements N. We plot the absolute difference between Monte Carlo estimates of the PMIz and normalized SMI₂ values as a function of the two-sided p-value. The larger the dataset size N, the better ((SMI,) approximates the true PMIz.
continuous
Monotonicity
When one clustering is changed to resemble another more, any clustering similarity measure should increase. A major drawback of the SMI, (A, B) is its non-monotonous behavior as the number of pairs of elements that agree in A and B increases [9. We show that the PMT,, on the other hand, is monotonous for q
4.1 Definition of monotonicity
The atomic operations that add new pairs of agreeing elements in two clusterings are the perfect split and the perfect merge
Definition 4.1 (Perfect split). B' a perfect split of B with respect A it splits single cluster B1 B into B,, B3 E B' such that for all either A, n B1 C B' or A, n B1 C B2z
Definition 4.2 (Perfect merge). B' is perfect merge of B with respect to A if B' is obtained by merging two clusters B1, Bg with B1, B2 C A, for some i.
Gösgens et 9 require that any clustering similarity measure increases monotonically for any combination of perfect splits and perfect merges.
Definition 4.3 (A-consistent improvement). B' is A-consistent improvement of B iff there exists a series of perfect splits and perfect merges that change B into B'.
Definition 4.4 (Monotonicity). symmetric clustering comparison measure monotonous if for every A, with 1 < kA < and any A-consistent improvement B' of B, V B') > V(A,
We show that the PMI, is monotonous for 2, making it the first known clustering comparison measure to be both type II unbiased and monotonous. The case g = is particularly interesting as corresponds to the well-known Rand Index.
4.2 Proof of monotonicity for PMI, with 2 2
The proof can be broken down into monotonicity under perfect splits and perfect merges. We first show that the joint q-entropy increases under any split that is not perfect.
5

---

Lemma 4.1. Let A, B be clusterings with 1 < AA < n. and B' be obtained by splitting a cluster B, B into non-empty clusters By, B', Then (A, B¹) (A, B) + AHg with AH, and equality iff the split is perfect with respect to A.
This statement is a direct consequence of the subadditivity of the q-entropy 7 In particular hy p pd log, is strictly convex function with (0) = 0 and hence strictly superadditive, i.c. (P1 + P2) (P1) hy (p2) for any P1,P2 with equality iff p1 0 P2 0.
Proof of Lemma 4.1
We express AHl
AHg = Σ
M4j
logg
Tly N
Majn N
logg
Flesa N
log
Nija N
N
N
r
Σ
hy
Flig
hgg
11
ha
N
N
N
From Mij n, 2 and the strict superadditivity of hn follows AH, 0 with equality iff n = =0 n2 0, i.e. when the split is perfect.
Conversely, a perfect merge maximizes the difference joint entropy.
Lemma 4.2. Let A, B, B' and AH, be in Lemma 4.1 then for q 2 AH, is maximal iff B is perfect merge of B' with respect to A.
Proof of Lemma
4.2 When B is perfect merge of B' with respect to A, then
bj
6'
b3
6/
AHpertee hg
hg
hg
(8)
To show that Alperied
superadditive as function of bjj we take its second derivative
d²
perfect
60-2 - (b, )9-2 2 O for 2 2 and by 6/₁, > 0. No
db
For q 2, strictly convex and thus strictly superadditive, For q 2 and by the difference F7 bb, is negative and thus A Hppetiset is also strictly superadditive. Now consider such
that B is not perfect merge with respect to Á. Then least two Åiς- Aig have non-vanishing overlap Bsgj Riaj > 0 with By such that
A Hpertect
Σ
hig
Taij N
hg
1/1 N
.hg
Aijj
8/1
for q 2 2.
(10)
With the superadditivity of hy follows Hrperfett
H7 perfect
(Compare Eq.
7
Now that we know how the joint entropy behaves under perfect splits and perfect merges, we can put together the proof of the monotonicity of the PMI..
Theorem 4.3. Let A, B be clusterings with 1 < ka < n and B' an A-consistent improvement of B. Then (A, B') > PMI, (A, B) for 2
Proof of Theorem 4.3
suffices to show monotonicity for B' a perfect split or perfect merge since any A-consistent improvement of B can be obtained by sequence of perfect splits and perfect merges.
Case 1. B' is perfect split.
Since A is not singleton cluster, a permutation a exists such that B' is not a perfect split with respect to o (A) and with Lemma 4.1 it follows
(A B')
Eossy (oESsI0(H, ((A,) H,(A,
(1I)

---

a)
b)
K4 kg 10
N = 1000
10a
10
10
runtime [s]
runtime [s]
100
109
SMI,
((N3)
B
SMIz
O(1)
10 1
PMI2
O)log.)
10
((SMl2)
PMI,
10 10-2
10-2
O(a
10
3
10
102
10a
10a
10
10
10
number datapoints
approximation error a
Figure 3: Runtime of the Monte Carlo PMI, and the SMI, for random clusterings of a) N elements into A = kn 10 clusters and b) random clusterings with = 1000 and varying approximation error a. The SMI, calculation, as proposed in (29). is prohibitively expensive for medium-sizer datasets. Our exact reformulation the SMI, and the Monte Carlo PMT, maintain practical runtimes for high N. The (SMM2) is faster, while the Monte Carlo PMIş allows for higher accuracy.
However, D' is perfect split B with respect A and equality holds Lemma 4.1 PMI,(A, B3) > Eoess (o B) - H, B))] (MI, B).
(12)
Case 2. B' is perfect merge. Let b1, b2 E B denote the merged clusters that form b/ E B'. Using Lemma
4.2 we find
PMI,(A, B¹) = Eoesy
(O)H, B) (0 H, B) + AH AHAA) (A, B), (13)
there is least permutation for which the merge is not perfect.
Approximations and runtime
A limitation of the PMI, is its computational complexity. Its exact calculation is intractable even for small datasets, as it requires sum over all contingency tables with given marginals. To mitigate this limitation, propose two approximation schemes:
Standardized approximation (q = 2): We approximate the true, discrete distribution of MI, with continuous normal distribution that matches its first and second statistical moments (See Figure 2 and b). While this approximation is particularly fast for = 2, does not preserve the theoretical guarantees of the PMI,-
2. Monte Carlo approximation: Given two clusterings A and B. we sample contingency tables with the same cluster sizes. The fraction of tables with MI, lower than MI, (A, B) approximates the true p-value. In this approach, the theoretical guarantees hold up to tunable approximation error at the cost of higher runtime.
5.1 The standardized Rand Index
We approximate the PMI, with the SMI,, normalized with the normal CDF & (Figure 2 This can be seen truncated, second-order Gram Charlier series the PMI, and while this could be continued for higher statistical moments, it is difficult to find an exact error term [7]. A more cautious

---

normalization permits the lower bound (M 21-
L+MM BA,)))) for (A, 0,
but has little practical significance in the context of this work [30]. Therefore, evaluate the approximation quality experimentally
M on 1000 pairs of clusterings drawn uniformly from the set of all clusterings with N E (50, 100, 200, 500, 1000) using method described in [16]. We compare (SMM2)) = (1 erf (SMI2/ / /22))/2 with Monte Carlo estimate of the PM with approximation error 0.001 in Figure 2 The values are highly correlated ("Pearson = 0.9983 for N = 50), and the approximation improves with larger values of N (FPearson = 0.9995 for N 1000). So although ((MM),) itself is not monotonous, it closely matches the PMI1. which is monotonous for 2 2.
While ((SMI,) is simplification O(N max(ka, kn) for general q is far from practical [5, 30 In this work, we con- tribute a novel algorithm for the special case y = 2 that improves the computational complexity.
the PMI,. its computational complexity
Proposition 5.1. The computational complexity of SMI₂ Okkkk))
The proof is in Appendix C This special case q 2 is of particular interest because of the correspon- dence with the well-known Rand Index and the monotonicity of PMI2- Our improved algorithm for the SMI, allows comparisons of moderately sized clusterings N sz 10,000 that are computationally out of reach for, g.g., the SMT, (Figure
5.2 Monte Carlo approximation
The standardized approximation has two limitations:
It is computationally inefficient only for g / 2.
There is no guarantee that it preserves the desirable theoretical properties of the PMI2-
We address both of these limitations by introducing a Monte Carlo approximation at the cost of increased runtime. For two clusterings A, B, the method samples contingency tables uniformly from all tables with their respective cluster sizes ai,..... ,,, bi, ....... bbg (Compare Table using the algorithms proposed 4 26). The fraction samples with MI, lower than (I, B) is an unbiased estimator of the PMI,- The sampling procedure terminates when given approximation error a is reached. This way, the theoretical properties of the PMI, are preserved up to the tunable approximation eπror.
However, lower approximation errors require more samples: Proposition 5.2. The computational complexity of the Monte Ominn(N, k log N)/a²), with the desired approximation error a.
Carlo
PMT,
is
The proof is in Appendix [, and Figure 3 shows an experimental study of the runtime compared to the standardized approximation. The Monte Carlo approach is computationally more expensive, especially for larger datasets. Therefore, the standardized approach is for choice when g = 2 and moderate approximation quality is acceptable. The Monte Carlo method should be used if q j 2 or theoretical guarantees are required.
6 Algorithm selection on real-world datasets
6.1 k-means clustering on image datasets
As first example, we mimic the synthetic experiment in Figure I For several numbers of clusters k. we apply k-means clustering [2T] with 1000 different random seeds. We select the clustering with the highest RI, AML, and PM12, approximated by ((SMI2) and denote the corresponding number of clusters kselected- Figure 4 shows the selection probabilities of kssllcttdd when compared with ground truth with Krne clusters for handwritten digit dataset [6] and Figure 4p for dataset of human faces [27]. Naturally, all measures favor solutions where Ksstected > kine as a higher number of clusters increases the chances of k-means matching the reference decision boundaries. However, the RI and AM2, additionally suffer from type bias, leading to higher overestimation of Kyelected
'The experiments were executed on AMD Ryzen 9 5950X. The code for all experiments is available at https://github. com/mad lab- waaoaaaappmm.mmm experiments
8

---

a)
b)
C)
selection probability
Plcellected
I selecteed
0.6
R1
RI
Leiden
AMI2
AMI2
0.4
PMI2
PMI2
Label Prop-
0.2
Map Eq.
0.0
10
11
12
13
14
15
40
44
48
52
56
60
25
50
75
175
200
seleocted
Rselected
Rselected
Figure 4: We apply k-means clustering 21 with varying to a) the UCI handwritten digit dataset [6] and b) the Olivetti faces dataset (27] and select the solution with the highest similarity to the ground truth. We repeat this experiment 1000 times with different random seeds and plot the selection probability under the RI, AM and normal approximation of the PMT2. The PMT, selects candidates where kselected is closer to the true number clusters kirne on average (dashed lines) compared the RI and AT2. In c), select connected subset of kiue 30 communities from the email EU core dataset (20) and detect communities using five algorithms with 22 parameter configurations. The RI, AMI2, and PMI2 select the best solution, and we plot the selection probability for kiselened after 100 repetitions. The PMI, prefers the Leiden algorithm, which produces kselecred on the order of hime. The AMI2 gives higher probability for Louvain Map Equation, and the RI sometimes selects low-quality Label Propagation results.
(compare with Figure T. The difference between the AMI, and the PMT₂ is subtle, but this is expected. Type II bias correction is just one step forward in clustering comparison and does not turn existing assessments based on metrics like the AMI2 on its head. practice, much wider ranges of kystected arise from different clustering algorithms which could potentially amplify the effect. Two additional experiments with spectral clustering instead of k-means can found Appendix
Community detection social networks
In social networks, detecting communities ubiquitous and can help to detect fraud, deliver person- alized content, or target ads [13. As result, many community detection algorithms are known in However, community detection is inherently unsupervised, and is a priori unclear which algorithm with which parameters will perform best for given application. In practice, human experts often annotate subset of the dataset, and an unsupervised algorithm is selected via clustering comparison measure on that subset.
the literature 3 28
We simulate this procedure tutions, where each institution is a ground truth cluster (20). We select a connected subset with kyue 30 institutions and detect communities using Degree Ordered Label Propagation, Label Propagation. Leiden, Louvain, and Louvain Map Equation [32) with 22 parameter configurations (Appendix D). We then select the most similar algorithm to the ground truth using RI,, A.M. and PMI, ~ (SMI)) This process is repeated for 100 subsets per dataset, and the resulting probabili- ties are shown Figure Label propagation a fast but inaccurate method 28 and overestimates kine by almost an order of magnitude in our experiment. During algorithm selection, RI was the only metric to choose Label Propagation in some cases. The PMI, differs from the AMI, in that selected Leiden more frequently over the I Louvain Map Equation, both of which are improvements over the original Louvain method [4 34). However, Leiden comes closer the true number of clusters kins and in that sense, PML, led better choice of algorithm.
network of email conversations between European research insti-

---

Table 2: Comparison of the PMI1 to the clustering comparison metrics in the systematic review by Gösgens et (9] Examples for type biasedness can be found in Appendix A We consider metric computationally tractable if its asymptotic complexity is linear in the number of data points N but not necessarily in the numbers of clusters k,, kg. The rationale is that in many cases, the number of clusters is much lower than the number of data points and metrics like the AMII with ON max A, kn) are widely used in practice [27 29). The PMIz the first metric to be Type unbiased and monotonous and, while computationally demanding, has efficient approximations,
Sneathh
Corr. Coeff.
Rand Index
Fair NMI
FMeasure
Corr. Dist.
NML
BCubed
Jaceard
Wallace
AMI
Dice
AMI,
AMI,
SML,
SML.
OX X PMI
PMI
VI
Type II unbiased
Type unbiased
X
XX
X
XXX XxXX
S X x
Xx x
< x
<<x x x
xxx
x
x <Sx
x
<sx
<Sx S
<<x
x
<<*
x
<<x
<Sx
XxOS
<xx<
SSSS
Monotonicity
Comp. tractable
Conclusion and outlook
Table summarizes findings for the PMI, and compares its theoretical properties to 17 clustering comparison measures from the systematic review by Gösgens et al. 19. We introduce the first type II unbiased and monotonous cluster comparison method, the p-value adjusted Rand Index (PMI2). Existing methods that addressed type II bias, namely the Standardized Mutual Information (SMI) and the Standardized Rand Index (SMI2) not monotonous, meaning clusterings closer to the ground truth can score worse. In addition, the SMI, has high computational complexity, making it unsuitable in practice. For the SMT, we showed that efficient algorithm exists and we leverage this algorithm for an efficient approximation of the proposed PMT,. However, our analysis of the errors in this standardized approximation limited to experimental observations, leaving a theoretical analysis for future work. We devised a Monte Carlo approximation for the PMI2 with tunable approximation error, for when theoretical guarantees theoretical findings, synthetic experiments confirm that the presented PMI, selects different cluster sizes with equal probability and is not subject to type II bias. In practice, the PMI, chooses better clustering algorithms from set of candidates when ground truth reference is available. Thanks to its monotonicity and computational efficiency, the PMI, a practical candidate for evaluating cluster similarity without type II bias. While we investigated p-value adjustment for the family of generalized information- -hhooretiic clustering comparison measures, further research required to understand other comparison measures, like the Jaccard Index, could benefit from similar adjustment.
required. To validate our
Acknowledgments and Disclosure of Funding
This work funded by the Digital Europe Grant Testing and Experimentation Facility for Health Al and Robotics (TEF- Health), Project number 101 100700 and the Bayerischen Verbundförderprograame (BayVFP)- Förderlinie Digitalisierung Förderbereich Informations- und Kommunikationstechnik of the Bavarian Ministry of Economic Affairs, Regional Development and Energy and supported by Bayern Innovativ Bayerische Gesellschaft für Innovation und Wissenstransser mbHl.
References
[I] C. C. Aggarwal and C. K. Reddy, editors. Data Clustering: Algorithms and Applications. CRC Press, 2014. ISBN 778-1-4665-5821-
[2] N. Arinik, V. Labatut, and R. Figueiredo. Characterizing and comparing external measures for the assessment of cluster analysis and community detection. IEEE Access, 9:20255-20276 2021. doi: 10. 10.1100 N0.110/ACCESS.222..000
10

---

[3] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10): 2008.
[4] J. M. Boyett. Algorithm AS 144: Random R x C tables with given row and column totals. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(3):329-332, 1979. ISSN 00359254, 14679876.
[5] C. Carpineto and G. Romano. Consensus clustering based on a new probabilistic rand index with application to subtopic retrieval. IEEE Trans. Pattern Anal. Mach. Intell., (4(12):2315-2326 2012. doi: 10. 109/TPAMM.2012.000
[6] D. Dua and Graff. UCI machine learning repository, 2019.
[7] S. Furuichi. Information theoretical properties of Tsallis entropies. Journal of Mathematical Physics, 47(2):023302, Feb. 2006. ISSN 0022-2488. doi: 10. 1061//121165744..
[8] A. J. Gates and Y.-Y. Ahn. The impact of random models on clustering similarity. Journal of Machine Learning Research, 18:87:1-87:28, 2017.
[9] M. Gösgens, A. Tikhonov, and L. Prokhorenkova. Systematic analysis of cluster similarity indices: How to validate validation measures. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021. Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1799-38000 PMLR, 2021.
[10] D. He, L. Zhai, Z. Li, D. Jin, L. Yang, Y. Huang, and P. S. Yu. Adversarial mutual information learning for network embedding. In Bessiere, editor, Proceedings of the Twenty-Ninth Inter- national Joint Conference Artificial Intelligence, IJCAI 2020, pages 3321-3327. ijeai.org, 2020. doi: 00.24963/iccai.220/4555
[11] L. Hubert and Arabie. Comparing partitions. Journal of Classification, 2(1):193-218, Dec. 1985. ISSN 4332-1343. doi: 10. 10.70//F00009000
[12] D. Jin, Z. Yu, P. Jiao, S. Pan, D. He. J. Wu, P. S. Yu, and W. Zhang. A survey of community detection approaches: From statistical modeling deep learning. IEEE Trans. Knowl. Data Eng..
2023. doi: 10.1 11111009TKD..20 3014155
[13] A. Karataş and S. Şahin. Application areas community detection: A review. In 2018 Inter- national Congress Big Data, Deep Learning and Fighting Cyber Terrorism CetrorismmBBIDDEE. (IBIGDELFT), pages 65-70, 2018. doi: 10. D0.110//// 8.8625349.
[14] Y. Kim and H. Jeong. Map equation for link communities. Physical Review E, 84(2):026110, 2011.
[15] K. Klede, I.. Schwinn, D. Zanca, and B. M. Eskofier. Fastami monte carlo approach to the adjustment for chance in clustering comparison metries. B. Williams, Chen, and J. Neville, editors, Shhret-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty- Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium Educational Adyances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 8317-8324, AAAI Press, 2023. doi: a3.. 26003.
[16] D. Knuth. The complexity of nonuniform random number generation. Algorithms and Com- plexity, New Directions and Results, pages 357-428, 1976.
[17] A. Lancichinetti and S. Fortunato. Consensus clustering in complex networks. Scientific Reports, 2(1):336, Mar. 2012. ISSN 2045-2322. doi: 10. 00.103//sep00336.
[18] D. Lazarenko and T. Bonald, Pairwise adjusted mutual information. CoRR, abs/2103.126411 2021.
[19] Y. Lei, J. C. Bezdek, S. Romano, X. V. Nguyen, J. Chan, and J. Bailey. Ground truth bias in external cluster validity indices. Pattern Recognition, 65:58-70. 2017, doi: 10. 10166/j-patcoe 2016.12.003.

---

[20] J. Leekovee, J. M. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1):2, 2007. doi: 10.1145//217299:111733.
[21] J. MacQueen. Classification and analysis of multivariate observations. In 5th Berkeley Symp. Math. Statist. Probability, pages 281-297. University of California Los Angeles LA USA, 1967.
[22] T. Mansour, M. Schork, and M. Shattuck. The generalized Stirling and Bell numbers revisited. J. Integer Seq. 15(8):47, 2012.
[23] E. Müller, S. Günnemann, I. Färber, and Seidl. Discovering multiple clustering solutions: Grouping objects in different views of the data. In G. I. Webb, B. Liu, C. Zhang, D. Gunopulos, and X. Wu, editors, ICDM 2010, the 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010, page 1220. IEEE Computer Society, 2010. doi: 10.110//CMM.2000..5
[24] X. V. Nguyen, J. Epps, and J. Bailey. Information theoretic measures for clusterings comparison: Is correction for chance necessary? In A. P. Danyluk, L. Bottou, and M. L. Littman, editors, Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pages 1073-1080. ACM, 2009. doi: 10. 1 1453/553334.15555511
[25] X. V. Nguyen, J. Epps, and J. Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11:2837-2854, 2010.
[26] W. M. Patefield. Algorithm AS 159: An efficient method of generating random R x C tables with given row and column totals. Journal of the Royal Statistical Society. Series C (Applied Statistics), 30( 1):91-97, 1981. ISSN 00359254, 14679876.
[27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[28] U. N. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3):036106, 2007.
[29] S. Romano, J. Bailey, X. V. Nguyen, and K. Verspoor. Standardized mutual information for clustering comparisons: One step further in adjustment for chance. In Proceedings of the 31th International Conference on Machine Learning. ICML 2014, Beijing. China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 1143-1151, 2014.
[30] S. Romano, X. V. Nguyen. J. Bailey, and K. Verspoor. Adjusting for chance clustering compari- son measures. Journal of Machine Learning Research, 17: 17:133:1-134:3 2016.
[31] D. A. Simovici. On generalized entropy and entropic metrics. J. Multiple Valued Log. Soft Comput., 13(4-6)2295-320 2007.
[32] C. L. Staudt, A. Sazonovs, and H. Meyerhenke. NetworKit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508-530, 2016. doi: ww..0017/ws.2006.22
[33] X. Su, S. Xue, F. Liu, J. Wu, J. Yang, C. Zhou, W. Hu, C. Paris, S. Nepal, D. Jin, Q. Z. Sheng, and P. S. Yu. A comprehensive survey community detection with deep learning. CoRR, abs/2105. 12584, 2021.
[34] V. A. Traag, L. Waltman, and N. J. Van Eck. From Louvain to Leiden: Guaranteeing well- connected communities. Scientific reports, (11)52333, 2019.
[35] C. Tsallis. Possible generalization of Boltzmann-Gibbe statistics. Journal of Statistical Physics, (2(1):4794487 July 1988. ISSN 1572-9613. doi: 10.00///01011
[36] Vanschoren, N. van Rijn, B. Bischl, and L. Torgo. Openml: networked science machine learning. SIGKDD Explorations, 15(2):49-60) 60, 2013, doi:
12

---

[37] D. L. Wallace. Asymptotic Approximations to Distributions. The Annals of Mathematical Statistics, 29(3):635-654, Sept. 1958. ISSN 0003-4851, 2168-8990 doi: 10.12 1//2o///s////////
1177706528.
[38] S. Wei, G. Han, R. Wang. Y. Yang, H. Zhang, and S. Li. Inductive multi-view multiple clusterings. In 2021 7th International Conference on Big Data and Information Analytics (BigDIA), pages 308-315, 2021. doi: 10.1 (tB.:/DDDDAS1111122099110110
[39] William M. Rand. Objective criteria for the evaluation of clustering methods. Journal of
the American Statistical Association, 666336) 1971. doi: 10. 00.100000122149911911 10482356.
13

---

Appendix
A Type II Bias
We show that the PMI, is both type and type unbiased:
Proof of Proposition
The choice of ((0) allows us use 0(x) 0(-x) such that
(A, =
ES (A, (A),
Ex (A) - -) Hg B))]
(14)
EEE (0(H) B) (A)), B))),
with B = (B) and ē = = Now in the definition of type I unbiasedness, B is element- symmetric, such that B B and
BB PMT, (A, (A, B)) PMM (A,
(15)
Hence, PMI, is type unbiased.
For type Il unbiasedness, B, are element symmetric and with Eq. 14
we get
EBaB.B'BB (PPM), B) (ML, B')) =
BBBB ((PMT, B²) PM B))
(16)
1 E BBB (PPMI PMI, B"))] 2
For other clustering comparison measures in Table 2 the proof or a counterexample to type I unbiasedness are given in [9. Here, provide an example for their type II bias. For N data points, we compare the clustering A = {{1, 4), (2, () with all clusterings with 2 clusters, distributed uniformly B. We also compare A to all clusterings from the uniform distribution B' of N = 4 data points into clusters. All comparison measures except the PMI, prefer either 2 or 3 clusters in the sense that their expectation value in Eq. is equal 1/2, and are thus type biased (See Table
Table 3: Example for type bias other clustering comparison measures. For A ([1,4), ()
and B, B¹ the uniform distribution of all clusterings with 4 elements into 2, 3 clusters respectively, the expected value ER-B, [0(V (A, B) V(A, B\ + z and hence these measures are type II biased.
Sokal&Sneath
Corr. Coeff.
Rand Index
Fair NMI
FMeasure
Corr. Dist.
NMI max
BCubed
Jaccard
Wallace
NMI
Dice
AMI
AML
SMI,
SMLL
VI
25
21
21
21
21
21
21
21
21
3
21
21
42
42
B Monte Carlo PMI,
Proof of proposition 5.2 Random contingency tables with fixed marginals can be generated in
Ommin(N N, KA log N)) 4 26). The error = /PMI((1 - P/I,)/ Saaples decreases with the inverse square root of the number Monte Carlo samples Naaplees Hence we need Nsamples S a 2/4 samples to reach the approximation error
14

---

C
The standardized Rand Index
For the proof of the runtime complexity of the SMI2, we use the fact that it is equivalent the SR1 (Corollary 2 in 33)
Rii - E Σij bj
Eis 183
RI
E
RI [T]
SRI
SMI2.
(17)
Var
Eig (m)))
Eig (1))
Proof of Proposition 5.1 tion
Hubert and Arabie
[1 derived the expected value under random permuta-
(2)
E
Σ Af
(18)
For the variance, also need the second moment. While Romano al. 30 give general formula in Eq. (13), it impractical in the given form as the authors themselves note the runtime complexity is O(N9KA max(ka, k-))- We observe that in the special case of the SRI, the higher moments can be simplified by leveraging the identity (39
min(NN2m) Σ
m
(2 1) 2
(a, ()) - pp) (19)
E
maj Hyp(a, by N)
II
N
with the generalized Stirling Number (2 k) [2 and the hypergeometric distribution Hyp. Note that the right-hand side is completely independent of Maj- Hence the expected values under the hypergeometric distributions in Eq. (13) in [30 can be calculated in O(max (ka, kB}) time, giving
2
Σ
n4j 2
=
2%
(N (N - 1))(b) - 1)b,
/=1
A
kB
+
a (a; - 1)
(4N 56, + 3)(6 - 2) 1)b;
/=1
RA
hg
+
a (a: - 1)
>
(by 3)(b, 2) 1)6,
1=1
j=1
kg
(20)
+ (12 %a,2)
by(b; 1)(b, 2) 3)
j=1
+ +17
16,2)
ag(a; 1)(a: 2)( 3)
i=1
+ (12 - 20. - 7,,2)
(N(N 1) 2)(N 3))'
for the most general case N 2 and no cluster larger than N 2, with
N a: 1) Ja. a2 1)2
N
NN Σ 1=1
Ya
= Σ
bb - 1)
76.2
03
1)2.
(21)
The other cases can be treated analogously using Eq. runtime complexity of the SRT is the RI itself with (kAAB)) for the sum over all contingency matrix elements.
19 Hence the dominant factor for the
D
15

---

D Community detection parameter configurations
For the experiment in Figure c. compared five community detection algorithms implemented in networkit [32). Label Propagation and Degree Ordered Label Propagation do not have any parameters. The parameter choices for the other algorithms listed Table
Table 4: Parameter configurations for the experiment the email EU core dataset. For Leiden, used all combinations of ry and randomize.
Algorithm
Parameters
Louvain
E [0.001, 0.01, 0.0, hierarchical (True, False)
Louvain Map Equation Leiden
E (1 10-6, 1.1 x 10-6, 0.0001, 0.001,0.001,0001,0000 randomize E (True, False}
E
Spectral clustering on image datasets
We conducted two additional experiments similar to the ones in Section 6.1 but using spectral clustering instead of k-means. We apply spectral clustering with varying number of clusters k to the UCI image segmentation dataset [6] and texture classification dataset from OpenML [36]. We compare each clustering solution with the ground truth labels and select the clustering with the highest RI, AMI2 and PMI2. Figure shows kseleated after 1000 trials with different random seeds. In the case of the image segmentation dataset, different subsets 1000 samples were chosen for each trial, due to the steep runtime requirements of spectral clustering. The results align with the k-means experiment in Section 6.1;; The PMI, selects clusterings a less biased way, the sense that the selected number of clusters kselected is closer to the true number of clusters kine than for RI and AMI2.
selection frequency
each number of clusters
b)
Rellectdd]
P(kuelected)
0.6
RI
RI
0.3
AMI2
AMI2
PMT2
PMT2
0.4
ktrue
0.2
0.2
0.1
0.0
0.0
4
6
7 8
9
10
10
11
12
13
14
15
16
kiselccted
Rgelected
Figure 5: We apply spectral clustering a) the UCI image segmentation dataset and b) texture classification dataset. The number of clusters parameter is set to eleven values between kime/ /
and 3/ime/ /2. We compare the resulting clusterings with the ground truth via RI, AML,, and PMT, and select the best clustering kselected according to each metric. We repeat the experiment with 1000 different random seeds and plot the selection probabilities of kislected for each metric. The PMT, selects candidates where the number of clusters is closer to the true number of clusters kine on average (dashed lines) compared to the RI and AM12.
16


Reviews:
[{"review_id": "ZiYzQGImng", "reviewer": "Reviewer_x3cb", "summary": "The paper proposes an improved clustering comparison metric. While many current metrics fix a \"type I\" bias (being biased towards certain cluster size distributions), many still suffer from a \"type II\" bias (a bias towards certain clusterings when they are compared to a ground truth clustering). Building on top of the Adjusted Rand Index, the type II bias is analyzed and a fast  and a p-value adjusted variant is introduced which is type II unbiased. A previous approach also solves this issue (SMI), however, it suffers from being non-monotonous, while the proposed metric is monotonous, i.e. when modifying a clustering in such a way that it objectively becomes better, the metric reflects this. While the proposed PMI metric relies on Monte Carlo approximation and thus is fairly costly, the SMI_2 metric is fast to compute and with a small modification seems to be a good approximation to the PMI_2. Results on three different datasets show that the best selected clusterings according to the PMI metric seem more reasonable when compared to two baselines.", "questions": "Given that you only theoretically prove that PMI_2 is type II unbiased, but you then in practice approximate it with SMI_2, is there some guarantee that this property still holds?", "limitations": "Limitations or potential negative impact have not been discussed in the paper. I would not be able to come up with a direct negative societal impact myself, but a discussion of potential limitations of the approach (if any are clear) would have been valuable.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is fairly easy to follow and seems to be well written. Even though I am not an expert in this field, I appreciate that the paper guided me through the most important considerations and different steps to get to the proposed metric.\n- Monotonicity is a reasonable aspect to consider from a clustering comparison metric, as also highlighted by Gösgens et al. [9]. Properly defining this concept and showing that the proposed PMI_q metric is monotonous for q>=2 is a valuable contribution.\n- The fast approximation of PMI_2 makes the proposed metric more practically applicable.\n- Code is provided.", "weaknesses": "My main concern is the overall practical significance of the proposed metric. While SMI is not monotonous according to Gösgens et al. [9], there seems to be empirical evidence for SMI_q. A proper proof for PMI_q is very nice, but the real-world experiments are based on the SMI_2 based approximation of PMI_2. In my mind the obvious baseline to compare to, would be SMI_2, but this is omitted for some reason and I really wonder why. Even though PMI_2 seems to select the more reasonable clusterings in all experiments, the margin to AMI_2 is not very large in two of the three setups and I would not be surprised if it is even smaller for the SMI_2 score. Adding such a comparison would give a more complete picture of how the different metrics compare.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and constructive feedback. We have taken all comments into consideration and summarize our response as follows:\n\n1. **Concern about practical significance**\n\t\n\t- While technically the $\\\\operatorname{SMI}\\_2$ was introduced in [1], the authors only provide the runtime complexity $\\\\mathcal{O}(N^3 k\\_A \\\\max\\\\{k\\_A,k\\_B\\\\})$ of the $\\\\operatorname{SMI}\\_q$ for general $q$, which is intractable in many real situations. Therefore, to the best of our knowledge, the $\\\\operatorname{SMI}\\_2$ has not seen any adoption in practice. We reformulate the $\\\\operatorname{SMI}\\_2$ and provide an implementation with a runtime of $\\\\mathcal{O}(k\\_A k\\_B)$, thus opening the $\\\\operatorname{SMI}\\_2$ for practical applications. Further, we normalize the $\\\\operatorname{SMI}\\_q$ in such a way, that it is closely related to the $\\\\operatorname{PMI}\\_q$. The latter is monotonous for $q=2$ but not $q=1$, providing further arguments for practitioners to chose the $\\\\operatorname{SMI}\\_2$ over the $\\\\operatorname{SMI}\\_1$.  \n\n\t- Ultimately, the nice theoretical guarantees only hold for the $\\\\operatorname{PMI}\\_2$ and not the $\\\\operatorname{SMI}\\_2$. Therefore we also introduce an unbiased Monte Carlo estimator that retains these guarantees up to a tunable error bound at the cost of a higher runtime. Practitioners can chose our MC implementation if theoretical guarantees are required.  \n\n\t- The difference between $\\\\operatorname{AMI}\\_2$ and $\\\\operatorname{PMI}\\_2$ in Figure 4 is subtle, but this is to be expected. Type II bias correction is just one step forward in clustering comparison and does not turn existing assessments based on metrics like the $\\\\operatorname{AMI}\\_2$ on its head. We included this train of thought into the discussion in Section 6.\n\t\n---\n\n2. **Why we base our real-world experiments on $\\\\Phi(\\\\operatorname{SMI}\\_2)$**\n\t\n\tWhile the differences between the $\\\\operatorname{PMI}\\_2$ and the $\\\\operatorname{AMI}\\_2$ in Figure 4 are already subtle, the difference between the two approximation schemes would be virtually non-existent (as you suspected). We think that for many applications, the practical benefits of the $\\\\Phi(\\\\operatorname{SMI}\\_2)$ approximation outweigh the theoretical guarantees of a Monte Carlo approximation (See Section 5), which is why we chose it for the real-world experiments. As the $\\\\Phi(\\\\operatorname{SMI}\\_2)$ is just a normalized $\\\\operatorname{SMI}\\_2$, a comparison to the latter would not provide further insight. We reformulated the explanation in Section 5 and 6 to explain this choice better.\n\t\n---\n\n3. **Discussion about limitations**\n\t\n\tA limitation of the $\\\\operatorname{PMI}$ is its computational complexity. We provide an efficient standardized approximation to address this limitation. However, strictly speaking, the standardized approximation loses the theoretical guarantees of the $\\\\operatorname{PMI}$. We mitigate this limitation by also introducing a Monte Carlo approximation that retains the theoretical guarantees up to a tunable approximation error, at the cost of higher runtime. We explicitly added a discussion of these two limitations to the manuscript. (See also our comment to Reviewer i4ZB)\n\n[1] Romano, S., Vinh, N. X., Bailey, J., & Verspoor, K. (2016). Adjusting for chance clustering comparison measures. _The Journal of Machine Learning Research_, _17_(1), 4635-4666."}, {"review_id": "fBzggTBzDZ", "reviewer": "Reviewer_heZh", "summary": "The paper introduces a new method called the p-value adjusted Rand Index (PMI2) for comparing clustering and community detection algorithms. The paper highlights the limitations of existing metrics, such as the Rand Index and Adjusted Rand Index, which suffer from bias and non-monotonicity issues. The PMI2 method addresses these issues by providing a type II unbiased and provably monotonic metric that has fast approximations. The paper also provides experimental results on image and social network datasets to demonstrate the effectiveness of the PMI2 method. \n", "questions": "A more extensive comparison of the PMI2 method with other recently proposed clustering comparison metrics to demonstrate its superiority would help to further validate the effectiveness of the PMI2 method.\n\nA more detailed and intuitive explanation of the approximations used in the PMI2 method and how they affect its accuracy would help readers to better understand the method and its limitations.", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Originality: The paper introduces a new clustering comparison metric, the p-value adjusted Rand Index (PMI2), which addresses the limitations of existing metrics. The PMI2 method is the first to be type II unbiased and provably monotonic, and it has fast approximations.\n\nQuality: The paper provides a thorough analysis of the limitations of existing clustering comparison metrics and demonstrates the effectiveness of the PMI2 method through experiments on synthetic benchmarks, image, and social network datasets. The paper also provides theoretical proofs of the PMI2 method's properties.\n\nClarity: The paper is well-organized and clearly presents the motivation, background, methodology, and experimental results of the PMI2 method. The paper also provides detailed explanations of the theoretical proofs and the approximations used in the method.\n\nSignificance: The paper's contributions are significant as they provide a more reliable and accurate way to evaluate clustering and community detection algorithms. The PMI2 method's properties make it a valuable tool for practitioners to choose better algorithms for their datasets. The paper's theoretical proofs and experimental results also provide a deeper understanding of clustering comparison metrics and their limitations.", "weaknesses": "One potential weakness of the paper is that it does not compare the PMI2 method with other recently proposed clustering comparison metrics. While the paper provides a thorough analysis of the limitations of existing metrics, it would be valuable to compare the PMI2 method with other state-of-the-art methods to demonstrate its superiority. \n\nAnother weakness is that the paper does not provide a detailed explanation of the approximations used in the PMI2 method. While the paper mentions that the method has fast approximations, it would be helpful to provide more information on how these approximations work and how they affect the accuracy of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and constructive feedback. We have taken all comments into consideration and summarize our response as follows:\n\n1. **Further comparison to other methods**\n\t\n\tWe added a table comparing a total of 19 clustering comparison metrics (See attached PDF), mostly adapted from a systematic review of cluster comparison metrics [1]. We added a column for type II bias and the $\\\\operatorname{PMI}\\_q$ for $q\\\\in\\\\{1,2\\\\}$. For all metrics except the $\\\\operatorname{PMI}\\_q$, we provide examples that violate type II unbiasedness in the appendix.\n\t\n---\n\n2. **Details about approximations**\n\t\n\t**Standardized approximation (**$\\\\mathbf{q=2}$**):** Intuitively, we approximate the true (discrete) distribution of $\\\\operatorname{MI}\\_q$ with a (continuous) normal distribution (See Figures 2a and b). We added this intuition to Section 5.1. As per Reviewer i4ZB's comment, we remodeled Figure 2c, to highlight the effect on accuracy (See attached PDF).\n\n\t**Monte Carlo approximation:** Given two clusterings $A$ and $B$, we sample contingency matrices (c.f. Table 1) with their cluster sizes $\\\\{a\\_1, \\\\dots, a\\_{k\\_A}\\\\}, \\\\{b\\_1, \\\\dots, b\\_{k\\_B}\\\\}$ using [2,3]. The fraction of matrices with $MI\\_q$ lower than $MI\\_q(A,B)$ then approximates the true $p$-value. We added this explanation to Section 5.2.\n\n[1] Gösgens, M. M., Tikhonov, A., & Prokhorenkova, L. (2021, July). Systematic analysis of cluster similarity indices: How to validate validation measures. In _International Conference on Machine Learning_ (pp. 3799-3808). PMLR.  \n[2] Boyett, J. M. (1979). Algorithm as 144: Random r× c tables with given row and column totals. _Journal of the Royal Statistical Society. Series C (Applied Statistics)_, _28_(3), 329-332.  \n[3] Patefield, W. M. (1981). Algorithm AS 159: an efficient method of generating random R× C tables with given row and column totals. _Journal of the Royal Statistical Society. Series C (Applied Statistics)_, _30_(1), 91-97."}, {"review_id": "mAnS0kMoxt", "reviewer": "Reviewer_dKDt", "summary": "The paper presents a performance measurement method for cluster analysis. The method can avoid Type II bias that exists in previous approaches. A tractable approximation is given. The proposed method demonstrates advantages in both synthetic and real-world data sets.", "questions": "* It is better to elaborate the importance of Type II unbiasedness. Specifically, explaining Definition 3.3 in common words help readers understand the concepts and your contribution.\n\n* There could be a mistake in Proposition 5.2. In the current formula, a higher accuracy leads to lower complexity, while a zero accuracy gives infinity.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work consists of solid theoretical contributions and satisfactory empirical results. The finding is an important step forward in clustering research.", "weaknesses": "More empirical results would make the work more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and constructive feedback. We have taken all comments into consideration and summarize our response as follows:\n\n1. **Further explanation of Type II unbiasedness**\n    \n    Type I bias means that certain cluster sizes receive higher metric values. Type II bias gives higher relative rank to certain cluster sizes, when multiple clusterings are compared with a ground truth.  We included this explanation to help illustrate Definition 3.3.\n    \n---\n\n2. **Definition of accuracy**\n\t\n\tAn accuracy $a=0.1$ means the error on the quantity is below $0.1$, a lower value of $a=0.01$ is thus more accurate. We eliminate the confusion by renaming \"accuracy\" to \"approximation error\".\n\t\n  ---\n\n3. **More empirical results would make the work more convincing**\n\t\n\tWe added further experiments using spectral clustering on an image segmentation and texture classification dataset see comment to Reviewer wdxj and attached PDF. "}, {"review_id": "xrFvXLf8sD", "reviewer": "Reviewer_i4ZB", "summary": "The article introduces a new measurement called $\\text{PMI}_q$ for comparing clustering methods. The name \"p-value adjustment\" comes from $\\text{PMI}_1$, which represents the p-value of the mutual information's variation. This new metric has desirable properties, including type II unbiasedness and monotonicity. The paper claims that $\\text{PMI}_q, q\\ge 2$ is the first clustering comparison method to satisfy both of these properties.\n\nThe definition of $\\text{PMI}_q$ involves taking an expectation over all permutations in $S_N$, which can be computationally challenging. To address this challenge, the author proposes a Monte Carlo estimation method for $\\text{PMI}_2$ and applies it to empirical experiments.\n\nThe paper's contribution lies in proposing a new unbiased and provably monotonic method for addressing the existing bias problem in current clustering comparison metrics. The author provides detailed and sufficient proofs to support the proposed method.\n\nThe paper's limitations include its disorganized structure and lack of clarity in some sections. The article's figures and tables need improvement, and the author does not explicitly address any limitations or potential future research directions.", "questions": "1. Is $\\text{PMI}_q$ type I unbiased? \n\n2. Section 6 is unclear on how to calculate $k_{pred}$. Although $\\text{PMI}$ can compare two clusterings, it is unclear which clusterings are being compared in the experiments discussed in Section 6. As such, further clarification is needed to understand how $k_{pred}$ is computed in this section.", "limitations": "1. The paper does not explicitly address any limitations or potential avenues for future research.\n\n2. While the author asserts that $\\text{PMI}_2$ is the first clustering comparison method to satisfy both type II unbiasedness and monotonicity, it is challenging to evaluate the significance of this claim without further comparison.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper provides valuable ideas and techniques for improving cluster comparison, particularly a new unbiased and provably monotonic method for addressing the existing bias problem, which may be useful to practitioners and researchers in the field of cluster comparison.\n\n2.Detailed and sufficient proofs give relatively clear theoretical and technical support on new methods.", "weaknesses": "1. The article's structure is somewhat disorganized and can be challenging to read. To improve clarity, the authors could provide more examples and intuitive explanations for Definitions 3.1 to 3.4 and 4.1 to 4.4.\n\n2. It would be beneficial to compare the proposed clustering comparison metric with other commonly used metrics in the field. By doing so, the authors could inform readers about whether these metrics possess desirable properties such as type II unbiasedness and monotonicity.\n\n3. The figures and tables in the article need improvement, as some elements are unclear or difficult to read. For example, Figure 3a has too a large legend. \n\n4. The results in Figure 2(c) could be more effectively presented to allow for easier differentiation across different N values. The authors may want to explore alternative visual representations or labeling techniques to better convey this information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and constructive feedback. We have taken all comments into consideration and summarize our response as follows:\n\n1. **Is $\\\\operatorname{PMI}\\_q$ type I unbiased?**\n    \n    Yes. Type I unbiased means that when you compare a fixed clustering $A$ to all permutations of any clustering $B$, the average metric value is the same for all $A$. The $p$-value of the mutual information ($\\\\operatorname{PMI}\\_q$) tells you what percentage of all permutations of the data points would have led to higher mutual information. Now, if we average that percentage over all permutations we get a constant 50%. Formally we use Eq. (15) from Appendix A with with $A,B,\\\\tilde{B},\\\\mathcal{B}$ as in Appendix A to get $\\\\mathbb{E}\\_\\\\mathit{B\\\\sim\\\\mathcal{B}}[\\\\operatorname{PMI}\\_q(A,B)]=1-\\\\mathbb{E}\\_\\\\mathit{\\\\tilde{B}\\\\sim\\\\mathcal{B}}[\\\\operatorname{PMI}\\_q(A,\\\\tilde{B})]=1/2$. We added the proposition to the main body and a short proof to the appendix.\n    \n---\n\n2. **What is $k\\_\\\\text{pred}$ in Section 6/Figure 4?**\n\t\n\tGiven a dataset with $k\\_\\\\text{true}=10$ ground-truth clusters, we apply $k$-means clustering for different $k\\_\\\\text{pred}\\\\in \\\\{10, 11, 12, 13, 14, 15 \\\\}$. We compare the $k$-means results with the ground truth and get for example $\\\\operatorname{PMI}\\_2$ values of $[0.1, 0.3, 0.4, 0.2, 0.3, 0.1]$. In this case $k\\_\\\\text{pred}=12$ had the highest score of $0.4$ and is selected. We repeat this experiment multiple times with different initializations of $k$-means and plot how often each $k\\_\\\\text{pred}$ was selected in Figure 4a. To stress this selection step, we changed the axis labels to $k\\_\\\\text{selected}$. We rephrased the Figure caption and extended the explanation of the experimental setup with examples in the main text.\n\t\n---\n\n3. **The paper does not explicitly address limitations or future directions**\n\t\n\tA limitation of the $\\\\operatorname{PMI}$ is its computational complexity. We provide an efficient standardized approximation to address this limitation. However, strictly speaking, the standardized approximation loses the theoretical guarantees of the $\\\\operatorname{PMI}$. We mitigate this limitation by also introducing a Monte Carlo approximation that retains the theoretical guarantees up to a tunable approximation error at the cost of higher runtime. Whether a weaker formulation of monotonicity can be found that carries over to the standardized approximation is an exciting direction for future research. Another open question is whether other metrics like the Jaccard Index could benefit from $p$-value adjustment and how it affects their monotonicity.  \n\tWe changed the conclusion to state those limitations explicitly. We also added the discussion about future avenues of research.\n\n---\n\n4. **Further comparison to other methods**\n\t\n\tWe added a table comparing a total of 19 clustering comparison metrics. See comment to Reviewer heZh and PDF attached.\n\n---\n\n5. **Clarity and figures**\n\t\n\tWe added intuitions for Definition 3.3, 3.2 and 3.4 (See Reviewer comment dKDt and the intuition for the PMI and type I bias in 1. of this comment). For a better understanding of Definitions 4.1 and 4.2 we added a reference to Definition 4 and Theorem 2 in [1], to stay within the page limit. We adjusted the legend size in Figure 3a and reworked the caption of Figure 4 (See 2. this comment).  We changed the presentation of Figure 2c, see PDF.\n\n\n[1] Gösgens, M. M., Tikhonov, A., & Prokhorenkova, L. (2021, July). Systematic analysis of cluster similarity indices: How to validate validation measures. In _International Conference on Machine Learning_ (pp. 3799-3808). PMLR."}, {"review_id": "efscubgHYD", "reviewer": "Reviewer_wdxj", "summary": "p-value Adjustment. The p-value adjusted Rand Index is unbiased. The authors claim that its approximations outperform STD Mutual Information. \nFirst, generalized MI relies on the TSALLIS entropy (same family of RENYI). AMIq comes from subtracting the expectation under random permutations. PMIq is derived and it is monotonic for q>=2 where q=2 is the Rand Index. Monotonicity is due to the properties of the bypass TSALLIS entropy.", "questions": "How critical is the choice of the Tsallis entropy? What about the  Kozackenko-Leonenko/Kraskow et al.’s approach? In ML there is an intererest in Rényi entropies and KNN graphs. Can you say anything about the properties of the graph associated with the clustering table.", "limitations": "The paper is general but few baselines are explored. Should be nice to test with segmented images or outputs of spectral clustering where there is an implicit bias. In other words, in my opinion the paper needs to tackle more recent datasets used in deep learning and image analysis to approach this result to the NEURIPS community.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is a general tool for testing clustering algorithms. The properties of bypass entropies such as Tsallis are leveraged. \nComputational complexity is quadratic.", "weaknesses": "It is quite theoretical and general. Poor experiments. Seems more a statistical paper. Please, motivate the use of bypass entropy estimators. It is more than a matter of efficiency. Other formal properties are also key (e.g. monotonicity).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and constructive feedback. We have taken all comments into consideration and summarize our response as follows:\n\n1. **Experiments with segmented images or spectral clustering**\n\t\n\tWe conducted two additional experiments using spectral clustering, on an image segmentation dataset [5] and a texture classification dataset [6]. The results are presented in Figure 1 in the attached PDF and confirm the experiments in Figure 4 in the manuscript. As the theoretical aspects of the $\\\\operatorname{PMI}\\_2$ are the main focus of this work, we prioritize having the comparison to other clustering comparison metrics in the main body (See Reviewer heZh, PDF). The experiments on spectral clustering will be included in the appendix, due to the similarity with Figure 4 and the page limit.\n\t\n---\n\n2. **Choice of Tsallis entropy over Rényi entropy**\n    \n    The Tsallis and Rényi entropy are distinct mathematical concepts that both generalize the Shannon entropy.  The Tsallis entropy replaces the logarithm with a modified $q$-logarithm (See Definition 2.1). This $q$-logarithm creates a link between information-theoretic and pair-counting measures [1]. For example, the adjusted Tsallis mutual information for $q=2$ is identical to the adjusted Rand Index. The Rényi entropy retains the conventional logarithm, such that this link to pair counting measures is not possible.  We rephrased lines 29f. and 86f. to further emphasize this point and refer to [1] for an in-depth discussion. \n    \n---\n\n3. **Mutual information estimation (Kozachenko-Leonenko/Kraskow et al., nearest-neighbor graphs)**\n\t\n\tWe assume you are referring to approaches to estimate mutual information of two *continuous* random variables, given a finite number of samples [2,3]. In this work, we focus on evaluating clusterings that consist of a *finite* number of clusters. Hence the cluster assignment can be understood as *discrete* random variable. Therefore the approach in [2,3] and KNN graph approaches like [4] are not applicable.\n\t\n---\n\n4. **Properties of the graph associated with the clustering table**\n\t\n\tWe assume you refer to the contingency table of two clusterings $A$ and $B$ (Table 1). Note that the contingency table is not necessarily a square matrix, such that it can be seen as a block in the adjacency matrix of a bipartite graph at best. The nodes on one side of this bipartite graph would represent the clusters in clustering $A$ and on the other clusters in clustering $B$. Edges would represent intersections between the clusters with the edge weight equal to the size of the intersection. While this is an interesting perspective on contingency tables, it is unclear to us how this contributes to the main content of our work, the $\\\\operatorname{PMI}\\_2$. \n\n\n[1] Romano, S., Vinh, N. X., Bailey, J., & Verspoor, K. (2016). Adjusting for chance clustering comparison measures. _The Journal of Machine Learning Research_, _17_(1), 4635-4666.  \n[2] Kozachenko, L. F., & Leonenko, N. N. (1987). Sample estimate of the entropy of a random vector. _Problemy Peredachi Informatsii_, _23_(2), 9-16.  \n[3] Kraskov, A., Stögbauer, H., & Grassberger, P. (2004). Estimating mutual information. _Physical review E_, _69_(6), 066138.  \n[4] Pál, D., Póczos, B., & Szepesvári, C. (2010). Estimation of Rényi entropy and mutual information based on generalized nearest-neighbor graphs. _Advances in Neural Information Processing Systems_, _23_.  \n[5] Image Segmentation. (1990). UCI Machine Learning Repository. https://doi.org/10.24432/C5GP4N.  \n[6] Brodatz, P. (1966). Textures: A Photographic Album for Artists and Designers. *Dover Publications,Inc.*, New York."}]

Author rebuttal:
We sincerely appreciate all reviewers’ time and efforts in reviewing our paper. We thank you all for the insightful and constructive suggestions, which helped further polish our paper. We attached a PDF with three improvements to our paper that were stimulated by the reviewers' comments:

- We added a table comparing the proposed $\operatorname{PMI}_2$ to 18 other clustering comparison metrics from the literature.
- We conducted two more experiments using spectral clustering on an image segmentation and a texture classification dataset.
- We modified Figure 2c to differentiate different dataset sizes $N$ better visually.

We included numerous other clarifications, additions, and reformulations in the manuscript, which we summarize in the direct replies to the reviews.

Meta-review: This is a borderline paper, but during the reviewer discussion and based on my own reading, I find that there are several nice ideas that are already mature in the current version, and room for further improvement with the additional experiments and promised discussions. Please carefully incorporate the constructive comments of the reviewers in preparing the revised version of the manuscript.
Decision: Accept (poster)