Code for Loopy Belief Propagation for Maximum Weight bd-Matching
Copyright 2008 Bert Huang (bert@cs.columbia.edu) and Tony Jebara

************************************************************************
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 in Artificial Intelligence and Statistics, 2007. 

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. 

Here is an example, assume we have a data matrix X with 20 two-dimensional
points and want to do b-matching with b=4. P contains the binary adjacency
matrix of the connectivity between the points. This is a unipartite
problem so the guarantees of the paper do not carry over but in practice
this works well also.

X=rand(20,2);
K=X*X';
D=diag(K)*ones(1,n)+ones(n,1)*diag(K)'-2*K;
nD=max(max(D))+0.01-D; nD=nD-diag(diag(nD));
b=4;
[P,B]=bdmatchwrapper(nD,ones(size(nD))-eye(size(nD)),b,b);
P = max(full(P),full(P)');



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.


Last modified on 
Fri Nov 14 20:29:15 EST 2008