Paper Info
Title
Query Complexity of Clustering with Side Information.
Abstract
Suppose, we are given a set of n elements to be clustered into k (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "do two elements u and v belong to the same cluster?". The goal is to recover the optimum clustering by asking the minimum number of queries. In this paper, we provide a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and give strong information theoretic lower bounds, as well as nearly matching upper bounds. Most clustering problems come with a similarity matrix, which is used by an automated process to cluster similar points together. However, obtaining an ideal similarity function is extremely challenging due to ambiguity in data representation, poor data quality etc., and this is one of the primary reasons that makes clustering hard. To improve accuracy of clustering, a fruitful approach in recent years has been to ask a domain expert or crowd to obtain labeled data interactively. Many heuristics have been proposed, and all of these use a similarity function to come up with a querying strategy. Even so, there is a lack systematic theoretical study. Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering. A similarity matrix represents noisy pair-wise relationships such as one computed by some function on attributes of the elements. A natural noisy model is where similarity values are drawn independently from some arbitrary probability distribution f(+) when the underlying pair of elements belong to the same cluster, and from some f(-) otherwise. We show that given such a similarity matrix, the query complexity reduces drastically from circle minus(nk) (no similarity matrix) to O(k(2)log n/H-2(f(+)parallel to f(-)) where H-2 denotes the squared Hellinger divergence. Moreover, this is also information-theoretic optimal within an O(log n) factor. Our algorithms are all efficient, and parameter free, i.e., they work without any knowledge of k, f(+) and f(-), and only depend logarithmically with n. Our lower bounds could be of independent interest, and provide a general framework for proving lower bounds for classification problems in the interactive setting. Along the way, our work also reveals intriguing connection to popular community detection models such as the stochastic block model and opens up many avenues for interesting future research.
Year
Venue
DocType
2017
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017)
Conference
Volume
ISSN
Citations 
30
1049-5258
4
PageRank 
References 
Authors
0.41
22
2
Name
Order
Citations
PageRank
Arya Mazumdar130741.81
Barna Saha262637.56