![]() Part of the reason for the lack of publications that structurally compare brain-graphs is that existing algorithms for matching very large graphs are largely ineffective, often sacrificing accuracy for efficiency. Yet, recent results suggest that the graph invariant approach to classifying is both theoretically and practically inferior to comparing whole graphs via matching. Thus, available tests for connectopic explanations of psychiatric disorders hinge on first choosing particular graph invariants to compare across populations, rather than comparing the graphs’ structure directly. disorders of the connections of the brain. This is despite the widely held doctrine that many psychiatric disorders are fundamentally “connectopathies,” i.e. To date, however, these comparisons have largely rested on anatomical (e.g., shape) comparisons, not graph (e.g., structural) comparisons. ![]() For example, it is becoming increasingly popular to diagnose neurological diseases via comparing brain images. Analyzing connectomes is an important step for many neurobiological inference tasks. ![]() We are motivated by applications in “connectomics,” an emerging discipline within neuroscience devoted to the study of brain-graphs, where vertices represent (collections of) neurons and edges represent connections between them. Graph matching has applications in a wide variety of disciplines, spanning computer vision, image analysis, pattern recognition, and neuroscience see for a comprehensive survey of the graph matching literature. In casting the GMP as a QAP, we bring to bear a host of existing optimization theoretic tools and methodologies for addressing graph matching: Frank-Wolfe, gradient-descent, etc. While QAPs are known to be NP-hard in general, they are widely applicable and there is a large literature devoted to their approximation and formulation see for a comprehensive literature survey. QAPs were first devised by Koopmans and Beckmann in 1957 to solve a ubiquitous problem in distributed resource allocation, and many important problems in combinatorial optimization (for example, the “traveling salesman problem,” and the GMP) have been shown to be specialized QAPs. In its most general form, the graph matching problem (GMP)-finding an alignment of the vertices of two graphs which minimizes the number of induced edge disagreements-is equivalent to a quadratic assignment problem (QAP). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.Ĭompeting interests: The authors have declared that no competing interests exist. įunding: This work was partially supported by the Research Program in Applied Neuroscience (JV, RJV, CEP, ), a National Security Science and Engineering Faculty Fellowship (CEP, ), Johns Hopkins University Human Language Technology Center of Excellence (DEF, JV, CEP, VL, ), and the XDATA program of the Defense Advanced Research Projects Agency (CEP, ) administered through Air Force Research Laboratory contract FA-0303. The work is made available under the Creative Commons CC0 public domain dedicationĭata Availability: The C. This is an open access article, free of all copyright, and may be freely reproduced, distributed, transmitted, modified, built upon, or otherwise used by anyone for any lawful purpose. Received: SeptemAccepted: FebruPublished: April 17, 2015 (2015) Fast Approximate Quadratic Programming for Graph Matching. Citation: Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, et al.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |