Graph Matching Toolbox in MATLAB

This software is made publicly for research use only. It may be modified and redistributed under the terms of the GNU General Public License.

Please cite the paper and source code if you are using it in your work.

This software implements spectral graph matching with affine constraint (SMAC), optionally with kronecker bistochastic normalization, introduced in the paper below. The software can be used to handle arbitrary graph matching / subgraph matching problems:

1) highly scalable compared to other approaches (hundreds of nodes in each graph, depending on sparsity)
2) accurate (performed similarly to SDP relaxation in our experiments)
3) exploits sparsity pattern in each graph
4) handles graphs of different sizes (subgraph matching)
5) handles partial matchings (not just full matching)

In addition, the code implements kronecker bistochastic normalization, which modifies the graph matching cost function and dramatically improves the matching accuracy for a variety of graph matching algorithms.

1) start matlab
2) cd to directory where you unzipped the files (containing a README)
3) type init (to add paths) (ignore warnings about assert if any)
4) type compileDir (ignore warnings about assert if any)  to compile mex files
    make sure it says at the end: "Compilation of files succeded without error", otherwise try to compile problem files by hand

start any of the 3 demos:
demo_graph_matching_SMAC;
demo_normalizeMatchingW;
demo_computeEigenvectorsAffineConstraint;

Description