Venue: NeurIPS 2021 Conference

Reviews:

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

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

Additionally, 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. 

In 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? 

Given the previous work of [4], I think that this paper is not strong enough for NeurIPS.
limitations_and_societal_impact: Yes.
review_title: null

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

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

limitations_and_societal_impact: This work is theoretical in nature.
review_title: null

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

Originality: 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:
- 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. 
- 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.
- 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.
Some potential shortcomings:
- 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?
- 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?
- The sequential algorithm reduces some dependency on \beta but takes a lot of space. The authors can consider compressing this section.
- 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.

Quality: It seems to me that the submission is technically sound and the theoretical claims are well supported. 

Clarity: 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.

Significance: 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.

Minor Comments:
- P5, Line 182, "Our goal is to construct efficient algorithms which with the aid of a domain expert ...": the "which" should be deleted.
- 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.
- 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.

limitations_and_societal_impact: The authors addressed these aspects, but it is postponed until the supplementary materials.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).

EDIT: I think the authors for their response; after reading it, I will leave my rating unchanged.
main_review: TLDR: I think this is a good paper and deserves acceptance.

Originality: 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:

https://proceedings.neurips.cc/paper/2020/hash/6950aa02ae8613af620668146dd11840-Abstract.html (NeurIPS 2020)
https://arxiv.org/abs/2102.00504 (to appear in COLT 21, according to the official list of accepted papers)

Quality: 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.

Clarity: 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.

Significance: 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.



DETAILED COMMENTS:

L66: "does" -> "do"

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

L118-128: there are some recent works that appear to be even more relevant to this discussion (see above).

L142: "corresponds to" the Voronoi diagram sounds a bit weird; perhaps "is induced by"?

L149: "take" -> "take on"

L168: can you explain the XB measure? It's obscure.

L182: "which with the aid... problem." something is missing in this sentence.

L208: the thing of the triplets is interesting. Can you spend a few more words on how it works?

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

L248: "a couple of notations", I think "notation" is uncountable.

L255: "for all $j \in k]" the left bracket is missing.

L282-295: the explanation here is not clear. Can you try making it clearer?

L287: "decreasing", you mean nonincreasing, right? That is, ties are allowed I suppose?

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

L311: "up to a certain controllable" what does this mean?




limitations_and_societal_impact: Limitations are adequately discussed. There is no foreseeable societal impact.
review_title: null

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)