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
Performance of U, QCV, PATH, and FAQ on synthetic C. elegans connectome data, graph matching the true chemical connectome with permuted versions of itself.Error is the fraction of vertices incorrectly matched. Circle indicates the median, thick black bars indicate the quartiles, thin black lines indicate extreme but non-outlier points, and plus signs are outliers. The left panel indicate error (fraction of misassigned vertices), and the right panel indicates wall time on a 2.2 GHz Apple MacBook. FAQ always obtained the optimal solution, whereas none of the other algorithms ever found the optimal. FAQ also ran very quickly, nearly as quickly as U and QCV, and much faster than PATH, even though the FAQ implementation is in Matlab, and the others are in C.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0121002.g005: Performance of U, QCV, PATH, and FAQ on synthetic C. elegans connectome data, graph matching the true chemical connectome with permuted versions of itself.Error is the fraction of vertices incorrectly matched. Circle indicates the median, thick black bars indicate the quartiles, thin black lines indicate extreme but non-outlier points, and plus signs are outliers. The left panel indicate error (fraction of misassigned vertices), and the right panel indicates wall time on a 2.2 GHz Apple MacBook. FAQ always obtained the optimal solution, whereas none of the other algorithms ever found the optimal. FAQ also ran very quickly, nearly as quickly as U and QCV, and much faster than PATH, even though the FAQ implementation is in Matlab, and the others are in C.

Mentions: Fig 5 displays the results of FAQ (initialized at J) along with U, QCV, and PATH. The left panel indicates that FAQ always perfectly unshuffles the chemical connectome, whereas none of the other algorithms ever perfectly unshuffles the graph. In light of Proposition 1, this is unsurprising. Indeed, there is a unique automorphism for this connectome, and the graph is asymmetric. For any choice of Q(k), the indefinite problem (6) therefore has a unique solution, namely . FAQ finds this global minima in all the cases. Contrast this with Eq (4)—the objective function of PATH and QCV—which could have multiple global minima in 𝒟. This could account for the high variance in the performance of QCV and PATH in Fig 5.


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)

Performance of U, QCV, PATH, and FAQ on synthetic C. elegans connectome data, graph matching the true chemical connectome with permuted versions of itself.Error is the fraction of vertices incorrectly matched. Circle indicates the median, thick black bars indicate the quartiles, thin black lines indicate extreme but non-outlier points, and plus signs are outliers. The left panel indicate error (fraction of misassigned vertices), and the right panel indicates wall time on a 2.2 GHz Apple MacBook. FAQ always obtained the optimal solution, whereas none of the other algorithms ever found the optimal. FAQ also ran very quickly, nearly as quickly as U and QCV, and much faster than PATH, even though the FAQ implementation is in Matlab, and the others are in C.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0121002.g005: Performance of U, QCV, PATH, and FAQ on synthetic C. elegans connectome data, graph matching the true chemical connectome with permuted versions of itself.Error is the fraction of vertices incorrectly matched. Circle indicates the median, thick black bars indicate the quartiles, thin black lines indicate extreme but non-outlier points, and plus signs are outliers. The left panel indicate error (fraction of misassigned vertices), and the right panel indicates wall time on a 2.2 GHz Apple MacBook. FAQ always obtained the optimal solution, whereas none of the other algorithms ever found the optimal. FAQ also ran very quickly, nearly as quickly as U and QCV, and much faster than PATH, even though the FAQ implementation is in Matlab, and the others are in C.
Mentions: Fig 5 displays the results of FAQ (initialized at J) along with U, QCV, and PATH. The left panel indicates that FAQ always perfectly unshuffles the chemical connectome, whereas none of the other algorithms ever perfectly unshuffles the graph. In light of Proposition 1, this is unsurprising. Indeed, there is a unique automorphism for this connectome, and the graph is asymmetric. For any choice of Q(k), the indefinite problem (6) therefore has a unique solution, namely . FAQ finds this global minima in all the cases. Contrast this with Eq (4)—the objective function of PATH and QCV—which could have multiple global minima in 𝒟. This could account for the high variance in the performance of QCV and PATH in Fig 5.

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