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:
- 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.
- 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.
- 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).
- 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.
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.
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