Finding Planted Partitions in Nearly Linear Timeusing Arrested Spectral Clustering

Nader H. Bshouty
Technionbshouty@cs.technion.ac.ilplong@google.com

Philip M. Long
GoogleAbstract
We describe an algorithm for clustering using
a similarity graph. The algorithm (a) runsin O(n log3 n + m log n) time on graphs withn vertices and m edges, and (b) with highprobability, finds all “large enough” clusters
in a random graph generated according to theplanted partition model. We provide lower
bounds that imply that our “large enough”
constraint cannot be improved much, evenusing a computationally unbounded algorithm. We describe some experiments running the algorithm and a few related algorithms on random graphs with partitions generated using a Chinese Restaurant Processes,
and some results of applying the algorithm tocluster DBLP titles.

1. Introduction
This work is aimed at using theoretical analysis toguide the design of large-scale clustering algorithms.
We are especially interested in problems in which the
purpose of clustering is to identify near-duplicates, forexample to eliminate them from the index of a searchengine.
For problems like these, it is possible to use a technique such as minhashing (Coh97; Bro97) to build agraph in which most pairs of items that should be clustered together are represented by edges, and there are
not too many spurious edges. There can be billions, or
more, of vertices. There are many clusters, and many
vertices are not clustered. The largest clusters are themost important, since they do the most harm. BeAppearing in Proceedings of the 26 th International Conference on Machine Learning, Haifa, Israel, 2010. Copyright2010 by the author(s)/owner(s).

cause the input is large, and such duplicate-detection
must be done often, efficient algorithms are important.
Even if massive parallelism is available to speed up algorithms, an algorithm that expends limited resources
overall is still valuable as a means to reduce costs andmake limited computing resources available for otherpurposes.
We analyze algorithms using the planted partition
model (CK01; McS01) in which an adversary partitions the vertices of a graph into clusters C1 , ..., Ct ,and then edges are included between members of thesame cluster independently with one probability p, andedges are included between members of different clusters with another, smaller, probability q. We show
that, if p ≥ 1/2, a O(n log3 n + m log n) time algorithm can, with probability 1 − 1/poly(n), output apartition U1 , U2 , ...Us that, for each input cell Ci ofsize Ω(max{qn, log n}), contains a cell Uj such that
Uj = Ci . We also provide lower bounds that imply
that this bound on the size of Ci cannot be improved
much, even with unlimited computation.
Condon and Karp (CK01) analyzed a nearly lineartime algorithm for recovering a planted partition in
the case that the cells of the partition have the same
size, and this size, and the number of cells, is known tothe algorithm a priori. Their algorithm applies local
perturbation to partition the vertices into two groups,
and then applies the algorithm recursively to each of
the two groups. They used the knowledge of the sizeof the cells to determine whether to make another recursive call or not.
Recent research has provided approximation guarantees for polynomial-time clustering algorithms using
weaker assumptions than the planted partition modelthat we study here (BBC04; KVV04; BBV08), butusing algorithms that require substantially more thanlinear time.

Arrested Spectral Clustering

2. The Problem and Results

McSherry (McS01) analyzed a spectral clustering algorithm using a model much like the embedded partition model studied here. The aim of this work
was to obtain similar guarantees with a faster algorithm. A number of authors have proposed toapproximate the spectrum of similarity matrices forapplications like this by different sampling schemes(WS00; FKV04; DM05; KMT09). Achlioptas and McSherry (AM07) provided a theoretical analysis of theapproximation capabilities of one such scheme. However the approximation is performed, however, when
there are k clusters, the resulting spectral clustering
algorithms appear to take Ω(k 2 ) time. In contrast,
the Subsquare algorithm takes time nearly linear in
the number of edges, no matter how many clusters
there are, which appears to make it more suitable forapplications like near-duplicate detection. This is supported by some experiments – we tried out an algorithm obtained by using a sampling scheme like theone analyzed by Achlioptas and McSherry in concert
with the spectral clustering algorithm proposed by Ng,
Jordan and Weiss (NJW01).

Let G = G(V, E) be a random graph with the set ofvertices V = {v1 , . . . , vn } and set of edges E that isbuilt as follows: (1) Choose an integer t and arbitrary
disjoint subsets C1 , . . . , Ct ⊂ V where C1 ∪ C2 ∪ · · · ∪Ct = V ; (2) For every i ≥ 1 and every v, w ∈ Ci add
the edge (v, w) to E with probability p; (3) For every
1 ≤ i < j ≤ t, v ∈ Ci and w ∈ Cj add the edge (v, w)
to E with probability q.

