A Practical Parallel Algorithm for Expander Decompositions
TL;DR
A work-efficient parallel algorithm for expander decompositions whose main cut-finding procedure requires no flow computations, and which shows that a weak expander decomposition for any target expansion Φ can be extracted from a hierarchical congestion approximator in linear time.
Abstract
Expander decompositions have recently been used in many breakthrough results that prove near-optimal theoretical bounds for hard graph problems but still remain impractical for real-world applications. The primary bottleneck is a heavy reliance on iterative max-flow computations, which introduce a prohibitive overhead. We address this bottleneck by introducing a work-efficient parallel algorithm for expander decompositions whose main cut-finding procedure requires no flow computations. Instead, it leverages random walks at the cost of a slightly higher number of inter-cluster edges. While this algorithm still occasionally requires flows in the "trimming" step, we present another algorithm for the variant of weak expander decompositions that operates entirely without flow computations. To demonstrate the validity of this new direction, we complement the analysis with a practical CUDA implementation. We evaluate its performance on a suite of real-world graphs and observe a significant speedup over an optimized sequential baseline. Furthermore, in a study of the downstream task of computing normalized cuts, we achieve competitive quality against a state-of-the-art strong-expander based implementation, while offering far superior scalability. Finally, we show that a weak expander decomposition for any target expansion Φ can be extracted from a hierarchical congestion approximator in linear time. Together with prior results, we obtain a parallelizable new scheme for computing weak expander decompositions in almost-linear time. Crucially, the running time is independent of Φ, which mitigates another weakness of recent algorithms, an expensive running time dependence on 1/Φ.