Correlation Clustering in Constant Many Parallel Rounds

Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski

Overview

This paper introduces the first algorithm for correlation clustering that runs in a constant number of parallel rounds within the Massively Parallel Computation (MPC) framework. By shifting from sequential "Pivot" strategies to a structural approach based on neighborhood agreement, the authors achieve a constant-factor approximation that is orders of magnitude faster than previous state-of-the-art parallel methods.

The Bottleneck in Correlation Clustering

Correlation clustering is a fundamental unsupervised learning task: given a graph where edges are labeled as "similar" (+) or "dissimilar" (-), the goal is to partition the nodes to minimize "disagreements" (positive edges between clusters or negative edges within a cluster).

While the problem is NP-hard, simple sequential algorithms like Pivot provide a good 3-approximation. However, as datasets grow to billions of edges, sequential approaches fail. Existing parallel versions of Pivot are still relatively slow, requiring $O(\log^2 n)$ or $O(\log n)$ rounds. In the world of massive data frameworks like MapReduce or Spark, every round involves heavy communication overhead. The holy grail is a "constant round" algorithm—one that finishes in a fixed number of steps regardless of how large the graph grows—while using sublinear memory per machine.

A Structural Approach: OURALGO

The authors depart from the standard strategy of simply parallelizing the Pivot algorithm. Instead, they propose a structural trimming approach called OURALGO:

  1. Agreement Testing: They define a notion of "weak agreement." Two nodes are in agreement if their neighborhoods significantly overlap. In the MPC setting, they approximate this overlap efficiently using random sampling.
  2. Graph Sparsification: They discard edges between nodes that aren't in agreement. They then categorize vertices as "heavy" or "light" based on how many neighbors they lost. Edges between two "light" vertices are also discarded.
  3. Connected Components: The key theoretical breakthrough is proving that the resulting "sparsified" graph consists of connected components with a constant diameter (specifically, at most 4).
  4. Clustering: Because the diameter is so small, the connected components (which form the final clusters) can be identified in just 4 parallel rounds using a simple label-propagation technique.

This approach also extends to the semi-streaming model, where the algorithm processes the graph in a constant number of passes over the data.

Key Insights

  • Structural over Procedural: Most parallel graph algorithms try to mimic sequential ones. This paper succeeds by instead identifying a graph structure (neighborhood agreement) that naturally yields clusters with low diameter.
  • The Power of 4: The "aha moment" is the proof that after trimming edges based on agreement, any remaining cluster has a diameter of at most 4. This collapses the round complexity from logarithmic to constant.
  • Theory vs. Practice Gap: While the theoretical approximation factor is quite high, the algorithm actually produces better quality clusterings in practice than the 3-approximation baselines. This suggests the structural approach captures the "ground truth" of clusters more effectively than randomized pivoting.

Empirical Results

The authors evaluated their algorithm on five large-scale real-world datasets from the Laboratory for Web Algorithmics, ranging from a 1-million node co-authorship network (dblp-2011) to massive web crawls and social graphs with over a billion edges (uk-2005, it-2004, twitter-2010, webbase-2001).

Unprecedented Speed

OURALGO is consistently 10x to over 1000x faster than previous parallel competitors like ClusterWild and ParallelPivot.

Relative execution time of OURALGO compared to baselines. Higher multipliers indicate the baseline took significantly longer to run.

Competitive Clustering Quality

In terms of the objective function (minimizing disagreements), OURALGO outperformed or matched baselines across most datasets, proving that its aggressive edge sparsification does not degrade practical performance.

Correlation Clustering Objective Value across datasets. OURALGO achieves competitive or superior (lower) disagreement scores compared to ClusterWild and PPivot.

Scalability and Efficiency

The algorithm demonstrated near-linear speedup as the number of machines increased from 1 to 8, before hitting communication bottlenecks at 16 machines. Furthermore, it operates successfully in the "sublinear memory regime," meaning each machine only needs $O(n^\delta)$ memory (where $\delta < 1$), making it suitable for truly massive graphs.

Limitations and Future Work

  • Theoretical Approximation: The constant-factor approximation is theoretically large. Refining the analysis to bring this number closer to the empirical performance is a clear next step.
  • Unweighted Focus: The current work focuses on the unweighted case (edges are +1 or -1). Extending this constant-round approach to weighted correlation clustering remains an open challenge.
  • Heuristic Links: The authors note similarities between their approach and the SCAN heuristic for community detection; formalizing this connection could lead to better hybrid algorithms.

Summary updated

Abstract

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 ...
BibTeX
@inproceedings{cohenaddad2021correlation,
  author = {Vincent Cohen-Addad and Silvio Lattanzi and Slobodan Mitrovic and Ashkan Norouzi-Fard and Nikos Parotsidis and Jakub Tarnawski},
  title = {{Correlation Clustering in Constant Many Parallel Rounds}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
}
Figure