The developing of this package aims two principal objectives. First, of course, make it easy for people working with large graphs to match them. And second, to propose a benchmark which may be used for evaluation and comparison of new graph matching algorithms. The package is written in C++ and it was designed to maximally simplify the implementation of new graph matching algorithms, the only thing you have to do is to write your algorithm, all other code modifications are restricted to three lines. More information about algorithms, parameters and the GraphM package may be found in graphm_doc.pdf.

Right now GraphM is distributed as a source package under GNU General Public License. Binary platform-specific packages are provided on request. If you use GraphM in your research, please, cite [M.Zaslavskiy and F.Bach and J-P.Vert. A path following algorithm for the graph matching problem, TPAMI 2009] in any resulting publication.

Download package (graphm-0.52.tar.gz) Download documentation
Previous versions:
graphm-0.51
graphm-0.5
graphm-0.4
graphm-0.3
graphm-0.2
graphm-0.1

News:
 08/01/2011 Fixing some bugs related to the use of deprecated strstring library
09/03/2010 Fixing some bugs related to the use of the STL library on the 64bit machines
14/12/2009 The project is migrated to Code: Blocks
20/02/2009 Some modifications in the Rank algoirthm, new default value for C.
08/09/2008 Some bugs are fixed (the local cost matrix in the Umeyama algorithm), new version of the package description document.
25/06/2008 New C-adaptation algorithm

Installation:

  1. unpack: tar zxvf graphm-0.1.tar.gz
  2. cd graphm
  3. ./graphm_install

Implemented algorithms

  1. Umeyama algorithm. S.Umeyama: An eigendecomposition approach to weighted graph matching problems.
  2. Linear programming approach. H.A. Almohamad and S.O. Duffuaa: Linear Programming Approach for the Weighted Graph Matching Problem
  3. Rank algorithm. R.Singh and J.Xu and B.Berger: Pairwise Global Alignment of Protein Interaction Networks By Matching Neighborhood Topology
  4. QCV (Quadratic convex relaxation) algorithm. M.Zaslavskiy and F.Bach and J-P.Vert A path following algorithm for the graph matching problem (preprint arxiv,full version (TPAMI))
  5. PATH (A path following) algorithm. M.Zaslavskiy and F.Bach and J-P.Vert A path following algorithm for the graph matching problem (preprint arxiv,full version (TPAMI))
  6. If you have your own graph matching algorithm which produces competitive results in terms of precision/time, we'll be glad to include it into the package and make it public, surely, with your copyrights and links on the original articles .

Recommendations

The choice of a graph matching algorithm depends on the particular problem. There are two principal criterion: time and approximation quality (precision). Usually algorithms producing better precision take more time and vice versa. If you have very small graphs (up to 20-30) you do not even need approximate methods, usually the problem may be solved exactly. Other extreme case, if you need to match a lot of large graph pairs, you have very tough time constraints and you do not really carry about good matching, then it is better to use the Umeyama or the RANK algorithms. If you want to match large graphs (several thousands vertices) and you need a good matching quality, then your choice is the PATH algorithm. The PATH algorithm has the same complexity order as the Umeyama or the RANK algorithms and it produces the best approximation quality (see A path following algorithm for the graph matching problem). Graphs with 1000 vertices may be matched in one and half hour on a modern computer (~3 Gz, 1Gb).

Links

  1. IAPR Technical commitee #15
  2. Special session on Graph-based representations in pattern recognition, ICISP 2008

Feedback

Please, contact us if
  1. you designed a new algorithm and you want to make it public (especially if it does the exact optimization in polynomial time)
  2. you applied the GraphM to a real problem and you want to share your experience (references on articles, technical reports or just descriptions are highly welcome)
  3. you have some remarks, comments, bugs reports or you are looking for collaboration partners.
Our contacts: Mikhail.Zaslavskiy at [ensmp.fr/gmail.com], Francis.Bach at [ensmp.fr/mines.org], Jean-Philippe.Vert at [ensmp.fr/mines.org]

ToDo

  1. Incorporation of some exact graph matching algorithms link
  2. Balanced graph matching
  3. Detailed table with comparison of implemented graph matching algorithms
  4. ...