Clustering via Crowdsourcing

arXiv:1604.01839v1 [] 7 Apr 2016

Arya Mazumdar∗
Barna Saha†
College of Information & Computer Science
University of Massachusetts Amherst
Amherst, MA, 01002

Abstract
In recent years, crowdsourcing, aka human aided computation has emerged as an eﬀective
platform for solving problems that are considered complex for machines alone. Using human
is time-consuming and costly due to monetary compensations. Therefore, a crowd based
algorithm must judiciously use any information computed through an automated process,
and ask minimum number of questions to the crowd adaptively.
One such problem which has received signiﬁcant attention is entity resolution. Formally,
we are given a graph G = (V, E) with unknown edge set E where G is a union of k (again
unknown, but typically large O(nα ), for α > 0) disjoint cliques Gi (Vi , Ei ), i = 1, . . . , k. The
goal is to retrieve the sets Vi s by making minimum number of pair-wise queries V ×V → {±1}
to an oracle (the crowd). When the answer to each query is correct, e.g. via resampling,
then this reduces to ﬁnding connected components in a graph. On the other hand, when
crowd answers may be incorrect, it corresponds to clustering over minimum number of
noisy inputs. Even, with perfect answers, a simple lower and upper bound of Θ(nk) on
query complexity can be shown. A major contribution of this paper is to reduce the query
complexity to linear or even sublinear in n when mild side information is provided by a
machine, and even in presence of crowd errors which are not correctable via resampling. We
develop new information theoretic lower bounds on the query complexity of clustering with
side information and errors, and our upper bounds closely match with them. Our algorithms
are naturally parallelizable, and also give near-optimal bounds on the number of adaptive
rounds required to match the query complexity.

∗
University of Massachusetts Amherst, arya@cs.umass.edu. This work is supported in part by an NSF
CAREER award CCF 1453121 and NSF award CCF 1526763.
†
University of Massachusetts Amherst, barna@cs.umass.edu.This work is partially supported by a NSF CCF
1464310 grant, a Yahoo ACE Award and a Google Faculty Research Award.

0

1

Introduction

Consider we have an undirected graph G(V ≡ [n], E), [n] ≡ {1, . . . , n}, such that G is a union
of k disjoint cliques Gi (Vi , Ei ), i = 1, . . . , k, but the subsets Vi ⊂ [n], k and E are unknown to
us. We want to make minimum number of adaptive pair-wise queries from V × V to an oracle,
and recover the clusters. Suppose, in addition, we are also given a noisy weighted similarity
matrix W = {wi,j } of G, where wi,j is drawn from a probability distribution f+ if i and j belong
to the same cluster, and else from f− . However, the algorithm designer does not know either
f+ or f− . How does having this side information aﬀect the number of queries to recover the
clusters, which in this scenario are the hidden connected components of G? To add to it, let
us also consider the case when some of the answers to the queries are erroneous. We want to
recover the clusters with minimum number of noisy inputs possibly with the help of some side
information. In the applications that motivate this problem, the oracle is the crowd.
In the last few years, crowdsourcing has emerged as an eﬀective solution for large-scale
“micro-tasks”. Usually, the micro-tasks that are accomplished using crowdsourcing tend to
be those that computers cannot solve very eﬀectively, but are fairly trivial for humans with
no specialized training. Consider for example six places, all named after John F. Kennedy 1 :
(ra ) John F. Kennedy International Airport, (rb ) JFK Airport, (rc ) Kennedy Airport, NY (rd ) John
F. Kennedy Memorial Airport, (re ) Kennedy Memorial Airport, WI, (rf ) John F. Kennedy Memorial
Plaza. Humans can determine using domain knowledge that the above six places correspond to
three diﬀerent entities: ra , rb , and rc refer to one entity, rd and re refer to a second entity, and rf
refers to a third entity. However, for a computer, it is hard to distinguish them. This problem
known as entity resolution is a basic task in classiﬁcation, data mining and database management
[26, 23, 29]. It has many alias in literature, and also known as coreference/identity/name/record
resolution, entity disambiguation/linking, duplicate detection, deduplication, record matching
etc. There are several books that just focus on this topic [17, 37]. For a comprehensive study
and applications, see [29].
Starting with the work of Marcus et al. [43], there has been a ﬂurry of works that have aimed
at using human power for entity resolution [31, 51, 22, 52, 27, 50, 21, 30, 39]. Experimental
results using crowdsourcing platforms such as Amazon Mechanical Turk have exceeded the
machine only performance [51, 52]. In all of these works, some computer generated pair-wise
similarity matrix is used to order the questions to crowd. Using human in large scale experiments
is costly due to monetary compensation paid to them, in addition to being time consuming.
Therefore, naturally these works either implicitly or explicitly aim to minimize the number
of queries to crowd. Assuming the crowd returns answers correctly, entity resolution using
crowdsourcing corresponds exactly to the task of ﬁnding connected components of G with
minimum number of adaptive queries to V × V . Typically k is large [51, 52, 27, 50], and we
can, not necessarily, take k ≥ nα for some constant α ∈ [0, 1].
It is straightforward to obtain an upper bound of nk on the number of queries: simply ask
one question per cluster for each vertex, and is achievable even when k is unknown. Except for
this observation [51, 22], no other theoretical guarantees on the query complexity were known
so far. Unfortunately, Ω(nk) is also a lower bound [22]. Bounding query complexity of basic
problems like selection and sorting have received signiﬁcant attention in the theoretical computer
science community [25, 10, 4, 9]. Finding connected components is the most fundamental graph
problem, and given the matching upper and lower bounds, there seems to be a roadblock in
improving its query complexity beyond nk.
In contrast, the heuristics developed in practice often perform much better, and all of them
use some computer generated similarity matrix to guide them in selecting the next question to
ask. We call this crowdsourcing using side information. So, we are given a similarity matrix
W = {wi,j }i,j∈V ×V , which is a noisy version of the original adjacency matrix of G as discussed
1

http://en.wikipedia.org/wiki/Memorials_to_John_F._Kennedy

1

in the beginning. Many problems such as sorting, selection, rank aggregation etc. have been
studied using noisy input where noise is drawn from a distribution [11, 12, 41]. Many probabilistic generative models, such as stochastic block model, are known for clustering [1, 35, 16, 45].
However, all of these works assume the underlying distributions are known and use that information to design algorithms. Moreover, none of them consider query complexity while dealing
with noisy input.
We show that with side information, even with unknown f+ and f− , a drastic reduction
in query complexity is possible. We propose a randomized algorithm that reduces the number
2
of queries from O(nk) to Õ( ∆(fk+ ,f− ) ), where ∆(f+ , f− ) ≡ D(f+ kf− ) + D(f− kf+ ) and D(pkq)
is the Kullback-Leibler divergence between the probability distributions p,
 and2 q, and
 recovers
the clusters accurately with high probability. Interestingly, we show Ω ∆(fk+ ,f− ) is also an
information-theoretic lower bound, thus matching the query complexity upper bound within
a logarithmic factor. This lower bound could be of independent interest, and may lead to
other lower bounds in related communication complexity models. To obtain the clusters accurately
with probability
1, we propose a Las Vegas algorithm with expected query complexity