Bansal, et al (BBC04), in Section 6 of their paper,described an algorithm based on neighborhood overlap, together with a sketch of an analysis in thecase in which edges between members of the samecluster are included with probability 1. Gibson, etal (GKT05) described a somewhat complicated algorithm that starts by applying minhashing to vertex
neighborhoods in an effort to quickly find vertices withsimilar neighborhoods.

2.2. The Algorithm

The Subsquare algorithm proposed in this paper canbe viewed as an approximation to more computational
intensive spectral algorithms. Roughly, the spectral
algorithms like to cluster together a pair (v, w) of vertices if a random walk from v is likely to land at w
(von07). We show that, to obtain guarantees for theembedded partition model, it is sufficient to examine
walks of length 2, or, in other words, to consider theextent to which neighborhoods of pairs of vertices overlap. However, simply squaring the adjacency matrix,
even in combination with random sparsification as in(AM07), appears not to work – if we sparsify sufficiently to achieve nearly linear time, then the neighborhoods of vertices in large clusters will not overlap enough to be detected. When deciding whether
to cluster together two vertices, instead of considering the overlap between random subsamples of bothof their neighborhoods, Subsquare checks how manymembers of a subsample of one vertex’s neighbors arein the list of all of the other vertex’s neighbors.

2.1. Planted partition model
We will analyze algorithms using a slight variant of
the planted partition model (JS98) (see also (CK01;
BLCS87; McS01)).

The choices of whether to add the edges are mutuallyindependent. We call a random graph generated thisway a (p, q)-clustered graph. The sets C1 , . . . , Ct are
called clusters. We can think of clusters of size 1 as
unclustered vertices.
For any vertex v, let C(v) be the cluster containing v,
let N (G, v) be the neighbors of v in G. We also willassume that p ≥ 1/2 (roughly, that a majority of goodedges are present). Let m be the number of edges in
the input graph, and n be the number of vertices.

The algorithm Subsquare makes its clustering decisions based on sampling estimates of some edges ofthe square of the adjacency matrix of G. The algorithm has three parameters, c0 , c1 and δ, which will
be determined in the analysis. Details are as follows:
2.3. Main results
Theorem 1 There are constants c, δ0 , m0 and n0
such that, for all p ∈ [1/2, 1], q ∈ [0, 1], m ≥ m0 ,n ≥ n0 , and 0 < δ ≤ δ0 , if G is a (p, q) clustered graphwith clusters C1 , ..., Ct , then, with probability 1 − δ,Algorithm Subsquare, when run with c0 = c/2 andc1 = c/25 , outputs a partition U1 , ..., Us of the vertices
of G such that, for all cluster indices i such that
|Ci | ≥ c max {qn, log(n/δ)}(1)

there is a output cluster index j such that Ci = Uj .
We will show that a constraint like (1) is necessary.
Note that if all Ci satisfy (1), then Subsquare is guaranteed to output the correct clustering with high probability.
Theorem 2 The expected running time of Subsquareis O(n(log2 (n/δ))(log n) + m log n).

Arrested Spectral Clustering• Choose a random bijection π : V → {1, ..., n}
to order the vertices.
• Make two passes over V in the order given
by π, performing the following steps for eachvertex v:
1. If v has fewer than c0 log(n/δ) neighbors,
assign v to its own cluster and go to thenext v.
2. Let Rtemp consist of the neighbors of v
that have already been assigned to clusters.
3. Form R by independently including
eachnelement of R
otemp with probabilitymin

c0 log(n/δ)|Rtemp | , 1.

4. Choose S by independently including
each member of N (G, v) with probabil0 log(n/δ)
ity c|N(G,v)| .

5. Initialize the set D of candidate clusters
for v to ∅.
6. For each w ∈ R, if(a) |S ∩ N (G, w)| ≥ c1 log(n/δ),(b) |N (G, w)| ≥ c0 log(n/δ), and Sw obtained by sampling each u ∈ N (G, w)
0 log(n/δ)
satisfies
with probability c|N(G,w)||Sw ∩ N (G, v)| ≥ c1 log(n/δ),
add Ĉ(w) (i.e., w’s cluster) to D.
7. If D is not empty, set Ĉ(v) toĈ(argminw′ ∈∪C∈D π(w′ )) and otherwise,start a new cluster consisting only of v.

