Neural Bipartite Matching

Graph neural networks (GNNs) have found application Performing the reasoning is achieved via neural execution, for learning in the space of algorithms. in a similar fashion to Veličković et al. (2020). GNNs have However, the algorithms chosen by existing research been both empirically (Veličković et al., 2020) and theoretically (sorting, Breadth-First search, shortest path (Xu et al., 2020) shown to be applicable to algorithmic finding, etc.) usually align perfectly with a standard tasks on graphs, strongly generalising on inputs of sizes GNN architecture. This report describes much larger than trained on. However, these algorithms how neural execution is applied to a complex algorithm, rely on a locally contained and fixed dataflow which aligns such as finding maximum bipartite matching perfectly with a standard GNN architecture, making them by reducing it to a flow problem and using easy to model with GNNs (c.f.