Solving Soft Clustering Ensemble via $k$-Sparse Discrete Wasserstein Barycenter
Authors: Ruizhe Qin
Mengying Li
Hu Ding
Venue: NeurIPS 2021 Poster (2021)
Keywords: ensemble clustering
Wasserstein barycenter
soft clustering
approximation algorithm

Abstract: Clustering ensemble is one of the most important problems in  ensemble learning. Though it has been extensively studied in the past decades, the existing methods often suffer from the issues like high computational complexity and the difficulty on understanding the consensus. In this paper, we study the more general soft clustering ensemble problem where each individual solution is a soft clustering. We connect it to the well-known discrete Wasserstein barycenter problem in geometry. Based on some novel geometric insights in high dimensions, we propose the sampling-based algorithms with provable quality guarantees. We also provide the systematical analysis on the consensus of our model. Finally, we conduct the experiments  to evaluate our proposed algorithms.  


Solving Soft Clustering Ensemble via k: k:-pparse Discrete Wasserstein Barycenter
Ruizhe Qin'
Mengying Li²
Hu Ding
Schooo of Computer Science and Technology
"Scoool Data Science
University of Science and Technology of China
red468mail, wwt.tu.t..........eee edu. en, limengy@mail. uutc. wuttc.eu..co edu.cn, hudingoustc. edu cn
Abstract
Clustering ensemble one of the most important problems in ensemble learning. Though it has been extensively studied in the past decades, the existing methods often suffer from the issues like high computational complexity and the difficulty on understanding the consensus. In this paper, we study the more general soft clustering ensemble problem where each individual solution is soft clustering. We connect it to the well-known discrete Wasserstein barycenter problem in geometry. Based on some novel geometric insights in high dimensions. we propose the sampling-basee algorithms with provable quality guarantees. We also provide the systematical analysis sis on the consensus of model. Finally, we conduct the experiments to evaluate our proposed algorithms.
1 Introduction
Clustering is fundamental topic that has important applications in various areas, such as data mining, networking, and bioinformatics 34 In the past decades, number of different clustering objectives and algorithms have been proposed. For example, the popular k-means aims to partition the given
data set into & clusters and minimize the average squared distance from the input data the set of cluster centers; the well known k-means clustering algorithms include the Lloyd's 's algorithm [47]
k-means++ (5), and local search 36 Other clustering objectives, like hierarchical clustering (49
and density-based clustering [3 are also widely used in practice.
Obviously, different clustering algorithms obtain different results. Moreover, for the same clustering algorithm (e.g., the Lloyd's algorithm), the initialization and data preprocessing (e.g., random projection [12 steps may yield different clustering results. Therefore, natural idea is to aggregate these different clustering results so as to achieve a more reliable result. The problem is called clustering ensemble (also termed clustering aggregation consensus clustering) [27].
However, the current methods still suffer from several issues in theory and practice. Most of existing clustering ensemble methods rely complicated optimization models, such the correlation clustering (28), graph partition [25), semi-definite programming [54), matrix completion [63], and spectral clustering [56]; these optimization problems usually have super- super-linear complexities and thus cannot be efficiently solved for large-scale datasets. Though several heuristic ideas have been proposed for speeding up the computation (e.g., the sampling idea proposed in [61]), they are in lack of rigorous theoretical analysis on their quality guarantees.
Another issue is about the interpretability of consensus. A large number of clustering ensemble models are based on utility function [57]
60 or co-association matrix [26] (5)). From the theoretical perspective, a fundamental question is why these models can yield the final clusterings close to
"Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the ground problem before [T3]. However, the analysis for clustering ensemble is more challenging, because we need to take into account the matchings between different clustering solutions.
-ouuth truth clustering. The similar consensus question was also studied for the classification
1.1 Our Contributions
In this paper, we focus on the more general soft clustering ensemble problem, where each given individual clustering is a soft clustering (also referred to as fuzzy clustering) [[]]. In soft clustering, data points can potentially belong to multiple clusters. For example, a point may be assigned to three clusters with the probabilities 10%, 20%, and 70%, respectively. Compared with hard clustering, soft clustering can provide more realistic and accurate clustering results in many real-
world applications [
They showed that clustering ensemble can be naturally formulated a "geometric prototype" problem. But their results are in lack of systematically studies on the efficiency of this model, especially from the theoretical perspective. In this paper, we illustrate that the geometric prototype actually is equivalent with an instance of Discrete Wasserstein Barycenter (DWB) [ in high dimensions (the formal definition will be given in Section This approach falls under the umbrella of utility function based model, where it uses discrete Wasserstein distance to measure the difference between two clusterings. Compared with other utility functions (e.g.. KL-divveggence, it has several attractive properties. For example, the discrete Wasserstein distance is symmetric and more robust to noise [42]. More importantly, the DWB based ensemble model can be easily interpreted from the geometric perspective, and thus we can analyze its performance more conveniently. But when applying the DWB model to the soft clustering ensemble problem, we still have several key issues remaining to be solved.
We adopt the geometric model that was studied in 18
(i) Though a number of DWB algorithms have been developed (as shown in Section 1.2] the clustering ensemble imposes two unique features to the DWB formulation. First, we require the returned DWB to be k-sparse, that is, it should be supported by at most & points in the space (since there are at most It clusters). Also, the number of different clustering solutions can be large in practical scenarios. For instance, to guarantee the consistency of the final ensemble solution to the ground-truth clustering, we may generate a large number of clustering solutions via random initializations or random projections (24). So from the algorithmic perspective, natural question is whether we can develop more efficient algorithm for the DWB problem with such features?
(ii) To the best of our knowledge, only Topchy et al. (58) and Jain (35 discussed the consensus of clustering ensemble in theory. However, both of their analyses rely on the assumption that the ground-truth clustering should be the optimal solution of the ensemble model, which is too strong and may not be realistic practice. Also, the analysis of (58] only considered hard clustering. worth noting that the number of hard clusterings on a fixed set of items is finite, but the number of soft clusterings is infinity.
In this paper, we focus on these two issues. First, based on some novel geometric insights, we show that it is possible to achieve fixedl-arameter algorithm for the soft clustering ensemble problem if k is a constant, where the obtained approximation factor is + with being any small number in (0, 1); though this is more a theoretical result, we believe that it of independent interest for such combinatorial optimization problem in high dimensions [17]. Moreover, the proposed sampling idea inspires our following speedup for the existing DWB algorithms with provable quality guarantee, even if l is large. Second, we prove that the obtained DWB should be close to the ground-truth clustering if the number of given clustering solutions is large enough. Our idea is quite different from [58 35 in particular, our analysis yields a detailed quantitive result for the consensus.
1.2 Related Works
Clustering ensemble. Clustering ensemble was introduced by Strehl and Ghosh 55 where they formulated it as two different graph partitioning problems; one is "Instance-Baac Based Graph Formulation (IBGF)", and the other is "Cluster- Based Graph Formulation (CBGF)". Fern and Brodley [25] later proposed hybrid graph partitioning model for clustering ensemble. Most existing clustering ensemble models can be roughly divided into utility function based 57
61 6 and co-association
matrix based [26 |6 56). The utility function based model is to find the final clustering result via
maximizing the total similarities to the set of given clusterings. A co-association matrix is actually

---

a new representation of the data items, where each entry of the matrix indicates the similarity of a pair of data items based on the information from the given clusterings. The soft clustering ensemble problem was particularly studied in [5T 61 For more detailed discussion about ensemble clustering.
the reader is referred to the survey 27
Wasserstein distance. The Wasserstein distance is defined for measuring the difference between Iwo probability distributions; if their supports are both discrete sets, the distance called discrete Wasserstein distance (or Earth Mover's distance) (59] 52 Computing the discrete Wasserstein
distance actually equivalent to solving a min-cost max flow problem 22 17 Several more efficient
discrete Wasserstein distance algorithms were proposed, such as 45 50 In the community of
machine learning. Cuturi [15] proposed new objective called "Sinkhorn Distance" that smoothes the transportation problem with an entropic regularization term, and it can be solved much faster than computing the exact discrete Wasserstein distance. Following Cuturi's work, several improved 48).
Sinkhorn algorithms have been proposed in recent years [23
Wasserstein barycenter. If there are m 2 different weighted point sets, the problem of discrete Wasserstein barycenter is to compute the average pattern that minimizes the total Wasserstein distances to them M. The recent algorithms for computing Wasserstein barycenter include 16
7
29 62
8 4 43). The computational complexity of Wasserstein barycenter was studied in 39 43)
Recently, Dognin et al. [21] applied the Wasserstein barycenter based ensemble method to solve several supervised learning problems.
2
Preliminaries
We always use A {a,, '2.-.. .nn to denote the set of n data items which we want to cluster. Definition 1 (Soft Clustering). Let k E Zt. A k-soft clustering of A can be represented by a set of k vectors {S S.) C [0, 1]", where each vector S represents an individual cluster and Σn=1 Sy is equal to the row vector [1, 1,,,,....11 Suppose Sj is the 1-th entry of Sj for 1 S I S n. Then, for fixed I, the set {Su,... ... ,Sa indicates the degrees of membership of ai to the l clusters.
For example, suppose
and k 2; the following k-soft clustering of A: C = {Si [0.1, 0.3, 0. = [0.9. 0.7, 0.2]} (e.g., the item d2 belongs to the first and second clusters with probability 30% and 70%, respectively).
In Definition]] D if we restrict each S, to be binary vector, the clustering C will be a hard clustering. Also, if a clustering C has k' < k clusters, we can simply add k k dummy clusters where each dummy cluster is just a zero vector [0,0,.... ,0.
Following the idea of 18 6 20 we define the function A to measure the difference between two clusterings of A. Suppose C = {S .S} and C" {
S are two different soft clusterings. We build the bipartite graph G from C and C" as follows: each of the two columns of G contains & vertices corresponding to the k clusters in C and C' respectively; for any pair of clusters (S,.Sy) with Sy C and Sj, C', there is edge connecting their corresponding vertices in G with weight equal to their squared Euclidean distance ||S, - 112. Then, the difference of C and i... ACC, C"), is the cost of the minimum weight bipartite matching of G. The function A can be computed through the Hungarian algorithm [14]. Assume the minimum weight bipartite matching between C and C' yields the permutation x of {1, 2, ... ,k). Namely,
A(C,C') = Σ ||s - P.
F=1
Obviously, if ACC, C') = 0. they should be the same clustering solution (the i clusters of C is just reordered by π in C'). To see the rationale behind ( we can imagine the case that and C' are both hard clusterings, i.e., each Sy E C (resp., Sy. " binary vector; so each such vector can be viewed as a subset of (e.g.. S, represents the set {aj aa E A and Sy1- = 13). It is easy to know the symmetric difference of S, and Sy.. [S, S + ISy SSy). is equal to ||S - Sy Therefore, computing the function ACC, C") in fact is to find the matching of C and C' that minimizes their total symmetric differences.
Following Definition I then introduce "soft clustering ensemble" below.
3

---

Definition 2 (Soft Clustering Ensemble (SCE)), Given m different soft clusterings Ci,... Cm of A, the problem of soft clustering ensemble (SCE) is to find the final soft clustering C that minimizes the objective finction
Σ ACC.C.. ==1
(2)
For any soft clustering C and X 2 1, if achieves an objective value no larger than times the minimum value of (2) say it is ">-approximation" for the SCE problem.
Let æ, be the permutation between Ć and C; for 1 S To minimize the objective function 2). the major challenge is to find these m permutations simultaneously. Suppose each C, = {5 ,K. Once these m permutations obtained, the set , C2 is divided into l parts:
( (T)) T. STh (1 isisk
(3)
If let the optimal solution é be -.,,... Se), from the objective function (2 it is easy know these k soft clusters should be the means of these parts, i.e.
5
1 m
5) - m Σ
5
St R.)) sissk.
This simple fact will be used in the analysis in our paper. We also have the following hardness result for SCE through the reduction from the NP-hard three-dimensional assignment problem [41
Theorem (The hardness). When m 2 3, optimizing the SCE objective (2) is NP-hard.
The rest of the paper is organized follows. In Section 3 discuss the relation between the SCE problem and discrete Wasserstein barycenter. In Section we present our approximation algorithms based random sampling. In Section 5 analyze the consensus of the SCE problem under Definition 2 limit, leave some proofs and the detailed experimental results the full version of this paper.
Finally, we illustrate our experimental results in Section 6 Due to the space
3 Relation With Discrete Wasserstein Barycenter
We introduce the relation between SCE and discrete Wasserstein barycenter in this section.
Definition (Discrete Wasserstein Distance [52)). Let P = (pi.P2,"'' and Q (q) 92, ... ... gnq) } be two sets of weighted points in Rd with nonnegative weights as and B, for each P. E P and qÿ E Q, and Die, a = Ei= 35 = 1. Their discrete Wasserstein distance is
np no
W. Q) min
Sullp: 4i113.
where || Ilss indicates the Ig-norm and F = {ffs 1 < is np, 1ip,,sis no} is a feasible flow from P to Q, i.e. each Jij 2 0, up Jij = By, and Ej Sij = 04.
In this paper, we only focus on the l2- lz-discrete Wasserstein distance. The lg-discrete Wasserstein barycenter (DWB2) considers the following objective. Given the nonnegative weighted point sets {Pi, P2.... ... Pm in Rdd, where each P, has the total weights equal to 1, the goal is to find a set of centroid points P. so as to minimize
Y2
(P..P.
(6)
m
Further, if we require P to have most & points with some & E Z+, the problem is called "k-sparse DWB2" (Л]] easy to observe that the k-sparse DWB2 problem very similar to SCE as described in Definition Intuitively, the obtained optimal ensemble clustering Ć can be viewed as the k-sparse DWB2, if each point of C, is assigned the weight 1/k for < m.

---

Theorem 2.
Given set of soft clusterings (C1.... C.mb the optimal solution of the SCE problem 2 exactly their optimal k-sparse DWB,. Moreover, for any 1, X-approximation of the k-sparse DWB2 can yield a X-approximate solution of 2
To prove the above theorem, we need to consider two issues. First, the discrete Wasserstein distance result in many-to-man matching between C and C, but the difference function ACĆ, C,) requires a one-to-one matching. Since the discrete Wasserstein distance is actually an instance of the min-cost max flow problem, we can convert the obtained many-to-many matching to a one-to-one matching without increasing the complexity. Second, we should further prove that the obtained (optimal or approximate) k-sparse DWB2 is a feasible soft clustering (i.e., it should satisfy the conditions described in Definition I)
of Definition may may
4 Approximation Algorithms
Due to Theorem [ we only focus on the approximation algorithms for SCE. is also worth noting that when m 2. the optimal k-sparse DWB, (and the SCE solution) can be easily obtained by computing the matching between C1 and C2; the optimal barycenter should just be the midpoints of the k matched pairs. In this section, we propose the approximation algorithms for optimizing the SCE objective 2 with m 2.
First, we present the following lemma which is the key to our algorithms. Given a point set Q C Rdd v²() and Var(Q) to denote the mean and variance respectively, Le., p(Q) क Ene ?
and Var (Q) [Q] EgeQ llg p(Q))??.
Lemma 1. 33 Let (0, Given a point set Q, suppose that Q' is a of points sampled from Q uniformly at random. Then with probability - 6, [[( =² S 1 Var(Q).
ot
Remark 1. Lemma reveals that we estimate p(Q) by just simple random sampling. For example, if we require the error no larger than eVar (Q) with some small e > 0, we only need to sample &e points from Q and the success probability is 1 6. Obviously, the smaller and ö, the larger the required sample size. Moreover, a highlight of Lemma 7 is that the sample size is independent of the dimensionality.
We also need the following lemma from 40
Lemma 2 indicates that if point p is close to (Q)).
the total squared distances to the points of Q should be close to Var (Q) as well.
Lemma 2. Let Q be a set of points in TRd. For any point p E RRd, T Egeq lla p| Var(Q)
(Ia(()) p11
In Section 4.1 propose fixed-parameter algorithm that returns is assumed to be small. Though it is more a theoretical result, the proposed sampling idea inspires
-)approxii solution, if
our following improvement in Section 4.2 on the existing alternating minimization algorithms for the case that k is not a constant.
4.1 A Fixed- -aremm-e Algorithm
When k is small, we can achieve (1 + e)- approximation for the SCE problem. We briefly illus- trate our idea below.
S.0
[0.07
6.73
0.20
[0.54
0.30 ... 0.65]
For ease of presentation, we "temporarily" assume the permutations ग; between Ć and C,, 1 < i S m, which yield the optimal solution of (2). are given at this moment. For each C₁, concatenate its k vectors (S ... S to be a long vector
[005
0.07
0.03]
[007 6.7
800]
Saa
S
6 (5) St (M))
Figure I: An illustration for the vector U..
in kn See Figure for an illustration. Meanwhile,
the ensemble clustering Č (Si,... ,S.) can be also represented as vector
i -= (8) ... .5)))
(8)
5

---

CiC, Let be the one Algorithm 1 (1 + A-pprrxiiattt SCE Algorithm
Input: m k-soft clusterings C2,,Co,. ... CC on a set A of n data items, and two parameters
6, S 1.
Select = 1 clusterings uniformly at random, and denote them by Ct Ciys C.., For 1 3 C, contains & vectors (i.e., soft clusters) (S 5 in [0, 1|".
2. Initiate a candidate set G Ø.
3. For each C S 1 S I, enumerate all the k! possible permutations for ni, (so there are (ks)) cases in total). For each case:
(a) Let C S2. Sk], where each
Sj = Σ
Sh my (3) =,,,,....
(b) Update G = G U [C}.
4. For each candidate C E G, compute the objective value 1 with the smallest objective value among G. Output: as the final solution.
in R We show that ē in fact is the mean of {oi.... Um) Then we can apply Lemma to estimate the position of ē. Finally, since & is assumed to be a constant, we can enumerate all the the final solution. Though
possible permutations of the sampled clusterings and choose the best Theorem iss more a theoretical result, we believe that it is of independent interest as a fixed-parameter solution for such combinatorial optimization problem in high dimensions.
Theorem 3. (i) With probability 1 - 6, Algorithm 7 vields (1 + c) -approximatee solution of the SCE problem. (ii The runtime is (eexp( de k log k) - mn)
Proof. First, we need to show that each candidate C E G is feasible soft clustering, that is, its k vectors {S..... ,S}} generated in Step 3(a) should satisfy the conditions of Definition [ Sj = -1E may (f)*
Since each
5 it must belong to [0, 1]". Also,
S 1=1
S S.,00 = [1, 111.,...1111 1].
t
1=1 j=1
where the final equality comes from the fact that each sampled C, is a feasible soft clustering. Consequently, each candidate from G also a feasible soft clustering.
Now, we consider the induced objective value of the best candidate selected from G. As discussed before (see Figure D. each soft clustering can be converted a long vector in Rd Denote by v; the vector of C,, for S i mt; similarly, denote by ō the vector of the optimal solution C, We use V to denote the set {vi, ..., Um }. Obviously, ē = x(V) (from the fact (4). Since {Ci, Ciy, Ci, are the randomly selected
clusterings from the input, together with Lemma
|
we have
||0 8'122 < cVar(V)
(10)
with probability 1 1-6 8, where 8'= D Ui Since 1 Em ||u - 5'112 Var(V) + 1
(by Lemma 2). the inequality (10) implies
m
1. - 5|| (1 (1 VaarVV)
(11)
7
Hence, 0' is (1 + -)-aprroximate solution of the objective 2 Because we do not know those permutations Rn. < I S t, we cannot directly obtain V.. Through enumerating all the (k:)* cases, can claim that there must exist one candidate in G that yields (1 + -pppppooxiittoonn
The time complexity contains two parts, i.e., constructing GG and selecting the best candidate from G. Since |G| (k!)' O(exp( d k log k)), the first part takes (exxp( oe k log k) t kn) time.

---

For the second part, we use the Hungarian algorithm to compute the one-to-one matching from C. 1 1 < m. each candidate of G. Note that the complexity of the Hungarian algorithm is 0(k-+12-1) O(k2n) ) (n > k), where the term A-2 is due to the time for building the x k bipartite graph IR."". Therefore the second part takes (eexp( be log k) m2)) time. Overall, the second part dominates the whole complexity, and the runtime of Algorithm is O(exp 1 k log k) k2 mn). C
&c
4.2 When Is Not a Constant
Now we consider the case that & is not a constant. Due to the discussion in Section 3 we can directly apply any existing k-sparse DWB2 algorithm to compute the final ensemble clustering. interesting observation is that a couple of widely used DWB2 algorithms follow the alternating minimization framework [16 62 (several previous ensemble clustering algorithms also used this alternating minimization idea [3 20 ): in each iteration, the algorithm alternatively performs the following two
steps:
1. update the matchings (i.e., the Wasserstein flows) from those C,s to the temporary barycenter;
2. update the k points of the temporary barycenter based on the new matchings.
Different algorithms may adopt different strategies for implementing these two steps. Eventually, the result will converge to a local optimum (note it is NP-hard to achieve a global optimum according to Theorem A bottleneck of this framework, especially when m is large, is the computation for the Wasserstein distances over all the clusterings C1. ... Cm In fact, similar to Algorithm | we can still apply Lemma | to reduce the time complexity for this bottleneck. Let č1 be the temporary barycenter at the beginning of the current iteration. Suppose CT is the updated barycenter if we compute all the m Wasserstein distances. Let S c, S 1. If we randomly select 2s clusterings and only compute these 1 Wasserstein distances to update C1 to be CT, we have the following result via the same idea of Theorem
Lemma 3. With probability - 6, Σ A(C+, C.) (1+ E A(CT,C.).
Lemma 3 indicates that we can avoid computing the m Wasserstein distances and still achieve a barycenter close to ČT via random sampling. Note that key difference with Algorithm | is that we do not need enumerate the permutations since the I matchings can be determined by C, ž
Analysis on the Consensus
Denote by Cgt the ground-truth clustering over the data items of A. In this section, analyze the consensus of the objective (2). Specifically, when the number m increases, we are wondering whether the optimal solution C will converge to the ground-truth clustering Cgt. Let Q be the set of all the possible soft clusterings over A. following probability measure p. Namely, for any soft clustering C E Q the probability of obtaining it p(C), and SceaP(C))d P(C)dC 1.
First, we propose the following assumption that there is an upper bound for the difference between Cgz and any Q.
Assumption 1. There exists value L such that ACC, Cat) S for any C e Ω.
Actually, this assumption is easy to understand the context of clustering ensemble. Since each clustering solution C is obtained by some reasonable clustering algorithm, it makes sense to assume that these solutions are not arbitrarily far from Cgt. Assumption| I directly implies the following Lemma which can be proved by the fact ACC, C²) < 2A(C, Cat. (CC)),C
Lemma 4. For any C and C' E Ω C'C,C') < 4L.
As mentioned in Section T.1 to the best of our knowledge, only Topchy et al. (58 and Jain 35 discussed the consensus of clustering ensemble in theory. However, both of their analyses need the assumption that the ground-truth clustering should be exactly the one achieving the smallest expected objective value over all the possible clustering solutions:
Czt = arg min / ((C)A(C,C)ac,
(12)
ČER
7

---

which may be too strong in reality. Also, they did not provide the quantitive analysis, e.g., the numerical relation between the convergence and the value m. Here, we relax the assumption (I2) In particular, we allow Cgt # arg min Jo (C, solution that achieves sufficiently low expected objective value, should be close to Cgt. Let Opt mingen So ((C) C'dC, and Copt be the clustering solution that achieves Opt. Note that Copt and Cg: are not necessary to be the same one, and our ultimate goal is to find a solution close to Cgt.
We instead assume any clustering
Assumption& 2. There exist two numbers c, 2 O. such that for any E Ω if its expected objective value Jn (A,))(C,,,CCo S (1 + c)tpt, we have ((C,Cg.) S.
Obviously, when c = { = O, Assumption 2 will be as same as the assumption 12 from 58 So our assumption more relaxed. We also need to point out that the objective (2) (and the k-sparse Wasserstein barycenter) may have multiple isolated global optimums. But under Assumption we restrict 5 local region and thus is reasonable to assume Assumption 2 to be true.
To begin analyzing the consensus, we fix clustering Ć E Ω first. We let x; A(Ć, C,) for i= 1,2, ... m, and view each x; as an independent random variable. Then, we denote their mean 1-1 Ti as T. Obviously, E[a] Jg (CC)A(C, C)dC. We then study the difference between T and E[a]. From Lemma we know z; E [0, 4L] for S S m. Through the Hoeffding's 's inequality [30],
m
for any 7) >> O we have
may ( (E()))
Prob
[ - E
[
2 exp(
21
Consequently, we have the following Lemma.
Lemma 5. Fix ê E Ω For any n, 8 E (0,1), if m 2
81,2
log 3. with probability 1 8,
(F(a)>
1 DE 1= A(C,C,) E (1 Sn (CC)A(C,
But Lemma 5 is only for a fixed č. We need to extend the Lemma to any é E Ω. To realize this goal, discretize the set f2 first.
Discretization. We use B(p,r) r) to denote the ball centered at a point p with radius 2 in R", We suppose the & soft clusters (i.e., the & vectors in I²") of Cge are Ig., Sgt, From Assumption I we know for each é E Ω2 its vectors should be covered by the region R ش ((S VL). à Imagine that we draw uniform grid inside R with the grid side length being equal to vn (the value of & will be determine later). Thus, for any two points inside the same cell of the grid, their distance no larger than Vn (0/vn)² O. Moreover, by using the formula for ball volume in R", know the size of J which denotes the set of the grid points inside B(S vD), is O
So the set Ogeia I'1 I12 x I's contains N = =0(( VxeL
different k-tuple points (i.e., soft clusterings). If we replace 5 by 5/N in Lemma 5 and take the union bound over all the soft clusterings of Sgridd we can obtain the following result.
y
Lemma 6. For any 7 E (0,1), if m 2 o( knt (Optp
log 4x), with probability 6,
L EE 1 A(C,C)) E (1 In ((C) C)dC for any &&gria-
Remark 2. We replace E [E] by Opt in the lower bound of m in Lemma 6 since [[ is always no smaller than Opt.
Now, we consider the clusterings in Ω \ A.gria- For each point p E R, we use N(()) to denote its nearest grid point. Similarly, for any = {SI.... S& E Q Sgria, we denote its "nearest clustering" as (C), which contains the & vectors (A(S)), (.()),,.-,((SSu))) We should prove that (AN(C)) C) ACC, C) small for any C E Ω. as long as 0 sufficiently small. Consequently, we can extend the result of Lemma 6 from Pgria to all the clusterings in S2.
Lemma 7. For any n E (0,1), if m 2 O(
RL) with probability 8, (Opt))= log nodp=): 1 E - A(C,C)) (1 7m) PCC))(C C)CC for any Ć E Ω.
8

---

The value of i is set to be n-Opt in the proof of Lemma (the detailed proof is placed to our full VSKL paper). Finally, we achieve the consensus theorem under Assumption T and 2
Theorem 4 (Consensus). Let d E 10 and < 7(2+c)' Suppose (C1,"" ,Cm) are drawn i.i.d kL
from St with the probability p()). If m 2 ( knL? log ndDpe). with probability 1 6, A(C, Cge) is
(/pp)))
no larger than & where Ć is the optimal solution for the objective 2
Proof. Suppose ACĆ, Cgt) > &. From Assumption
2
we know Sa (CC) (1 c)0pt.
which implies
Σ (1- (1))
(13)
via Lemma Moreover, by using Lemma again, we have
m (CCopt, C.) $ (1 7n)0pt.
(14)
Since we let 1) < 7(2+c)* 13 and 14) together imply 1 E. ACCopt Ci)
- ACC, C.).
i==
m which is contradict with the fact that C is the optimal solution for the objective ( inequality ACC, Cge) I f is true.
m
Hence the
6 Experimental Results
We evaluate the practical performance of our proposed algorithm in this section, All the experimental results were obtained on server equipped with 2.8GHz Intel CPU, 8GB main memory, and Matlab 2019a. We consider three real datasets: USPS has 11000 data items in 2256 with k 10 [32];
IRIS [22] has 150 data items R with 3; CIFAR- 10 33 has 10000 data items in R-3072 with k = 10. Similar with 24 [3,, we apply random projections to generate the clustering solutions (in each random subspace, we use k-means to cluster the data). We consider two representative baselines: the bipartite graph partition method BGP [25]: the top-down method FURTHEST (28). Our sampling idea of Section 4.. is incorporated into the alternating minimization Wasserstein barycenter algorithm [62], which is denoted as AM-r with r representing the sample rate (e.g., AM-1 means we
directly run the algorithm on the original data without sampling).
We set m = 1000 (i.e., the number of generated clustering solutions for ensemble) and show the results in Figure 2 (a)-(i). We can see our Wasserstein barycenter based algorithm significantly outperforms other baselines in terms of the objective value 2 the Wasserstein distance to ground truth, and the runtime on the datasets USPS and CIFAR- 10. Only for the smallest dataset IRIS, the baselines are faster (actually all the runtimes are very close for this small dataset). Also, we study the convergence of our obtained result, iee, Wasserstein distance to the ground-truth clustering as m increases, in Figure (i)-(l). (I- We can see in general the convergence performs better when the sample rate is larger. Due the space limit, we leave the detailed experimental results to our full paper.
Conclusion and Future Work
In this paper, we connect the soft clustering ensemble problem to k-sparse discrete Wasserstein barycenter. There are several interesting problems deserved to study in future. For example, the robustness of the Wasserstein barycenter based clustering ensemble is in lack of discussions so far. In particular, we can consider its robustness under adversarial attacks, e.g., the poisoning and evasion attacks (10). Also, believe it is important to study some other relevant issues, egg,, the privacy-preserving problem and the fairness problem, for clustering ensemble.

---

USPS
Iris
1.5
Olbective Valne
1.2
1.0
8.8
0.1
0.0
AMX- AMA43 AX-45 A061 Nabol
AMAL AMA-L AMALS Packol 0
0.0
AMALI AN-- AN-- AMVLS AM61
SUT Neko
Mathods
Michods
Mathods
(a)
(b)
(c)
Wooorra Douxeero
Whoerreen Distense
1.5
30-
1.2
1.0-
0.8
10
0.4
Methods
Mathods
Methods
(d)
(e)
(f)
USPS
0.8
lris
Cifie
Brotoee:-1100 00
Runtimots"
0.6
XM6I1 AMEEY AMERS AM.
ICF Farked
0.0
3MTTT ACGES AMI Ferher
AKCI3 AMGES AMT
IP Fateo
Methods
Mathods
(g)
(h)
(i)
Wokcoen dotuae (0))
USPS
20
Wommrsnn dettree
AM--1
10
AM-1
AM-1
10
1.5
Log
Log
Log
(i)
(k)
Figure 2: The objective values (the first line), the Wasserstein distance ground truth (the second line), the runtimes (the third line), and the convergence (the third line) on the datasets. All the results averaged across 30 trials.
Acknowledgment
We would like to thank the anonymous reviewers for their helpful suggestions and comments.
References
[1] M. Agueh and G. Carlier. Barycenters in the wasserstein space. SIAM Math. Anal., 43(2):904 924, 2011.
[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applica- tions. Prentice Hall, 1993.
[3] J. Altschuler, F. Bach, A. Rudi, and J. Niles-Weed. Massively scalable sinkhorn distances via the nyström method. In Advances in Neural Information Processing Systems, pages 2019.
[4] Anderes, S. Borgwardt, and Miller. Discrete wasserstein barycenters: optimal transport for discrete data. Math. Methods Oper. Res., 84(2):389-409) 2016.
10

---

[5] D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027-1035. Society for Industrial and Applied Mathematics, 2007.
[6] M. Balcan, A. Blum, and A. Gupta. Clustering under approximation stability. J. ACM, 60(2):8:1- 8:34, 2013.
[7] M. Baum, K. Peter, D. Uwe, et al. On wasserstein barycenters and mmospa estimation. IEEE Signal Processing Letters, 22(10):511-1111, 2015.
[8] J. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré. Iterative bregman projections for regularized transportation problems. SIAM Scientific Computing, 37(2), 2015.
[9] C. Bezdek, Pattern Recognition with Fuezy Objective Function Algorithms. Springer, 1981.
[10] B. Biggio and F. Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognition, 84:317-331, 2018. 2018.
[11] Borgwardt and Patterson. On the computational complexity of finding a sparse wasserstein barycenter. CoRR, abs/1910.07568. 2019.
[12] C. Boutsidis, A. Zouzias, M. W. Mahoney, and P. Drineas. Randomized dimensionality reduction for k-means clustering. IEEE Trans. Inf. Theory, 61425:0045 2015.
[13] T. I. Cannings and R. J. Samworth. Random-projection ensemble classification. Journal of the Royal Statistical Society Series B, 7944)9959-1035, 2017.
[14] T. H. Cormen, C. R. Leiserson, R. L., Rivest, and C. Stein. Introduction to Algorithms (Second Edition). DBLP, 2001.
[15] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States., pages 2292-2300, 2013.
[16] M. Cuturi and A. Doucet. Fast computation of wasserstein barycenters. In International Conference on Machine Learning, pages 685-693, 2014.
[17] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorrrih Springer, 2015.
[18] E. Dimitriadou, Weingessel, and K. Hornik. A combination scheme for fuzzy clustering. In N. R. Pal and M. Sugeno, editors, Advances in Soft Computing AFSS 2002, 2002 AFSS International Conference on Fuzzy Systems. Calcutta, India, February 3-6. 2002, Proceedings. volume 2275 of Lecture Notes in Computer Science, pages 332-338. Springer, 2002.
[19] H. Ding and M. Liu. On geometric prototype and applications. In Y. Azar, H. Bast, and G. Herman, editors, 26th Annual European Symposium Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of L.Plcs, pages 23:1-23:15. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018
[20] H. Ding, L. Su, and J. Xu. Towards distributed ensemble clustering for networked sensing systems: a novel geometric approach. In F. Dressler and M. auf der Heide, editors, Proceed- ings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2016, Puderborn, Germany, July 4-8, 2016, pages 1-10. ACM, 2016.
[21] L. Dognin, I. Melnyk, Y. Mroueh, J. Ross, C. N. dos Santos, and T. Sercu. Wasserstein barycenter model ensembling. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[22] D. Dua and C. Graff. UCI machine learning repository, 2017.

---

[23] P. E. Dvurechensky, A. V. Gasnikov, and A. Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent better than by sinkhorm's 's algorithm. In G. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML. 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1366-1375 PMLR, 2018
[24] X. Z. Fern and C. E. Brodley. Random projection for high dimensional data clustering: A cluster ensemble approach. In T. Fawcett and N. Mishra, editors, Machine Learning. Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 193, AAAI Press, 2003.
[25] X. Z. Femn and C. E. Brodley. Solving cluster ensemble problems by bipartite graph partitioning. E. Brodley, editor, Machine Learning, Proceedings of the Twenty-first International Con- ference (ICML 2004), Banff. Alberta, Canada, July 4-8, 2004, volume 69 of ACM International Conference Proceeding Series. ACM, 2004.
[26] A. L. N. Fred and A. K. Jain. Combining multiple clusterings using evidence accumulation. IEEE Trans. Pattern Anal. Mach. Intell., 27(6)) 2005.
[27] Ghosh and A. Acharya. Cluster ensembles: Theory and applications. In Data Clustering: Algorithms and Applications, pages 551-570. 2013.
[28] A. Gionis, H. Mannila, and P. Tsaparas. Clustering aggregation. ACM Trans. Knowl. Discov. Data, 1(1):4, 2007.
[29] A. Gramfort, G. Peyré, and M. Cuturi. Fast optimal transport averaging of neuroimaging data. In International Conference on Information Processing in Medical Imaging, pages 261-272. Springer, 2015.
[30] W. Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages 409-426. Springer, 1994.
[31] K. Hornik and W. Böhm. Hard and soft euclidean consensus partitions. In C. Preisach, H. Burkhardt, L. Schmidt Thiemm, and R. Decker, editors, Data Analysis, Machine Learning and Applications Proceedings of the 31st Annual Conference of the Gesellschaft für Klassifikation V., Alberr-Ludwigs- Senddiig-Uniivrsittae Universität Freiburg. March 7-9, 2007, Studies in Classification, Data Analysis, and Knowledge Organization, pages 147-154. Springer, 2007.
[32] J. Hull. A database for handwritten text recognition research. IEEE Trans. Pattern Anal. Mach. Intell., 16(5):550-555 5544, 1994.
[33] M. Inaba, N. Katoh, and H. Imai. Applications of weighted voronoi diagrams and randomization variance-based k-clustering (extended abstract). In Mehlhorn, editor, Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, USA, June 6-8, 1994, pages 332-339. ACM, 1994.
[34] A. K. Jain. Data clustering: 50 years beyond k-means. Pattern Recognit. Lett., 31(8):651-666 2010.
[35] B. J. Jain. Consistency of mean partitions in consensus clustering. Pattern Recognit., 71:26-35, 2017.
[36] T. Kanungo, D. M. Mount, N. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. local search approximation algorithm for k-means clustering. In Proceedings of the eighteenth anmual symposium on Computational geometry, pages 10-18. ACM, 2002.
[37] A. B. Khesin, A. Nikolov, and D. Paramonov. Preconditioning for the geometric transportation problem. In 35th International Symposium on Computational Geometry, pages 15:1-15:14, 2019.
[38] A. Krizhevsky, Learning multiple layers of features from tiny images. 2009.
12

---

[39] A. Kroshnin, N. Tupitsa, D. Dvinskikh, P. E. Dvurechensky, A. Gasnikov, and C. A. Uribe. On the complexity of approximating wasserstein barycenters. K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3530-3540. PMLR, 2019.
[40] A. Kumar, Y. Sabharwal, and S. Sen. A simple linear time (1+))-approxima) algorithm for k-means clustering in any dimensions. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 3344622. IEEE Computer Society, 2004.
[41] Y. Kuroki and T. Matsui. An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors. Discret. Appl. Math., 157(9):2124-2) 2135, 2009.
[42] E. Levina and P. J. Bickel. The earth mover's distance is the mallows distance: Some insights from statistics. In Proceedings of the Eighth International Conference On Computer Vision (ICCV-0I), Vancouver, British Columbia, Canada, July 7-14, 2001 Volume 2, pages 251-256 IEEE Computer Society, 2001.
[43] T. Lin, N. Ho, X. Chen, M. Cuturi, and M. I. Jordan. Fixed-support wasserstein barycenters: Computational hardness and fast algorithm. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[44] T. Lin, N. Ho, and M. I. Jordan. On efficient optimal transport: An analysis of greedy and accelcrated mirror descent algorithms. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3982 1991. PMLR, 2019.
[45] H. Ling and K. Okada. An efficient earth mover's distance algorithm for robust histogram comparison. IEEE transactions on pattern analysis and machine intelligence, 29(5):840-833, 2007.
[46] H. Liu, T. Liu, J. Wu, D. Tao, and Y. Fu. Spectral ensemble clustering. In L. Cao. C. Zhang, T. Joachims, G. I. Webb, D. D. Margineantu, and G. Williams, editors, Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Sydney, NSW, Australia, August 10-13, 2015, pages 715-724. ACM, 2015.
[47] S. Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 2892):129-137, 1982.
[48] B. Muzellec and M. Cuturi. Subspace detours: Building transport plans that optimal on subspace projections. In Annual Conference on Neural Information Processing Systems, pages 6914-6925, 2019.
[49] F. Nielsen. Chapter 8: Hierarchical clustering. In Introduction HPC with MPI for Data Science. Springer, 2016.
[50] O. Pele and M. Werman. Fast and robust earth mover's distances. In Computer vision, 2009 IEEE 12th international conference on, pages 460 467. IEEE, 2009.
[51] K. Punera and J. Ghosh. Consensus based ensembles of soft clusterings. In H. R. Arabnia, M. Dehmer, F. Etmert-Streib, and M. Q. Yang, editors, Proceedings of the 2007 International Conference Machine Learning: Models, Technologies & Applications, MLMTA 2007, June 25-28, 2007, Las Vegas Nevada, USA, pages 3-9. CSREA Press, 2007.
[52] Y. Rubner, C. Tomasi, and L. J. Guibas. The earth mover's 's distance as a metric for image retrieval. International journal of computer vision, 40(2):99-121, 2000.
[53] J. Sander, M. Ester, H.-P. Kriegel, and X. Xu. Density-based clustering in spatial databases: The algorithm gdbssaan and its applications. Data mining and knowledge discovery, 2(2):169 199-14999 1998.
13

---

[54] V. Singh, L. Mukherjee. J. Peng, and J. Xu. Ensemble clustering using semidefinite programming with applications. Mach. Learn., 79(1-2):177-200, 2010.
[55] A. Strehl and J. Ghosh. Cluster ensembles-a knowledge reuse framework for combining partitionings. In AAAI/IAA,, pages 93-99, 2002.
[56] Z. Tao, H. Liu, S. Li, Z. Ding, and Y. Fu. Robust spectral ensemble clustering via rank minimization. ACM Trans. Knowl. Discov. Data, 13(1):4:1-4:22 2019.
[57] A. P. Topchy, A. K. Jain, and W. F. Punch. Clustering ensembles: Models of consensus and weak partitions. JEEE Trans. Pattern Anal. Mach. Intell., 27(12):186--181 2005.
[58] A. Topchy, M. C. Law, A. K. Jain, and N. Fred. Analysis of consensus partition in cluster ensemble. In Proceedings of the 4th IEEE International Conference on Data Mining (ICDM 2004), 1-4 November 2004, Brighton, UK, pages 225-232. IEEE Computer Society, 2004.
[59] C. Villani. Topics in optimal transportation. American Mathematical Society, 58, 2008.
[60] J. Wu, H. Liu, H. Xiong, J. Cao, and J. Chen. K-means-based consensus clustering: A unified view. IEEE Trans. Knowl. Data Eng., 27(1):155-115 2015.
[61] J. Wu, Z. Wu, J. Cao, H. Liu, G. Chen, and Y. Zhang. Fuzzy consensus clustering with applications on big data. IEEE Trans. Fuzzy Syst., 2566):1430-1445, 2017.
[62] Ye, P. Wu. J. Z. Wang, and J. Li. Fast discrete distribution clustering using wasserstein barycenter with sparse support. IEEE Trans. Signal Process., 65(9):2317-23322 2017.
[63] J. Yi, T. Yang, R. Jin, A. K. Jain, and M. Mahdavi. Robust ensemble clustering by matrix completion. J. Zaki, A. Siebes, X. Yu, Goethals, G. I. Webb, and Wu, editors, 12th IEEE International Conference on Data Mining, ICDM 2012, Brussels, Belgium, December 10-13, 2012, pages 1176-1181, IEEE Computer Society, 2012.
14


Reviews:
[{"review_id": "iXGYNggwWTY", "reviewer": "Reviewer_jwX5", "summary": "This paper proposes a new approach for soft clustering ensemble, using a new problem formulation (a “geometric prototype”), which is equivalent to a Discrete Wasserstein Barycenter problem.\n\nThe proposed algorithm achieves, with a fixed probability 1 – δ, a (1+ ε)-approximate solution to the soft clustering ensemble problem, when the number of clusters k is fixed and small. As the authors state, this is a theoretical result since the runtime is more than exponential in k, 1/ δ, and 1/ε.\n\nIn addition, the authors propose an improvement on the existing alternating minimization algorithms in the case of k not being a constant. Then, they prove that the obtained solution converges to the ground-truth clustering as the number m of clustering increases.\n\nFinally, they evaluate the performance of the alternating minimization Wasserstein barycenter algorithm with the proposed improvement, and they compare it to three baselines from the literature. The results show that their algorithm outperforms the baselines in terms of the objective function value and, for the largest datasets, also in terms of runtime.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is generally clear and well organized. Occasionally, the writing should be improved, and some small mistakes should be corrected.\n\nThe problem is well described and motivated. However, some claims lack adequate reference, as for instance in lines 128-129, lines 138-139; and Lemma 1 and 2. Even if the online supplement contains additional details, the main paper should be self-contained.\n\nThe main results appear to be an improvement on an existing algorithm, and the proof of the convergence of the solution with m clustering to the ground truth under weaker assumptions and with a quantitative analysis.\n\nThe experimental results are good when compared to the baselines.\n\nA remark: the Discrete Barycenter Problem is NP-hard when the support points of the barycenter are not given or they are not in polynomial size. If the support points of the barycenter are given, problem (6) is not NP-hard, but it is polynomially solvable by Linear Programming, and it can be efficiently solved to optimality also in practice by the barrier algorithm of commercial solvers such as Gurobi (at least for dataset of the size you’re considering), as shown, for example, in \n\n-\tAuricchio, G., Bassetti, F., Gualandi, S. and Veneroni, M., 2019. Computing Wasserstein Barycenters via Linear Programming. In CPAIOR-2019, 355-363. Springer.\n\nQuestions for the authors: are the baselines method selected for the comparison really the state of the art for the (small) datasets you have used in your experiments? Do you have any test where you have the “real” ground truth, and you can really check that with your approach you are able to recover the true optimal clustering? Evaluating the clustering only in terms of the objective function value can be misleading if the objective function is not the best possible to recover the ground truth.\n\nSome comments:\n-\tEquation (5) is wrong: it misses a “^1/s” for the minimal value. If you use s for the norm, maybe is better to use the index p for the power of the norm, and “1/p” for the minimum distance.\n-\tLine 63: that whether; ?\n-\tLine 68: infinity -> infinite\n-\tLine 108: C subset of [0,1]^n is not correct (actually S_j is a subset of [0,1]^n)\n-\tLine 153: formal definition of F is not correct: the conditions on f_ij should be inside the braces\n-\tLine 170: covert -> convert\n-\tSection 4.1: the letter of the dimension of the space changes from d to n\n-\tAlgorithm 1: δ, ε >; 0 (instead of ≥)\n-\tLine 262: that\n-\tLine 264: since ρ is a density, ρ(C) is not the probability of obtaining C\n-\tLine 279: what\n-\tLine 284: necessary to be -> necessarily\n-\tAssumption 2, as it is formulated, is weaker than Assumption 1: it can be easily seen by taking ξ = L. Can it just be removed?\n-\tLine 326: the\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It's ok.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "eAmPyHofze6", "reviewer": "Reviewer_V1Ay", "summary": "Authors connected the soft clustering ensemble and discrete Wasserstein barycenters. They proposed a (1+eps) approximation algorithm and adopted a uniform sampling scheme to reduce the time complexity of computing Wasserstein barycenters. Convergence is proved and verified via experiments. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The connection of Wasserstein barycenters and soft clustering ensemble\n\n+ Solid the mathematical derivation seems; claims in the paper seem to be supported by either proofs or reference.\n\nWeaknesses:\n- Theorem 2 seems a straightforward result of connecting the objectives of DWB and SCE.\n\n- Algorithm 1 is not practical ($k!$ in step 3) and not used in the experiments. Please correct me if I am wrong but I found in the code that alternative optimization for DWB was actually adopted instead. \n\n- The results don't show much improvement for a smaller sampling rate. And in Figure 2, (a-f) I wonder if x-ticks are wrong because they suggest a large rate leads to shorter time but the largest rate AM-1 took the longest time.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "_5Np9rtuPAN", "reviewer": "Reviewer_9VVF", "summary": "This manuscript shows the connection between soft clustering ensemble and the discrete Wasserstein barycenter problem. Based on the connection, a sampling-based algorithm is proposed with some provable quality guarantees. The manuscript provides some theoretical analysis about the quality of the obtained consensus clustering results.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This manuscript shows theoretical analyses of soft clustering ensemble problems. It has been known that clustering ensemble can be formulated as a geometric prototype problem. One of the main contributions of this manuscript is to show that the geometric prototype is actually equivalent with an instance of discrete Wasserstein barycenter (DWB). The explanations about this point and intuitions are well described in the manuscript.\n\nA sampling-based algorithm is proposed with provable quality guarantees based on the connection between the soft clustering ensemble and the discrete Wasserstein barycenter. It has been shown that the obtained DWB can be close to the ground-truth clustering if the number of given clustering solutions is large enough. I did not check all the details about the proofs, but the high-level intuition seems reasonable.\n\nI wonder how the proposed method compares to the following paper if the assignment is assumed to be a hard clustering.\n* Spectral ensemble clustering (KDD 2015) by H. Liu et al.\n\nI might have missed something, but I wonder how the proposed method can achieve better runtime than the other methods in the experiments for $k=10$ (USPS and CIFAR-10 datasets) even though in Algorithm 1, the third step includes computing $k!$ permutations for $\\pi_i$. \n\nIn the experiments, it is stated that \"we apply random projections to generate the clustering solutions (in each random subspace, we use $k$-means to cluster the data).\" More details should be provided to understand this experimental setting clearly. How are the base soft clustering results generated?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Does not apply.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "K_jJP4109Wd", "reviewer": "Reviewer_Jegc", "summary": "This paper studies the ensemble clustering problem with soft clustering indicators. They reveal an interesting equivalence between the soft clustering ensemble problem and the $k$-sparse discrete Wasserstein barycenter. The authors proved the hardness result of SCE and reported approximation algorithms for two different regimes (fixed $k$ or not). On the modeling side, they provided consensus results for the SCE problem under a weaker assumption on the ground-truth clustering set than prior results. They also conducted numerical experiments to support their results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is original and clearly written. The new connection between soft clustering ensemble and $k$-sparse discrete Wasserstein barycenter is interesting, which allows using techniques in DWB literature to solve the SCE problem. Building a bridge between seemingly different tasks is always a good thing, as it may introduce new tools for both problems. Leveraging the new equivalence, the hardness and consensus analysis are reported for the SCE problem by studying the equivalence DWB problem. Approximation algorithms are also provided, though these results are mostly working in theory due to the efficiency issue (see complexity in Theorem 3). So new efficient algorithms for $k$-sparse DWB might be interesting for further research. \n\nOverall, considering the new connection brings fruitful results for the SCE problem, I tend to vote yes for its acceptance.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The algorithm in Section 4 might run slowly in practice due to the number of permutations in the sub-procedure. In Theorem 3, the exponential dependence on $\\frac{1}{\\delta\\epsilon}$ seems not desirable.\n\n* Eq.(3): $W_s(P,Q)$ should be $W_s^s (P,Q)$?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The majority reviewers are in favor of accepting this paper.  The reviewers in general liked the connection made between the soft clustering ensemble problem and discrete Wasserstein barycenter.  The hardness result and convergence analysis rounded out the paper.  However, there was concern about the lack of direct practical implications of the result due to the exponential dependence on the number of centers.


Decision: Accept (Poster)