FENNEL: streaming graph partitioning for massive scale graphs

Charalampos E. Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, Milan VojnovicWSDM 2014 · DOI

TL;DR

This paper introduces FENNEL, a novel streaming graph partitioning framework that achieves state-of-the-art performance for massive graphs. FENNEL offers a flexible objective function that balances edge cuts and partition sizes, outperforming existing streaming methods and rivaling offline methods like METIS in quality while being significantly faster.

What Problem Does This Paper Address?

Processing massive graphs, which are increasingly prevalent in areas like social networks, web graphs, and recommendation systems, presents significant computational challenges. Graph partitioning is a crucial technique to enable efficient distributed processing of these large graphs. The goal is to divide a graph into smaller, balanced partitions while minimizing the number of edges that connect different partitions (edge cuts). This minimizes communication overhead in distributed systems. Traditional methods often struggle with the scale of modern graphs, requiring significant computation time or producing suboptimal partitions. Streaming graph partitioning, where vertices and edges arrive sequentially and decisions must be made on-the-fly, is particularly challenging due to the need for speed and efficiency without multiple passes over the data. Existing streaming methods often make trade-offs between partition quality and speed, or are limited in their objective functions.

Methods

FENNEL introduces a unifying framework for graph partitioning that allows for a flexible objective function. This objective function combines two components: an "inter-partition cost" (related to edge cuts) and an "intra-partition cost" (related to the sizes of individual partitions). This formulation allows for a principled design of algorithms.

The core of FENNEL is a one-pass streaming algorithm that greedily assigns each arriving vertex to the partition that maximizes the increase in the objective function. This greedy approach is efficient and can be implemented with low computational overhead.

The paper also explores theoretical aspects:

  • Relaxation of Hard Constraints: FENNEL relaxes the strict cardinality constraints often found in traditional balanced graph partitioning, leading to a more adaptable framework.
  • Modularity Connection: A special case of FENNEL's objective function is shown to be equivalent to maximizing graph modularity, a popular metric for community detection. The paper provides the first rigorous approximation algorithm for this specific objective.
  • SDP Rounding: For the optimal k-graph partitioning problem, the paper proposes an SDP (semidefinite programming) rounding algorithm that achieves an approximation guarantee.

Datasets

The paper evaluates FENNEL on a variety of datasets, including:

  • Real-world graphs: amazon0312, LiveJournal1, Twitter (with over 1.4 billion edges), and others listed in Table 2.
  • Synthetic graphs:
    • Hidden Partition (HP) model: Used to generate graphs with controlled parameters for number of vertices, clusters, and edge probabilities.
  • Chung-Lu (CL) model: Used to generate random power-law graphs with a specified degree distribution slope.

The paper does not introduce new benchmark datasets but uses a comprehensive collection of existing ones to demonstrate FENNEL's performance.

Key Insights and Ideas

  • Flexibility is Key: The core innovation is the flexible objective function that allows tuning the trade-off between edge cuts and partition balance. This adaptability is crucial for different system characteristics and application needs.
  • Streaming Can Rival Offline: FENNEL demonstrates that a one-pass streaming algorithm can achieve partition quality comparable to, and sometimes better than, sophisticated offline algorithms like METIS, which require multiple passes over the data.
  • Bridging Theory and Practice: FENNEL's framework connects theoretical concepts like modularity and approximation algorithms with practical, scalable streaming algorithms.
  • Interpolation is Powerful: The paper shows that interpolating between existing heuristics (like "non-neighbors" and "linear weighted degrees") leads to improved performance, forming the basis of FENNEL's greedy strategy.

Key Results

  • Performance on Twitter Graph: For the Twitter graph (1.4 billion edges), FENNEL partitioned it in about 40 minutes, achieving a cut of 6.8% edges. METIS took over 8 hours for a 11.98% cut.
  • Comparison to Competitors: FENNEL consistently outperforms other streaming algorithms (like LDG, EDG, etc.) in terms of both edge cut and load balance.
  • METIS Comparison: FENNEL's partition quality is comparable to METIS, often achieving better edge cuts with significantly less runtime.
  • Runtime: FENNEL's streaming nature results in much faster partitioning times, especially for large graphs.
  • Approximation Guarantee: For the modularity objective, FENNEL provides the first rigorous O(log(k)/k) approximation algorithm.
  • System Evaluation: When used for PageRank computation on Apache Giraph, FENNEL-partitioned graphs resulted in shorter runtimes and reduced communication costs compared to hash partitioning and LDG.

Limitations and Future Work

  • Distributed Implementation: While the paper presents a streaming algorithm, a full distributed implementation is left as future work. The authors suggest that efficient distributed implementation of marginal value index computation is feasible.
  • Cost Function Exploration: The paper suggests exploring other cost functions beyond the ones discussed.
  • Offline Community Detection: The authors plan to develop an offline community detection algorithm based on their framework.
  • Approximation Factor: The paper conjectures that the derived approximation factor for the SDP-based approach is near-optimal.

Summary updated

BibTeX
@inproceedings{tsourakakis2014fennel,
  author = {Charalampos E. Tsourakakis and Christos Gkantsidis and Bozidar Radunovic and Milan Vojnovic},
  title = {{FENNEL: streaming graph partitioning for massive scale graphs}},
  booktitle = {WSDM},
  year = {2014},
  doi = {10.1145/2556195.2556213},
}
Figure