Skip to main content

Graph Matching: Relax at Your Own Risk.

Publication ,  Journal Article
Lyzinski, V; Fishkind, DE; Fiori, M; Vogelstein, JT; Priebe, CE; Sapiro, G
Published in: IEEE transactions on pattern analysis and machine intelligence
January 2016

Graph matching-aligning a pair of graphs to minimize their edge disagreements-has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics. Its attention can be partially attributed to its computational difficulty. Although many heuristics have previously been proposed in the literature to approximately solve graph matching, very few have any theoretical support for their performance. A common technique is to relax the discrete problem to a continuous problem, therefore enabling practitioners to bring gradient-descent-type algorithms to bear. We prove that an indefinite relaxation (when solved exactly) almost always discovers the optimal permutation, while a common convex relaxation almost always fails to discover the optimal permutation. These theoretical results suggest that initializing the indefinite algorithm with the convex optimum might yield improved practical performance. Indeed, experimental results illuminate and corroborate these theoretical findings, demonstrating that excellent results are achieved in both benchmark and real data problems by amalgamating the two approaches.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE transactions on pattern analysis and machine intelligence

DOI

EISSN

1939-3539

ISSN

0162-8828

Publication Date

January 2016

Volume

38

Issue

1

Start / End Page

60 / 73

Related Subject Headings

  • Pattern Recognition, Automated
  • Models, Statistical
  • Models, Neurological
  • Mathematical Concepts
  • Humans
  • Diffusion Tensor Imaging
  • Computer Simulation
  • Computer Graphics
  • Caenorhabditis elegans
  • Brain Mapping
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Lyzinski, V., Fishkind, D. E., Fiori, M., Vogelstein, J. T., Priebe, C. E., & Sapiro, G. (2016). Graph Matching: Relax at Your Own Risk. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(1), 60–73. https://doi.org/10.1109/tpami.2015.2424894
Lyzinski, Vince, Donniell E. Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, and Guillermo Sapiro. “Graph Matching: Relax at Your Own Risk.IEEE Transactions on Pattern Analysis and Machine Intelligence 38, no. 1 (January 2016): 60–73. https://doi.org/10.1109/tpami.2015.2424894.
Lyzinski V, Fishkind DE, Fiori M, Vogelstein JT, Priebe CE, Sapiro G. Graph Matching: Relax at Your Own Risk. IEEE transactions on pattern analysis and machine intelligence. 2016 Jan;38(1):60–73.
Lyzinski, Vince, et al. “Graph Matching: Relax at Your Own Risk.IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 1, Jan. 2016, pp. 60–73. Epmc, doi:10.1109/tpami.2015.2424894.
Lyzinski V, Fishkind DE, Fiori M, Vogelstein JT, Priebe CE, Sapiro G. Graph Matching: Relax at Your Own Risk. IEEE transactions on pattern analysis and machine intelligence. 2016 Jan;38(1):60–73.

Published In

IEEE transactions on pattern analysis and machine intelligence

DOI

EISSN

1939-3539

ISSN

0162-8828

Publication Date

January 2016

Volume

38

Issue

1

Start / End Page

60 / 73

Related Subject Headings

  • Pattern Recognition, Automated
  • Models, Statistical
  • Models, Neurological
  • Mathematical Concepts
  • Humans
  • Diffusion Tensor Imaging
  • Computer Simulation
  • Computer Graphics
  • Caenorhabditis elegans
  • Brain Mapping