Fast $b$-Matching via Sufficient Selection Belief Propagation

Abstract

This article describes scalability enhancements to a previously established belief propagation algorithm that solves bipartite maximum weight $b$-matching. The previous algorithm required $O(|V|+|E|)$ space and $O(|V||E|)$ time, whereas we apply improvements to reduce the space to $O(|V|)$ and the time to $O(|V|^{2.5})$ in the expected case (though worst case time is still $O(|V||E|))$. The space improvement is most significant in cases where edge weights are determined by a function of node descriptors, such as a distance or kernel function. In practice, we demonstrate maximum weight $b$-matchings to be solvable on graphs with hundreds of millions of edges in only a few hours of compute time on a modern personal computer without parallelization, whereas neither the memory nor the time requirement of previously known algorithms would have allowed graphs of this scale.