Code for Loopy Belief Propagation for Maximum Weight bd-Matching Copyright 2008 Bert Huang bert@cs.columbia.edu ************************************************************************ This code is a development version and is provided as is with no guarantees about the accuracy of its output. This software is currently released under the GNU General Public License http://www.gnu.org/copyleft/gpl.html If you use this code in research for publication, please cite the paper "Loopy Belief Propagation for Bipartite Maximum Weight b-Matching" by Bert Huang and Tony Jebara. Please provide feedback if you have any questions or suggestions. ************************************************************************ Included files: Makefile bdmatch.h bdmatch.c bp.c quickselect.c README bdmatchwrapper.m COMPILING The Makefile is configured for compilation using gcc. Type "make all". USAGE: bdmatch [-arg1 val] [-arg2 val] [..] Flags: -w [filename] Weight file -d [filename] Degree file -o [filename] Output file -i [integer] Maximum iterations (default 1000) -damp [float] Damping proportion (default 1) -h Help -s [0 1] Sparse input (default 1. 0 NOT IMPLEMENTED YET) -t [integer] Number of threads (default 4) -v [0 1 2] Verbose (default 1) Sparse format should have 'N nnz' as first line Copyright 2008 Bert Huang INPUT WEIGHT FILE FORMAT The bdmatch program currently expects the weight file to be in sparse ijw format. The first line of the weight file should list the number of nodes in the graph and the number of non-zero entries in the matrix. The following lines should list the endpoints and the weight of an edge. Example file: 10 90 1 2 .4 1 3 .6 ... INPUT DEGREE FILE FORMAT The degree format lists the lower and upper bounds for each node in order. Example file: 4 4 5 8 0 9 ... EXAMPLE USAGE Example input files are included in the Example subdirectory. Run bdmatch with the following command: ./bdmatch -w Example/weights.txt -d Example/deg.txt -o Example/out.txt -i 10000 -damp .8 -t 2 -v 1 The example problem provided is one that should not converge, but we can obtain the approximate solution by either early-stopping (by choosing maximum iterations with -i) and/or damping (with -damp). Also the output file contains the log-beliefs, which can be used to pull out an approximate solution using other logic than the default method, which is to greedily choose edges to maximize belief but satisfy the row constraints. When BP has not converged, this strategy often results in column constraints being unsatisfied. MATLAB INTERFACE A matlab utility function, bdmatchwrapper.m, is included that converts to the proper file format and runs the bdmatch tool. NOTES: - The algorithm is guaranteed for bipartite graphs when there is a unique solution. Otherwise, it is only an approximation algorithm. We find the approximations to be fairly accurate. - Non-sparse input format is currently not implemented, but the MATLAB interface takes a sparse or non-sparse matrix and converts it to the sparse format. - This is a generalization of the algorithm described in the paper "Loopy Belief Propagation for Bipartite Maximum Weight b-Matching", but by setting all the lower bounds and upper bounds to the same value, you get exactly the same algorithm. 1/19/2009 - fixed Makefile to link to math and pthread libraries. Last modified on Mon Jan 19 16:54:04 EST 2009