Scalable Graph Clustering with Pregel

Bryan Perozzi, Christopher McCubbin, Spencer Beecher, James T. HalbertCompleNet 2013 · DOI

TL;DR

This paper introduces "ParallelNibble," a novel distributed algorithm for finding local clusters in massive graphs. By combining Pregel for parallel PageRank approximation and MapReduce for sweeping, it efficiently identifies communities and scales to graphs with billions of nodes, outperforming traditional methods in certain aspects.

What Problem Does This Paper Address?

Extracting meaningful community structures (local clusters) from massive, distributed graphs is a significant challenge. Traditional graph clustering algorithms often struggle with the sheer scale of modern datasets, leading to prohibitively long computation times or requiring immense computational resources. While methods like Personalized PageRank (PPR) can identify local clusters, their parallelization for extremely large graphs has been an open problem. This paper aims to bridge this gap by developing a scalable, parallel approach to local graph clustering that can handle graphs with billions of nodes.

Methods

The core of the paper's contribution lies in the ParallelNibble algorithm, which is a four-step process extending prior work:

  1. Seed Selection: Random pairs of source vertices and cluster sizes are chosen. Vertices are sampled based on their degree from the stationary distribution, and cluster sizes are determined using a modified version of the Spielman's RandomNibble procedure.
  2. Parallel Approximate PageRank (PAPR): This is a key novel component. It computes approximate Personal PageRank (PPR) vectors in parallel using the Pregel distributed graph processing framework. PAPR is a direct parallelization of the approach by Andersen et al. [2], allowing for efficient computation of PPR vectors across a distributed graph.
  3. MapReduce Sweep (MRSweep): After PAPR computes the PPR vectors, a MapReduce job is used to sweep through these vectors. This step efficiently identifies potential local clusters by ordering vertices based on a sweep metric derived from PPR probabilities and vertex degrees.
  4. Overlap Reconciliation: To produce a final, non-overlapping clustering, overlapping local clusters are reconciled. Vertices are assigned to the cluster with the lowest conductance, a method inspired by Andersen et al.

The paper also details the PAPR algorithm, which uses a push operation at vertices to iteratively refine PageRank vectors and a halt condition based on an energy constant ($\epsilon$) to control approximation quality. The MRSweep algorithm leverages MapReduce's partitioning and sorting capabilities to efficiently process the output of PAPR.

Datasets

The paper evaluates its method on several publicly available graph datasets, including:

  • soc-livejournal
  • web-google
  • web-stanford
  • amazon0302
  • ca-AstroPh
  • ca-GrQc
  • ca-HepPh
  • email-Enron
  • loc-gowalla
  • oregon1-010526
  • soc-Epinions1
  • wiki-Vote

These datasets represent a variety of real-world graphs with varying sizes and characteristics. The paper does not introduce new benchmarks but uses these existing datasets to evaluate the quality and scalability of its proposed algorithm.

Key Insights and Ideas

  • Parallelizing Local Clustering: The paper demonstrates that local graph clustering techniques, traditionally difficult to scale, can be effectively parallelized using distributed graph processing frameworks like Pregel and MapReduce.
  • PAPR as a Scalable Foundation: The Parallel Approximate PageRank (PAPR) algorithm is a crucial innovation, enabling the efficient computation of PPR vectors on massive distributed graphs, which is a prerequisite for many local clustering methods.
  • MRSweep for Efficient Cluster Identification: The MapReduce Sweep (MRSweep) component efficiently processes the PPR outputs to identify candidate local clusters, leveraging MapReduce's strengths in parallel sorting and aggregation.
  • Conductance as a Quality Metric: The paper emphasizes the use of conductance as a primary metric for evaluating cluster quality, aligning with prior work that connects it to global spectral clustering.
  • Scalability with Worker Count: The experiments show that increasing the number of workers generally decreases running time, highlighting the algorithm's scalability, although synchronization and communication overhead become limiting factors at very high worker counts.

Key Results

  • Low Conductance Clusters: The PAPR algorithm is shown to be capable of finding low-conductance clusters, indicating tightly connected communities.
  • Scalability: The algorithm demonstrates significant speedups as the number of workers increases. For instance, the total run time for the soc-livejournal graph decreases substantially with more workers, though it plateaus around 10 workers due to communication overhead.
  • Comparison to Fast Unfolding: While the paper's method produces low-conductance clusters, the overall clustering quality (measured by modularity) is noted to be worse than the baseline modularity derived from the first phase of the Fast Unfolding algorithm. This suggests that while ParallelNibble excels at finding local, low-conductance communities, optimizing for global modularity might require different strategies.
  • Time Complexity: The complexity of PAPR is stated as $O(\epsilon \alpha \omega m)$, where $\epsilon$ is the energy constant, $\alpha$ is the teleportation constant, $\omega$ is the number of workers, and $m$ is the number of edges.

Limitations and Future Work

  • Modularity Optimization: The paper acknowledges that its postprocessing step for resolving overlapping clusters (assigning vertices to the cluster with lowest conductance) is not optimal for maximizing modularity.
  • Small Cluster Detection: The chosen method for selecting cluster sizes might be unable to detect small clusters, suggesting a need for recursive application of the procedure.
  • Communication Overhead: For graphs with power-law distributions, the random assignment of vertices to workers in Pregel can lead to significant communication overhead, limiting further parallelization gains.
  • Future Work: The authors plan to conduct more scalability analysis on even larger graphs ("Internet scale") and explore how these local clustering techniques can be applied to other aspects of network community analysis. They also suggest that their approach could potentially be enhanced by other techniques for approximating PageRank vectors, such as those using MapReduce.

Summary updated

BibTeX
@inproceedings{perozzi2013scalable,
  author = {Bryan Perozzi and Christopher McCubbin and Spencer Beecher and James T. Halbert},
  title = {{Scalable Graph Clustering with Pregel}},
  booktitle = {CompleNet},
  year = {2013},
  doi = {10.1007/978-3-642-36844-8\_13},
}
Figure