Parallel Correlation Clustering on Big Graphs

Abstract

Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: an algorithm that serially clusters neighborhoods of vertices, and obtains a 3-approximation ratio. Unfortunately, KwikCluster in practice requires a large number of clustering rounds, a potential bottleneck for large graphs. We present C4 and ClusterWild!, two algorithms for parallel correlation clustering that run in a polylogarithmic number of rounds and achieve nearly linear speedups, provably. C4 uses concurrency control to enforce serializability of a parallel clustering process, and guarantees a 3-approximation ratio. ClusterWild! is a coordination free algorithm that abandons consistency for the benefit of better scaling; this leads to a provably small loss in the 3-approximation ratio. We provide extensive experimental results for both algorithms, where we outperform the state of the art, both in terms of clustering accuracy and running time. We show that our algorithms can cluster billion-edge graphs in under 5 seconds on 32 cores, while achieving a 15x speedup.

References in corpus (4)

• Greedy Sequential Maximal Independent Set and Matching are Parallel on Average
• Correlation Clustering with Noisy Partial Information
• The phase transition in site percolation on pseudo-random graphs
• Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds

Cited by in corpus (11)

• CYCLADES: Conflict-free Asynchronous Machine Learning
• Parallel Index-Based Structural Graph Clustering and Its Approximation
• Clustering Via Crowdsourcing
• Info-Clustering: A Mathematical Theory for Data Clustering
• Always Lurking: Understanding and Mitigating Bias in Online Human Trafficking Detection
• Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
• Parallel Pairwise Correlation Computation On Intel Xeon Phi Clusters
• Motif Clustering and Overlapping Clustering for Social Network Analysis
• Differentially Private Correlation Clustering
• Correlation Clustering in Data Streams
• Parallelism in Randomized Incremental Algorithms