Code from 2011 paper "Fast b-Matching via Sufficient Selection Belief Propagation" by Bert Huang and Tony Jebara
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
Shared Library


This software solves maximum weight b-matchings using fast belief 
propagation. It is provided as-is, with no warranty, and can be freely 
used for scientific research. Please contact me at if 
you want to use it for commercial reasons. 

If you use this code in research for publication, please cite the papers:

Fast b-Matching via Sufficient Selection Belief Propagation
B. Huang and T. Jebara. Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS) 2011


Loopy Belief Propagation for Bipartite Maximum Weight b-Matching.
B. Huang and T. Jebara. Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS) 2007,

Compile the software by using the makefile in the "Release" directory, 
which will create a binary BMatchingSolver program. Or if you wish to use 
the static methods in the BMatchingLibrary as a dynamic library, use the
makefile in "Shared Library", which creates a dylib file. Alternatively, this 
repository is an Eclipse project, which can be imported into your workspace.

See the "html" directory for documentation. 

Please send questions, comments to 

See shell script examples/ for how to call the command line tool, and see the matlab script tester.m for how to call the matlab functions.

Usage: BMatchingSolver <options>
-w, --weights	weight matrix file
-d, --degree	degree file
-x, --data	node descriptor file
-o, --output_file	output file
-n, --total	total number of nodes
-D, --dimensions	dimensionality of node descriptors
-c, --cacheSize	number of cached weights per row
-b, --bipartite	number of nodes in first bipartition
-t, --weight_type	weight type (0 = matrix, 1 = negative Euclidean, 
                                    2 = inner product)
-i, --max_iter	maximum iterations of belief propagation to run
-B, --binary	use binary data files

The weight matrix file is a tab-delimited matrix ascii matrix of size nxn
Alternatively, you can give node descriptor (feature vectors) of size nxd.
The degree file is a file of ascii numbers, one per line, indicating the 
target degree for each node. Parameter n is the total number of nodes in
your input graph, and if the graph is bipartite, parameter b is the number
of nodes in the first bipartition.

A number of matlab toolbox functions are in the matlab directory:

bdmatch_augment.m - create an augmented weight matrix for bd-matching (degree-
                    constrained subgraph) using auxiliary nodes
BMatchingSolver.cpp - mex c++ file for direct matlab interface
BMatchingSolver.mexmaci64 - 64-bit mac binary for mex version
BMatchingSolverCmd.m - command line wrapper that calls the CLI BMatchingSolver
lprelax.m - much slower lp relaxation solver for bd-matchings
makeMex.m - script to compile the mex BMatchingSolver.cpp 
tester.m - tests the mex and the CLI versions against the lprelax on 
            various random problems of different sizes