  The graph matching problem seeks to find an alignment between the nodes of
two graphs that minimizes the number of adjacency disagreements. Solving the
graph matching is increasingly important due to it's applications in operations
research, computer vision, neuroscience, and more. However, current
state-of-the-art algorithms are inefficient in matching very large graphs,
though they produce good accuracy. The main computational bottleneck of these
algorithms is the linear assignment problem, which must be solved at each
iteration. In this paper, we leverage the recent advances in the field of
optimal transport to replace the accepted use of linear assignment algorithms.
We present GOAT, a modification to the state-of-the-art graph matching
approximation algorithm "FAQ" (Vogelstein, 2015), replacing its linear sum
assignment step with the "Lightspeed Optimal Transport" method of Cuturi
(2013). The modification provides improvements to both speed and empirical
matching accuracy. The effectiveness of the approach is demonstrated in
matching graphs in simulated and real data examples.
