Recently, there has been much work on the design of general heuristics for
graph-based, combinatorial optimization problems via the incorporation of Graph
Neural Networks (GNNs) to learn distribution-specific solution
structures.However, there is a lack of consistency in the evaluation of these
heuristics, in terms of the baselines and instances chosen, which makes it
difficult to assess the relative performance of the algorithms. In this paper,
we propose an open-source benchmark suite MaxCut-Bench dedicated to the NP-hard
Maximum Cut problem in both its weighted and unweighted variants, based on a
careful selection of instances curated from diverse graph datasets. The suite
offers a unified interface to various heuristics, both traditional and machine
learning-based. Next, we use the benchmark in an attempt to systematically
corroborate or reproduce the results of several, popular learning-based
approaches, including S2V-DQN [31], ECO-DQN [4], among others, in terms of
three dimensions: objective value, generalization, and scalability. Our
empirical results show that several of the learned heuristics fail to
outperform a naive greedy algorithm, and that only one of them consistently
outperforms Tabu Search, a simple, general heuristic based upon local search.
Furthermore, we find that the performance of ECO-DQN remains the same or is
improved if the GNN is replaced by a simple linear regression on a subset of
the features that are related to Tabu Search. Code, data, and pretrained models
are available at: https://github.com/ankurnath/MaxCut-Bench.

设计适用于基于图的组合优化问题的通用启发式方法，通过引入图神经网络 (GNN) 来学习分布特定的解决方案结构。通过提出开源基准测试套件 MaxCut-Bench，对多个学习方法进行系统验证，并发现某些学习启发式方法无法胜过贪婪算法，只有一种方法在各个维度上具有一致的优越性能。