A Distributed Vertex Rearrangement Algorithm for Compressing and Mining Big Graphs

Namyong Park, Chiwan Park, U KangJournal of KIISE 2016 · DOI

TL;DR

This paper introduces a distributed version of the SlashBurn algorithm, enabling efficient compression and mining of massive graphs. By parallelizing the vertex rearrangement process, their approach achieves significant speedups and handles graphs far larger than previously possible with single-machine solutions.

What Problem Does This Paper Address?

Compressing and analyzing extremely large graphs (billions of edges) is a major challenge. Traditional methods like the single-machine SlashBurn algorithm, while effective for smaller graphs, struggle with memory limitations and slow processing times on massive datasets. This bottleneck hinders efficient graph compression and the performance of graph mining algorithms like PageRank, which rely on these compressed representations. The authors aim to overcome these limitations by developing a distributed algorithm that can scale to handle these "big graphs."

Methods

The core of the paper is the Distributed SlashBurn algorithm. It adapts the original SlashBurn's strategy of rearranging vertices to concentrate non-zero entries in the adjacency matrix, thereby improving compression and mining efficiency. The key innovations are:

  • Distributed Connected Components: They leverage a state-of-the-art distributed connected components algorithm (Alternating) to efficiently find and process these components in parallel.
  • Load-Balanced Output: The algorithm is designed to distribute the output of the vertex rearrangement process across multiple machines, preventing bottlenecks and ensuring scalability.
  • Handling Hubs and Spokes: The distributed approach carefully manages the identification and rearrangement of "hub" vertices (high-degree nodes) and "spoke" vertices (nodes in smaller connected components) across the cluster.
  • Apache Spark Implementation: The distributed algorithm is implemented on Apache Spark, a popular distributed computing framework known for its efficiency in handling iterative computations.

Datasets

The authors evaluated their algorithm on a variety of real-world and synthetic graph datasets:

  • Real-world Graphs:
    • Amazon (product co-purchase network)
    • Web-BS (web page link graph)
    • LiveJournal-Links (social network connections)
    • LiveJournal-Membership (user-group membership)
    • Orkut (user-group membership)
    • Friendster (social network connections)
  • Synthetic Graphs: R-MAT graphs, generated using a recursive model to mimic the properties of real-world graphs.

Key Insights and Ideas

  • Power-Law is Key, but Scalability is Crucial: While the power-law property of real-world graphs is fundamental to SlashBurn's effectiveness, its single-machine nature severely limits its applicability to large-scale data.
  • Distributed Connected Components are a Bottleneck: The connected components finding step is computationally intensive. Using a distributed approach here is critical for overall performance.
  • Load Balancing is Essential for Output: Simply distributing the computation isn't enough; the output phase also needs careful load balancing to avoid becoming a bottleneck.
  • Iterative Nature Demands Efficient Distribution: SlashBurn's iterative nature makes it a prime candidate for distributed processing, where each iteration can be parallelized.

Key Results

  • Significant Speedup: The distributed SlashBurn algorithm ran over 45 times faster than the single-machine version on large real-world graphs.
  • Massive Scalability: The distributed approach could process graphs 16 times larger than what the single-machine version could handle.
  • Linear Scalability with Machines: For the LiveJournal-Membership graph, increasing the number of machines from 1 to 16 showed near-linear performance improvements.
  • Handling Untouchable Graphs: The distributed algorithm successfully processed graphs (like Orkut and Friendster) that were too large to be handled by the single-machine version within a 12-hour time limit.

Limitations and Future Work

  • Connected Components Algorithm Performance: The authors acknowledge that the performance of the distributed connected components algorithm (Alternating) is a significant factor in the overall runtime. They plan to investigate further improvements to this component in future work.
  • Further Optimization: While the distributed algorithm shows excellent scalability, there's always room for further optimization, particularly in fine-tuning the distributed processing framework and communication overhead.

Summary updated

Abstract

수십억 개 간선들로 구성된 대용량 그래프를 어떻게 효과적으로 압축할 수 있을까? 정점 재배치를 통해 인접 행렬의 0이 아닌 값들을 집중시키면 그래프를 효율적으로 압축할 수 있을 뿐 아니라 페이지랭크 등 여러 그래프 마이닝 알고리즘의 수행 속도를 개선할 수 있다. 최신 정점 재배치 기법인 SlashBurn 은 실세계 네트워크의 멱법칙 특성을 활용하는 실세계 그래프에 효과적인 방법이다. 하지만 단일 머신 기반으로 설계되어 대용량 그래프에 대해 처리 속도가 현저히 느려지거나 적용이 불가능한 한계가 있다. 본 논문에서는 이러한 한계를 극복하기 위한 분산 SlashBurn을 제안한다. 분산 SlashBurn은 대규모의 정점재배치 프로세스를 분산 처리하여 대용량 그래프를 기존 방법보다 훨씬 빠르고 확장성 있게 처리한다. 대용량 실세계 그래프들에 대한 실험 결과, 분산 SlashBurn은 단일 머신 SlashBurn보다 45배 이상 빠르게 동작하였고, 16배 이상 큰 그래프를 처리할 수 있었다.
BibTeX
@article{park2016distributed,
  author = {Namyong Park and Chiwan Park and U Kang},
  title = {{A Distributed Vertex Rearrangement Algorithm for Compressing and Mining Big Graphs}},
  journal = {Journal of KIISE},
  year = {2016},
  doi = {10.5626/jok.2016.43.10.1131},
}
Figure