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:
- 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.
- 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.
- 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, anduk-2002. - Massive:
Metaclust50(37.2B edges) and theHyperlinkgraph (124.9B edges). TheHyperlinkgraph 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