AC$\oplus$DC search: behind the winning solution to the FlyWire graph-matching challenge
Authors: Daniel Lee
Arie Matsliah
Lawrence K. Saul
Venue: Accepted by TMLR ()

Abstract: This paper describes the Alternating Continuous and Discrete Combinatorial (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, ending on January 31, 2025. During this period, the challenge attracted teams of researchers 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 sparse weighted graphs with thousands of nodes and millions of edges, and the challenge was to find the permutation that best maps the nodes and edges of one graph onto those of the other. 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. For the latter, the doubly stochastic matrices were optimized by combining Frank-Wolfe methods with a fast preconditioner to solve the linear assignment problem at each iteration. We provide a complete implementation of these methods with a few hundred lines of code in MATLAB. Notably, this implementation obtains a winning score to the challenge in less than 10 minutes on a laptop computer.

Published in Transactions on Machine Learning Research (01/2026)
AC + DC search: behind the winning solution to the FlyWire graph-matching challenge
Daniel D. Lee
dd446 edu
Cornell Tech, School of Electrical and Computer Engineering 2 W Loop Rd, New York, NY 10044
Arie Matsliah
arie@princeton.c edu
Princeton Neuroscience Institute 40 Woodlands Way, Princelon, NJ 08540
Lawrence K. Saul
konl@öfadironknniitutt.oo
Flatiron Institute, Center for Computational Mathematics 162 Fifth Avenue, New York, NY 10010
Reviewed on OpenReview: https: // opt.//veew.ee....e net/ forum? id- 8M
Abstract
This paper describes the Alternating Continuous and Discrete Combinatorial (AC#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, ending on Jamuary 31, 2025. During this period, the challenge attracted leams of researchers 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 one-to-one correspondence between the neurons in their ventral nerve cords. The connectomes were represented as sparse weighted graphs with thousands of nodes and millions of edges, and the challenge was to find the permutation that best maps the nodes and edges of one graph onto those the other. 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 socond, continuous relaxation of this problem the space of doubly stochastic matrices. For the latter, the doubly stochastic matrices were optimized by combining Frank- Wolfe methods with a fast preconditioner to solve the lincar assignment problem at each iteration. We provide a complete implementation of these methods with few hundred lines of code in MATLAB. Notably, this implementation obtains a winning score to the challenge in less than 10 minutes on laptop computer.
1 Introduction
The problem of graph matching is to find the permutation that best maps the nodes and edges of one graph onto those of another. The problem arises in many areas of science and engineering where graphs are used to encode similarity, co-dependence, or the flow of information: specific applications include keypoint matching
in computer vision (Conte el. al. 2004 Haller et al.) 2022 Zhou el al. 2023). biological and social network
alignment [Chen et al. 2016 Mamano Hayes 2017 Lázaro et al.j 2025 and vulnerability detection in software systems (Li et al. 2019). The problem is solved in practice by maximizing an objective function that scores each permutation by quantifying the similarity of nodes and edges that brings into correspondence.
Graph matching is in general NP-hard problem; one find globally optimal solution by exhaustively

---

Published in Transactions on Machine Learning Research (01/2026)
considering all permutations, but this is only possible for small graphs. For large graphs, the best solvers rely on approximate search algorithms that attempt to find high-scoring match.
A particular instance of this problem was at the heart of a recent challengepposed by the Wire consortium at the Princeton Neuroscience Institute. The goal of the challenge was to align the connectomes of a male and female fruit fly, where each connectome was represented by a sparse graph. The nodes in these graphs represented neurons, and the edges indicated which neurons were connected by synapses. These graphs were also directed and weighted: each edge counted the number of synapses observed in particular direction between two neurons. The determination of these connectomes- down to the level of individual synapses was the culmination of many years of painstaking rescarch (Takemura et al.) 2017 Dorkenwald et al. 2024 Bates et al. 2025), and the Wire consortium has since issued a stream of open challenges to further process these results. This particular challenge was posed in the winter of 2024, and its purpose was to study how sex differences in fruit flies are manifested in the connectomes of their ventral nerve cords (VNCs).
There were two features of this challenge that made for an especially compelling problem in graph matching, First was the problem size: each VNC connectome was represented by graph with 18524 nodes and millions of edges. Notably, these connectomes are larger by two orders of magnitude than that of the hermaphrodite C. elegans, which consists of only 302 neurons (Chen et al., 2016; Varshney et al.) 2011 Lázaro et al. 2025). The graphs in the challenge were also much larger than those of typical benchmarks for keypoint- matching problems in computer vision (Haller et al., 2022) and other related problems in graph-representation learning (Morris et al. 2020). At the same time, the VNC connectomes were small enough that soft matches, represented by dense doubly stochastic matrices, could fit into the memory of a modestly equipped computer. It was therefore possible to explore approaches that took advantage of this ability and did not rely on purely combinatorial techniques.
The second distinguishing feature of the challenge was the particular way that different matches were scored.
Let ı denote the permutation of the indices (1,2....,n) n),, with n= 18524, that maps i to Ti, and let A and B denote, respectively, the sparse nxn matrices whose nonzero elements record edge weights in the male and female connectomes. The alignment score for the VNC matching challenge was computed as
S(T) =
Σ min(A Aig. BrIT,)
The beghtted-intesscttinn score in eq. 11 is a variant on the weighted Jaccard distance, and it was chosen by the challenge organizers because it appeared to correlate better with known biological isomorphisms. In particular, they found that eq. ([) was more robust with respect to these isomorphisms than scores based on simple correlation or cosine distance. The score in eq. can be computed efficiently by restricting the sum to nonzero elements of A and B.
The challenge ran for three months, and it attracted teams of researchers with expertise in machine learning, nigh--perfrmmance computing, graph data mining, biological network analysis, and quadratic assignment problems. The challenge organizers provided a baseline match that was determined from neuron cell types, and this benchmark solution (though not the cell type metadata) was made available for teams to use as a warm start. Nearly all teams continued to submit improved solutions up to the deadline on January 31, 2025, and the scores of these submissions were independently verified by the challenge organizers. Throughout the challenge, scores were not disclosed, and different teams did not share code or details of their solutions.
In this paper, we reveal the methods behind the winning solution to the challenge. The solution combined two complementary approaches to graph matching: the first was a combinatorial optinization over the space of permutation matrices, and the second was a continuous relaxation of this problem to the space of doubly stochastic matrices. Both of these approaches were pursued individually by other high-placing teams in the challenge lears which included, for example, the co-inventors of leading methods based on simulated annealing Mamano & Hayes, 2017) and fast approximate quadratic programming (Vogelstein et al. 2015). These methods, based on either discrete or continuous search, provided strong baselines for the challenge, placing among the top five scores on the Wire VNC leaderboard. However, we describe here, it was
https://codex.. flywire..rrr.rrrrrrrrrrrr.. www.wtww....w...eeeeee hta/aap//ncmmmacchnng.ooo challegge
2

---