Figure 1. Algorithm Subsquare.

3. The analysis
Our proof of Theorem 1 is broken up into a series oflemmas.
Throughout this analysis, we will follow the conventionof using “w.h.p.” as a shorthand for “with probability
1 − δ/poly(n)”. As we will see, polynomially many
events will be bounded with this probability, so that,with probability at least 1 − δ, all of them hold. We
will show that, for any polynomial in this confidencebound, some values of the constants in our analysis
will work.
Definition 3 Refer to the comparisons performed fora particular value of w in Step 6 of Subsquare as anedge test. Say that the test succeeds if C(v) = C(w)and v is put into D, or if C(v) 6= C(w) and v is not
put into D.
Note that, to put Ĉ(w) into D, Subsquare requires
both that |S ∩ N (G, w)| ≥ c1 log(n/δ) and that |Sw ∩N (G, v)| ≥ c1 log(n/δ).
Lemma 4 W.h.p., for any vertex v whose cluster
C(v) satisfies (1), at least half of v’s neighbors arein C(v).
Proof: Since edges between vertices from distinct
clusters are included with probability q, we have
E(|N (G, v) − C(v)|) ≤ qn ≤ |C(v)|/16, by (1), as
long as c ≥ 16. But, since |C(v)| ≥ c log(n/δ), thestandard Chernoff bound (see Theorem 4.3 of (MR95))
implies that, w.h.p., |N (G, v) − C(v)| ≤ |C(v)|/8. On
the other hand, since p ≥ 1/2, we have E(|N (G, v) ∩C(v)|) ≥ (|C(v)| − 1)/2, and, since |C(v)| ≥ c log n,
this implies that, w.h.p., |N (G, v) ∩ C(v)| ≥ (|C(v)| −1)/4 ≥ |C(v)|/8.
Lemma 5 For a pair {v, w} of vertices, if C(v) =C(w), and the cluster satisfies (1), and an edge test
is conducted for v and w, then, w.h.p., this edge test
succeeds.
Proof: First, we have that, w.h.p.,|S ∩ C(v)| ≥ (c0 /4) log(n/δ)(2)

since Lemma 4 implies that w.h.p., |N (G, v) ∩ C(v)| ≥|N (G, v)|/2, which in turn implies E(|S ∩ C(v)|) ≥( c0|Nlog(n/δ)(G,v)| )(|N (G, v)|/2), from which (2) follows by a
Chernoff bound.
Now, conditioned on a fixed value of S, which depends
only on the random neighbors of v and the randomization of the algorithm, the events that the membersof S ∩ C(v) are neighbors of w are independent. Given(2), we have
E(|S ∩ N (G, w)|) ≥ E(|S ∩ C(v) ∩ N (G, w)|)
≥ |S ∩ C(v)|/2
since p ≥ 1/2. Thus, a Chernoff bound implies that,w.h.p. |S ∩ N (G, w)| ≥ c1 log(n/δ).
Arguing analogously, we get that, w.h.p. |Sw ∩N (G, v)| ≥ c1 log(n/δ), and therefore the lemma holds.
Lemma 6 For any pair {v, w} of vertices, if C(v) satisfies (1), and an edge test is conducted between v andw, and C(v) 6= C(w), then w.h.p. the edge test is successful.

Arrested Spectral Clustering

Proof: Because the edge test is symmetrical, we may
assume without loss of generality that it takes place
during v’s turn. Thus, it suffices to show that, w.h.p.,
S ∩ N (G, w) < c1 log(n/δ).

Lemma 7 For any C that satisfies (1) for all v ∈ C
and all vertices w, with high probability, if Ĉ(v) =Ĉ(w) then C(v) = C(w).

For each u, let Xu be the random variable that indicates whether u ∈ N (G, v) ∩ N (G, w). Suppose that
{Yu : u ∈ V } are {0, 1}-valued
randomo variables suchn

Proof: This follows from induction using Lemma 6.

for all u, andthat Pr(Yu = 1) = min c0|Nlog(n/δ)(G,v)| , 1
that are mutually independent. We can think of thevariables Yu as an extension of all of V of the randomvariables that were used to decide whether to include
each member of N (G, v) in S.
We claim that w.h.p.,XYu ≥ (c0 /2) log(n/δ).

(3)u∈N (G,v)

