Title: Clustering with Noisy Queries,
Abstract: In this paper, we initiate a rigorous theoretical study of clustering with
noisy queries (or a faulty oracle). 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
{\em 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 {\em 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 {\em
stochastic block model} where one has an incomplete stochastic block model
matrix to recover the clusters.