Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

The 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. 

The 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.

The 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.
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.

That 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.

Here are some questions that I would like to see the authors address:

1. 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?

2. 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

This is a recent paper so if not a detailed response, it would be good to see the authors' initial thoughts.
clarity,_quality,_novelty_and_reproducibility: The paper is well written overall. The algorithm is along well-studied lines, but the analytical model is new, to the best of my knowledge.

The work is primarily theoretical, so the reproducibility question is not applicable. 
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strength:
- The paper is easy to follow in general. Most of the notations are properly defined.
- The flow of the analysis is clear (original problem -> matrix problem -> SDP -> algorithms).

Weakness:

My 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. 

About the problem:
- 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.
- 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.
- How should I interpret RPM? Why is it reasonable? Is there any real world dataset follows from the model?  

About novelty:
- The vector -> matrix -> SDP relaxation is standard in SBM works; for instance see SDP-1 in [1]. 
- The idea of using a permutation matrix is covered in a highly similar fashion between (3.3) and (3.4) in [1]. 
- 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.

References:
- [1] Amini, Arash A., and Elizaveta Levina. "On semidefinite relaxations for the block model." The Annals of Statistics 46.1 (2018): 149-179.
clarity,_quality,_novelty_and_reproducibility: - Are the relaxations tight? See above.
- What is the relationship between RPM and SBM, in terms of the association matrix? Can one be subsumed by the other?
- It seems to me that Eq. (5) does not parse, since both Z and P's are variables in the argmin, but the left hand side is only Z. Should it be \argmin_Z \min_{P_1,\dots,P_N}?
- Page 3: "One can verify that problem (5) is equivalent to (3)." Could you give a brief proof?
summary_of_the_review: The problem setting and analysis feel artificial, and the techniques are standard.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
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? 
clarity,_quality,_novelty_and_reproducibility: The paper is very well structured and written, with the important technical details proved in the supplementary. A few clarifications for some minor details: (1) In definition (1), the permutation matrix $P$ is sampled from all permutation matrices, right? In particular, if $Z_{1}$ and $Z_{2}$ are sampled from the model, the corresponding $P_{1}$ and $P_{2}$ can be different if I understand correctly. (2) In most cases, the refinement procedure improves the solution quality. But for the green curve (CC Pivot), the result is the reverse, is there any explanation?
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the problem of aggregating clusterings of a dataset: we are given a collection of clusterings of a dataset and the goal is to produce a new clustering that is "close" to the given ones. The problem is non-trivial because clusterings remain the same even after permuting the labels. This work develops a natural algorithm based on studying the association/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.

The paper is very well-structured and well-written.

The main contributions of the paper are to provide: a consistency analysis of such a procedure under a generative model for clusterings, and 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.

Given the generative model, the authors show that a very popular algorithm (BestOFK) is in general inconsistent, despite being a 2-approximation to the median partition problem. This shows that consistency in this problem is not to be taken for granted. 

Among the questions raised are that since RPM has a strong connection with Bayesian aggregation, have other probabilistic models been considered, and how robust the proposed algorithm is against other settings. 


justification_for_why_not_higher_score: Having seen past oral/spotlight papers, I don't see this rising to that level. For instance, while the dependence on the parameter N is analyzed, the dependence on the other parameters such as beta is not.
justification_for_why_not_lower_score: A clean and natural model, good theoretical progress, some surprises regarding known approximation algorithms.
Decision: Accept: poster