If |N (G, v)| ≤ c0 log(n/δ), this is because in thiscase
P Pr(Yu = 1) = 1 for all u, and thereforeu∈N (G,v) Yu = |N (G, v)|. Otherwise, it follows froma Chernoff bound, together with the fact thatX
Yu  ≥ c0 log(n/δ).
E
u∈N (G,v)

Since S is a subset of the vertices
P for which Yu = 1,
we have that |S ∩ N (G, w)| ≤ u∈V −{v,w} Xu Yu .

Note that, though {Xu Yu : u ∈ V − {v, w}} might
not be independent, after we condition the values of{Xu : u ∈ V − {v, w}}, then they are.
P We will firstobtain a high probability
boundonu Xu , and thenP
use it to get a bound on u Xu Yu that holds with highprobability.
For each u ∈ V − {v, w}, either u 6∈ C(v) or u 6∈C(w),P so Pr(u ∈ N (G, v) ∩ N (G, w)) ≤ pq. Thus
E( u Xu ) ≤ pqn ≤ qn ≤ |C(v)|/29 by (1), so longas c ≥ 29 . Note that each Xu is determined solely by
the random generation of the graph, thus the various
Xu variables are mutuallyaPindependent. Applying
8
Chernoff bound, w.h.p.,u Xu ≤ |C(v)|/2 . Sincep ≤ 1/2, w.h.p., |N (G, v)| ≥ |C(v)|/4, soXXu ≤ |N (G, v)|/26 .
(4)uSince for each u, Pr(Yu = 1) ≤ c0|Nlog(n/δ)(G,v)| , we
have
that,
conditioned
on
the
event
that
(4) holds,P
E( u Xu Yu ) ≤ (c0 /25 ) log(n/δ) ≤ (c1 /2) log(n/δ).
Applying another Chernoff bound together with thefact that the Yu ’s are independent completes the proof.

Definition 8 The first member of a cluster C encountered by Subsquare is called the head of C.
Lemma 9 During the first pass through the vertices,
for any C that satisfies (1), for any vertex v with anedge to the head vC of C, w.h.p., Ĉ(v) = Ĉ(vC ).
Proof: The proof is by induction on π(v).
If |Rtemp | ≤ c0 log(n/δ), then vC ∈ R and the lemma
follows from Lemma 5.
Suppose |Rtemp | > c0 log(n/δ). Since p ≥ 1/2,
w.h.p., |Rtemp ∩ N (G, vC )| > |Rtemp |/4. Thus, E(|R ∩N (G, vC )|) ≥ (c0 /4) log(n/δ), and, therefore, w.h.p.
|R ∩ N (G, vC )| =6 ∅, and the lemma follows from
Lemma 5 together with the inductive hypothesis, together with the fact that Subsquare assigns v to thecluster in D with the least head node.
Lemma 10 During the second pass through the vertices, for any C that satisfies (1), for any v ∈ C,
Ĉ(v) = Ĉ(vC ).
Proof: Since p ≥ 1/2, E(|N (G, v) ∩ N (G, vC )|) ≥|N (G, v)|/2.
During the second pass, Rtemp =N (G, v), thus, w.h.p., |R ∩ N (G, vC )| =6∅. By
Lemma 9, though, for any w ∈ N (G, vC ), after the
first pass, w.h.p., Ĉ(w) = Ĉ(vC ). So, w.h.p., some w
with Ĉ(w) = Ĉ(vC ) will be in R. The lemma thenfollows from Lemma 5.
Now that we have finished the proof of Theorem 1, we
now turn to Theorem 2, the analysis of the running
time.
Proof of Theorem 2: In O(m log n) time, Subsquarecan create a data structure that will enable it to test
membership in N (G, v) for any vertex v in O(log n)time. This can be done by creating a balanced binary
tree for each vertex v with the neighbors of v on theleaves. These “neighbor trees” can be found if there isa higher-level balanced binary tree that has a pointerto a neighbor tree for each vertex v at each leaf.
We can then see that, for each vertex, at mostO(log(n/δ)) candidate clusters are examined, and eachcandidate requires neighbor lookups for O(log(n/δ))neighbors, each requiring O(log n) time.

Arrested Spectral Clustering

