title: Fast approximate quadratic programming for graph matching.
abstract: Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm. We empirically demonstrate that our algorithm is faster and achieves a lower objective value on over 80% of the QAPLIB benchmark library, compared with the previous state-of-the-art. Applying our algorithm to our motivating example, matching C. elegans connectomes (brain-graphs), we find that it efficiently achieves performance.
authors.affiliation: Department of Biomedical Engineering, Johns Hopkins University, Baltimore, MD, USA.
authors.forename: Joshua T
authors.initials: JT
authors.lastname: Vogelstein
authors.affiliation: Institute for Defense Analyses, Center for Computing Sciences, Bowie, MD, USA.
authors.forename: John M
authors.initials: JM
authors.lastname: Conroy
authors.affiliation: Johns Hopkins University Human Language Technology Center of Excellence, Baltimore, MD, USA.
authors.forename: Vince
authors.initials: V
authors.lastname: Lyzinski
authors.affiliation: Institute for Defense Analyses, Center for Computing Sciences, Bowie, MD, USA.
authors.forename: Louis J
authors.initials: LJ
authors.lastname: Podrazik
authors.affiliation: Institute for Defense Analyses, Center for Computing Sciences, Bowie, MD, USA.
authors.forename: Steven G
authors.initials: SG
authors.lastname: Kratzer
authors.affiliation: Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA.
authors.forename: Eric T
authors.initials: ET
authors.lastname: Harley
authors.affiliation: Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA.
authors.forename: Donniell E
authors.initials: DE
authors.lastname: Fishkind
authors.affiliation: Johns Hopkins University Applied Physics Laboratory, Laurel, MD, USA.
authors.forename: R Jacob
authors.initials: RJ
authors.lastname: Vogelstein
authors.affiliation: Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA.
authors.forename: Carey E
authors.initials: CE
authors.lastname: Priebe
mesh_terms: D000465:Algorithms; D000818:Animals; D017173:Caenorhabditis elegans / Q000502:physiology*; D063132:Connectome