Limits...
Fast approximate quadratic programming for graph matching.

Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, Priebe CE - PLoS ONE (2015)

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: Department of Biomedical Engineering, Johns Hopkins University, Baltimore, 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.

Show MeSH
Absolute wall time for running each of the five algorithms on all 137 QAPLIB benchmarks.We fit a line on this log-log plot for each algorithm; the slope is displayed beside each line. The FAQ slope is much better than the PATH slope, and worse than the others. Note, however, the time for RANK and U appears to be superlinear on this log-log plot, suggesting that perhaps as the number of vertices increases, PATH might be faster.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4401723&req=5

pone.0121002.g003: Absolute wall time for running each of the five algorithms on all 137 QAPLIB benchmarks.We fit a line on this log-log plot for each algorithm; the slope is displayed beside each line. The FAQ slope is much better than the PATH slope, and worse than the others. Note, however, the time for RANK and U appears to be superlinear on this log-log plot, suggesting that perhaps as the number of vertices increases, PATH might be faster.

Mentions: The utility of an approximation algorithm depends not just on its accuracy, but also its efficiency. To empirically test these algorithms’ efficiency, we compare the wall time of each of the five algorithms on all 137 QAPS in QAPLIB in Fig 3. For each of the 5 algorithms, we fit an iteratively weighted least squares linear regression function (Matlab’s “robustfit”) to regress the logarithm of time (in seconds) onto the logarithm of the number of vertices being matched. The numbers beside the lines indicate the slopes of the regression functions.


Fast approximate quadratic programming for graph matching.

Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, Priebe CE - PLoS ONE (2015)

Absolute wall time for running each of the five algorithms on all 137 QAPLIB benchmarks.We fit a line on this log-log plot for each algorithm; the slope is displayed beside each line. The FAQ slope is much better than the PATH slope, and worse than the others. Note, however, the time for RANK and U appears to be superlinear on this log-log plot, suggesting that perhaps as the number of vertices increases, PATH might be faster.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4401723&req=5

pone.0121002.g003: Absolute wall time for running each of the five algorithms on all 137 QAPLIB benchmarks.We fit a line on this log-log plot for each algorithm; the slope is displayed beside each line. The FAQ slope is much better than the PATH slope, and worse than the others. Note, however, the time for RANK and U appears to be superlinear on this log-log plot, suggesting that perhaps as the number of vertices increases, PATH might be faster.
Mentions: The utility of an approximation algorithm depends not just on its accuracy, but also its efficiency. To empirically test these algorithms’ efficiency, we compare the wall time of each of the five algorithms on all 137 QAPS in QAPLIB in Fig 3. For each of the 5 algorithms, we fit an iteratively weighted least squares linear regression function (Matlab’s “robustfit”) to regress the logarithm of time (in seconds) onto the logarithm of the number of vertices being matched. The numbers beside the lines indicate the slopes of the regression functions.

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: Department of Biomedical Engineering, Johns Hopkins University, Baltimore, 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.

Show MeSH