What's Wrong with Deep Learning in Tree Search for Combinatorial
  Optimization
  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.