4. Lower bounds
Theorem 11 For any function ψ such that ψ(n) =o(log(n)), there is no algorithm A with the following
property:
There are constants c, m0 and n0 such that,for all p ∈ [1/2, 1], q ∈ [0, 1], m ≥ m0 , andn ≥ n0 , if G is a (p, q) clustered graph withclusters C1 , ..., Ct , then, with probability 1/8,
Algorithm A, outputs a partition U1 , ..., Us ofthe vertices of G such that, for all cluster indices i such that |Ci | ≥ c max {qn, ψ(n)} there
is a output cluster index j such that Ci = Uj .
Proof Sketch: Suppose p = 1/2 and q = 0. Lett = n/(cψ(n)).
We will show that, for a randomly chosen partition
C1 , ..., Ct , Algorithm A fails with probability at least
1/8, which will imply the existence of a partition
C1 , ..., Ct with this property. Suppose that the random partition over the vertices v1 , ..., vn is chosen by
assigning vi to Ci for i ≤ t, and, for i > t, assigningeach vertex independently to a random cluster. Let C
be this clustering.
Suppose further that, if any vertex v 6∈ {v1 , ..., vt }(i.e., whose cluster assignment was chosen randomly)
is not incident on any edges, then Algorithm A is given
the cluster assignments of all vertices other than v.
A lower bound given this assumption implies a lower
bound for the original clustering problem, since A has
the option to ignore the additional information.

