Statistical Guarantees for Consensus Clustering
Authors: Zhixin Zhou
Gautam Dudeja
Arash A Amini
Venue: ICLR 2023 poster (2023)
Keywords: consensus clustering
unsupervised label aggregation
spectral clustering
barycenter problem
Frechet mean
semidefinite relaxation

Abstract: Consider the problem of clustering $n$ objects. One can apply multiple algorithms to produce $N$ potentially different clustersings of the same objects, that is, partitions of the $n$ objects into $K$ groups. Even a single randomized algorithm can output different clusterings. This often happens when one samples from the posterior of a Bayesian model, or runs multiple MCMC chains from random initializations. A natural task is then to form a consensus among these different clusterings. The challenge in an unsupervised setting is that the optimal matching between clusters of different inputs is unknown. We model this problem as finding a barycenter (also known as Fr\'{e}chet mean) relative to the misclassification rate. We show that by lifting the problem to the space of association matrices, one can derive aggregation algorithms that circumvent the knowledge of the optimal matchings. We analyze the statistical performance of aggregation algorithms under a stochastic label perturbation model, and show that a $K$-means type algorithm followed by a local refinement step can achieve near optimal performance, with a rate that decays exponentially fast in $N$. Numerical experiments show the effectiveness of the proposed methods.

Published as a conference paper at ICLR 2023
STATISTICAL GUARANTEES FOR CONSENSUS CLUSTERING
Zhixin Zhou', Gautam Dudeja², Arash A. Amini?
1 City University of Hong Kong, University of California, Los Angeles
zh 00825ggma1llmm..mmmmm com,
aaami @ucla edu.
ABSTRACT
Consider the problem of clustering objects. One can apply multiple algorithms to produce potentially different clustersings the same objects, that is, partitions of the objects into K groups. Even single randomized algorithm can output different clusterings. This often happens when one samples from the posterior of a Bayesian model, or runs multiple MCMC chains from random initializations. A natural task is then to form a consensus among these different clusterings. The challenge in unsupervised setting is that the optimal matching between clusters different inputs is unknown. We model this problem as finding a barycenter (also known as Fréchet mean) relative to the misclassification rate. We show that by lifting the problem to the space of association matrices, one can derive aggregation algorithms that circumvent the knowledge of the optimal matchings. We analyze the statistical performance of aggregation algorithms under a stochastic label perturbation model, and show that a K-means type algorithm followed by a local refinement step can achieve near optimal performance, with a rate that decays exponentially fast in N. Numerical experiments show the effectiveness of the proposed methods.
INTRODUCTION
Clustering is fundamental task in machine learning and data analysis. Given data on each of the objects a set, there are numerous algorithms to produce clustering of these n objects, which formally partitioning of {1...., n into K disjoint sets. A natural problem that arises in practice how to form a consensus among these clusterings. This is especially important the different clusterings produced by single randomized algorithm. This situation often arises in Bayesian modeling, where the posterior naturally encodes the variability of the clustering problem. Finding a consensus clustering then corresponds finding the center of the posterior, from which we can also obtain estimates of the variability of the posterior.
clustering of objects assume that we are given N label vectors Z₁ E [K,] for j ,,...,,, N, with potentially different number of clusters each. Let K max, K, and note that The task is to obtain a consensus K K-cllustrrngg that is, a label vector E [K]" which is close to all the same time. We also refer to this task as the label aggregation problem.
be viewed
label vector in [K]" where [K] = (1,..., K}. We
can view all zÿ as vectors [K]
NN 21.....
In the context of clustering, there is no meaning to the label of each cluster, that is, the label aggregation problem unsupervised, in the sense that there is no natural correspondence between labels of different clusterings. This is in contrast to label aggregation in classification in which the labels have common meaning among different input classifications. We refer to the latter task as supervised label aggregation.
In the unsupervised setting, forming a consensus label is nontrivial task due the label-switching problem. Consider for example, the case = 5 and the two label vectors 2 = 1, 2) and 22 = (2, 2, 2, 1, 1). These two vectors are different in all 5 positions but they define the same clusterings of the objects. In this case, the consensus label 2 can be taken to be either 21 22. More generally, for every 2j, there could be permutation गł on [K]. such that the permuted vectors Ty 2 = (TT(22) y) closer to each other than the original Z,S.

---

Published as a conference paper at ICLR 2023
To formalize the above idea, recall the definition of the misclassification rate between two label vectors, 2, y E [K]":
Mis(z, y) min
1f2 + (Vy))}
where the minimum is taken over all the permutations и [K] - [ Mis(::)) :) is a proper metric on the space K -ellusterings of n objects. is also a metric on [K] if we identify vectors that are obtained from each other by label-switching, We can now define the consensus label the barycenter of 21, 21...., EN in Mis(.,.) metric, that is,
N
2 argmin =E[K]" j=1
Σ wy (2,)(2,2,)
where wy 2 0 are a given set of weights. We often assume uniform weights: wy = for all j. The barycenter 5 is also known the Frechét mean. Solving (2) is complicated by the presence of the permutation in the definition of Mis function. More explicitly, we need to solve
N ΣΣ wy mz(zi))
E argmin min a E [K] TI..EN
showing that in addition to z, we have to optimize over N permutations Ty. = I. N. In this paper, we provide alternative solutions that avoid optimizing over these permutations.
The unsupervised version of the label aggregation problem is the realistic and practical one when dealing with aggregating labels from Bayesian clustering algorithms, since the posterior has K! modes corresponding to all possible label permutations, and the output will be near an arbitrary mode in each run of the algorithm. The main contributions of this paper to unsupervised aggregation the following:
Our contributions
1. We show that by lifting the barycenter problem to the space of association matrices, one can derive algorithms that avoid optimizing over the unknown permutations (Section 2. In particular, we propose both basic and spectral K K-means type aggregation algorithm.
2. We propose a random perturbation model (RPM) under which we can study the theoretical performance of both supervised and unsupervised aggregation algorithms. We prove the statistical consistency of the basic aggregation algorithm under RPM (Section 2.2).
3. Under RPM, the supervised setting corresponds to an oracle that knows the true matching permutations. By studying this oracle, we derive the optimal statistical misclassification rate for supervised aggregation (Section 3.1).
4. We propose an efficient local refinement step on the output of any consistent aggregation algorithm in the unsupervised setting, and show that the updated labels achieve nearly the same misclassification rate as the above oracle (Section 3.2).
Our theoretical analysis illustrates how different parameters affect the difficulty of the label aggrega- tion problem. In Section 4, we provide numerical experiments comparing the performance of the proposed algorithms against each other and existing methods.
Related work In the supervised setting, the problem of label aggregation is to combine multiple annotated dataset. The label inferred for each item from those produced by multiple annotators acts as the ground truth for the classification task. Various probabilistic models have been proposed for aggregating annotations, with parameters to account for the expertise of the annotators and the noise in the labeling process (47; 37). The unsupervised setting is more challenging as there is no meaning to the cluster labels (the label-switching issue) and the clusterings can have potentially different number of clusters. The idea of passing to association matrices to get around the label-switching issue, has been leveraged in several existing approaches (13; 24; 43; 13; 21; 29), although the connection make to the lifted barycenter problem and the resulting spectral methods is to the best of our knowledge. In (24; 43), the authors employ an Expectation Mititttiioo-Miiizzattiii nonnegative matrix factorization of the combined association matrix. The authors of (41) provide
strategy to obtain a
2

---

Published as a conference paper at ICLR 2023
several approaches, using the hypergraph representation of the clusterings, that have shown promising results in the context of image segmentation (22). A set of fuzzy consensus algorithms is proposed in (40) that generate soft consensus partitions by combining a collection of fuzzy clusterings.
What we referred to as unsupervised label aggregation problem has appeared under many differ- names in the literature, including but not limited to, cluster ensembles (41), clustering/cluster ensemble problem (44; 10), ensemble clustering (1), clustering aggregation (17), combining cluster- ings (42; 14; 27), consensus clustering (48; 18) and the median partition problem (12; 46; 18). As can be surmised from the variety of names, there is a copious literature on the subject, spanning over multi- ple fields, with many ideas rediscovered time after time. We refer to the excellent surveys (48; 44; 18) for more exhaustive list of references and historical discussions. There is also parallel line of work in the Bayesian clustering literature on aggregating the posterior clusterings (31; 7: 9; 25; 15; 45; 8).
The barycentric view to aggregation that we take in (2) has appeared in many previous work, but often with a different distance in place of Mis, including but not limited to the symmetric difference distance (SDD), a.k.a. the Mirkin metric (up to constant), in the median partition problem (39; 23; 12; 17: 18), the Binder loss and variational information (VT) in (45; 15), the normalized mutual information (NMI) in the pioneering work of (41), the adjusted Rand index (15) and the category utility function (42: 35), After introducing our methods, in Section 2.3, we give a more detailed comparison with the literature. We choose Mis as the distance in the present work for a better comparison with the oracle problem in Section 3.1. We also show in Appendix B. that consistency in Mis implies the consistency in other distances.
Despite the voluminous literature on the subject, statistical analysis of the methods under a statistical model for the input clusterings has not been undertaken before. This is the gap that we fill in this paper, by providing the first consistency and optimality results under a statistical model (the RPM) for a method of clustering aggregation that we propose. To the best of our knowledge, the question of consistency, let alone optimality, has not been considered for any method of aggregation before. We also shed more light on the relation between the barycenteric approach and those based on association matrices (Section 2.3), and how convex relaxation leading to a spectral method can be used to approximate the median partition. To illustrate the importance of statistical analysis, we also show that a simple common approach to the median partition problem, known as the BestOfK (18), is in general inconsistent under RPM, despite being shown to be a 2-factor approximation of the median partition problem (12). This further highlights the key insights that statistical analysis under model can provide which is not possible to obtain by CS-type theory on approximation algorithms.
2 LIFTED AGGREGATION ALGORITHMS
We start by introducing some notation. Let &x = { be the set of standard basis vectors of R The elements of & can be considered one-hot encodings of the labels from [K]. From now on, instead of encoding labels as element of [K], we encode them element of &g. We can then view labelings of n objects as elements of the following set
EK {z =
zn) z; E EK Vi E [n]]-
(4)
Each 2; is viewed as K x vector and each element of EK as K x n matrices, which we refer to as label matrices. For E &x, permuting the cluster labels is equivalent to pre-multiplication by a K K permutation matrix P, that is, PZ.
The label aggregation problem can be restated as follows: Given label matrices Z AN E &
find a consensus label matrix Z E ER. by solving the barycenter problem:
N
2 E argmin ZEER
min
wil 2 - P,,
(5)
1=1
where Pı..... PN are K x K permutation matrices and |X := (E X2) is the Frobenius norm of matrix X. One can verify that problem (5) is equivalent to (3). The following result shows that if we know the optimal permutations P,s. we can easily find the barycenter Z:
Proposition 1. Let (Pr,... PNN y be an optimal set of permutation matrices in (5). Then, the optimal solution Z of (5) is the colummwise "argmax" of E, w. N,,P, PzZ.-
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 Basic label aggregation algorithm.
1: Form association matrices Xj = Zj Zz.
2: Form the average association matrix X 2j=1 WjXj.
N
3: Perform K-means on the rows of X.
Algorithm 2 Spectral label aggregation algorithm.
1: Define the same average association matrix X as in Algorithm
2: Perform K-trrnncated eigendecomposition of X UAU where A R contains top-K
eigenvalues on the diagonal and the columns of U E RB*X are the corresponding eigenvectors.
3: Perform K-means on the rows of U.
2.1 LIFTING TO ASSOCIATION MATRICES
The difficulty in the unsupervised setting is that the optimal permutations (P,) are unknown. To get around this issue, we lift the barycenter problem to the space of association matrices. For a label matrix Z Kg we define the corresponding association matrix that Xi- = iff i and j are in the same cluster according to Z, otherwise Xij = 0. The advantage of
X - Z E {0, 10,1] 1]"xx, Note
X is that it invariant to label switching: = 7d 7 = (PZ)² PZ for any permutation matrix P. This suggests solving the following lifted barycenter problem instead of (3):
X E argmin XeXx
Σ ==1
-
(6)
where X, =Z5 with at most clusters.
25 2j and Xx = ( 2: Z E EK that is, the set of (binary) association matrices
Semidefinite relaxation Problem (6) is still hard to solve due to the combinatorial nature of Xg- An approach to solving problems over XxK is to relax to a semidefinite program, an idea that has been applied before to community detection in networks (4). In particular, Xx is inside the doubly nonnegative cone (X X z 0, X 2 0}. where X 2 0 and X 2 0 mean is positive semidefinite and elementwise nonnegative. We note that Xa 1 for all i. This suggests relaxing the following problem
N X E argmin Σ
X 0, X20, Xa = 1vi
Problem (7) has a simple solution. The solution of the unconstrained version of (7) over Rexn is X' = Σj= w/X,// Σ/= wy. Since {Xy} belong to the constraint set of (7) and this set is convex, X' too belongs to the constraint set. Hence, X' is the solution of (7), that is, X = X'. It remains to translate X back to labels, for which we can preform rowwise K-means, leading to Algorithm 1.
Since elements of Xx of rank at most K, to get a solution which is closer to that of the lifted barycenter problem (6), we can perform spectral truncation of X to K top eigenvectors, before applying the rowwise K-means. This leads to the spectral aggregation Algorithm 1. Other variants of spectral clustering on X are also possible, e.g., using the normalized Laplacian, etc. In the K-means step of Algorithm and 2, any constant-factor approximation to the K-means problem can be used.
2.2 CONSISTENCY
In order to study the statistical performance of different aggregation algorithms, we propose a random perturbation model (RPM), where both the clusters and the labels of the clusters can undergo random perturbations, allowing us to study the difficulty of the unsupervised aggregation problem. Let Z" & be the "true" label matrix with columns E Ex, i 1,....
Definition 1 (RPM). We write independently as follows:
L(Z", P)) if = (21...., 2n) EK with columns 2, drawn
2, = P2 2 ~ (1 (1- p)) + +p Unif(ER)
(8)
where d2g is the point mass 2 and P is independent K K permutation matrix.
4

---

Published as a conference paper at ICLR 2023
Under RPM, the observed label matrices Zi...., Nn are i...d., it is reasonable to let wi WN = in Algorithms 1 and 2. We will discuss the algorithm for weighted samples in Section 5. Let ny (2(Z)) be the number of objects in cluster & according to Z". We make the following assumption:
mx(Z") S Bn/K, k E
for some / E [1, R.. Here, 3 measures how much the true clustering deviates from being balanced. For = 1, we have nig (Z*) = n/ K for all k; while 3 = K corresponds to no restriction on the sizes of the true clusters. The following result shows that the basic aggregation algorithm is statistically consistent under the RPM:
Theorem (Consistency).. Let 7 E & be a label matrix satisfying (9). Assume that Zi,... , ZN are i.d. draws from Z .P) and E= p(2 p). Let Mis be the misclassification rate between the true label matrix Z², and the output of Algorithm I with wi = 1 for all j [N]. Then, there exists a universal constant C' >> O, such that
2,3 E[Mss] S E1 N
CE
EK
(10)
Consistency of Algorithm 1 follows from (10) and the Markov inequality: For any >> O, we have P(Mis 2 5) S 8- 3-EE[Mis] + as n, - oo and p is bounded away from 1. We note that in this and subsequent results all the parameters, such as K and are allowed to change as n, N + oc, subject to the conditions of the theorems.
The first term inside the parentheses in (10) is the dominant one. Assume for simplicity that 3 x 1. If the model has low noise, then p is small and so is & since { x p. Then, the dominant term O(pK/N) that is, smaller number of clusters, K, and larger sample size, N, improve the performance. The second term independent of of the sample size, but vanishes at the rate Opp K2/n) in the low noise setting, as the number of objects, n. grows.
2.3 LITERATURE COMPARISON
The relation between the metrics on clusterings is discussed in (34; 33). Let d',((, Zz, be the Mirkin metric between clusterings Z and 7, (34, Eqn (6)). As we show in Appendix B, it turns out that (2, = ||X - X,, = |X - Xxile, leading to d2 = SDD = Binder = (1) - Rand) where Binder denotes the Binder loss (5) and Rand, the Rand index (36). It follows that the lifted barycenter (6) that we derived is equivalent to the median partition (12) and the Binder loss barycenter of (45) as well the Rand barycenter (15). This problem is often solved by greedy search starting from a random initialization (45; 8). Our Algorithm 2 then provides a fast scalable spectral method of obtaining an approximate solution to this ubiquitous problem. A lot of algorithms proposed for consensus clustering operate on the average association matrix X, by treating it as a similarity matrix and performing usual clustering on it, for example, by performing agglomerative clustering (31; 18; 14; 28). Wade and Ghahramani (45) criticize these approaches as being ad-hoc compared to the docision-theoree
approach of finding a barycenter. However, we show X is indeed a solution to the relaxed version (7) of the barycenter (6) which is the same as the Binder barycenter in (45), hence clustering X is effectively solving the same problem with a different method.
A k-means based aggregation algorithm, called KCC, has been proposed in (48). In our notation, this is equivalent to concatenating Zys row-wise form an NK n matrix and running k-means on the columns. This is different from our Algorithm (I) that operates on X. We compare with KCC in Section 4. Unlike KCC, Algorithm (1) comes with a consistency guarantee under our model assumptions. The BestOrK (12) essentially solves (6) by restricting the feasible region to (Xi,... XN)), ), hence picking the lowest-scoring input clustering. The approach proposed in (7; 9) (see also (15)) to find the input clustering that minimizes the cost X + || X]|r. It is not hard to see that the barycenter cost (6) is equal to |X X [| plus constant (essentially a bias-variance decomposition; see (26)). Hence, the approach of (7; 9) is equivalent to the BestOrK. As we show in Appendix A, BestOfK is, in general, inconsistent under RPM unless N grows exponentially in n, very strong condition not needed by our algorithms.
The K-means step 3 in Algorithm (1) can be replaced by other clustering algorithms. e.g. average- linkage clustering, BestOfK and CC pivot algorithm of (18; 12). Besides global clustering algorithms, many authors, including (41; 17; 18; 45; 8) also propose local search, a.k.a. greedy, algorithms which
5

---

Published as a conference paper at ICLR 2023
Chernoff divergence
Boyesion Error Probability
K=2
18
-N
2.5
K
-N 10
K-
10
16
N (Chemolf div.
-[log(P NNNN JUN
122
1
1.5
0.0
1.
0.5
04
0
0
0.2
0.4
0.6
0.8
p
Figure 1: Left: Chernoff divergence in equation (11) as a function of the label perturbation probability. Right: How fast - (log PN)/N converges to the Chernoff divergence for K 2.
update one label at a time to minimize the barycenter loss, based on any number of metrics discussed earlier, including the information-thhorett ones (NMI and VI (32)). In (26), after reducing (6) to minimizing X + ||X ||? they write X = z Z (in our notation) and then relax Z to general nonnegative matrix and solve the problem with nonnegative matrix factorization. Their work has the flavor of our Algorithm 2, although our approach, being based on regular spectral decomposition, is highly robust and scalable.
The RPM, with P set equal to the identity, is closely related to the artificial data model considered in (18), with the difference that RPM does not potentially create a new cluster after perturbation, and introduces random permutation of the clusters labels after perturbation (via P). In Appendix E, we argue that RPM is good model of a concentrated posterior, hence consistency under RPM is relevant to Bayesian aggregation problems for which posterior consistency has been shown.
OPTIMAL RATE
Theorem 1 guarantees O(N rate of misclassification for Algorithm 1. A natural question is whether we can do better. To answer this question, we first consider what is the best an oracle, with the knowledge of the random permutations in (8), do. This oracle is effectively solving the supervised version of the problem. We then show that refinement step allows us to achieve nearly the same as the optimal oracle rate, without knowing the matching permutations.
3.1 SUPERVISED ORACLE
Let Z' be label matrix with the ith column 2 ~ (1-p)6.; + Unif(Ex), ), and let Zi.... N be independent copies of Z'. We would like to recover the true label matrix Z-. This is the oracle version of model (8), since Zys are label matrices without random permutations. In this case, the problem decouples independent label recovery problems. We further simplify the problem to that of deciding between 2 = é and ž = 62. This problem is equivalent the hypothesis testing:
Ho Multinomial N, p. q. .......))
.)) versus H1 Multinomial (N, (g. ")....q)):
where ;= p/A K and p : (K - l)q == q-q. A classical result from information theory (6, Theorem 11.9.1) allows us to determine the optimal performance this case:
Proposition 2. The Bayesian error probability, for testing Ho against H1, with positive prior probabilities, is bounded by eNN where
== - log 2 2 p)q (K - 2)q)
(11)
is the best achievable error exponent in the sense that - N/2 log PN - I as N 00.
The left panel in Figure shows plots of as a function of p. for various K, and the right panel shows the convergence of the exponent of PN for K 2. The Bayesian error probability Py be achieved by performing a likelihood ratio test between the two hypotheses. We can generalize this result to testing between K hypotheses, in which case the Bayesian error probability is bounded by

---

Published as a conference paper at ICLR 2023
Algorithm 3 Local Refinement
1: Input: Average association matrix X, initial label matrix Z.
2: Output: An updated label matrix Z.
3: for i= 1 to N do
4: Let X; be the ith column of X == wyXx.
5: Replace the ith column of Z by zeros and denote this matrix by Z_:.
6: Let (M1),...,,*) _x) be the row sums of Z-i.
7: Let (bl..... bx) Z_.X,.
8: Update the ith label by arg maxy (bx. (b//na).
9:
end for
(K 1)e The oracle algorithm that achieves this bound is the one that finds the column wise "argmax" of the average of Zys. In light of Proposition the bound in Theorem far from optimal since it guarantees linear decay of the error in N, that is O(N-1), rather than the exponential decay --NI The question is whether this gap can be filled by non-oracle algorithm.
3.2 LOCAL REFINEMENT
To approach the oracle rate, we propose a fast local refinement on the label of each object, as outlined in Algorithm& 3. This refinement
be performed on the output of any reasonable aggregation algorithm. The idea of performing a local refinement to boost the performance of clustering algorithms has been employed in various settings, including clustering of sub-Gaussian mixtures (30) and community detection in stochastic block models (SBM) (3; 16; 50; 51). more detailed comparison with the SBM appears in Appendix F.
Algorithm 3 requires a good initial label matrix Z, with small number of mismatches relative to the true matrix Z The algorithm focuses on the local information of the ith object. With X the average of the association matrices, X;, is the sample proportion of objects i and j appearing in the same cluster. Viewing X the adjacency matrix of weighted graph, one can verify that k} is the weighted number connections between object and objects in cluster The algorithm then normalizes the number of connections by the cluster size ng. Thus, bu/ne estimates the probability that object i is connected to another object in cluster k. The higher this probability is, the higher the chance that object belongs to cluster k. The last step in the for loop, updates the ith label according these statistics.
by = Eij; Wj (x
It is possible to repeat the local refinement procedure, by feeding its output 2 back initial label matrix. Given a good initialization, local refinements usually converge in constant or Oloog number of steps (30).
3.3 ACHIEVIIG THE SUPERVISED RATE WITHOUU SUPERVISION
From the oracle result (Proposition 2), we expect the optimal misclassification rate to be close to e -NI, This is verified by the next result, showing that a single local refinement step applied to a consistent aggregation algorithm, such Algorithm 1, can get nearly the optimal rate:
Theorem 2. Assume that Zi....,
.a....,Zy ZN are i.i.d. draws from the random perturbation model (8). Let Ž be the oulput of Algorithm 3 initialized by some, possibly data-dependent, Z. Let Timin minkelK] nu(2 be the smallest true cluster size and recall the definition of in (11), Assume that
(a) m1 (1A A T)/K + Dc and log
NI
K
-
and there exists d satisfying K Knō/(romn))) (Tmminp)) ) o(1) such that one of the followings holds:
(bl) PMMis 7, 7*) < 8) =1 1- o(1),
(b2) TE (aaiiss(,,) 7, 2*) <
Then, for some 77 o(1), the misclassification rate satisfies
P(Mis{ (","") s (1-n)))) = 1
(12)
7

---

Published as a conference paper at ICLR 2023
The assumptions of Theorem 2 are mild. Suppose that is bounded away from 0 or 1, say p [0.01, 0.99], K = =(1) and the cluster sizes are similar. Then, the assumptions can be simplified to mmin .N- - co and 6 = o(1). The theorem is most interesting when p + 1 and K is large. In this case, 1 + 0 and the first requirement of assumption (a) becomes 1mmin / K + co. This assumption guarantees that the samples provide sufficient information to recover the permutations, although we have not attempted to do so in our algorithm. The second requirement of assumption (a) provides evidence to distinguish the true labels from the other K labels.
Under the assumptions of Theorem 2, Algorithm 3 initialized with input satisfying (12), will have an output satisfying (b1). Hence, Theorem also guarantees rate-optimality of an iterative Algorithm 3.
EXPERIMENTAL RESULTS
We now present empirical results comparing the performances of the proposed aggregation algorithms,
with additional results provided in Appendix C. The ground truth label matrix Z' is generated by randomly assigning each of the objects to one of the K labels. The N input clusterings Zj. E [N] are generated from model (8). We measure the performance of an algorithm by the adjusted Rand index (ARI) of its output against the ground truth. We consider seven different aggregation algorithmss (I) Our Algorithm I, referred to "Basic" in the plots; (2) Our Algorithm 2, referred to as SC; (3) KCC algorithm (48); (4) CC Pivot algorithm (2; 18) with threshold 0.25; (5) Best One Element Move (BOEM) algorithm (11; 18): (6) the EM algorithm of (24); and (7) BestOfK algorithm (12; 18). In addition, we consider variants of algorithms (1)-(5 where we apply our refinement step to their output. This gives us total of 12 methods. In the plots, the refined version is denoted with solid line and the original version (without refinement) with a dotted line. We also use the average ARI of the N input clusterings, denoted by the INPUT, as a baseline.
Balanced setting with varying n and N. Figure 2 depicts plots of ARI versus the noise probability p in model (8), for various methods. The results are averaged over 40 replications. The settings in Figure 2 all correspond to balanced cluster sizes. Generally, our proposed Basic and SC algorithms outperform the EM, KCC, CCPivot and BOEM algorithms, with the failure thresholds occurring at larger values of p (harder problems). In some settings, the refinement shows some improvement, but in others, the output of the refinement applied to Basic and SC nearly coincides with the original algorithm. This shows that in some settings the original algorithm implicitly performs the refinement itself. We note that increasing N shifts the failure thresholds to the right as expected, as does the increasing of both consistent with our theory. Note that BestOfK performs no better than INPUT. Moreover, refined versions of KCC and BOEM outperform their original versions.
Unbalanced setting. Figure 3 depicts the results obtained with disproportionate cluster sizes, specifically with P1 proportion of the objects in one cluster and the rest distributed uniformly to the remaining clusters. Local refinement over Basic and SC performs significantly better as we deal with input clusterings of disproportionate cluster sizes, especially at lower noise probabilities.
5 CONCLUSION AND DISCUSSION
In the present paper, we defined the random perturbation model to study the label aggregation problem. We developed K-means type algorithm followed by an efficient local refinement step to achieve the optimal misclassification rate under the assumptions of the model. Numerical experiments also show the effectiveness of our proposed methods. Let us also discuss possible avenues for future work.
A single-stage algorithm. Two-stage algorithms have been popular in many clustering problems (3; 30: 16). Numerical experiments show that, in many cases, a K-means type algorithm performs sufficiently close to the local refinement with good initialization (Section 4). The K-means type algorithm assigns labels based on the distances between the objects and the centers. This criterion is different from the likelihood ratio test in many cases, and so the output of the algorithm will not achieve the misclassification rate of the oracle problem. It will be a novel improvement if the K-means type algorithm can be generalized to an EM-type algorithm so that the "distance" between the parameter and the object is defined by the likelihood. Whether such an algorithm exists, and how interesting open questions.
efficient it is statistically and computationally,
robust algorithm. We observe i.i.d. label matrices from the random perturbation model defined in Definition 1. As long as p < every label matrix from this model provides the same amount
8

---

Published as a conference paper at ICLR 2023
1.0
Method
1.00
Method
Jank
BeslD
Adjusted Rand Indexx
0.75
CCPhst
Adjusted Rand Indoxx
0.75
CCPNet
rput
Irput
<CC
KCC
0.30
0.50
TAUE
FALSE
FALSE
04
08
1.0
04
0.6
0.8
1.0
Probabilty
Probabiity
(a) = 100, N 20, K =
(b) n = 100, N 200, K =
1.00
Method
1.00
Methed
Bosk
Bask
BestbX
BestO%
0.75
CCP
0.75
CCPNet
ReristeRRardl Rardirdox Inddox
Adjusted Rand
Adjusted Rard
rpua
Input
KCC
0.50
0.50
Refined
Refined
0.25
TRUB
0.25
TRUE
TA1S
FMIST
0.20
0.00
04
08
1.0
84
0.6
1.0
Probabilly
Probebilly
nt) 500, N 20, K 6
(d) 500, N 200, K = 6
Figure Performance impact with the increase and
1.00
Method
1.00
Methed
Book
Bask
TeethX
BesoO
0.75
CCPlet
0.75
CCPlet
Adjotted Rand Randi Index
Adjusted laddo
rpptt
Input
KCC
0.50
0.50
Refined
Refined
0.25
TRUP
0.25
7ALSE
FALSE
04
08
1.0
0.4
0.6
1.0
Probabilty
Probabiity
(a) 100, N = 20, K = 6, 0.5
(b) n 100, N 20, K 6, 0.75
Figure Significant improvements due local refinement in the case of unbalanced cluster sizes.
of information in expectation, so there is no reason to assign different weights to label matrices. However, in practice, the samples may not be i.i.d.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
Zhixin Zhou was supported by the Research Grants Council of Hong Kong [Project Number 21502921]. A. A. Amini supported by the NSF grant DMS-1945667.
REFERENCES
[1] Daniel Duarte Abdala, Pakaket Wattuya, and Xiaoyi Jiang. Ensemble clustering via random walker consensus strategy. In 2010 20th International Conference on Pattern Recognition, pages 1433-1436. IEEE, 2010.
[2] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008
[3] Arash A Amini, Aiyou Chen, Peter J Bickel, and Elizaveta Levina. Pseudo-likelihen methods for community detection large sparse networks. The Annals of Statisties, 2144):2097-2122 2013.
[4] Arash A. Amini and Elizaveta Levina. On semidefinite relaxations for the block model. The Annals of Statistics,
2018.
[5] David A Binder. Bayesian cluster analysis. Biometrika, 65(1):31-38, 1978.
[6] Thomas M Cover. Flements of information theory. John Wiley Sons, 1999.
[7] David B Dahl. Model-based clustering for expression data via a dirichlet process mixture model.
Bayesian inference for gene expression and proteomics, 4:201-218, 2006.
[8] David B Dahl, Devin J Johnson, and Peter Müller. Search algorithms and loss functions for bayesian clustering. Journal of Computational and Graphical Statistics, pages 1-13, 2022.
[9] David Dahl and Michael A Newton. Multiple hypothesis testing by clustering treatment effects. Journal of the American Statistical Association, 102(478):5 17-5226 2007.
[10] Xiaoli Zhang Fem and Carla E Brodley. Solving cluster ensemble problems by bipartite graph partitioning. In Proceedings of the wennty-firsi international conference on Machine learning. page 36, 2004.
[11] Vladimir Filkov and Steven Skiena. Heterogeneous data integration with the consensus clus- tering formalism. In International Workshop on Data Integration in the Life Sciences, pages 110-123. Springer, 2004.
[12] Vladimir Filkov and Steven Skiena. Integrating microarray data by consensus clustering. International Journal on Artificial Intelligence Tools, 13(04))863-880, 2004.
[13] A. L. N. Fred and A. K. Jain. Data clustering using evidence accumulation. In 2002 International Conference on Pattern Recognition, volume 4, pages 276-280. IEEE, 2002.
[14] Ana LN Fred and Anil K Jain. Combining multiple clusterings using evidence accumulation. IEEE transactions pattern analysis and machine intelligence, 27(6):835 850, 2005.
[15] Arno Fritsch and Katja Ickstadt. Improved criteria for clustering based on the posterior similarity matrix. Bayesian analysis, 4(2):367-391, 2009.
[16] Chao Gao, Zongming Ma, Anderson Y Zhang, and Harrison Zhou. Achieving optimal misclassification proportion in stochastic block models. The Journal of Machine Learning Research, 18(1):190-20244, 2017.
[17] Aristides Gionis, Heikki Mannila, and Panayiotis Tsaparas. Clustering aggregation. Acm transactions knowledge discovery from data (tkdd), 1(1):4-es, 2007.
[18] Andrey Goder and Vladimir Filkov. Consensus clustering algorithms: Comparison and refine- ment. In 2008 Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 109-117 117. SIAM, 2008
10

