Fri May 29 09:02:12 UTC 2020

test phlog post 5

--

Graph  neural networks 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.) are usually trivial, from the viewpoint  of  a  theoretical
computer scientist. 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-Fulker-
son to find the maximum flow. This is achieved via neural  execu-
tion  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.