Fuzzy Clustering with Similarity Queries
Authors: Wasim Huleihel
Arya Mazumdar
Soumyabrata Pal
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fuzzy clustering
oracle
similarity queries
k-means
soft clustering.

Abstract: The fuzzy or soft $k$-means objective is a popular generalization of the well-known $k$-means problem, extending the clustering capability of the $k$-means to datasets that are uncertain, vague and otherwise hard to cluster. In this paper, we propose a semi-supervised active clustering framework, where the learner is allowed to interact with an oracle (domain expert), asking for the similarity between a certain set of chosen items. We study the query and computational complexities of clustering in this framework. We prove that having a few of such similarity queries enables one to get a polynomial-time approximation algorithm to an otherwise conjecturally NP-hard problem. In particular, we provide algorithms for fuzzy clustering in this setting that ask $O(\mathsf{poly}(k)\log n)$ similarity queries and run with polynomial-time-complexity, where $n$ is the number of items. The fuzzy $k$-means objective is nonconvex, with $k$-means as a special case, and is equivalent to some other generic nonconvex problem such as non-negative matrix factorization. The ubiquitous Lloyd-type algorithms (or alternating-minimization algorithms) can get stuck at a local minima. Our results show that by making few similarity queries, the problem becomes easier to solve. Finally, we test our algorithms over real-world datasets, showing their effectiveness in real-world applications. 

Fuzzy Clustering with Similarity Queries
Wasim Huleihel
Arya Mazumdar
Department Electrical Engineering Tel Aviv University
Haltcroglu Data Science Institute University of California, San Diego La Jolla, CA 92093 arya@ucsd. edu
Tel Aviv 6997801, Israel
wasimhStauex. aa i1
Soumyabrata Pal
College of Information & Computer Sciences University of Massachusetts Amherst
Amherst, MA 01003 sounyabratap@umass edu
Abstract
The fuzzy or soft k-means objective is a popular generalization of the well-known k- means problem, extending the clustering capability of the k-means to datasets that are uncertain, vague and otherwise hard to cluster. In this paper, we propose a semi- supervised active clustering framework, where the learner is allowed to interact with an oracle (domain expert), asking for the similarity between certain set of chosen items. We study the query and computational complexities of clustering this framework. We prove that having few of such similarity queries enables one to get a polynomial-time approximation algorithm to an otherwise conjecturally NP-hard problem. In particular, we provide algorithms for fuzzy clustering in this setting that ask (ppoly(k) logn) similarity queries and run with polynomial- time-complexity, where n is the number of items. The fuzzy k-means objective is nonconvex, with h-means as special case, and is equivalent to some other generic nonconvex problem such non-negative matrix factorization. The ubiquitous Lloyd-type algorithms (or alternating-minimizze minimization algorithms) can get stuck at a local minima. Our results show that by making few similarity queries, the problem becomes easier to solve. Finally, we test our algorithms over real-world datasets, showing their effectiveness in real-world applications.
Introduction
The k-means objective for clustering is perhaps the most ubiquitous of all unsupervised learning paradigms. extremely well studied, with Lloyd's algorithm being the most popular solution method, while the problem in general being NP Hard [11, 7]. A variety of approximate solutions for k-means exists (such as, [20, 31).
In recent times, there have been efforts to bring in flavor of active learning in k-means clustering: by allowing the learner make limited number of carefully chosen label/membership queries [4, 2, 18). In this setting, the main objective is to show that polynomial-time solution exists provided that small number of such queries an oracle is permitted. Note that, an alternative to membership query (i.e., query of the form "does the ith element belong to the jth cluster") is the same-cluster/simile query (i.e., "do elements and j belong to the same cluster"). Given representatives from each cluster is available, one can simulate any membership query with at most k same cluster queries. Hence whatever is achievable with membership queries, can be also achieved by same cluster queries by asking at most & times many queries [4].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

How realistic is to allow the learner to make such label queries, and how realistic is the oracle assumption? It turns out that many clustering tasks, primarily entity-reollutin, are being delegated to crowdsourcing models. One can easily assume that the crowd is playing the role of an oracle here. is natural in these models to assign crowd workers with sub-tasks, which can either be answering the membership query or the same cluster query [5, 49, 50, 38, 23].
Fuzzy k-means or soft k-means a generalized model of the k-means objective that covers lot more grounds being applicable to dataset where datapoints show affinity to multiple labels, the clustering criteria are vague and data features are unavailable [8]. In fuzzy clustering. instead of an element being part of one fixed cluster, it is assumed that it has membership value between O and 1 to each of the clusters. The objective of the clustering is to recover all of the membership values for each element or datapoint. This relaxation in membership values from {0, 1] to [0, 1] makes the fuzzy k-means an attractive model for overlapping clusters [52], multilabel classification [30] and numerous other applications such as, pattern recognition [8], computational biology [6], bioinformatics [47], image segmentation [1, 19] and so on.
What is more interesting is that solving fuzzy clustering is equivalent to approximate solution of nonnegative symmetric matrix factorization problems [22]. Given such applications, it somewhat surprising that the theoretical results known about fuzzy clustering is quite limited. As is even the computational tractability of fuzzy k-means is only conjecturally known. In fact algorithmic study of fuzzy k-means algorithm seems to have been only recently started [9. 10, 31].
Membership vs. similarity queries. As mentioned above, in the hard-clustering case, one can simulate any membership query with at most k same-cluster (or, similarity) queries [4]. In fuzzy clustering, we are given set of n vectors (items) in the d-dimeensionl Euclidean space, and we tasked the problem of determining the k-dimensional membership vector for each of the items. The clustering algorithm has access the set of vectors, and can also make queries about the underlying soft clustering. As in hard-clustering, these queries can take at least two forms. Specifically, membership queries refer the existence of membership-orucle which whenever queried, replies with the membership value of the 2th item to the jth cluster, i.e., the jth entry of the 7th membership vector. One could argue that querying the membership values, and specifically, the existence of such a membership-oree -oaclle is not realistic. and often impractical in real-world settings since it requires knowledge of the relevant clusters. Instead, the similarity query model that takes two or three elements as input and ask "How similar are all these elements?" ?" is much easier to implement in practice. Accordingly, in similar vein to hard-clustering, we show that membership queries can be simulated by similarity queries, measured by the inner-product between pairs (and triplets) of membership vectors. Finally, as will be explained in more detail, the responses of the oracle or the target solution do not need to correspond to the optimum solution of the fuzzy k-means objective, but instead need to satisfy a few mild conditions. Accordingly, the target solution can represent noisy/quantized version of the optimum solution of the fuzzy k-means objective function making our set-up highly practical in crowdsourcing settings.
A natural question that one can ask about fuzzy clustering following the lead of [4] is how many membership/similartyy queries one may ask so that the clustering can be efficiently solved with a good approximation of the target solution? In this paper, our main motivation is to answer this rather basic question. It has to be noted that revealing fractions of labels during clustering algorithm in fuzzy k-means has been studied with some heuristics in [42], but not only the model was different from ours, a rigorous theoretical study was also lacking in the past literature.
Our contributions and techniques. We design several algorithms and analyze their query and computational complexities. Specifically, the first algorithm we propose works in two phases: in the first phase, we estimate the center of each cluster using non-adaptive queries, and in the second phase we recover the membership of each element to each cluster using the estimated centers obtained in the first phase. We show with this algorithm it is possible to get an approximation of the membership vectors by making only O(poly(k:
log n) queries, where /3 is ratio of the volume of the smallest cluster to the average volume, informally speaking. Then, we show that by allowing one to ask adaptive/sequential queries in the first phase, the polynomial dependence on 8 of the query complexity can be further improved. Despite the strong dependency of the query complexity on B, for large regime of parameters, our query complexity is non-trivial and sublinear in n. Interestingly, for the special case of l 2. we can completely get rid of the dependency of the query complexity on B, and it suffices to ask Olog² n) queries only.
2

