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
Relative accuracy—defined to be —of all the four algorithms compared with FAQ.Note that FAQ is better than all the other algorithms on ≈ 94% of the benchmarks. The abscissa is the log number of vertices. The gray dot indicates the mean improvement of FAQ over the other algorithms.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0121002.g002: Relative accuracy—defined to be —of all the four algorithms compared with FAQ.Note that FAQ is better than all the other algorithms on ≈ 94% of the benchmarks. The abscissa is the log number of vertices. The gray dot indicates the mean improvement of FAQ over the other algorithms.

Mentions: Performance is measured by minimizing the assignment cost . We write for the value of the local minimum of f obtained by the algorithm X ∈ {FAQ, PATH, QCV, RANK, U, all}, where “all” is just the best performer of all the non FAQ algorithms. Fig 2 plots the logarithm (base 10, here and elsewhere) of the relative accuracy, i.e. , for X ∈ {PATH, QCV, RANK, U, all}. FAQ performs significantly better than the other algorithms, outperforming all of them on ≈ 94% of the problems, often by nearly an order of magnitude in terms of relative error.


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)

Relative accuracy—defined to be —of all the four algorithms compared with FAQ.Note that FAQ is better than all the other algorithms on ≈ 94% of the benchmarks. The abscissa is the log number of vertices. The gray dot indicates the mean improvement of FAQ over the other algorithms.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0121002.g002: Relative accuracy—defined to be —of all the four algorithms compared with FAQ.Note that FAQ is better than all the other algorithms on ≈ 94% of the benchmarks. The abscissa is the log number of vertices. The gray dot indicates the mean improvement of FAQ over the other algorithms.
Mentions: Performance is measured by minimizing the assignment cost . We write for the value of the local minimum of f obtained by the algorithm X ∈ {FAQ, PATH, QCV, RANK, U, all}, where “all” is just the best performer of all the non FAQ algorithms. Fig 2 plots the logarithm (base 10, here and elsewhere) of the relative accuracy, i.e. , for X ∈ {PATH, QCV, RANK, U, all}. FAQ performs significantly better than the other algorithms, outperforming all of them on ≈ 94% of the problems, often by nearly an order of magnitude in terms of relative error.

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