Fast b-matching via Sufficient Selection Belief Propagation


Bert Huang, Tony Jebara ;
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:361-369, 2011.


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. [pdf]

Related Material