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.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-huang11a, title = {Fast $b$-matching via Sufficient Selection Belief Propagation}, author = {Huang, Bert and Jebara, Tony}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {361--369}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/huang11a/huang11a.pdf}, url = {https://proceedings.mlr.press/v15/huang11a.html}, 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.} }
Endnote
%0 Conference Paper %T Fast $b$-matching via Sufficient Selection Belief Propagation %A Bert Huang %A Tony Jebara %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-huang11a %I PMLR %P 361--369 %U https://proceedings.mlr.press/v15/huang11a.html %V 15 %X 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.
RIS
TY - CPAPER TI - Fast $b$-matching via Sufficient Selection Belief Propagation AU - Bert Huang AU - Tony Jebara BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-huang11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 361 EP - 369 L1 - http://proceedings.mlr.press/v15/huang11a/huang11a.pdf UR - https://proceedings.mlr.press/v15/huang11a.html AB - 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. ER -
APA
Huang, B. & Jebara, T.. (2011). Fast $b$-matching via Sufficient Selection Belief Propagation. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:361-369 Available from https://proceedings.mlr.press/v15/huang11a.html.

Related Material