Title :
A Lagrangian relaxation network for graph matching
Author :
Rangarajan, Anand ; Mjolsness, Eric D.
Author_Institution :
Dept. of Diagnostic Radiol., Yale Univ., New Haven, CT, USA
fDate :
11/1/1996 12:00:00 AM
Abstract :
A Lagrangian relaxation network for graph matching is presented. The problem is formulated as follows: given graphs G and g, find a permutation matrix M that brings the two sets of vertices into correspondence. Permutation matrix constraints are formulated in the framework of deterministic annealing. Our approach is in the same spirit as a Lagrangian decomposition approach in that the row and column constraints are satisfied separately with a Lagrange multiplier used to equate the two “solutions”. Due to the unavoidable symmetries in graph isomorphism (resulting in multiple global minima), we add a symmetry-breaking self-amplification term in order to obtain a permutation matrix. With the application of a fixpoint preserving algebraic transformation to both the distance measure and self-amplification terms, we obtain a Lagrangian relaxation network. The network performs minimization with respect to the Lagrange parameters and maximization with respect to the permutation matrix variables. Simulation results are shown on 100 node random graphs and for a wide range of connectivities
Keywords :
graph theory; matrix algebra; minimisation; neural nets; simulated annealing; Lagrangian decomposition approach; Lagrangian relaxation network; deterministic annealing; distance measure; fixpoint preserving algebraic transformation; graph isomorphism; graph matching; maximization; minimization; permutation matrix; symmetry-breaking self-amplification term; Annealing; Computational modeling; Computer science; Computer vision; Lagrangian functions; Matrix decomposition; Neural engineering; Polynomials; Radiology;
Journal_Title :
Neural Networks, IEEE Transactions on