k2
Õ n + ∆(f+ ,f− ) which again matches the corresponding lower bound.
So far, we have considered the case when crowd answers are accurate. It is possible that
crowd answers contain errors, and remain erroneous even after repeating a question multiple
times. That is, resampling, repeatedly asking the same question and taking the majority vote,
does not help much. Such observation has been reported in [50, 34] where resampling only
reduced errors by ∼ 20%. Crowd workers often use the same source (e.g., Google) to answer
questions. Therefore, if the source is not authentic, many workers may give the same wrong
answer to a single question. Suppose that error probability is p < 12 . Under such crowd error
model, our problem becomes that of clustering with noisy input, where this noisy input itself
is obtained via adaptively querying the crowd.
We give the ﬁrst information theoretic lower bounds in this model to obtain the maximum likelihood estimator, and again provide nearly matching upper bounds with and without
side information. Side information helps us to drastically reduce the query complexity, from
k2
nk
) to Õ( D(pk1−p)∆(f
) where D(pk1 − p) = (1 − 2p) log 1−p
Õ( D(pk(1−p))
p . An intriguing fact
+ ,f− )
log n

about this algorithm is that it has running time O(k D(pk1−p) ), and assuming the conjectured
hardness of ﬁnding planted clique from an Erdős-Rényi random graph [36], this running time
cannot be improved2 . However, if we are willing to pay a bit more on the query complexity,
then the running time can be made into polynomial. This also provides a better bound on an
oft-studied clustering problem, correlation clustering over noisy input [44, 8]. While prior works
have considered sorting without resampling [12], these are the ﬁrst results to consider crowd
errors for a natural clustering problem.
The algorithms proposed in this work are all intuitive, easily implementable, and can be
parallelized. They do not assume any knowledge on the value of k, or the underlying distributions f+ and f− . On the otherhand, our information theoretic lower bounds work even with
the complete knowledge of k, f+ , f− . While queries to crowd can be made adaptively, it is also
important to minimize the number of adaptive rounds required maintaining the query upper
bound. Low round complexity helps to obtain results faster. We show that all our algorithms
extend nicely to obtain close to optimal round complexity as well. Recently such results have
been obtained for sorting (without any side information) [10]. Our work extends nicely to two
more fundamental problems: ﬁnding connected components, and noisy clustering.
2

Note that a query complexity bound does not necessarily removes the possibility of a super-polynomial
running time.

2

1.1

Related Work

In a recent work [10], Braverman, Mao and Weinberg studied the round complexity of selection
and obtaining the top-k and bottom-k elements when crowd answers are all correct, or are
erroneous with probability 12 − λ2 , or erased with probability 1 − λ, for some λ > 0. They
do not consider any side information. There is an extensive literature of algorithms in the
TCS community where the goal is to do either selection or sorting with O(n) comparisons in
the fewest interactive rounds, aka parallel algorithms for sorting [49, 47, 5, 6, 4, 9]. However,
those works do not consider any erroneous comparisons, and of course do not incorporate side
information. Feige et al., study the depth of noisy decision tree for simple boolean functions,
and selection, sorting, ranking etc. [25], but not with any side information. Parallel algorithms
for ﬁnding connected components and clustering have similarly received a huge deal of attention
[28, 33, 18, 46]. Neither those works, nor their modern map-reduce counterparts [40, 24, 32, 2]
study query complexity, or noisy input. There is an active body of work dealing with sorting and
rank aggregation with noisy input under various models of noise generation [11, 12, 41]. However
these works aim to recover the maximum likelihood ordering without any querying. Similarly,
clustering algorithms like correlation clustering has been studied under various random and
semirandom noise models without any active querying [8, 44, 42]. Stochastic block model is
another such noisy model which has recently received a great deal of attention [1, 35, 16, 45],
but again prior to this, no work has considered the querying capability when dealing with noisy
input. In all these works, the noise model is known to the algorithm designer, since otherwise
the problems become NP-Hard [11, 8, 3].
In more applied domains, many frameworks have been developed to leverage humans for performing entity resolution [52, 31]. Wang et al. [52] describe a hybrid human-machine framework
CrowdER, that automatically detects pairs or clusters that have a high likelihood of matching
based on a similarity function, which are then veriﬁed by humans. Use of similarity function
is common across all these works to obtain querying strategies [31, 51], but hardly any provide
bounds on the query complexity. The only exceptions are [51, 22] where a simple nk bound on
the query complexity has been derived when crowd returns correct answers, and no side information is available. This is also a lower bound even for randomized algorithms [22]. Firmani
et al. [27] analyzed the algorithms of [52] and [51] under a very stringent noise model.
To deal with the possibility that the crowdsourced oracle may give wrong answers, there are
simple majority voting mechanisms or more complicated heuristic techniques [50, 21, 30, 39]
to handle such errors. No theoretical guarantees exist in any of these works. Davidson et al.,
consider a variable error model where clustering is based on a numerical value–in that case
clusters are intervals with few jumps (errors), and the queries are unary (ask for value) [22].
This error model is not relevant for pair-wise comparison queries.

1.2

Results and Techniques

Problem (Crowd-Cluster). Consider an undirected graph G(V ≡ [n], E), such that G is a union
of k disjoint cliques (clusters) Gi (Vi , Ei ), i = 1, . . . , k, where k, the subsets Vi ⊆ [n] and E
are unknown. There is an oracle O : V × V → {±1}, which takes as input a pair of vertices
u, v ∈ V × V , and returns either +1 or −1. Let O(Q), Q ⊆ V × V correspond to oracle answers
to all pairwise queries in Q. The queries in Q can be done adaptively.
The adjacency matrix of G is a block-diagonal matrix. Let us denote this matrix by A = (ai,j ).
Consider W , an n × n matrix, which is the noisy version of the matrix A. Assume that the
(u, v)th entry of the matrix W , wu,v , is a nonnegative random variable in [0, 1] drawn from a
probability density or mass function f+ for ai,j = 1, and is drawn from a probability density or
mass function f− if ai,j = 0. f+ and f− are unknown.
• Crowd-Cluster with Perfect Oracle Here O(u, v) = +1 iﬀ u and v belong to the same
cluster and O(u, v) = −1 iﬀ u and v belong to diﬀerent clusters.
3

1. Without Side Information. Given V , ﬁnd Q ⊆ V × V such that |Q| is minimum,
and from O(Q) it is possible to recover Vi , i = 1, 2, ..., k.
2. With Side Information. Given V and W , ﬁnd Q ⊆ V × V such that |Q| is
minimum, and from O(Q) it is possible to recover Vi , i = 1, 2, ..., k.

• Crowd-Cluster with Faulty Oracle There is an error parameter p = 21 −λ for some λ > 0.
We denote this oracle by Op . Here if u, v belong to the same cluster then Op (u, v) = +1
with probability 1 − p and Op (u, v) = −1 with probability p. On the otherhand, if u, v do
not belong to the same cluster then Op (u, v) = −1 with probability 1 − p and Op (u, v) = +1
with probability p (in information theory literature, such oracle is called binary symmetric
channel).
1. Without Side Information. Given V , ﬁnd Q ⊆ V × V such that |Q| is minimum,
and from Op (Q) it is possible to recover Vi , i = 1, 2, ..., k with high probability.
2. With Side Information. Given V and W , ﬁnd Q ⊆ V × V such that |Q| is minimum, and from Op (Q) it is possible to recover Vi , i = 1, 2, ..., k with high probability.

• Crowd-Cluster with Round Complexity Consider all the above problems where O (similarly Op ) can answer to n log n queries simultaneously, and the goal is to minimize the
number of adaptive rounds of queries required to recover the clusters.
1.2.1

Lower Bounds

When no side information is available, it is somewhat straight-forward to have a lower bound
on the query complexity if the oracle is perfect. Indeed, in that case the query complexity of
Crowd-Cluster is Ω(nk) where n is the total number of elements and k is the number of clusters.
To see this, note that, any algorithm can be provided with a clustering designed adversarially
in the following way. First, k elements residing in k diﬀerent clusters are revealed to the
algorithm. For a vertex among the remaining n − k vertices, if the algorithm makes any less
than k − 2 queries, the adversary still can place the vertex in one of the remaining 2 clusters–
resulting in a query complexity of (n − k)(k − 1). This argument can be extended towards
randomized algorithms as well, by using Yao’s min-max principal, and has been done in [22].
However [22] left open the case of proving lower bound for randomized algorithms when the
clusters are nearly balanced (ratio between the minimum and maximum cluster size is bounded).
One of the lower bound results proved in this paper resolves it.
Our main technical results for perfect oracle are for Crowd-Cluster with side information.
Our lower bound results are information theoretic, and can be summarized in the following
theorem.
Theorem 1. Any (possibly randomized) algorithm
with the knowledge of f+ , f− , and the number

k2
of clusters k, that does not perform at least Ω ∆(f+ ,f− ) queries, ∆(f+ , f− ) > 0, will be unable
to return the correct clustering with probability at least

1
10 .

(Proof in Sec. 4.1).

Corollary 1. Any (possibly randomized but Las Vegas) algorithmwith the knowledge of f+ , f− ,
k2
queries,
and the number of clusters k, that does not perform at least Ω n + min{1,∆(f
+ ,f− )}
∆(f+ , f− ) > 0, will be unable to return the correct clustering. (Proof in Sec. 4.1).
The main high-level technique is the following. Suppose, a vertex is to be assigned to a
cluster. We have some side-information and answers to queries involving this vertex at hand.
Let these constitute a random variable X that we have observed. Assuming that there are k
possible clusters to assign this vertex to, we have a k-hypothesis testing problem. By observing
X, we have to decide which of the k diﬀerent distributions (corresponding to the vertex being
4

in k diﬀerent clusters) it is coming from. If the distributions are very close (in the sense of total
variation distance or divergence), then we are bound to make an error in deciding.
We can compare this problem of assigning a vertex to one of the k-clusters to ﬁnding a
biased coin among k coins. In the later problem, we are asked to ﬁnd out the minimum number
of coin tosses needed for correct identiﬁcation. This type of idea has previously been applied
to design adversarial strategies that lead to lower bounds on average regret for the multi-arm
bandit problem (see, [7, 13]).
The problem that we have in hand, for lower bound on query-complexity, is substantially
diﬀerent. It becomes a nontrivial task to identify the correct input and design the set-up so
that we can handle the problem in the framework of ﬁnding a biased coin. The key insight here
is that, given a vertex, the combined side-information pertaining to this vertex and a cluster
plays the role of tossing a particular coin (multiple times) in the coin-ﬁnding problem. However
the liberty of an algorithm designer to query freely creates the main challenge.
For faulty oracle, note that we are not allowed to ask the same question multiple times to
get the correct answer with high probability. This changes the situation quite a bit, though
in some sense this is closer to coin-tossing experiment than the previous one as we handle
binary random variables here (the answer to the queries). We ﬁrst note that, for faulty-oracle,
even for probabilistic recovery a minimum size bound on cluster size is required. For example,
k−2
consider the following two diﬀerent clusterings. C1 : V = ⊔i=1
Vi ⊔ {v1 , v2 } ⊔ {v3 } and C2 :
k−2
V = ⊔i=1 Vi ⊔ {v1 } ⊔ {v2 , v3 }. Now if one of these two clusterings are given two us uniformly
at random, no matter how many queries we do, we will fail to recover the correct cluster with
probability at least p. Our lower bound result works even when all the clusters are close to their
average size (which is nk ), and resolves a question from [22] for p = 0 case.
This removes the constraint on the algorithm designer on how many times a cluster can be
queried with a vertex and the algorithms can have greater ﬂexibility. While we have to show
that enough number of queries must be made with a large number of vertices V ′ ⊂ V , either
of the conditions on minimum or maximum sizes of a cluster ensures that V ′ contains enough
vertices that do not satisfy this query requirement.
Theorem 2. Assume either of the following cases:
• the maximum size of a cluster is ≤

4n
k .

• the minimum size of a cluster is ≥

n
20k .

For a clustering
that satisﬁes
either of the above two conditions, any (randomized) algorithm


nk
must make Ω D(pk1−p) queries to recover the correct clusters with probability 0.9 when p > 0.
For p = 0 any (randomized) algorithm must make Ω(nk) queries to recover the correct clusters
with probability 0.9. (Proof in Sec. 6.1.1).
We believe that our lower bound techniques are of independent interest, and can spur new
lower bounds for communication complexity problems.
1.2.2

Upper Bounds

Our upper bound results are inspired by the lower bounds. For Crowd-Cluster with perfect oracle,
a straight forward algorithm achieves a nk query complexity. One of our main contributions
is a drasticR reduction in query
complexity of Crowd-Cluster when side information is provided.
R
Let µ+ ≡ xf+ (x)dx, µ− ≡ xf− (x)dx. Our ﬁrst theorem that assumes µ+ > µ− is as follows.

Theorem 3 (Perfect Oracle+Side Information). With known µ+ , µ− , there exist a Monte Carlo
2 log n
algorithm for Crowd-Cluster with query complexity O( (µk+ −µ
2 ), and a Las Vegas algorithm with
−)
2

log n
expected query complexity O(n + (µk+ −µ
2 ) even when µ+ , µ− are unknown. (Proof in Sec. 4.2).
−)

5

Many natural distributions such as N (µ+ , 1) and N (µ− , 1) have ∆(N (µ+ , 1)kN (µ− , 1)) =
(µ+ − µ− )2 . But, it is also natural to have distributions where µ+ = µ− but ∆(f+ , f− ) > 0. As
a simple example, consider two discrete distributions with mass 1/4, 1/2, 1/4 and 1/3, 1/3, 1/3
respectively at points 0, 1/2, 1. Their means are the same, but divergence is constant.The
following theorem matches the lower bound upto a log n factor with no assumption on µ+ , µ− .
Theorem 4 (Perfect Oracle+Side Information). Let f+ and f− be pmfs 3 and mini f+ (i),
mini f− (i) ≥ ǫ for a constant ǫ. There exist a Monte Carlo algorithm for Crowd-Cluster with
k 2 log n
) with known f+ and f− , and a Las Vegas algorithm with expected
query complexity O( ∆(f
+ ,f− )
2

k log n
) even when k, f+ and f− are unknown. (Proof in Sec. 4.2).
query complexity O(n log n+ ∆(f
+ ,f− )

To improve from Theorem 3 to Theorem 4, we would need a more precise approach. The
minor restriction that we have on f+ and f− , namely, mini f+ (i), mini f− (i) ≥ ǫ allows
∆(f+ , f− ) ≤ 2ǫ . Note that, by our lower bound result, Lemma 1, it is not possible to achieve
query complexity below k2 .
While our lower bound results assume knowledge of k, f+ and f− , our Las Vegas algorithms
do not even need to know them, and none of the algorithms know k. For Theorem 4, indeed,
either of mini f− (i) or mini f+ (i) having at least ǫ will serve our purpose.
The main idea is as follows. It is much easier to determine whether a vertex belongs to a
cluster, if that cluster has enough number of members. On the other hand, if a vertex v has the
highest membership in some cluster C with a suitable deﬁnition of membership, then v should be
queried with C ﬁrst. For any vertex v and a cluster C, deﬁne the empirical “inter” distribution
1
· |{u : wu,v = ai }|. Also compute
pv,C in the following way. For, i = 1, . . . , q,: pv,C (i) = |C|
1
the ‘intra’ distribution pC for i = 1, . . . , q, pC (i) = |C|(|C|−1) · |{(u, v) : u 6= v, wu,v = ai }|. Then
Membership(v, C) = −kpv,C − pC kT V , where kpv,C − pC kT V denotes the total variation distance
between distributions deﬁned in Section 3. If Membership(v, C) is highest for C, then using
Sanov’s Theorem (Theorem 9) it is highly likely that v is in C, if |C| is large enough. However
we do not know f+ or f− . Therefore, the highest membership could be misleading since we
do not know the desired size threshold that C must cross to be reliable. But yet, it is possible
to query a few clusters and determine correctly the one which contains v. The main reason
behind using total variation distance as opposed to divergence, is that divergance is not a metric,
and hence do not satisfy the triangle inequality which becomes crucial in our analysis. This
is the precise reason why we need the minimum value to be at least ǫ in Theorem 4. Under
these restrictions, a close relationship between divergence and total variation distance can be
established using Pinsker’s and Reverse Pinsker’s inequalities (see, Section 3).
For faulty oracle, let us ﬁrst take the case of no side information (later, we can combine it
with the previous algorithm to obtain similar results with side information). Suppose all V × V
queries have been made. If the maximum likelihood (ML) estimate on G with these n2 query
answers is same as the true clustering of G, then Algorithm 2 ﬁnds the true clustering with
high probability. We sample a small graph G′ from G, by asking all possible queries in G′ , and
check for the heaviest weight subgraph (assuming ±1 weight on edges) in G′ . If that subgraph
crosses a desired size, it is removed from G′ . If this cluster is detected correctly, then it has
enough members; we can ask separate queries to them to determine if a vertex belongs to that
cluster. The main eﬀort goes in showing that the computed cluster from G′ is indeed correct,
and that G′ has small size.
Theorem 5 (Faulty Oracle with No Side Information). There exists an algorithm with
query

complexity O( λ12 nk log n) for Crowd-Cluster that returns Ĝ, ML estimate of G with all n2 queries,
with high probability when query answers are incorrect with probability p = 12 − λ. Noting that,
4λ2
, this matches the information theoretic lower bound on the query complexity
D(pk1− p) ≤ 1/2−λ
3

We can handle probability density functions as well for Theorem 4 and Theorem 6, if the quantization error is
small. Our other theorems are valid for f+ and f− being both probability mass functions and density functions.

6

within a log n factor. Moreover, the algorithm returns all the true clusters of G of size at least
36
log n with high probability. (Proof in Sec. 6.1.2).
λ2
Theorem 6 (Faulty Oracle with Side Information). Let f+ , f− be pmfs and
mini f+ (i), mini f− (i) ≥ ǫ for a constant ǫ. With side information and faulty oracle with
error probability 12 − λ, there exist an algorithm for Crowd-Cluster with query complex2
n
ity O( λ2 k∆(flog
) when f+ , f− known, and an algorithm with expected query complexity
+ ,f− )
2

n
) when f+ , f− unknown, that recover Ĝ, ML estimate of G with all
O(n + λ2 k∆(flog
+ ,f− )
with high probability. (Proof in Sec. 6.1.3).

n
2

queries,

log n

A subtle part of these results is that, the running time is O(k λ2 ), which is optimal assuming
the hardness of planted cliques. However, by increasing the query complexity, the running time
can be reduced to polynomial.
Corollary 2 (Faulty Oracle with/without Side Information). For faulty oracle with error probability 12 − λ, there exists a polynomial time algorithm with query complexity O( λ12 nk2 ) for CrowdCluster that recovers all clusters of size at least O(max { λ12 log n, k}). (Proof in Sec. 6.1.2).

As it turns out the ML estimate of G with all n2 queries is equivalent to computing correlation clustering on G [11, 8, 3, 14, 15]. As a side result, we get a new algorithm for correlation
√
clustering over noisy input, where any cluster of size min (k, n) will be recovered exactly with
√
n
log n
high probability as long as k = Ω( log
λ2 ). When k ∈ [Ω( λ2 ), o( n)], our algorithm strictly
improves over [11, 8].
We hope our work will inspire new algorithmic works in the area of crowdsourcing where
both query complexity and side information are important.


1.2.3

Round Complexity

Finally, we extend all our algorithms to obtain near optimal round complexity.
Theorem 7 (Perfect Oracle with Side Information). There exists an algorithm for CrowdCluster with perfect oracle and unknown side information f+ and f− such that it√achieves a
√
round complexity within Õ(1) factor of the optimum when k = Ω( n) or k = O( ∆(f+nkf− ) ), and
otherwise within Õ( ∆(f+1kf− ) ). (Proof in Sec. 7.1).

Theorem 8 (Faulty Oracle with no Side Information). There exists an algorithm for CrowdCluster with faulty oracle with error probability 21 −λ and no side information such that it achieves
√
a round complexity
within Õ( log n) factor of the optimum that recovers Ĝ, ML estimate of G

with all n2 queries with high probability. (Proof in Sec. 7.2).
This also leads to a new parallel algorithm for correlation clustering over noisy input where
computation in every round is bounded by n log n.

2

Organization of the remaining paper

The rest of the paper is organized as follows. In Section 3, we provide the information theoretic
tools (deﬁnitions and basic results) necessary for our upper and lower bounds.
In Section 4 we provide our main upper bound results for the perfect oracle case when f+
and f− are unknown. In Section 5 we give some more insight into the working of Algorithm
1 and for the case when f+ and f− are known, provide near optimal Monte Carlo/Las Vegas
algorithms for Crowd-Cluster with side information and perfect oracle. In Section 6, we consider
the case when crowd may return erroneous answers. In this scenario we give tight lower and
upper bounds on query complexity in both the cases when we have or lack side information.
In Section 7, we show that the algorithms developed for optimizing query complexity naturally
extend to the parallel version of minimizing the round complexity.
7

3

Information Theory Toolbox

The lower bounds for randomized algorithms presented in this paper are all information theoretic.
We also use information theoretic tools of large-deviations in upper bounds. To put these
bounds into perspective, we will need deﬁnition of many information theoretic quantities and
some results. Most of this material can also be found in a standard information theory textbook,
such as Cover and Thomas [19].
Definition (Divergence). The Kullback-Leibler divergence, or simply divergence, between two
probability measures P and Q on a set X , is deﬁned to be
D(P kQ) =

Z

X

dP ln

dP
.
dQ

When P and Q are distributions of a continuous random variable, represented by probability
R∞
(x)
fp (x) ln ffpq (x)
densities fp (x) and fq (x) respectively, we have, D(fp kfq ) = −∞
dx. Similarly when
P and Q are discrete random variable taking values in the set X , and represented by the
probability mass functions p(x) and q(x), where x ∈ X respectively, we have D(p(x)kq(x)) =
P
p(x)
x∈X p(x) ln q(x) .
For two Bernoulli distributions with parameters p and q, where 0 ≤ p, q ≤ 1, by abusing the
notation the divergence is written as,
D(pkq) = p ln

1−p
p
+ (1 − p) ln
.
q
1−q

p
1−p
In particular, D(pk1 − p) = p ln 1−p
+ (1 − p) ln 1−p
p = (1 − 2p) ln p . Although D(P kQ) ≥ 0,
with equality when P = Q, note that in general D(P kQ) 6= D(QkP ). Deﬁne the symmetric
divergence between two distribution P and Q as,

∆(P, Q) = D(P kQ) + D(QkP ).
The following property of the divergence is going to be useful to us. Consider a set of
random variables X1 , . . . , Xm , and consider the two joint distribution of the random variables,
P m and Qm . When the random variables are independent, let Pi and Qi be the corresponding marginal distribution of the random variable Xi , i = 1, . . . , m. In other words, we have,
Qm
Q
m
P m (x1 , x2 , . . . , xm ) = m
i=1 Qi (xi ). Then we must have,
i=1 Pi (xi ) and Q (x1 , x2 , . . . , xm ) =
m

m

D(P kQ ) =

m
X
i=1

D(Pi kQi ).

(1)

A more general version, when the random variables are not independent, is given by the
chain-rule, described below for discrete random variables.
Lemma 1. Consider a set of discrete random variables X1 , . . . , Xm , and consider the two joint
distribution of the random variables, P and Q. The chain-rule for divergence states that,
D(P (x1 , . . . , xm )kQ(x1 , . . . , xm )) =

m
X
i=1

D(P (xi | x1 , . . . , xi−1 )kQ(xi | x1 , . . . , xi−1 )),

where,
D(P (x|y)kQ(x|y)) =

X

P (Y = y)D(P (x|Y = y)kQ(x|Y = y)).

y

8

Definition (Total Variation Distance). For two probability distributions P and Q deﬁned on a
sample space X and same sigma-algebra F, the total variation distance between them is deﬁned
to be,
kP − QkT V = sup{P (A) − Q(A) : A ∈ F}.
In words, the distance between two distributions is their largest diﬀerence over any measurable
set. For ﬁnite X total variation distance is half of the ℓ1 distance between pmfs.
The total variation distance and the divergence are related by the Pinsker’s inequality.
Lemma 2 (Pinsker’s inequality). For any two probability measures P and Q,
1
kP − Qk2T V ≤ D(P kQ).
2
It is easy to see that, there cannot be a universal ‘reverse’ Pinsker’s inequality, i.e., an
upper bound on the divergence by the total variation distance (for example, the total variation
distance is always less than 1, while the divergence can be inﬁnity). However, under various
assumptions, such upper bounds have been proposed [48, 20]. For example we provide one such
inequality below.
Lemma 3 (Reverse Pinsker’s inequality[48]). For any two probability measures on ﬁnite alphabet X , given by probability mass functions p and q, we must have,
kp − qk2T V ≥

minx∈X q(x)
D(pkq)
2

(2)

This inequality can be derived from Eq.(28) of [48].
A particular basic large-deviation inequality that we use for the upper bounds is Sanov’s
theorem.
Theorem 9 (Sanov’s theorem). Let X1 , . . . , Xn are iid random variables with a ﬁnite sample
space X and distribution P . Let P n denote their joint distribution. Let E be a set of probability
P
distributions on X . The empirical distribution P̃n gives probability P̃n (A) = n1 ni=1 1Xi ∈A to
any event A. Then,
P n ({x1 , . . . , xn } : P̃n ∈ E) ≤ (n + 1)|X | exp(−n min
D(P ∗ kP )).
∗
P ∈E

A continuous version of Sanov’s theorem is also possible but we omit here for clarity.
Hoeﬀding’s inequality for large deviation of sums of bounded independent random variables
is well known [38, Thm. 2].
Lemma 4 (Hoeﬀding). If X1 , . . . , Xn are independent random variables and ai ≤ Xi ≤ bi for
all i ∈ [n]. Then
Pr(|

n
1X
2n2 t2
).
(Xi − EXi )| ≥ t) ≤ 2 exp(− Pn
2
n i=1
i=1 (bi − ai )

This inequality can be used when the random variables are independently sampled with
replacement from a ﬁnite sample space. However due to a result in the same paper [38, Thm.
4], this inequality also holds when the random variables are sampled without replacement from
a ﬁnite population.
Lemma 5 (Hoeﬀding). If X1 , . . . , Xn are random variables sampled without replacement from
a ﬁnite set X ⊂ R, and a ≤ x ≤ b for all x ∈ X . Then
Pr(|

n
2nt2
1X
(Xi − EXi )| ≥ t) ≤ 2 exp(−
).
n i=1
(b − a)2

9

Crowd-Cluster with Perfect Oracle

4

In this section, we consider the clustering problem using crowdsourcing when crowd always
returns the correct answers, and there is side information.

4.1

Lower Bound

Recall that there are k clusters in the n-vertex graph. That is G(V, E) is such that, V = ⊔ki=1 Vi
and E = {(i, j) : i, j ∈ Vℓ for some ℓ}. In other words, G is a union of at most k disjoint cliques.
Every entry of the side-information matrix W is generated independently as described in the
introduction. We now prove Theorem 1.
Proof of Theorem 1. We are going to construct an input that any randomized algorithm will
be unable to correctly
j identify
k with positive probability.
1
Suppose, a = ∆(f+ ,f− ) . Consider the situation when we are already given a complete
cluster Vk with n − (k − 1)a elements, remaining (k − 1) clusters each has 1 element, and the
rest (a − 1)(k − 1) elements are evenly distributed (but yet to be assigned) to the k − 1 clusters.
This means each of the smaller clusters has size a each. Note that, we assumed the knowledge
of the number of clusters k.
The side information matrix W = (wi,j ) is provided. Each wi,j are independent random
variables.
Now assume the scenario when we use an algorithm ALG to assigns a vertex to one of the
k − 1 clusters, Vu , u = 1, . . . , k − 1. Note that, for any vertex, l, the side informations wi,j where
i 6= l and j 6= l, do not help in assigning l to a cluster (since in that case wi,j is independent of l).
Therefore, given a vertex l, ALG takes as input the random variables wi,l s where i ∈ ⊔t Vt , and
makes some queries involving l and outputs a cluster index, which is an assignment for l. Based
on the observations wi,l s, the task of algorithm ALG is thus a multi-hypothesis testing among
k − 1 hypotheses. Let Hu , u = 1, . . . k − 1 denote the k − 1 diﬀerent hypotheses Hu : l ∈ Vu .
And let Pu , u = 1, . . . k − 1 denote the joint probability distributions of the random variables
wi,j s when l ∈ Vu . In short, for any event A, Pu (A) = Pr(A|Hu ). Going forward, the subscript
of probabilities or expectations will denote the appropriate conditional distribution.
For this hypothesis testing problem, let E{Number of queries made by ALG} = T. Then,
there exist t ∈ {1, . . . , k − 1} such that, Et {Number of queries made by ALG} ≤ T. Note that,
k−1
X
v=1

Pt { a query made by ALG involving cluster Vv } ≤ Et {Number of queries made by ALG} ≤ T.
Consider the set
J ′ ≡ {v ∈ {1, . . . , k − 1} : Pt { a query made by ALG involving cluster Vv } <

1
}.
10

1
≤ T, which implies, |J ′ | ≥ k − 1 − 10T.
We must have, (k − 1 − |J ′ |) · 10
Note that, to output a cluster without using the side information, ALG has to either make
a query to the actual cluster the element is from, or query at least k − 2 times. In any other
case, ALG must use the side information (in addition to using queries) to output a cluster. Let
E u denote the event that ALG output cluster Vu by using the side information.
Pk−1
10
Let J ′′ ≡ {u ∈ {1, . . . , k − 1} : Pt (E u ) ≤ k−1
}. Since, u=1
Pt (E u ) ≤ 1, we must have,

(k − 1 − |J ′′ |) ·

We have,

9(k − 1)
10
≤ 1, or |J ′′ | ≥
.
k−1
10

|J ′ ∩ J ′′ | ≥ k − 1 − 10T +

9(k − 1)
9(k − 1)
− (k − 1) =
− 10T.
10
10

10

Now consider two cases.
Case 1: T ≥ 9(k−1)
100 . In this case, average number of queries made by ALG to assign one vertex
to a cluster is at least 9(k−1)
10 . Since there are (k − 1)(a − 1) vertices that needs to be assigned
to clusters, the expected total number of queries performed by ALG is

9(k−1)2 (a−1)
.
10

. In this case, J ′ ∩ J ′′ is nonempty. Assume that we need to assign the
Case 2: T < 9(k−1)
100
vertex j ∈ Vℓ for some ℓ ∈ J ′ ∩ J ′′ to a cluster (Hℓ is the true hypothesis). We now consider the
following two events.
E1 =

n

a query made by ALG involving cluster Vℓ

n

o

o

E2 = k − 2 or more queries were made by ALG .

Note that, if the algorithm ALG can correctly assign j to a cluster without using the side
information then either of E1 or E2 must have to happen. Recall, E ℓ denote the event that ALG
S S
output cluster Vℓ using the side information. Now consider the event E ≡ E ℓ E1 E2 . The
probability of correct assignment is at most Pℓ (E). We have,
Pℓ (E) ≤ Pt (E) + |Pℓ (E) − Pt (E)| ≤ Pt (E) + kPℓ − Pt kT V ≤ Pt (E) +

r

1
D(Pℓ kPt ),
2

where we ﬁrst used the deﬁnition of the total variation distance and in the last step we have
used Pinsker’s inequality (Lemma 2). Now we bound the divergence D(Pℓ kPt ). Recall that Pℓ
and Pt are the joint distributions of the independent random variables wi,j , i ∈ ∪u Vu . Now,
using lemma 1, and noting that the divergence between identical random variables are 0, we
obtain
D(Pℓ kP1 ) ≤ aD(f− kf+ ) + aD(f+ kf− ) = a∆ ≤ 1.
This is true because the only times when wi,jqdiﬀers under Pt and under Pℓ is when i ∈ Vt or
i ∈ Vℓ . As a result we have, Pℓ (E) ≤ Pt (E) + 12 .
Now, using Markov inequality Pt (E2 ) ≤

T
k−2

≤

Pt (E) ≤ Pt (E ℓ ) + Pt (E1 ) + Pt (E2 ) ≤

9(k−1)
100(k−2)

≤

9
100

+

9
100(k−2) .

Therefore,

10
1
9
9
+
+
+
.
k − 1 10 100 100(k − 2)

19
+
For large enough k, we overall have Pℓ (E) ≤ 100
1
j to the correct cluster with probability at least 10 .

q

1
2

<

9
10 .

This means ALG fails to assign

Considering the above two cases, we can say that any algorithm either makes on average
1
queries, or makes an error with probability at least 10
.

9(k−1)2 (a−1)
10

Note that, in this proof we have not in particular tried to optimize the constants. Corollary
1 follows by noting that to recover the clusters exactly, the query complexity
has to be at least
k
k
(n − k) + 2 . If the number of queries issued is at most (n − k) + 2 − 1, then either there
exists a vertex v in a non-singleton cluster which has not been queried to any other member of
that same cluster, or there exist two clusters such that no inter-cluster edge across them have
been queried.

4.2

Upper Bound

We do not know k, f+ , f− , µ+ , or µ− , and our goal, in this section, is to design an algorithm
with optimum query complexity for exact reconstruction of the clusters with probability 1. We
are provided with the side information matrix W = (wi,j ) as an input. Let θgap = µ+ − µ− .
11

The algorithm uses a subroutine called Membership that takes as input a vertex v and a
subset of vertices C ⊆ V.
PAt this point, let the membership of a vertex v in cluster C is deﬁned
wv,u

as follows: avg(v, C) = u∈C
, and we use Membership(v, C) = avg(v, C).
|C|
The pseudocode of the algorithm is given in Algorithm 1. The algorithm works as follows.
Let C1 , C2 , ..., Cl be the current clusters in nonincreasing order of size. We ﬁnd the minimum
index j ∈ [1, l] such that there exists a vertex v not yet clustered, with the highest average
membership to Cj , that is Membership(v, Cj )≥Membership(v, Cj ′ ), ∀j ′ 6= j, and j is the smallest
index for which such a v exists. We ﬁrst check if v ∈ Cj by querying v with any current member
of Cj . If not, then we group the clusters C1 , C2 , .., Cj−1 in at most ⌈log n⌉ groups such that
1 | |C1 |
, 2i ). For each group, we pick the cluster which
clusters in group i has size in the range [ 2|Ci−1
has the highest average membership with respect to v, and check by querying whether v belongs
to that cluster. Even after this, if the membership of v is not resolved, then we query v with
one member of each of the clusters that we have not checked with previously. If v is still not
clustered, then we create a new singleton cluster with v as its sole member.
We now give a proof of the Las Vegas part of Theorem 3 here using Algorithm 1, and defer
the more formal discussions on the Monte Carlo part to the next section.
Proof of Theorem 3, Las Vegas Algorithm. First, The algorithm never includes a vertex in a
cluster without querying it with at least one member of that cluster. Therefore, the clusters
constructed by our algorithm are always proper subsets of the original clusters. Moreover, the
algorithm never creates a new cluster with a vertex v before ﬁrst querying it with all the existing
clusters. Hence, it is not possible that two clusters produced by our algorithm can be merged.
Let C1 , C2 , ..., Cl be the current non-empty clusters that are formed by Algorithm 1, for some
l ≤ k. Note that Algorithm 1 does not know k. Let without loss of generality |C1 | ≥ |C2 | ≥ ... ≥
n
.
|Cl |. Let there exists an index i ≤ l such that |C1 | ≥ |C2 | ≥ · · · ≥ |Ci | ≥ M , where M = 6θlog
2
gap

Of course, the algorithm does not know either i or M . If even |C1 | < M , then i = 0. Suppose j ′
is the minimum index such that there exists a vertex v with highest average membership in Cj ′ .
There are few cases to consider based on j ′ ≤ i, or j ′ > i and the cluster that truly contains v.
Case 1. v truly belongs to Cj ′ . In that case, we just make one query between v and an
existing member of Cj ′ and the ﬁrst query is successful.
Case 2. j ′ ≤ i and v belongs to Cj , j 6= j ′ for some j ∈ {1, . . . , i}. Let avg(v, Cj )
and avg(v, Cj ′ ) be the average membership of v to Cj , and Cj ′ respectively. Then we have
avg(v, Cj ′ ) ≥ avg(v, Cj ), that is Membership(v, Cj′ )≥Membership(v, Cj ). This is only possible if
θ

θ

gap
′
either avg(v, Cj ′ ) ≥ µr + gap
2 or avg(v, Cj ) ≤ µg − 2 . Since both Cj and Cj have at least
M current members, then using the Chernoﬀ-Hoeﬀding’s bound (Lemma 4) followed by union
bound this happens with probability at most n23 . Therefore, the expected number of queries
involving v before its membership gets determined is ≤ 1 + n23 k < 2.
Case 4. v belongs to Cj , j 6= j ′ for some j > i. In this case the algorithm may make k
queries involving v before its membership gets determined.
Case 5. j ′ > i, and v belongs to Cj for some j ≤ i. In this case, there exists no v with its
highest membership in C1 , C2 , ..., Ci .
Suppose C1 , C2 , ..., Cj′ are contained in groups H1 , H2 , ..., Hs where s ≤ ⌈log n⌉. Let Cj ∈

1|
Ht , t ∈ [1, s]. Therefore, |Cj | ∈ [ 2|Ct−1
, |C21t | ]. If |Cj | ≥ 2M , then all the clusters in group Ht
have size at least M . Now with probability at least 1 − n22 , avg(v, Cj ) ≥ avg(v, Cj ′′ ), that is
Membership(v, Cj )≥Membership(v, Cj ′′ ) for every cluster Cj ′′ ∈ Ht . In that case, the membership
of v is determined within at most ⌈log n⌉ queries. Otherwise, with probability at most n22 , there
may be k queries to determine the membership of v.
Therefore, once a cluster has grown to size 2M , the number of queries to resolve the membership of any vertex in those clusters is at most ⌈log n⌉ with probability at least 1− n2 . Hence, for at
most 2kM elements, the number of queries made to resolve their membership can be k. Thus the

12

2

log n
expected number of queries made by Algorithm 1 is O(n log n + M k2 ) = O(n log n + (µk+ −µ
2 ).
−)
Moreover, if we knew µ+ and µ− , we can calculate M , and thus whenever a clusters grows to
size M , remaining of its members can be included in that cluster without making any error with
high probability. This leads to Theorem 3.

We can strengthen this algorithm by changing the subroutine Membership in the following
way. Assume that f+ , f− are discrete distributions over q points a1 , a2 , . . . , aq ; that is wi,j takes
value in the set {a1 , a2 , . . . , aq } ⊂ [0, 1].
The subroutine Membership takes v ∈ V and C ⊆ V \ {v} as inputs. Compute the ‘inter’
1
· |{u : wu,v = ai }|.
distribution pv,C for i = 1, . . . , q, pv,C (i) = |C|
1
Also compute the ‘intra’ distribution pC for i = 1, . . . , q, pC (i) = |C|(|C|−1)
· |{(u, v) : u 6=
v, wu,v = ai }|. Then deﬁne Membership(v, C) = −kpv,C −pC kT V . Note that, since the membership
is always negative, a higher membership implies that the ‘inter’ and ‘intra’ distributions are
closer in terms of total variation distance. With this modiﬁcation in the subroutine we can
prove what is claimed in Theorem 4.
The analysis for this case proceeds exactly as above. However, to compare memberships we
use Lemma 6 below. Indeed, Lemma 6 can be used in the cases 2 and 5 in lieu of ChernoﬀHoeﬀding bounds to obtain the exact same result.
Lemma 6. Suppose, C, C ′ ⊆ V , C ∩ C ′ = ∅ and |C| ≥ M, |C ′ | ≥ M =
mini f+ (i), mini f− (i) ≥ ǫ for a constant ǫ. Then,




Pr Membership(v, C ′ ) ≥ Membership(v, C) | v ∈ C ≤

16 log n
ǫ∆(f+ ,f− ) ,

with where

4
.
n3

Proof. Let β = kf+ −f2− kT V . If Membership(v, C ′ ) ≥ Membership(v, C) then we must have, kpv,C ′ −
pC ′ kT V ≤ kpv,C − pC kT V . This means, either kpv,C ′ − pC ′ kT V ≤ β2 or kpv,C − pC kT V ≥ β2 . Now,
using triangle inequality,


Pr kpv,C ′ − pC ′ kT V ≤


≤ Pr kpv,C ′ − f+ kT V


β
β
≤ Pr kpv,C ′ − f+ kT V − kpC ′ − f+ kT V ≤
2
2



β
β
≤ β or kpC ′ − f+ kT V ≥
≤ Pr kpv,C ′ − f+ kT V ≤ β + Pr kpC ′ − f+ kT V ≥
.
2
2

Similarly,


Pr kpv,C − pC kT V ≥


≤ Pr kpv,C − f+ kT V


β
β
≤ Pr kpv,C − f+ kT V + kpC − f+ kT V ≥
2
2


β
β
β
β
≥ or kpC − f+ kT V ≥
≤ Pr kpv,C − f+ kT V ≥
+ Pr kpC − f+ kT V ≥
.
4
4
4
4

Now, using Sanov’s theorem (Theorem 9), we have,




Pr kpv,C ′ − f+ kT V ≤ β ≤ (M + 1)q exp(−M

min

p:kp−f+ kT V ≤β

D(pkf− )).

At the optimizing p of the exponent,
D(pkf− ) ≥ 2kp − f− k2T V

from Pinsker’s Inequality (Lemma 2)
2

≥ 2(kf+ − f− kT V − kp − f+ kT V )

from using triangle inequality

2

≥ 2(2β − β)

kf+ − f− k2T V
2
ǫ
≥ max{D(f+ kf− ), D(f− kf+ )}
2

from noting the value of β

=

from reverse Pinsker’s inequality (Lemma 3)
13

ǫ∆(f+ , f− )
4
Again, using Sanov’s theorem (Theorem 9), we have,
≥



Pr kpC ′ − f+ kT V ≥

β
≤ (M + 1)q exp(−M
min
D(pkf+ )).
2
p:kp−f+ kT V ≥ β2

At the optimizing p of the exponent,
D(pkf+ ) ≥ 2kp − f+ k2T V
≥

from Pinsker’s Inequality (Lemma 2)

β2

from noting the value of β
2
kf+ − f− k2T V
=
8
ǫ
≥ max{D(f+ kf− ), D(f− kf+ )} from reverse Pinsker’s inequality (Lemma 3)
8
ǫ∆(f+ , f− )
≥
16
Now substituting this in the exponent, using the value of M and doing the same exercise
for the other two probabilities we get the claim of the lemma.

5

Crowd-Cluster with Perfect Oracle: Known f+, f−

In this section, we take a closer look at the results presented in Section 4. Recall that, we
have an undirected graph G(V ≡ [n], E), such that G is a union of k disjoint cliques Gi (Vi , Ei ),
i = 1, . . . , k, but the subsets Vi ∈ [n] and E are unknown to us. The goal is to determine these
clusters accurately (with probability 1) by making minimum number of pair-wise queries. As a
side information, we are given W which represents the similarity values that are computed by
some automated algorithm, and therefore reﬂects only a noisy version of the true similarities
({0, 1}). Based on the sophistication of the automated algorithm, and the amount of information
available to it, the densities f+ and f− will vary. We have provided a lower bound for this in
Section 4.
In Algorithm 1, we do not know k, f+ , f− , µ+ , or µ− , and our goal was to achieve optimum
query complexity for exact reconstruction of the clusters with probability 1. In this section we
are going to provide a simpler algorithm that has the knowledge of µ+ , µ− or even f+ , f− , and
show that we can achieve optimal query complexity.
Let µ+ − µ− ≥ θgap , and we select a parameter M satisfying
M=

6 log n
.
2
θgap

The simpler algorithm, referred to as Algorithm (1-a), contains two phases, that are repeated
as long as there are vertices that have not yet been clustered.
Querying Phase. The algorithm maintains a list of active clusters which contain at least
one vertex but whose current size is strictly less than M . For every v which has not yet been
assigned to any cluster, the algorithm checks by querying to the oracle whether v belongs to
any of the cluster in the list. If not, it opens a new cluster with v as its sole member, and add
that cluster to the list.
Estimation Phase. If the size of any cluster, say C in the list becomes M , then the cluster
is removed from the list, and the algorithm enters an estimation phase with C. For every vertex
v which has not yet been clustered, it computes the average membership score of v in C as
θgap
1 P
avg(v, C) = |C|
u wu,v . If avg(v, C) ≥ µ+ − 2 , then include v in C. After this phase, mark C
as ﬁnal and inactive.
14

Algorithm 1 Crowd-Cluster with Side Information. Input: {V, W } (Note: O is the perfect
oracle.
⊲ Initialization.
1: Pick an arbitrary vertex v and create a new cluster {v}. Set V = V \ v
2: while V 6= ∅ do
⊲ Let the number of current clusters be l ≥ 1
3:
Order the existing clusters in nonincreasing size.
⊲ Let |C1 | ≥ |C2 | ≥ . . . ≥ |Cl | be the ordering (w.l.o.g).
4:
for j = 1 to l do
5:
If ∃v ∈ V such that j = maxi∈[1,l] Membership(v, Ci ), then select v and Break;
6:
end for
7:
O(v, u) where u ∈ Cj
8:
if O(v, u) == “ + 1” then
9:
Include v in Cj . V = V \ v
10:
else
⊲ logarithmic search for membership in the large groups. Note s ≤ ⌈log n⌉
11:
Group C1 , C2 , ..., Cj−1 into s consecutive classes H1 , H2 , ..., Hs such that the clusters
1 | |C1 |
, 2i )
in group Hi have their current sizes in the range [ 2|Ci−1
12:
for i = 1 to s do
13:
j = maxa:Ca ∈Hi Membership(v, Ca )
14:
O(v, u) where u ∈ Cj .
15:
if O(v, u) == “ + 1” then
16:
Include v in Cj . V = V \ v. Break.
17:
end if
18:
end for
⊲ exhaustive search for membership in the remaining groups
19:
if v ∈ V then
20:
for i = 1 to l + 1 do
21:
if i = l + 1 then
⊲ v does not belong to any of the existing clusters
22:
Create a new cluster {v}. Set V = V \ v
23:
else
24:
if ∄u ∈ Ci such that (u, v) has already been queried then
25:
O(v, u)
26:
if O(v, u) == “ + 1” then
27:
Include v in Cj . V = V \ v. Break.
28:
end if
29:
end if
30:
end if
31:
end for
32:
end if
33:
end if
34: end while

15

Lemma 7. The total number of queries made by Algorithm (1-a) is at most k2 M .
Proof. Suppose, there are k′ clusters of size at least M . The number of queries made in the
querying phase to populate these clusters is at most M k′ · k. For the remaining (k − k′ ) clusters,
their size is at most (M − 1), and again the number of queries made to populate them is at
most (M − 1)(k − k′ ) · k. Hence, the total number of queries made during the querying phases is
k2 M . Furthermore, no queries are made during the estimation phases, and we get the desired
bound.
Lemma 8. Algorithm (1-a) retrieves the original clusters with probability at least 1 − n2 .
Proof. Any vertex that is included to an active cluster, must have got a positive answer from
a query during the querying phase. Now consider the estimation phase. If u, v ∈ V belong to
the same cluster C, then wu,v ∼ f+ , else wu,v ∼ f− . Therefore, E[wu,v | u, v ∈ C] = µ+ and
E[wu,v | u ∈ C, v ∈
/ C] = µ− . Then, by the Chernoﬀ-Hoeﬀding bound (Lemma 4),


Pr avg(v, C) < µ+ −
And similarly,

2

M θgap
1
θgap
|v ∈ C ≤ e− 2 ≤ 3 .
2
n


M θ2
1
θgap
− 2gap
| v 6∈ C ≤ e
≤ 3.
Pr avg(v, C) > µ− +
2
n
Therefore by union bound, for every vertex that is included in C during the estimation phase
truly belongs to it, and any vertex that is not included in C truly does not belong to it with
probability ≥ 1− n22 . Or, the probability that the cluster C is not correctly constructed is at most
2
n2 . Since, there could be at most n clusters, the probability that there exists one incorrectly
constructed cluster is at most n2 . Note that, any cluster that never enters the estimation
phase is always constructed correctly, and any cluster that enters the estimation phase is fully
constructed before moving to a new unclustered vertex. Therefore, if a new cluster is formed
in the querying phase with v, then v cannot be included to any existing clusters assuming the
clusters grown in the estimation phases are correct. Hence, Algorithm (1-a) correctly retrieves
the clusters with probability at least 1 − n2 .


So far, Algorithm (1-a) has been a Monte Carlo algorithm. In order to turn it into a Las
Vegas algorithm, we make the following modiﬁcations.
θ

• In the estimation phase with cluster C, if avg (v, C) ≥ µ+ − gap
2 , then we query v with
some member of C. If that returns +1 (i.e., the edge is present), then we include v, else,
we query v with one member of every remaining clusters (active and inactive). If none of
these queries returns +1, then a singleton cluster with v is created, and included in the
active list. We then proceed to the next vertex in the estimation phase.
Clearly, this modiﬁed Algorithm (1-a) retrieves all clusters correctly and it is a Las Vegas
algorithm. We now analyze the expected number of queries made by the algorithm in the
estimation phase.
Lemma 9. The modiﬁed Las Vegas Algorithm (1-a) makes at most n + 2 queries on expectation
during the estimation phase.
Proof. In the estimation phase, only 1 query is made with v while determining its membership
if indeed v belongs to cluster C when avg (v, C) ≥ µ+ − θgap
2 . Now this happens with probability
at least 1 − n22 . With the remaining probability, at most (k − 1) ≤ n extra queries may be
made with v. At the end of this, either v is included in a cluster, or a new singleton cluster is
formed with v. Therefore, the expected number of queries made with v, at the end of which
the membership of v is determined is at most 1 + 2(k−1)
n2 . Hence the expected number of total
queries made by Algorithm (1-a) in the estimation phase is at most n + 2.
16

Theorem 10. With known µ+ and µ− , there exist a Monte Carlo algorithm for Crowd2 log n
Cluster with query complexity O( (µk+ −µ
2 ) and a Las Vegas algorithm with expected query com−)
plexity O(n +

k 2 log n
(µ+ −µ− )2 ).

Comparing with the Lower Bound.
Example 1. The KL-divergence between two univariate normal distributions with means
µ1 and µ2 , and standard deviations
σ1 and σ2 respectively can be calculated as

σ12 +(µ1 −µ2 )2
σ1
D(N (µ1 , σ1 )kN (µ2 , σ2 )) = log σ2 +
− 12 . Therefore ∆(f+ , f− ) = (µ+ − µ− )2 .
2σ2
2

Algorithm (1-a) is optimal under these natural distributions within a log n factor.
Example 2.
f− (x) =

(

(1 + ǫ)
(1 − ǫ)

if 0 ≤ x < 12
if 1 ≥ x ≥ 12 ;

f+ (x) =

(

(1 − ǫ)
(1 + ǫ)

if 0 ≤ x < 12
if 1 ≥ x ≥ 12 .

That is, they are derived by perturbing the uniform distribution slightly so that f+ puts
slightly higher mass when x ≥ 12 , and f− puts slightly higher mass when x < 21 .
R 1/2

1
(1 − ǫ) dx = 1. Similarly, 01 f+ (x) dx = 1, that
Note that 01 f− (x) dx = 0 (1 + ǫ) dx + 1/2
is they represent valid probability density functions.
We have
Z 1
2−ǫ
1 ǫ
(1 + ǫ) 3(1 − ǫ)
+
=
= −
xf− (x) dx =
µ− =
8
8
4
2 4
0
and
Z 1
2+ǫ
1 ǫ
(1 − ǫ) 3(1 + ǫ)
+
=
= + .
µ+ =
xf+ (x) dx =
8
8
4
2 4
0

R

R

R

Thereby, µ+ − µ− = 2ǫ . Moreover
D(f+ kf− ) =

Z

0

1/2

(1 − ǫ) log

1−ǫ
dx +
1+ǫ

Z

1

(1 + ǫ) log

1/2

1+ǫ
1+ǫ
dx = ǫ log
= O(ǫ2 )
1−ǫ
1−ǫ

Therefore, again Algorithm (1-a) is optimal under these distributions within a log n factor.
Improving Algorithm (1-a) to match the lower bound. We will now show a way to
achieve the lower bound in the Crowd-Cluster up to a logarithmic term (while matching the
denominator) by modifying Algorithm (1-a). We ﬁrst do this by assuming f+ , f− to be discrete
distributions over q points a1 , a2 , . . . , aq . So, wi,j takes value in the set {a1 , a2 , . . . , aq }.
Theorem 11. With known f+ and f− such that mini f+ (i), mini f− (i) ≥ ǫ for a constant ǫ,
k 2 log n
) and a
there exist a Monte Carlo algorithm for Crowd-Cluster with query complexity O( ∆(f
+ ,f− )
Las Vegas algorithm with expected query complexity O(n +

k 2 log n
∆(f+ ,f− ) ).

Indeed, either of mini f− (i) or mini f+ (i) strictly greater than 0 will serve our purpose. We
have argued before that it is not so restrictive condition.
Proof of Theorem 11. For any vertex v and a cluster C, deﬁne the empirical distribution pv,C in
the following way. For, i = 1, . . . , q,
pv,C (i) =

1
· |{u : wu,v = ai }|.
|C|
17

Now modify Algorithm (1-a) as follows. The querying phase of the algorithm remains exactly
same. In the estimation phase for a cluster C and an unassigned vertex v, include v in C if
D(pv,C kf+ ) < D(pv,C kf− ).
Everything else remains same.
Now, a vertex v ∈ C will be erroneously not assigned to it with probability








Pr D(pv,C kf+ ) ≥ D(pv,C kf− ) | v ∈ C = f+ {pv,C : D(pv,C kf+ ) ≥ D(pv,C kf− )}
= (M + 1)q exp(−M

min

p:D(pkf+ )≥D(pkf− )

D(pkf+ )),

where in the last step we have used Sanov’s theorem (see, Theorem 9). Due to lemma 10, we
can replace the constraint of the optimization in the exponent above by an equality.
Hence,




Pr D(pv,C kf+ ) ≥ D(pv,C kf− ) | v ∈ C ≤ (M + 1)q+1 exp(−M
whenever

min

D(pkf+ )) ≤

p:D(pkf+ )=D(pkf− )

1
,
n3

8 log n
.
min
D(pkf+ )

M=

p:D(pkf+ )=D(pkf− )

This value of M is also suﬃcient to have,




Pr D(pv,C kf+ ) < D(pv,C kf− ) | v ∈
/C ≤

1
.
n3

While the rest of the analysis stays same as before, the overall query complexity of this modiﬁed
algorithm is


k2 log n
O
.
min
D(pkf+ )
p:D(pkf+ )=D(pkf− )

If the divergence were a distance then in the denominator above we would have got D(f+ kf− )/2
and that would be same as the lower bound we have obtained. However, since that is not the
case, we rely on the following chain of inequalities instead at the optimizing point of p.
D(pkf+ ) + D(pkf− )
≥ kp − f+ k2T V + kp − f− k2T V
2
+ kp − f− kT V )2
kf+ − f− k2T V
≥
,
2
2

D(pkf+ ) = D(pkf− ) =
≥

(kp − f+ kT V

where we have used the Pinsker’s inequality (Lemma 2), the convexity of the function x2 and
the triangle inequality for the total variation distance respectively. Now as the last step we use
the reverse Pinsker’s inequality (Lemma 3) to obtain,
kf+ − f− k2T V ≥

ǫ
ǫ∆(f+ , f− )
max{D(f+ kf− ), D(f− kf+ )} ≥
.
2
2

This completes the proof.
Lemma 10.
min

p:D(pkf+ )≥D(pkf− )

D(pkf+ ) =

18

min

D(pkf+ ).

p:D(pkf+ )=D(pkf− )

Proof. Since the condition D(pkf+ ) ≥ D(pkf− ) can be written as
to solve the constrained optimization

P

f− (i)
i p(i) ln f+ (i)

min D(pkf+ )
p

such that
X
i

p(i) ln

f− (i)
≥ 0.
f+ (i)

≥ 0 we need
(3)

(4)

We claim that the inequality of (4) can be replaced by an equality without any change
in the optimizing value. Suppose this is not true and the optimizing value p̃ is such that
P
f− (i)
i p̃(i) ln f+ (i) = ǫ > 0.
Let, λ = ǫ+D(fǫ− kf+ ) ∈ (0, 1). Note that for the value p∗ = λf+ + (1 − λ)p̃ we have,
s

X

p∗ (i) ln

i

f− (i)
= −λD(f+ kf− ) + (1 − λ)ǫ = 0.
f+ (i)

However, since D(pkf+ ) is a strictly convex function of p, we must have,
D(p∗ kf+ ) < λD(f+ kf+ ) + (1 − λ)D(p̃kf+ ) = (1 − λ)D(p̃kf+ ),
which is a contradiction of p̃ being the optimizing value.

6

Crowd-Cluster with Faulty Oracle

We now consider the case when crowd may return erroneous answers. We do not allow resampling of the same query. By resampling one can always get correct answer for each query with
high probability followed by which we can simply apply the algorithms for the perfect oracle.
Hence, the oracle can be queried with a particular tuple only once in our setting.

6.1
6.1.1

No Side Information
Lower bound for the faulty-oracle model

Suppose, G(V, E) is a union of k disjoint cliques as before. We have, V = ⊔ki=1 Vi . We consider
the following faulty-oracle model. We can query the oracle whether there exists an edge between
vertex i and j. The oracle will give the correct answer with probability 1 − p and will give the
incorrect answer with probability p. We would like to estimate the minimum number of queries
one must make to the oracle so that we can recover the clusters with high probability. In this
section we forbid the use of any side information that may be obtained from an automated
system. The main goal of this section is to prove Theorem 2.
As argued in the introduction, there is a need for a minimum cluster size. If there is no
minimum size requirement on a cluster then the input graph can always consist of multiple
clusters of very small size. Then consider the following two diﬀerent clusterings. C1 : V =
k−2
k−2
⊔i=1
Vi ⊔ {v1 , v2 } ⊔ {v3 } and C2 : V = ⊔i=1
Vi ⊔ {v1 } ⊔ {v2 , v3 }. Now if one of these two
clusterings are given to us uniformly at random, no matter how many queries we do, we will fail
to recover the correct cluster with probability at least p (recall that, resampling is not allowed).
The argument above does not hold for the case when p = 0. In that case any (randomized)
algorithm has to use (on expectation) O(nk) queries for correct clustering (see the p = 0 case
of Theorem 2 below). While for deterministic algorithm the proof of the above fact is straightforward, for randomized algorithms it was established in [22]. In [22], a clustering was called
balanced if the minimum and maximum sizes of the clusters are only a constant factor way. In
19

particular, [22] observes that, for unbalanced input the lower bound for p = 0 case is easier.
For randomized algorithms and balanced inputs, they left the lower bound as an open problem.
Theorem 2 resolves this as a special case.
Indeed, in Theorem 2, we provide lower bounds for 0 ≤ p < 1/2, assuming inputs such that
either 1) the maximum size of the cluster is within a constant times away from the average size,
or 2) the minimum size of the cluster is a constant fraction of the average size. Note that the
average size of a cluster is nk .
The technique to prove Theorem 2 is similar to the one we have used in Theorem 1. However
we only handle binary random variables here (the answer to the queries). The signiﬁcant
diﬀerence is that, while designing the input we consider a balanced clustering with small sized
clusters we can always fool any algorithm as exempliﬁed above). This removes the constraint
on the algorithm designer on how many times a cluster can be queried with a vertex. While
Lemma 11 shows that enough number of queries must be made with a large number of vertices
V ′ ⊂ V , either of the conditions on minimum or maximum sizes of a cluster ensures that V ′
contains enough vertices that do not satisfy this query requirement.
As mentioned, Lemma 11 is crucial to prove Theorem 2.
Lemma 11. Suppose, there are k clusters. There exist at least 4k
5 clusters such that a vertex v
from any one of these clusters will be assigned to a wrong cluster by any randomized algorithm
k
with positive probability unless the number of queries involving v is more than 10D(pk1−p)
when
p > 0 and

k
10

when p = 0.

Proof. Let us assume that the k clusters are already formed, and we can moreover assume that
all vertices except for the said vertex has already been assigned to a cluster. Note that, queries
that do not involve the said vertex plays no role in this stage.
Now the problem reduces to a hypothesis testing problem where the ith hypothesis Hi for
i = 1, . . . , k, denote that the true cluster is Vi . We can also add a null-hypothesis H0 that
stands for the vertex belonging to none of the clusters. Let Pi denote the joint probability
distribution of our observations (the answers to the queries involving vertex v) when Hi is true,
i = 0, 1, . . . , k. That is for any event A we have,
Pi (A) = Pr(A|Hi ).
Suppose Q denotes the total number of queries made by a (possibly randomized) algorithm
at this stage. Let the random variable Qi denote the number of queries involving cluster
Vi , i = 1, . . . , k.
P
We must have, ki=1 E0 Qi ≤ Q. Let,
J1 ≡ {i ∈ {1, . . . , k} : E0 Qi ≤

10Q
}.
k

9k
Since, (k − |J1 |) 10Q
k ≤ Q, we have |J1 | ≥ 10 .
Let Ei ≡ { the algorithm outputs cluster Vi }. Let

J2 = {i ∈ {1, . . . , n} : P0 (Ei ) ≤

10
}.
k

9k
Moreover, since ki=1 P0 (Ei ) ≤ 1 we must have, (k − |J2 |) 10
k ≤ 1, or |J2 | ≥ 10 . Therefore,
J = J1 ∩ J2 has size,
4k
9k
−k =
.
|J| ≥ 2 ·
10
5
Now let us assume that, we are given a vertex v ∈ Vj for some j ∈ J to cluster. The
probability of correct clustering is Pj (Ej ). We must have,

P

Pj (Ej ) = P0 (Ej ) + Pj (Ej ) − P0 (Ej ) ≤
20

10
+ |P0 (Ej ) − Pj (Ej )|
k

10
10
≤
+ kP0 − Pj kT V ≤
+
k
k

r

1
D(P0 kPj ).
2

where we again used the deﬁnition of the total variation distance and in the last step we have
used the Pinsker’s inequality (lemma 2). The task is now to bound the divergence D(P0 kPj ).
Recall that P0 and Pj are the joint distributions of the independent random variables (answers to
queries) that are identical to one of two Bernoulli random variables:Y , which is Bernoulli(p), or
Z, which is Bernoulli(1 − p). Let X1 , . . . , XQ denote the outputs of the queries, all independent
random variables. We must have, from the chain rule (lemma 1),
D(P0 kPj ) =
=

Q
X

i=1
Q
X

D(P0 (xi |x1 , . . . , xi−1 )kPj (xi |x1 , . . . , xi−1 ))
X

i=1 (x1 ,...,xi−1 )∈{0,1}i−1

P0 (x1 , . . . , xi−1 )D(P0 (xi |x1 , . . . , xi−1 )kPj (xi |x1 , . . . , xi−1 )).

Note that, for the random variable Xi , the term D(P0 (xi |x1 , . . . , xi−1 )kPj (xi |x1 , . . . , xi−1 )) will
contribute to D(pk1 − p) only when the query involves the cluster Vj . Otherwise the term will
contribute to 0. Hence,
D(P0 kPj ) =

Q
X

X

i=1 (x1 ,...,xi−1 )∈{0,1}i−1 :ith query involves Vj

= D(pk1 − p)

Q
X

= D(pk1 − p)

Q
X

P0 (x1 , . . . , xi−1 )D(pk1 − p)

X

P0 (x1 , . . . , xi−1 )

i=1 (x1 ,...,xi−1 )∈{0,1}i−1 :ith query involves Vj

i=1

P0 (ith query involves Vj ) = D(pk1 − p)E0 Qj ≤

10Q
D(pk1 − p).
k

Now plugging this in,
10
+
D(P0 kPj ) ≤
k
if Q ≤
10Q
k

k
10D(pk1−p) .

s

10
1 10Q
D(pk1 − p) ≤
+
2 k
k

r

1
,
2

On the other hand, when p = 0, Pj (Ej ) < 1 when E0 Qj < 1. Therefore

≥ 1 whenever p = 0.

Now we are ready to prove Theorem 2.
Proof of Theorem 2. We will show that claim by considering any input, with a restriction on
either the maximum or the minimum cluster size. We consider the following two cases for the
proof.
Case 1: the maximum size of a cluster is ≤

4n
k .

Suppose, total number of queries is = T . That means number of vertices involved in the
queries is ≤ 2T . Note that, there are k clusters and n elements.
Let U be the set of vertices that are involved in less than 16T
n queries. Clearly,
(n − |U |)

16T
≤ 2T,
n

or |U | ≥

7n
.
8

Now we know from Lemma 11 that there exists 4k
5 clusters such that a vertex v from any one
of these clusters will be assigned to a wrong cluster by any randomized algorithm with positive
21

probability unless the expected number of queries involving this vertex is more than

k
10D(pk1−p) ,

k
for p > 0, and 10
when p = 0.
We claim that U must have an intersection with at least one of these 4k
5 clusters. If not,
7n
4k
k
then more than 8 vertices must belong to less than k − 5 = 5 clusters. Or the maximum size
4n
of a cluster will be 7n·5
8k > k , which is prohibited according to our assumption.
Consider the case, p > 0. Now each vertex in the intersection of U and the 4k
5 clusters
k
are going to be assigned to an incorrect cluster with positive probability if, 16T
≤
n
10D(pk1−p) .
Therefore we must have
nk
.
T ≥
160D(pk1 − p)

Similarly, when p = 0 we must have, T ≥

nk
160 .

n
.
Case 2: the minimum size of a cluster is ≥ 20k
′
Let U be the set of clusters that are involved in at most 16T
k queries. That means, (k −
16T
7k
′
′
|U |) k ≤ 2T. This implies, |U | ≥ 8 .
∗
Now we know from lemma 11 that there exists 4k
5 clusters (say U ) such that a vertex v
from any one of these clusters will be assigned to a wrong cluster by any randomized algorithm
with positive probability unless the expected number of queries involving this vertex is more
k
k
, p > 0 and 10
for p = 0.
than 10D(pk1−p)
4k
27k
Quite clearly |U ∗ ∩ U | ≥ 7k
8 + 5 − k = 40 .
∗
Consider a cluster Vi such that i ∈ U ∩ U , which is always possible because the intersection
is nonempty. Vi is involved in at most 16T
k queries. Let the minimum size of any cluster be t.
Now, at least half of the vertices of Vi must each be involved in at most 32T
kt queries. Now each
k
of these vertices must be involved in at least 10D(pk1−p)
queries (see Lemma 11) to avoid being
assigned to a wrong cluster with positive probability (for the case of p = 0 this number would
k
).
be 10
This means,


nk
k
32T
≥
,
or T = Ω
,
kt
10D(pk1 − p)
D(pk1 − p)

for p > 0, since t ≥
6.1.2

n
20k .

Similarly when p = 0 we need T = Ω(nk).

Upper Bound

Now we provide an algorithm to retrieve the clustering with the help of the faulty oracle when
no side information is present. The algorithm is summarized in Algorithm 2. The algorithm
works as follows. It maintains an active list of clusters A, and a sample graph G′ = (V ′ , E ′ )
which is an induced subgraph of G. Initially, both of them are empty. The algorithm always
maintains the invariant that any cluster in A has at least c log n members where c = λ62 , and
p = 21 − λ. Note that the algorithm knows λ. Furthermore, all V ′ (G′ ) × V ′ (G′ ) queries have
been made. Now, when a vertex v is considered by the algorithm (step 3), ﬁrst we check if v
can be included in any of the clusters in A. This is done by picking c log n distinct members
from each cluster, and querying v with them. If majority of these questions return +1, then
v is included in that cluster, and we proceed to the next vertex. Otherwise, if v cannot be
included in any of the clusters in A, then we add it to V ′ (G′ ), and ask all possible queries to
the rest of the vertices in G′ with v. Once G′ has been modiﬁed, we extract the heaviest weight
subgraph from G′ where weight on an edge (u, v) ∈ E(G′ ) is deﬁned as ωu,v = +1 if the query
answer for that edge is +1 and −1 otherwise. If that subgraph contains c log n members then
we include it as a cluster in A. At that time, we also check whether any other vertex u in G′
can join this newly formed cluster by counting if the majority of the (already) queried edges to

22

this new cluster gave answer +1. At the end, all the clusters in A, and the maximum likelihood
clustering from G′ is returned.
Before showing the correctness of Algorithm 2, we elaborate on ﬁnding the maximum likelihood estimate for the clusters in G.
Finding the Maximum Likelihood Clustering of G with faulty oracle We have an
undirected graph G(V ≡ [n], E), such that G is a union of k disjoint cliques Gi (Vi , Ei ), i =
1, . . . , k. The subsets Vi ∈ [n] are unknown to us. The adjacency matrix of G is a block-diagonal
matrix. Let us denote this matrix by A = (ai,j ).
Now suppose, each edge of G is erased independently with probability p, and at the same
time each non-edge is replaced with an edge with probability p. Let the resultant adjacency
matrix of the modiﬁed graph be Z = (zi,j ). The aim is to recover A from Z.
The maximum likelihood recovery is given by the following:
max

Sℓ ,ℓ=1,···:V =⊔ℓ Sℓ

=

max

Sℓ ,ℓ=1,···:V =⊔ℓ=1 Sℓ

Y

Y

Y

Y

Y

P+ (zi,j )

r,t,r6=t i∈Sr ,j∈St

ℓ i,j∈Sℓ ,i6=j

ℓ i,j∈Sℓ ,i6=j

Y

P− (zi,j )

P+ (zi,j ) Y
P− (zi,j ).
P− (zi,j ) i,j∈V,i6=j

where, P+ (1) = 1 − p, P+ (0) = p, P− (1) = p, P− (0) = 1 − p. Hence, the ML recovery asks for,
max

Sℓ ,ℓ=1,···:V =⊔ℓ=1 Sℓ

X

X

ln

ℓ i,j∈Sℓ ,i6=j

P+ (zi,j )
.
P− (zi,j )

Note that,
ln
Hence the ML estimation is,

P+ (0)
P+ (1)
p
= − ln
= ln
.
P− (0)
P− (1)
1−p
max

Sℓ ,ℓ=1,···:V =⊔ℓ=1 Sℓ

X

X

ωi,j ,

(5)

ℓ i,j∈Sℓ ,i6=j

where ωi,j = 2zi,j − 1, i 6= j, i.e., ωi,j = 1, when zi,j = 1 and ωi,j = −1 when zi,j = 0, i 6= j.
Further ωi,i = zi,i = 0, i = 1, . . . , n.
Note that (5) is equivalent to ﬁnding correlation clustering in G with the objective of maximizing the consistency with the edge labels, that is we want to maximize the total number of
positive intra-cluster edges and total number of negative inter-cluster edges [8, 44, 42]. This
can be seen as follows.
max

Sℓ ,ℓ=1,···:V =⊔ℓ=1 Sℓ

X

X

ωi,j

ℓ i,j∈Sℓ ,i6=j

≡

Sℓ ,ℓ=1,···:V =⊔ℓ=1 Sℓ

=

max

max

Sℓ ,ℓ=1,···:V =⊔ℓ=1 Sℓ

X

X

ℓ i,j∈Sℓ ,i6=j

X

X



(i, j) : ωi,j = +1 − (i, j) : ωi,j = −1 +
(i, j) : ωi,j = +1 +

ℓ i,j∈Sℓ ,i6=j

 X

r,t:r6=t

X

i,j∈V,i6=j

(i, j) : ωi,j = −1


(i, j) : i ∈ Sr , j ∈ St , ωi,j = −1 .

Therefore (5) is same as correlation clustering, however viewing it as obtaining clusters with
maximum intra-cluster weight helps us to obtain the desired running time of our algorithm.
Also, note that, we have a random instance of correlation clustering here, and not a worst case
instance.
We are now ready to prove the correctness of Algorithm 2.
23

Algorithm 2 Crowd-Cluster with Error & No Side Information. Input: {V }
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

V ′ = ∅, E ′ = ∅, G′ = (V ′ , E ′ )
A=∅
while ∃v ∈ V yet to be clustered do
for each cluster C ∈ A do
⊲ Set c = λ62 where λ ≡ 12 − p.
Select u1 , u2 , .., ul , where l = c log n, distinct members from C and obtain Op (ui , v),
i = 1, 2, .., l. If the majority of these queries return +, then include v in C. Break.
end for
if v is not included in any cluster in A then
Add v to V ′ . For every u ∈ V ′ \ v, obtain Op (v, u). Add an edge (v, u) to E ′ (G′ )
with weight ωu,v = +1 if Op (u, v) == +1, else with ωu,v = −1
Find the heaviest weight subgraph S in G′ . If |S| ≥ c log n, then add S to the list of
clusters in A, and remove the incident vertices and edges on S from V ′ , E ′ .
P
while ∃z ∈ V ′ with u∈S ωz,u > 0 do
Include z in S and remove z and all edges incident on it from V ′ , E ′ .
end while
end if
end while
return all the clusters formed in A and the ML estimates from G′

Correctness of Algorithm
2 To establish the correctness of Algorithm 2, we show the

following. Suppose all n2 queries
on V × V have been made. If the Maximum Likelihood (ML)

estimate of G with these n2 answers is same as the true clustering of G, then Algorithm 2 ﬁnds
the true clustering with high probability. There are few steps to prove the correctness.
The ﬁrst step is to show that any set S that is retrieved in step 9 of Algorithm 2 from G′ ,
and added to A is a subcluster of G (Lemma 12). This establishes that all clusters in A at any
time are subclusters of some original cluster in G. Next, we show that vertices that are added
to a cluster in A, are added correctly, and no two clusters in A can be merged (Lemma 13).
Therefore, clusters obtained from A, are the true clusters. Finally, the remaining of the clusters
can be retrieved from G′ by computing a ML estimate on G′ in step 15, leading to theorem 12.
Lemma 12. Let c′ = 6c = λ362 , where λ = 12 − p. Algorithm 2 in step 9 returns a subcluster
of G of size at least c log n with high probability if G′ contains a subcluster of G of size at least
c′ log n. Moreover, Algorithm 2 in step 9 does not return any set of vertices of size at least
c log n if G′ does not contain a subcluster of G of size at least c log n.
Proof. Let V ′ = Vi′ , i ∈ [1, k], Vi′ ∩ Vj′ = ∅ for i 6= j, and Vi′ ⊆ Vi (G). Suppose without loss
of generality |V1′ | ≥ |V2′ | ≥ .... ≥ |Vk′ |.
The lemma is proved via a series of claims.
S

Claim 1. Let |V1′ | ≥ c′ log n. Then in step 9, a set S ⊆ Vi for some i ∈ [1, k] will be returned
with size at least c log n with high probability.
For an i : |Vi′ | ≥ c′ log n, we have
E

X

s,t∈Vi′ ,s<t

ωs,t

!

!

|Vi′ |
|Vi′ |
=
((1 − p) − p) = (1 − 2p)
.
2
2

Since ωs,t are independent binary random variables, using the Hoeﬀding’s inequality (Lemma

24

4),
Pr



X

s,t∈Vi′ ,s<t

ωs,t ≤ E

−



X

ωs,t − u ≤ e

s,t∈Vi′ ,s<t

(

2

u2
|V ′ |
i
2

).

Hence,
Pr



X

s,t∈Vi′ ,s<t

ωs,t > (1 − δ)E

Therefore with high probability
c′2
3 (1

2

P

X

s,t∈Vi′ ,s<t

s,t∈Vi′ ,s<t ωs,t



ωs,t ≥ 1 − e−

> (1 − δ)(1 − 2p)
1
3 ).

− 2p) log n, for an appropriately chosen δ (say δ =

δ 2 (1−2p)2
2

|Vi′ |
2

(deﬁne c′′ = c′

q

2(1−2p)
)
3

with high probability - since otherwise

X

c′

ωi,j <

i,j∈S,i<j

q

2(1−2p)
3

!

log n

2

<

.

≥ (1 − δ)(1 − 2p)
c′

So, Algorithm 2 in step (9) must return a set S such that |S| ≥

′

(|V2i |)

q

2(1−2p)
3

c′ log n
2

>

log n = c′′ log n

c′2
(1 − 2p) log2 n.
3

Now let S * Vi for any i. Then S must have intersection with at least 2 clusters. Let
Vi ∩ S = Ci and let j ∗ = arg mini:Ci 6=∅ |Ci |. We claim that,
X

X

ωi,j <

i,j∈S,i<j

ωi,j ,

(6)

i,j∈S\Cj ∗ ,i<j

with high probability. Condition (6) is equivalent to,
X

X

ωi,j +

i,j∈Cj ∗ ,i<j

ωi,j < 0.

i∈Cj ∗ ,j∈S\Cj ∗

However this is true because,
1. E



P

i,j∈Cj ∗ ,i<j ωi,j = (1−2p)

|Cj ∗ |
2

and E



P

i∈Cj ∗ ,j∈S\Cj ∗ ωi,j = −(1−2p)|Cj ∗ |·|S\Cj ∗ |.

√
2. As long as |Cj ∗ | ≥ 2 log n we have, from Hoeﬀding’s inequality (Lemma 4),
Pr



X

ωi,j

i,j∈Cj ∗ ,i<j

|C ∗ |
λ2 (1−2p)2 ( j )
|Cj ∗ | 
2
−
2
= on (1).
≥ (1 + λ)(1 − 2p)
≤e
2

!

While at the same time,
Pr



X

i∈Cj ∗ ,j∈S\Cj ∗



ωi,j ≥ −(1 − λ)(1 − 2p)|Cj ∗ | · |S \ Cj ∗ | ≤ e−

λ2 (1−2p)2 |Cj ∗ |·|S\Cj ∗ |

In this case of course with high probability
X

i,j∈Cj ∗ ,i<j

ωi,j +

X

i∈Cj ∗ ,j∈S\Cj ∗

25

ωi,j < 0.

2

= on (1).

√
3. When |Cj ∗ | < 2 log n, we have,
X

i,j∈Cj ∗ ,i<j

ωi,j ≤

!

|Cj ∗ |
≤ 2 log2 n.
2

While at the same time,
Pr



X

i∈Cj ∗ ,j∈S\Cj ∗



ωi,j ≤ (1 − λ)(1 − 2p)|Cj ∗ | · |S \ Cj ∗ | ≤ e−

λ2 (1−2p)2 |Cj ∗ |·|S\Cj ∗ |
2

= on (1).

Hence, even in this case, with high probability,
X

i,j∈Cj ∗ ,i<j

ωi,j +

X

ωi,j < 0.

i∈Cj ∗ ,j∈S\Cj ∗

Hence (6) is true with high probability. But then the algorithm 2 in step 9 would not return S,
but will return S \ Cj ∗ . Hence, we have run into a contradiction. This means S ⊆ Vi for some
Vi .
q
log n, while |V1′ | ≥ c′ log n. In fact, with high probability, |S| ≥
We know |S| ≥ c′ 2(1−2p)
3
(1−δ) ′
2 c log n.

Since all the vertices in S belong to the same cluster in G, this holds again by the
application of Hoeﬀding’s inequality. Otherwise, the probability that the weight of S is at least
as high as the weight of V1′ is at most n12 .
Claim 2. If |V1′ | < c log n. then in step 9 of Algorithm 2, no subset of size > c log n will be
returned.

If Algorithm 2 in step 9 returns a set S with |S| > c log n then S must have intersection
with at least 2 clusters in G. Now following the same argument as in Claim 1 to establish Eq.
(6), we arrive to a contradiction, and S cannot be returned.
This establishes the lemma.
Lemma 13. The collection A contains all the true clusters of G of size ≥ c′ log n at the end of
Algorithm 2 with high probability.
Proof. From Lemma 12, any cluster that is computed in step 9 and added to A is a subset
of some original cluster in G, and has size at least c log n with high probability. Moreover,
whenever G′ contains a subcluster of G of size at least c′ log n, it is retrieved by our Algorithm
and added to A.
A vertex v is added to a cluster in A either is step 5 or step 11. Suppose, v has been
added to some cluster C ∈ A. Then in both the cases, |C| ≥ c log n at the time v is added, and
there exist l = c log n distinct members of C, say, u1 , u2 , .., ul such that majority of the queries
of v with these vertices returned +1. By the standard Chernoﬀ-Hoeﬀding bound (Lemma
2
2λ2
λ2
4), Pr(v ∈
/ C) ≤ exp(−c log n (1−2p)
12p ) = exp(−c log n 3(1+2λ) ) ≤ exp(−c log n 3 ), where the
last inequality followed since λ < 21 . On the other hand, if there exists a cluster C ∈ A
such that v ∈ C, and v has already been considered by the algorithm, then either in step
5 or step 11, v will be added to C. This again follows by the Chernoﬀ-Hoeﬀding bound, as
2
λ2
λ2
Pr(v not included in C | v ∈ C) ≤ exp(−c log n (1−2p)
8(1−p) ) = exp(−c log n 1+2λ ) ≤ exp(−c log n 2 ).
Therefore, if we set c = λ62 , then for all v, if v is included in a cluster in A, the assignment is
correct with probability at least 1 − n2 . Also, the assignment happens as soon as such a cluster
is formed in A.
Furthermore, two clusters in A cannot be merged. Suppose, if possible there are two clusters
C1 and C2 both of which are proper subset of some original cluster in G. Let without loss of
generality C2 is added later in A. Consider the ﬁrst vertex v ∈ C2 that is considered by our
26

Algorithm 2 in step 3. If C1 is already there in A at that time, then with high probability v will
be added to C1 in step 5. Therefore, C1 must have been added to A after v has been considered
by our algorithm and added to G′ . Now, at the time C1 is added to A in step 9, v ∈ V ′ , and
again v will be added to C1 with high probability in step 11–thereby giving a contradiction.
This completes the proof of the lemma.
All this leads us to the following theorem.
Theorem 12. If the ML estimate on G with all possible n2 queries return the true clustering,
then Algorithm 2 returns the true clusters with high probability. Moreover, Algorithm 2 returns
all the true clusters of G of size at least c′ log n with high probability.


Proof. From Lemma 12 and Lemma 13, A contains all the true clusters of G of size at least
c′ log n with high probability. Any vertex that is not included in the clusters in A at the end of
Algorithm 2 are in G′ , and G′ contains all possible pairwise queries among them. Clearly, then
the ML estimate of G′ will be the true ML estimate of G restricted to these clusters.
Query Complexity of Algorithm 2
1
2
′
k

Lemma 14. Let p =

− λ. The query complexity of Algorithm 2 is

36nk log n
.
λ2

Proof. Let there be
clusters in A when v is considered in step 3 of Algorithm 2. Then v
is queried with at most ck′ log n current members, c log n each from these k′ clusters. If the
membership of v does not get determined then v is queried with all the vertices in G′ . We
have seen in the correctness proof (Lemma 12) that if G′ contains at least c′ log n vertices from
any original cluster, then ML estimate on G′ retrieves those vertices as a cluster in step 9 with
high probability. Hence, when v is queried with all vertices in G′ , |V ′ | ≤ (k − k′ )c′ log n. Thus
the total number of queries made to determine the membership of v is at most c′ k log n, where
c′ = 6c = λ362 when the error probability p = 12 −λ. This gives the query complexity of Algorithm
2 considering all the vertices.
This matches the lower bound computed in Section 6.1.1 within a log n factor, since D(pk1−
1/2+λ
2λ
4λ2
2
p) = (1 − 2p) ln 1−p
p = 2λ ln 1/2−λ = 2λ ln(1 + 1/2−λ ) ≤ 1/2−λ = O(λ ).
Now combining all these we get the statement of Theorem 5.
Theorem (5). Faulty Oracle with No Side Information. There exists an algorithm with
query

complexity O( λ12 nk log n) for Crowd-Cluster that returns Ĝ, ML estimate of G with all n2 queries,
with high probability when query answers are incorrect with probability p = 12 − λ. Noting that,
4λ2
D(pk1− p) ≤ 1/2−λ
, this matches the information theoretic lower bound on the query complexity
within a log n factor. Moreover, the algorithm returns all the true clusters of G of size at least
36
λ2 log n with high probability.
Running Time of Algorithm 2 and Further Discussions In step 9 of Algorithm 2, we
need to ﬁnd a large cluster of size at least O( λ12 log n) of the original input G from G′ . By
Lemma 12, if we can extract the heaviest weight subgraph in G′ where edges are labelled ±1,
and that subgraph meets the required size bound, then with high probability, it is a subset of
1
an original cluster. This subset can of course be computed in O(n λ2 log n ) time. Since size of
1
G′ is bounded by O( λk2 log n), the running time is O([ λk2 log n] λ2 log n ). While, query complexity
is independent of running time, it is unlikely that this running time can be improved to a
polynomial. This follows from the planted clique conjecture.
Conjecture 1 (Planted Clique Hardness). Given an Erdős-Rényi random graph G(n, p), with
p = 12 , the planted clique conjecture states that if we plant in G(n, p) a clique of size t where
√
t = [O(log n), o( n)], then there exists no polynomial time algorithm to recover the largest clique
in this planted model.
27

Given such a graph with a planted clique of size t = Θ(log n), we can construct a new graph
H by randomly deleting each edge with probability 13 . Then in H, there is one cluster of size
t where edge error probability is 31 and the remaining clusters are singleton with inter-cluster
edge error probability being (1 − 12 − 61 ) = 31 . So, if we can detect the heaviest weight subgraph
in polynomial time in Algorithm 2, there will be a polynomial time algorithm for the planted
clique problem.
Polynomial time algorithm We can reduce the running time from quasi-polynomial to
polynomial, by paying higher in the query-complexity. Suppose, we accept a subgraph extracted
from G′ as valid and add it to A iﬀ its size is Ω(k). Then note that since G′ can contain at
most k2 vertices, such a subgraph can be obtained in polynomial time following the algorithm
√
of correlation clustering with noisy input [44], where all the clusters of size at least O( n) are
recovered on a n-vertex graph. Since our ML estimate is correlation clustering, we can employ
[44]. For k ≥ λ12 log n, the entire analysis remains valid, and we get a query complexity of
1
1
Õ(nk2 ) as opposed to O( nk
λ2 ). If k < λ2 log n, then clusters that have size less than λ2 log n are
anyway not recoverable. Note that, any cluster that has size less than k are not recovered in
√
√
this process, and this bound only makes sense when k < n. When k ≥ n, we can however
√
recover all clusters of size at least O( n).
Corollary (2). There exists a polynomial time algorithm with query complexity O( λ12 nk2 ) for
Crowd-Cluster when query answers are incorrect with probability 12 −λ, which recovers all clusters
of size at least O(max { λ12 log n, k}) in G.
This also leads to an improved algorithm for correlation clustering over noisy graph. Pre√
viously, the works of [44, 8] can only recover cluster of size at least O( n). However, now if
√
n
k ∈ [Ω( log
λ2 ), o( n)], using this algorithm, we can recover all clusters of size at least k.
6.1.3

With Side Information

The algorithm for Crowd-Cluster with side information when crowd may return erroneous answers
is a direct combination of Algorithm 1 and Algorithm 2. We assume side information is less
accurate than querying because otherwise, querying is not useful. Or in other words ∆(fg , fr ) <
∆(p, 1 − p).
We therefore use only the queried answers to extract the heaviest subgraph from G′ , and
add that to the list A. For the clusters in list A, we follow the strategy of Algorithm 1 to
recover the underlying clusters. The pseudocode is given in Algorithm 3. The correctness of
the algorithm follows directly from the analysis of Algorithm 1 and Algorithm 2.
We now analyze the query complexity. Consider a vertex v which needs to be included in a
cluster. Let there be (r − 1) other vertices from the same cluster as v that have been considered
by the algorithm prior to v.
1. Case 1. r ∈ [1, c log n], the number of queries is at most kc log n. In that case v is added
to G′ according to Algorithm 2.
2. Case 2. r ∈ (c log n, 2M ], the number of queries can be k ∗ c log n. In that case, the cluster
n
). In
that v belongs to is in A, but has not grown to size 2M . Recall M = O( ∆(flog
+ ,f− )
that case, according to Algorithm 1, v may need to be queried with each cluster in A, and
according to Algorithm 2, there can be at most c log n queries for each cluster in A.
3. Case 3. r ∈ (2R, |C|], the number of queries is at most c log n ∗ log n. In that case,
according to Algorithm 1, v may need to be queried with at most ⌈log n⌉ clusters in A,
and according to Algorithm 2, there can be at most c log n queries for each chosen cluster
in A.
28

Hence, the total number of queries per cluster is at most O(kc2 (log n)2 + (2M −
c log n)kc log n + (|C| − 2M )c(log n)2 ). So, over all the clusters, the query complexity is
O(nc(log n)2 + k2 M c log n). Note that, if have instead insisted on a Monte Carlo algorithm
with known f+ and f− , then the query complexity would have been O(k2 M c log n). Recall that
∆(pk(1 − p)) = O(λ2 ).
Theorem (6). Let f+ and f− be pmfs and mini f+ (i), mini f− (i) ≥ ǫ for a constant ǫ. With
side information and faulty oracle with error probability 21 − λ, there exist an algorithm for
2
n
) with known f+ and f− , and an algorithm
Crowd-Cluster with query complexity O( λ2 k∆(flog
+ ,f− )
2

n
with expected query complexity O(n+ λ2 k∆(flog
) even when f+ and f− are unknown that recover
+ ,f− )

Ĝ, ML estimate of G with all

7

n
2

queries with high probability.

Round Complexity

So far we have discussed developing algorithms for Crowd-Cluster where queries are asked adaptively one by one. To use the crowd workers in the most eﬃcient way, it is also important to
incorporate as much parallelism as possible without aﬀecting the query complexity by much. To
formalize this, we allow at most Θ(n log n) queries simultaneously in a round, and then the goal
is to minimize the number or rounds to recover the clusters. We show that the algorithms developed for optimizing query complexity naturally extends to the parallel version of minimizing
the round complexity.

7.1

Crowd-Cluster with Perfect Oracle

When crowd gives correct answers and there is no side information, then it is easy to get a
round complexity of k which is optimal within a log n factor as Ω(nk) is a lower bound on the
query complexity in this case. One can just pick a vertex v, and then for every other vertex
issue a query involving v. This grows the cluster containing v completely. Thus in every round,
one new cluster gets formed fully, resulting in a round complexity of k.
We now explain the main steps of our algorithm when side information W is available.
1. Sample

√

n log n vertices, and ask all possible

√

n log n
2

queries involving them.

2. Suppose C1 , C2 , ..., Cl are the clusters formed so far. Arrange these clusters in nondecreasing size of their current membership. For every vertex v not yet clustered, choose
the cluster Cj with j = maxi∈[1,l] Membership(v, Ci ), and select at most ⌈log n⌉ clusters
using steps (11) and (13) of Algorithm 1. Issue all of these at most n log n queries simultaneously, and based on the results, grow clusters C1 , C2 , ..., Cl .
√
3. Among the vertices that have not been put
into any cluster, pick n log n vertices uni√

formly at random, and ask all possible n 2log n queries involving them. Create clusters
C1′ , C2′ , ..., Cl′′ based on the query results.
′

ll
4. Merge the clusters C1′ , C2′ , ..., Cl′′ with C1 , C2 , ..., Cl by issuing a total of ll′ queries in ⌈ n log
n⌉
rounds. Goto step 2.

Analysis First, the algorithm computes the clusters correctly. Every vertex that is included
in a cluster, is done so based on a query result. Moreover, no clusters in step 2 can be merged.
So all the clusters returned are correct.
We now analyzed the number of rounds required to compute the clusters.

29

Algorithm 3 Crowd-Cluster with Error & Side Information. Input: {V, W }
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:

V ′ = ∅, E ′ = ∅, G′ = (V ′ , E ′ ), A = ∅
while V 6= ∅ do
If A is empty, then pick an arbitrary vertex v and Go to Step 23
⊲ Let the number of current clusters in A be l ≥ 1
Order the existing clusters in A in nonincreasing size of current membership.
⊲ Let |C1 | ≥ |C2 | ≥ . . . ≥ |Cl | be the ordering (w.l.o.g).
for j = 1 to l do
If ∃v ∈ V such that j = maxi∈[1,l] Membership(v, Ci ), then select v and Break;
end for
Select u1 , u2 , .., ul ∈ Cj , where l = c log n, distinct members from Cj and obtain Op (ui , v),
i = 1, 2, .., l. checked(v, j) = true
if the majority of these queries return +1 then
Include v in Cj . V = V \ v
else
⊲ logarithmic search for membership in the large groups. Note s ≤ ⌈log k⌉
Group C1 , C2 , ..., Cj−1 into s consecutive classes H1 , H2 , ..., Hs such that the clusters
1 | |C1 |
, 2i )
in group Hi have their current sizes in the range [ 2|Ci−1
for i = 1 to s do
j = maxa:Ca ∈Hi Membership(v, Ca )
Select u1 , u2 , .., ul ∈ Cj , where l = c log n, distinct members from Cj and obtain
Op (ui , v), i = 1, 2, .., l. checked(v, j) = true.
if the majority of these queries return +1 then
Include v in Cj . V = V \ v. Break.
end if
end for
⊲ exhaustive search for membership in the remaining groups in A
if v ∈ V then
for i = 1 to l + 1 do
if i = l + 1 then
⊲ v does not belong to any of the existing clusters
Add v to V ′ . Set V = V \ v
For every u ∈ V ′ \ v, obtain Op (v, u). Add an edge (v, u) to E ′ (G′ ) with
weight ω(u, v) = +1 if Op (v, u) == +1, else with ω(u, v) = −1
Find the heaviest weight subgraph S in G′ . If |S| ≥ c log n, then add S to
the list of clusters in A, and remove the incident vertices and edges on S from V ′ , E ′ .
P
while ∃z ∈ V ′ with u∈S ω(z, u) > 0 do
Include z in S and remove z and all edges incident on it from V ′ , E ′ .
end while
Break;
else
if checked(v, i) 6= true then
Select u1 , u2 , .., ul ∈ Cj , where l = c log n, distinct members from Cj
and Op (ui , v), i = 1, 2, .., l. checked(v, i) = true.
if the majority of these queries return +1 then
Include v in Cj . V = V \ v. Break.
end if
end if
end if
end for
end if
end if
end while
return all the clusters formed in A and the ML estimates from G′
30

In one iteration of the algorithm (steps 1 to 4), steps 1 to
3 each require one round, and
√
min (k 2 ,k n log n)
rounds and issue at most
issue at most n log n queries. Step 4 requires at most
n log n
√
√
2
′
min (k , k n log n) queries. This is because l ≤ n log n.
n
)), for i ∈ [1, l], then, at the end of that step,
In step 2, if |Ci | ≥ 2M (recall M = O( ∆(flog
+ kf− )
Ci will be fully grown with high probability from the analysis of Algorithm 1. This happens
since with high probability any vertex that belongs to Ci has been queried with some u already
in Ci . However, since we do not know M , we cannot identify whether Ci has grown fully.
Consider the case when steps 1 and 3 have picked 6kM random vertices. Consider all those
n
. Note that by Markov Inequality, at least n2 vertices are
clusters that have size at least 2k
n
.
contained in clusters of size at least 2k
If we choose these 6kM vertices with replacement, then on expectation, the number of
n
members chosen from each cluster of size 2k
is 3M , and with high probability above 2M .
This same concentration bound holds even though here sampling is done without replacement
(Lemma 5).
Therefore, after 6kM vertices have been chosen, and step 2 has been performed, at least n2
vertices get clustered and removed.
⌉. If k2 ≥ n, then
The number of iterations required to get 6kM random vertices is ⌈ √6kM
n log n
the number of rounds required in each iteration is 2 + ⌈ √n klog n ⌉. So the total number of rounds
2

M
required to get 6kM vertices is O( nklog
n ). And, ﬁnally to get all the vertices clustered, the
2

number of rounds required will be O( k nM ), whereas the optimum round complexity could be
2M
O( nklog
n ).
If k2 < n, then the number of rounds in each√iteration is at most 3. Hence the total number
. If kM ≤ n log n, then the number of rounds required
of iterations is at most 3 + √6kM
n log n
√
√
is O(1). Else, we have kM > n log n and k < n. While our algorithm requires O( √nkM
)
log n
2

rounds, we know the optimum round complexity is at least O( nklogMn ). Overall, the gap may be
√

n
at most O( n klog n ) = O(M ) = O( ∆(flog
).
+ kf− )
This leads to Theorem 7.

Theorem (7). Perfect Oracle with Side Information. There exists an algorithm for CrowdCluster with perfect oracle and unknown side information f+ and f− such that it√achieves a
√
round complexity within Õ(1) factor of the optimum when k = Ω( n) or k = O( ∆(f+nkf− ) ), and
otherwise within Õ(∆(f+ kf− )).

7.2

Crowd-Cluster with Faulty Oracle

We now move to the case of Crowd-Cluster with faulty oracle. We obtain an algorithm with close
to optimal round complexity when no side information is provided. By combining this algorithm
with the one in the previous section, one can easily obtain an algorithm for Crowd-Cluster with
faulty oracle and side information. This is left as an exercise to the reader.
We now give the algorithm for the case when crowd may return erroneous answer with
probability p = 12 − λ (known), and there is no side information.
√
1. Sample n log n vertices uniformly at random, and ask all possible
volving them to form a subgraph G′′ = (V ′′ , E ′′ )

√

n log n
2

queries in-

2. Extract the highest weighted subgraph S from G′′ after setting a weight of +1 for every
positive answer and −1 for every negative answer like in Algorithm 2. If |S| ≥ c log n
where c is set as in Algorithm 2, then for every vertex not yet clustered issue c log n
queries to distinct vertices in S simultaneously in at most c rounds. Grow S by including
any vertex where the majority of those queries returned is +1. Repeat step 2 as long as
31

the extracted subgraph has size at least c log n, else move to step 3 while not all vertices
have been clustered or included in G′′ .
3. Among the vertices that have not
been clustered yet, Pick r vertices Sr uniformly at
r
random, and ask all possible 2 + r|V ′′ | queries among Sr and across Sr and V ′′ . r is
chosen such that the total number of queries is at most n log n. Goto step 2.
Analysis By the analysis (Lemma 12) of Algorithm 2 the extracted subgraph S will have size
≥ c log n iﬀ G′′ contains a subcluster of original G of size O(c log n). Moreover, by Lemma 13,
once S is detected S will be fully grown at the end of that step, that is within the next c rounds.
Now by the same analysis as in the previous section 7.1, once we choose 4kc log n vertices,
2 2
thus query 16k2 c2 log n edges in ⌈ 16kn c ⌉ rounds, then with high probability, each cluster with
n
size will have c log n representatives in G′′ and will be fully grown. We are then left
at least 2k
with at most n2 vertices and can apply the argument recursively. Thus the round complexity is
2 2
O(⌈ 16kn c ⌉ log n + kc) where the second term comes from using at most c rounds for growing
cluster S in step 2.
n
, then we pick n2 edges in at most logn n rounds, and the optimum algorithm
If kc ≥ 4√log
n
√
kc
√ n
log n factor of
has round complexity at least Θ( log
n ) = Θ( 4 log n log n ). So, we are within a
the optimum.
√
√
n
If kc ≤ 4√log
, but kc ≥ log n, then the round complexity of our algorithm is O(kc log n+
n
√
√
log n) = O(kc
√ log n), again within a log n log n factor of the optimum.
√
If kc ≤ log n, then in the ﬁrst round, all the clusters that have size at least c n will have
enough representatives, and will be fully grown at the end of step 2. After that each cluster
√
√
will have at most c n vertices. Hence, a total of at most kc n ≤ log n vertices will remain to
be clustered. Thus the total number of rounds required will be O(kc), within log n factor of the
optimum.
1
), we get Theorem 8.
Recalling that c = O( λ12 ) = O( ∆(pk(1−p))
Theorem (8). Faulty Oracle with no Side Information. There exists an algorithm for CrowdCluster with faulty oracle with error probability 21 −λ and no side information such that it achieves
√
a round complexity
within Õ( log n) factor of the optimum that recovers Ĝ, ML estimate of G

with all n2 queries with high probability.
This also gives a new parallel algorithm for correlation clustering over noisy input where in
each round n log n work is allowed.

References
[1] Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recovery in the stochastic
block model. IEEE Trans. Information Theory, 62(1):471–487, 2016.
[2] Kook-Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Ian
Wirth. Correlation clustering in data streams. In Proceedings of the 32nd International
Conference on Machine Learning, volume 37, 2015.
[3] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information:
ranking and clustering. Journal of the ACM (JACM), 55(5):23, 2008.
[4] Miklos Ajtai, János Komlos, William L Steiger, and Endre Szemerédi. Deterministic selection in o (loglog n) parallel time. In Proceedings of the eighteenth annual ACM symposium
on Theory of computing, pages 188–195. ACM, 1986.

32

[5] N. Alon and Y. Azar. The average complexity of deterministic and randomized parallel comparison sorting algorithms. In Proceedings of the 28th Annual Symposium on Foundations
of Computer Science, FOCS ’87, pages 489–498, 1987.
[6] Noga Alon and Yossi Azar. Sorting, approximate sorting, and searching in rounds. SIAM
Journal on Discrete Mathematics, 1(3):269–280, 1988.
[7] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic
multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002.
[8] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning,
56(1-3):89–113, 2004.
[9] Béla Bollobás and Graham Brightwell. Parallel selection with high probability. SIAM
Journal on Discrete Mathematics, 3(1):21–31, 1990.
[10] Mark Braverman, Jieming Mao, and Matthew S. Weinberg. Parallel algorithms for select and partition with noisy comparisons. In 48th Annual Symposium on the Theory of
Computing, STOC. ACM, 2016.
[11] Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proceedings
of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 268–276.
Society for Industrial and Applied Mathematics, 2008.
[12] Mark Braverman and Elchanan Mossel.
abs/0910.1191, 2009.

Sorting from noisy information.

CoRR,

[13] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[14] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near
optimal lp rounding algorithm for correlationclustering on complete and complete k-partite
graphs. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of
Computing, pages 219–228. ACM, 2015.
[15] Flavio Chierichetti, Nilesh Dalvi, and Ravi Kumar. Correlation clustering in mapreduce.
In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery
and data mining, pages 641–650. ACM, 2014.
[16] Peter Chin, Anup Rao, and Van Vu. Stochastic block model and community detection
in the sparse graphs: A spectral algorithm with optimal rate of recovery. arXiv preprint
arXiv:1501.05021, 2015.
[17] Peter Christen. Data matching: concepts and techniques for record linkage, entity resolution, and duplicate detection. Springer Science & Business Media, 2012.
[18] Richard Cole, Philip N. Klein, and Robert E. Tarjan. Finding minimum spanning forests
in logarithmic time and linear work using random sampling. In Proceedings of the Eighth
Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’96, pages 243–
250, 1996.
[19] Thomas M Cover and Joy A Thomas. Elements of information theory, 2nd Ed. John Wiley
& Sons, 2012.
[20] Imre Csiszár and Zsolt Talata. Context tree estimation for not necessarily ﬁnite memory
processes, via bic and mdl. Information Theory, IEEE Transactions on, 52(3):1007–1016,
2006.
33

[21] Nilesh Dalvi, Anirban Dasgupta, Ravi Kumar, and Vibhor Rastogi. Aggregating crowdsourced binary ratings. In WWW, pages 285–294, 2013.
[22] Susan B. Davidson, Sanjeev Khanna, Tova Milo, and Sudeepa Roy. Top-k and clustering
with noisy comparisons. ACM Trans. Database Syst., 39(4):35:1–35:39, 2014.
[23] Ahmed K Elmagarmid, Panagiotis G Ipeirotis, and Vassilios S Verykios. Duplicate record
detection: A survey. IEEE Trans. Knowl. Data Eng., 19(1):1–16, 2007.
[24] Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using mapreduce. In
Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery
and data mining, pages 681–689. ACM, 2011.
[25] Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy
information. SIAM Journal on Computing, 23(5):1001–1018, 1994.
[26] Ivan P Fellegi and Alan B Sunter. A theory for record linkage. Journal of the American
Statistical Association, 64(328):1183–1210, 1969.
[27] Donatella Firmani, Barna Saha, and Divesh Srivastava. Online entity resolution using an
oracle. PVLDB, 9(5):384–395, 2016.
[28] Hillel Gazit. An optimal randomized parallel algorithm for ﬁnding connected components
in a graph. SIAM Journal on Computing, 20(6):1046–1067, 1991.
[29] Lise Getoor and Ashwin Machanavajjhala. Entity resolution: theory, practice & open
challenges. PVLDB, 5(12):2018–2019, 2012.
[30] Arpita Ghosh, Satyen Kale, and Preston McAfee. Who moderates the moderators?: crowdsourcing abuse detection in user-generated content. In EC, pages 167–176, 2011.
[31] Chaitanya Gokhale, Sanjib Das, AnHai Doan, Jeﬀrey F Naughton, Narasimhan Rampalli,
Jude Shavlik, and Xiaojin Zhu. Corleone: Hands-oﬀ crowdsourcing for entity matching. In
SIGMOD Conference, pages 601–612, 2014.
[32] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation
in the mapreduce framework. In Algorithms and Computation, pages 374–383. Springer,
2011.
[33] John Greiner. A comparison of parallel algorithms for connected components. In Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, pages
16–25. ACM, 1994.
[34] Anja Gruenheid, Besmira Nushi, Tim Kraska, Wolfgang Gatterbauer, and Donald Kossmann. Fault-tolerant entity resolution with the crowd. CoRR, abs/1512.00537, 2015.
[35] Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving exact cluster recovery threshold via
semideﬁnite programming: Extensions. arXiv preprint arXiv:1502.07738, 2015.
[36] Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best nash
equilibrium? SIAM J. Comput., 40(1):79–91, January 2011.
[37] Thomas N. Herzog, Fritz J. Scheuren, and William E. Winkler. Data Quality and Record
Linkage Techniques. Springer Publishing Company, Incorporated, 1st edition, 2007.
[38] Wassily Hoeﬀding. Probability inequalities for sums of bounded random variables. Journal
of the American statistical association, 58(301):13–30, 1963.
34

[39] David R Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing systems. In NIPS, pages 1953–1961, 2011.
[40] Howard Karloﬀ, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for
mapreduce. In Proceedings of the twenty-ﬁrst annual ACM-SIAM symposium on Discrete
Algorithms, pages 938–948. Society for Industrial and Applied Mathematics, 2010.
[41] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Sorting noisy
data with partial information. In Proceedings of the 4th conference on Innovations in
Theoretical Computer Science, pages 515–528. ACM, 2013.
[42] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Correlation
clustering with noisy partial information. In Proceedings of The 28th Conference on Learning Theory, pages 1321–1342, 2015.
[43] Adam Marcus, Eugene Wu, David Karger, Samuel Madden, and Robert Miller. Humanpowered sorts and joins. Proceedings of the VLDB Endowment, 5(1):13–24, 2011.
[44] Claire Mathieu and Warren Schudy. Correlation clustering with noisy input. In Proceedings
of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010,
Austin, Texas, USA, January 17-19, 2010, pages 712–728, 2010.
[45] Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for binary symmetric
block models. Arxiv preprint, 2014.
[46] Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan. Parallel correlation clustering on big graphs. In Advances in
Neural Information Processing Systems, pages 82–90, 2015.
[47] Rudiger Reischuk. A fast probabilistic parallel sorting algorithm. In Proceedings of the
22Nd Annual Symposium on Foundations of Computer Science, FOCS ’81, pages 212–219,
1981.
[48] Igal Sason. On reverse pinsker inequalities. arXiv preprint arXiv:1503.07118, 2015.
[49] Leslie G Valiant. Parallelism in comparison problems. SIAM Journal on Computing,
4(3):348–355, 1975.
[50] Vasilis Verroios and Hector Garcia-Molina. Entity resolution with crowd errors. In 31st
IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea,
April 13-17, 2015, pages 219–230, 2015.
[51] Norases Vesdapunt, Kedar Bellare, and Nilesh Dalvi. Crowdsourcing algorithms for entity
resolution. PVLDB, 7(12):1071–1082, 2014.
[52] Jiannan Wang, Tim Kraska, Michael J Franklin, and Jianhua Feng. Crowder: Crowdsourcing entity resolution. PVLDB, 5(11):1483–1494, 2012.

35