---

Published as a conference paper at ICLR 2023
[19] David Inouye, Pradeep Ravikumar, and Inderjit Dhillon. Square root graphical models: Multi- variate generalizations of univariate exponential families that permit positive dependencies. In International conference machine learning, pages 2445-2453 PMLR, 2016.
[20] David Inouye, Eunho Yang, Genevera Allen, and Pradeep Ravikumar. A review of multivari- ate distributions for count data derived from the poisson distribution. Wiley Interdisciplinary Reviews:
Computational Statistics, r( 2017.
[21] Paul Kellam, Xiaohui Liu, Nigel Martin, Christine Orengo, Stephen Swift, and Allan Tucker. Comparing, contrasting and combining clusters in viral gene expression data. In Proceedings of 6th workshop on intelligent data analysis in medicine and pharmocology, pages 56-62, 2001.
[22] Jens Keuchel and Daniel Küttel. Efficient combination of probabilistic sampling approximations for robust image segmentation. In Joint Puttern Recognition Symposium, pages 41-50. Springer, 2006.
[23] Ludmila I Kuncheva and Dmitry P Vetrov. The problems of approximation in spaces of relations and qualitative data analysis. Information and Remote Control, 35(11):1424-1441 2006.
[24] Tilman Lange and Joachim M Buhmann. Combining partitions by probabilistic label aggregation. In Proceedings the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 147-156, 2005.
[25] John W Lau and Peter Green. Bayesian model-based clustering procedures. Journal of Computational and Graphical Statistics, 16(3):526-553) 2007.
[26] Tao Li and Chris Ding. Weighted consensus clustering. In Proceedings of the 2008 SIAM International Conference Data Mining, pages
SIAM, 2008.
[27] Tao Li, Mitsunori Ogihara, and Sheng Ma. On combining multiple clusterings: an overview and new perspective. Applied Intelligence, 33(2):207-219, 2010.
[28] Yan Li, Jian Yu, Pengwei Hao, and Zhulin Li. Clustering ensembles based on normalized edges. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 664 671. Springer, 2007.
[29] Yuan Li, Benjamin Rubinstein, and Trevor Cohn. Exploiting worker correlation for label aggregation crowdsourcing. In International Conference on Machine Learning, pages 3886-3895. PMLR, 2019.
[30] Yu Lu and Harrison H Zhou. Statistical and computational guarantees of lloyd's algorithm and its variants. arXiv preprint 1612. 2016.
[31] Mario Medvedovic and Siva Sivaganesan. Bayesian infinite mixture model based clustering of gene expression profiles. Bioinformatics, 1899):1194-2006 2002.
[32] Marina Meilä. Comparing clusterings by the variation of information. In Learning theory and kernel machines, pages 173-187. Springer, 2003.
[33] Marina Meilä. Comparing clusterings an information based distance. Journal of multivariate analysis, 98(5):873-8)) 2007.
[34] Marina Meilă. Comparing clusterings: axiomatic view. In Proceedings of the 22nd interna- tional conference on Machine learning, pages 577-584, 2005.
[35] Boris Mirkin. Reinterpreting the category utility function. Machine Learning, 45(2):219-228, 2001.
[36] William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, (6(336))846-887)) 1971.
[37] Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. Learning from crowds. Journal of machine learning research, 11(4), 2010.
11

