Correlation Clustering in Constant Many Parallel Rounds
  Correlation clustering is a central topic in unsupervised learning, with many
applications in ML and data mining. In correlation clustering, one receives as
input a signed graph and the goal is to partition it to minimize the number of
disagreements. In this work we propose a massively parallel computation (MPC)
algorithm for this problem that is considerably faster than prior work. In
particular, our algorithm uses machines with memory sublinear in the number of
nodes in the graph and returns a constant approximation while running only for
a constant number of rounds. To the best of our knowledge, our algorithm is the
first that can provably approximate a clustering problem on graphs using only a
constant number of MPC rounds in the sublinear memory regime. We complement our
analysis with an experimental analysis of our techniques.
