X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs

Abstract

The maximum weight perfect matching (MWPM) problem in bipartite graphs has extensive applications in database, machine learning, financial markets, and other data-intensive domains, and serves as a general formulation of weighted matching problems. The Hungarian algorithm is widely adopted for solving bipartite MWPM, and substantial research efforts have focused on improving its sequential time complexity. As data volumes grow and real-time processing demands escalate, parallel solutions become increasingly essential. However, efficient parallelization remains highly nontrivial due to the algorithm's intricate execution patterns, inherently sequential data dependencies, frequent phase switching, and the single-path-per-iteration search constraint. These critical issues motivate us to develop X-Wim, a massively parallel framework. It is built on a new phase-decoupled approach that breaks the strong interleaving between algorithmic phases, eliminates frequent global updates, enables concurrent search for multiple disjoint paths, and incorporates an adaptive search strategy. These algorithmic design efforts lead to substantial performance gains, even in the single-threaded setting. Extensive experiments on real-world datasets indicate that X-Wim surpasses state-of-the-art baselines, achieving up to a 9.93x speedup with 1 core and up to a 56.3x speedup with 8 cores. It also exhibits strong scalability. In tests up to 96 cores, it achieves an average 1.70x speedup each time the number of threads doubles. To the best of our knowledge, X-Wim is the fastest solution for this class of graph algorithms.