神经二部匹配（CS ML）---蔡秋纯

图神经网络已经发现在算法空间学习中的应用。但是，从理论计算机科学家的角度来看，现有研究选择的算法（排序，广度优先搜索，最短路径查找等）通常是微不足道的。该报告描述了如何将神经执行应用于复杂算法，例如通过将最大二部匹配简化为流量问题并使用Ford-Fulkerson查找最大流量来找到最大二部匹配。 这仅通过基于单个GNN生成的特征的神经执行来实现。 评估显示出具有很强的概括性结果，其中网络几乎100％的时间都实现了最佳匹配。

原文标题：Neural Bipartite Matching

原文：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-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.

原文作者：Dobrik Georgiev, Pietro Lió

原文地址：https://arxiv.org/abs/2005.11304