PPubMed17 Apr 2015Cited 142×

Fast Approximate Quadratic Programming for Graph Matching 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, Mark R. Muldoon

Abstract

'Louis J. Podrazik' 'Steven G. Kratzer' 'Eric T. Harley' 'Donniell E. Fishkind' 'R. Jacob Vogelstein' 'Carey E. Priebe' 'Mark R. Muldoon'] 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.

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

The FAQ algorithm provides a fast, O(n³) approximate graph‑matching method that outperforms prior approaches on most QAPLIB benchmarks in both speed and accuracy.

What’s new

i.Introduces the Fast Approximate Quadratic assignment (FAQ) algorithm for graph matching
ii.Shows state‑of‑the‑art accuracy and speed on >80% of QAPLIB benchmarks
iii.Provides theoretical justification for using the indefinite relaxation of the QAP
iv.Extends the method to directed, weighted, and brain‑connectome graphs
v.Proposes a multiple‑restart variant to improve robustness

How they did it

The problem is relaxed to a doubly‑stochastic matrix (rQAP) and solved with the Frank‑Wolfe first‑order algorithm. After convergence the solution is projected onto the set of permutation matrices via a linear assignment (Hungarian) step. Optional random restarts are used to escape local minima.

What they found

FAQ outperforms prior algorithms on ≈94% of QAPLIB problems, often by an order of magnitude in relative error
Achieves both higher accuracy and lower runtime on 80% of benchmarks (99% more accurate)
Runs in O(n³) time with a very small leading constant ≈10⁻⁹
Finds the optimal objective value in every simulation and perfectly unshuffles the C. elegans connectome

Caveats

✕Performance degrades for very large graphs because O(n³) can still be too slow for some applications
✕Algorithm is sensitive to initialization; quality depends on starting point
✕Wall‑time variance due to the number of Hungarian sub‑problems required
✕Scalability to graphs with thousands‑plus vertices remains an open challenge

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Similar papers in all four archives

The same idea searched in arXiv, PubMed, bioRxiv and chemRxiv at once, so a method can lead you to where it is being applied.

AarXiv4 found

PPubMed4 found

BbioRxiv3 found

CchemRxiv2 found

Searching the other archives…