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