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
Running time of FAQ as function of number of vertices.Data was sampled from an Erdös-Rényi model with p = log(n)/n. Each dot represents a single simulation, with 100 simulations per n. The solid line is the best fit cubic function. Note the leading constant is ≈ 10−9. FAQ finds the optimal objective function value in every simulation.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0121002.g001: Running time of FAQ as function of number of vertices.Data was sampled from an Erdös-Rényi model with p = log(n)/n. Each dot represents a single simulation, with 100 simulations per n. The solid line is the best fit cubic function. Note the leading constant is ≈ 10−9. FAQ finds the optimal objective function value in every simulation.

Mentions: As mentioned above, GM is computationally difficult, and even in the special cases for which polynomial time algorithms are available, the leading constants are intractably large. Given a bounded number of FW iterates, the FAQ algorithm has complexity O(n3). However, a very large lead order constant could still render this algorithm practically infeasible. Fig 1 suggests that FAQ has O(n3) complexity, and also has very small leading constants (≈ 10−9). This suggests that this algorithm is feasible for matching even reasonably large graphs. Note that other state-of-the-art approximate graph matching algorithms also have cubic or worse time complexity in the number of vertices. We will describe these other algorithms and their time complexity in greater detail below.


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)

Running time of FAQ as function of number of vertices.Data was sampled from an Erdös-Rényi model with p = log(n)/n. Each dot represents a single simulation, with 100 simulations per n. The solid line is the best fit cubic function. Note the leading constant is ≈ 10−9. FAQ finds the optimal objective function value in every simulation.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0121002.g001: Running time of FAQ as function of number of vertices.Data was sampled from an Erdös-Rényi model with p = log(n)/n. Each dot represents a single simulation, with 100 simulations per n. The solid line is the best fit cubic function. Note the leading constant is ≈ 10−9. FAQ finds the optimal objective function value in every simulation.
Mentions: As mentioned above, GM is computationally difficult, and even in the special cases for which polynomial time algorithms are available, the leading constants are intractably large. Given a bounded number of FW iterates, the FAQ algorithm has complexity O(n3). However, a very large lead order constant could still render this algorithm practically infeasible. Fig 1 suggests that FAQ has O(n3) complexity, and also has very small leading constants (≈ 10−9). This suggests that this algorithm is feasible for matching even reasonably large graphs. Note that other state-of-the-art approximate graph matching algorithms also have cubic or worse time complexity in the number of vertices. We will describe these other algorithms and their time complexity in greater detail below.

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