Communication-Optimal Distributed Clustering∗
Jiecao Chen†

He Sun‡

David P. Woodruff§

Qin Zhang¶

arXiv:1702.00196v1 [cs.DS] 1 Feb 2017

Abstract
Clustering large datasets is a fundamental problem with a number of applications in machine
learning. Data is often collected on different sites and clustering needs to be performed in a
distributed manner with low communication. We would like the quality of the clustering in
the distributed setting to match that in the centralized setting for which all the data resides
on a single site. In this work, we study both graph and geometric clustering problems in two
distributed models: (1) a point-to-point model, and (2) a model with a broadcast channel. We
give protocols in both models which we show are nearly optimal by proving almost matching
communication lower bounds. Our work highlights the surprising power of a broadcast channel
for clustering problems; roughly speaking, to spectrally cluster n points or n vertices in a graph
distributed across s servers, for a worst-case partitioning the communication complexity in a
point-to-point model is n · s, while in the broadcast model it is n + s. A similar phenomenon
holds for the geometric setting as well. We implement our algorithms and demonstrate this
phenomenon on real life datasets, showing that our algorithms are also very efficient in practice.

∗

A preliminary version of this paper appears at the 30th Annual Conference on Neural Information Processing
Systems (NIPS), 2016.
†
Department of Computer Science, Indiana University, Bloomington, USA. Work supported in part by NSF CCF1525024 and IIS-1633215. Email: jiecchen@indiana.edu
‡
Department of Computer Science, University of Bristol, Bristol, UK. h.sun@bristol.ac.uk
§
IBM Research Almaden, San Jose, USA. dpwoodru@us.ibm.com
¶
Department of Computer Science, Indiana University, Bloomington, USA. Work supported in part by NSF CCF1525024 and IIS-1633215. Email: qzhangcs@indiana.edu

Contents
1 Introduction
1.1 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
2

2 Preliminaries
2.1 Graph Laplacian . . . . . .
2.2 Spectral sparsification . . .
2.3 Models of computation . . .
2.4 Communication complexity
2.5 Information complexity . .

.
.
.
.
.

3
3
3
4
5
5

3 Distributed graph clustering
3.1 The message passing model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 The blackboard model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
6
8

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

4 Distributed geometric clustering
9
4.1 The message passing model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 The blackboard model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Experiments
5.1 Datasets. . . . . . . . . . . . . . . . . . . .
5.2 Results on clustering quality . . . . . . . . .
5.3 Results on communication costs . . . . . . .
5.4 Parameters in MsgPassing and Blackboard

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

13
13
14
15
15

1

Introduction

Clustering is a fundamental task in machine learning with widespread applications in data mining,
computer vision, and social network analysis. Example applications of clustering include grouping
similar webpages by search engines, finding users with common interests in a social network, and
identifying different objects in a picture or video. For these applications, one can model the objects
that need to be clustered as points in Euclidean space Rd , where the similarities of two objects are
represented by the Euclidean distance between the two points. Then the task of clustering is to
choose k points as centers, so that the total distance between all input points to their corresponding
closest center is minimized. Depending on different distance objective functions, three typical
problems have been studied: k-means, k-median, and k-center.
The other popular approach for clustering is to model the input data as vertices of a graph,
and the similarity between two objects is represented by the weight of the edge connecting the
corresponding vertices. For this scenario, one is asked to partition the vertices into clusters so
that the “highly connected” vertices belong to the same cluster. A widely-used approach for graph
clustering is spectral clustering, which embeds the vertices of a graph into the points in Rk through
the bottom k eigenvectors of the graph’s Laplacian matrix, and applies k-means on the embedded
points.
Both the spectral clustering and the geometric clustering algorithms mentioned above have
been widely used in practice, and have been the subject of extensive theoretical and experimental
studies over the decades. However, these algorithms are designed for the centralized setting, and
are not applicable in the setting of large-scale datasets that are maintained remotely by different
sites. In particular, collecting the information from all the remote sites and performing a centralized
clustering algorithm is infeasible due to high communication costs, and new distributed clustering
algorithms with low communication cost need to be developed.
There are several natural communication models, and we focus on two of them: (1) a point-topoint model, and (2) a model with a broadcast channel. In the former, sometimes referred to as
the message-passing model, there is a communication channel between each pair of users. This may
be impractical, and the so-called coordinator model can often be used in place; in the coordinator
model there is a centralized site called the coordinator, and all communication goes through the
coordinator. This affects the total communication by a factor of two, since the coordinator can
forward a message from one server to another and therefore simulate a point-to-point protocol.
There is also an additional additive O(log s) bits per message, where s is the number of sites,
since a server must specify to the coordinator where to forward its message. In the model with a
broadcast channel, sometimes referred to as the blackboard model, the coordinator has the power
to send a single message which is received by all s sites at once. This can be viewed as a model for
single-hop wireless networks.
In both models we study the total number of bits communicated among all sites. Although the
blackboard model is at least as powerful as the message-passing model, it is often unclear how to
exploit its power to obtain better bounds for specific problems. Also, for a number of problems the
communication complexity is the same in both models, such as computing the sum of s length-n
bit vectors modulo two, where each site holds one bit vector [21], or estimating large moments [23].
Still, for other problems like set disjointness it can save a factor of s in the communication [5].

1.1

Our contributions

We present algorithms for graph clustering: for any n-vertex graph whose edges are arbitrarily
e
partitioned across s sites, our algorithms have communication cost O(ns)
in the message passing
1