---

For our theoretical results to hold, we make an assumption on the dataset that quantifies the cluster- ability of the data. We would like to emphasize that our assumption is only needed for deriving the theoretical guarantees; our algorithms are demonstrated to perform well on real- cal-world datasets irre- spective of whether our assumption holds or not. The computational complexity of all the algorithms scales as d times the number of queries.
is to be noted that the analysis of the aforementioned algorithms are technically much more demanding than solving the analogous query complexity problem for hard k-means. For the case of hard k-means, a general principle would be to sample a small set of items and estimate the centre of the largest cluster from the samples (see, [4]). Subsequently all the items closest to the estimated centre can be assigned
it and the cluster can be removed from consideration. One can iterate over this algorithm to find all the clusters. However the size of a cluster is not well-defined in the fuzzy setting: and also it is not possible to assign items to a cluster and remove them from consideration, since they can very well have nonzero memberships to other clusters.
To tackle these difficulties, we have to use more challenging technical tools and analysis methods than the hard k-means literature. In a nutshell, since at any step of the algorithm we cannot remove items from consideration, we propose sophisticated random sub-sampling algorithms that explore the space of items efficiently. Specifically, having reliable approximations for the centers and memberships of some processed clusters, we partition the space of items into bins that have the same approximated sum of membership weights to unprocessed clusters. Sampling equally from every bin ensures that we obtain enough samples from items which have high membership weight to those clusters which have not yet been approximated. Also, contrary to hard k-means where a simple (unbiased) empirical mean estimator is used to approximate the means, in the fuzzy setting, we end up with a form of self-normalized importance sampling estimators. While these estimators are biased, we managed to bound their deviations in an elegant way using concentration inequalities. We tested our algorithms over both synthetic and real-world datasets, and illustrate the tradeoff and effect of different values of 33 and on the estimation error and query complexity.
Related work. Clustering with limited label-queries have mostly followed two different lines of works. In the first line of work, queries were used to make the objective based clustering, such as k-means, polynomial time solvable [4, 2, 18, 12, 13, 14]. The problem being considered here is most closely related to this line of work, albeit, instead of hard k-means, we focus on soft objective.
In the second line of work, instead of an objective based clustering. it is assumed that there exists a ground-truth clustering, and by label-querying one gets (noisy) answer from oracle about this ground-truth. The aim of this line of work has been to give catistical-computation
guarantees on recovery of the ground truth [36, 37, 35, 2, 15, 46, 43]. The work in this canon that is closest to our problem is [28), where an overlapping clustering groundtruth was considered. At high level, we also consider overlapping clusters, however, focus on objective-baser based clustering therein.
It is worth noting that clustering with same cluster, or other label queries, has found connections with and application to correlation clustering [15, 43], community detection [37, 17], heavy-hitee [44] and possibly other areas, that we might have missed. Our problem can be seen as approximately equivalent to non-negative symmetric matrix factorization [40] with limited access the entries of the factors (via queries) [22].
Organization. The rest of the paper is organized as follows. In Section 2 we present our model and the learning problem. Then, in Section we present our algorithms and their theoretical guarantees. The main theoretical results can be found in Theorems 1,2,3. Due to space limitation, proofs, some pseudocodes, experimental results over both synthetic and real-world datasets, and conclusions are relegated to the supplementary material.
2 Model formulation and background
2.1 The optimization problem
We start by describing the hard k-means problem, and then move forward to the fuzzy k-means problem (soft clustering). Let X C Rd be a set of d-dimensional points, with |X = n. We denote this set of vectors by [2 and assume without loss of generality that x; ((0, R), for any i E [n]]. where B R) is the LucEudiid ball of radius R R4 centered around E Ed Let
3

---

