A Lagrangian relaxation network for graph matching

Presents a Lagrangian relaxation network for graph matching. The problem is find a permutation matrix M that minimizes a distance between the two graphs. The authors adopt a deterministic annealing approach which is similar to a Lagrangian decomposition approach in that the row and column constraints of the permutation matrix are satisfied separately and Lagrange multipliers are used to equate the two "solutions". A fixpoint preserving transformation is applied to the graph matching constraint. A symmetry-breaking term is added in order to obtain a permutation matrix and is reversed via another fixpoint preserving transformation. The resulting network performs minimization with respect to the Lagrange parameters and maximization with respect to the match matrix variables. Simulation results are shown on 100 node random graphs and for a wide range of connectivities.>