Binary Relaxation on Unlabeled Graph Matching: A Twin-VAMP Approach

We study a variant of the graph isomorphism problem called “unlabeled graph matching” (UGM) between two graphs where noisy and permuted versions of their adjacency matrices are observed. By relaxing the estimation of permutation matrices to binary ones, we recast UGM to a compressed sensing problem with two observation models. We then build upon the vector approximate message passing (VAMP) framework to devise a new algorithm, coined Twin-VAMP, to handle two observation matrices. Numerical results on permutation matrices of 3-digit size demonstrate the effectiveness of the proposed Twin-VAMP in solving the UGM problem.