Neural Bipartite Matching
This addresses the problem of extending neural execution beyond simple algorithms for researchers in algorithm learning, though it is incremental as it adapts existing methods to a more complex case.
The paper tackles the challenge of applying neural execution to complex algorithms like maximum bipartite matching, which is reduced to a flow problem and solved using Ford-Fulkerson, achieving optimal matching almost 100% of the time.
Graph neural networks (GNNs) have found application for learning in the space of algorithms. However, the algorithms chosen by existing research (sorting, Breadth-First search, shortest path finding, etc.) usually align perfectly with a standard GNN architecture. This report describes how neural execution is applied to a complex algorithm, such as finding maximum bipartite matching by reducing it to a flow problem and using Ford-Fulkerson to find the maximum flow. This is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.