论文标题
ERDOS神经：一个无监督的学习框架，用于图形上的组合优化
Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
论文作者
论文摘要
众所周知，组合优化问题对于神经网络来说是具有挑战性的，尤其是在没有标记实例的情况下。这项工作为图表上的CO问题提供了无监督的学习框架，可以提供不可或缺的认证质量解决方案。受Erdos的概率方法的启发，我们使用神经网络来参数集合概率分布。至关重要的是，我们表明，当网络优化时，W.R.T.适当选择的损失，学习的分布包含具有控制概率的低成本积分解决方案，遵守组合问题的约束。然后将存在的概率证明被取代以解码所需的解决方案。我们证明了这种方法的功效，以获取最大集团问题并执行本地图聚类的有效解决方案。我们的方法在实际数据集和合成硬实例上都取得了竞争成果。
Combinatorial optimization problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem. The probabilistic proof of existence is then derandomized to decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.
