Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.
翻译:组合优化是许多现实世界问题的核心。 特别是自图形神经网络( GNNS) 崛起以来, 深层学习界一直在开发解决方案解决NP- 硬性问题的解决方案。 但是, 复制这些出版物的结果证明是困难的。 我们做了三项贡献。 首先, 我们为NP- 硬最大独立Set 问题提供了一个开放源基准套件, 包括加权和不加权的变体。 该套件为各种最先进的传统和机器学习型解决方案提供了统一的界面。 其次, 我们使用基准套件, 对李等人的流行型树搜索算法进行深入分析。 [NeurIPS 2018], 复制这些出版物的结果证明是困难的。 我们通过重新应用它们的算法, 重点是代码质量和外延性。 我们显示, 树搜索中使用的图形变异网络无法学习解决方案的有意义的表现, 并且事实上可以被随机值所取代。 相反, 树类搜索基于原始的树类搜索方法, 而不是像图表分析系统一样, 。 我们通过原始的更快速的解算法分析, 。