On spectral properties for graph matching and graph isomorphism problems

Published

Journal Article

© The authors 2015. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved. Problems related to graph matching and isomorphisms are very important both from a theoretical and practical perspective, with applications ranging from image and video analysis to biological and biomedical problems. The graph matching problem is challenging from a computational point of view, and therefore different relaxations are commonly used. Although common relaxations techniques tend to work well for matching perfectly isomorphic graphs, it is not yet fully understood under which conditions the relaxed problem is guaranteed to obtain the correct answer. In this paper, we prove that the graph matching problem and its most common convex relaxation, where the matching domain of permutation matrices is substituted with its convex hull of doubly-stochastic matrices, are equivalent for a certain class of graphs, such equivalence being based on spectral properties of the corresponding adjacency matrices. We also derive results about the automorphism group of a graph, and provide fundamental spectral properties of the adjacency matrix.

Full Text

Duke Authors

Cited Authors

  • Fiori, M; Sapiro, G

Published Date

  • January 1, 2015

Published In

Volume / Issue

  • 4 / 1

Start / End Page

  • 63 - 76

Electronic International Standard Serial Number (EISSN)

  • 2049-8772

Digital Object Identifier (DOI)

  • 10.1093/imaiai/iav002

Citation Source

  • Scopus