---

Published as a conference paper at ICLR 2023
[38] Zahra Razaee and Arash Amini. The potts-ising model for discrete multivariate data. Advances in Neural Information Processing Systems, 33:13727-13753 2020.
[39] Simon Régnier. Sur quelques aspects mathématiques des problèmes de classification automa- tique. Mathématiques Sciences humaines, 82:13-29, 1983.
[40] Xavier Sevillano, Francese Alías, and Joan Claudi Socoró. Positional and confidence voting- based consensus functions for fuzzy cluster ensembles. Fuzzy Sets and Systems, 193:1-32, 2012.
[41] Alexander Strehl and Joydeep Ghosh. Cluster ensembles knowledge reuse framework for combining multiple partitions. Journal of machine learning research, 3(Dec):583-617, 2002.
[42] Alexander Topchy, Anil K Jain, and William Punch. Combining multiple weak clusterings. In Third IEEE international conference on data mining, pages 331-338. IEEE, 2003.
[43] Alexander Topchy, Anil K Jain, and William Punch. A mixture model for clustering ensembles. In Proceedings of the 2004 SIAM international conference on data mining, pages 379-390.
SIAM, 2004.
[44] Sandro Vega-Pons and José Ruiz-Shulcloper. A survey of clustering ensemble algorithms. International Journal of Pattern Recognition and Artificial Intelligence, 25(33:333322 2011.
[45] Sara Wade and Zoubin Ghahramani. Bayesian cluster analysis: Point estimation and credible balls (with discussion). Bayesian Analysis, 13(2):559-626, 2018
[46] Yoshiko Wakabayashi. The complexity of computing medians of relations. Resenhas do Instituto de Matemática Estatística da Universidade de São Paulo, 3(3):233-349 1998.
[47] Jacob Whitchill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration labels from labelers of unknown expertise. Advances in neural information processing systems, 22, 2009.
[48] Junjie Wu, Hongfu Liu, Hui Xiong, Jie Cao, and Jian Chen. K-means-based consensus clustering: A unified view. IEEE transactions on knowledge and data engineering, 27(1): 169, 2014.
[49] Zhixin Zhou and Arash A Amini. Analysis of spectral clustering algorithms for community detection: the general bipartite setting. The Journal of Machine Learning Reseurch, 20(1):1774- 1820, 2019.
[50] Zhixin Zhou and Arash A Amini. Optimal bipartite network clustering. The Journal Machine Learning Research, (()::4460-152) 2020.
[51] Zhixin Zhou and Ping Li. Rate optimal Chernoff bound and application to community detection the stochastic block models. Electronic Journal of Statistics, 14(1):1302 1347, 2020.
12

---

Published as a conference paper at ICLR 2023
Supplementary material for "Statistical Guarantees for Consensus Clustering"
This supplement contains the detailed proofs of the results and some extra simulations.
A INCONSISTENCY OF BESTOFK
Using the notation of the present paper, the name "BestOfK" should be "BestOfN". We will use our notation in the following proposition and keep the name "BestOfK".
Proposition 3. BestOfK is not consistent unless N grows exponentially fast in n..
Proof. We will prove this proposition by providing counterexample. Suppose K = 2, - 0.6 and 0.4. Then for label vector from the RPM, by the Hoeffding inequality,
F(Mis(z, 2") 0.1) 2 1 exp(2(0.4 0.1)² exp(2(0.6 0.1)²n) 2 1 2 exxp(-0.11
where we have accounted for the two permutations in the definition of Mis. Suppose we observe N i..dd label vectors 21,..., 2N from the RPM. Then
P min Mis(z,, =²) 2 0.1) 2 (1 2 2exp(-0.18n))* 2 - 1 2N exp( exp(-0.18m). VE(N
This probability (of missing the target) approaches I unless N grows exponentially fast in n.
B RELATIONS AMONG CLUSTERING DISTANCES
Let ny be the size of the kth cluster Z E EK and, ni the size of the éth cluster of Z E Ez. and let X and X be the corresponding association matrices. The Mirkin distance (34, Equ (6)) given by
(2,
Σ 1 Σ (mz) (m7)2-22
Σ
Tiee
2
(13)
R,E
where uhe is the number of objects that are in cluster k according to and cluster according to Z It is not hard see that Σn ni | and similarly (n;) | We also have Z(Z~)T (nze), hence, using || 1 trAA),
Σ | =) A,E
=
Combining these facts, obtain the first equality below
d' (7, 7*) ||X X ||x X*ller-
(14)
The second equality follows from X X having elements in 1,, 13. Here l| denotes the & norm of matrix viewed as a vector. The equality d',, (2, Z*) = - immediately shows that d', is indeed a distance on the space of clusterings. It also connects the Mirkin distance with the Rand index.
To see the connection with the Rand index, let Naisagees be the number of pairs of objects for which Z and Z' disagree about their co-clustering, that is, whether the two objects are in the same cluster or not. Similarly, let Nagree be the number of pairs of objects for which Z and 7' agree about their co-clustering. We have Naisagree + Nagree agreements, that is,
(*). The Rand index is defined as the proportion of the
Nagree (?)
Rand
is easy to see that ||X - X* 2.disagree where the factor of 2 is due to the double-counting caused by the symmetry of X X*. This proves the relation
2 _d'rr
1
n1 ( (1-Rand) Rand).
(15)
The symmetric difference distance (SDD) is another name for Naisugree hence d'n/2 SDD. The Binder loss is defined half the expression in (13), that is, d's /2 Binder.
13

---

Published as a conference paper at ICLR 2023
B.1 CONSISTENCY IN Mis IMPLIES CONSISTENCY IN MIRKIN DISTANCE
Let us now show that the consistency in Mis implies consistency in the normalized Mirkin distance defined dı == d'r /n". See (34, Eqn (9)). It then follows that consistency in Mis implies consistency in the normalized SDD, normalized Binder loss and the Rand index, as discussed above. This claim follows from the following inequality:
Proposition 4. We have du S 2 Mis.
Proof. Let X and X be the association matrices corresponding to label vectors and z². Then (z, x*) ||X lee shown in (14). The entries of X X take values in (-1,0,1) Assume, WLOG, that the optimal permutation between 2 and x" is the identity. Then:
If the label 2; zi then the ith row X X has at most "n Mis" nonzero entries. There are at most such rows.
2. If the label 2; # 2 then the ith row of X X has most nonzero entries. There most "n Mis" such rows.
Therefore, d's = X lel S (n-Mis)) + (n Mis) n Mis and the result follows.
C EXTRA SIMULATION RESULTS
Method
Method
Bea1DK
BssKOK
0.75
CCPASE
Adjested Rend Index
EM
Adjusted Rand Indiox
EM
rppe
Irput
KCC
KFC
0.50
0.50
Refined
Refined
0.25
FALSE
FALSE
0.00
04
0.
1.0
0.4
0.6
1.0
Protabilly
Probabilty
(a) n 100, = 20, = 6, 0.8
(b) 100, 20, = 6, P1 0.9
Figure 4: Significant improvements due to local refinement in the case of unbalanced cluster sizes.
Figure shows some extra cases of unbalanced cluster sizes (various values of pı as defined earlier), showing the significant improvement of the refinement step in such cases. All the results for the unbalanced case (including those in the main text) are averaged over 120 runs.
Tables 1, and 3 show the average ARI in all the eight settings (abbreviated Set in the tables) shown in Figures 2, and 4. The tables show the performance of the methods at noise probabilities p 0.45, 0.55 and 0.65 respectively corresponding to the y-axis, crossing the z-axis at the respective value of p. The settings are as follows:
cross-section of each plot at line parallel
1. Set 1: Balanced, n 100, N 20.
2. Set 2: Balanced, 100, N 200.
3. Set 3: Balanced, n 500, N = 20.
4. Set 4: Balanced, n 500, N = 200.
5. Set 5: Unbalanced, 100, 20, P1 0.5.
6. Set Unbalanced, 100, N 20, PI 0.75.
14

---

Published as a conference paper at ICLR 2023
Method
Refined
Set
Set 2
Set
Set 4
Set 5
Set
Set 7
Set 8
Basic
FALSE
1.00
1.00
1.00
1.00
0.82
0.35
0.24
0.093
Basic
TRUE
1.00
1.00
1.00
1.00
0.98
0.91
0.86
0.690
BestOrK
FALSE
0.32
0.30
0.29
0.31
0.33
0.28
0.24
0.150
BOEM
FALSE
0.50
0.48
0.57
0.69
0.38
0.41
0.33
0.310
BOEM
TRUE
0.65
0.59
0.94
1.00
0.60
0.70
0.52
0.430
CCPivot
FALSE
0.77
1.00
0.77
1.00
0.81
0.78
0.77
0.670
CCPivot
TRUE
0.84
1.00
0.81
1.00
0.81
0.75
0.70
0.570
EM
FALSE
0.97
0.98
0.97
0.99
0.72
0.41
0.36
0.220
Input
FALSE
0.30
0.30
0.30
0.30
0.33
0.28
0.25
0.160
KCC
FALSE
1.00
1.00
1.00
1.00
0.91
0.44
0.34
0.130
KCC
TRUE
1.00
1.00
1.00
1.00
0.93
0.50
0.41
0.180
SC
FALSE
0.99
1.00
1.00
1.00
0.96
0.65
0.65
0.430
SC
TRUE
1.00
1.00
1.00
1.00
0.99
0.98
0.97
0.880
Table I: Mean adjusted rand index (ARI) for all settings at noise probability 0.45.
Method
Refined
Set
Set 2
Set
Set 4
Set 5
Set 6
Set 7
Set 8
Basic
FALSE
0.96
1.00
0.98
1.00
0.66
0.26
0.19
0.077
Basic
TRUE
0.97
1.00
0.98
1.00
0.89
0.64
0.57
0.370
BestOrK
FALSE
0.20
0.21
0.20
0.20
0.23
0.19
0.17
0.096
BOEM
FALSE
0.21
0.21
0.23
0.29
0.33
0.39
0.31
0.240
BOEM
TRUE
0.46
0.36
0.56
0.65
0.55
0.62
0.48
0.280
CCPivot
FALSE
0.51
0.99
0.51
0.99
0.57
0.52
0.44
0.360
CCPivot
TRUE
0.61
0.98
0.54
0.94
0.52
0.36
0.32
0.200
EM
FALSE
0.87
0.95
0.91
0.97
0.64
0.33
0.27
0.140
Input
FALSE
0.20
0.20
0.20
0.20
0.23
0.18
0.16
0.098
KCC
FALSE
0.94
1.00
0.98
1.00
0.67
0.28
0.21
0.081
KCC
TRUE
0.97
1.00
0.98
1.00
0.74
0.36
0.27
0.130
SC
FALSE
0.95
1.00
0.98
1.00
0.75
0.41
0.35
0.170
SC
TRUE
0.97
1.00
0.98
1.00
0.95
0.86
0.79
0.550
Table 2: Mean adjusted rand index (ART) for all settings noise probability p 0.55.
7. Set 6: Unbalanced, 100, N 20, Pl 0.8.
8. Set 7: Unbalanced, 100, N 20, 0.9.
D PROOFS
D.1 PROOF OF PROPOSITION 1
For any Z E &R. we have 12 = Σx, - Zki n. Thus, 1 = 11;2,111 = n for
j E [N]. Hence, solving (5) equivalent maximizing f(Z) Ex= Wy tr(ZT tz
over ER. where Z = Σ, P,,, Let Z , and Z :x) Maximizing (z,, 2) is a separable problem over and maximizing 2 + (z, ž,) over & amounts to finding the index of the maximum element of E, that is, the "argmax" of 2, claimed.
= (
D.2 PROOF OF THROREM 1
We have Z, =P where Z' 12/////-.... (2/11...., and 2/2 are i..dd draws as in (8). Since the algorithm is invariant to permutations P,, without loss of generality we assume P, I,. hence Z, Zzz We write X (T 7" for the true association matrix. Let F,,, be the all-ones matrix.
15

---

Published as a conference paper at ICLR 2023
Method
Refined
Sct
Set
Set 3
Set 4
Set
Set 6
Set 7
Set 8
Basic
FALSE
0.790
1.000
0.88
1.00
0.47
0.17
0.120
0.061
Basic
TRUE
0.810
1,000
0.89
1.00
0.60
0.33
0.280
0.160
BestOrK
FALSE
0.120
0.130
0.12
0.12
0.13
0.11
0.098
0.062
BOEM
FALSE
0.085
0.098
0.12
0.11
0.24
0.29
0.320
0.270
BOEM
TRUE
0.130
0.150
0.21
0.22
0.36
0.33
0.290
0.150
CCPivot
FALSE
0.250
0.690
0.22
0.67
0.28
0.24
0.210
0.140
CCPivot
TRUE
0.280
0.540
0.21
0.37
0.22
0.12
0.088
0.051
EM
FALSE
0.600
0.920
0.74
0.95
0.46
0.23
0.180
0.078
Input
FALSE
0.120
0.120
0.12
0.12
0.14
0.11
0.096
0.059
KCC
FALSE
0.590
1.000
0.89
1.00
0.39
0.16
0.100
0.045
KCC
TRUE
0.740
1,000
0.89
1.00
0.52
0.24
0.180
0.083
SC
FALSE
0.750
1.000
0.88
1,00
0.47
0.19
0.140
0.076
SC
TRUE
0.810
1.000
0.89
1.00
0.65
0.40
0.330
0.190
Table 3: Mean adjusted rand index (ARI) for all settings at noise probability 0.65.
Lemma 1. Let Z L(Z"" ,P) and let X - 7 be the corresponding association mutrix. Then,
1 1-11 (11)))))
M B[X] = -1- + < K En
(1
(16)
where & p(2 p).
Proof of Lemma 1. We have Xis Z)² (2 23) and B[zz] = (1 p)2t + + 1x. For i 2i and 2j are independent, hence
1
EXG, = (Ezi, B2y) = ((1 - 2) + P K, (1 p)zz +p
1k)
K
1
= (1-p) (2) 25) + 2p(1 p) K
p K
For = j. we have [[X = The above shows that
E E[x]= - -)- p(2 p)
() En + +l2 +p(2-))11 1
K }
which simplifies to the desired expression.
Let Zi...., ZN, Z ~ L(Z".P) .p) be independent draws, and let X, = 2J Z, and X = ZT be the
associated association matrices. Setting X N EN Xt, we obtain
BIJ- MIB. >=EEXx,, E(X,; M2j) Σ var(X
N Σ var(X
1
ij
i5
We have var (Xi)) = 0 for i = j. For i + j. one has Xij ~ (e Xi + +E/K)
-
hence
var(X.;) = (1 - Xi
(1- + (1 x) + K2
+(E 1 2 Xij + ({{/K)
2
K
where (xx) = =x01= - .r). Note that E p(2 p) E (0, 1). It follows that
N E M < (5) - K
3) Σ X +n²((E/K) "
where the inequality due to bounding var(X(;) by the same formula used for var(X1;), # j. Let ni be the number of entities in cluster & of Zz, that is, nă -2 In).. We have E X
|| 1, 2 Using the assumption nł < 8n/ K, have
82n
N E X M < (5) (1 K
+ n² (E/KE.
K
16

---

Published as a conference paper at ICLR 2023
Calculating the center separations. diagonal and
Let M (1 (1- +1- We note that M - -M is
| - - -| e
It follows that
B -
E Σ
- - + Σ (X, - M,)²
- = - M + +52
We obtain
- - MB
2 < N
(E) (1 (1- 2 32
+ (E/KK)) + 20²
K
K
The matrix M is K-means matrix with K distinct rows. If x k =zr then
MM - Mr.11 = (1 - - - (1-)){{)))) + + 2 2(1 2(1 n
3K
using n 2 n/(3)), which holds by assumption (9). We have n, 2 2(1 - - (g )² which gives the following bound, using (49, Proposition 1),
E[Mis,] - N(L (E) 2) 822
1
5²
K22²
E
Here, Mis, is the misclassification rate over true cluster r. The dependence on 3 of the first term is O(3²) when K and ((3*) when K > Ignoring this difference, we can simplify the bound, by noting that K2 (²/(K/K) KE(1 - E/K) < Kg and B S 3r. Then,
2K3 3
5² 3²
E|Mis,]
2
N
(1
8)
from which the bound in the theorem follows since Mis (n7./v)) Misp.
D.3 PROOF SKETCH FOR THEOREM
For the benefit of the readers, first give proof sketch for Theorem 2 and its key lemma. A detailed proof is given in Appendix D.4. The proof of Theorem 2 relies on the following key lemma:
Lemma 2. Let B()) denote the set of label matrices Z with at most nō labels different from Z", and let (Z) be the output of Algorithm 3 with initial label matrix Z. If Timia(1 A 1)/K + oc and
log K + 0, then N1
P(3Z B()) such that 2((Z) # =5) se -(L-7)
3KadN 2p
(17)
for some n o().
The first step is to prove the case 8 in Lemma 2, corresponding to the initial label matrix in Algorithm 3 being z" If ,. ei, then the algorithm fails to recover z if there exists k * 1 such that Y4 = n, b, nxb 0. Ys the average of i.i.d. samples, where each sample follows a mixture model depending on which events among = Ei. 2 or 2, & {e1, ex happens. We compute the MGF of Y₁ and obtain the bound
E E[exp((NNY
p))}] < ((1-ū)e ((1-0)e-(+o(1)) (1++((1) + qe (1+0(11) (K 2)g
Timi 23
The choice of has little affect on the last term since Mmmi is large, so we set / = Z log((1 p)/q] to minimize (1 - pte-+ + ge.. Under the regularity conditions of the lemma and the definition of in (11), we have
E [[eep(tYY/( p}))] < [2 p)q + (K 2)q] (1-)(1))N -0-(o((N))
17

---

Published as a conference paper at ICLR 2023
Applying the Chernoff inequality, it follows that
((2((Z)
PP (Y 2 0) S Σ Blexp(tY) p)))| S (K 1)e- (1-O(1)
Using the assumption log K
0. obtain (Z)) 2!) e-(1-)) This proves the
case 5 = 0. Now we compare Y&'s obtained from Algorithm initialized with label matrices Z and Z. and denoted by (Z*) and (Z), respectively. For all Z E B(o), we show that [Yx(Z*) (Z)) & 3(m V ni) no if 2 E1, giving
P(3Z B(6) such that ( + 2
Σ k=2
P(Y 3((1 V nk)nd).
We apply the Chernoff inequality with the same choice of t to obtain (17). We arrive at the proof of Theorem 2. Let (Z) be the output of Algorithm with initial label matrix Z. Consider the event As = (Mis( Ž, Zz) I 63. For any E > 0,
P(Mis [ 2*) 8) s P(A)) + P E B(O)), Mis (is( s).
We have P(Ag) = (1) under assumption (b1). Letting = Nle [ 3Ke88
2ymiin one can verify that the second probability also converges 0 under the conditions of the theorem and e (1-o(())) This proves (20) under assumption (bl). For the proof under assumption (b2), please see Appendix D.4
D.4 DETAILED PROOF OF THEOREM 2
Let ?(Z) be the output of Algorithm 3 with initial label matrix Z. Consider the event Ag.
[Mis( Z, 2*) < J. For any & > 0,
P(Mis( 2(22, 2)) > ((A)) + P(3
B(8"), (is
(18)
assumption (b1) holds, then let 8' 8 so that P(AA) = o(1) asssumttio (b2) holds, Then we let = V P (n) so that
Kn8d
Knō Deminpl
o(1)
Pminp]
and by Markov's inequality,
P(Mis Ž. 2z) 8') S E[Mis{ Z, z²) 5 8
Knδ
o(1).
8'
Ammppl
Then, (bl) is satisfied with 8 8' Therefore, it is enough only consider assumption (b1) and let
= 5 for the rest of the proof.
Let nt be the permutation corresponding to Mis(ž, 2*) in assumption (b1), that is, n" argmin, Σ 1(2, # π( Since we can always assume T' (=*) be the true label, with- out loss of generality, we can assume x² = identity. Writing T2 for the second term in (18),
Te < 32 E B(8). Σ (2(()) # 2 nE
< P
[E e 8()), # # > nE
By Markov's inequality, we obtain
1 P P(3Z E B(6), 2(Z) + =
1 -1111')) Sprinie
T2
-e
(19)
nE
where the second inequality follows from Lemma 2, given assumption (a) of the theorem.
18

---

Published as a conference paper at ICLR 2023
Assumption (a) of the theorem also implies 3KnoN o(NI), this term can be absorbed into 2pmmin
INN, T2 S -1-01=="M NI for some - o(1). = Let
8 = NIe (ie--1111 (1~1")N7 = =
o(1). It follows from (19) that where 7) = rf" log(NT)
T2 - - (1 (1-1")N1
NI = o(1)
Hence, we obtain (12) as desired.
D.4.1 AN AUXILIARY LEMMA
We state the case 5 0 in Lemma 2 as separate lemma and prove it first. Recall that 7mmin [ My where y is the size of the kth cluster. We have the following lemma.
Lemma 3 (Local refinement with Z ). Suppose the initial label matrix in Algorithm 3 is Z", and assume p (1 A T)/K K 0G and log K
N7 0, then
P( + 2, = e (1-7)NN
(20)
for some v o(1). As direct consequence, E [M (2 22)" S -
Proof of Lemma 3. Let q := p/K and p= (K 1)9 = 9. We first focus on the probability P(21 + z(). Let C = {i 2 2 z = ex We have by = -iiec; (z,, 21). Since = = ei by assumption, takes values e1 and any of ex, l + 1 w.p. 1 - p and q. For i Ci, has the same distribution 21. For i Cj. 24 takes values e2 and any of ex, + 2 w.p. P and q respectively.
Note that (b1, b2) is independent of 21. It follows that
Bin(n1, 1 p) @ Bin q),
if 21
b2) 21
Bin(n1, q) (in p).
if 21 = 62
(21)
Bin(ni, q) @ Bin( 9),
i $ (21.
where @ is the notation for the product measure, that is, by and by are independent each case. The three possibilities above hold with probability 1-p. and (K 2 respectively. Let Y n1b2 n2bb1 and let (A) be the moment-generating function (MGF) of
Let (): 1 p ped be the MGF of Ber(p) variable. Then, the MGF of Bin p) is p):
and hence
Blexy AY
21]
Eledmabs [2]] Be Amabi Anabi
[11]
((Am: =2 (60--b((n Anz; 1 - n) if = e1 if =
((An) 1- - p)m² " ((Mm:g)) ((-An22:)"
if & (2),
Let ((): = exp(u(e> - 1)) be the MGF of Poi(u) and note that (>:pp)) S o(>; mp). Then, for example, have
Brear AY | = e1] ((Am; mz9) (app:)g))--(((Mmiae
p))
Since ()); expp(u(> + o())) exppp>(( [[])] for A = o(1), we obtain
EieAY 2 e1] - exp m2 + mn - (1
assuming that X(n1 n2)) o(1) Then,
Ele 1 en s -
Take A 1 - p) for some
> 0 to be determined below. Noting q + 5 -(1 ---1) p).
E 31 el < expl xxp[-((1 (1)))
19

---

Published as a conference paper at ICLR 2023
The case e2 is argued similarly and we obtain the bound BleAM 21 ez] s exp[t(1+o(1))]-
For 21 $ (e1,e2); we perform a second-order expansion, assuming X = o[))
<(>: explu(2 2 _ + o({)))] - exp exp(p1 [M(A (A + 22)]
and obtain
() ( 9) " - exp | (1 + n2)g
y :- 24 - p)² and let Ahhar :- 2111112///// (nı + n2) be the harmonic mean of and n22 Note
that Thar 2 memin- We have
[²1 + n2)g 71² //har. ( + n2)4 11 (1 p)2
To summarize, the conditional MGF satisfies
+ +o())]
if 61 if e2 = $ {2),
/ [1]]
exp (11 + +0(1) exp(11t /Tnar))
Recall that the events 21 E1, = 62 and ø1 & e2) happen with probability 1- p. q and (K - 2)q respectively. It follows that
(y p))) (1 p) ([++([1)) + q (( (K- 2)q e / /an..
(22)
Let us set
1 = log((1 D)/4) log 1 +
1
K (1
(1-1)):
(23)
p
so that (1- = get v11 - p)q. Then, t and since log(1 - x) S z, we have 1 i K (1 - p)p()
(24)
The condition A(11 + 122) = o(1 is satisfied under assumption Rmin K + ca, since
(ml 12)1
21
K(1 p)/p
K
X(11 + 112)
o(1).
n1n2 - p) T (1 p) naarr (1 p)
RaninP
Recalling that q P/K, K, the exponent of the last term in (22) satisfies
yt? - <1 p)
2qK²
K
K
=(1)
Tharr 4p2
4p2
2TharP
2nminn
under the assumption of the lemma. It follows that
Mr(l//mmm2(1 - (p)) < 2/(11 F)y + (K - 21
= =(( (1 p1 1o(1) + (K 2)qe (())
[[[ - ()1) V v e
where the first equality by eo(t) (ef)o(1) = (v(11 p)g) (1)) for our choice of and the second equality by the definition (11) of T. Since v(1- - 1)9 S e_t, we have (v(1 p)g) = eo()) hence
My My(t/(min211 - pp)) I ( è -1 1 = e (1-0(1)) = e (1-1)) Let Y YN be the i..dd copies of Y. By Markov's inequality,
N
Mv, = - Y, 2 1) S BEAEX E v, = My,(A)* < (1-w))
The above argument shows that IP( it shows that
l2 ng
(1--)))) ml
b
Repeating the argument for the ith label,
b
by
bi n2
P(2 + 2
max K
S S(K
-a---nn (1-mN1
12...KK
n&kk
n1
T2k
If K 2, then we have already obtained (20). If K > 2, then
(K -1-m)NN = No
= =
The term oNTT be absorbed into n,N, so we can still obtain (20).
20

---

Published as a conference paper at ICLR 2023
D.4.2 DETAILED PROOF OF LEMMA 2
Let i without loss of generality, and let Z B(6), and ûх nng(() the size of the kth cluster in the label matrix Z. Let bu (Z*) = (Z= and bn (Z) = (2-1X1)) where X1 is the first column of X in the algorithm. Suppose Z has at most nó labels different from Z", then
[m]b2(Z*) - (221((")) (2) - nobbi [2)]] < (01 V m2)) nō.
and
[[]bb((Z) (2gil)))nnn(((_) (Z) [ fzb1 (Z)]l s |m1 nnl (2( [n2 -22l (z) S ná (πi n22).
= n2 ( n2b1 (2*) and Y(2) = (2) ûzb1 (Z). Combining the two by the Let -
triangle inequality, we obtain
nd IY(2*) - (Z)) s 3(n1 V nō h()).
By Markov's inequality, for x 1
P max Y(2) 20) < 2 -h()) 2EB(8)
=P(e\NV(Z) 20 2 -ANh(1)) (ANN(01E(
As in the proof of Lemma 3, we take == =t/11nn21 -p)l_ with i given by (23). Using the upper bound (24), we have
ANh(6) 3(mi V V12)nN
3KnoN
n1n2(1 56 S
2pm
The result follows as in Lemma 3.
E
RPM AND BAYESIAN AGGREGATION
One might ask whether RPM is a useful model in practice. For the applications in which all the label vectors are perturbations of a common true "center", and our goal is recover this center, RPM is good first approximation. This is the case for Bayesian label aggregation as we argue below. In such settings, the RPM is like the i.i.d. noise model used in classical regression. Although one can imagine more complex regression models (like those with heteroscedastic noise, or mixtures of regressions, etc.), the i.i.d. setting still provides a lot of insights for understanding the more complex models.
E. RPM IS A GOOD MODEL FOR A CONCENTRATED POSTERIOR
Lets us argue how can arrive RPM in the context of Bayesian aggregation, by systematically making some assumptions. First, we note that our goal in the paper is not to prove the "posterior concentration around the truth", also known as posterior consistency. This is problem-specific and out of the scope of this work. We assume that we are working with a model for which posterior consistency has already been established. The question that we are trying to answer is then this:
Given that the posterior concentrates around the true partition, and given that the MCMC has converged that is, we are sampling from this concentrated posterior- obtain consistent estimate of the center of the posterior (which would be the true partition) based these samples?
For this purpose, it is enough to assume that we are observing samples from the posterior p(2,,...,,,, D), where D is the observed data, and this posterior is concentrating around x" which the true partition. For simplicity, let us drop D and note that the posterior is some multivariate discrete distribution p(z1...., 2.). Then, we proceed in steps:
1. First, address the label-switching issue. Let be sample from the posterior and let permutation म be the minimizer H (2" ा (2))) over all K! permutations, where H (:.)) is the Hamming distance. We note that ι is equivalent label vector (only the cluster
21

---

Published as a conference paper at ICLR 2023
labels are permuted.) We consider the distribution of x (2) as the posterior distribution rather than that of z. This is only to simplify the discussion and is without loss of generality, since methods are invariant to label-switching. The distribution of (2)) will have a single mode at =" while that of z will have K! modes on all equivalent versions of =". Given such simplification, renaming (=))
from now on, the posterior is multivariate distribution p(z1,..., 2n) which is highly concentrated around x = (2i,...,,,,) 2,)) This follows from the posterior consistency assumption.
2. We claim that this multivariate distribution can be approximated by the product of its marginals p( =n) ~ Ih p.(z:). This is intuitively clear for any concentrated discrete distribution. Alternatively, it is intuitively clear to anyone who has looked at MCMC samples at stationarity. Each node/object i usually has most likely assignment which is 2/, but it occasionally jumps to some other label with a small probability. The fluctuations for different nodes are independent; this is intuitively because the bulk of the labels don't 't change their clusters all at once; only a few do at any given time.
3. Non-uniform RPM: Given the independence assumption across i, the most general form pi(z;) can take is categorical (a.k.a. Multinomial(I.n)) (1. distribution. The bulk of the mass of this categorical variable will be on 2j and the rest distributed among the other labels. For example, for some node, i, the label can jump, say, between 2 and 5 with the bulk of the probability on 3. For others it could be that when they jump from z they land over larger collection of labels. Here, we are making the simplifying assumption that for each node, the mass that is put on anything other than = is uniformly distributed over the label set [K] \ {zā }. This assumption can be removed, and we can work with general categorical variables, at the expense of making the rates and the analysis more complicated.
4. Inhomogeneous RPM: Given that the noise in the categorical variable is uniform over [K] } we now assume that the probability of taking any of those values is the same for the all nodes (i.e., independent of i). This is exactly the homogeneous RPM that we consider. This assumption is easy to remove and we can work with the inhomogeneous RPM that allows this probability to depend on i.
We do not lose anything in Step 1. Steps 3 and 4 are simplifying steps that are taken for the ease of understanding and presentation. The main assumption is Step 2, the approximation by the product of marginals. Below we provide some hard evidence that this is very reasonable in the Bayesian setting.
E.2 HARD EVIDENCE OF NEAR-INDEPENDENCE
We consider the problem of recovering the clusters in stochastic block model (SBM) which is random network model with latent node clusters. Figure 5 shows the Sequential NMI plot for Gibbs sampler on nonpmarmet SBM (with a Dirichlet Process prior on labels). The sequential NMI means that we compute the NMI of the partition at iteration relative to that at iteration / 1, and the x-axis shows f. The plot suggests that the chain enters stationarity roughly around iteration 100.
We use the MMD-based approach, described in (19; 20; 38), to compare the posterior joint distribution of the labels to its approximate versions:
Figure 6(a) shows the result for samples from iterations 100 to 1000 of the Gibbs sampler.
This is the stationary joint distribution.
Figure 6(b) shows the result for samples from iterations 1 to 100 of the Gibbs sampler. This is based on the transient samples (effectively, average joint behavior over the transient period).
Figure 6(c) shows the results on movie rating dataset with complicated dependent joint distribution (that has nothing to do with SBM).
We refer to (19; 20; 38) for details of how these experiments are performed. The bootstrap MMD serves as the baseline; those methods whose MMD is closer to the bootstrap are better approximations of the joint distribution. In general smaller MMD means a better approximation of the joint. Ind Mult is exactly the approximation by independent multinomials (i.c. product of marginals). The Copula Mult is good joint model for the discrete multivariate distribution.
22

---

Published as a conference paper at ICLR 2023
0.75
Squential NMI
0.50
0.25
0.00
Iteration
Figure 5: Sequential NMI for the SBM Gibbs sampler
fd
50)
=30
Ind M.
Coouta MAR
Copult Mii
Pati-comppemmet Max Mean Diccippnnyy
Pall-conskement Maximum Moan Dicrspancy
Par-comssleeen Macimm Mean Dacrppanc
(a)
(b)
(c)
Figure 6: MMD histograms between the posterior distribution and its various approximations
We see that for the movie rating data and the transient chain, indeed Copula Mult has much lower MMD, than Ind Mult, showing that there is dependence in the joint that is not captured by Ind Mult. However, for the stationary distribution (Figure 6(a)), the Ind Mult has comparable (and even slightly smaller MMD) relative to the Copula Mult, and is close to bootstrap. This shows that the product of marginals is good approximation in this case, and justifies Step 2 in our reduction.
F COMPARISON WITH STOCHASTIC BLOCK MODEL
Below we outline some of the similarities and differences between the problem of cluster recovery in SBM and the consensus clustering problem consider in this paper. Suppose that A the adjacency matrix generated from the stochastic block model (SBM) and X is the association matrix generated from the RPM.
A larger value of X increases the likelihood of and j being in the same cluster in RPM. Similarly, Au i.e., there is edge between and j, increases the likelihood of i and j being the same community in SBM. Therefore, both X and can be considered proximity matrices and we can utilize min-cut algorithm them find the clusters. To approximate the
Similarity:
23

---

Published as a conference paper at ICLR 2023
min-cut algorithm, various researchers have proposed the approach of using good initialization plus a local refinement step. This idea can be applied to many clustering problems, including community detection. In this paper, show that it can also be applied consensus clustering.
The entries of the adjacency matrix A are independent, but the entries of the association matrix X are not. Indeed, the entries on the same row of X have very strong dependence. The likelihood function of X is very different from A, but we can still show that simple local refinement step outputs optimal labels. The error rate comparable to the Bayes error rate given by likelihood ratio test.
Difference:
24


Reviews:
[{"review_id": "uTJ4eVXxYe8", "reviewer": "Reviewer_38hB", "summary": "", "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": "", "summary_of_the_paper": "The paper studies the problem of computing consensus clustering when groups can be equivalently permuted. They analyzed the problem in the discrete vector form, combinatorial matrix form, and nonnegative semidefinite programming (SDP) form by relaxation, and propose a simple weighting algorithm to compute the low rank matrix and consequently the labeling. To provide some guarantees for their proposed algorithm, the authors propose a random perturbation model (RPM) which generates the aforementioned labeling instances in a stochastic way. Under this RPM setting, the authors provide some upper bounds with respect to the misclassification rate. ", "summary_of_the_review": "The problem setting and analysis feel artificial, and the techniques are standard.", "strength_and_weaknesses": "Strength:\n- The paper is easy to follow in general. Most of the notations are properly defined.\n- The flow of the analysis is clear (original problem -> matrix problem -> SDP -> algorithms).\n\nWeakness:\n\nMy biggest concern is that the problem being studied feels artificial, and a lot of techniques used are standard and very similar to existing community detection / stochatic blockmodel (SBM) literature. \n\nAbout the problem:\n- I feel that the problem is intentionally posed in the current way to make the analysis more complicated than necessary. For example, the authors stress on Page 2, that problem (3) is hard because of the factorial number of permutations. This is exaggerating because one can simply consider the association matrices zz^T, and this is a quite common step in community detection literature because very often people do not care about permutations.\n- If the authors believe that the step by step relaxation is necessary (instead of going for xx^T's directly), it would be helpful if they show the tightness of their relaxation. In other words, is there any proof governing that, under what models or statistical conditions, the optimal solution to (7) is equal to the optimal solution to (6), and the optimal solution to (5)? Otherwise, such relaxation is heuristic and without guarantee.\n- How should I interpret RPM? Why is it reasonable? Is there any real world dataset follows from the model?  \n\nAbout novelty:\n- The vector -> matrix -> SDP relaxation is standard in SBM works; for instance see SDP-1 in [1]. \n- The idea of using a permutation matrix is covered in a highly similar fashion between (3.3) and (3.4) in [1]. \n- In fact, I fear that the problem of minimizing the Frobenious norm in this paper is equivalent to the problem of maximizing the inner product as in SDP-1 [1], by adding some entrywise summation constraints like X \\1 = (n/k) \\1.\n\nReferences:\n- [1] Amini, Arash A., and Elizaveta Levina. \"On semidefinite relaxations for the block model.\" The Annals of Statistics 46.1 (2018): 149-179.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "U3S48CafZZ", "reviewer": "Reviewer_QD6L", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the unsupervised consensus clustering problem: given $N$ $K$- clustering vectors on n data points, a single clustering solution is to be found that minimizes the distance to $N$ $K$- clustering vectors. This problem is in general challenging due to the freedom of label switching among $N$ $K$ - clustering vectors. The authors address the label-switching issue by lifting the solution space to association matrices, and relaxing the original problem to a semi-definite programming (SDP) problem that has a closed-form solution. Afterwards, the clustering solution can be constructed from the SDP solution. The proposed algorithm achieves statistical consistency, i.e., the error bound goes to 0 as $n,N\\to\\infty$, under the random perturbation generative model of these $N$ $K$- clustering vectors. Moreover, a further refinement procedure on the clustering solution can be shown to attain the near optimal error rate with respect to $N$. The authors corroborate the theory by evaluating the proposed algorithm under different choice of n, N and data balancedness. A quite comprehensive comparison with other algorithms in the literature has also been done in this work. ", "summary_of_the_review": "This work makes a contribution for establishing the statistical consistency and near optimality rate for the unsupervised consensus clustering problem, under a generative model. The theory is interesting to the community. ", "strength_and_weaknesses": "The statistical consistency under the random perturbation model has been proved for the proposed algorithms. In particular, the proposed local refinement procedure is interesting, which is motivated by matching the error rate in the supervised consensus clustering. This is an important technical contribution. There are a few aspects I believe the authors can further elaborate: (1) RPM has a strong connection with the Bayesian aggregation, as shown in the supplementary. Have other probabilistic models been considered in literature? Empirically, how robust is the proposed algorithm against other settings? (2) Computationally, by lifting the solution space to the association matrices, the dimension is $n\\times n$, would it be too expensive when $n$ is large? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PTM7zMJdgpV", "reviewer": "Reviewer_12P5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of aggregating clusterings of a set of data points. This is a well-studied problem in we are given a collection of clusterings of a given dataset and the goal is to produce a new clustering that is \"close\" to the given ones.\n\nThe problem is non-trivial because clusterings remain the same even after permuting the labels. Thus the authors produce a natural algorithm based on looking at the association (or similarity) matrices of the clusterings and taking an average of those. This is a natural idea, and it has been extensively studied in the literature as the authors also note. \n\nThe main contribution of the paper is to provide (a) a consistency analysis of such a procedure under a generative model for clusterings, and (b) giving an algorithm that can achieve an error that drops optimally with the number of clusterings. The generative model is what the authors call the \"robust perturbation model\", and is a natural one in this context: a set of clusterings are obtained from a \"ground truth\" clustering by permuting the labels and adding IID error to them. Given these clusterings, the goal is to recover the ground truth up to a permutation.\n\nThe paper shows that the simple algorithm that first averages the association matrices and then performs a K-means step achieves a consistency guarantee that goes to zero with the number of clusterings 'N' and the number of points 'n'. They then give an algorithm that improves the dependence on N via a post-processing step.", "summary_of_the_review": "(Pasted from above): The main strength of the paper is in analyzing the consistency, especially in terms of the number of misclassifications. They also do so for a natural algorithm. That said, the results are not too surprising given the generative model. Also algorithmically, it seems that other than improving the N dependence, there was not sufficient novelty, especially for a theory paper. So while I am overall positive about the paper, I don't see it as a definite accept.\n", "strength_and_weaknesses": "The main strength of the paper is in analyzing the consistency, especially in terms of the number of misclassifications. They also do so for a natural algorithm.\n\nThat said, the results are not very surprising given the generative model. Also algorithmically, it seems that other than improving the N dependence, there was not sufficient novelty, especially since all the results are theoretical. So while I am overall positive about the paper, I don't see it as a definite accept.\n\nHere are some questions that I would like to see the authors address:\n\n1. While the dependence on N is analyzed, the dependence on the other parameters such as \\beta is not. Can the authors say if they expect the dependence to be improvable?\n\n2. The kinds of issues the authors run into in terms of cluster recovery are similar to those in the following recent paper: https://proceedings.mlr.press/v178/gamlath22a.html\n\nThis is a recent paper so if not a detailed response, it would be good to see the authors' initial thoughts.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster