Fast approximate quadratic programming for graph matching

Joshua T Vogelstein; John M Conroy; Vince Lyzinski; Louis J Podrazik; Steven G Kratzer; Eric T Harley; Donniell E Fishkind; R Jacob Vogelstein; Carey E Priebe

doi:10.1371/journal.pone.0121002

Fast approximate quadratic programming for graph matching

PLoS One. 2015 Apr 17;10(4):e0121002. doi: 10.1371/journal.pone.0121002. eCollection 2015.

Authors

Joshua T Vogelstein¹, John M Conroy², Vince Lyzinski³, Louis J Podrazik², Steven G Kratzer², Eric T Harley⁴, Donniell E Fishkind⁴, R Jacob Vogelstein⁵, Carey E Priebe⁴

Affiliations

¹ Department of Biomedical Engineering, Johns Hopkins University, Baltimore, MD, USA.
² Institute for Defense Analyses, Center for Computing Sciences, Bowie, MD, USA.
³ Johns Hopkins University Human Language Technology Center of Excellence, Baltimore, MD, USA.
⁴ Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA.
⁵ Johns Hopkins University Applied Physics Laboratory, Laurel, MD, USA.

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.

Publication types

Research Support, Non-U.S. Gov't
Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

Algorithms*
Animals
Caenorhabditis elegans / physiology*
Connectome

Grants and funding

This work was partially supported by the Research Program in Applied Neuroscience (JV, RJV, CEP, http://www.jhuapl.edu/ourwork/red/an/), a National Security Science and Engineering Faculty Fellowship (CEP, http://www.acq.osd.mil/rd/basic_research/program_info/nsseff.html), Johns Hopkins University Human Language Technology Center of Excellence (DEF, JV, CEP, VL, http://hltcoe.jhu.edu/), and the XDATA program of the Defense Advanced Research Projects Agency (CEP, http://www.darpa.mil/Our_Work/I2O/Programs/XDATA.aspx) administered through Air Force Research Laboratory contract FA8750-12-2-0303. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.