variables obey Chernoff bounds (see (DR98)), we haveX
Bi ≤ 2) ≤ exp(−(t/8)(1 − 1/t)n−t−1 )
Pr(
i



(1 − 1/t)n−t−1= exp −ncψ(n)= exp(−n exp(−Θ(ψ(n)))) = exp(−n1−o(1) ).
Thus, for large enough n, with probability at least
1/2, we have that, for distinct i and j, ni = nj = 1,
and thus the conditional probability that A makes
a mistake, given that N (G, v) = ∅, is at least 1 −Pt1 −n ≥ 1/2.
i
2+

i=3

2

Now let us compute a lower bound on the probability that any vertex is disconnected. At least t/2 ofthe clusters have at most 2n/t elements. Let us callthese clusters light. Let us lower bound the probabilityof an isolated vertex by the probability of an isolated
vertex in a light cluster. For some such cluster, let ℓbe the number of elements in the cluster. Any individual vertex in the cluster is disconnected from the restwith probability 2−ℓ , so the probability that the cluster is not connected is at least this large. Since theedges in different clusters are chosen independently,
the probability that any light cluster is disconnected
is therefore at least 1 − (1 − 2−2n/t )t/2 which is at least
1 − exp(−(t/2)2−2n/t ). Now,limt −2n/t
2
= lim

n→∞ 2

n

n→∞ 2ψ(n)2−2cψ(n)= lim exp(ln n − o(ln n)) = ∞.
n→∞

= (C1′ , ..., Ct′ ) consists of the cluster assignments

If C
to vertices other than v, we have Pr(C(v) = j|G) =Pr(C(v) = j|N (G, v), C ′ ).

Thus, for large enough n, the probability that somecluster is disconnected is at least 1/2, so that the probability of error is at least 1/8.

Further, applying Bayes’ rule, it is possible to show

Theorem 12 For any function ψ such that ψ(n) =o (n), there is no algorithm A with the following property:′−|C ′ |jthat Pr(C(v) = j|N (G, v) = ∅, C ) = t Pr(N2(G,v)=∅|C ′ ) .

′Thus, given that N (G, v) = ∅, together with theknowledge of the cluster assignments other than v,
a Bayes optimal algorithm chooses arbitrarily fromamong the clusters of smallest size, and, if ni = |Ci′ |,then the probability that the Bayes optimal algorithm
max 2−njmakes an error on v is 1 − Pt j −nj .
j=1

2

We claim that, for large enough n, with probability
1/2, the cluster assignments to vertices other than v
leave at least two clusters with one member each. Leteach B1 , ..., Bt be an indicator variable for whether thecorresponding cluster in C1 , ..., Ct has more than one
member. B1 , ..., Bt are negatively associated in thesense of (JP83) (see (DR98)). For each i, E(Bi ) =(1 − 1/t)n−t−1 . Since negatively associated random

There are constants c, m0 and n0 such that,for all p ∈ [1/2, 1], q ∈ [0, 1], m ≥ m0 , andn ≥ n0 , if G is a (p, q) clustered graph withclusters C1 , ..., Ct , then, with probability 3/4,
Algorithm A, outputs a partition U1 , ..., Us ofthe vertices of G such that, for all cluster indices i such that |Ci | ≥ c max {qψ(n), log n}there is a output cluster index j such that
Ci = Uj .
n⌋ and p = q = 1/2. Note that,
Proof: Let t = ⌊ ψ(n)since ψ(n) = o(n), if n is large enough, t ≥ 2.

Suppose C = (C1 , C2 , ..., Ct ) is obtained by picking an
arbitrary vertex v, randomly partitioning the remain-Arrested Spectral Clusteringing vertices into equal-sized clusters, and then randomly assigning v to one of those clusters.
Since the edge probabilities are unaffected by the cluster assignments, and algorithm A that makes random
cluster assignments is Bayes optimal, and therefore its
probability of error is at least 1 − 1/t ≥ 1/2. Since thisis true on average for a randomly chosen clustering C,
there exists a clustering C such that A has probability
1/2 of making an error for C.

5. Experiments
5.1. Modifications to Subsquare
We performed our experiments with a slightly modified
version of Subsquare.
First, instead of independently randomly putting eachlog(n/δ), the modifiedvertex in R with probability c0|R
temp |
algorithm sets R to be a random subset of size at mostc0 log(N/δ), and it chooses S similarly.
Second, in Step 6 of Figure 1, instead of requiring thatw has c0 log(N/δ) neighbors, the revised algorithm estimates the probability that a random neighbor of w is
also a neighbor of v dividing the number of neighborsof w found in v’s adjacency list by one more than thenumber of neighbors tried.
Third, when computing the above statistics, the counts
for neighbors w of v that have been assigned to thesame cluster C(w) are consolidated, so that the algorithm computes an overall estimate p̂(C, v) of theprobability that a random neighbor of v is in an adjacency list of a random vertex that has been assigned
to cluster C. Vertex v is then assigned to the cluster,from among those for which p̂(C, v) ≥ θ, which contained the most of the neighbors w that were examined
during v’s turn.
5.2. Other Algorithms
The first, inspired by the analysis of Achlioptas and
McSherry (AM07), randomly samples edges with probability p, and then applies the spectral clustering algorithm of Ng, Jordan and Weiss (NJW01). The NJW
algorithm requires the user to specify the number kof clusters. We computed the top eigenvectors using
the iterative block power method (Str86) which has
the number of iterations as an adjustable parameter.
The NJW algorithm also calls for the application of
k-means, which also has a variable number of iterations. We experimented with various settings of theseparameters, as described below.
The second is an algorithm that performs minhash-ing (Coh97; Bro97), and forms a cluster from eachbucket. This can be equivalently described as an algorithm that processes the vertices in random order,
and, if a vertex v has not been assigned a cluster when
it was encountered, a new cluster is formed with v andits unclustered neighbors.
The third is version 9.308 of MCL (vD00; EVDO02).
The key parameter for MCL, which trades between
precision and recall, is called “expansion”. We foundthat, on this data, the default value of 2 optimized excessively for precision, so we tried 1.5, 2, and 3 whichroughly covered the range of values suggested on the
MCL website. To save space, we report only on thebest result, for 1.5, below (the other results are significantly worse). While Subsquare and the minhashalgorithm were coded in python in the most straightforward way, the MCL implementation is optimized C
code.
5.3. Chinese Restaurant Process Data
To get large-scale data with known cluster assignments and some variety in cluster sizes, we generated data by first partitioning the vertices using a
Chinese restaurant process (Pit95; Teh10) with α =1 and θ = −20/n. This tends to generate clusters of sizes roughly on the order of 20 vertices,which is similar to the most challenging applications
targeted in this work. We generated graphs withn = 10000, 20000, 50000, 100000 vertices. We included
edges between vertices in the same cell with probability 1/2, and then added random edges until the number of such “noisy” edges was equal to the number of“clean” edges. For each such dataset we ran Subsquareand the minhash algorithm 10 times, and averaged theprecision and recall obtained. (When computing precision and recall, we interpret a clustering as a seriesof predictions of whether each pair of vertices are in
the same cluster.) We also recorded the time taken byeach algorithm. We stopped the MCL algorithm after
it ran for 1000 minutes on the two larger datasets.
We ran Subsquare with δ and c1 chosen so thatc1 log(n/δ) = 100, and with the threshold θ describedin Section 5.1 chosen to be 0.05.
Results are as follows (time is in minutes):

n
10000
20000
50000
100000

Minhash
time
F
1
0.24
1
0.24
1
0.24
3
0.24

Subsquare
time
F
3
0.97
6
0.98
13
0.99
28
0.99

MCL
time
F
47
0.96
175
0.97
>1000
>1000

Arrested Spectral Clustering

The time required by Subsquare is seen to scale linearly with the number of vertices. Subsquare achieves
better accuracy than MCL while requiring an orderof magnitude less time. The time required by MCL
appears to be scaling superlinearly.
For the sampling spectral algorithm, we tried (a) sampling each edge with various probabilities p: 0.05, 0.1,
0.2; (b) setting the number of clusters to various values s: 100, 200, 500 (since the expected size of eachcluster is 20 the true number is approximately 500);(c) running the block power method for various numbers of iterations Ipow : 10, 25, and 100; (d) runningk-means for various numbers of iterations Ik : 2, 5,
and 10. We tried all 81 combinations of these parameters on the n = 10000 dataset. After eliminating the
combinations that required more than 1000 minutes
to run, the five combinations of parameters with thebest values of the F -score are shown, along with theSubsquare result.
p
0.2
0.2
0.2
0.2
0.2

s
Ipow
200
25
200
10
200
10
200
25
100 100
Subsquare

Ik
10
10
5
5
10

time
503
231
212
466
920
3

F-score
0.59
0.55
0.53
0.52
0.40
0.97

5.4. Bi-holdout experiments
To evaluate algorithms on the DBLP data, we used asingle training-test split variant of bi-cross-validation(Gab02; OP09), which might be called a bi-holdout
experiment. For graph-based clustering, the most natural application of bi-cross-validation appears to be torepeatedly apply the following steps: (a) Randomly
split the vertices into training vertices U and test vertices W; (b) Run each algorithm on the subgraph induced by U , called the “training graph”; (c) For eachtest vertex w ∈ W , determine the cluster assignment of
w by using the assignment made to a random neighborof w in U . (The edges of the graph consisting only ofedges with one vertex in W and one vertex in U , whichmight be called the “bridge graph”, are used for this.);(d) For each pair of vertices in W , predict that there isan edge between them if and only if they are assigned
to the same cluster in the preceding step; (e) Compare
the predictions with the actual presence of absence ofedges between vertices in W (these edges constitutethe “test graph”). We only used a single training-test
split because our graphs are large. A fraction 1/10 ofthe vertices were placed in the test graph.
We first used the bi-holdout estimate to compare thealgorithms on the synthetic data described above. We
applied both Subsquare and the minhash algorithm tothe graph in the n=100000 case, and compared theresults using this protocol. The Subsquare algorithm
achieved an F-score of 0.136, where the minhash algorithm obtained 0.046. While Subsquare still performs better, the edge-prediction accuracy obtained ismuch smaller than the cluster-membership accuracy
that was measured earlier. This is not surprising, inlight of the fact that there are three chances for a correct determination that two vertices u and v in the test
graph should be clustered together to fail to be recognized by this protocol: (1) the edge between u and v
may be missing from the graph, (2) a spurious edge
from u to the training graph may be chosen, and (3)a spurious edge from v to the training graph may bechosen. Nevertheless, since these should be expectedto effect all algorithms equally, the statistics obtained
through this protocol should still give an idea of therelative merit of clustering algorithms.
Next, we applied performed a similar experiment using
the titles in the DBLP database. We used a variantof minhashing (Coh97; CDF+ 01; LCH08) to computethe similarity graph. Each title was summarized using
a bag of its length-4 substrings (called “k-mers”, withk = 4). Next, we removed all k-mers that appearedin at least 1000 titles from all bags. We then fixed arandom permutation of the k-mers, and further summarized each title by a list of the first 25 k-mers, insorted order according to this permutation, appearing
in its bags. Titles whose resulting “sketches” shared atleast 5 k-mers were deemed similar and given an edgein the graph. The resulting graph had roughly 1.5 million edges, and was clustered by Subsquare on a fouryear-old desktop workstation in less than 25 minutes.
The bi-holdout F-score for Subsquare (here with δ andc1 chosen so that c1 log(n/δ) = 100 and θ = 0.9)) was
0.504, where the minhash algorithm obtained 0.471.

