AC$\oplus$DC search: the winning solution to the FlyWire ventral nerve cord matching challenge

This paper describes the $A$lternating $C$ontinuous and $D$iscrete $C$ombinatorial (AC$\oplus$DC) optimizations behind the winning solution to the FlyWire Ventral Nerve Cord Matching Challenge. The challenge was organized by the Princeton Neuroscience Institute and held over three months, attracting research teams with expertise in machine learning, high-performance computing, graph data mining, biological network analysis, and quadratic assignment problems. The goal of the challenge was to align the connectomes of a male and female fruit fly, and more specifically, to determine a one-to-one correspondence between the neurons in their ventral nerve cords. The connectomes were represented as large weighted graphs, and the challenge was posed as a problem in graph matching, or finding a permutation that maps the nodes of one graph onto the nodes of another. The winning solution to the challenge alternated between two complementary approaches to graph matching--the first, a combinatorial optimization over the symmetric group of permutations, and the second, a continuous relaxation of this problem to the space of doubly stochastic matrices that is amenable to Frank-Wolfe methods. We provide a complete implementation of these methods in MATLAB; with only a few hundred lines of code, it is able to obtain a winning score to the challenge in less than 15 minutes on a laptop computer.