Mathematics – Optimization and Control
Scientific paper
2011-12-23
Mathematics
Optimization and Control
7 pages, 2 figures, 1 table
Scientific paper
It is becoming increasingly popular to represent myriad and diverse data sets as graphs. When the labels of vertices of these graphs are unavailable, graph matching (GM)---the process of determining which permutation assigns vertices of one graph to those of another---is a computationally daunting problem. This work presents an inexact strategy for GM. Specifically, we frame GM as a quadratic assignment problem, and then relax the feasible region to its convex hull. We prove that our relaxed optimization function has the same solution as the original problem, yet it is continuously differentiable. Because the objective function is not necessarily convex, we consider multiple principled initializations. Performance exceeds the previous state-of-the-art in all of 16 benchmark tests. Moreover, this approach is fast, scaling cubically with the number of vertices, requiring only about a minute on a laptop for graphs with a few hundred vertices. We illustrate this approach via a brain-graph application (the Caenorhabditis elegans "connectome"). We find that we can find the optimal solution for nearly every random permutation of the connectome that we sample. Although this strategy already natively operates on weighted graphs, either directed or undirected, we propose a number of possible extensions, and make all code available.
Conroy John M.
Fishkind Donniell E.
Kratzer Steven G.
Podrazik Louis J.
Priebe Carey E.
No associations
LandOfFree
Fast Inexact Graph Matching with Applications in Statistical Connectomics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast Inexact Graph Matching with Applications in Statistical Connectomics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Inexact Graph Matching with Applications in Statistical Connectomics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-191869