Cx - (CI, C,. C be a clustering (or, partition) of X' where k E is the number of clusters. We say that a clustering Cx is center-based if there exists a set of centers μ - (14, M2..... P C R such that the clustering is induced by the Voronoi diagram over those center points. The objective function of hard k-means is
Jm (X, He U)
Uis | My
where U E {0, 1]xxk is the partition matrix, i.e., the membership weight U: is 1 if at E Cj. and otherwise. In hard clustering each data point is assigned exactly to one cluster and every cluster must contain at least one data point. The goal of k-means is to minimize (1) w.n.t. (u, U).
In soft-clustering there is no partitioning of X. Instead, deseribe the 4thh cluster of fuzzy clustering as a vector of the fractions of points assigned to it by the membership function. In particular, the memberships weights take on real-valued numbers in [0, 1] rather than {0, 1]. for hard clustering. The fuzzy k-means problem is defined as follows.
Definition (Fuzzy k-means). Let a 2 and k E N. The fuzzy k-means problem is to find a set of means = {MetRe(M) C R and a membership matrix U [0, 1|mx* minimizing
(m, pe U)
U || 1,
subject to Σ}= Vig = and 0 < E.= Uig < n, for all i E [m] and j E [R:].
The parameter a is called the fuzzifier, and is not subject to optimization. It can be shown that when a + 1, the fuzzy k-means solution coincides with that of the hard k-means prob- lem. Similarly to the classical k-means problem, it is easy to optimize the means or mem- berships of fuzzy k-means, assuming the other part of the solution is fixed. Specifically, given a set of means μe, it can be shown that U in (3) below is the optimal membership weights minimizing the cost in (2) (see, e.g., [8][Theorem 11.1]). On the other hand, given a set of membership weights U, the weighted centers in (4) below are the optimal minima.
2/(a-1)7
Σ 1=
U 0;
Ug
Σ
D 14
(3)
M3
U
x Pell
for all i E [n], j [k]. Iterating these solutions known as the Lloyd's algorithm [32], which provably lands on local optima. It is well-known, however, that finding the optimal solution (i.e., global minimia) to the k-means problem is is NP-hard in general [33, 48]. While the same result unknown for the fuzzy formulation, it is strongly believed to be the case (c.g.. [9. 16)).
Finally, although several validity indexes for the performance of fuzzy k-means solutions have been proposed in the literature (see, e.g., [24, 251), the Xie Beni [51] is the most widely used in the literature. This measure is defined as follows'
Jim p, U)
XB(X' A nk min; ||I, M1 112
(5)
For the rest of this paper, we denote a clustering by P a (1,, U). and we replace XB(X', μa. U) by XB(X' P). Accordingly, the optimal solution to the fuzzy k-means problem (Defintion 1) is denoted by Pa. Finally, we say that a clustering P is consistent center-based if:
Given membership weights U, the centers μe are given by (4).
The membership weights U are monotone, i.c., if [z. - 12y112 - |x1 -13122 then Ut₁ 2
Utj, for any i, E [n] and j E [kc].
The first condition appears also in [4]. The second condition excludes inconsistent membership weights U. In particular, as is shown in [16], and in Lemma 5 in the appendix, both conditions
In (5) we divide by rul and not just by n, as in [51], where & was consider fixed parameter. If & is allowed grow (e.g., with n.), then our definition makes more sense, in general the numerator in (5) can grow with k.

---

are satisfied by the optimal solution Pt, as well as by (4). We would like to clarify that the above assumptions are only required for the theoretical analysis; Our proposed algorithms can be implemented regardless of these assumptions. As is shown in Appendix F, in real-world applications, our algorithm works well even if these assumptions do not hold.
2.2 Domain expert/oracle
Our goal is construct efficient algorithms with the aid of domain expert who can give an approximate solution to the fuzzy k-means problem. Specifically, given a clustering P, P-oracle a function Op that answers queries consistent with P. One can think of such an oracle user that has some idea about its desired solution, enough to answer the algorithm's queries. Importantly, note that as long as P is a consistent center-based clustering, need not be the optimal solution P minimizing (2). The algorithm then tries to recover (or, approximate) P by querying the oracle a small number of times. For hard clustering, the same-cluster query oracle model (i.e., "do elements i and belong to the same cluster") was considered in [4]. Using certain number of such same-cluste queries and the data points X' the clustering P can be found efficiently [4], while finding the optimal solution without the aid of an oracle is NP-hard. For the fuzzy formulation, one can think of analogous oracle models, and in this paper, we focus on the following.
Definition (Membership--raccee A membership query asks the membership weight of an instance 3; to cluster j. ie.,, Otunay j) = Viy-
Basically we ask the oracle for the membership weight of æ; to cluster C,. Using a certain amount of such queries and the data set X' we would like to approximate the solution for fuzzy k-means problem. As discussed in the Introduction, one could argue that querying the membership values, and specifically, the existence of such a membership-oracee. is not realistic, and often impractical in real-world settings since it requires knowledge of the relevant clusters. Instead, the following similarity query models are easy to implement in practice.
Definition 3 Oranae. A fuzzy pairwise similarity query asks the similarity of two distinct instances Dy and By i.e., O (p, ④) = (Up. Ug). A fuzzy triplet similarity query asks the similarity of three distinct instances Ep. Bgg Ty. i.e.. Ouriplec (p.q. q.r) -Ee(() Up UpeUgeUre
We show in Appendix H, however, that each membership query can be simulated with few similarity queries. From theoretical perspective, membership queries can be simulated with only fuzzy pairwise similarity queries if there exists many pure instances (instances that have a membership weight of 1 to a particular cluster in the dataset), see Lemma 14 in appendix. Unfortunately this strong condition is necessary as well. But it turns out that by using a few triplet similarity queries at the beginning, we can resolve this issue. Specifically, prove the following result, informally stated, that is interesting in its own right.
Lemma (Membership to Similarity Queries Reduction, Informal). Suppose there exists an algorithm An with time complexity Tn that uses membership queries to provide some guaranteed solution of the fuzzy k-means problem. In that case, under mild conditions on the dataset, the same guarantee can be obtained with O(k?) fuzzy triplet similarity queries and (km) fuzzy pairwise similarity queries, with a time complexity of + 0(mk + k2
Therefore, we can express everything in terms of the more natural notion of similarity queries and hence, we use membership queries for the rest of the paper to make the representation of our algorithms simpler.
Noisy/Inaceurate Oracle. Our algorithms work even with inaccuracies in the oracle answer, provided the deviation is small. Under the assumption that such inaccuracies are random, in particular, a repetition algorithm can remedy such errors. Specifically, consider the case where Ouwzay ji = Ui + Saj. where Çij is a zero-mean random variable, and assume the errors to be independent, i.e., the answers are collected from independent we show how one can convert any "successful" solver for the noiseless problem into a solver for the noisy problem; generally speaking, by repeating the noiseless solver for T consecutive steps using the noisy responses, and then averaging the results to obtain the final estimate. Note that, the technique used to handle the subsequent steps are also applicable to any bounded error. For simplicity of exposition and clarity, opted to focus on the noiscless setting given in Definition 2.
workers Then, in Appendix G
5

---

2.3 Objective and learning problem
The goal of the algorithm is to find an approximated clustering that consistent with the answers given to its queries. We have the following definition.
Definition 4 (Oracle-Based Solver). Lei (X, P) be a clustering instance. An algorithm A is called a E2, 62, Q)-solver if can approximate P by having access to X and making at most Q mem- bership queries to a P-oracle. Specifically, for any E2, > 0, the algorithm outputs P such that max || - P/ S e and (a) [U,g - -Oyl S 62. Such an algorithm is polynomial 62, -soolvrr if its time-complexity is polynomial in (n, k, 1 ,
We would like to emphasize that we seek an approximate solution rather than exact one. It is important to note Q = (nk) membership queries suffice to recover the P-oracle clustering. Also, with unbounded computational resources one can find the optimal clustering P without any queries. Nonetheless, in this paper, we would like to have sub-lineas dependency of the query complexity on and polynomial dependency of the time complexity on k. Having an algorithm such as the one in Definition 4, implies the following guarantee, proved in Appendix A.
Lemma 2. Let (X,P) be a clustering instance, and A (61, 62, Q)-solver. Then,
XB(X,P) - -XB(X, XB(X, ((G)) + (E2))
e +
+o
(6)
/ ||m, - Myl12 11
min
||M - M
The lemma above shows that if 61 and 62 are small enough, then the XB measure associated with an (f1, 62, Q)-solver is "close" to the XB measure associated with P. Note, however, that the r.h.s. of (6) depends inversely on minezj ||, 13, 1| Accordingly, if for some clustering instance (X, P) this
quantity is too small compared to the estimation error, then the difference [XB , P) XB(X, P)] uncontrolled. This is reasonable since when clusters are "close". the estimation task gets harder.
Finally, we introduce certain notations that will be needed for the presentation of our main results. Given set of points A' and v E Rdd let Te : [n] + [n] be the permutation defined on [n] such that
a ( (l11 || x=, 12
for all < j E [n]. To wit, Tu is the ranking of the elements in X' when they are sorted ascending order w.r.t to their distance from Then, we let E R4 be the maximum positive number such that for all j e [k:].
T Tu, Vp E B(ug,
(8)
Intuitively, if one has reliable estimates for the centers, then the ordering of X' w.r.t. these estimated centers is the same as the ordering w.r.t. the target centers. Next, we define the cluster membership size associated with P by Eve(s) Uzy. for all j E [k], and a parameter 3 RR by 3 2 minyelM kn-1. Eig(n) Uty- Accordingly, in terms of B, the minimum cluster membership size is at least 3n/k: k. Notice that 3 must be less than unity since Σnj Uij = and there must exist at least one cluster whose membership size is at most n/k. We mention that 3 was introduced in [18] as well.
3 Algorithms and theoretical guarantees
3.1 Two-Phase algorithm
We start by providing a non-formal description of our algorithm, whose pseudocode given in Algorithms 1-3. Specifically, in the first three steps of Algorithm 1 we approximate the centers of all clusters. To that end, we start by sampling at random m elements from [z] with replacement, and denote the obtained samples by S. The value of m is specified in Theorem below. Subsequently, we query the membership weights U,j. for all i E S and j [k). Using these queries, we approximate the center of every cluster using the estimator defined in Step 3 of Algorithm 1. Note that this estimator the most natural candidate when one knows the membership weights only for a set of sub-sampled elements. Although this algorithm is quite intuitive, it suffers from the natural drawback that if the

---

size of a particular cluster is small, many samples are needed for reliable estimate of its center.
Algorithm 1 Parallel algorithm for approximat-
Algorithm 2 MEMBERSHIP(X* a,)
ing P.
Input: X, and Otuzy-
Input: X, Otuzy. ax m, and i7-
Output: An estimate {U., )
Output: An estimate P.
1: Find Tiy w.r.t. X.
I: Let S be set of m elements sampled random
2: for s 0, I...., 1/1 do
from [n] with replacement.
3: Find
( U= (03 an using
2: Query Oruzay (i.j), Vi E S.j E [K]]
BINARYSEARCHCK, -8).
Eiss u Vj E [k).
3: Compute m1; Lies Ug
4: end for
5: for 0, 1, 1/11 do
4: for j = 1,2...., do
6: for l, 1.....- ((o+1) + do
5: (Ü:))== <- MEEMBERSHIP(2 a,,an,)
7: Set 2220(05 (s)s = 877.
Ü.j < Ü.g + 1- Ug Vi [n].
8: end for
7: end for
9: end for
Next, using the approximated centers, we approximate the membership weights of every element up to a pre- cision of 1j by using Algorithm To that end, in the first step of this algorithm, we sort the elements of 2' in an ascending order according to their distance from the estimated center. Accordingly, if the estimation error of the centers e satisfics e S y, then (8) implies that the obtained ordering of elements after sorting from
Algorithm 3 BINARY TT
Input: Ohazy-
1: Set low = and high
2:
while low & high do
Set mid = [[low + high)/2
4: Query ( (mim)),
5:
if U Unimmits 2 x then
the estimated centers same as the true ordering of the elements obtained by sorting according distance
6:
Set low mid.
7: else
(in ascending order) from the exact centers (instead of approximated centers). Furthermore, the fact that P is a consistent center-based clustering implies that for any [k] the membership weights Uraytos are
Set high = mid 1.
9: end if
10:
end while
non-increasing in i. Therefore, for any j E [kc] using the binary search in Algorithm 3, we find the maximum index & such that Uzzg is larger than sn, for 10, 1/n)- This will create an 17-spaced grid, and we approximate each membership weight in accordance to the cell it falls into. Specifically, we assign Üzp, (,)) = $7,, for all t E [L,, - 1...., lot1 + 1]. Clearly, the estimation error is at most r7. Overall, each binary search step takes Olog n) queries, and therefore the total query complexity of this step is Ollog n/n). Finally, Step 6 transforms Ü.ş to ensure that EL U. = 1, for j E [k:]. We have the following result, the detailed proof of which is delegated to Appendix C.
Theorem 1. Let (X, be consistent center-based clustering instance, and recall the definitions of E R and E 1). Pick e S 7, 17 E (0, 1), and E (0, 1). Take as inpul to Algorithm m
RA 6
log & for some constant 0. Then, with probability at least 1-5, Algoriitn I is (c, Q)- A logg membership queries. Furthermore, Algorithm I
solver using Q o -(
[R'x40+1 log (epa)s
time-complexity is of order O (T logn
gR (e3"))
log K klogn
7
Proof Sketch of Theorem 1. To prove Theorem we first show that with high probability, Steps 1-4 in Algorithm output an c-approximation for all centers. To that end, we first show Lemma
that for given cluster j E [k]. with probability 6, |M, - 11,
4R² V m log 3. where Y e Y²
minje[s] n. Eiejn) UG This result follows by noticing that both the numerator and denominator of ūy are unbiased estimates of the corresponding numerator and denominator of μ, in (4). Representing my as a sum the true underlying center μú and a certain error term, the generalized Hoeffding's 's inequality in Lemma 4 implies the above estimation error guarantee. In light of this result, using Hölder's inequality and the union bound we show in Lemma that A - -11112 S for all j [k], m is as given in Theorem 1. Note that this centers estimation algorithm requires a total of km membership-oracle queries. Next, conditioned on the above proxy of any given center, show in
7

---

Lemma 7 that Algorithm 2 estimates the corresponding membership weights within a certain range of error with high probability. Specifically, for given cluster j. we prove that Algorithm 2 outputs Üzy. for i E [m], such that S U.₃ Ü. S 7 and Ü. (0, 7) 21,,..., 1.. Vi E [n], using (log n/n) queries to the nnembership-oracle Roughly speaking, this result follows from the arguments presented in the paragraph preceding the statement of Theorem 1. Finally, it is evident from the above that the total number of membership-oracle queries is Okm + k log n/n).
...
Note that both the query and computational complexities in Theorem exhibit exponential dependency on the "fuzzifier" a. As mentioned in Subsection 2.1, this parameter is not subject to optimization and, usually, practitioners pick a 2. Nonetheless, there has been a lot of work on this topic; one notable example is [27] which presents an initial theoretical approach towards the investigation of this question. seems that the value of a is influenced by the structure of the dataset, iee, the number of clusters and the distribution of each cluster. Currently, a definite answer on how to pick is unknown. Indeed, since there no baseline, one cannot decide which value of a is preferable. Note also that despite the fact that our query complexity naturally depend on a, it cannot be used to determine the "best" value of a. Assuming the existence of a ground truth, in Appendix F we compare the clustering accuracy for different values of a on real-world dataset.
3.2 Sequential algorithm
As mentioned in the previous subsection, the main drawback faced by Algorithm is its undesirable strong dependency on B3. The algorithm proposed in this section remedies this drawback to some extent. The algorithm works as follows. In the first four steps of Algorithm 1, we randomly draw m samples from [n]. and query the membership weights that correspond to all these samples. Using these samples we estimate the center of largest cluster i, having the maximal total membership weight Eies U... among the k clusters. Corollary 4 in Section D specifies the number of such elements needed to have a reliable estimate. Then, using this approximated center, we estimate the membership of every element in cluster i using Algorithm such that the estimate is multiple of m and further, the estimate has an additive eиror of at most 7/, just as we did in the two-phase algorithm. For the rest of the clusters, we follow the sequential algorithm in Steps 5-13 of Algorithm 4, the guarantees of which are characterized in the following result:
Theorem 2. Let (X,P) be a consistent center-based clustering instance, and recall the defini- gRag tions of y E R4+ and |3 E (0,1). Take m = c(( (Ra") =[(Ree) log 8. r 2gg log n1 for some constant e > O, and any 8 E 10, Then, with probability at least 1 - 8, Algorithm 4 is (c, 12, Q)-solver using Q = m log 16
2k
R4g4041
llog n
membership queries, for any + Alogg
chosen e S. and 1/2 s.m
S K
))
Furthermore, Algorithm 4 time-complexity is of order
O ( dRt24011 (Bcaa log
ak 4
+
1s log n
+
k log n + kn logn).
na
The proof of Theorem follows from a technically complicated induction. Due to space limitations, the details have been delegated to Appendix D and below, provide only a short sketch.
Proof Sketch of Theorem 2. Suppose that we have approximated the means of l < k clusters, indexed by To A (t1,,2....,47 ..). with an estimation error at most < 7, and further approximated the membership weights of every element in X' for all clusters indexed by Tr, up to an additive error Wh The leftover clusters, indexed by [k] Te, are the umprocessed clusters. The above implies that we can also approximate the sum ΣşE( Use,, for each i E X. up to an additive error ém-.
Note that, since Ün, is multiple of 77, for all: j E [4]. EşEØJ Ü., must also be multiple of Th Subsequently, we partition A' into bins, where the elements in particular bin have the same approximated sum of membership weights Formally, let Σ & {0, 1,... 1/12}. For each s E Σ, we define X, A (i [n] EyEr Üa,- sm be the 5th bin. Then, in Steps 9-10 of Algorithm randomly sample min(r, (X,)) elements from each bin with replacement, and denote the resulted sub-sampled set by )).. The value of is specified in Theorem 2. Sampling equally from every bin ensures that we obtain enough samples from elements which have high membership weight to the unprocessed clusters, i..., Exe[hN1 Ust, is large. Given these sub sampled sets, query the
8

---

membership weights Uzy, for all i E UserD, and j [b] Tr. Using these queries we would like to approximate the center of some unprocessed cluster. We choose the unprocessed cluster having the largest total membership size, weighted by the size of each bin. Mathematically, the index of the (f++1) 1)th cluster, and its approximated center are given as follows,
[L and Pu_, A E.Er ΣiEy,
U 18441 2
t--1 A argmax
Σ
U RE
(9)
EBer. 1. T Liey, Uür4
JE SET.
We choose the number of samples large enough so that the estimation error is less than The above steps are repeated until all unprocessed clusters are exhausted. Finally, once we have approximated all the centers, we apply Algorithm 2 to approximate the membership weight of every cluster up to an additive error of 1/2 I 7/1
Algorithm Sequential algorithm for approximating P.
Input: X, Oruzy. m, r, ??,, and 172.
Output: An estimate P.
8:
for 8 = 0,1,...,1/m do
I: Let S be set of m elements sampled at random
9:
Let V. be a set of minn(, (&x)) elements sam- pled random from X, with replacement.
from [xx] with replacement.
Query Oiuzzy( (f, (i, j), Vi E S.j E [k)]
10:
end for
3: f1- argmax,e14 Eies U
11: Compute t++1 using (9).
4: Compute Ph:, = Liss U2
12:
Compute P.,,, using (9).
Lies Us,
13: end for
for 8= 1.2...... do
14: for j = 1, 1, , k do
6: (U:,)[=1 M-EMBERSHIP(XX' m.,. a.
15: {Ū., M=1 + +EMBERSHHPPC Pay, 12))
122).
7: Set X, A {i [m] Eyele Unt sm) for
16: Ü.y + Ü.5 + 1-2% Uy
vi E [n].
8 S (0.,,....,1// 1/m.).
17: end for
Comparing Theorems and 2 we see that the sequential algorithm has a more graceful dependency on B. the size of the smallest cluster. On the other hand, the query complexity of the two-phase (recall that ? S 1/k for the sequential algorithm). Note that the
algorithm is better in terms query complexity of the sequential algorithm still has some dependency on B. This stems from the fact that we estimate the membership weights up to a precision of 7), which might be too large there exists cluster j such that maxte[s] U.j S m/1 Accordingly, in this case, all elements will fall into a single bin in the partition, leading to the same drawback the two-phase algorithm suffers from. Finally, we mention that for k: 2, we devise an algorithm whose query complexity is completely independent of 3. Due to space limitation, the details are given in Appendix E, but we state here our main conclusion and provide short sketch of the proof.
Theorem 3. Let (X, P) be consistent center-based clustering instance, recall the defini- tion of 7 E R2, in (8), and let k = 2. Then, with probability at least 1 8, Al- gorithm with m o ((S) log and r = o ( 318 is (c, n. Q)-solver us- ing Q = =0 R* log log(1/nd) + log2 n + logn
membership queries, for any chosen S Furthermore, Algorithm 5 time-complexity of order log
y, 8 (0,1) and n >
O nlogn dR' log n (19(1/7))
log" 2
7
We now explain the main ideas behind Algorithm 5. First, let S be a set of m elements sampled from [n] with replacement. Denote by ( E (1,2) the index of the larger cluster and l2 {1,2) the index of the smaller cluster, i.e., Eies Ug, > Eies U. The algorithm works as follows. We start by computing an estimate Pt, for the center of the largest cluster 41- Corollary 4 shows that O ((R/c)* log(4/8)) membership queries are needed to guarantee that || M4, ll S c. Now, the main novelty Algorithm
a non-trivial querying scheme used to estimate the memberships of the second cluster, Utt for all i E [n), using the center estimated for the first cluster t1. Note that for the special case of two clusters, querying Uit, reveals Uit, since Ust, Ung = 1. While, in the sequential algorithm, we always approximated the membership weights using bins of fixed size m,, here, we will approximate Uit with bins whose size data detendeeendn The reason for using variable bin sizes rather than fixed size bins is that with the latter might ask for many redundant

---

membership queries simply because many bins might be empty. Accordingly, by adaptively choosing the bin size for approximating the membership weights of the smaller cluster tz. while querying membership weights to the larger cluster 4, allows us to get around this issue completely; this results in theoretical guarantee that completely independent of B.
Algorithm 5 Sequential algorithm for approximating P with two clusters
Input: X. Ofuzzy a, m, T, and
I: Let S be set of m elements sampled at ran-
8: Query Ouuzzy (2, to obtain Ust, for all i E
dom from [r]] with replacement.
2: Query O (izze((1.)) and store Uij for all j E
9: end for
{1.2}.
10: Let Q be set of r elements sampled at ran-
3: Choose t argmax)E(1.2) Eies U
dom from P1 with replacement.
4: Compute estimator Pi, = Eieo U
2ies Uiz "i
11: Query Ouuzzy (i, 12) to obtain UN, for all i E
Q.
5: Obtain Pı, P2, N,, N2...., and Uit for
12: Compute P., in (111).
all i E [nx] using MEMBERSHIP2(X, a)
13:
for j = 1,2 do
6: for 1,2,3,..... log do
14: Run Alg MEMBERSHIP(X,, a,,,,, to
7: Let Ve be set of elements sampled
update Ü.Н for all E [n].
random from Xg with replacement.
15: end for
16: Return 14 Fh and Ü.g Vie [ E (1,
We now describe Algorithm 7 used to estimate the membership weights of cluster 12. We start by sorting X' in ascending order according to their distance from ni and initialize 7) U Upp., (n)ez
and Pm n. To wit, 7n is the membership of the element farthest from P. to the smaller cluster l2. For each q E= (2.3.... 3, log nt), we set 7/, = 1 and then perform binary search to find Pna arg 1 mp, Gie 2 144-- Here, we should think of ph, to be the index for which L (P%.) is the element closest from P.,, such that its membership to the smaller cluster t2 is at least 17g. Now, if Ipng - P 2 log n, we keep 77 unchanged, set Pny = Ph, and put all elements which are closer to Pt, than Fug,, (Png-1)- but farther than Fape, (Pn,) into a single bin. Notice that each such bin contains at least log n elements by definition. However, if ph,, is the same Png-1 then the membership queries in the latter binary search to compute P'y is wasteful. In order to fix this issue, we check if there are a sufficient number (at least log n.) of elements between phy, and P If there are not, then we set Ph, such that the above condition satisfied. More formally, Ih%, - P < log n we update Pr, min(0, P 1 1 log n)) and f/ = Uzp., (Po.) )2. In other words, we set pn, such that there at least log n elements between pn, and Pn,-1, and accordingly, we set 77 to be the membership of Tū. (Pn,) to the cluster 12. Subsequently, we query Ua, for every element that is closer to Pr, than Far,, (Pa.-1) but farther than Fxi,, (P,,)* In this case, we call these elements special elements, since we query every one of them. We will assume that all these special elements between Fnp,, (Pm.-1) )) and Exp,, (Pmç) are assigned a single bin.
To resolve the edge case, we put all those elements which are closer to fr, than Fups, (Prg n.) into a separate bin. Let g be the total number of bins formed by this algorithm, and say X, is the 5th bin formed by this method that does not contain any special elements. Let P be the set of all special elements. Notice that the number of bins g is at most 1 3 log n. and the number of special elements most 3 log" (since each bin can contain at most log n special elements). Moreover, for any bin X3 not containing any special elements, we can show that max,ex, Uit, < 2 min U which should be contrasted with the guarantee we have for the sequential algorithm, i.e., for a particular bin Xz. maxiex, Uit, minjex; Utt1 S 7/1 Finally, we again sub-sample r elements from each such bin X, with replacement, and denote the resulting subset by V/. We approximate the center of the second cluster by
X.l Σ, ΣiEY; U L. ΣiEr U
P
(10)
Σ, 1 D
EEEY U EiEr U
and show that the required r is independent of the cluster size.
10

---

Acknowledgements:: 1934846.
This work is supported in part by NSF awards 2133484, 2127929, and
References
[1] M. N. Ahmed, M. Yamany, N. Mohamed, A. A. Farag, and T. Moriarty. A modified fuzzy c-means algorithm for bias field estimation and segmentation of mri data. IEEE transactions on medical imaging, 21(3):193-11 2002.
[2] N. Ailon, A. Bhattacharya, R. Jaiswal, and A. Kumar. Approximate clustering with same-cluster queries. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz--T
fuer Informatik, 2018.
[3] D. Arthur and S. Vassilvitskii. k-means++:
the advantages of careful seeding. In N. Bansal, K. Pruhs, and C. Stein, editors, Proceedings of the Eighteenth Annual (CM--SAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027-1035. SIAM, 2007.
[4] H. Ashtiani, S. Kushagra, and S. Ben-David. Clustering with same-cluster queries. In Advances in Neural Information Processing Systems 29, pages 3216-3224. 2016.
[5] M.-F, Balean and A. Blum. Clustering with interactive feedback. International Conference on Algorithmic Learning Theory, pages 316-328. Springer, 2008.
[6] A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. Journal of computational biology, 6(3-4):281-297, 1999.
[7] P. Berkhin. A survey of clustering data mining techniques. In Grouping multidimensional data, pages 25-71. Springer, 2006.
[8] J. C. Bezdek. Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media, 2013.
[9] Blömer, S. Brauer, and K. Bujna. A theoretical analysis of the fuzzy k-means problem. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 805-810. IEEE, 2016.
[10] J. Blömer, S. Brauer, and K. Bujna. Coresets for Fuzzy K-Means with Applications. In 29th International Symposium Algorithms and Computation (ISAAC 2018), volume 123 of Leibniz International Proceedings in Informatics (LJPIcs), pages 46:1-46:13 12, 2018.
[11] A. Blum, J. Hoperoft, and R. Kannan. Foundations of data science. Cambridge University Press, 2020.
[12] M. Bressan, N. Cesa-Bianchi, S. Lattanzi, and A. Paudice. Exact recovery of mangled clusters with same-cluster queries. arXiv preprint urXiv:2006.04677 2020.
[13] M. Bressan, N. Desa-Bianchi, S. Lattanzi, and Paudice. Exact recovery of clusters in finite metric spaces using oracle queries. arXiv preprint arXiv:2102.00504 2021.
[14] M. Bressan, N. Cesa-Bianchi, S. Lattanzi, and A. Paudice. On margin-based cluster recovery with oracle queries. arXiv preprint arXiv:2106.04%9 2021.
(15) M. Bressan, N. Cesa-Bianchi, A. Paudice, and F. Vitale. Correlation clustering with adaptive similarity queries. Advances in Neural Information Processing Systems, pages 12510-12519, 2019.
[16] K. Bujna. Soft Clustering Algorithms Theoretical and Practical Improvements. PhD thesis, Paderborn University, 2017.
[17] I. Chien, C.-Y. Lin, and I.-H. Wang. Community detection in hypergraphs: Optimal statistical limit and efficient algorithms. In International Conference on Artificial Intelligence and Statistics, pages 871-879, 2018.
11

---

[18] I. Chien, C. Pan, and O. Milenkovic. Query k-means clustering and the double dixie cup problem. In Advances in Neural Information Processing Systems, pages 6649-6658, 2018.
[19] K.-S. Chuang. H.-L. Tzeng, S. Chen, J. Wu, and T.-J. Chen. Fuzzy c-means clustering with spatial information for image segmentation. Computerized Medical Imuging and Graphics, 30(1))9-15, 2006.
[20] W. F. De La Vega, M. Karpinski, C. Kenyon, and Y. Rabani. Approximation schemes for clustering problems. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 50-58, 2003.
[21] M. L. D. Dias. fuzzy-c-means: An implementation of fuzzy c-means clustering algorithm.. May 2019.
[22] C. Ding, X. He, and H. D. Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the 2005 SIAM international conference on data mining, pages 606-610. SIAM, 2005.
[23] D. Firmani, S. Galhotra, B. Saha, and D. Srivastava. Robust entity resolution using crowdoracle. IEEE Data Eng. Bull., 41(2):91-103, 2018.
[24] Y. Fukuyama. A new method of choosing the number of clusters for the fuzzy c-mean method. 1989.
[25] I. Gath and A. Gev. Unsupervised optimal fuzzy clustering. IEEE Trans. Pattern Anal. Mach. Intell., 11(7):773-780, July 1989.
[26] K. Huang, N. D. Sidiropoulos, and A. Swami. Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Transactions on Signal Process- ing, 62(1):211 1222244, 2013.
[27] M. Huang, Z. Xia, H. Wang, Q. Zeng, and Q. Wang. The range of the value for the fuzzifier of the fuzzy c-means algorithm. Puttern Recognition Letters, 33(16):2280 2284, 2012.
[28] W. Huleihel, A. Mazumdar, M. Médard, and S. Pal. Same-cluster querying for overlapping clusters. In Advances in Neural Information Processing Systems, pages 10485-10495, 2019.
[29] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM review, 51()):455- 500, 2009.
[30] X. Lin and X.-w. Chen. Mr. knn: soft relevance for multi-labed classification. In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 349-358, 2010.
[3]] Q. Liu, J. Liu, M. Li, and Y. Zhou. A novel initialization algorithm for fuzzy c-means problem. In J. Chen, Q. Feng, and Xu, editors, Theory and Applications of Models of Computation, pages 215-225. Springer International Publishing, 2020.
[32] S. P. Lloyd. Least squares quantization in pem. IEEE Trans. Inf. Theory, 28(2): 1982.
[33] M. Mahajan, P. Nimbhorkar, and R. Kasturi. The planar k-means problem is np-hard. volume 442, pages 274-285, 02 2009.
[34] X. Mao, P. Sarkar, and D. Chakrabarti. On mixed memberships and symmetric nonnegative matrix factorizations. In International Conference on Machine Learning, pages 2324-2333. PMLR, 2017.
[35] A. Mazumdar and Pal. Semisupervised clustering, and-queries and locally encodable source coding. In Advances in Neural Information Processing Systems, pages 6489-6499, 2017.
[36] A. Mazumdar and B. Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems, pages 5788-5799, 2017.
[37] A. Mazumdar and B. Saha. Query complexity of clustering with side information. In Advances in Neural Information Processing Systems, pages 4682-4693, 2017.
12

---

[38] A. Mazumdar and B. Saha. A theoretical analysis of first heuristics of crowdsourced entity resolution. Thirty-First AAAI Conference on Artificial Intelligence, 2017.
[39] A. Moitra. Algorithmic aspects of machine learning. Lecture notes, 2014.
[40] Paatero and U. Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Emvironmetrics, 5(2):111-126, 1994.
[41] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2830, 2011.
[42] W. Pedrycz and J. Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems, Man, and Cybernetics, Part (Cybernetics), 27(5):787-795, 1997.
[43] B. Saha and S. Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. In 27th Annual European Symposium Algorithms (ESA 2019). Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, 2019.
[44] S. Sarmasarkar, K. Reddy, and N. Karamchandani. Query complexity of heavy hitter estimation. arXiv preprint arXiv:2005. 14425, 2020.
[45] N. D. Sidiropoulos and Bro. On the uniqueness of multilinear decomposition of n-way arrays. Journal of Chemometrics: A Journal of the Chemometries Society, 14(3):229-239, 2000.
[46] C. E. Tsourakakis, M. Mitzenmacher, K. G. Larsen, J. Btasiok, B. Lawson, P. Nakkiran, and Nakos. Predicting positive and negative links with noisy queries: Theory & practice, arXiv preprint arXiv: (eXivv/70.0073000 2017.
[47] F. VALAFAR. Pattern recognition techniques in microarray data analysis: A survey, Annals of the New York Academy of Sciences, 980:41 1-4, 2002.
[48] A. Vattani. The hardness of k-means clustering in the plane.
[49] N. Vesdapunt, K. Bellare, and N. Dalvi. Crowdsourcing algorithms for entity resolution. Proceedings of the VLDB Endowment, 7(12):1071-100
2014.
[50] Wang, T. Kraska, M. J. Franklin, and Feng. Crowder: Crowdsourcing entity resolution. Proceedings of the VLDB Endowment, 5(11), 2012.
[51] X. L. Xie and G. Beni. A validity measure for fuzzy clustering. IEEE Truns. Pattern Anal. Mach. Intell., 13(8):841-877, Aug. 1991.
[52] S. Zhang, R.-S Wang, and X.-S. Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications, 374(1):48344)) 2007.
13


Reviews:
[{"review_id": "acDFLHZzeDi", "reviewer": "Reviewer_E3Xr", "summary": "This work gives algorithm for the soft k-means problem using similarity queries. This means that the clustering algorithm is allowed to make queries of the form \"how similar are two data items\". There have been recent results in this setting for k-means/median problems. This paper extends such results in the context of the soft k-means problem. The soft k-means problem is a generalisation of the k-means problem where assignment of a point to a center is on 0/1. So, the goal is to output k centres and membership weights U_{ij} (the degree of assignment of point i to center j).", "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": "The main contribution of this paper is to give theoretical bounds on the quality of soft clustering given by simple random sampling based algorithms. The theoretical bounds is in terms of Xie-Beni validity index. The main idea is to randomly sample a few points S, make membership queries (which is basically querying for weights U_{ij} for i \\in S and j \\in [k]). Once these weights are known, the centers are approximated and with respect to these centers, the U_{ij}'s for all i is calculated.\n\nOn the positive side, the paper extends a recent popular line of work to the soft k-means setting. On the negative side, the discussion for why it is okay to assume that there is an oracle that returns U_{ij}'s approximately is a bit lacking (at least in the main submission).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical in nature.", "review_text": "", "extra_scores": {"ethical_concerns": "This work is theoretical in nature. There are no serious ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "NghidU8Kv-v", "reviewer": "Reviewer_Yscy", "summary": "The paper extends the results in Ashtiani, Hassan, Shrinu Kushagra, and Shai Ben-David. \"Clustering with Same-Cluster Queries.\" NeurIPS.2016 into the context of fuzzy clustering where assignments of points to centers are fractional. Analogous to the same-cluster queries proposed in the original paper, this paper proposed using similarity queries which would return a scalar reprenseting the similarity of the memberships of any two points (this is the inner product of the two membership vectors). The work first states that the similarity queries and the seemingly stronger membership queries (which directly return the fractional assignment of a point to a cluster) can be converted into each other. Then, given any \"true\" underlying fuzzy clustering solution, the paper formally defines how to measure the proximity of any fuzzy clustering solution to this underlying benchmark, and relates this proximity to a previous proposed performance metric for fuzzy clustering. The main body of the paper focuses on developing a fuzzy clustering algorithm based on similarity queries and providing theoretical guarantees of the number of queries needed, and how close the constructed fuzzy clustering is to the underlying clustering.", "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": "Overall I think this paper has some interesting insights, a relatively complete theoretical framework, but it also has some defects which hurts its quality. In particular, I think this paper needs to change its format to suit the requirements of this venue before it gets published and I'm not sure if those changes can be considered minor. See detailed comments below.\n\nOriginality: This paper has good originality is the sense that it extended the framework of clustering with same-cluster queries into the context of fuzzy clustering, redefined the type of queries needed and has been able to find results that are analogous to the original work. Some of the highlights:\n- A relatively reasonable definition of queries used by the main algorithm. Just like the relationship between same-cluster and point-cluster-membership queries in the hard k-means literature, the authors were able to recover a similar relationship between the similarity queries used here and the membership queries. \n- The algorithm design, despite having a similar two-phase structure of center estimation plus membership estimation, shows that the authors have put a lot of efforts, as is required given the more challenging context of fuzzy clustering.\n- Naturally, the algorithms have some dependency on the size of the smallest cluster, which arises due to center/membership estimation based on sampled points. The authors tried to reduce the depency using more clever algorithm designs.\nSome potential shortcomings:\n- The quality of fuzzy clustering is measured using only one performance metric (5), which is a factor of min||\\mu_i - \\mu_j||^2 away from the natural fuzzy clustering cost (2). The performance of the algorithm is analyzed using (5), but I wonder what the performance guarantees are for (2) itself?\n- For the theoretical guarantees to hold, the underlying fuzzy k-means clustering has to be \"consistent center-based\", which seems too strong for me. Can we somehow relax the conditions?\n- The sequential algorithm reduces some dependency on \\beta but takes a lot of space. The authors can consider compressing this section.\n- In Section 3.2, the authors included a new algorithm that could reduce the dependency on \\beta. I think there should be a more intuitive description of the algorithm design and why it helps.\n\nQuality: It seems to me that the submission is technically sound and the theoretical claims are well supported. \n\nClarity: Despite the soundness of the results, I think this work should be reorginized and tidied up before it is ready for publishing at this venue. I found the description of the algorithms and the analysis to be wordy and I think the contents can be compressed and partially moved to the supplementary to make room for the numerical experiments and conclusion sections, which are in the supplementary now. The authors can also tidy up the notation systems and the statements in the main theorems to help readers understand the gist of the main theorems.\n\nSignificance: The results add to the community's understanding of fuzzy clustering better and is a good exploration of the possible designs of cluster queries and what can be achieved with them. Others might also be able to build on this work theoretically.\n\nMinor Comments:\n- P5, Line 182, \"Our goal is to construct efficient algorithms which with the aid of a domain expert ...\": the \"which\" should be deleted.\n- In Definition 2, j is used to index clusters, while in Definition 3 j is used to index a point x_j. I think it is better to change the notation in Def. 2 to avoid confusion.\n- The algorithm description can be shortened and the authors can work on providing more intuition and leaving out some details. For example, I think it is fine to postpone Procedure 3, the binary search algorithm till the appendix since it is relatively intuitive and can be described with a few sentences.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed these aspects, but it is postponed until the supplementary materials.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hrs"}, "extra_text": {}}, {"review_id": "71t6ul7LxN", "reviewer": "Reviewer_Qp7i", "summary": "Given a set of points X in R^d, a fuzzy k-means clustering of X is an assignments of k weights in [0,1] to every point in X, so that the i-th weight represents \"how much\" that point belongs to the i-th cluster. The problem tackled in this work is to recover a hidden fuzzy k-mean clustering of a given set X by querying some similarity oracle that answers queries in the form \"how similar are the weight vectors of these two points?\". The authors develop an algorithm to approximately recover the hidden clustering (in a well-defined optimization sense) with a number of queries that grows as log |X|, and that depends polynomially on other parameters (including the desired accuracy).\n\nEDIT: I think the authors for their response; after reading it, I will leave my rating unchanged.", "questions": "", "limitations": "", "rating": 7, "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": "TLDR: I think this is a good paper and deserves acceptance.\n\nOriginality: good. Not much is known about this problem. The authors develop novel algorithms that are based on a combination of different ideas. The comparison with previous work is done correctly. I would only point out additional works, of which I am aware of, that do active clustering based on same-cluster queries, but are more recent than those cited at lines 118-128:\n\nhttps://proceedings.neurips.cc/paper/2020/hash/6950aa02ae8613af620668146dd11840-Abstract.html (NeurIPS 2020)\nhttps://arxiv.org/abs/2102.00504 (to appear in COLT 21, according to the official list of accepted papers)\n\nQuality: good. I could not check the proofs, but I followed the proof sketches and they look ok. The authors point out both the strengths and the weaknesses of the work.\n\nClarity: fair. The paper is clearly written and I found it smooth to read. There a couple of points that could be improved, but these are minor concerns.\n\nSignificance: good. The paper provides new knowledge on this problem, for which little was known. The algorithms are interesting as well, as they exploit a combination of different techniques in a clever way (standard sampling, weighted sampling, binary search); I think they are likely to be used in further developments on the subject. The only \"drawback\" is that the bounds are quite complex and difficult to intepret. However I fear that this is rather unavoidable with this problem.\n\n\n\nDETAILED COMMENTS:\n\nL66: \"does\" -> \"do\"\n\nL96 and others: note that [4] assumes that the clusters are realized by spheres. This is a non-standard hypothesis so you may want to specify it.\n\nL118-128: there are some recent works that appear to be even more relevant to this discussion (see above).\n\nL142: \"corresponds to\" the Voronoi diagram sounds a bit weird; perhaps \"is induced by\"?\n\nL149: \"take\" -> \"take on\"\n\nL168: can you explain the XB measure? It's obscure.\n\nL182: \"which with the aid... problem.\" something is missing in this sentence.\n\nL208: the thing of the triplets is interesting. Can you spend a few more words on how it works?\n\nDefinition 4: I find a bit disappointing that the solver is said to be polynomial as soon as its complexity is polynomial in n+k alone (incidentally: I think that \"polynomial in (n,k)\" is not very correct although it's clear what you mean). Shouldn't it be polynomial in the approximation parameters as well? This is the case for your algorithm, so it's even better.\n\nL248: \"a couple of notations\", I think \"notation\" is uncountable.\n\nL255: \"for all $j \\in k]\" the left bracket is missing.\n\nL282-295: the explanation here is not clear. Can you try making it clearer?\n\nL287: \"decreasing\", you mean nonincreasing, right? That is, ties are allowed I suppose?\n\nTheorem 1: the statement has a technical problem (easily fixed). It is saying that for *every* m \\ge M, the q-solver uses O(f(M)) queries. This is obviously false (suppose we take m = (R k^a / ( \\epsilon \\beta^a))^10   just for instance). You should let m \\in \\Theta(M), or say \"for some large enough m \\in O(M)\". The same in the other theorems.\n\nL311: \"up to a certain controllable\" what does this mean?\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are adequately discussed. There is no foreseeable societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3eJv8hio1W", "reviewer": "Reviewer_NtfQ", "summary": "The authors study the fuzzy k-means problem in the presence of a cluster membership oracle. For the fuzzy k-means problem this is an oracle that returns the i-th entry in the j-th cluster membership vector. The authors aim at polynomial time algorithms that in the presence of a  sublinear number of membership queries. \n\nUnder some assumptions on the structure of the input instances they give different algorithms that achieve this goal. The first algorithm takes a uniform random sample and then queries the oracle for cluster memberships. Based on the results, it guesses the cluster centers. Then it exploits the structural assumption and the oracle to compute the clusters. A second algorithm is given that uses a different method to compute the clustering. It also samples a subset of the input data and then queries the oracle to identify the cluster with the largest membership weight in the sample. Then it computes the cluster of this center. After identifying the first cluster the algorithm iterates a sequential algorithm that always predicts the center of the next largest remaining cluster.", "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": "The paper builds upon earlier work [4] that obtained a similar result for the k-means problem and I also took at [4] to better understand the new contribution of this paper. The extension to the fuzzy k-means problem is non-trivial, requires some technical work and also the right structural assumptions. Still, algorithmically, the approach (in particular, the first algorithm) is  somewhat similar to [4], so that the result as such is not too surprising. The second algorithm differs more from [4].\n\nAdditionally, the main result is hard to parse: The paper would benefit from making the structural assumption on the input set more clear. Also, the use of the Xie-Beni distance in order to present the guarantees is not very helpful. I think that expressing the bounds in terms of the objective function would help to clarify the main message of the paper. \n\nIn particular, it is not clear to me why the authors can claim that \"making a few similarity queries, the problem becomes easier to solve.\" Wouldn't it be necessary for this claim to argue that under the same input assumptions the problem cannot be solved in, say, polynomial time with the same guarantees? \n\nGiven the previous work of [4], I think that this paper is not strong enough for NeurIPS.", "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": {}}]

Author rebuttal:

Meta-review: The authors study the fuzzy k-means problem with oracle queries and present algorithm that outperform previous work. The reviewers find the result interesting and novel and so, after the discussion phase, we think that the paper should be accepted.

One limitation of the paper is that it is a bit hard to read but the authors should be able to address the reviewers concerns for the final version of the paper. One important point raised by the reviewer is that Lemma 2 in the current form is very confusing and it should be rewritten and probably moved to the end of the paper. 
Decision: Accept (Poster)