FastSV: A Distributed-Memory Connected Component Algorithm with Fast Convergence

Yongzhe Zhang, Ariful Azad, Zhenjiang Hu

Finding connected components (CC) in a graph—identifying groups of nodes where every node is reachable from every other node—is a foundational task in data science. Whether you are clustering proteins in bioinformatics or analyzing web structures, you need an algorithm that can handle billions of nodes and trillions of edges.

In their paper, "FastSV: A Distributed-Memory Connected Component Algorithm with Fast Convergence," researchers Yongzhe Zhang, Ariful Azad, and Zhenjiang Hu introduce a streamlined, high-performance approach that outperforms the previous state-of-the-art by an average of 2.2x.

TL;DR

FastSV is a simplified and optimized version of the classic Shiloach-Vishkin (SV) algorithm for finding connected components in massive undirected graphs. By employing novel "hooking" strategies and leveraging linear algebraic primitives (GraphBLAS), it scales to over 262,000 cores and can process a graph with 124 billion edges in just 30 seconds.

What Problem Does This Paper Address?

Parallelizing connected component algorithms is notoriously difficult for "high-diameter" graphs (where the path between two nodes can be very long). Traditional methods like Breadth-First Search (BFS) perform poorly here because their parallel depth is proportional to the graph's diameter.

The alternative is the Shiloach-Vishkin (SV) scheme, which treats the graph as a forest of trees and iteratively "hooks" trees together and "shortcuts" them to reduce their height. However, the most advanced existing implementation, LACC, is complex, involving four distinct stages per iteration. The authors noticed that while LACC is scalable, its complexity introduces significant computational overhead. They sought to create a simpler algorithm that converges faster without sacrificing the ability to scale to the world's largest supercomputers.

Methods

FastSV simplifies the SV framework down to two primary steps: hooking and shortcutting. To compensate for the removal of certain complex steps in LACC (like unconditional hooking), the authors introduced three key optimizations:

  1. Hooking to Grandparent: Instead of a tree root hooking onto a neighbor’s parent, it hooks onto the neighbor’s grandparent. This creates shorter trees from the start, accelerating the path to the final "star" configuration where all nodes point directly to a single representative root.
  2. Stochastic Hooking: In traditional SV, only roots can initiate a hook. FastSV allows any node in a tree to hook independently. While this might temporarily "break" a tree into fragments, those fragments eventually merge into the correct component, often much faster than waiting for root-level operations.
  3. Aggressive Hooking: This gives nodes an extra chance to hook into a neighbor's grandparent during the shortcutting phase, effectively performing extra work where it is computationally "cheap" to do so.

The authors implemented these steps using GraphBLAS, a standard for expressing graph algorithms as linear algebra (matrix-vector multiplications). This allowed them to use the CombBLAS library for distributed-memory execution and SuiteSparse for shared-memory systems.

Datasets

The researchers evaluated FastSV on 14 diverse real-world and synthetic datasets, ranging from structural problems to web crawls:

  • Small/Medium: archaea, eukarya, and uk-2002.
  • Massive: Metaclust50 (37.2B edges) and the Hyperlink graph (124.9B edges). The Hyperlink graph is currently one of the largest publicly available datasets for connectivity problems.

Key Insights and Ideas

  • Simplicity is Speed: By reducing the number of operations per iteration, FastSV's individual iterations are roughly 2x faster than LACC's. Even if FastSV requires a few more iterations to converge, the total runtime is significantly lower.
  • The Power of Sparsity: In later iterations of the algorithm, most nodes have already found their roots. FastSV dynamically switches from dense matrix-vector multiplication (SpMV) to sparse-matrix sparse-vector multiplication (SpMSpV), drastically reducing communication costs as the algorithm nears completion.
  • Early Termination: The authors proved a new lemma: if the "grandparent" vector ($f[f]$) remains unchanged after an iteration, the algorithm has converged. This allows FastSV to skip the final "cleanup" iteration required by other SV variants.

Key Results

  • Performance: FastSV achieved an average speedup of 2.21x (and up to 4.27x) over LACC across various graphs.
  • Extreme Scalability: On the Cray XC40 supercomputer (Cori), the algorithm scaled linearly up to 262,144 cores.
  • Efficiency: It processed the 124.9 billion edge Hyperlink graph in 30 seconds.
  • Convergence: The new hooking strategies reduced the number of iterations required by approximately 35% compared to a basic simplified SV algorithm.

Limitations and Future Work

The authors noted that LACC still holds an advantage on specific types of graphs—namely those with a massive number of very small, disconnected components (like the archaea dataset). This is because LACC can detect and "retire" converged components early, whereas FastSV's current design processes all vertices until the entire graph is resolved.

Future work includes porting FastSV to other high-performance frameworks, such as GraphBLAST for GPUs and pygraphblas for Python-based large-scale analytics.

Summary updated

Abstract

This paper presents a new distributed-memory algorithm called FastSV for finding connected components in an undirected graph. Our algorithm simplifies the classic Shiloach-Vishkin algorithm and employs several novel and efficient hooking strategies for faster convergence. We map different steps of FastSV to linear algebraic operations and implement them with the help of scalable graph libraries. FastSV uses sparse operations to avoid redundant work and optimized MPI communication to avoid bottlenecks. The resultant algorithm shows high-performance and scalability as it can find the connected components of a hyperlink graph with over 134B edges in 30 seconds using 262K cores on a Cray XC40 supercomputer. FastSV outperforms the state-of-the-art algorithm by an average speedup of 2.21x (max 4.27x) on a variety of real-world graphs.
BibTeX
@inproceedings{zhang2020fastsv,
  author = {Yongzhe Zhang and Ariful Azad and Zhenjiang Hu},
  title = {{FastSV: A Distributed-Memory Connected Component Algorithm with Fast Convergence}},
  booktitle = {PPSC},
  year = {2020},
  url = {https://openreview.net/forum?id=ejgSUsqSwB},
}

Loading related content...

Figure