e + s) in the blackboard model, where the O
e notation
model, and have communication cost O(n
suppresses polylogarithmic factors. The algorithm in the message passing model has each site
send a spectral sparsifier of its local data to the coordinator, who then merges them in order to
obtain a spectral sparsifier of the union of the datasets, which is sufficient for solving the graph
clustering problem. Our algorithm in the blackboard model is technically more involved, as we
show a particular recursive sampling procedure for building a spectral sparsifier can be efficiently
implemented using a broadcast channel. It is unclear if other natural ways of building spectral
sparsifiers can be implemented with low communication in the blackboard model. Our algorithms
demonstrate the surprising power of the blackboard model for clustering problems. Since our
algorithms compute spectral sparsifiers, they also have applications to solving symmetric diagonally
dominant linear systems in a distributed model. Any such system can be converted into a system
involving a Laplacian (see, e.g., [1]), from which a spectral sparsifier serves as a good preconditioner.
Next we show that Ω(ns) bits of communication is necessary in the message passing model to
even recover a constant fraction of a cluster, and Ω(n + s) bits of communication is necessary in
the blackboard model. This shows the optimality of our algorithms up to poly-logarithmic factors.
We then study clustering problems in constant-dimensional Euclidean space. We show for any
c > 1, computing a c-approximation for k-median, k-means, or k-center correctly with constant
probability in the message passing model requires Ω(sk) bits of communication. We then strengthen
this lower bound, and show even for bicriteria clustering algorithms, which may output a constant
factor more clusters and a constant factor approximation, our Ω(sk) bit lower bound still holds. Our
proofs are based on communication and information complexity. Our results imply that existing
e
algorithms [3] for k-median and k-means with O(sk)
bits of communication, as well as the folklore
e
parallel guessing algorithm for k-center with O(sk) bits of communication, are optimal up to polylogarithmic factors. For the blackboard model, we present an algorithm for k-median and k-means
e + k) bits of communication. This again separates
that achieves an O(1)-approximation using O(s
the models.
We give empirical results which show that using spectral sparsifiers preserves the quality of
spectral clustering surprisingly well in real-world datasets. For example, when we partition a graph
with over 70 million edges (the Sculpture dataset) into 30 sites, only 6% of the input edges
are communicated in the blackboard model and 8% are communicated in the message passing
model, while the values of the normalized cut (the objective function of spectral clustering) given
in those two models are at most 2% larger than the ones given by the centralized algorithm, and
the visualized results are almost identical. This is strong evidence that spectral sparsifiers can
be a powerful tool in practical, distributed computation. When the number of sites is large, the
blackboard model incurs significantly less communication than the message passing model, e.g., in
the Twomoons dataset when there are 90 sites, the message passing model communicates 9 times as
many edges as communicated in the blackboard model, illustrating the strong separation between
these models that our theory predicts.

1.2

Related work

There is a rich literature on spectral and geometric clustering algorithms from various aspects (see,
e.g., [2, 19, 20, 22]). Balcan et al. [3, 4] and Feldman et al. [10] study distributed k-means ([3]
also studies k-median), and present provable guarantees on the clustering quality. Very recently
Guha et al. [11] studied distributed k-median/center/means with outliers. Cohen et al. [7] study
dimensionality reduction techniques for the input data matrices that can be used for distributed
k-means. The main takeaway is that there is no previous work which develops protocols for spectral
clustering in the common message passing and blackboard models, and lower bounds are lacking as
2

well. For geometric clustering, while upper bounds exist (e.g., [3, 4, 10]), no provable lower bounds
in either model existed, and our main contribution is to show that previous algorithms are optimal.
We also develop a new protocol in the blackboard model.

2

Preliminaries

Let G = (V, E, w) be an undirected graph with n vertices, m edges, and weight function
P V ×V →
R≥0 . The set of neighbors of a vertex v is represented by N (v), and its degree is dv = u∼v w(u, v).
The
P maximum degree of G is defined to be ∆(G) = max
P v {dv }. For any set S ⊆ V , let µ(S) ,
v∈S dv . For any sets S, T ⊆ V , we define w(S, T ) ,
u∈S,v∈T w(u, v) to be the total weight of
edges crossing S and T . We define the conductance of any set S by
φ(S) =

w(S, V \ S)
.
µ(S)

For two sets X and Y , the symmetric difference of X and Y is defined as X4Y , (X \Y )∪(Y \X).
For any matrix A ∈ Rn×n , let λ1 (A) ≤ · · · ≤ λn (A) = λmax (A) be the eigenvalues of A. For
any two matrices A, B ∈ Rn×n , we write A  B to represent B − A is positive semi-definite (PSD).
Notice that this condition implies that x| Ax ≤ x| Bx for any x ∈ Rn . Sometimes we also use a
weaker notation (1 − ε)A r B r (1 + ε)A to indicate that
(1 − ε)x| Ax ≤ x| Bx ≤ (1 + ε)x| Ax
for all x in the row span of A.

2.1

Graph Laplacian

The Laplacian matrix of G is an n × n matrix LG defined by LG = DG − AG , where AG is
the adjacency matrix of G defined by AG (u, v) = w(u, v), and DG is the n × n diagonal matrix
with DG (v, v) = dv for any v ∈ V [G]. Alternatively, we can write LG with respect to a signed
edge-vertex incidence matrix : we assign every edge e = {u, v} an arbitrary orientation, and let
BG (e, v) = 1 if v is e’s head, BG (e, v) = −1 if v is e’s tail, and BG (e, v) = 0 otherwise. We
further define a diagonal matrix WG ∈ Rm×m , where WG (e, e) = we for any edge e ∈ E[G].
|
Then, we can write LG as LG = BG
WG BG . The normalized Laplacian matrix of G is defined
−1/2
−1/2
−1/2
−1/2
by LG , DG LG DG
= I − DG AG DG . We sometimes drop the subscript G when the
underlying graph is clear from the context.

2.2

Spectral sparsification

For any undirected and weighted graph G = (V, E, w), we say a subgraph H of G with proper
reweighting of the edges is a (1 + ε)-spectral sparsifier if
(1 − ε)LG  LH  (1 + ε)LG .

(1)

By definition, it is easy to show that, if we decompose the edge set of a graph G = (V, E) into
E1 , . . . , E` for a constant ` and Hi is a spectral sparsifier of Gi = (V, Ei ) for any 1 ≤ i ≤ `, then
the graph formed by the union of edge sets from Hi is a spectral sparsifier of G. It is known that,
for any undirected graph G of n vertices, there is a (1 + ε)-spectral sparsifier of G with O(n/ε2 )
edges, and it can be constructed in almost-linear time [15].
The following lemma shows that a spectral sparsifier preserves the clustering structure of a
graph.
3

Lemma 2.1. Let H be a (1 +
 ε)-spectral sparsifier of G for some ε ≤ 1/3. Then, it holds for any
1
set S ⊆ V that φH (S) ∈ 2 , 2 φG (S).
Proof. Let xu ∈ Rn be the indicator vector of vertex u, i.e., xu (v) = 1 if u = v, and xu (v) = 0
otherwise. We have that
(1 − ε) · x|u LG xu ≤ x|u LH xu ≤ (1 + ε) · x|u LG xu ,
which implies that (1 − ε) · µG (S) ≤ µH (S) ≤ (1 + ε) · µG (S) for any subset S.
Similarly, for any set S ⊆ V we define the indicator vector of S by xS ∈ Rn , where xS (u) = 1
if u ∈ S, and xS (u) = 0 otherwise. Hence, x|S LG xS = wG (S, V \ S), and x|S LH xS = wH (S, V \ S).
Combining these with (1), we have that
(1 − ε) · wG (S, V \ S) ≤ wH (S, V \ S) ≤ (1 + ε) · wG (S, V \ S).
Hence, for any subset S we have that
φH (S) =

wH (S, V \ S)
(1 + ε)wG (S, V \ S)
≤
≤ 2 · φG (S),
µH (S)
(1 − ε)µG (S)

where the last inequality holds by assuming ε ≤ 1/3. Similarly, we have that
φH (S) =

wH (S, V \ S)
(1 − ε)wG (S, V \ S)
1
≥
≥ · φG (S).
µH (S)
(1 + ε)µG (S)
2

Hence, φH (S) and φG (S) differ by at most a factor of 2 for any vertex set S.

2.3

Models of computation

We study distributed clustering in two models for distributed data: the message passing model
and the blackboard model. The message passing model represents those distributed computation
systems with point-to-point communication, and the blackboard model represents those where
messages can be broadcast to all parties.
More precisely, in the message passing model there are s sites P1 , . . . , Ps , and one coordinator.
These sites can talk to the coordinator through a two-way private channel. In fact, this is referred
to as the coordinator model in Section 1, where it is shown to be equivalent to the point-to-point
model up to small factors. The input is initially distributed at the s sites. The computation is in
terms of rounds: at the beginning of each round, the coordinator sends a message to some of the s
sites, and then each of those sites that have been contacted by the coordinator sends a message back
to the coordinator. At the end, the coordinator outputs the answer. In the alternative blackboard
model, the coordinator is simply a blackboard where these s sites P1 , . . . , Ps can share information;
in other words, if one site sends a message to the coordinator/blackboard then all the other s − 1
sites can see this information without further communication. The order for the sites to speak is
decided by the contents of the blackboard.
For both models we measure the communication cost as the total number of bits sent through
the channels. The two models are now standard in multiparty communication complexity (see,
e.g., [5, 21, 23]). They are similar to the congested clique model [16] studied in the distributed
computing community; the main difference is that in our models we do not post any bandwidth
limitations at each channel but instead consider the total number of bits communicated.

4

2.4

Communication complexity

For any problem A and any protocol Π solving A, the communication complexity of a protocol
Π is the maximum communication cost of Π over all possible inputs X. When the protocol is
randomised, we define the error of Π by
max P (the coordinator outputs an incorrect answer on X) ,
X

where the max is over all inputs X and the probability is over all random strings of the coordinator
and s sites. The δ-error randomised communication complexity Rδ (A) of a problem A in the
message passing model is the minimum communication complexity of any randomised protocol Π
that solves A with error at most δ.
Let µ be an input distribution on X. We call a deterministic protocol (δ, µ)-error if it gives the
correct answer for A on at least a 1−δ fraction of all input pairs, weighted by the distribution µ. We
denote Dδ,µ (A) as the cost of the minimum-communication (δ, µ)-error protocol. A standard lemma
in communication complexity called Yao’s minimax lemma shows that Rδ (A) ≥ maxµ Dδ,µ (A).

2.5

Information complexity

We abuse notation by using Π for both the protocol and its transcript (its concatenation of messages). In the message passing model, let Πi (i ∈ [s]) be the transcript (set of messages exchanged)
between the i-th site and the coordinator. Then Π can be seen as a concatenation Π1 ◦ Π2 ◦ . . . ◦ Πs
ordered by the timestamps of the messages. We define the information complexity of a problem A
in the message passing model by
X
ICµ,δ (A) =
min
I(X1 , . . . , Xs ; Πi ),
(δ,µ)-error Π

i∈[s]

where I(· ; ·) is the mutual information function. It has been shown in [12] that Rδ (A) ≥ ICδ,µ (A)
for any input distribution µ.

3

Distributed graph clustering

In this section we study distributed graph clustering. We assume that the vertex set of the input
graph G = (V, E) can be partitioned into k clusters, where vertices in each cluster S are highly
connected to each other, and there are fewer edges between S and V \ S. To formalize this notion,
we define the k-way expansion constant of graph G by
ρ(k) ,

min

max φG (Ai ).

partition A1 , . . . , Ak 1≤i≤k

Notice that a graph G has k clusters if the value of ρ(k) is small. It was shown in [14] that ρ(k)
closely relates to λk (LG ) by the following higher-order Cheeger inequality:
p
λk (LG )
≤ ρ(k) ≤ O(k 2 ) λk (LG ).
2
Hence, a large gap between λk+1 (LG ) and ρ(k) implies (i) the existence of a k-way partition {Si }ki=1
such that every Si has small conductance φG (Si ) ≤ ρ(k), and (ii) any (k + 1)-way partition of G

5

contains a subset with high conductance ρ(k + 1) ≥ λk+1 (LG )/2. Therefore, a large gap between
λk+1 (LG ) and ρ(k) ensures that G has exactly k clusters. In the following, we assume that
Υ , λk+1 (LG )/ρ(k) = Ω(k 3 )
to ensure that the input graph G has exactly k clusters. The same assumption has been used in
the literature for studying graph clustering in the centralized setting [20].
Both algorithms presented in the section are based on the following spectral clustering algorithm:
(i) compute the k eigenvectors f1 , . . . , fk of LG associated with λ1 (LG ), . . . , λk (LG ); (ii) embed every
vertex v to a point in Rk through the embedding
1
F (v) = √ · (f1 (v), . . . , fk (v));
dv
(iii) run k-means on the embedded points {F (v)}v∈V , and group the vertices of G into k clusters
according to the output of k-means.

3.1

The message passing model

We assume the edges of the input graph G = (V, E) are arbitrarily allocated among s sites
P1 , · · · , Ps , and we use Ei to denote the edge set maintained by site Pi . Our proposed algorithm consists of two steps: (i) every Pi computes a linear-sized (1 + ε)-spectral sparsifier Hi of
Gi , (V, Ei ), for a small constant ε ≤ 1/10, and sends the edge set of Hi , denoted by Ei0 , to the coordinator;
 S(ii) the coordinator runs a spectral clustering algorithm on the union of received graphs
H , V, ki=1 Ei0 . The theorem below summarizes the performance of this algorithm, and shows
the approximation guarantee of this algorithm is as good as the provable guarantee of spectral
clustering known in the centralized setting, which is shown in the lemma below.
Lemma 3.1 ([20]). Let G be a graph satisfying the condition Υ = Ω(k 3 ), and k ∈ N. Then,
a spectral clustering algorithm outputs sets A1 , . . . , Ak such that µ(Ai 4Si ) = O k 3 · Υ−1 · µ(Si )
holds for any 1 ≤ i ≤ k, where Si is the optimal cluster corresponding to Ai .
Theorem 3.2. Let G = (V, E) be an n-vertex graph with Υ = Ω(k 3 ), and suppose the edges
of G are arbitrarily allocated among s sites. Assume S1 , · · · , Sk is an optimal partition that
achieves ρ(k). Then,
 the algorithm above computes a partition A1 , . . . , Ak satisfying µ(Ai 4Si ) =
e
O k 3 · Υ−1 · µ(Si ) for any 1 ≤ i ≤ k. The total communication cost of this algorithm is O(ns)
bits.
P
Proof. By the definition of the Laplacian matrix, we have that LG = si=1 LGi . Since every Hi
is a (1 + ε)-spectral sparsifier of graph Gi , we have that (1 − ε)LHi  LGi  (1 + ε)LHi . This
implies that (1 − ε)LH  LG  (1 + ε)LH , by the definition of Hi and graph Laplacians. Now we
show that our assumption on Υ is preserved in H. By Lemma 2.1, we have for any 1 ≤ i ≤ k that
φH (Si ) ∈ 21 , 2 φG (Si ), which implies that Si has low conductance in H, and ρH (k) ∈ 12 , 2 ρG (k).
To show that λk (LH ) is a constant approximation of λk (LG ), notice that
(1 − c) · x| LG x ≤ x| LH x ≤ (1 + c) · x| LG x
holds for any x ∈ Rn . Hence it holds for any x ∈ Rn that
−1/2

(1 − ε) · x| DG

−1/2

LG D G

−1/2

x ≤ x| DG

−1/2

LH DG
6

−1/2

x ≤ (1 + ε) · x| DG

−1/2

LG DG

x.

−1/2

−1/2

−1
−1
−1
Since DG LG DG
= LG and 12 DG
 DH
 2DG
, we have that λi (LH ) = Θ (λi (LG )), and
the assumption on Υ in H is preserved from G up to a constant factor. By Lemma 3.1, the output
of a spectral clustering algorithm on H satisfies the claimed properties. The total communication
e
cost of O(ns)
bits follows from the fact that every Hi has O(n) edges.

Next we show that the communication cost of our proposed algorithm is optimal up to a
logarithmic factor. Our analysis is based on a reduction from graph clustering to the Multiparty
Set-Disjointness problem (DISJs,n ): for any s sites P1 , . . . , Ps , where each Pi has a set Si ⊆ [n],
let Xi = (Xi1 , . . . , Xin ) be the characteristic vector of Si , and let X = (X1 , . . . , Xs ) be the input
matrix with Xi being the i-th row. Let X j = (X1j , . . . , Xsj ) be the j-th column of the input
V matrix
X. We define a function ALLONEs on an s-bit vector Y = (Y1 , . . . , Ys ) as ALLONEs (Y ) = i∈[s] Yi ,
W
and DISJs,n (X) = j∈[n] ALLONEs (X j ). Then the DISJs,n problem asks the value of DISJs,n (X).
We introduce two hard input distributions for ALLONEs and DISJs,n respectively.
• Hard input distribution ν on Y ∈ {0, 1}s for ALLONEs : with probability 1/2, we choose each
Yi (i ∈ [s]) to be 0 or 1 with equal probability; with probability 1/4 we choose Y to be an
all-1 vector; and with the remaining probability 1/4 we choose Y to be a random vector with
n − 1 coordinates being 1’s and a random coordinate being 0.
• Hard input distribution µn on X ∈ {0, 1}s×n for DISJs,n : For each j ∈ [n], we choose X j ∼ ν.
Theorem 3.3 ([5]). It holds that IC0.49,ν (ALLONEs ) = Ω(s), and IC0.49,ν (DISJs,n ) = Ω(sn).
Lemma 3.4. In the message passing model, any randomized algorithm that computes DISJs,n correctly with probability 0.9 needs Ω(sn) bits of communication.
Proof. The lemma follows from Theorem 3.3 and Yao’s minimax lemma.
Theorem 3.5. Let G be an undirected graph with n vertices, and suppose the edges of G are
distributed among s sites. Then, any algorithm that correctly outputs a constant fraction of a
cluster in G requires Ω(ns) bits of communication. This holds even if each cluster has constant
expansion.
Proof. Our proof is based on the reduction from graph clustering to the Multiparty Set-Disjointness
problem (DISJs,n ). For any item j and site Pi , we set Xij = 0 if item j appears in site Pi , and
Xij = 1 otherwise. Then DISJs,n (X) = 1 if there is some item not appearing in any site. Now we
construct a graph G based on the hard instance X of DISJn,s as follows: initially, graph G consists
of n isolated vertices `1 , . . . , `n , and r isolated vertices r1 , . . . , rs . Then, we add an edge between `j
and ri if item j appears in site Pi . With this construction, it is easy to see that DISJs,n (X) = 0 if
every vertex `j is connected to some ri , and DISJs,n (X) = 1 if there are some isolated vertices `j .
We will show that, when DISJs,n (X) = 0, our constructed graph G is a bipartite expander,
i.e., G has only 1 cluster. To prove this, notice that, from the hard input distribution µ on
Y ∈ {0, 1}s described above, with probability 1/2 we choose each Yi (i ∈ [s]) to be 0 or 1 with equal
probability. This implies that, for any `i and rj , there is an edge between `i and rj independently
with probability at least 1/4. By standard results on constructing expanders, this implies G is a
bipartite expander with constant expansion, and in particular is connected.
On the other side, when DISJs,n (X) = 1, every isolated vertex `j itself forms a cluster with
conductance 0 and constant expansion, and the giant component of G forms a cluster with conductance 0 and constant expansion (since, as argued in the previous paragraph, it is a bipartite
expander). Let k be the number of connected components in graph G. Then, ρ(k) = 0, and our
7

assumption on Υ = λk+1 (LG )/ρ(k) = Ω(k 3 ) holds trivially. Hence any clustering algorithm that
is able to find a constant fraction of each cluster in graph G satisfying Υ = Ω(k 3 ) can be used to
solve DISJs,n . The lower bound on the communication complexity of graph clustering follows from
the lower bound for DISJs,n .
As a remark, it is easy to see that this lower bound also holds for constructing spectral sparsifiers:
for any n × n PSD matrix A whose entries are arbitrarily distributed among s sites, any distributed
algorithm that constructs a (1+Θ(1))-spectral sparsifier of A requires Ω(ns) bits of communication.
This follows since such a spectral sparsifier can be used to solve the spectral clustering problem.
Spectral sparsification has played an important role in designing fast algorithms from different areas,
e.g., machine learning, and numerical linear algebra. Hence our lower bound result for constructing
spectral sparsifiers may have applications to studying other distributed learning algorithms.

3.2

The blackboard model

e + s) bits of communication cost in the
Next we present a graph clustering algorithm with O(n
blackboard model. Our result is based on the observation that a spectral sparsifier preserves the
structure of clusters, which was used for proving Theorem 3.2. So it suffices to design a distributed
algorithm for constructing a spectral sparsifier in the blackboard model.
Our distributed algorithm is based on constructing a chain of coarse sparsifiers [18], which
is described as follows: for any input PSD matrix K with λmax (K) ≤ λu and all the non-zero
eigenvalues of K at least λ` , we define d = dlog2 (λu /λ` )e and construct a chain of d + 1 matrices
[K(0), K(1), . . . , K(d)],

(2)

where γ(i) = λu /2i and K(i) = K +γ(i)I. Notice that in the chain above every K(i−1) is obtained
by adding weights to the diagonal entries of K(i), and K(i − 1) approximates K(i) as long as the
weights added to the diagonal entries are small. We will construct this chain recursively, so that
K(0) has heavy diagonal entries and can be approximated by a diagonal matrix. Moreover, since
K is the Laplacian matrix of a graph G, it is easy to see that d = O(log n) as long as the edge
weights of G are polynomially upper-bounded in n.
Lemma 3.6 ([18]). The chain (2) satisfies the following relations: (1) K r K(d) r 2K; (2)
K(`)  K(` − 1)  2K(`) for all ` ∈ {1, . . . , d}; (3) K(0)  2γ(0)I  2K(0).
Based on Lemma 3.6, we will construct a chain of matrices
h
i
e
e
e
K(0),
K(1),
. . . , K(d)

(3)

e
e + 1)
in the blackboard model, such that every K(`)
is a spectral sparsifier of K(`), and every K(`
e
can be constructed from K(`).
The basic idea behind our construction is to use the relations among
different K(`) shown in Lemma 3.6 and the fact that, for any K = B | B, sampling rows of B with
respect to their leverage scores can be used to obtain a matrix approximating K.
Theorem 3.7. Let G be an undirected graph on n vertices, where the edges of G are allocated among
s sites, and the edge weights are polynomially upper bounded in n. Then, a spectral sparsifier of G
e + s) bits of communication in the blackboard model. That is, the chain
can be constructed with O(n
e + s) bits of communication in the blackboard model.
(3) can be constructed with O(n

8

Proof. Let K = B | B be the Laplacian matrix of the underlying graph G, where B ∈ Rm×n is the
e + 1) can be constructed based on
edge-vertex incidence matrix of G. We will prove that every K(i
e
e
e
K(i) with O(n + s) bits of communication. This implies that K(d),
a (1 + ε)-spectral sparsifier of
e
K, can be constructed with O(n+s)
bits of communication, as the length of the chain d = O(log n).
First of all, notice that λu ≤ 2n, and the value of n can be obtained with communication
e + s) (different sites sequentially write the new IDs of the vertices on the blackboard).
cost O(n
In the following we assume that λu is the upper bound of λmax that we actually obtained in the
blackboard.
Base case of ` = 0: By definition, K(0) = K + λu · I, and 21 · K(0)  γ(0) · I  K(0),
due to Statement 3 of Lemma
3.6. Let ⊕ denote appending the rows of one matrix to another.
p
|
We define Bγ(0) = B ⊕ γ(0) · I, and write K(0) = K + γ(0) · I = Bγ(0)
Bγ(0) . By defining
τi = b|i (K(0))| bi for each row of Bγ(0) , we have τi ≤ b|i (γ(0) · I) bi ≤ 2 · τi . Let τei = b|i (γ(0) · I)+ bi
be the leverage score of bi approximated using γ(0) · I, and let τe be p
the vector of approximate
leverage scores, with the leverage scores of the n rows corresponding to γ(0) · I rounded up to 1.
e
Then, with high probability sampling O(ε−2 n log n) rows of B will give a matrix K(0)
such that
e
(1 − ε)K(0)  K(0)
 (1 + ε)K(0). Notice that, as every row of B corresponds to an edge of G,
the approximate leverage scores τei for different edges can be computed locally by different sites
maintaining the edges, and the sites only need to send the information of the sampled edges to the
e + s) bits.
blackboard, hence the communication cost is O(n
e
Induction step: We assume that (1 − ε)K(`) r K(`)
r (1 + ε)K(`), and the blackboard
e
e
maintains the matrix K(`). This implies that (1 − ε)/(1 + ε) · K(`) r 1/(1 + ε) · K(`)
r K(`).
Combining this with Statement 2 of Lemma 3.6, we have that
1−ε
1
e
K(` + 1) r
K(`)
 K(` + 1).
2(1 + ε)
2(1 + ε)
e + 1) such that
We apply the same sampling procedure as in the base case, and obtain a matrix K(`
e
e
(1−ε)K(`+1) r K(`+1)
r (1+ε)K(`+1). Notice that, since K(`)
is written on the blackboard,
the probabilities used for sampling individual edges can be computed locally by different sites, and
in each round only the sampled edges will be sent to the blackboard in order for the blackboard to
e + 1). Hence, the total communication cost in each iteration is O(n
e + s) bits. Combining
obtain K(`
this with the fact that the chain length d = O(log n) proves the theorem.
Combining Theorem 3.7 and the fact that a spectral sparsifier preserves the structure of clusters,
e + s)
we obtain a distributed algorithm in the blackboard model with total communication cost O(n
bits, and the performance of our algorithm is the same as in the statement of Theorem 3.2. Notice
that Ω(n + s) bits of communication are needed for graph clustering in the blackboard model,
since the output of a clustering algorithm contains Ω(n) bits of information and each site needs to
communicate at least one bit. Hence the communication cost of our proposed algorithm is optimal
up to a poly-logarithmic factor.

4

Distributed geometric clustering

We now consider geometric clustering, including k-median, k-means and k-center. Let P be a set
of points of size n in a metric space with distance function d(·, ·), and let k ≤ n be an integer.
In the k-center problem we want to find a set C (|C| = k) such that maxp∈P d(p, C) is minimized, where d(p, C) P
= minc∈C d(p, c). In
Pk-median and k-means we replace the objective function
maxp∈P d(p, C) with p∈P d(p, C) and p∈P (d(p, C))2 , respectively.
9

4.1

The message passing model

As mentioned, for constant dimensional Euclidean space and a constant c > 1, there are algorithms
e
that c-approximate k-median and k-means using O(sk)
bits of communication [3]. For k-center,
e
the folklore parallel guessing algorithms (see, e.g., [9]) achieve a 2.01-approximation using O(sk)
bits of communication.
The following theorem states that the above upper bounds are tight up to logarithmic factors.
The proof uses tools from multiparty communication complexity. We in fact can prove a stronger
statement that any algorithm that can differentiate whether we have k points or k + 1 points in
total in the message passing model needs Ω(sk) bits of communication.
Theorem 4.1. For any c > 1, computing c-approximation for k-median, k-means or k-center
correctly with probability 0.99 in the message passing model needs Ω(sk) bits of communication.
Proof. We can in fact prove a more general result: we can show that the Ω(sk) lower bound holds
for any eligible function which evaluates to 0 if there are at most k points, and evaluates to a value
greater than 0 if there are at least k + 1 points. Note that k-median, k-means and k-center are all
eligible functions. We prove this by a simple reduction from DISJs,` where ` = (k + 1)/2 (w.l.o.g.,
assuming k is odd).
The reduction is as follows. Given an s-player set-disjointness instance of size ` (i.e., DISJs,` ),
let Xi = (Xi1 , . . . , Xi` ) be the i-th row of the input matrix X. Let p1 , . . . , p` and q 1 , . . . , q ` be 2`
distinct point locations on a line under Euclidean distance. Each site i does the following: for each
coordinate j, if Xij = 0 then it put a point uji at location q j ; otherwise if Xij = 1 it put a point
at location pj . It is easy to see that DISJs,` = 1 if and only if the number of distinct points in
S
uj is 2(` − 1) + 1 = k; and DISJs,` = 1 if and only if the number of distinct points in
Si∈[s],j∈[`] ji
i∈[s],j∈[`] ui is 2(` − 1) + 2 = k + 1. The lower bound follows from the definition of eligible function
and Theorem 3.3.
A number of works on clustering consider bicriteria solutions (e.g., [6, 13]). An algorithm is
a (c1 , c2 )-approximation (c1 , c2 > 1) if the optimal solution costs W when using k centers, then
the output of the algorithm costs at most c1 W when using at most c2 k centers. We can show
that for k-median and k-means, the Ω(sk) lower bound holds even for algorithms with bicriteria
approximations.
Theorem 4.2. For any c ∈ [1, 1.01], computing (7.1 − 6c, c)-bicriteria-approximation for k-median
or k-means correctly with probability 0.99 in the message passing model needs Ω(sk) bits of communication.
Before proving Theorem 4.2, we first show the following technical lemma.
Lemma 4.3. In the message-passing model, Ω(s`) bits of communication is needed for computing
at least a 0.8 fraction of j ∈ [`] ALLONEs (X j ) correctly with probability 0.99 under the input
distribution X ∼ µ` .
Proof. By a Markov inequality, there must exist Ω(s) coordinates j such that the algorithm computes ALLONEs (X j ) (X j ∼ ν) with error probability at most 0.24. Call each of these coordinates

10

j good. Let Π be the protocol transcript. We have
X
I(X j ; Π | X −j )
I(X; Π) =
j∈[`]

≥

X

I(X j ; Π)

(X j and X −j are independent)

j∈[`]

≥

X

I(X j ; Π)

good j

≥ Ω(s) · IC0.24,ν (ALLONEs )
≥ Ω(s`).

(Theorem 3.3)

Now we are ready to prove the theorem.
Proof of Theorem 4.2. We consider 8` point locations on a line (under Euclidean distance) with
x-coordinates being 1, 2, . . . , 8`. We put a point with infinite weight at every even point location.
We name the 4` odd point locations from left to right as
p1 , q 1 , p2 , q 2 , . . . , p` , q ` , z 1 , z 2 , . . . , z 2` .
For each site i ∈ [s] and each column j ∈ [`], if Xij = 0 then we put a point with weight 1 at
location q j ; otherwise if Xij = 1 then we put a point with weight 1 at location pj . We also put a
point with weight 1/2 at each of the “dummy” locations z 1 , . . . , z 2` . Let the weight of a location
be the sum of the weights of points falling into that location.
Given such an input X, for both k-median and k-means, the optimal solution (OPT) which
is allowed to use k = 6` centers will include all locations pj and q j whose weights are at least 1
(note that there are at most 2` such locations), the 4` even point locations, and as many as dummy
locations that it can still include. The cost of the optimal solution will be precisely the cost of
linking the points in the rest of the dummy locations to their nearest centers (at the even locations),
which can be written as
OPT = 1/2 · (k/3 − (k/3 − F0 )) = 1/2 · F0 ≤ `,
where F0 is the number of locations in {p1 , q 1 , . . . , p` , q ` } that have weights at least 1.
Now suppose our solution (SOL) outputs ck centers for a constant c ∈ [1, 1.01]. Each time we
include a location q j as a center when there is no 0-coordinate in the input column X j , we have a
loss of 1/2 since we miss out on including a dummy location (i.e., we can take one more dummy
location instead of taking q j as a center). Similarly, each time we do not include a location q j as
a center when there is a 0-coordinate in X j , we have a loss of 1/2 since a point at q j has weight
at least 1 but a point at a dummy location has weight at 1/2. Therefore, even if we are allowed to
output ck medians, we will still need to figure out whether there is any point at location q j for at
least an α = 0.9 fraction of the coordinates j ∈ [`]. If not, then
SOL − OPT ≥ 1/2 · (1 − α)` − 1 · (c − 1)k
(1 − α) − 12(c − 1)
=
·`
2
≥ (6.1 − 6c)OPT,

11

(4)

where the first term in the RHS of (4) counts the loss of incorrectly computing the (at least) (1−α)`
coordinates j ∈ [`], and the second term counts the maximum gain of the extra (c − 1)k centers
SOL can use (compared with OPT).
By Lemma 4.3, we have that for any c ∈ [1, 1.01], computing (7.1−6c, c)-bicriteria-approximation
for k-median or k-means in the message passing model correctly with probability 0.9 under distribution X ∼ µ needs Ω(sk) bits of communication. The theorem follows by Yao’s minimax
principle.

4.2

The blackboard model

e + k) bits
We can show that there is an algorithm that achieves an O(1)-approximation using O(s
of communication for k-median and k-means. For k-center, it is straightforward to implement the
e + k) bits of communication.
parallel guessing algorithm in the blackboard model using O(s
Our algorithm for k-median/means is an easy adaptation of the successive sampling algorithm
proposed by Mettu and Plaxton [17] in the (centralized) RAM model. We first summarize their
algorithm and then describe how to port it to the blackboard model.
Let X1 , . . . Xs be the point sets at sites P1 , . . . , Pk respectively. The successive sampling algorithm proceeds in rounds. At each round j it does the following:
1. s sites jointly sample O(k) point centers, denoted by Yj ;
2. s sites grow balls from each
S of the point centers in Yj synchronously until a time step when
a 0.9 fraction of points in i∈[s] Xi are covered;
3. each site Pi updates Xj by removing those points that are covered by any of the balls centered
at points in Yj ;
4. s sites remove all the points covered by balls centered at points in Yj , and proceed to the
next round j + 1.
It is easy to see that the computation will finish in r = O(log n) rounds since at each round we
remove a constant fraction of points.SAt the end we compute an O(1)-approximation of k-median
or k-means on the O(k log n) points j∈[r] Yj . In [17] it has been shown that this algorithm gives
an O(1)-approximation to k-median or k-means with high probability.
We now describe how to implement this centralized algorithm in the blackboard model. We
first consider each round. Step 1 can be done by the distributed sampling algorithm in [8] using
e + s) bits of communication; note that at the end of this step the sampled points in Yj are
O(k
written onSthe blackboard. Step 2 can be done by a binary search for S
the minimum ball radius tj
such that p∈Yj Ball(p, tj ) covers at least a 0.9 fraction of points in i∈[s] Xi , where Ball(p, tj )
e
denotes the ball centered at p with radius tj ; this binary search can be done using O(1)
bits of
communication. Step 3 and 4 can be done locally without any communication.
After r rounds, the
S
final clustering step can be done by any of the s sites since all points in j∈[r] Yj have already been
e + s).
written on the blackboard. Therefore the total communication cost can be bounded by O(k
Finally, we would like to mention that Ω(k + s) is an obvious lower bound, and thus our upper
bound is tight up to logarithmic factors. To see this, notice that k is the size of the output, and
the coordinator has to communication with each of the s sites for at least 1 bit.

12

5

Experiments

In this section we present experimental results for graph clustering in the message passing and
blackboard models. We will compare the following three algorithms. (1) Baseline: each site sends
all the data to the coordinator directly; (2) MsgPassing: our algorithm in the message passing
model (Section 3.1); (3) Blackboard: our algorithm in the blackboard model (Section 3.2).
Besides giving the visualized results of these algorithms on various datasets, we also measure
the qualities of the results via the normalized cut, defined as
1 X w(Ai , V \Ai )
ncut(A1 , . . . , Ak ) =
,
2
µ(Ai )
i∈[k]

which is a standard objective function to be minimized for spectral clustering algorithms.
We implemented the algorithms using multiple languages, including Matlab, Python and C++.
Our experiments were conducted on an IBM NeXtScale nx360 M4 server, which is equipped with
2 Intel Xeon E5-2652 v2 8-core processors, 32GB RAM and 250GB local storage.

5.1

Datasets.

We test the algorithms in the following real and synthetic datasets, which is visualized in Figure 1.

(a) Twomoons

(b) Gauss

(c) Sculpture

Figure 1: Visualization of the datasets for our experiments.

• Twomoons: this dataset contains n = 14, 000 coordinates in R2 . We consider each point to be
a vertex. For any two vertices u, v, we add an edge with weight w(u, v) = exp{−ku − vk22 /σ 2 }
with σ = 0.1 when one vertex is among the 7000-nearest points of the other. This construction
results in a graph with about 110, 000, 000 edges.
• Gauss: this dataset contains n = 10, 000 points in R2 . There are 4 clusters in this dataset,
each generated using a Gaussian distribution. We construct a complete graph as the similarity
graph. For any two vertices u, v, we define the weight w(u, v) = exp{−ku − vk22 /σ 2 } with
σ = 1. The resulting graph has about 100, 000, 000 edges.
• Sculpture: a photo of The Greek Slave 1 . We use an 80 × 150 version of this photo where
each pixel is viewed as a vertex. To construct a similarity graph, we map each pixel to a
point in R5 , i.e., (x, y, r, g, b), where the latter three coordinates are the RGB values. For any
two vertices u, v, we put an edge between u, v with weight w(u, v) = exp{−ku − vk22 /σ 2 } with
σ = 0.5 if one of u, v is among the 5000-nearest points of the other. This results in a graph
with about 70, 000, 000 edges.
In the distributed model edges are randomly partitioned across s sites.
1

Available in e.g., http://artgallery.yale.edu/collections/objects/14794

13

5.2

Results on clustering quality

(a) Baseline

(b) MsgPassing

(c) Blackboard

Twomoons, k = 2;

(d) Baseline

(e) MsgPassing

(f) Blackboard

Gauss, k = 4

(g) Baseline

(h) MsgPassing

(i) Blackboard

Sculpture, k = 3.
Figure 2: Visualization of the results on Twomoons, Gauss and Sculpture. In the message passing model each site samples 5n
edges; in the blackboard model all sites jointly sample 10n edges (in Twomoons and Gauss) or 20n edges (in Sculpture) and
the chain has length 18. s = 15.

We visualize the clustered results for the Twomoons, Gauss and Sculpture in Figure 2. It can
be seen that Baseline, MsgPassing and Blackboard give results of very similar qualities. For
simplicity, here we only present the visualization for s = 15. Similar results were observed when
we varied the values of s.
We also compare the normalized cut (ncut) values of the clustering results of different algorithms. The results are presented in Figure 3. In all datasets, the ncut values of different algorithms
are very close. The ncut value of MsgPassing slightly decreases when we increase the value of s,
while the ncut value of Blackboard is independent of s.

14

(a) Twomoons

(b) Gauss

(c) Sculpture

Figure 3: Comparisons on normalized cuts. In the message passing model, each site samples 5n edges; in each round of the
algorithm in the blackboard model, all sites jointly sample 10n edges (in Twomoons and Gauss) or 20n edges (in Sculpture)
edges and the chain has length 18.

(a) Twomoons

(d) Twomoons

(b) Gauss

(e) Gauss

(c) Sculpture

(f) Sculpture

Figure 4: Comparisons on communication costs. In the message passing model, each site samples 5n edges; in each round of
the algorithm in the blackboard model, all sites jointly sample 10n (in Twomoons and Gauss) or 20n (in Sculpture) edges and
the chain has length 18.

5.3

Results on communication costs

We compare the communication costs of different algorithms in Figure 4. We observe that while
achieving similar clustering qualities as Baseline, both MsgPassing and Blackboard are significantly more communication-efficient (by one or two orders of magnitudes in our experiments). We
also notice that the value of s does not affect the communication cost of Blackboard, while the
communication cost of MsgPassing grows almost linearly with s; when s is large, MsgPassing uses
significantly more communication than Blackboard. These confirm our theory.

5.4

Parameters in MsgPassing and Blackboard

Figure 5 shows in MsgPassinghow the value of ncut is affected by the number of sites and the
number of edges sampled in each site. Here, each site samples cn edges. When c = 3 and s = 1,
the ncut value diverges in all datasets. This is because with such a small c, the algorithm does not
generate a valid sparsifier. In general, increasing c or s will slightly decrease the ncut value. But
15

once they are above some thresholds, the ncut values of MsgPassing and Baseline become very
close.
Figure 6 shows in Blackboardhow the ncut value is affected by the number of iterations and
the number of edges sampled. When the number of iterations is set to be 5, ncut values diverge
in all datasets. This is because we cannot expect to generate a valid sparsifier by using such few
iterations. It can be seen from 6(b) that for a fixed c, performing more iterations will help to reduce
ncut values. From the same figure, one can also conclude that for fixed iterations, increasing c also
helps to reduce the ncut values.

(a) Twomoons

(b) Gauss dataset

(c) Sculpture

Figure 5: The pictures above show the ncut values with respect to the values of c and s for the MsgPassing algorithm. Here
each site samples cn edges.

(a) Twomoons

(b) Gauss

(c) Sculpture

Figure 6: The pictures above show how the ncut values are affected by the number of iterations and the value of c for the
Blackboard algorithm. Here all sites jointly sample cn edges.

References
[1] Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin
Zhang. On sketching quadratic forms. In ITCS, pages 311–319, 2016.
[2] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In
SODA, pages 1027–1035, 2007.
[3] Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median
clustering on general communication topologies. In NIPS, pages 1995–2003, 2013.

16

[4] Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, and David P. Woodruff. Improved distributed principal component analysis. CoRR, abs/1408.5823, 2014.
[5] Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan.
A tight bound for set disjointness in the message-passing model. In FOCS, pages 668–677,
2013.
[6] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility
location problems with outliers. In SODA, pages 642–651, 2001.
[7] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.
Dimensionality reduction for k-means clustering and low rank approximation. In STOC, pages
163–172, 2015.
[8] Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. Continuous sampling from
distributed streams. J. ACM, 59(2):10, 2012.
[9] Graham Cormode, S Muthukrishnan, and Wei Zhuang. Conquering the divide: Continuous
clustering of distributed data streams. In ICDE, pages 1036–1045, 2007.
[10] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data:
Constant-size coresets for k -means, PCA and projective clustering. In SODA, pages 1434–
1453, 2013.
[11] Sudipto Guha, Yi Li, and Qin Zhang. Distributed partial clustering. Manuscript, 2017.
[12] Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication complexity of approximate matching in distributed graphs. In STACS, pages 460–473, 2015.
[13] Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local
search heuristic for facility location problems. In SODA, pages 1–10, 1998.
[14] James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way spectral partitioning and
higher-order cheeger inequalities. In STOC, pages 1117–1130, 2012.
[15] Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear
time. In FOCS, pages 250–269, 2015.
[16] Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in O(log log n)
communication rounds. In SPAA, pages 94–100, 2003.
[17] Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering.
Machine Learning, 56(1-3):35–60, 2004.
[18] Gary L. Miller and Richard Peng. Iterative approaches to row sampling. CoRR, abs/1211.2713,
2012.
[19] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an
algorithm. Advances in neural information processing systems, 2:849–856, 2002.
[20] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! In COLT, pages 1423–1455, 2015.

17

[21] Jeff M. Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty
communication complexity, made easy. SIAM J. Comput., 45(1):174–196, 2016.
[22] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395–416,
2007.
[23] David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In
STOC, pages 941–960, 2012.

18

