Probabilistic graph matching by canonical decomposition

We present in this paper a solution to the graph isomorphism problem, by a unique decomposition of a graph into a set of atoms via its clique minimal separators. The resulting set of atoms is then used to collapse the original graph into a bipartite attributed relational graph, having a fewer number of vertices. Finally a probabilistic matching algorithm operates on the reduced graphs, simulating a belief propagation run, and decides whether the original graphs are isomorphic, in which case their corresponding atoms match. The complete approach yields a good suboptimal solution, while retaining a polynomial time complexity.