References[AM07] D. Achlioptas and F. McSherry. Fast computation of low-rank matrix approximations. JACM, 54(2), 2007.
[AV79] D. Angluin and L. Valiant. Fast probabilistic algorithms for Hamiltonion circuits andmatchings. J. Comp. Sys. Sci., 18(2):155–
193, 1979.
[BBC04] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(13):89–113, 2004.
[BBV08] M. Balcan, A. Blum, and S. Vempala. A

Arrested Spectral Clustering

discriminative framework for clustering via
similarity functions. STOC, 2008.
[BLCS87] T. N. Bui, F. T. Leighton, S. Chaudhuri,
and M. Sipser. Graph bisection algorithms
with good average case behavior. Combinatorica, 7(2):171–191, 1987.
[Bol85] B. Bollobas. Random Graphs. Academic
Press, 1985.
[Bro97] Andrei Z. Broder. On the resemblance andcontainment of documents. SEQUENCES,
pages 21–29, 1997.
[CDF+ 01] E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J. D. Ullman,
and C. Yang. Finding interesting associations without support pruning. IEEE
Trans. Knowl. Data Eng., 13(1):64–78,
2001.
[CK01] A. E. Condon and R. M. Karp. Algorithms
for graph partitioning on the planted partition model. Random Structures and Algorithms, 18(2):221–232, 2001.
[Coh97] E. Cohen.
Size-estimation frameworkwith applications to transitive closure andreachability. JCSS, 55(3):441–453, 1997.
[DM05] P. Drineas and M. W. Mahoney. Approximating a gram matrix for improved kernelbased learning. COLT, 2005.
[DR98] D. Dubhashi and D. Ranjan.
Balls
and bins: A study in negative dependence. Random Structures & Algorithms,
13(2):99–124, 1998.
[EVDO02] A. J. Enright, S. Van Dongen, and C. A.
Ouzounis. An efficient algorithm for largescale detection of protein families. Nucl.
Acids Res., 30(7):1575–1584, 2002.
[FKV04] A. Frieze, R. Kannan, and S. Vempala. Fast monte-carlo algorithms forfinding low-rank approximations. JACM,
51(6):1025–1041, 2004.