Published in Transactions on Machine Learning Research (01/2026)
combination of these complementary approaches that led much more quickly to winning solution. We refer to this alternation of continuous and discrete combinatorial methods ACBDC search.
The continuous relaxation of this problem is obtained by extending the score in eq. to the convex set of doubly stochastic matrices. The relaxed objective is given by
S(P) = Σ min((ri B&s P Pge,
(2)
where P is an n X n nonnegative matrix whose rows and columns sum to one. Note that the objective in oq. (2) is quadratic but not concave in its argument; also, when is dense, it appears naively to require O(n*) operations to perform its quadruple sum. The winning solution optimized eq. (2) by adapting Frank-Wolle methods for constrained convex optimization (Frank & Wolfe, 1956) alongside a fast preconditioner to solve the linear assignment problem each iteration. This type of relaxation has been used successfully for other quadratic assignment problems (Vogelstein et al. 2015). The main novelties described in this paper are highly optimized routines for computing the gradient of eq. 2 and projecting this gradient into the space of permutation matrices.
With these techniques, we show how to obtain a winning score to the challenge in under 10 minutes, on a laptop computer, with a few hundred lines of code in MATLAB. Though not revealed at the time because teams on the Icaderboard were listed by the date of their most recent submission- ACODC methods held the top score for the final forty days of the challenge. These methods should be of direct interest to other researchers in biological network analysis, and also of general interest to researchers in machine learning whose problems require optimizations over the permutation group (Mena et al. 2018 Cuturi et al. 2019:
Grover et al. 2019 Santa Cruz et al. 2019 Prillo & Eisenschlos 2020 Dröge et al. 2023).
The organization of this paper is as follows. In section 2 we describe a greedy search algorithm for the combinatorial optimization of eq. [ over the space of permutation matrices. This approach has the ad- vantage of simplicity, and it also directly optimizes the score in eq. (1) But it improves the score slowly in the early stages of optimization, and in the later stages, it is prone to getting stuck. In section 3 we describe a first-order method for the continuous optimization of eq. (2). This method has the advantage that it makes rapid initial progress, but it does not converge to permutation matrix that maximizes eq. ( In section [ we describe the winning solution that is found by alternating these approaches, and we also discuss further techniques (albeit with diminishing returns) for optimizing the scores in eqs. (1 and (2). Finally, in section we conclude with a discussion open problems and directions for future work.
2 Discrete search
There are many ways to search for a permutation that maximizes the score in eq. [ Arguably the simplest is a hill-climbing approach that makes local moves in the space of n! permutations. This approach can oquivalently be viewed as an optimization over the space of n xx permutation matrices-that is, matrices whose elements are equal zero one and whose rows and columns sum one. Within this approach, there are also many types of local moves that can be considered, but the simplest are those that swap exactly one pair of indices (viewing permutations as shuffles) or exactly one pair of rows (viewing them as matrices). In this section, we describe an efficient way to evaluate these moves and illustrate the strengths and weaknesses of this approach.
2.1 Evaluation of pairwise swaps
Our first goal is to evaluate how the score in eq. 1 is changed by single pairwisc swaps. The following nolation will be useful. Let pr denote the nxn permutation matrix corresponding to the permutation whose elements are given by P = 6(T,, k), where d(.,)) is the Kronecker delta function. Similarly, let ay denote the permutation that swaps and j while leaving all other indices intact, and let diy denote the composition (from right to left) of these two permutations- that is, the permutation obtained by first swapping and j and then permuting the indices according to æ.
3

---

Published in Transactions on Machine Learning Research (01/2026)
We begin by computing the x symmetric matrix A whose elements record the difference in scores between permutations that are related by single pairwise swap of indices. In particular, let
A = 0()) -
(3)
so that the diagonal elements of A are zero while the nonzero elements indicate those local moves in the space of permutations that change the score. Note that for this challenge, with n 18524 nodes per graph, each matrix A records the effect of over 171 million pairwise swaps.
Let P denote the convex set of doubly stochastic n X matrices. Since the score in eq. (2 is quadratic in the matrix P E P, the differences in eq. (3) can also be expressed in terms of the gradient and Hessian of this score. The gradient of eq. (2 is given by the nxn matrix with elements
[VS(P))
= Σ ab
min( Aug Bae) + min(m Bes)) Psk:
(4)
and it generally a dense matrix even when the matrices A, B, and P in eq. 4 are sparse. Of particular interest is the form of this gradient at the permutation matrix pa. We denote this gradient by G = VSPP). and its elements are given by
Gje = Σ (iij Br,e) + min(AAs, Bend)
(5)
The gradient in eq. (5) can be computed in (n²²) operations by exploiting the sparsity of the connectome weights in the matrices and B. In particular, for the matrices of size n= 18524 this challenge, this gradient takes about 12 seconds to compute on a Macbook Pro (M1 Max) laptop.
Next consider the way in which the Hessian of the score in eq. 2 enters into the calculation of differences in eq. 3). To this end, we introduce a new matrix B", whose elements are obtained by permuting the rows and columns of B according to the permutation n; in particular,
B Brary
(6)
The elements of 8 appear in certain combinations of Hessian elements that arise repeatedly in the caleu- lation of the matrix A As further shorthand, we define the functions
(7((a) min(a, BB) + min(a, BJ,) min(a, B3) min(a, BJ)),
(7)
where in practice we will take the argument a to be a particular connectome weight from the matrix A. For example, when a a= -As; the right side of eq. 7 expresses a particular linear combination of elements from the Hessian eq. (2 evaluated at the matrix PT.
With the above definitions, we can express the effects of swaps in eq. (3) in terms of the connectome weights and the gradient and Hessian of the score. In terms of these quantities, the elements of A given by
1 G + GJT, GT,,, GTT,, + (A5(s)) + -H,()) H (Ap))
(8)
and again, all n² matrix elements in this equation can be computed in 0(n²) operations for given per- mutation For the matrices of size 18524 in this challenge, it takes about additional seconds to compute the elements in eq. ( on top of the gradient in eq. (5). We provide pseudocode for a procedure (EVALuATESWAPS) to compute these elements in Algorithm
It is possible for none of the matrix elements A in eq. (8) to be positive. When this the case, indicates that the permutation cannot be improved by a single pairwise swap of indices. Otherwise, the largest (i.e., most positive) element of = indicates the swap that most improves the weighted-inntersottne score in eq. [pp This suggests a simple algorithm for greedy local search which describe in the next section.
4

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm Given connectome weights A, B x and base permutation x, evaluate the score differ- ences in eq. obtained by single pairwise swap of indices.
procedure A SVALUATESWAP((AABB.
Compute gradient at and permute rows and columns of B
for i to n do
for j + to n do
Gij t- [k=[(min( (min(AAn Baus) + min( (Atte Bjns))
B f Ba,,,
end for end for Evaluate difference in scores due to pairwise swaps
for i to n do
for j - 1 to n do
H₁ +- min( Ag, B
+ min Ag, - min(mnn B
min(AH, Bi)
Hj < min(AAj. B.a + min( 3j
(Ajj,
mij(Ajj, B,,) min(Ajj. B²))
Нi - min(Aij, BT) + *minn(As B
-min(Aij, BT,
min( (ij( Biy)
Hςs < min(Aft BB) + *min(Aj;: B5g
-min(Aj,, B7)
min( (an(AAts Bj)
Dij < Gin, Gjv, Gin, Gjzz Hu + H5j Hij -ys
end for end for end procedure
2.2 Greedy search with pairwise swaps
attempt to optimize the score in eq. ① by alternating two procedures; the first evaluates the effect of each pairwise swap by computing its corresponding element in A and the second performs those swaps that seem likely to increase the score by the largest amount. We give the pseudocode for a greedy search based on these two procedures in Algorithm 2 The search terminates when the first procedure, sketched in Algorithm returns a matrix A x with no positive clements.
Starting from initial permutation
We threshold procedure in Algorithm 2 performs up swaps that increase the score while skipping over swaps that do not. The threshold is only needed in the early stages of optimization, when the permulation is very far from optimal; in this case, the matrix A returned by the first procedure (EVALUATESWAPS) may have an inordinately large number of positive elements. The MAKESWAPS procedure considers pairwise swaps in descending order of their corresponding elements AT. If the maximal element A positive, then the first such swap is guaranteed to yield permutation with a higher score. However, successive swaps are not guaranteed to increase the score, even if they correspond to positive elements of A", due to possible interference with previously executed swaps. (A trivial example of such interference arises from the symmetry of the matrix A a swap j++i will exactly negale the gain from immediately preceding swap i++j-)
adjust the balance of time spent in these two procedures. The MAKESWAPS
The left panel of Fig. I shows results from the greedy search in Algorithm 2 for different thresholds on the maximum numbers pairwise swaps per iteration. All of these runs were initialized from the benchmark solution with score 5154247 provided by the challenge organizers. The algorithm converges to different solutions for different thresholds r, but all of these solutions have scores around 5818K. These solutions are evidence of the large number of local maxima this problem: there are many permutations whose scores cannot be improved by any pairwise swaps of indices (of which there are over 171 million).
There are many ways to augment the greedy search in Algorithm 2 so that it discovers higher-scoring permutations. One is to introduce an element of randomness, sometines performing a pairwise swap that decreases the score, as is done in simulated annealing (Mamano & Hayes 2017). Another is to evaluate and perform higher-order moves that swap three or more indices a time. While these approaches may require more resources, one can also optimize them aggressively, in faster languages than MATLAB, while exploiting opportunities for parallelism (e.g., multi-core, GPUs) (Koblentz) 2025
5

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 2 Given connectome weights A, B R"x= and an initial permutation To, perform greedy
search with up pairwise swaps (per iteration) to find local maximum in the alignment score of eq.
procedure x = CREEDYSEARCH(AAAB.o..
procedure
MAKESWAPS(AABB7,A.))
S Eij min(Ay, BrSx,)
N no A EvALUATHSWWPS((A B)
while ((T > 0) AND (max,, (A 0)) do
while (max; (A,) 0) do + MAKEŠWAPS(A, B, T)
(i.j) t- argmaxig (Aij)
x' + π oij
A + EVALUCTESSAPPS(A, B,
+ Eij min( (Aigi Bx(sj)
end while end procedure
if (S' > S) then
(n, (m,S,T)
(T , T-
end if
(Aij. Agi) + (0,
end while
end procedure
discrete search
continuous relaxation
5900K
5900K
5700K
5700K
5850K
5820K
5840K
score
5810K
0-000000
score
5500K
5500K
5830K
20
minutes
15
20
minutes
5300K
5300K
Φ- T 200
doubly stochastic permutation
- T 400
O- T 800
5100K
5100K
0
5
10 minutes
15
20
0
3
6
minutes
Figure Alignment scores in eqs. 12 versus wall clock time starting from the benchmark solution
score 5154247. Left. Greedy discrete search in Algorithm 2 with up to pairwise swaps per iteration. Right.
Frank-Wol updates in eqs. (11 and 13 to optimize the continuous relaxation in eq- (2). Neither method by itself converges to a winning score for the challenge (indicated by the dashed line at 5850K).
Multiple leams experimented with these ideas in the days and weeks leading to the deadline. But even with considerably longer runs, these more elaborate forms of discrete search were not able to reach the dashed line in Fig. indicating a score (at 5850K) that was high enough however, this winning score can be obtained in under 10 minutes by combining discrete and continuous approaches to the optimization of eq. (1] With this goal in mind, we now turn to the latter approach.
the challenge. As mentioned carlier,

---

Published in Transactions on Machine Learning Research (01/2026)
3 Continuous relaxation
In this section we describe a complementary approach to graph matching, one based on a continuous op- timization over the convex set of doubly stochastic matrices. This type of relaxation has been studied previously for quadratic assignment problems (Vogelstein et al. 2015), but for the best results this contin- nous optimization must be tailored specifically to the weighted-inte -nnthteedinttesocttinn score in eq. This score is quadratic function of P. but it is not concave, and therefore an iterative hill-climbing procedure is not guaranteed to find its global maximum. Here we show that an iterative procedure, based on the Frank-Wolfe algorithm for constrained convex optimization (Frank & Wolfe, 1956), can be adapted to this problem with extremely competitive results. One part of this procedure is to calculate a projected gradient, and we also describe fast. preconditioner for this calculation that is crucial to its overall efficiency.
3.1 Frank-Wolfe updates
The iterative procedure shown in Algorithm g and it alternates between three steps. The first step computes the gradient in eq- 4 As mentioned previously, it takes about 12 to compute this gradient at permutation matrix of size n 18524. For this iterative procedure,
need to compute the gradient at doubly stochastic matrices, which in general can take much longer. As we shall see, however, the procedure converges very quickly, so that in practice-41 if the search is initialized by a permutation matriz- we only need to compute gradients for doubly stochastic matrices that are highly sparse. When this is the case, it takes only slightly longer to compute the gradient eq.
The second step of the iterative procedure projects this gradient back into the convex of doubly stochastic matricos. In particular, this step computes
Q: = argmax trace TT)( QEP
(9)
Note that eq. 19) defines linear program whose solution always lies at vertez of the set P; in other words, its solution Q is not merely a doubly stochastic matrix, but also a permutation matrix. The optimization in eq. 99 is most commonly known as the linear assignment problem, or the problem of perfect matching in a complete bipartite graph. It can be solved by the so-called Hungarian method (uhnn 1955) in polynomial time (Munkres) 1957 Edmonds & Karp 1972 Tomizawa 1971), but this not the approach that was used in the winning solution to the challenge. We discuss this step more later, since without further acceleration it presents the biggest computational bottleneck.
The third step of the iterative procedure is to find the convex combination of Pt and Qa that maximizes the score in eq. ( In particular, the update is given by
04 = argmax ((1-a)) aE[0.1]
(10)
P.1 = (1-a)P
(11)
In practice, it is not necessary to perform a line search to compute the optimal convex combination in eq. (10 Instead one can simply calculate the point where the gradient of the score vanishes along the line connecting P, and Q-- Since the score eq. (2) is quadratic in its argument, this gradient vanishes at some point (1-A)P; + XQ; where R.R. In particular, satisfics the linear equation
(1- trace ((Qi-..) [..P)) = AtQ,ace((Q) [V(Q.))
(12)
If E [0, 1], then the weight a, in eq. 10) is simply equal to X. If (0, 1]. then there are two possibilities: either the score along the line from P. to Q, is concave with a marimum at À >>L. 1, or it is convex with a minimum X- In both these cases, eq. (10) yields a; 1. Finally, we note that the updates eqs. @ converge monotonically to doubly stochastic matrix that stationary point (where the gradient has no component inside P) of this procedure.

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm Given connectome weights A, B R and an initial doubly stochastic matrix Po, perform T Frank- Wolfe updates to optimize the score in eq-
(2). then return the doubly stochastic matrix Pr and permutation matrix 117 found from these updates.
procedure (Pr. I DOFRAAKWOLPP((A....
P Po
for + do Compute gradient
for i 1+11t to n do
for srrj+1o to n do
Gij + Ene minn(As, BB5) + min(Ax, BBt)] Pste
end for end for
Project gradient, compule slep size, and interpolate
Q argmaxQer trace G Q]
arginaxaejo.1] (8(1-a)
P (1-a)P+ aQ
Compute matchstg permutation matriz + argmaxner trace [
end for
Pr e P 1 + end procedure
3.2 Application to graph matching
While the Frank-Wolf updates lead to monotonic improvement in the score of eq. 2 they converge in general to a doubly stochastic matrix and not. permulation matrix. But the latter that is needed align two graphs with a score given by eq. [T]. To rectify this problem, we also compute a permutation
matrix II, each iteration of the updates in eqs. 9 This is done by projecting the doubly stochastic
matrix Pt into the space of permutation matrices:
II, = argmax (trace P.T1)
(13)
TEP
Eq. 13 is a lincar program whose solution is the closest-matching permutation matrix to P.. Again this can be solved by the Hungarian method or any other algorithm for perfect matching in complete bipartite graph. Tn practice the linear program eq. (13) is much faster to solve than the one eq. 9 the reason is that the doubly stochastic matrix Pt in eq. (13) is highly sparse expressible as convex combination of small number of permutation matrices-whercas the gradient VS(P,) in eq. 9 is dense.
Since the updates for P; in eqs. it is also true that their projections to 1I, in eq. (13) converge to permutation matrix at a vertex of this set. But while the scores (S(P)) of these doubly stochastic matrices increase monotonically as a result of these updates, the same is not true for the scores (S(TT)) their closest-maten mateshnn permutation matrices. The right panel of Fig. I plots the scores from these updates starting from the benchmark solution with score 5154247.
11 converge to point inside the convex set of doubly stochastic matrices,
From the results in Fig. D make several observations of interest. First, at the outset of the optimization, the continuous updates in the convex set of doubly stochastic matricos (shown right) increase the score much more rapidly than the discrete search based on pairwise swaps (shown left). Second, the scores of the permutation matrices 11, in eq. (13) generally track the scores of the doubly stochastic matrices P, in eq. (II) but the latter increase monotonically while the former do not. Third, the scores of the doubly stochastic matrices Pt saturate around 5856K, while those the permutation matrices II, saturate just below 5850K. In particular, these updates by themselves do not obtain handily winning score for the challenge.
8

---

Published in Transactions on Machine Learning Research (01/2026)
3.3 Acceleration by preconditioning
In this section we describe how the winning entry to the challenge solved the linear program in eq- 9 As mentioned previously, this problem is equivalent to one of perfect matching, and it is more typically posed in terms of a cost matrix, CeR"x,, where the goal is to find the permutation x that minimizes the lincar assignment cost
trace (T = - Cine
(14)
There is an internal (though not especially well-documented) routine in MATLAB that solves this problem by permuting large entries to the diagonal of a sparse matrix (Duff & Koster 2001). It assumes that C is stored as a dense matrix, and is called as
म matlab. internal internal.graph. www.gg.a.......rgeee per.pppcpheectttchcingCgCC
(15)
We used this internal routine to solve the linear programs in eqs. 9 and 13 whose cost matrices had 18524 rows and columns. The routine is based on a polynomial-tinee algorithm, but it can be very slow if called in the above manner when C is a dense matrix. For example, when C' = (P()), this routine requires 10 to 15 minutes per call on MacBook Pro (M1 Max) with 64 GB of RAM. Of course it would not be possible to obtain a winning solution in less than 15 minutes if each iteration of Algorithm required this much computation.
We discovered heuristie that greatly accelerates this routine for perfect matching when it is called with the gradients VS(P)) that appear in eq. !9) The heuristic is based three observations. First, the result in eq. 15 is unaffected if we shift any row column of the cost matrix by a constant value. Second, the result is trivially equal to the identity permutation if C has negative elements on the diagonal and nonnegative elements off the diagonal. Third, suppose that an approximate solution w can be guessed for eq. (15), where w is a permutation that nearly solves the linear assignment problem. Then the matrix product C (PO) should be closer than C to a matrix whose smallest entries appear on the diagonal.
Based on these observations, we discovered something akin to preconditioner for the routine in eq. 15 when C = -- VS((:). We describe this proconditioner in detail because it yielded significant speedup, reducing the time per call by factor of 50x, or from minutes to seconds. As shorthand, let 1 ER" denote the column vector of all ones, and let diag(-) denote the column vector of diagonal elements from its matrix argument. We start by observing that II, in eq- (13) provides an approximate guess for Qt in eq. With this and the previous observations in mind, we solve eq. (9) in the following way:
(PERMUTE)
A VS(P.
(16)
(SHIFT)
Ω = A + diag (A)1" + diag(A) - 11 TA A11 matlab. internal graph www..peeeeecaaaciing------
(17)
(MATCH)
(18)
(UNPERMUTE)
Q IIII,
(19)
Intuitively, the first of these steps (PERMUTE) ensures that A has positive elements on the diagonal, the second (SHFF) makes it more likely that Ω has negative elements off the diagonal, and the third (MAтCH) is fastest when & has positive elements on the diagonal and none clsewhere, in which case w is close to the identity permutation. We do not have a formal justification for this heuristic, but in practice it removed eq. 9 as the main bottleneck Algorithm Further details can be found in Appendix A
4 A winning solution (and beyond)
It is possible to combine the methods for search in the last two sections and reap the advantages of both. The discrete swaps in section 2 lcad to slow but steady improvement until they reach local maximum from which they cannot escape. The continuous Frank-Wolf updates in section 3 lead to rapid improvement in the weighted-inten intersection score, but they plateau when the high-scoring doubly stochastic matrices in eq. (2) do not project high-scoring permutation matrices eq. (1] A winning solution can be quickly obtained by alternating these approaches, using each to offset the weaknesses of the other. This is the method of alternating continuous and discrete combinatorial (ACBDC) search.
9

---

Published in Transactions on Machine Learning Research (01/2026)
AC+DC search
5855K
5850K
score
5845K
doubly stochastic
5840K
permutation (projected)
permutation (swaps)
0
10
20
30
40
50
minutes
Figure 2: Alignment scores in eqs. 1 versus wall clock time starting from the benchmark solution at score 5154247. The scores were obtained by alternating updates for continuous and discrete combinatorial (AC@DC) search-in in particular, Frank-Wolfe updates (in batches of ten) for the former and greedy pairwise swaps (repeated until no further swaps improved the score) for the latter. takes less than minutes for this method to produce a winning score for the challenge (indicated by the dashed line al 5850K).
4.1 ACODC search
Fig. 2 shows the results from this alternating approach. First, we use ten Frank-Woll updates to climb from the benchmark score at 5154K to a score above 5845K in less than 7 minutes. Then we apply pairwise swaps until the score can no longer be further improved; in 3 additional minutes, these swaps produce a solution whose score exceeds 5850K, higher than all but the wimning entry to the challenge. As shown in the figure, the score can be further improved by alternating these different types of search, with the Frank- Wolfe updates jumping out of the local maximum reached by the pairwise swaps, and the pairwise swaps reaching higher scores from wherever they subsequently initialized. This combined approach reaches score over 5852K in under 50 minutes. In the supplementary material, provide MATLAB code (less than 400 lines) to obtain this winming solution, as well as code to generate all the figures in this paper.
Fig. 2 also highlights the different role played by the contimuou Frank- Wolfe updates in the later stages of optimization. In the first few iterations, before the five-minute mark, there high degree of correlation between the scores of the doubly stochastic matrices in eq. [1I and their closest-matching permutation matrices in eq. [3]: when the former increase (shown in blue), do the latter (shown in red). But this relationship no longer holds past the five-minute mark in Fig. 2 In this regime, we see that higher-scoring interior solutions often project to lower-scoring permutation matrices. Nevertheless these continuous updates still play a crucial role: they re-initialize the next stage of discrete updates in a basin of alt where pairwise swaps can reach a higher maximum the score in eq. The overall result is the seesaw pattern of improvement between the red and yellow curves that we see Fig. Finally we note that the experiments Fig. provide an ablation study, revealing the ceilings in performance when discrete and continuous updates are not alternated but instead used in isolation.
10

---

Published in Transactions on Machine Learning Research (01/2026)
4.2 Further improvements
For the VNC matching challenge, we have shown that score of over 5852K can be reached in under one hour by combining simple methods for discrete and continuous search. In this section, we give a brief overview of additional methods to further improve the score. At the outset, we note that above 5852K the optimization appears to enter a regime of diminishing returns. As shown in Fig. 2 it takes only few minutes to improve the benchmark score by nearly 700K, and less than an hour after that to improve the score by an additional 10K. But beyond this regime it takes many additional hours-oven for the more claborate methods we discuss next to obtain improvements that are ordens-of-maggituuee less. In light of this, we only provide high-level sketch of these methods.
4.2.1 Higher-order swaps
The discrete search in S finds a solution that cannot be improved by further pairwise swaps. This search over permutation matrices can be extended by considering higher-order swaps that permute more than two indices at a time. For higher-order swaps, however, it is no longer feasible to evaluate all possible local moves before considering which ones to perform; there are, for instance, over one trillion different three-node swaps that can be performed a graph with n= 18524 nodes. Instead one can evaluate subset of higher-order moves that seem most likely to yield improvements. For example, we considered the subsct of Chree-cycles {(i+j>>--i)) where the index & was chosen greedily for all pairwise swaps {(i++)) that did not reduce the score by a certain threshold. We also devised similar strategies for considering many different types of higher-order swaps. In total, our most sophisticated discrete scarch considered not only pairwise swaps, but also 3-cycles, 4-cycles, and 5-cycles, as well as 2x2, 3x2, 3x3, 4x2, 5x2, 2x2x2, 3x2x2, and 2x2x2x2 swaps. With these higher-order swaps, it takes another dozen hours to boost the score from 5852K to 5853K (amounting to a gain of less than 0.01%).
4.2.2 Multiplicative updates
The Frank-Wolfe updates in Algorithm 3 produce a sequence of doubly stochastic matrices that improve the score in eq. (2). When these updates are initialized from permutation matrix, they produce a sequence of sparse doubly stochastic matrices. This sparsity has certain computational advantages: for example, it can be exploited to compute the gradient in eq. (4) much more efficiently. But it also has potential disadvantagee in particular, an optimization restricted to sparse solutions may not fully leverage the continuous scarch that is afforded by the relaxation to doubly stochastic matrices.
Recall that the updates in eq. [1 are additive updates in which the existing solution P. is linearly interpo- lated with the projected gradient Qe. We also experimented with multiplicative updates that use the gradient in eq. (4 quite differently. These updates take the form
PP+lle = [Pl] VS(()))
(20)
u; + 0g
where in the numerator of eq. 20 appear the elements of the gradient VS((.) and in the denominator appear Lagrange multipliers v E IR.. This multiplicative update can be derived as a generalization of those for nonnegative and (singly) stochastic matrix factorization {Lee & Seung. 1999 Saul & Pereira 1997). The main generalization is to introduce two sets of Lagrange multipliers into the update; these two sets are nceded to enforce sum-to-one constraints on both the rows and columns of doubly stochastic matrices. The resulting update is similar but not equivalent to the Sinkhorn-Knopp procedure for projecting nonnegative matrix onto the set of doubly stochastic matrices (Sinkhorn & Knopp 1967 J.
The multiplicative updates in eq. (00 can be used to optimize the score in eq. 2 and unlike the Frank- Wolfe updates, they do not involve the expense of computing a projected gradient, as in eq. (9) But to use these updates on dense doubly stochastic matrices, it is necessary to compute the score in eq. 2 and the
gradient in eq. 4 when P dense. Naively this appears to require O(n") operations, a prohibitive scaling for matrices of size n 18524. We devised a faster way to compute these gradients by exploiting the fact that the connectome weights are quanlized. This method is described in Appendix B
11

---

Published in Transactions on Machine Learning Research (01/2026)
Submitted
Name
Score
2025-02-18
Old School
5,853,925
2025-02-17
D. A. Bader, H. A. Sriram, S. Chinthalapudi, and Z. Du
5,853,910
2025-01-31
Old School (Winner)
5,853,779
2025-01-31
D. A. Bader, H. A. Sriram, S. Chinthalapudi, and Z. Du
5,849,534
2025-01-31
Y. Ma, X. Zhu, and L. Zhu
5,842,347
2025-01-31
W. B. Hayes, M. Longo, and R. Longo
5,841,041
2025-01-31
Team FAQ
5,838,188
2025-01-31
D. Hashorva
5,837,872
01-31
J. C. Duarte, C. Larsen, and R. Willemsen
5,834,246
2025-01-31
T. M. da Nóbrega
5,824,339
Table 1: Top ten scores on the leaderboard of the VNC matching challenge as of December 2025. The winning score 2025-01-31 was obtained using the methods in this paper, and the top score 2025-02-18 obtained by combining the methods of the two leading teams.
4.3 Comparison to competing methods
The official winning score to the challenge was 5853779. This score was submitted on Jamuary 31, 2025 and achieved by alternating the additive updates for sparse doubly stochastic matrices in eq. [1] with the multiplicative updates for dense doubly stochastic matrices in eq. (20). Two higher scores were subsequently obtained in February 2025, but only by using the winning solution as an initial seed. Table I reproduces the top ten scores on the leaderboard of December 2025.
A number of competing methods for graph matching were explored by other teams in the challenge. None of these teams obtained scores above 5850K, indicated by the dotted line in Fig. 2 despite in some cases significantly more compute (e.g., hours to weeks versus minutes). The second-place team pursued a purely combinatorial search in a high-performance computing environment [Koblentz] 2025). and their ceiling sug- gests the limitation of this strategy even when backed by considerable resources. This approach, however, was able to improve on the winning solution (using it as an initial seed) after the conclusion of the challenge; this is consistent with our finding that combinatorial methods have larger role to play than continuous ones in the later stages of search. The fourth-place leam in the challenge obtained score of 5841K with mature package for biological network alignment based on simulated annealing (Mamano & Hayes 2017) The strength of this package is its versatility, as it can be applied out of the box to optimize any objective function for graph matching. However, it much slower its initial stages than the Frank- Wolfe updates from section 3 which surpass its score within a few iterations. The fifth-place team obtained a score of 5838K with method for graph matching based on fast approximate quadratic (FAQ) programming (Vo-) gelstein et al.) 2015). Their method, like ours, was based on a continuous relaxation of the problem, but it approximated the weighted-inten intersectint score in eq. {I) by simpler correlation score whose gradient is casier to compute. Their ceiling suggests the limitation of strategy that optimizes approximation to the weighted-inntersectoon score rather than eq. [ itself.
Overall the performances of these competing methods serve to reinforce the essential components of our approach. First and foremost to our success was the alternation of continuous and diserete-combinattraal methods for search. But the alternating search only unlocked the potential for higher-scoring matches; it required further effort find these matches in efficient. manner. Other essential components of our approach include the optimized routines in Algorithm | for evaluating swaps and computing gradients, the heuristic in eqs. 17] for fast preconditioning in the linear assignment problem, and finally the optimizations described in section 4.2 for the last iotas of improvement.
4.4 Other related work
There a large literature on continuous relaxations for graph-matching problems. We briefly mention few other well-known approaches and discuss their suitability for the VNC matching challenge. Gold & Rangarajan (1996) investigated graduated-assignnent algorithm that combines softmax operations,
12

---

Published in Transactions on Machine Learning Research (01/2026)
Sinkhorn rescalings, and an outer annealing procedure to optimize over doubly stochastic matrices and permutation matrices. Their framework can be applied to general quadratic assignment problems, but the softmax computations can be expensive for large dense matrices. More recently, [uu et al. (2019) studied how to align graphs by defining a Gromov- Wasserstein discrepancy and minimizing the non-convex loss
L(P) -Ag i5ki
(21)
where P is doubly stochastic. They minimize the loss in eq. 21 by a proximal gradient method; specif- ically they use the Sinkhorn-Knopp algorithm to solve a sequence of convex (linearized and regularized) subproblems, and they develop a recursive, divide-and-conquer procedure for larger graphs. They obtain state-of-the-art results on these problems, but they also report that the proximal-gradien method can be sensitive to the choice of regularization hyperparameter and require many iterations in large graphs.
Many authors have studied graph-matching problems for the special case of symmetric graphs with least- squares loss functions. There are strategies in this setting that exploit the simpler choice of loss function as well as the undirected structure of the graphs. Most notably, in this setting the continuous relaxation to doubly stochastic matrices yields a conver optimization with loss
L(P) |AP-
(22)
Zaslavskiy et al. (2099) observed that the best-performing doubly stochastic matrices for this loss function do not project to the best rest-performing permutation matrices; this is the same difficulty that we observed in Section 3.2 To find better projections, they use solutions from the convex relaxation to initialize a path-following algorithm that solves a sequence of convex-concave programs. In later work. Lu et al. (2016) investigated a fast projected fixed-point. algorithm for these types of graph-matching problems. They obtain significant speedups by avoiding the bottleneck of Hungarian algorithms on large graphs; this is the same bottleneck that we addressed via the heuristics in section 3.3 More rocently, (Hermanns et al. 2023) pursued altogether different strategy that lifts the problem of node alignment to the more general problem of aligning functions on graphs. Their algorithm starts by constructing graph Laplacians from the adjacency matrices A and B and finding an orthogonal matrix that aligns the bases defined by their leading eigenvectors. It then solves a least-squares problem to compute a mapping matrix between time- panaeeaaratttzzed heat kernels and finally obtains a permutation from this mapping matrix by solving a linear assignment problem.
Our approach in this paper borrows elements from many of these approaches (e.g., continuous relaxations, convex subproblems, perfect matchings). As mentioned previously, though, the graphs in the VNC matching challenge are asymmetric as well as substantially larger (with millions of edges) than previous benchmarks. For the best results, the optimizations must also be tailored to the weighted intersection score in eq.
5 Discussion
In this paper we have described the ACODC optimizations behind the winning solution to the VNC Matching Challenge. The graphs in this challenge were large enough to foil exhaustive methods, but small enough to experiment with many different approaches on a modestly equipped computer. The highest-scoring solution was obtained by combining contimuous relaxations, additive and multiplicative updates, bespoke graph decompositions, and higher-order swaps. But most of the work was done by alternating simple (but aggressively optimized) methods for continuous and discrete combinatorial search and exploiting the particular structure of the srighteddintersecttion score in eq.
We mention several directions for future work. First, not all of the methods in this paper scale gracefully to larger graphs with hundreds of thousands of nodes. For such graphs, it seems necessary to develop divide- and-conquer hoth that do not require the storage of dense n x n matrices where n > 1 Second, we expect the linear assignment problem in eq. (9) to remain a crucial subroutine for higher-order assignment problems (or at least for any problem whose score function can be lincarized). We need to understand better why certain heuristics, such as the preconditioner in Section 3.3, lead to faster solutions, and then perhaps we can use this understanding to develop even faster approaches. Third, the winning solution to
13

---

Published in Transactions on Machine Learning Research (01/2026)
the VNC matching challenge was implemented in MATLAB, relatively high-level programming language, but it is surely possible to produce faster implementations that are better at exploiting sparsity, managing high-speed memory, and harnessing GPUs. Finally, the challenge was focused on connectomic graphs that are highly structured and biologically related. While our experiments with perturbed edge weights suggest that ACBDC is robust. lo moderate noise, remains to study the algorithm systematically across different noise models and graph familics.
Our work also provides lessons beyond the specific problem of graph matching considered here. One of the goals of the challenge was to determine if the graph structure of the VNC connectomes sufficed by itself to derive a high-scoring match. For this reason, the teams were not provided with auxiliary node features for cach neuron (e.g,, cell type, left/right hemisphere), let alone training examples of fully or partially matched graphs. But the methods in this paper could potentially be integrated into graph- matching frameworks where node features and/or labeled examples are available for richer forms of graph-based learning (Li et al., 2019 Haller
ct al. 2022 Zhou et al. 2023 Ramachandran et al. 2024). Even more generally, the alternating strategy explored here could be applied to a broader class of large-scale problems in combinatorial optimization. Many problems in discrete optimization and structured prediction admit continuous relaxations where gradient- based methods may converge to interior-point solutions. For such problems, our results suggest that it can be much more effective to alternate between discrete and contintous approaches rather than to pursue these individual approaches in isolation.
Acknowledgements
The authors thank the anonymous reviewers of this mamuscript for many useful pointers and suggestions. DL and LS are grateful to Sebastian Seung for introducing us to this problem. DL also acknowledges support by the Institute of Information & Communications Technology Planning & Evaluation (ITTP) grant by the Korean MSIT (No. R0S-002-004578822, National AI Research Lab Project). AM, one of the organizers of the FlyWire VNC Matching Challenge, joined this work at the invitation of DL and LS after the conclusion of the challenge. DL and LS developed the methods described here, while the challenge data, evaluation procedures, and results were fixed prior to this collaboration. The authors are also grateful to Mala Murthy and Amy Sterling for their part in organizing the concluding workshop in March 2025 at Princeton University and to the other teams in the challenge who shared their results at this workshop.
References
A. S. Bates, J. S. Phelps, M. Kim, H. H. Yang, A. Matsliah, Z. Ajabi, E. Perlman, K. M. Delgado, M. A. M. Osman, C. K. Salmon, J. Gager, B. Silverman, S. Renauld, M. F. Collie, J. Fan, D. A. Pacheco, Y. Zhao, J. Patel, W. Zhang, L. Serratosa- Capiteiiil,, R. J. V. Roberts, E. J. Munnelly, N. Griggs, H. Lang- lcy, B. Moya-Llamas, R. T. Maloncy, S.-C. Yu, A. R. Sterling, M. Sorck, K. Kruk, N. Scrafctinidis, S. Dhawan, T. Stürner, F. Klemm, P. Brooks, E. Lesser, J. M. Jones, S. E. Pierce- Lundgre,n S.-Y. Lee, Y. Luo, A. P. Cook, T. H. McKim, E. C. Kophs, T. Falt, A. M. Negrón-Morales, A. Burke, J. Heb- ditch, K. P. Willie, R. Willic, S. Popovych, N. Kemnitz, D. Th, K. Leo, R. Lu, A. Halageri, J. A. Bac, B. Jourdan, G. Schwartzman, D. D. Demarest, E. Behnke, D. Bland, A. Kristiansen, J. Skelton, T. Stocks, D. Garner, F. Salman, K. C. Daly, A. Hernandez, S. Kumar, The BANC-Fly Wire Consortium, S. Dorken- wald, F. Collman, M. P. Suver, L. M. Fenk, M. J. Pankratz, G. S.X.E. Jefferis, K. Eichler, A. M. Seeds, S. Hampel, S. Agrawal, M. Zandawala, T. Macrina, D.-Y. Adjavon, J. Funke, J. C. Tuthill, A. Azevedo, H. S. Seung, B. L. de Bivort, M. Murthy, J. Drugowilsch, R. I. Wilson, and W.-C A. Lee. Distributed control circuits across brain-and-cord connectome. bio Rziv, 2025. doi: 10. 201101120220 0025.007.31666777 httpp://www.
URL
www.ww.w..ii...mmmmmo www.://wwww....gooeeeeeeeeeeeeee ottp:///tteeeeeeeaaa//////////// 07.
L. Chen, J. T. Vogelstein, V. Lyzinski, and C. E. Priebe. A joint graph inference case study: the C. elegans chemical and electrical connectomes. Worm, 5(2)xe1140041, 2016.
D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. International Journal of Pallern Recogrition and Artificial Intelligence,
2004.
14

---

Published in Transactions on Machine Learning Research (01/2026)
M. Cuturi, O. Teboul, and J.-P. Vert. Differentiable ranking and sorting using optimal transport. In Advances in Neural Information Processing Systems 32, pp. 6858 6868, 2019.
S. Dorkenwald, A. Matsliah, A. Sterling, Schlegel, S.-C. Yu, C. E. McKellar, A. Lin, M. Costa, K. Fichler, Y. Yin, W. Silversmith, C. Schneider-Mizell C. S. Jordan, D. Brittain, A. Halageri, K. Kuehner, O. Ogedengbe, R. Morey, J. Gager, K. Kruk, E. Perlman, R. Yang, D. Deutsch, D. Bland, M. Sorek, R. Lu, T. Macrina, K. Lee, J. A. Bae, S. Mu, B. Nehoran, E. Mitchell, S. Popovych, J. Wu, Z. Jia, M. A. Castro, N. Kemnitz, D. Th, A. S. Bates, N. Eckstein, J. Funke, F. Collman, D. D. Bock, G. S. X. E. Jefferis, H. Scung, M. Murthy, and The FlyWire Consortium. Neuronal wiring diagram of an adult brain. Nature, 634:124 138, 2024.
H. Dröge, Z. Lähner, Y. Bahat, O. Martorell Nadal, F. Heide, and M. Moeller. Kissing to find a match: Efficient low-rank pernutation representation. In Advances in Neural Information Processing Systems 36, pp. 48459 48471, 2023.
I. S. Duff and J. Koster. On algorithms for permuting large entries to the diagonal of a sparse matrix. STAM Journal on Matrir Analysis and Applications, 22(4):973 996, 2001.
J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248 264, 1972.
M. Frank and Wolfe. An algorithm for quadratic programming. Naval Research Logisties Quarterly. 3(1-2):95 110, 1956.
S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on Paltern Analysis and Machine Intelligence, 18:4:377 388, 1996.
A. Grover, E. Wang, A. Zweig, and S. Ermon. Stochastic optimization of sorting networks via continuous relaxations. In Proceedings of the 7th International Conference on Learning Represenlations (ICLR-2019), 2019.
S. Haller, L. Feineis, L. Hutschenreiter, F. Bernard, C. Rother, D. Kainmüller, P. Swoboda, and B. Savchyn- skyy, A comparative study of graph matching algorithms in computer vision. In Proceedings of the 1 17th European Conference on Computer Vision (ECCV-2022), pp. 636-653, 2022.
J. Hermanns, S. Konstantinos, A. Tsitsulin, M. Munkhoeva, A. F. Kyster, S. D. Nielsen, A. Bronstein, D. Mottin, and P. Karras. GRASP: Graph aligmment through spectral signatures. ACM Transactions on Knowledge Discovery from Dala 17(4), Article 50, 2023.
E. Koblentz. Fruit fly research led NJIT scientists and Edison teens to better AI habits supercomputers. 2025. Accessed: 2025-06-11.
https://davidbadde.
H. W. Kuhn. The Hungarian method for the assignment problem. Navol Research Logistics Quarterly, 2: 83-97, 1955.
T. Lázaro, R. Guimerà, and M. Pardo. Probabilistic alignment of multiple networks. Nature Commu- nications, 16, Article 3949, 2025.
D. D. Lee and H. S. Seung. Learning the parts of objects by non- non-negative matrix factorization. Nature, 401: 788-791, 1999.
Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. In Proceedings of the 36th International Conference on Machine Learning (ICML-2019), pp. 3835 3845, 2019.
Y. Lu, K. Huang, and C.-L. Liu. A fast projected fixed-point algorithm for large graph matching. Pattern Recognition, 60:C:971-9928 2016.
N. Mamano and W. B. Hayes. Simulated annealing far outperforms many other search algorithms for biological network alignment. Bioinformatics, 33(14):2156 2164, 2017.
15

---

Published in Transactions on Machine Learning Research (01/2026)
G. E. Mena, D. Belanger, S. Linderman, and J. Snock. Learning latent permutations with Gumbel-Sinkhom wetworks. In Proceedings of the 6th. International Conference on Learning Represenlations (ICI.R-008)) 2018.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In JCML 2020 Workshop Graph Representation Learning and Begond (GRL+-2020), 2020.
J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Malhemalics, 5(1):32 38, 1957.
S. Prillo and J. M. Eisenschlos. SoftSort: a contimuous relaxation for the argsort operator. In Proceedings of the 37th International Conference on Machine Learning (ICMI-2020), pp. 7793-7802, 2020.
A. Ramachandran, V. Raj, I. Roy, S. Chakrabarti, and A. De. Iteratively refined early interaction alignment for subgraph matching based graph retrieval. In Adoances in Neural Information Processing Systems 87, pp. 77593-77629, 2024.
R. Santa Cruz, B. Fernando, A. Cherian, and S. Gould. Visual permutation learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31112):3100-3114 2019.
L. Saul and F. Pereira. Aggregate and mixed-order markov models for statistical language processing. In Proceedings of the 2nd Conference Empirical Methods in Natural Language Processing, pp. 81-89, 1997.
Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21:343 348, 1967.
S.-Y. Takemura, A. Nern, D. B. Chklovski,, L. K. Scheffer, G. M. Rubin, and I. A. Meinertzhagen. The comprehensive connectome of a neural substrate for 'on' motion detection in Drosophila. eLife, 6:e24394, apr 2017. ISSN 2050-084X. doi: 10.7554/eL 24394. URL
11111..555//effeee. 24394
N. Tomizawa. On some techniques useful for solution of transportation network problems. Networks, 1(2): 173 194, 1971.
L. R. Varshney, B. L. Chen, E. Paniagua, D. H. Hall, and D. B. Chklovskii. Structural properties of the caenorhabditis elegans neuronal network. PLoS Computational Biology, ((2):c1001066, 2011.
J. T. Vogelstein, J. M. Conroy, Lyzinski, L. J. Podrazik, S. G. Kratzer, E. T. Harley, E. Fishkind, R. Vogelstein, and C. E. Priebe. Fast approximate quadratic programming for graph matching. PLOS ONE, 10(4):1-17, 2015.
Xu, D. Luo, and L. Carin. Scalable Gromov-Wart Wasserstein learning for graph partitioning and matching. In Advances Neural Information Processing Systems 32, pp. 3046-3056, 2019.
M. Zaslavskiy, F. Bach, and J.-P. Vert. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31:12:2227 2242, 2009.
Y. Zhou, R. Jia, H. Lin, H. Quan, Y. Zhao, and X. Lyu. Improving graph matching with positional reconstruction encoder-decoder network. In Advances in Neural Information Processing Systems 36, pp. 34557-34569, 2023.
A Preconditioner for perfect matching
In this appendix we provide further details on the method used to compute perfect matchings in section 3.3 To recall, a perfect matching is computed prior to each line search in order to find the permutation matrix Q. with the largest projection onto the gradient (S((P): see eq. OD. In this calculation,
more convenient
consider how Qe is changed relative to the current permutation matrix II, in eq. [13). To do so, we re-index the rows and columns of the gradient and equivalently seek the permutation whose corresponding matrix
16

---

Published in Transactions on Machine Learning Research (01/2026)
has the largest projection onto the matrix A VS(P) II as in eq. (16). Finally use internal matlab routine to compute the perfect matching 4, as in eq. 18 This routine can be called most simply
w = matlab interninn www.pppp...rreehhccccnninngggee.
(23)
but for the graphs arising from the VNC Matching Challenge, it takes roughly 15 minutes to compute each perfect matching in this way. In what follows, we describe two heuristics that we investigated to accelerate these matchings.
The hcuristics stem from the observation that perfect matchings not affected by adding constant rows columns to the cost matrix that appears as argument in eq- 23 In practice, we found that the matching routine executed much more quickly if the rows and columns of the nonnegative matrix A were shifted to create strongly negative entries off the diagonal. We investigated two such shifts one that has the effect of zeroing the diagonal elements, and another that has the effect (in general) of decreasing the diagonal elements but not necessarily zeroing them. For the diagonal-zerving preconditioner, we perform the shift.
Agj t As - (Aa + AAg);
(24)
while for the diagonal-decrassin preconditioner, we perform the shift
Aij f Aig I(Ax + Akg).
(25)
lepti
Note that eq. (25 is an equivalent way of writing eq. (17 in section 3.3 and it has no effect if the matrix A is purely diagonal. Since (.,))) is a nonnegative matrix, so is the matrix A in eq- (16.. and as a result, both these shifts work to create strongly negative entrics off the diagonal. Such a pattern suggests that the perfect match close to an identity permutation, and in practice this was found to accelerate the internal MATLAB routine by significant amount.
Fig. shows the speedups provided by these preconditioners when they were used for the VNC matching challenge roughly 5x for the diagonal-zeroing shift in eq. (24), and roughly 50x for the diagonal-decreasin shift in eq. (25 In particular, the latter reduced the time required for each perfect matching from 10-15 minutes to 10-20 seconds. In theory, these preconditioners should not affect the results returned by the perfect matching routine, and for small problems, we observed this to be true. However, for the large graphs in the VNC matching challenge, the routine did often return matches that were very slightly different for different preconditioners.
B Cost and gradient computation for multiplicative updates
In this appendix we describe how to compute the alignment score in eq. (2) and its gradient in eq. 4 more efficiently for dense doubly stochastic matrices P. Our key trick is to exploit the fact that the connectome weights are quantized. In particular, each nonzero weight records positive number of synapses, and therefore not only are the elements of A and B quantized, but so are the possible values of (Aij, Ba) in eq. Let Q = {40. fI, } denote the set of these quantized values, with do = 0 and < g and let O denote the step function defined by 0(2)=
=1 if 2 > 0 and ((z)=0 otherwise. Then follows that
M-1
min( Aig. BB)
Σ m=
O(Au- gm. -m (Bat (m)) (gm+1 - (m)
(26)
for all connectome weights Aij and Bu- Note how this identity expresses the minimum as sum over M components. We now use this identity to more efficiently compute the score in eq. (2) and the gradient in eq. 44. To do so, for each interval (fm, 1m+1), we define connectome components with weights
(m) OAAi - qm) v vm+ Jos
(27)
1j
B (m) O(B; am) / am-1 Jm.
(28)
17

---

Published in Transactions on Machine Learning Research (01/2026)
perfect matching with different preconditioners
40
diagonal-decreasing
30
diagonal-zeroing
none
20
10
0
10
10
103
seconds
Figure 3: Effect of different preconditioners on the time required for MATLAB's internal graph routine for perfect matching. The figure shows histograms for each preconditioner; each histogram profiles the execution times of the perfect matching routine throughout the optimization in Fig. [ (right). The diagonal-zeroing preconditioner in eq. 24 leads to roughly 5x speedup, while the dingonal-ddereasingg preconditioner in
eqs. (17 and 25 leads to roughly 50x speedup.
Note that each connectome component is a sparse matrix in its own right, one that at least as sparse as the connectome from which it is derived. Finally, combining eqs. 26 28 we rewrite the score in eq. (2) as
S(P) Σ min(Aij: Pu Ajkl
(29)
(m) B(m)) ki
Psx Pa
(30)
Aj
m
(A(m))) (PBim)
trace
(31)
Note that this final expression for the score in eq. 31 can computed O(Mn²) as opposed to On This savings is significant when M < n, and it is also inherited by the computation of the gradient. For the VNC matching challenge, there weights of the male and female fruit fly. With this savings, and using GPU, it takes less than 2 minutes to compute the gradient of eq. (31 and perform each multiplicative update in eq. 20
M=617 graph components that arise from the nonzero connectome
18


Reviews:
[{"review_id": "eQHlj3juHX", "reviewer": "Reviewer_VkRf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes the winning strategy of the Flywire Ventral Nerve Cord Matching Challenge. The proposed approach, called AC+DC, is based on alternating combinatorial and continuous optimization procedures. In essence, the problem consists of graph matching. AC+DC employs a local search based on pairwise swaps (i.e., pairs of indices in a permutation) and a relaxed formulation of the problem, in which doubly stochastic matrices naturally arise. The combination of these procedures led to the winning solution. The paper also provides a detailed discussion of the computational and algorithmic aspects underlying the method’s success.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is entirely focused on the specific problem of the VNC Matching Challenge, demonstrating that the proposed solution achieves top performance in this setting. Moreover, the paper is clearly written and provides comprehensive implementation details, including pseudocode.", "audience_yn": "Yes", "audience_explanation": "I believe that members of the Graph Machine Learning community may find the proposed solution for graph matching particularly relevant. In particular, graph matching has become increasingly important for tasks such as graph similarity computation, cross-graph alignment, and subgraph retrieval, which are central to applications in molecule analysis, vision, and relational reasoning (e.g., see [1,2,3]).\n\n[1] Improving Graph Matching with Positional Reconstruction Encoder-Decoder Network, NeurIPS 2023.\n\n[2] Graph Matching Networks for Learning the Similarity of Graph Structured Objects, ICML 2019.\n\n[3] Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval, NeurIPS 2024.", "requested_changes": "I believe the paper would benefit from:\n\n- Discussing the broader relevance to the ML community. It would be valuable to elaborate on how the ideas behind AC+DC could inform or inspire future developments in machine learning;\n\n- Clarifying the motivation for the heuristics used to accelerate the perfectMatching routine. The rationale behind this component was somewhat unclear. Was it primarily introduced to avoid trivial identity permutations? How did the authors come to Eqs (16)-(19)?\n\n- Including ablation studies to demonstrate the impact of the main design choices—possibly on smaller subproblems. Overall, I missed additional experiments that could justify the specific architectural and algorithmic decisions behind AC+DC, especially when compared to simpler or “vanilla” baselines;\n\n- Expanding the discussion of related work. It remains unclear which prior methods have explored similar alternating combinatorial–continuous optimization strategies. A more detailed discussion would help contextualize the contribution and clarify the novelty of the proposed approach.", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WA1SR0zeUM", "reviewer": "Reviewer_1eku", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an approach for solving a graph matching problem. It focuses in particular on a problem that was given as a research competition, consisting in aligning the connectomes of a neural structure (ventral nerve cord) between two flies (male and female). The challenge had 18k nodes in both graphs.\n\nThe authors propose the approach that won the challenge. This approach relies on alternating greedy permutations in the matching matrix (as a discrete optim problem) and optimizing a continuous relaxation of the matching matrix (in the space of doubly stochastic matrices).\n\nThe paper's claims is that their approach provides good performances in a short time", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes, I do believe that the paper provides clear and accurate evidence of their claims. The code is provided, and I mention here that I did not run the code to verify it.\n\nThe descriptions of the approach are clearly detailed, allowing to understand the processes and the grounds for decision. The ablation studies (fig 1) isolating both components also offers relevant insight into the method's motivation.", "audience_yn": "Yes", "audience_explanation": "Yes, I believe that the winning solution to a graph matching competition anchored in biologic data is of interest to the respective communities of the methods (graph learning/graph matching) and applications (neuronal biologists).", "requested_changes": "The scope and novelty of the paper are somewhat limited. It applies existing techniques to a single use-case, which provides no guarantee of generalization of the method with regards to other scenarios in the broad world of graph matching. I believe that comparing the approach to existing techniques on existing benchmarks would be very beneficial, as the community could benefit from a more exhaustive study of the strengths and weaknesses of the method. Please note that I fully acknowledge that this is not ground for rejection of this paper.\n\nMoreover, the comparison to baselines is shallow, and there is a lack of comparison to other graph matching methods. The leaderboard of the competition is relevant in proving the method is performant, but a few issues remain:\n* D. A. Bader, H. A. Sriram, S. Chinthalapudi, and Z. Du obtain very close results (albeit after the end of the competition). It would be relevant to discuss what method that team used and compare it to the ACDC approoach\n* The runtime of the approach is evoked several time throughout the paper, but no comparison is offered with other methods from the leaderboard. How quick/slow is the Bader approach, for instance?\n* The lack of related works is hindering a good situation of the approach in the larger scope. It is in my opinion necessary that other methods for graph matching be discussed and compared, especially those that were used during that competition and that achieved a good score. This would allow to understand the strengths of ACDC much better, and understand the generalization possibilities.", "broader_impact_concerns": "No concern.", "additional_comments": "I believe that this is an overall well written paper, with clear and detailed presentation of the method. I believe that the method in question, ACDC, is of interest to the community and proved its effectiveness in the FlyWire challenge. The components of the method are not novel (greedy swaps + Frank-Wolfe), but the paper succeeds in demonstrating that using them in an alternating fashion works better than each of them individually.\n\nMy main concern is the lack of comparison to other methods in terms of complexity/runtime, both methods used by other competitors but also more general methods for graph matching, since it is a well studied problem, even on large graphs. Moreover, it would be of great interest to the community to study the power of the method outside of the single, instanced problem posed by the competition. Analysis of the performance on a wider scope of settings could show the strengths and weaknessess of the method much further.", "extra_scores": {}, "extra_text": {}}, {"review_id": "dWbFgKbZ1k", "reviewer": "Reviewer_d4Zf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "# Summary\n\nThis paper presents the winning solution to the Flywire Ventral Nerve Cord Matching Challenge, which involved aligning connectomes of male and female fruit flies.  The authors detail two main optimization components for graph matching between large fly connectomes: (1) a greedy combinatorial permutation search, and (2) a continuous relaxation using Frank-Wolfe optimization over doubly stochastic matrices, enhanced by a preconditioning heuristic. \n\n# Pros\n* Addresses a real, large-scale problem with practical constraints\n* Clear algorithmic exposition with detailed complexity analysis\n* Novel combination of existing techniques yielding superior performance\n\n# Cons\n* Limited theoretical analysis of why the alternating approach works\n* Some ad-hoc heuristics (especially the preconditioning) lack formal justification.\n* Scalability concerns for much larger graphs are not thoroughly addressed.\n* No direct, systematic comparisons with state-of-the-art graph matching algorithms", "claims_and_evidence_yn": "No", "claims_explanation": "Please provide more experiments to support the proposed model.", "audience_yn": "Yes", "audience_explanation": "The emphasis on achieving strong results with modest computational resources aligns with practical ML concerns about accessibility and efficiency.", "requested_changes": "* Could the authors provide quantitative benchmarks or ablations showing the acceleration benefit from their preconditioning heuristic relative to standard assignment solvers and/or state-of-the-art alternatives?\n* How would the approach behave under different forms of graph noise, weight quantization levels, or in settings where the input graphs are less similar?", "broader_impact_concerns": "The work focuses on computational methods for biological network analysis, which is generally beneficial for scientific understanding. The specific application to fruit fly connectomes is purely for scientific research.", "additional_comments": "N/A", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)