Presentation
When Label Propagation Outperforms BFS in Breadth-First Graph Traversal
DescriptionWe tackle the challenge of breadth-first traversal (BFT) on sparse graphs with a high number of connected components. We propose a novel distributed-memory parallel algorithm that uses the label propagation (LP) algorithm to perform BFT on all connected components of the graph simultaneously. In synthetic benchmarks with RMAT-like graphs, we show that our LP-based algorithm can be up to 77x faster compared to the parallel direction-optimized BFS in the Combinatorial BLAS library, while scaling up to 1.5k CPU cores.
Event Type
Research and ACM SRC Posters
TimeThursday, 20 November 20258:00am - 5:00pm CST
LocationSecond Floor Atrium
Archive
view