[JP83] K. Joag-Dev and F. Proschan. Negative association of random variables, withapplications. The Annals of Statistics,
11(1):286–295, 1983.
[JS98] M. Jerrum and G. B. Sorkin. The metropolis algorithm for graph bisection. Discrete Applied Mathematics, 82(1-3):155–
175, 1998.
[KMT09] S. Kumar, M. Mohri, and A. Talwalkar.
On sampling-based approximate spectral
decomposition. ICML, 2009.
[KVV04] R. Kannan, S. Vempala, and A. Vetta. On
clusterings: Good, bad and spectral. J.
ACM, 51(3):497–515, 2004.
[LCH08] P. Li, K. W. Church, and T. L. Hastie. One
sketch for all: theory and application of
conditional random sampling. NIPS, 2008.
[McS01] F. McSherry. Spectral partitioning of random graphs. FOCS, 2001.
[MR95] R. Motwani and P. Raghavan. Randomized
Algorithms. Cambridge University Press,
1995.
[NJW01] A. Y. Ng, M. I. Jordan, and Y. Weiss. On
spectral clustering: Analysis and an algorithm. NIPS, 2001.
[OP09] A. B. Owen and P. O. Perry. Bi-crossvalidation of the SVD and nonnegative matrix factorization. The Annals of Applied
Statistics, 3(2):564–594, 2009.
[Pit95] J. Pitman. Exchangeable and partiallyexchangeable random partitions. Probab.
Theory Relat. Fields, 102:145–158, 1995.
[Str86] G. Strang. Linear Algebra and its applications – third edition. Saunders College,
1986.
[Teh10] Y. W. Teh. Dirichlet processes. In Encyclopedia of Machine Learning. 2010.
[vD00] S. van Dongen. Graph Clustering by Flow
Simulation. PhD thesis, University of
Utrecht, 2000.

[Gab02] K. Gabriel. Le biplot-outil d’ exploration
de donn’ees multidimensionelles. Journal de la Societe Francoise de Statistique,
143:5–55, 2002.

[von07] U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing,17(4):395–416, 2007.

[GKT05] D. Gibson, R. Kumar, and A. Tomkins.
Discovering large dense subgraphs in massive graphs. VLDB, 2005.

[WS00] C. K. I. Williams and M. Seeger. Using
the Nyström method to speed up kernel
machines. NIPS, 2000.