Fuzzy Clustering with Similarity Queries
Year: 2022

Abstract:
The fuzzy or soft k-means objective is a popular generalization of the well-known kmeans 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 semisupervised 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(poly(k) log n) similarity queries and run with polynomialtime-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.

heading: 1 Introduction
text: The k-means objective for clustering is perhaps the most ubiquitous of all unsupervised learning paradigms. It is 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, 3]).
In recent times, there have been efforts to bring in a flavor of active learning in k-means clustering; by allowing the learner to make a limited number of carefully chosen label/membership queries [4, 2, 18]. In this setting, the main objective is to show that a polynomial-time solution exists provided that small number of such queries to 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/similarity query (i.e., “do elements i 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 k times as many queries [4].
35th Conference on Neural Information Processing Systems (NeurIPS 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-resolution, are being delegated to crowdsourcing models. One can easily assume that the crowd is playing the role of an oracle here. It 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 is 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 a membership value between 0 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 is 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 a set of n vectors (items) in the d-dimensional Euclidean space, and we are tasked the problem of determining the k-dimensional membership vector for each of the items. The clustering algorithm has access to 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 to the existence of a membership-oracle which whenever queried, replies with the membership value of the ith item to the jth cluster, i.e., the jth entry of the ith membership vector. One could argue that querying the membership values, and specifically, the existence of such a membership-oracle, 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 a 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/similarity 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 a 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 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 of the query complexity can be further improved. Despite the strong dependency of the query complexity on , for a large regime of parameters, our query complexity is non-trivial and sublinear in n. Interestingly, for the special case of k = 2, we can completely get rid of the dependency of the query complexity on , and it suffices to ask O(log2 n) queries only.
For our theoretical results to hold, we make an assumption on the dataset that quantifies the clusterability 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-world datasets irrespective of whether our assumption holds or not. The computational complexity of all the algorithms scales as d times the number of queries.
It 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 to 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 and k 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 a 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 a (noisy) answer from an oracle about this ground-truth. The aim of this line of work has been to give statistical-computational 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 a high level, we also consider overlapping clusters, however, focus on objective-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-hitters [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 to 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 3 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.

heading: 2 Model formulation and background

heading: 2.1 The optimization problem
text: We start by describing the hard k-means problem, and then move forward to the fuzzy k-means problem (soft clustering). Let X ⇢ Rd be a set of d-dimensional points, with |X | = n. We denote this set of vectors by {xi}ni=1, and assume without loss of generality that xi 2 B(0,R), for any i 2 [n], where B(a,R) is the L2-Euclidean ball of radius R 2 R+ centered around a 2 Rd. Let
CX , {C1, C2, . . . , Ck} be a clustering (or, partition) of X , where k 2 N is the number of clusters. We say that a clustering CX is center-based if there exists a set of centers µ , {µ1,µ2, . . . ,µk} ⇢ Rd such that the clustering is induced by the Voronoi diagram over those center points. The objective function of hard k-means is
Jkm(X ,µ,U) = nX
i=1
kX
j=1
Uij xi µj 2 2 , (1)
where U 2 {0, 1}n⇥k is the partition matrix, i.e., the membership weight Uij is 1 if xi 2 Cj , and 0 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.r.t. (µ,U).
In soft-clustering there is no partitioning of X . Instead, we describe the kth cluster of a 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}, as for hard clustering. The fuzzy k-means problem is defined as follows. Definition 1 (Fuzzy k-means). Let ↵ 1 and k 2 N. The fuzzy k-means problem is to find a set of means µ = {µ`}`2[k] ⇢ Rd and a membership matrix U 2 [0, 1]n⇥k minimizing
Jfm(X ,µ,U) , nX
i=1
kX
j=1
U ↵ ij xi µj 2 2 , (2)
subject to Pk j=1 Uij = 1 and 0 < Pn i=1 Uij < n, for all i 2 [n] and j 2 [k].
The parameter ↵ is called the fuzzifier, and is not subject to optimization. It can be shown that when ↵ ! 1, the fuzzy k-means solution coincides with that of the hard k-means problem. Similarly to the classical k-means problem, it is easy to optimize the means or memberships of fuzzy k-means, assuming the other part of the solution is fixed. Specifically, given a set of means µ, 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.
Uij =
2 4 kX
`=1
xi µj
kxi µ`k
!2/(↵ 1)3
5 1 (3) µj = Pn i=1 U ↵ ijxiPn
i=1 U ↵ ij
, (4)
for all i 2 [n], j 2 [k]. Iterating these solutions is known as the Lloyd’s algorithm [32], which provably lands on a 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 is unknown for the fuzzy formulation, it is strongly believed to be the case (e.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, 25]), the Xie–Beni [51] is the most widely used in the literature. This measure is defined as follows1
XB(X ,µ,U) , Jfm(X ,µ,U) nk ·mini 6=j µi µj 2 2 . (5)
For the rest of this paper, we denote a clustering by P , (µ,U), and we replace XB(X ,µ,U) by XB(X ,P). Accordingly, the optimal solution to the fuzzy k-means problem (Defintion 1) is denoted by P?. Finally, we say that a clustering P is consistent center-based if:
• Given membership weights U, the centers µ are given by (4). • The membership weights U are monotone, i.e., if
xi µj 2  x` µj 2 then Uij U`j , for any i, ` 2 [n] and j 2 [k].
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
1In (5) we divide by nk and not just by n, as in [51], where k was consider a fixed parameter. If k is allowed to grow (e.g., with n), then our definition makes more sense, as in general the numerator in (5) can grow with k.
are satisfied by the optimal solution P?, 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.

heading: 2.2 Domain expert/oracle
text: Our goal is to construct efficient algorithms with the aid of a domain expert who can give an approximate solution to the fuzzy k-means problem. Specifically, given a clustering P , a P-oracle is a function OP that answers queries consistent with P . One can think of such an oracle as a 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, it 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 j belong to the same cluster") was considered in [4]. Using a certain number of such same-cluster 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 2 (Membership-Oracle). A membership query asks the membership weight of an instance xi to a cluster j, i.e., Ofuzzy(i, j) = Uij .
Basically we ask the oracle for the membership weight of xi to cluster Cj . 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-oracle, 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 (Similarity-Oracle). A fuzzy pairwise similarity query asks the similarity of two distinct instances xp and xq i.e., Osim(p, q) = hUp,Uqi. A fuzzy triplet similarity query asks the similarity of three distinct instances xp,xq,xr, i.e., Otriplet(p, q, r) = P t2[k] UptUqtUrt.
We show in Appendix H, however, that each membership query can be simulated with a few similarity queries. From a 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, we prove the following result, informally stated, that is interesting in its own right. Lemma 1 (Membership to Similarity Queries Reduction, Informal). Suppose there exists an algorithm An with time complexity Tn that uses m 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(k3) fuzzy triplet similarity queries and O(km) fuzzy pairwise similarity queries, with a time complexity of Tn +O(mk + k3).
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/Inaccurate 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 Ofuzzy(i, j) = Uij + ⇣ij , where ⇣ij is a zero-mean random variable, and assume the errors to be independent, i.e., the answers are collected from independent crowd-workers. Then, in Appendix G 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, we opted to focus on the noiseless setting given in Definition 2.

heading: 2.3 Objective and learning problem
text: The goal of the algorithm is to find an approximated clustering that is consistent with the answers given to its queries. We have the following definition. Definition 4 (Oracle-Based Solver). Let (X ,P) be a clustering instance. An algorithm A is called a (✏1, ✏2,Q)-solver if it can approximate P by having access to X and making at most Q membership queries to a P-oracle. Specifically, for any ✏1, ✏2 > 0, the algorithm outputs bP such that maxj2[k] µj bµj 2  ✏1 and maxi2[n],j2[k] |Uij bUij |  ✏2. Such an algorithm is a polynomial (✏1, ✏2,Q)-solver if its time-complexity is polynomial in (n, k, ✏ 11 , ✏ 1 2 ).
We would like to emphasize that we seek an approximate solution rather than exact one. It is important to note Q = O(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 a sub-linear dependency of the query complexity on n and a polynomial dependency of the time complexity on n, 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 be a (✏1, ✏2,Q)-solver. Then,
XB(X ,P) XB(X , bP) 
XB(X ,P) ·O(✏1) +O(✏2)
mini 6=j µi µj 2 2
+ o
✏ 2 1 + ✏ 2 2
mini 6=j µi µj 2 2
! . (6)
The lemma above shows that if ✏1 and ✏2 are small enough, then the XB measure associated with an (✏1, ✏2,Q)-solver is “close" to the XB measure associated with P . Note, however, that the r.h.s. of (6) depends inversely on mini 6=j µi µj 2 2 . Accordingly, if for some clustering instance (X ,P) this quantity is too small compared to the estimation error, then the difference |XB(X ,P) XB(X , bP)| is 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 a set of points X and v 2 Rd, let ⇡v : [n] ! [n] be the permutation defined on [n] such that
v x⇡v(i) 2  v x⇡v(j) 2 , (7)
for all i < j 2 [n]. To wit, ⇡v is the ranking of the elements in X when they are sorted in ascending order w.r.t. to their distance from v. Then, we let 2 R+ be the maximum positive number such that for all j 2 [k],
⇡bµ = ⇡µj , 8bµ 2 B(µj , ). (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
P i2[n] Uij , for all j 2 [k], and a parameter 2 R+ by , minj2[k] kn 1 ·P
i2[n] Uij . Accordingly, in terms of , the minimum cluster membership size is at least n/k. Notice that must be less than unity since P i,j Uij = n, and there must exist at least one cluster whose membership size is at most n/k. We mention that was introduced in [18] as well.

heading: 3 Algorithms and theoretical guarantees

heading: 3.1 Two-Phase algorithm
text: We start by providing a non-formal description of our algorithm, whose pseudocode is 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 [n] with replacement, and denote the obtained samples by S . The value of m is specified in Theorem 1 below. Subsequently, we query the membership weights Uij , for all i 2 S and j 2 [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 is 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 a reliable estimate of its center.
Algorithm 1 Parallel algorithm for approximating P . Input: X , Ofuzzy, ↵, m, and ⌘. Output: An estimate bP . 1: Let S be a set of m elements sampled at random
from [n] with replacement. 2: Query Ofuzzy(i, j), 8i 2 S, j 2 [k]. 3: Compute bµj = P i2S U ↵ ijxiP
i2S U ↵ ij , 8j 2 [k]. 4: for j = 1, 2, . . . , k do 5: {bUij}ni=1 MEMBERSHIP(X , bµj ,↵, ⌘). 6: bUij bUij + 1 Pk j=1 bUij k , 8i 2 [n]. 7: end for
Algorithm 2 MEMBERSHIP(X , bµj ,↵, ⌘) Input: X , and Ofuzzy. Output: An estimate {bUij}ni=1. 1: Find ⇡bµj w.r.t. X . 2: for s = 0, 1, . . . , 1/⌘ do 3: Find `s = argmaxi2[n]U⇡bµj (i)j s⌘ using
BINARYSEARCH(X ,⇡bµj , s⌘). 4: end for 5: for s = 0, 1, 2, . . . , 1/⌘ do 6: for i = `s, `s 1, . . . , , `(s+1) + 1 do 7: Set bU⇡bµj (i)j = s⌘. 8: end for 9: end for
Algorithm 3 BINARYSEARCH(X ,⇡, x) Input: Ofuzzy. 1: Set low = 1 and high = n. 2: while low 6= high do 3: Set mid = d(low + high)/2e. 4: Query Ofuzzy(⇡(mid), j). 5: if U⇡(mid)j x then 6: Set low = mid. 7: else 8: Set high = mid 1. 9: end if 10: end while Next, using the approximated centers, we approximate the membership weights of every element up to a precision of ⌘ by using Algorithm 2. To that end, in the first step of this algorithm, we sort the elements of X in an ascending order according to their distance from the estimated center. Accordingly, if the estimation error of the centers ✏ satisfies ✏  , then (8) implies that the obtained ordering of elements after sorting from the estimated centers is same as the true ordering of the elements obtained by sorting according to distance (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 j 2 [k] the membership weights U⇡bµj(i)j are non-increasing in i. Therefore, for any j 2 [k] using the binary search in Algorithm 3, we find the maximum index `s such that U⇡bµj(`s)j is larger than s⌘, for s 2 {0, 1, . . . , 1/⌘}. This will create an ⌘-spaced grid, and we approximate each membership weight in accordance to the cell it falls into. Specifically, we assign bU⇡bµj(t)j = s⌘, for all t 2 [`s, `s 1, . . . , `s+1 + 1]. Clearly, the estimation error is at most ⌘. Overall, each binary search step takes O(log n) queries, and therefore the total query complexity of this step is O(log n/⌘). Finally, Step 6 transforms bUij to ensure thatPn
i=1 bUij = 1, for j 2 [k]. We have the following result, the detailed proof of which is delegated to Appendix C. Theorem 1. Let (X ,P) be a consistent center-based clustering instance, and recall the definitions of 2 R+ and 2 (0, 1). Pick ✏  , ⌘ 2 (0, 1), and 2 (0, 1). Take as input to Algorithm 1 m = c ⇣ Rk↵
✏ ↵
⌘4 log k , for some constant c > 0. Then, with probability at least 1 , Algorithm 1 is (✏, ⌘,Q)-
solver using Q = O ⇣ R4k4↵+1
(✏ ↵)4 log k + k logn ⌘
⌘ membership queries. Furthermore, Algorithm 1
time-complexity is of order O ⇣ kn log n+ dR 4k4↵+1
(✏ ↵)4 log k + k logn ⌘
⌘ .
Proof Sketch of Theorem 1. To prove Theorem 1 we first show that with high probability, Steps 1–4 in Algorithm 1 output an ✏-approximation for all centers. To that end, we first show in Lemma 6 that for a given cluster j 2 [k], with probability 1 ,
µj bµj 2 2  4R2 Y2 q c m log 1 , where Y ,
minj2[k] 1 n P i2[n] U ↵ ij . This result follows by noticing that both the numerator and denominator of bµj are unbiased estimates of the corresponding numerator and denominator of µj in (4). Representing bµj as a sum of the true underlying center µj and a certain error term, the generalized Hoeffding’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 8 that
bµj µj 2  ✏, for all j 2 [k],
if 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, we show in
Lemma 7 that Algorithm 2 estimates the corresponding membership weights within a certain range of error with high probability. Specifically, for a given cluster j, we prove that Algorithm 2 outputs bUij , for i 2 [n], such that 0  Uij bUij  ⌘ and bUij 2 {0, ⌘, 2⌘, . . . , 1}, 8i 2 [n], using O (log n/⌘) queries to the membership-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 O(km+ k log n/⌘).
Note that both the query and computational complexities in Theorem 1 exhibit an exponential dependency on the “fuzzifier" ↵. As mentioned in Subsection 2.1, this parameter is not subject to optimization and, usually, practitioners pick ↵ = 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. It seems that the value of ↵ is influenced by the structure of the dataset, i.e., the number of clusters and the distribution of each cluster. Currently, a definite answer on how to pick ↵ is unknown. Indeed, since there is no baseline, one cannot decide which value of ↵ is preferable. Note also that despite the fact that our query complexity naturally depend on ↵, it cannot be used to determine the “best" value of ↵. Assuming the existence of a ground truth, in Appendix F we compare the clustering accuracy for different values of ↵ on a real-world dataset.

heading: 3.2 Sequential algorithm
text: As mentioned in the previous subsection, the main drawback faced by Algorithm 1 is its undesirable strong dependency on . 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 t1, having the maximal total membership weight P i2S U ↵ ij , 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 t1 using Algorithm 2 such that the estimate is a multiple of ⌘1 and further, the estimate has an additive error of at most ⌘1, 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 definitions of 2 R+ and 2 (0, 1). Take m = c Rk↵
✏
4 log 2k , r = cR4k4↵
✏4 4↵ 4 log 4k ⌘1 , for some constant c > 0, and any 2 (0, 1). Then, with probability at least 1 , Algorithm 4 is (✏, ⌘2,Q)-solver using Q = O ⇣ R4k4↵+1
⌘1✏4 4↵ 4 log 4k⌘1 + k logn ⌘1 + k logn⌘2
⌘ membership queries, for any
chosen ✏  and ⌘2  ⌘1  1k ⇣ 1 k ⌘ . Furthermore, Algorithm 4 time-complexity is of order
O
⇣ dR4k4↵+1
⌘1✏4 4↵ 4 log 4k⌘1 + k logn ⌘1 + k logn⌘2 + kn log n ⌘ .
The proof of Theorem 2 follows from a technically complicated induction. Due to space limitations, the details have been delegated to Appendix D and below, we provide only a short sketch.
Proof Sketch of Theorem 2. Suppose that we have approximated the means of `  k clusters, indexed by T` , {t1, t2, . . . , t`}, with an estimation error at most ✏  , and further approximated the membership weights of every element in X for all clusters indexed by T`, up to an additive error ⌘1. The leftover clusters, indexed by [k] \ T`, are the unprocessed clusters. The above implies that we can also approximate the sum P j2[`] Uitj , for each i 2 X , up to an additive error `⌘1. Note that, since bUitj is a multiple of ⌘1 for all j 2 [`], P j2[`] bUitj must also be a multiple of ⌘1. Subsequently, we partition X into bins, where the elements in a particular bin have the same approximated sum of membership weights. Formally, let ⌃ , {0, 1, . . . , 1/⌘1}. For each s 2 ⌃, we define Xs , {i 2 [n] : P j2[`]
bUitj = s⌘1} to be the sth bin. Then, in Steps 9-10 of Algorithm 4, we randomly sample min(r, |Xs|) elements from each bin with replacement, and denote the resulted sub-sampled set by Ys. The value of r 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.e., P j2[k]\[`] Uitj is large. Given these sub-sampled sets, we query the
membership weights Uij , for all i 2 [s2⌃Ys and j 2 [k] \ T`. 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 (`+ 1)th cluster, and its approximated center are given as follows,
t`+1 , argmax j2[k]\T`
X
s2⌃
|Xs|
r
X
i2Ys
U ↵ ij and bµt`+1 ,
P s2⌃ |Xs| r P i2Ys U
↵ it`+1xiP
s2⌃ |Xs| r P i2Ys U ↵ it`+1 . (9)
We choose the number of samples r 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 ⌘2  ⌘1.
Algorithm 4 Sequential algorithm for approximating P . Input: X , Ofuzzy, ↵, m, r, ⌘1, and ⌘2. Output: An estimate bP . 1: Let S be a set of m elements sampled at random
from [n] with replacement. 2: Query Ofuzzy(i, j), 8i 2 S, j 2 [k]. 3: t1 = argmaxj2[k] P i2S U ↵ ij . 4: Compute bµt1 = P i2S U ↵ it1 xiP i2S U
↵ it1 . 5: for ` = 1, 2, . . . , k 1 do 6: {bUi,`}ni=1 MEMBERSHIP(X , bµt` ,↵, ⌘1). 7: Set Xs , {i 2 [n] : P j2[`]
bUitj = s⌘1} for s 2 {0, 1, . . . , 1/⌘1}.
8: for s = 0, 1, . . . , 1/⌘1 do 9: Let Ys be a set of min(r, |Xs|) elements sam-
pled at random from Xs with replacement. 10: end for 11: Compute t`+1 using (9). 12: Compute bµt`+1 using (9). 13: end for 14: for j = 1, 2, . . . , k do 15: {bUij}ni=1 MEMBERSHIP(X , bµj ,↵, ⌘2). 16: bUij bUij + 1 Pk j=1 bUij k , 8i 2 [n]. 17: end for
Comparing Theorems 1 and 2 we see that the sequential algorithm has a more graceful dependency on , the size of the smallest cluster. On the other hand, the query complexity of the two-phase algorithm is better in terms of k (recall that ⌘1  1/k for the sequential algorithm). Note that the query complexity of the sequential algorithm still has some dependency on . This stems from the fact that we estimate the membership weights up to a precision of ⌘1, which might be too large if there exists a cluster j such that maxi2[n] Uij  ⌘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 . Due to space limitation, the details are given in Appendix E, but we state here our main conclusion and provide a short sketch of the proof. Theorem 3. Let (X ,P) be a consistent center-based clustering instance, recall the definition of 2 R+ in (8), and let k = 2. Then, with probability at least 1 , Al-
gorithm 5 with m = O ✓⇣
R ✏
⌘4 log 4 ◆ and r = O ⇣ R4
✏4 log 2 ⌘
⌘ is a (✏, ⌘,Q)-solver us-
ing Q = O ⇣
R4 logn log(1/⌘ ) ✏4 + log 2 n+ logn⌘
⌘ membership queries, for any chosen ✏ 
, 2 (0, 1) and ⌘ > 0. Furthermore, Algorithm 5 time-complexity is of order O ⇣ n log n+ dR
4 logn log(1/⌘ ) ✏4 + log 2 n+ logn⌘
⌘ .
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 t1 2 {1, 2} the index of the larger cluster and t2 2 {1, 2} the index of the smaller cluster, i.e., P i2S U ↵ it1 > P i2S U ↵ it2 . The algorithm works as follows. We start by computing an estimate bµt1 for the center of the largest cluster t1. Corollary 4 shows that O (R/✏)4 log(4/ ) membership queries are needed to guarantee that
bµt1 µt1 2  ✏. Now, the
main novelty in Algorithm 5 is a non-trivial querying scheme used to estimate the memberships of the second cluster, Uit2 , for all i 2 [n], using the center estimated for the first cluster t1. Note that for the special case of two clusters, querying Uit1 reveals Uit2 since Uit1 + Uit2 = 1. While, in the sequential algorithm, we always approximated the membership weights using bins of fixed size ⌘1, here, we will approximate Uit2 with bins whose size is data-dependent. The reason for using variable bin sizes rather than fixed size bins is that with the latter we 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 t2, while querying membership weights to the larger cluster t1, allows us to get around this issue completely; this results in a theoretical guarantee that is completely independent of .
Algorithm 5 Sequential algorithm for approximating P with two clusters Input: X , Ofuzzy, ↵, m, r, and ⌘.
1: Let S be a set of m elements sampled at random from [n] with replacement. 2: Query Ofuzzy(i, j) and store Uij for all j 2 {1, 2}. 3: Choose t1 = argmaxj2{1,2} P i2S U ↵ ij . 4: Compute estimator bµt1 = P i2S U ↵ it1 xiP i2S U ↵ it1 . 5: Obtain P1,P2,X1,X2, . . . ,Xq and bUit2 for all i 2 [n] using MEMBERSHIP2(X , bµt1 ,↵) 6: for q = 1, 2, 3, . . . , 3 log n do 7: Let Yq be a set of r elements sampled at
random from Xq with replacement.
8: Query Ofuzzy(i, t2) to obtain Uit2 for all i 2 Yq
9: end for 10: Let Q be a set of r elements sampled at ran-
dom from P1 with replacement. 11: Query Ofuzzy(i, t2) to obtain Uit2 for all i 2
Q. 12: Compute bµt2 in (111). 13: for j = 1, 2 do 14: Run Alg MEMBERSHIP(X , bµj ,↵, ⌘, j) to update bUij for all i 2 [n]. 15: end for 16: Return bµ1, bµ2 and bUij 8 i 2 [n], j 2 {1, 2}.
We now describe Algorithm 7 used to estimate the membership weights of cluster t2. We start by sorting X in ascending order according to their distance from bµt1 , and initialize ⌘1 = U⇡bµt1 (n)t2 and p⌘1 , n. To wit, ⌘1 is the membership of the element farthest from bµt1 to the smaller cluster t2. For each q 2= {2, 3 . . . , 3 log n}, we set ⌘q = ⌘q 1/2, and then perform binary search to find p 0 ⌘q = argminj2[n]1[U⇡bµt1 (j)t2
⌘q]. Here, we should think of p0⌘q to be the index for which x⇡bµt1 (p 0 ⌘q
) is the element closest from bµt1 , such that its membership to the smaller cluster t2 is at least ⌘q. Now, if |p0⌘q p⌘q 1 | log n, we keep ⌘q unchanged, set p⌘q = p 0 ⌘q , and put all elements which are closer to bµt1 than x⇡bµt1 (p⌘q 1 ), but farther than x⇡bµt1 (p⌘q ) into a single bin. Notice that each such bin contains at least log n elements by definition. However, if p0⌘q is the same as p⌘q 1 , then the membership queries in the latter binary search to compute p0⌘q is wasteful. In order to fix this issue, we check if there are a sufficient number (at least log n) of elements between p0⌘q and p⌘q 1 . If there are not, then we set p⌘q such that the above condition is satisfied. More formally, if |p
0 ⌘q p⌘q 1 |  log n we update p⌘q = min(0, p⌘q 1 1 log n) and ⌘q = U⇡bµt1 (p⌘q )t2 . In other words, we set p⌘q such that there at least log n elements between p⌘q and p⌘q 1 , and accordingly, we set ⌘q to be the membership of ⇡bµt1 (p⌘q ) to the cluster t2. Subsequently, we query Uit2 for every element that is closer to bµt1 than x⇡bµt1 (p⌘q 1 ) but farther than x⇡bµt1 (p⌘q ). 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 x⇡bµt1 (p⌘q 1 ) and x⇡bµt1 (p⌘q ) are assigned a single bin.
To resolve the edge case, we put all those elements which are closer to bµt1 than x⇡bµt1 (p⌘3 log n ) into a separate bin. Let g be the total number of bins formed by this algorithm, and say Xj is the jth 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 is at most 3 log2 n (since each bin can contain at most log n special elements). Moreover, for any bin Xj not containing any special elements, we can show that maxi2Xj Uit2  2mini2Xj Uit2 , which should be contrasted with the guarantee we have for the sequential algorithm, i.e., for a particular bin Xj , |maxi2Xj Uit2 mini2Xj Uit2 |  ⌘1. Finally, we again sub-sample r elements from each such bin Xj with replacement, and denote the resulting subset by Yj . We approximate the center of the second cluster by
bµt2 = P j |Xj | r P i2Yj U ↵ it2xi + P i2P U ↵ it2xi
P j |Xj | r P i2Yj U ↵ it2 + P i2P U ↵ it2 , (10)
and show that the required r is independent of the cluster size.
Acknowledgements: This work is supported in part by NSF awards 2133484, 2127929, and 1934846.

Review summaries:
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.   Under 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.

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).  EDIT: I think the authors for their response; after reading it, I will leave my rating unchanged.

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

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.