Clustering with Noisy Queries
In this paper, we provide a rigorous theoretical study of clustering with noisy queries. Given a set of n elements, our goal is to recover the true clustering by asking minimum number of pairwise queries to an oracle. Oracle can answer queries of the form "do elements u and v belong to the same cluster?"-the queries can be asked interactively (adaptive queries), or non-adaptively up-front, but its answer can be erroneous with probability p. In this paper, we provide the first information theoretic lower bound on the number of queries for clustering with noisy oracle in both situations. We design novel algorithms that closely match this query complexity lower bound, even when the number of clusters is unknown. Moreover, we design computationally efficient algorithms both for the adaptive and non-adaptive settings. The problem captures/generalizes multiple application scenarios. It is directly motivated by the growing body of work that use crowdsourcing for entity resolution, a fundamental and challenging data mining task aimed to identify all records in a database referring to the same entity. Here crowd represents the noisy oracle, and the number of queries directly relates to the cost of crowdsourcing. Another application comes from the problem of sign edge prediction in social network, where social interactions can be both positive and negative, and one must identify the sign of all pair-wise interactions by querying a few pairs. Furthermore, clustering with noisy oracle is intimately connected to correlation clustering, leading to improvement therein. Finally, it introduces a new direction of study in the popular stochastic block model where one has an incomplete stochastic block model matrix to recover the clusters.
NOTE: I am reviewing two papers that appear to be by the same authors and on the same general topic.  The other one is on noiseless queries with additional side information.
This paper gives upper and lower bounds on the query complexity of clustering based on noisy pairwise comparisons.  While I am familiar with some of the related literature, my knowledge of it is far from complete, so it's a little hard to fully judge the value of the contributions.  One limitation is that the main result would be extremely easy to obtain if the noise were independent when sampling the same pair multiple times.  On the other hand, the case where the same noisy answer is always returned is well-motivated in certain applications.
My overall impression of both papers is that the contributions seem to be good (if correct), but the writing could do with a lot of work.  I acknowledge that the contributions are more important than the writing, but there are so many issues that my recommendation is still borderline.  It would have been very useful to have another round of reviews where the suggestions are checked, but I understand this is not allowed for NIPS.  
Here are some of my more significant comments:
- Many of the central results are not written precisely.  The order of quantification is Lemma 1 is unclear (e.g., Pr(for all v) vs. for all v, Pr(...)).  The last step in its proof only holds for sufficiently large k, whereas the lemma is stated for arbitrary k.  The appendix is full of theorems/lemmas/claims with the imprecise phrase "with high probability", and in some cases it seems to be crucial to specify the convergence rate (even if it's done in the proof, it should still appear in the formal statement).
- Near the bottom of p3, the runtime and query complexity are not consistent, with the latter exceeding the former in certain regimes like k = n^(1/6) or p very close to 1/2.  I guess this is because certain dependences were omitted in the runtime (which they shouldn't be without further statement).
- The appendices are often hard to follow.  The strange and somewhat unclear phrases "Suppose if possible" and "Let if possible" are used throughout.  Inequalities like the one at the end of Claim 2's proof appear questionable at first (e.g., when p is close to half), and the reader has to go back and find the definitions of c, c' (and check their dependence on p).  There are a lot of statements along the lines of "similarly to [something earlier]", which I trusted but wasn't certain of.
- The paper is FULL of grammar mistakes, typos, and strange wording.  Things like capitalization, plurals, spacing, and articles (a/an/the) are often wrong. Commas are consistently mis-used (e.g., they usually should not appear after statements like "let" / "we have" / "this means" / "assume that" / "is", and very rarely need to be used just before an equation).  Sentences shouldn't start with And/Or.  There are typos like "entrees", "once crucial".  The word "else" is used strangely (often "otherwise" would be better).  This list of issues is far from complete -- regardless of the decision, I strongly urge the authors to proof-read the paper with as much care as possible.
Here are some comments of a technical nature:
- The paper is so dense that I couldn't check the upper bound proof in as much detail as ideal.  I was reasonably convinced of the proof of the lower bound.
- In Section 2, I don't see why the first "balanced" condition is useful.  Even with a given maximum cluster size, the exact same problem as that described in the first few sentences can still occur, making the problem ill-posed.  I think you should only keep the condition on the minimum cluster size.
- The numerical section does not seem to be too valuable, mainly because it does not compare against any existing works or simple baselines.  Are your methods really the only ones that can be considered/implemented?
Some less significant comments:
- The second half of the abstract can be considerably shortened
- The algorithm descriptions are very wordy.  It might have been useful to accompany them with figures and/or an "Algorithm" environment.
- Sometimes extra citations are needed (e.g., runtime of heaviest weight subgraph, Turan's theorem, and maybe previous use of the TV->KL technique on p5 like Auer et al 1998 bandit paper)
- I would remove "initiate [a rigorous theoretical study]" from the abstract/intro.  Given that there are so many related works, I don't think this is suitable.  It is even less suitable to simultaneously say it in two different papers.
- In the formal problem statement "find Q subset of V x V" makes it sound like the algorithm is non-adaptive.
- The sentence "which might also be the aggregated..." is confusing and should be removed or reworded
- Many brackets are too small throughout the appendix
- In the Unknown k algorithm, l (which should be \ell?) is never updated, so k=2l always assigns the same value
- I would avoid phrases like "information theoretically optimal algorithm", which makes it sound like it is THE algorithm that minimizes the error probability.
[POST-AUTHOR FEEDBACK COMMENTS]
The authors clarified a few things in the responses, and I have updated the recommendation to acceptance.  I still hope that a very careful revision is done for the final version considering the above comments.  I can see that I was the only one of the 3 reviewers to have significant comments about the writing, but I am sure that some of these issues would make a difference to a lot more NIPS readers, particularly those coming from different academic backgrounds to the authors.
Some specific comments:
- The authors have the wrong idea if they feel that "issues like capitalization and misplaced commas" were deciding factors in the review.  These were mentioned at the end as something that should be revised, not as a reason for the borderline recommendation.
- I am still confused about the "balanced" condition and minimum/maximum cluster size.  My understanding is that if you only assume a bound on the maximum size, then the problem is in general ill-posed, by your example (definitions of C_1 and C_2) on lines 149-150.  If you only assume a bound on the minimum size, everything looks fine.  You could also assume both simultaneously, but this doesn't seem to be what you are doing (since on line 155 you write "either of" rather than "both of").   Consider re-wording/explaining more as needed.
- Please revise/re-word the runtime and query complexity on p3 -- if the stated runtime only holds for p = constant, then you should add something like "when p is constant".  I think cases like k = n^(1/6) (where samples seems to exceed runtime) might still look strange to some readers, but since there is no true contradiction, I don't insist on anything.
- It is important that theorems and lemmas are stated precisely (e.g., all assumptions are included like k being large or certain quantities behaving as constants, and convergence rates of probabilities are specified if they play an important role in the later analysis)
- Although it is not a major point, I will mention that I don't recall seeing "Suppose if possible" or "Let if possible" despite reading mathematical papers from many domains.  The latter in particular sounds very strange.  Even for the former, at least for me, a re-wording to something like "Suppose by way of contradiction that..." would be clearer.