What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization
Authors: Maximilian Böther
Otto Kißig
Martin Taraz
Sarel Cohen
Karen Seidel
Tobias Friedrich
Venue: ICLR 2022 Poster (2022)
Keywords: deep learning
combinatorial optimization
maximum independent set

Abstract: 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.

Published as a conference paper at ICLR 2022
WHAT'S WRONG WITH DEEP LEARNING IN TREE SEARCH FOR COMBINATORIAL OPTIMIZATION
Maximilian Böther; Otto Kißigg& & Martin Taraz
Sarel Cohen
Hasso Plattner Institute, University of Potsdam
The Academic College of Tel Aviv-Yaffo, Israel
Karen Seidel Department of Mathematics, University of Potsdam
Tobias Friedrich
Hasso Plattner Institute, University of Potsdam
ABSTRACT
Combinatorial optimization lies at the core of many real-world problems. Espe- cially 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 mooblem-speciffe solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present open-source benchmark suite for the NP-hard MAXIMUM INDEPENDENT SET problem, in both its weighted and unweighted variants. The suite offers a uni- fied interface to various state-of- to-the--rt traditional and machine learning-base solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li al. NeurlPS 2018], testing various configurations on small and large synthetic and real-world graphs. By e--mmplementin 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 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.
INTRODUCTION
Various communities have been dealing with the question of how to efficiently solve combinatorial problems, which frequently are NP-hard. These problems often have real-world applications in industry, for instance in staff assignment (Peters et al. 2019), supply chain optimization (Eskandarpour et al. 2015), and traffic optimization (Böther et al. 2021).
In recent years, also the machine learning community has been engaged in solving combinatorial problems. One reason that learning-based approaches are interesting, even though commercial general purpose solvers like Gurobi (Gurobi Optimization LLC 2021] exist, is that might be able to learn the solution structure of a family of instances, e.g., similar vehicle routing problems instances are solved everyday (Khalil together with an algorithmic component to find reasible solutions quickly; we outline in SSection 2. the designs that past works have used.
2017; Dong et al. 2021). Such trained model can be used
However, these statistics-basse techniques have the well-known problem of reproducibility (Ioannidis] 2005) [aker 2016), which is a particular problem in machine learning research with untested or even unpublished code and data sets (Kapoor & Narayanan] 2020 Ding et al., 2020), and is the
"Correspondence maxi @boether.de

---

Published as a conference paper at ICLR 2022
reason for the interest in initiatives such Papers With Code and the ReScience Journa Keeping the importance of reproducibility in mind, we evaluate various machine learning approaches for combinatorial optimization, and compare them to traditional solvers. We focus on the MAXIMUM (WEIGHTED) INDEPENDENT SET problem (Miller & Muller 1960, Karp 1972), as the previous
works analyze have centered around variants of this problem. Overall, contribute the following.
We provide an open-source, extensible benchmark suite for MAXIMUM (WEIGHTED) INDEPENDENT SET solvers. The software currently supports five state-of-the-ar solvers. INTEL-TREESEARGA (Li, Chen, and Koltun 2018). GUROBI (Gurobi Optimization LLC, 202ID, KAMIS (Lamm et al.] 2017; Hespe et al.) 2019; [Lamm et al., 2019). LEARNING WHIAT To DEFER (Ahn, Seo, and Shin 2020), and
Our DGL- TREESEARCH is a modern re-implementation of the INTEL-TREESTE TREESEARCE implemented in PyTorch (Paszke et al., 2019) and the Deep Graph Library (Wang et al. 2019), with a focus on clean, readable code, as well as performance, and it fixes various issues of the original code. Our evaluation suite lays the ground for further research hard combinatorial (graph) problems and aims at providing a fair and comparable environment for further evaluations.
Using our immlemeenttiionn of the tree search. we propose and analyze additional tech- niques aiming at improving the guided search. Employing the benchmark suite, we conduct an exhaustive analysis of various configurations of the tree search algorithms, showing that the results of the highly-cited INTEL- TREESERRCEE approach are not reproducible, neither with the original code nor with our re-implementation. When exploring the design space further, we show that the various techniques used by the tree search algorithm to improve the results, like graph kernelization, are the reason for good performance, especially on hard data sets. In fact, replacing the GNN output with random values performs similar to using the trained network.
Having analyzed the configuration space, we compare the tree search approaches to the classical solvers like GUROBI and KAMIS, showing that problem-tailored solvers are often the superior approach. Without using techniques like graph reduction in the tree search, classical solvers are superior. The classical solvers show to be more efficient even when accessing these routines- - that have been implemented for the algorithmic solvers in the first place in the tree search. Last, we show that LEARNING WHAT To DEFER seems to be able to find good results very quickly, indicating that unsupervised reinforcement learning for combinatorial problems is promising direction for future research.
2 INDEPENDENT SET SOLVERS AND MACHINE LEARNING FOR COMBINATORIAL OPTIMIZATION
In this section, we formally introduce the MAXIMUM INDEPENDENT SET (MIS) problem well as the solvers included in our analysis, and discuss related work in the broader space of deep learning for combinatorial optimization. Given undirected graph G = (V, E), independent set is a set of vertices S C V for which for all vertices u, E S, (u, v) & E. For u E V. let w., be its weight, and let GG) be all independent sets of G. then the MAXIMUM WEIGHTED INDEPENDENT SET (MWIS) problem aims at determining arg maxseIs(G) Σves W.. The unweighted MIS problem is equivalent to the MWIS problem, where f.a. u E V, W. = 1. Both problems are strongly NP-complete (Garey & Johnson 1978). Next, we briefly explain the solvers that we use to find such MIS.
Gurobi. GUROBI is a commercial mathematical optimization solver. There are various ways of formulating the M(WIIS problem mathematically (Butenko 2003). In the main paper, we formulate the MWIS problem as the linear program above, and discuss other variants in Apppedixx D
KaMIS. KAMIS is an open-source solver tailored towards the MIS and MWIS problems. It offers support both for the unweighted case (Lamm et al. 2017: Hespe et al. 2019) as well as the weighted case (Lamm et al., 2019). employs graph kernelization and an optimized cranch-and-boure algorithm to efficiently find independent sets. Note that the algorithms and techniques differ between the weighted and unweighted cases. We use the code unmodified from the official repository
htttpss//paperswithcoo com/
https://github.ce com sruheMi 8/ KaM
2

---

Published as a conference paper at ICLR 2022
Intel-TreeSearch In their influential paper, [i et al. (2018) propose a guided tree search algorithm to find maximum independent sets of a graph. The idea is to train a graph convolutional network (GCN) (Kipf & Welling 2017), which assigns each vertex probability of belonging to the inde- pendent set, and then greedily and iteratively assign vertices to the set. They furthermore employ the reduction and local search algorithms by KAMIS speed up the computation. We use their published code which unfortunately is not runnable in its default state. We apply git patch to make the code runnable, enable further evaluation by collecting statistics, and add command-line flags for more fine- eme-grained control of the solver configuration. In [pppendixx CJ we give some details on possible complications with the original code. Because good knowledge of the algorithm is important to follow the remainder of this paper. we briefly describe the algorithm. A pseudocode description of the algorithm is found in Algorithm 1 The core element of the tree search a queue P of partial solutions S E {0, 1, 1 to the MIS problem, i.e., labelings of the graph at hand marking each vertex as either included in the MIS (1), excluded (0), or unlabeled (a decision is still to be made, L). To be a valid (partial) solution to the MIS problem, each element in the queue fulfills the constraint that no two adjacent vertices can both be included. Furthermore, all vertices adjacent to an included one must be excluded.
Given graph G = (V, F),, we start with an empty solution, i.e., f.a. E S. = In each step of the tree search, a partial labeling is popped from the queue, and the residual graph Gresidaal consisting only of the unlabeled vertices is constructed. Next, we obtain predefined number of probability maps, each of which contains a value for all vertices of the residual graph, posing the "probability of being in the MIS", by calling the trained GCN, which outputs its assignments from vertices to probabilities, i.e., GCN(G) E [0, V
From each of these probability maps, a new partial solution is derived as follows: The probabilities of the maps sorted in descending order. The vertex with the highest probability gets labeled as included, and all adjacent vertices as excluded. This step is repeated until we would have to label an already excluded vertex included, in which case we break, and add the partial solution to the queue. In case all vertices are labeled we obtained a full solution. This procedure is repeated for all probability maps. For further modifications of this algorithm (e.g., reduction), we refer to to/Appendix B
DGL-TreeSearch. Because the code provided by et al. (2018) might be difficult to read and maintain, and hence is prone errors in the evaluation, we re-implement the tree search using Py PyTorch (Paszke et al.) 2019) and the established Deep Graph I Library (Wang et al. (019). Our implementation aims at offering a more readable and modern implementation, which benefits from improvements in the two deep learning libraries during recent years. Furthermore, it fixes various issues of the original implementation that sometimes deviates from the paper. Additionally, we implement further techniques to improve the search, like queue pruning, and weighted selection of the next element, as well as multi-GPU functionality.
Learning What To Defer. We test LEARNING WHAT TO DEFER (LwD), unsupervised deep reinforcement bearning-basee solution introduced by Ahn et al. 2020). Their idea is similar to the tree search, as the algorithm iteratively assigns vertices to the independent set. However, this is not done using a supervised GCN, but instead by an unsupervised agent built upon the GraphS architecture (Hamilton et al. 2017) and trained by Proximal Policy Optimization (Schulman et al. 2017). There is no queue of partial solutions. We refer to the original paper for details on the algorithm. As their code" does not work with generic input, we patch their code.
Our open-source benchmarking suite iittegrates all these solvers in one easily accessible command- line interface using Anaconda (Anaconda Inc., 2020), with unified input and output format. We provide our code for and patch the other solvers on-demand. It handles the correct invocation of the solvers and allows to quickly run experiments on various solvers in different configurations.
and our GUROBI interface directly, and download, compile,
https://g/t wttp:iclooooo///eeeeeeee
A git patch is file transparently stating the changes we require to make the code compatible with our benchmarking suite.
"We use the term queue stay consistent with other works. However, P is not traditional LIFO queue, but a list (infinite-sized array).
ht http:////h.../..ooooooo/ooo//aaa what to defer
Repository: http:///ggtihha....////aaaaaaaaa
framework
3

---

Published as a conference paper at ICLR 2022
2.1
RELATED WORK
Al for Combinatorial Optimization. Research at the intersection of artificial intelligence and com- binatorial optimization is not limited to MIS. These methods differ in the problem they tackle, and how algorithmic components and learned components interact. The evolutionary computation com- munity, for example. has researched various NP-hard routing problems. like the VEHICLE ROUTING PROBLEM (Berger & Barkaoui 2003] PPotvin 2009) and the MULTIPLLE ROUTES problem (Böther al. 202T). nutshell, evolutionary optimization is an iterative improvement that not guided by a learned component, but instead tries to mutate and combine existing solutions randomly, in order to find better solutions. ML-based solvers often are variants of branch-and- such solvers partition the search space by some rule set; for ML-based solvers, the partition rules are not pre-defined, but given by a model that learned how to branch (Balcan et al.. 20188. The concrete algorithms differ in the model used, how they utilize the model to branch within the search space, and how the model is trained. For example, the INTEL- TREESEERRRRRRRR EARCH trains a GCN on pre-tabeled data, and expects from its guidance model a probability for each vertex that describes how likely it is that the vertex belongs to the MIS, and then greedily operates on these probabilities. In comparison to that, LWD instead models the branching process as an unsupervised agent that can choose vertices in a Markov Decision Process, that similarly to the tree search iteratively picks vertices, but for example allows to roll-back invalid solutions, instead of greedily pushing forward. This methodology applies to other combinatorial problems as well. For example. Kool et al. (2019) propose attention-based sateeer-eccode---rhieeeeee
solvers. In general,
as a model for solving TRAVELLING SALESMAN PROBLEM (TSP) instances, where the decoder iteratively outputs probabilties for each vertex to be visited next. They analyze different algorithmic components that utilize that model, for example, greedily following the most probable vertex, or sampling multiple tours and picking the best. Other research has shown that the question of scaling such architectures to real-world instances poses a challenge by itself, and that currently, algorithmic solvers often outperform ML-based solvers for larger instances (Joshi et al., 2021]. A theoretical understanding of how such models extrapolate to different instance families is also topic of current research (Xu al. 102
With this discussion, we want to show that the design space for MI--based solvers is broad, as on the one hand, one has to design a model that learns how solve a problem, and on the other hand build an efficient algorithmic component that utilizes that model to actually find solution. These components can become very complex, as seen in recent work by Nair et al. (02T)) which aims at solving Mixed Integer Programs and uses two neural network components instead of one; the neural diving component finds variable assignments, while the neural branching component guides the branch-and-bound algorithm in its next step.
Other Solvers for Maximum Independent Set. Next to the solvers included in this paper, there are some other solvers available. Khalil et al. (2017) propose S2V-DQN, in which they use Q-learning to solve the minimum vertex cover problem Compared to LwD, which marks multiple vertices as part of the MIS in a single step, S2V-DQN only labels single vertex in each step. We mention the recent publication by Hespe et al. (202)) introducing some new reduction rules for MIS, which have not yet been included in KAMIS. Another heuristic for MIS that do not consider in this paper in favor of KAMIS is GRASP (Feo et al., 1994). Note that all of these solvers are heuristics and hence only solve MIS approximately; exact solvers have been proposed by Jain & Seshadhril (2020); Xiao & Nagamochi] (2017): Tomita et al. (2010), for example, and theory has been working on understanding why and in what models MIS poses to be difficult (Censor- Ceenor-Hilllll et al. 2017).
3 EVALUATION
In this section, we first introduce our experimental setup and then focus on the analysis of the supervised tree search approach for combinatorial optimization in /Section 3.1 After having derived good configuration for the tree search algorithm, we continue to compare the tree search algorithms to the other classical and reinforcement learning solvers in Section 3.2) We investigate the scalability of the approaches in /Secieenon 3.3) and analyze the behavior on the weighted MIS problem in (Section 3.4
Experimental Setup. We run all our experiments on NVIDIA DGX-1 with 20-Core Intel Xeon E6-2 CPUS at 2.2 GHz, leading to overall 40 physical and 80 logical cores, 512 GB of
MVC is very related to the maximum independent set, one can just flip the assignment.
4

---

Published as a conference paper at ICLR 2022
Table 1: Results of the tree searches in various configurations; the full table with more datasets and more configuration options can be found in Table 2 For all configurations, in the first row, we state the average MIS size as well the average approximation factor. In the second row, the average time in seconds until the best solution was found, and, in brackets, the number of graphs where any solution was found are given. The average values refer only to the graphs within a dataset for which a solution was found. For Intel, here we show the default setting (d) and the setup with both reduction and local search enabled (r+1s). For DGL, we explore the configuration space further, as we analyze the default (c). reduction and local search (I+1s), queue pruning and weighted queue pop (pp+wp), and the full configuration where we replace the GCN by randomly generated outputs (+ (+rand), For the random graphs of size 50- 100, all solvers have time limit of 15 seconds; for the SATLIB and PPI datasets the time limit is 30 seconds; for VC-BM and DIMACS graphs, the time limit is 5 minutes.
Intel
DGL
Graph
Nodes
d
r+Is
d
r+Is
qp+wp
<p+wptr+ls+rrnd
20.58 (0.98)
20.83 (1.00)
19.88 (0.95)
20.83 (1.00)
(0.92)
20.83 (1.00)
50-100
ER
1.70 (500)
0.02 (500)
3.53 (500)
0.28 (500)
3.39 (500)
0.31 (500)
700-800
12.00 (100)
39 (-)
16.81 (100)
(100)
(-)
12.82 (100)
9.11 (100)
34.79
10.08 (100)
33.62 (0.99)
32,80
33.72 (1.00)
30.93 (0.92)
HRG
50-100
3.24 (495)
0.00 (500)
5.50 (500)
0.06 (500)
3.45 (500)
0.07 (500)
700-800
(
304.21 (1.00)
0.05 (100)
221.80
17.81 (5)
364.21 (1.00)
0.40 (100)
245.29 (0.80)
13:55 (98)
304.21 (1.00)
0.44 (100)
SATLIB
1209-1347
426.39 (0.99)
(0.79)
426.25 (0.99)
356,93 (0.84)
426.48 (0.99)
(500)
18:48 (2)
9.55 (500)
17,91 (211)
(500)
VC-BM 450-1534
39.85
11,26
(-)
44,35
(-)
44,58 (-)
(40))0
(39)
(40)
(40)
64.57 (40)
DIMACS
125-4000
79730((37)
37.14.6)
43.12
76.41 (-)
87.53 (37)
57.68 (-)
36.36 (37)
76.49
42.56 (37)
45.54
27.89
76.51 (-)
PPI
591-3180
-0
1002,83 (1.00) 24.70
269.00 (0:97))
23.56 (1)
1002.67 (0.9 (..99)
3.70 (24)
804,38 (0.92)
20.11 (13)
1002.79 (0.99)
memory, and a total of eight NVIDIA Tesla V100 GPUs For each experiment, we explicitly state the number of threads and GPUs used. We run Ubuntu 20.04.1 LTS, using Linux kernel 4.15.0. 0-124
Datasets. We evaluate the various solvers and configurations using both real-world datasets as well as generated random graphs in various sizes. We make use of the random graph models by Erdös & Rényí 1960) (ER), Albert & Barabási (2002) (BA). Holme& & Kim (2002) (HK), Watts & Strogatz (1998) (WS) and the Hyperbolic Random Graph model (Krioukov et al. 2010 (HRG). The graph generation functionality, employing NetworkX (Hagberg et al. (008) and girgs (Bläsius et al.) 2019) as backends, is integrated into our benchmark suite. For real-world datasets, we focus on the hard SATLIB dataset (Hoos & Stützle| 2000). which consists of synthetic 3-SAT AT instances, the vertex cover benchmark (VC-BM) (Xu et al.] 2007) consisting of 40 graphs on which finding the maximum independent set is synthetically made hard, and the DIMACS challenge graphs; we also test various other graphs, like citation networks. Details on all mentioned datasets as well as hyperparameters of graph generation can be found in Appendix E
3.1 ANALYSIS OF THE TREE SEARCH
In this subsection, we analyze the WNTEL-TREESEAREE and DGL-TREESEARCI. These supervised approaches require training a GCN (Kipi & Welling 2017). Following Li et al. (2018). we train both on the SATLIB dataset for 20 epochs using the Adam optimizer (Kinmma & Ba 2015). As the GCN outputs multiple probability maps (c.f. Appendix B). we employ the hindsight loss, which, for multiple choices, outputs the loss of the best choice (Guzmán-Rivera et al. 2012 Chen & Koltun 2017). We fix the number of probability maps to 32, to enable comparison with Li et al. (2018). We test the solvers in different configurations with increasing levels of complexity and intuitively should improve the solution quality. Details on what effects the individual configuration options have outlined in Appendix B An excerpt of our results can be found in Table I the full table can be found in the Appendix A in Table 2
various graphs; these configurations are assorted
Random Graph Results. First, we discuss the results of the random graphs. For all small graphs, both tree searches in all configurations find solutions most of the time. These are close to optimal as soon reduction (+r) and local search (+1 s) involved. Notably, on larger non-ER random graphs, in
5

---

Published as a conference paper at ICLR 2022
ER 50-100
ER 700-800
HRG 700-800
SATLIB
VC-BM
Time solotion ba
300
MOLLA
60
10
15
40
10
20
5
460
320
55
300
50
MIS sizee
22.5
40
280
400
45
20.0
260
40
17.5
35
240
350
35
220
30
30
200
300
25
(e) Intel
(b) Ired riis
(6) DGL
(d) DGL mila
(e) DCL gpopp
(b) Innel mile
(d) DGL mile
(e) DGL ap-igg
(0 DGL -ww.---------eeeee.. op-tanat
Lizel pris
(c) DGL
(4) hGI. nole
(4) DGL. gpoeg
(n DGL be-tege upp prnm
DGL
(c) DCG, mile
(6) DGL gett-ggei wp
(n DGL la tege hap tand
(a) Intel
Ined rele
(c) DGL
(c) DCI, mila
(6) DGL gp-orp
0y DCL, r- r-lo--eg woseeee-----pp-aaaee opperand
hpp
(a)
(n DGL la
Figure 1: Violin plots of time to solution and MIS sizes of the tree searches in various configurations on selection of data sets.
the default variants, where neither reduction nor local search is enabled, both INTEL-TRRESFFACH and AGL-TREESEARCH do not often find solution. This shows that for medium-sized graphs, vanilla tree searches cannot discover solutions within a feasible time limit. The reductions often mogglehhandedl] solve the problem instance, as seen for example on the simple BA graphs, where solution is found instantaneously.
Queue Pruning and Weighted Queue Pop. To approach the issue of requiring hand-tailored we analyze queue pruning
reduction techniques to obtain any solution, with DGL--RRESSAAR and the weighted queue pop. While queue pruning itself performs similar to the default configuration for all graphs, the weighted pop vastly increases the number of solutions found. For example, for large hyperbolic random graphs, in the default configuration, the DGL-TRELSEARCH was only able to find solutions for graphs (and the SEEEL--REEEE.AE whereas using queue pruning together with the weighted queue pop, we find solutions for 98 of all large HRGs. A similar observation
was not able to find any solution),
be made for WS graphs. Interestingly, it seems like the MIS problem is harder to address with the default approach on graphs that try to model real-world networks, such the just mentioned HRGs and WS graphs (Bläsius al. 2018). Overall, queue pruning might be desirable to reduce memory consumption. but its impact on solving quality and time is limited; on the other hand, weighted queue popping is general idea that brings some more depth-search-Ii behavior into the breadth-search--in like approach at hand, and thus enables the solver to find lot more solutions.
Importance of Reduction. For small and large BA, HK, WS graphs as well as HRGs, the reduction itself already leads an achieved average approximation of 1. Only for the large ER graphs, for which GUROBI was not able to find provably optimal assignments, the local search further improves average independent set size. Multithreading cannot improve the results of the random graphs.
Hard Real-World Graph Results. Now, we discuss the results for the hard benchmark datasets. Unlike previously, where we just aimed at finding an MIS on random graphs, solving the MIS problem on SATLIB is equivalent to finding satisfiable assignment to synthesized hard 3-SAT instances. Thus, one can expect this data set to be particularly hard. Our experiments confirm this, as both implementations rarely find solutions within the time limit without reduction enabled. We can that, similar to the random graphs, the weighted queue pop enables the search to at least find some solution, as this configuration least able to find 211 instead of results at all. However, the

---

Published as a conference paper at ICLR 2022
average independent set size is 357, which is not very good, considering each MIS in this dataset contains at least 403 vertices.
Considering VC-BM, due to the higher time limit, the default configurations are already able to find some solution. Interestingly. for VC-BM, the reductions do not improve the performance of the solvers. Hence, the weighted queue pop is very important for finding results quickly, shrinking the time needed from the default 140 seconds to under 70 seconds. For DIMACS, we see similar behavior SATLIB, i.e., the reduction and local search techniques improve the average MIS, and the weighted queue pop enables faster discovery of solutions.
Impact of the Findings. These results are interesting for various reasons. First, the models trained on SATLIB instances, but the default configuration does not find any independent set for other instances of the this family, which was one motivation for using machine learning for optimization (c.f. ..f.fScciion]] T). The results contradict the original paper by Li et al. (2018), which claims an average MIS of 426 and related work by [Ahn et al. (202)). claiming an average MIS of 418. Additionalyy to our own trained weights, we test the model weights provided in the official repository, but do not find any differences in the results. Ahn et al. (2020) mention that they modified the official their queue pruning has been implemented, nor were the authors themselves able to provide us their modifications to the original -NTES-TREEEEARCE repository when we contacted them. Hence, remains unclear whether the difference in the SATLIB results between AAhn et al. (2020) and our experiments stems from how they implemented queue pruning, or from some unwanted side effects in their experiments (e.g.. the reduction may have been still enabled). Furthermore, we unsuccessfully contacted Li et al. (2018) about our findings. As both the INTEL-TREESEARCI and our re-implementation DGL- HGL-TTREEE REEESERRII, which was written from scratch, exhibit this behavior, we suspect that there must be an undocumented modification or problem in the experiments that leads to Ahn et al. (2020) obtaining rather good results with the default configuration. Overall, neither the original code with the original weights, nor the original code with newly trained weights, nor our reimplementation are performing as originally claimed. In order to be as transparent as possible about our findings, we provide all of our code changes applied to the Intel repository as a patch and provide the entire source code of the re-implemented
RRIII
code. Unfortunately, neither the paper documents how exactly
as well.
Replacing the GCN with Random Values. Next, we analyze the replacement of the outputs of the GCN with random values. We start with the randomized default configuration, i.e., no techniques like reduction are enabled. In this case, we find that for all small random graphs, the tree search is still able to find solutions; however, the quality of these MIS seems be slightly worse than the default results. For 80 % of the larger random graphs - except for ER graphs - tte randomized tree search is not able to find solutions. As the default configuration is not able to find any solution for SATLIB, it is to be expected that the random configuration does not find any solution either.
Randomness for Other Real-Worid Graphs. For the other real-world graphs, the reddit datasets are the only datasets where the default configuration performed reasonably well. We find that the randomness here in fact increases the performance of the algorithm.
Robustness. Most ouf our datasets consist of multiple instances. In order to shed light onto the distribution of both the solution size well as the time until the solution was found, in Figure we show violin plots for some data sets and tree search configurations. Note in most real world scenarios, we do not know when we can terminate, hence the run time will always be the maximum time limit configured. In these plots, we can for example again confirm that the combination of queue pruning and weighted popping enables us to find solutions quicker. We also see that as soon as reduction and local search are enabled, the solution distributions of the tree searches are very similar, no matter whether whether we query the GCN or use random values; for SATLIB, we see that using random values the distribution of the time to solution is even narrower towards O, because no GPU computation is required.
Final Considerations. We conclude that the guidance by the GCN does not help our tree search algorithm; for some datasets, it is not able to generalize well (randomness beats the GCN), for others, there is no performance difference between random values and the GCN. If we focus on the configuration of the tree search that could be considered the production version 10 i.e., with at least
Recall that the default version is not able to solve the SATLIB dataset without the help of reduction and local search techniques.
7

---

Published as a conference paper at ICLR 2022
reduction and local search enabled, find that random outputs lead to identical performance, with very minor differences in the time until the final solution discovery. Overall, major contributing factors to solution quality are the reduction and local search by KAMIS, and in fact, the tree search algorithm a "smarter brute-force" approach that does not gain any performance by being guided by machine learning model. Instead, the search space is only narrowed by techniques such data reduction and weighted queue popping, instead of good guidance by the ML model.
3.2 COMPARING TREE SEARCH SOLVERS TO OTHER SOLVERS
Having understood the implications of the various possible configurations of tree searches, next, we compare
and OGL-TREESEARCH to KAMIS, a heuristic solver optimized for the MAXIMUM INDEPENDENT SET problem, the mathematical optimization tool GUROBI, and the reinforcement learning tool LEARNING WHAT To DEFER. For LwD, we train for 20 000 iterations of proximal policy optimization on the SATLIB dataset, using the hyperparameters given for SATLIB in Table 5 (Appendix A.I) of Ahn et al. (2020). Due to space constraints, the detailed results are given in Appendix A in Table 3
KAMIS and GUROBI. As we can see, the sophisticated state-of-the-art solver KAMIS can solve almost all instances perfectly; for example, for the large ER graphs the multithreaded INTEL- TREESEARCH has a slightly higher average MIS, and a faster time until a solution is found. For other graphs, especially the SATLIB dataset, KAMIS is very fast, while obtaining very high-qualit results. These results are in line with Ahnn et al. 2020), who also observed KA outperforming the tree search. Regarding the general-purpose solver GUROBI, we find that it performs similar KAMIS on simple instances, however, on harder datasets such as SATLIB or VC-BM, we see that Gurobi takes significantly more time find good solutions, and the average MIS is a little smaller (e-g.. for large ER graphs, KAMIS achieves 44.57, compared to 37.79 for GUROBI). Note that GUROBI and KAMIS have rely on the CPU, while the tree search employs one one or more GPUs, unless uses random values. Evening when assigning eight V100 GPUs to the multithreaded tree search, the computational advantage of the tree search does not help to outperform the other solvers, showing that the workload is not GPU-bound.
LwD. We analyze LwD first in its default configuration and then, similar to the tree search, replace the output of the graph neural network with random tensor. First, LWD is very fast, even though it requires neural network inference. For example, on the DIMACS data set, LwD finds solutions on average in just 4 seconds, while KAMIS takes 121 seconds. Quality-wise, except for the VC-BM dataset, it always finds near-optimal solutions. Note that we did not use the local search or reduction techniques for LwD, which could further improve solution quality. When using random output instead of the neural network, unlike the tree search algorithms, the solution quality degrades noticeably. These promising results show that LwD did not only learn the solution structure of the SATLIB instance family, but additionally is able to generalize over different datasets.
Robustness. Due to space constraints, we show violin plots of the results in AmpAppdddxx A in Figure We clearly see the impact of randomness on LwD, and can visually compare the time difference between GUROBI and KAMIS, for example on VC-BM.
Final Considerations. For tree search approaches, we see that state-of-the-art algorithmic techniques are required find good solutions. As the fully-configured versions of the tree searches employ these LAMISSinterma routines, one can argue that the purely algorithmic solvers are the better choice, because the quality difference is negligible, while KAMIS faster than the tree searches. Purely algorithmic solvers do not come with the overhead of a machine learning environment (training as well as execution are more complicated), and the important algorithmic techniques need to be developed in any case. Our results are in line with observations by Joshi al. (2221) who have compared algorithmic and classical solvers to deep learning solutions for TSP, and observe that DL-based solutions are often outperformed, especially on larger instances.
3.3 LARGE-SCALE GRAPHS
However, the question is whether these observations also hold true for large-scale graphs. To this end, we evaluate the solvers on random graph instances from 500 000 to 5 5000 000 vertices, and on huge real-world graphs. Detailed results can be found in Appendix Alin Table 4]
8

---

Published as a conference paper at ICLR 2022
Overall, we observe similar performance characteristics on large-scale graphs. Only KAMIS and GUROBI are able to find solutions for all scenarios. KAMIS performs best, both with respect to solution quality and time required to find these solutions; in many cases, it is more than one order of magnitude faster than other solvers. Compared to the TREES-TREESAACH the DGL.- TReeSeARCH time outs more often due to VRAM limits; the INTEL-TREESFARCH benefits from lower-level implementation using numpy arrays and sparse adjacency matrices, while the DGL- TREESEARCH employs the higher level Deep Graph Library graph abstraction, consuming more memory. For LwD, we see good results for graphs up to 500 000 vertices, but cannot verify the scalability up to 000 000 vertices of the original paper
3.4 WEIGHTED GRAPHI
Having analyzed the solvers on unweighted graphs, we briefly want to see how the solvers perform on weighted graphs. Intuitively, the weighted problem is harder, because each vertex can have a different value; hence specialized reduction techniques have be developed. [amm al. (2019) were the first to present such rules also for the weighted case that are implemented in KAMIS, however, only integer weights are currently supported. We test weighted random graphs and three Amazon MWIS data sets. The results and details on the weighted graph generation are given in Apppnddxx A in Table 5] note that INTEL-TTREES TREESEARCH does not support the weighted case, and while Ahn et al. (2020) evaluate LwD for MWIS, they do not provide the code to do so.
We observe that on HK, WS, and HRG graphs, where KAMIS is able to utilize its reduction techniques, it is able to instantaneously solve the weighted problem well. However, on ER graphs, the reduction times out, showing that the suitability of the algorithmic techniques is graph-dependent. In the weighted case ER graphs, the best result. GUROBI finds solutions of similar quality to KAMIS very quickly. For the Amazon data sets, all solvers except GUROBI reach their limits. KAMIS does not support the large node weights that are used in the Amazon instances and hence is not able to solve them. The DGL-TREESE. goes out of memory and crashes while solving these instances. Overall, we see that both GUROBI as well as the vanilla tree search have the advantage of being problem-agnostic, i.e., an extension to the weighted case was easily possible, while for the algorithmic solver, new reductions are needed, that currently cannot deal with some graphs. On smaller random graphs where the reductions are successful, KAMIS finds solutions of the highest quality, showing the trade-off between general and specialized solvers. GUROBT is the only solver that is able to solve large, weighted, real-world MWIS instances, and shows that mndstry-standarr optimizers are very robust towards different inputs of different sizes, while smaller algorithmic solvers need more time to reach that level of robustness.
with queue pruning enabled finds the
4 CONCLUSION AND FUTURE WORK
We present our comprehensive, open-source benehmark environment for the MAXIMUM (WEIGHTED) INDEPENDENT SET problem. Using this environment, we run several experiments on both real-world and synthetic graphs of different sizes. Our analysis shows that guided tree searches, such as the ANTELTRREESEARO by Li et al. (2018), owe their good results not to the trained neural network, but instead the various techniques used make "better" brute-force algorithm. To verify this, we show that the GCN that guides the search can be replaced by random values without a noticeable performance impact. Furthermore, we are not able to reproduce the results of previous work in the default configuration of the algorithm and claim that without algorithmic techniques, the tree search algorithms are not able to solve hard MIS instances. We believe our results to be an important insight for the community researching at the intersection of combinatorial optimization and machine learning. The benchmark suite lays the ground fur future reproducible evaluations for new MIS solvers, and the promising results for LEARNING WHAT To DEFER indicate that reinforcement learning is superior to supervised approaches. This might be kept in mind when developing solving techniques using machine learning in the future. For future work, further variants of the MAXIMUM INDEPENDENT SET problem, such as the GENERA AENERALIZER ALIZED INDEPENDENT SET problem (Colombi et al. 2017 Hosseinian & Butenko 2019). and other problems, such as TSP, should be considered, to further understand for what kind of problem what solver architecture should be used.
As Ahn et al. 2020) do not explicitly state the hyperparameter configuration for their large-scale experiments and random graph generation, these experiments might not be directly comparible
9

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
We adhere to the ICLR Code of Ethics and declare that we have no conflicts of interest. We tried to contact the authors of the related work, stated in the respective sections.
REPRODUCIBILITY STATEMENT
As our results contradict previous work, we to be as transparent possible about our process. The solvers we use are documented in Section 2 The changes we apply to LwD and INTEL-TREESEARCI are supplied as a git patch with our benchmark suite that can be accessed via the our repository or in the supplementary material published alongside with this paper. The datasets we use are listed in Appendix El supply the code required to preprocess the datasets.
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their invaluable feedback and the HPI FutureSOC Lab for computing infrastructure.
REFERENCES
Sungsoo Ahn. Younggyo Sco, and Jinwoo Shin. Learning what defer for maximum independent sets. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, 2020.
Réka Albert and Albert-László Barabási. Statistical mechanies of complex networks. Reviews of Modern Physics, 74(1), 2002. doi: 10.1105hewmoppyyy744477
Anaconda Inc. Anaconda software distribution, 2020. URL https::/docs... anwconda.
Monya Baker. 1,000 scientists lift the lid on reproducibility. Nature, 533(7604), 2016. doi: 10.1038/533452a
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, 2018.
Jean Berger and Mohamed Barkaoui. A hybrid genetic algorithm for the capacitated vehicle routing problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2003, 2003. doi: 10.1007/3-5400455005-
Thomas Bläsius, Tobias Fricdrich, Maximilian Katzmann, Anton Krohmer, and Jonathan Stricbel. Towards systematic evaluation of generative network models. In Proceedings of the International Workshop on Algorithms and Models for the Web Graph (WAW), 2018. doi: 10. 10.10077/78-3-311 92871-558.
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. In Proceedings the 27th Annual European Symposium on Algorithms (ESA), 2019. doi: 10.4230/LIPICSS 210.III.I...EES..........
Geoff Boeing. OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 65, 2017. doi: 10. (0.1016/j.ompennv rbsys.2017. 2007.005000.
Maximilian Böther, Leon Schiller, Philipp Fischbeck, Louise Molitor, Martin S. Krejca, and Tobias Friedrich. Evolutionary minimization of traffic congestion. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 2021. doi: 10.1 04.144/3444933.3455330
Sergiy Butenko. Maximum Independent Set and Related Problems, with Applications. PhD thesis, University of Florida, 2003.
httpp::/giite thtp. com Maxi Hoether
10

---

Published as a conference paper at ICLR 2022
Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near- wear-quadratic lower bounds for the congest model. In Proceedings of the 31st Interaational Symposium on Distributed Computing (DISC), 2017. doi: 1042:00LPICC..DSS222....
Qifeng Chen and Vladlen Koltun. Photographic image synthesis with cascaded refinement networks. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017. doi: 10.1 10.1109/cccv.oo 1091iccc.2201........ 20017.168.
Marco Colombi, Renata Mansini, and Martin Savelshergh. The generalized independent set problem: Polyhedral analysis and solution approaches. European Journal of Operational Research, 260(1): 41-55, 2017. doi: (tt.://eeor.2216..1111
Zihao Ding, Aniketh Reddy, and Aparna Joshi. Reproduciblity, 2020. URL httts://bblog.n. cmu.
Yuanyuan Dong, Andrew V. Goldberg. Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, and Quico Spaen. New instances for maximum weight independent from a vehicle routing application. Operations Research Forum, 2(4), 2021. doi: 10. 10.1007/44509--01-0008444
Paul Erdós and Alfréd Rényi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1), 1960.
Majid Eskandarpour, Pierre Dejax, Joe Miemezyk, and Olivier Péton. Sustainable supply chain network design: An optinization-oriente review. Omega, 54, 2015. doi: 10.1016//.omeg.2015..
1.006.
Thomas A. Feo, Mauricio G. C. Resende, and Stuart H. Smith. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42(5), 1994.
Tobias Friedrich. From graph theory to network science: The natural emergence of hyperbolicity (Iutorial). In Proceedings of the 36th International Symposium Theoretical Aspects of Computer Science (STACS), 2019. doi: 1142300LLPIISSSSTAASSS.0
Michael R. Garey and David S. Johnson. Strong NP-completeness results. Journal of the ACM, 25 (3), 1978. doi: 10. 145/322077.322000
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the 3rd Conference on Digital Libraries (DL), 1998. doi: 10.1 14457766 75.276685.
Gurobi Optimization LLC.. Gurobi website, 2021. URL http/:t/t////tt htt.tpp::/www..gurobb... com/
Abner Guzmán- Rivera, Dhruv Batra, and Pushmeet Kohli. Multiple choice learning: Learning to produce multiple structured outputs. In Advances in Neural Information Processing Systems (NeurIPS), volume 25, 2012.
Aric Hagberg. Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab. (LANL), Los Alamos, NM (United States), 2008
William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2017.
Demian Hespe, Christian Schulz, and Darren Strash. Scalable kernelization for maximum independent sets. ACM Journal of Experimental Algorithmics, 24(1). 2019. doi: 10.1 155/3355505..
Demian Hespe, Sebastian Lamm, and Christian Schorr. Targeted Branching for the Maximum Independent Set Problem. In Proceedings of the 19th International Symposium on Experimental Algorithms (SEA), 2021. doi: A22.00...PPcc.SSAA.22.......
Petter Holme and Beom Jun Kim. Growing scale-free networks with tunable clustering. Physical Review E, 65(2), 2002. doi: 10. 10.11003phyrreve..5.0222 wtwp://srreee...22611.. 65.026107.
Holger Hoos and Thomas Stützle. Satlib: An online resource for research on sat. In SAT 2000. IOS Press, 2000.
11

---

Published as a conference paper at ICLR 2022
Seyedmohammadhossein Hosseinian and Sergiy Butenko. Algorithms for the generalized independent set problem based on a quadratic optimization approach. Optimization Letters, 13(6), 2019. doi: 1591000911100000-000111
John P. A. Ioannidis. Why most published research findings are false. PLoS Medicine, 2(8), 2005.
doi: 00.137//jormall.mme..02222 1420144.
Shweta Jain and Seshadhri. The power of pivoting for exact clique counting. In Proceedings of the 13th International Conference on Web Search and Data Mining (WSDM), 2020. doi:
10.1 1111444/3361913333 191.73118899
Chaitanya K. Joshi, Quentin Cappart,
Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP), 2021. doi: 10.4230LIPPCS..CP. 33..01.3.
Sayash Kapoor and Arvind Narayanan. Irreproducibility in machine learning, 2020. URL https 1/reprdducible cs pr prinncttonneeii
Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Compu-
tations. Springer US, 1972. doi:
Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Reprexentations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR), 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82(3), 2010, doi: 10. 10.1103/physre ve.82.036106.
Srijan Kumar, Francesca Spezzano, V. Subrahmanian, and Christos Faloutsos. Edge weight prediction in weighted signed networks. In Proceedings of the 16th IEEE International Conference on Data Mining (ICDM), 2016. doi: 10. 109/icdm.2016.0000
Srijan Kumar, Bryan Hooi, Disha Makhija. Mohit Kumar, Christos Faloutsos, and V.S. Subrahmanian. REV2: fraudulent user prediction in rating platforms. In Proceedings of the 11th International Conference on Web Search and Data Mining (WSDM), 2018. doi: 10. 145/3 05553359652..3 315922..
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. Finding near-optimal independent sets at scale. Journal of Heuristics, 23(4), 2017. doi: 10.1007/s10732-0
17-9337-x.
Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. Exactly solving the maximum weight independent set problem on large real-world graphs. In Proceedings of the 21st Symposium on Algorithm Engineering and Experiments (ALENEX), 2019. doi: 10.113 111.9781611 1975499.12
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 25, 2012.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceeding of the / Ith ACM International Conference on Knowledge Discovery and Data Mining (KDD), 2005. doi: 10.1 1455/1111 01000011100088 1081893.
Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1), 2009. doi: 10. 00.00///54279511 2009..011991177
12

---

Published as a conference paper at ICLR 2022
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In Proceedings of the 28th International Conference on Human Factors in Computing Systems (CHI), 2010. doi: (0.1145/1733326.1555533
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Marius Lindauer and Frank Hutter. Warmstarting of model-based algorithm configuration. In Proceedings of the 32nd Conference on Artificial Intelligence (AAAI), 2018.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2), 2000. doi: 00955588110099911111
Raymond E. Miller and David E. Muller. A problem of maximum consistent subsets. IBM Research Report RC-240, 1960.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki. Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks. arXiv preprint 2012.13349, 2021.
OpenStreetMap Contributors. Planet dump retrieved from https:/ppaantt.osm.ogg https: www openstzeetmap. org 2017.
Panos M. Pardalos and Gregory P. Rodgers. branch and bound algorithm for the maximum clique problem. Computers and Operations Research, 19(5), 1992. doi: 10.101 (00000000005444229000000
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performane deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Jannik Peters, Daniel Stephan, Isabel Amon, Hans Gawendowicz, Julius Lischeid, Lennart Salabarria. Jonas Umland, Felix Werner, Martin S. Krejca, Ralf Rothenberger, Timo Kötzing, and Tobias Friedrich. Mixed integer programming versus evolutionary computation for optimizing a hard real-world staff assignment problem. In Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS), 2019.
Jean-Yves Potvin. State-of-the art review reviee--evolutionaryy Journal on Computing, 21(4), 2009, doi: 10.1287/joc.10800031.
evolutionary algorithms for vehicle routing. INFORMS
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. peL/attoee//eettoxxeepppooyyy com
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1707.06347 2017.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Radd. Collective classification in network data. Al Magazine, 29(3), 2008. doi: 10.1609/aimag. 22913.21 57.
Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, and Mitsuo Wakatsuki. A simple and faster branch-and-Bel bound algorithm for finding maximum clique. In Proceedings of the International Workshop on Algorithms and Computation ( (WALCOM), 2010. doi: 10. 1007//9777 642-11440- 18.
13

---

Published as a conference paper at ICLR 2022
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-perfomme package for graph neural networks. arXiv preprint 1909.01315, 2019.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of 'small-world" networks. Nature, 393(6684), 1998. doi: 10.1038/30918.
Robert West, Hristo Paskov, Jure Leskovec, and Christopher Potts. Exploiting social network struc- ture for person-to-peree sentiment analysis. Transactions of the Association for Computational Linguistics, 2, 2014. doi: 00.1162/tacla.001844
Mingyu Xiao and Hiroshi Nagamochi, Exact algorithms for maximum independent set. Information and Computation, 255, 2017. doi:
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 171(8-9), 2007. doi: htt00///..attt.22000 .04.001..
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Pinar Yanardag and S. S.V.N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM International Conference Knowledge Discovery and Data Mining (KDD), 2015. doi: 10.1 (0.1145/ 7783258.2783417.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth Knowledge and Information Systems, 42(1), 2013. doi: 10.10077110115-003-006699
A ADDITIONAL TABLES AND PLOTS
In this section, you can find the tables and plots omitted in the main paper due to space constraints.
14

---

Published as a conference paper at ICLR 2022
Table 2: Results of the tree searches in various configurations. We run experiments on both synthetic and real-world graphs with varying numbers of nodes (c.f. (ppendixx Ep. For all configurations, in the first row, we state the average MIS size as well as the average approximation factor for graphs where we were able to pre-calculate the provably optimal MIS using GUROBI. In the second row, the average time in seconds until the best solution was found, and, in brackets, the number of graphs where any solution was found are given. The average values refer only to the graphs within a dataset for which a solution was found. Columns that start with plus (+) add an additional flag to the previous column; columns that do not start with a plus use just the stated flags. For Intel, we start with the default setting (c), proceed to include the graph reduction (+x), and then the local search (+1s), and last test reduction and local search in multithreaded setup (+mt). For DGL., we explore the configuration space further. After analyzing the default (d), adding reduction (+r), and local search (+1s), we test configurations replacing the GCN with random outputs (ranc), using queue pruning (gp), and weighted queue pop (+wp). We also test a combination of reduction, queue pruning. and weighted queue pop (+x), proceed add the local search (+1s), and again replace the GCN by randomly generated outputs (+rand). The full configuration is tested with and without random output in a multithreaded setup (+mt). All multithreaded experiments in this table use 8 threads, and all threads share a single GPU. For the random graphs of size 50-100, all solvers have a time limit of 15 seconds; for the SATLIB, as-caida, PPI, REDDIT, Citeseer, Cora, and ego-facebook datasets the time limit is 30 seconds; for the bitcoin, PubMed, Wikipedia, VC-BM, DIMACS, and roadnet-berlin graphs, the time limit is minutes. We refer to Apppendix B for detailed explanations of the techniques used. We mark the configuration/solver that has the best average MIS in bold, and grey out configurations for which solutions were found for less than 20 % of all graphs.
1nd
DCL
1:2 M11
34
12
440044
BA
1030
424
41031100
-0401.00
4:41
510 (10
640 2003
1649
5.01200
$1/200
42.0 3M0
422011.0
0.0. 3U0
42311
CL (UR)
79.09
4081
10:00
0411
4400000
16- 1110
16W076M (800
0/81174
HBG
0511
0/9000
2121
1255
5.0 12:000
54.000
1050 830
126-00
1501 210
52)
VC 1
DIMACS
178.00
199
HIDOITE S
150 201
10 (.00
REDDITSK
REDDIT-12K
4.00
wil--BAA
1998
200
2411
Cora
Chasser
106
Hixte- abtt
130 1000
Nocote-tic
rendact Aeslis
4156
15

---

Published as a conference paper at ICLR 2022
Table 3: Results of the modern MIS solver KAMIS, the optimization tool GUROBI, the reinforcement- learning based LEARNING WHAT To DEFER, and the tree search algorithms in their default and full configuration. For the explanation of the various configuration flags, we refer to the caption of Tf All multithreaded experiments in this table use 8 threads, and all threads share a single GPU. Time limits are set equally to Table 2 We note that KAMIS and LWD always run single-threadedly, while GUROBI employs up to 8 threads, as needed. For D,D, we test the default configuration (d) and replace the output of the GNN with a random tensor (rand); the random graphs are executed with 32 iterations per episode, and all other graphs with 128 iterations per episode (c.f. [Ahn et al. (2020)) We mark the configuration/solver that has the best average MIS in bold, and grey out confi configurations for which solutions were found for less than 20 % of all graphs.
Intel
DGL.
L.w
KaMIS
Gumbbi
Graph
Nodes
d
rels+m!
d
reppexptlsem
d
+rand
defauls
default
ER
50-100
20.58 o1 98)
1.70 (500)
28,33 (1.00)
5.39 (500)
19:85 (0.95)
3.53 (530)
2033 (1.99)
0.1 (500)
20.30 36 (0.97)
0.24 (500)
5:66 01
0.06 (500)
308311199
160 (500)
28,33
0.10 (500)
700-900
12.00 (100)
M-C-
(1.90-100)
44.98
13.03 (100)
17-15
22.97 (96)
64 (1)
0.57 (100)
$7.69
0.12 (100)
31.25 (100)
44.57 (-)
30001 (100)
17 79
50-100
42:42 (0.99)
0.54 (400)
42.43 (1.00)
(110)
42.55 10,99)
(L.00
0:11 (1B))
42.43 (1.80)
22.38 53)
0.06 (400)
42.43 (1,00)
1905
42.43 (1.00)
0.00 (110)
700-300
(0.97)
433.58
389:55
432.5 (1.00)
432.57
0.26 (1000
187.79 03:3)
0.10
432.58 (3.00)
433.58 (1.00)
(2:0101.000
HK
700-900
50-100
417.89 (3.95)
(,50(500)
4.53 (19)
426.51
5.15 55155500)
5 (100
59064 (0.90)
19.65 (53)
2.59.500
429.0 42900
0:42 (100)
(500)
055 1000000
222 1000
198
9.09 1000
0.06
(000)
(1,8)
429.81 (11A)
0.01
0.00 (500)
WS
700-800
50-1C0
(0.99)
0.55 (500)
-G
286.00 (1 (0)
367001.00
5.24 (500)
(100)
37.51
530 (500)
10.97)
38 (1000)
000 (500)
6:39 1100)
12 1900
12:20 1100
220000
24.59
000
0.0 (000)
00.031 10
2000
1866
38.70-1.00
1000 (100)
110000000
38.70 1220
0000 (000
HRG
50-100
35 10 99) 3,24
3332 (1.00)
31:30 1099
550
530,
1872
000 2000
020 1000
19.51 10 S8
TE1 (200
700-300
5.51 (110)
1981 15
36421 (100)
(0066
1000
140,30 100
(500)
SATLIB
1309-1347
426.51
2.9
2000
340.50
426.55
13.12 (900)
de (0:90)
144 15
029
00.30
(000
436-59
(899)
426.5 (0.50)
VC-BM
450-1534
14h 501 (40)
50 (-
51.64 (000
48.101-1
15155 (40)
145 (40)
44
190 190000
015 (00)
48.05 65
54 6401
266.71 (10)
42 75
DIMACS
175-0000
37. (.)
10 1975
21.28 (87)
T636
45.64 (261
7003
3534 5534035
(37)
1200
76.75
2022 1N (977
T4 2.35 (.)
as- as-CCaiaa 5020-26475
14.49
(0 991
(122)
-19
1A3NT 20 (LIM))
15:63 (122)
18989 22 (0:90)
3 (123)
7761
5.23
1122)
19983-
223
13 (009)
(122)
1MI9TAR 11 (V
0.15 (227)
PPI
591-5480
-6)
1002.71 (0.09)
(.75
269000 (0.9))
23.56 (1)
1002.50 (0.00)
5.10 (24)
1001
54 (0.99)
1.07 1.07
251.62
0.28 (24)
(0 25
1002
+.00 (34)
19925311 11 MO
9.1% 1901
REDDIT-B
06 10 99)
287.54
185 11
(0.T)
287.54 (1101)
287 (1.99)
147.79
10 57)
5.94
5.37 (500)
11.81
(400)
0.26 (500))
0,00 (500)
9.08
(500)
1.3 0000
0.00 (500))))))
REDDIT-SK
586-31 (0.00)
252.74 (0.55)
15.36
596.22 (1.00)
0-46 (400)
596 (0.99)
0.9% (990
287.7H
0.10 (909)
59633 596-3/2009
11.2 1920
58621 10 (O0
(400)
REDDIT-12K
41-907
3,99
170.20 (1.00)
136.05
170L30 (1101
DUOT 2000
170-20 170-2911.00
178.30 (1.001
wiki -iki
11380
-6)
-1
9096
$100.00
(0.99)
$1LL (1.00)
wiki-Vote
7155
0866.00
8.56
4966
11.25
3.94
1430000
2.18
(1,00)
6966.00
0.50
PuhMed
1977
-6) 19912.00 (1.00)
12.90
-0
15958. v0 (0)
23.34
15912.00 (1.00)
1.34
5474.00
(0.34)
2.07
E5912.00 (L,00)
0.16
19912000 (LEB))
Cora
2006
66 1453,00 (1.000
5.65
-0
1451.00 (1.17))
13:63
1451J10
(3,00)
2.74
644 (1)
1:25
0L06
1451.00 (1.001)
Citeseer
3264
-63 180500 (1.00)
5.51
-19
1900.00 (L.0))
14.02
(1.00)
1.5%
9380000 (1)
1.24
0.06
1988.00 (1-00)
bitcoin-ahe alpha
66 2715:00 11 1.00
-0
2716,00 (1599)
2718410 (.900)
10011000 (0
377
3738/10 (3,00)
2718:00 1.00
11.41
2:31
1.85
0.05
bitcoin-ote
-03 4345.00 991
-99
4152101 (L.M))
43446 00
3771
1574
(0
221
43446
000
(699))
4346000 (99
ego- ego-facebookk
(1.00)
90
-61
1064
1946.00 (1.09)
roadnet-berlin
30845.00
144.22
19
2900000 (LIM))
(0-00)
145200000
211
16

---

Published as a conference paper at ICLR 2022
ER 50-100
ER. 700-800
HRG 700-800
SATLIB
VC-BM
Tine to solution [s]
15
300
30
20
60
20
15
40
2001
10
X
100
4510
40
400
MIS size
350
30
250
300
15
20
2000
250
10
200
20
10
150
150
(a) Intel
(b) lnad pela
(6) DGL
(e) Lab
LedD nont
(e) KaMns
(b) Guak
(b) Tmral rel
rand
(e) Lew
mond
(e) KsMMs
(b) Gumbi
(b) r+s
(c) DGL
(d) DGL -o----- rwp rond
(e) beb
(0 LwD rand
(e) KaMis
(b) Gualia
(b) Tonal rile
(e) DGL
(e) LwD
Len rand
(e) KaMss
(b) Gusoki
(a) Inte
(b) Insal riis
(e) LwD
(0 LeeD rond
(e) KaMdss
(b) Guzula
(e)
(e)
(8) DeL net.-tleee sale wopp
(e)
(a) DGL ctleseeeeeee hap
(a) DGL stlewg
(d)
Figure 2: Violin plots of time to solution and MIS sizes of the modern MIS solver KAMIS, the optimization tool GUROBI, the reinforcement-leanie learning based LEARNING WHAT To DEFER, and the tree search algorithms in their default and full configuration a selection of data sets.
Table 4: Results of the modern MIS solver KAMIS, the optimization tool GUROBI, the reinforcement- learning based LEARNING WHAT To DEFER, and the tree search algorithms in their full configuration, on huge random graphs and huge real world networks. We do not test huge ER graphs due to the time complexity of generating them, and do not test BA graphs as they are similar to HK graphs. For the explanation of the various configuration flags, we refer the caption of Table 2, All multithreaded experiments in this table use 8 threads, and all threads share a single GPU. The time limit for all graphs was set to hours. For LWD, the algorithm is executed with with 128 iterations per episode (c.f. Ahn et al. (2020)). We mark the configuration that has the best average MIS in bold. Configurations that consumed too much VRAM or DRAM are noted as out of memory (OOM).
Intel
DGL
LwD
KaMIS
Gurobi
Graph
Nodes
rtls+mt
r+gptwp+ls+mt
default
default
default
500
289:866.0
242.00
289486600 (-)
289486.00
289486.00
289486.00 00
HK
2000000
1157643.00
COM
OCM
1157644.00 (-)
1157643.00
1064.55
1.15
154.
50000000
2891242.00 (-)
0OM
0OM
2892242.000 (-)
2892242.00 00
3.80
446.83
500000
258887.00 000 (+)
219.57
258887.00 (-)
171.97
258887.00 (-)
11.28
258887.00 (-)
0.22
258887.00 018887..00 (x)
5.4]
WS
2000000
1035715.00
1035715.00 (-)
0OM
1035715.00 (-)
1035715.00
28
5000000
1128,76
(-)
COM
0OM
2589519.00 (-)
2.82
2589519.00
76.26
500
210950.00
374.55
210950000
216.09
21000000011
210950.00
0.78
2109499.00 00
47.20
HRG
2000000
$436188.00 (-)
11144.92 144992
0OM
MOM
$43618.00 (-)
3.5
843616.00 (-)
374,15 15
5 0000000
2110-401.001
1866.42
COM
OOM
2110401,000 (-)
8.62
2110400.00 (-)
1822155 (
DBLPP
317080
153131.00 (1.00)
152131.00 (1.00)
152131,00 (1.00)
152131.00 (1.00)
142.15
112.32
0.30
7.15
puadnet-pennsllvaiia
0888992
0OM
OOM
539625 2000000000000
17.49
533628.00 00
3662.87 .87
ego-gplus
107614
$7394.00
0OM
567744000
57334.00 (-)
$7521 00
399.20
115.76
10802.52
web-google
875213
529138.00 (1.98)
663.18
COM
328725.00 (0.99)
822.14
529138.00 (1.00)
10.67
529138.00 (1. (1.00)
83.30
17

---

Published as a conference paper at ICLR 2022
Table 5: Results of the MIS solver KAMIS, the optimization tool GUROBI, and the DGL.- TREESEARCH in various configurations on weighted random graphs, and Amazon MWIS instances. The weights on the random garphs have been sampled per vertex from a normal distribution ' with 100, `= = 30, capped to be larger than O, and rounded to integer values. For the explanation of the various configuration flags, we refer to the caption of Table All multithreaded experiments in this table use 8 threads, and all threads share single GPU. The time limit for all graphs was set to 30 seconds. We mark the configuration that has the best average MIS bold, and grey out configurations for which solutions were found for less than 20 % of all graphs. Similar to the unweighted experiments, we run the solvers on 500 graphs per type. Configurations where there was timeout due to KAMIS' reduction techniques marked as TO. Configurations where the solver went out of memory are marked as OOM. Note that KAMIS did not support the Amazon instances, as the node weights too large.
DGL
KaMIS
Gunobi
Graph
Nodes
+
+3
4P
+wp
+
+1s
+111
defuult
default
ER
700-000
14 (99)
16.01 (100)
11 (46)
wiot (941
HK
T00-00
30.11
438MA1
100 1906
0.8 1990
2616 (39)
IN 430RAI
1199/500)
0.87 (96)
4YESUH MUAA
042 (930
40RMUU
0.09 1906
0.1 (500)
(1 1681n 9 (1.7) 41163 91:00
1095 53 67)
VOMH (8)
6119 (901))
AEEG (1:6)
HRG
T00-000
236IEA8 (NTR)
33396 8 (199) 37685 (1.999
1390
25583 (2:8))
00 1221
36407A1 (8)7))
1106 (482)
3330658 0106)
1909
0.34
37686 99.99
0331 1306
S36WONG (LAB)
1.01 1900
33006566 (1.8)
UII1 CACE
AMAZON MR 19156-33-01 33-67
214726722
AMAZON-MT 775-12200
AMAZON-MW 30364/204
B TREE SEARCH
In the following, we describe some additional details on the guided tree search approach introduced by Li et al. (2018). A textual description can be found in [Section 2] and a pseudocode description in Algorithm I for a visualization, we refer to Figure of Li et al. (2018). The pseudocode makes use of a function gen probmaps
+ [0, 1] | that can take arbitrary unweighted graphs G E G as input. In the default case, this function calls the trained GCN, which outputs its assignments from vertices to probabilities, i.e., GCN(G') E [0, _|[V We obtain the final solution in a non- non-pseud implementation like OGL-TREESEARCH for example by choosing the largest independent set that is yielded.
Furthermore, there are several modifications (flags) discussed in Section 3.1 In the following, we briefly discuss how these flags impact the tree search algorithm.
Reduction. Reduction or graph kernelization is an addition that uses algorithmic techniques to find vertices which (provably) have to be in the independent set. After determining the residual graph, before generating the probability maps. we optionally can determine whether some vertices can be labeled due to the reduction rules, and then continue to determine the probability maps with an even smaller residual graph.[Lamm et al. (2017) and [Hespe al. (2019) provide reduction rules for the unweighted case, which both INTEL- TREESEARCH and WGL-TREESEARCE access using Python-C++ C+o interface. Furthermore, for the MAXIMUM WEIGHTED INDEPENDENT SET problem, DGL-TREESEARCH uses the recently proposed reduction rules by Lamm et al. (2019).
Local Search. A local search is an addition based on small mutations which try to fur- ther improve a full solution before it is yielded. It can be understood as fine-tuning a solution. The INTEL-TREESFAA plementation by Lamm et al. (2017) and Hespe et al. (2019), and for the weighted case, OGL-TREESEARCH uses the local search by Lamm et al. (2019).
and TREE use the local search im-
Multithreading. To find the MIS faster, one can use multiple threads that search for independent sets. The parallelization idea is very simple, each thread just follows the same procedure stated in [Algorithm I In the INTEL- ONTEL-TREESEARCH, the threads share the queue P, making push and pop operations a critical section. Because we want to avoid this critical section, and due to issues with shared state in Python multiprocessing, in the
18

---

Published as a conference paper at ICLR 2022
Algorithm 1:
Guided Treesearch Algorithm to find MIS (adjusted from Li et al. (2018)). For solution and vertex V, we denote by S, the current status of (included, excluded, unlabeled). For more detailed description, refer to Appendix B
Input: Graph G EV, Function gen gen.probmaps B [0, 1]
Output: Independent sets S; V.
P 6 {(_,
E {0, 1, 1],1,1)11
while P is not empry do
S + random Pop(P);
Vresidual {u V S. 1};
Gresidual -- residual,, {(u, u) E E v E Vresidua))) }); for M gen.een-oomme gen.probmaps (Gressuuu)))) do
S' + S;
for u E Vesidual sorted by descending probability M do
if S = 0 then
break:
S 1;
12
for v E Vesidual adjacent to u do 8 0;
if Vu E V Sy + 1 then
yield S";
16
else
append S' to P;
DGL-TREESEARCH, we give each thread its own queue, and first initialize enough partial solutions, such that each thread has one partial solution to start on.
difficult datasets like SATLIB, the tree search almost cannot find any solution. Furthermore, their experiments, AAhn et al. (2020) state out of memory, something that did not observe
Queue Pruning. As
in Section 3.1
that the INTEL- TREEE-RRE for medium-sized graphs. Queue pruning is a technique used to tackle these two issues. Unfortunately, we could not obtain the information how the queue pruning approach by Ahn et al. (2000) implemented via private communication, hence we propose our own solution. We a maximum number of elements on our queue P. and after appending a new partial solution to the queue, we remove the oldest elements (at position 0) from the queue, until the queue is small enough again. The intuition is that we find more solutions faster, because there is a higher chance to pop an almost labeled (more recent) solution from the queue, and we also limit the memory used. Queue pruning was not proposed in the original paper by Li et al. (2018).
Weighted Queue Pop. By default, the random used in Algorithm chooses an element from the queue uniformly at random. Weighted Queue Pop. the other hand, shifts the probability of each element to be chosen according to how many unlabeled vertices are left in it, favoring fewer unlabeled vertices. Similar queue pruning, the intuition is to find fully labeled solutions faster while keeping some randomness in the popping behavior. It can be freely combined with queue pruning used on its own. To the best of knowledge, no other paper has proposed this addition to the tree search algorithm yet.
Random Values as Probability Maps. This flag changes gen probmaps to random generator, effectively replacing the GCN output with probability values chosen uniformly at random.
We note that the original implementation by Li et al. (2018) does not exactly follow our description and Algorithm 1 We note differences between their paper and the published code in the next section.
19

---

Published as a conference paper at ICLR 2022
C REMARKS ON THE INTEL-TREESEARE IMPLEMENTATION
In this section, we note some important facts to keep in mind when dealing with the original tree search implementation, next to the rather difficult understandability and maintainability of the code. First, for difficult instances, with reduction and local search both disabled, the search queue appears to grow indefinitely without ever finding a single solution. To circumvent this effect and to able to find solutions, it might be necessary to limit the search queue fixed maximum size, observed by |Ahn et al. (2020). They furthermore stress the importance of pruning to limit memory usage. We discuss our approach queue pruning in Appendix B
Second, the paper, it is stated that the GCN is trained for 200 epochs. However, in the implementa- tion, one epoch iterates over just 2000 randomly chosen samples of the 38000 samples in the training sef T3] This is not what you would expect given the term "epoch". Furthermore, the original code has some hardcoded values (e.g., sometimes expects the number of input graphs to be flexible, and sometimes it is hardcoded within the same file). Our patch provided in the benchmark suite fixes these issues.
Third, the selli-threeded variant of the algorithm (demo-parall) www.ppaaaallppep..... py) uses just one randomly chosen probability map of the GCN outputs instead of all. This makes this variant's 's performance in terms of search steps per second, appear to scale superlinearly, and furthermore is not documented in the paper and needs to be kept mind for evaluation.
D DETAILS ON USING GUROBI AS A M(W)IS SOLVER
Gurobi is a general purpose, off-the-shelf, mathematical optimization tool. Hence, many parameters can be tuned, and the performance can very on how the problem to be solved inputted into the solver. In the following two subsections, we investigate the impact of these two dimensions.
D.1 GUROBI TUNING
Similar to training machine learning models, can try optimize Gurobi's performance for the problem at hand. This is called hyperparameter tuning or algorithm configuration, and often done using heuristic searches, e.g., by evolutionary algorithms. One well known optimizer for this is SMAC (Lindauer & Hutter 0); however, in this subsection, we use grbtune as it is the native tool supported by Gurobi for parameter tuning.
Our methodology is as follows. We generate a Gurobi configuration based on 10 instances of the VC-BM dataset. We choose this data set because for most other datasets like SATLIB, grbt une states that it is not able to improve over the default parameters. We note that grbtune decides when it is done, and we do not impose time limit on the tuning process. The resulting found parameters are Heuristics = 0.001, PumpPasses O, and ZeroObjNodes 20000000. We then run Gurobi both with the default configuration and the tuned configuration on various data sets, and split the VC-BM data set into the training and test sets.
The results can be seen in Table 6. We find that tuning does not improve the results, and even on the training set leads to worse performance, although the optimization was performed on exactly those instances. Only for the DIMACS data set, the tuned Gurobi finds the solution faster than the default Gurobi configuration. As Gurobi [ "The bottom line is that automated performance tuning is meant to give suggestions for parameters that could produce consistent, reliable improvements on your models. It is not meant be a replacement for efficient modeling careful performance testing." " One possible explanation might be that grbtune might be more effective on more complex linear programs. Additionally, on most data sets, even states it cannot improve the default parameters. Our
61 21184c277train..yyl.. " in C. of the paper contains an unbound variable responsille for this ambiguity.
htm1
20

---

Published as a conference paper at ICLR 2022
Table 6: Run times results of the the optimization tool GUROBI with default and tuned parameters (c.f. Appendix D.I) For the explanation of the various configuration flags, we refer to the caption of Table 2 Time limits are set equally Table 2 GUROBI employs up 8 threads, as needed. We mark the configuration/soleer that has the best average MIS in bold.
Gurobi
Graph
Nodes
default
tuned
ER
700-800
37.79 (-)
36.61 (-)
30.01 (100)
30,02 (100)
HRG
700-800
304,21 (1.00)
304,21 (1.00)
0.01 (100)
SATLIB
1209-1347
426,57 (0.99)
426.88 (0.99)
3,12 (500)
3,19 (500)
VC-BM (Train)
450-1534
32,00 (-)
31.80
179.55 (10)
205.31 (10)
VC-BM (Test)
450-1534
46.30 (-)
45.63 (-)
300.04 (30)
300.07 (30)
DIMACS
125-4000
74.35 (-)
73.59 (-)
(37)
196.87 (37)
PPI
591-3480
1002.83 (1.00)
1002.79 (0.99)
8.16 (24)
8.96 (24)
experiments show that at least for the linear MIS program, the default configuration of a commercial solver like Gurobi are sufficient. This may differ for other problems and hyperparameter tuning should always be considered, but we do not find any benefit on our data sets.
D.2 ALTERNATIVE MIS FORMULATION
The configuration of the solver is way can impact performance. Another way is reformulating the mathematical optimization task into something that the solver can solver more efficiently. Until now, we have used linear formulation of the MWIS problem, i.e., arg maxsers(G) Eves Wu- Literature has discussed different formulations of the MIS problem (Butenko 2003). We want to whether using different program makes a difference on our benchmark datasets. To this end, we quadratic formulation of the MIS problem (Pardalos & Rodgers 1992). Following the notation of Butenko )2003), let G be graph with n vertices, Ag be its adjacency matrix, and J the x n identity matrix. Let J Ag.
Then, we can calculate the MIS as
arg max X" Ax (0.00
which is quadratic program instead of a linear one, that however might be easier to solve in practice.
To understand the impact of this formulation, of the linear one again on our data sets. The results can be seen in Table 7] We find that, with the exception of the DIMACS data set, the linear formulation always performs equally or better, with both respect to solution size and run time. On DIMACS, the quadratic formulation performs maginally better (74.35 average MIS vs 74.62 average MIS), but also requires more time (202 seconds vs 242 seconds). On all other graphs, especially the hard benchmark instances, the linear formulation is faster, for example for VC-BM, where the linear program requires 269 seconds, and the quadratic program 300 seconds.
Gurobi with this quadratic program instead
21

---

Published as a conference paper at ICLR 2022
Table 7: Results of the modern MIS solver KAMIS, the reinforcement-leaming based LEARNING WHAT To DEFER, the tree search algorithms in their default and full configuration, in comparison to GUROBI with the MIS as a linear program (de fault) and quadratic program (quadratic). For the explanation of the various configuration flags, we refer to the caption of Table All multithreaded experiments in this table use 8 threads, and all threads share single GPU. Time limits are set equally to Table 2 We note that KAMIS and LWD always run single-threadedly, while GUROBI employs up to 8 threads, iterations per episode, and all other graphs with 128 iterations per episode (c.f. [Ahn et al. (2020)) )
needed. For LWD, the random graphs are executed with 32
We mark the configuration/solwe that has the best average MIS in bold, and grey out configurations for which solutions were found for less than 20 % of all graphs.
Intel
DGL
LwD
KaMIS
Gurobi
Graph
Nodes
r+lo+mi
Hip--ppts+ml
dcSoult
quadratic
30.100
1:30 (200)
(1.00
19 (3.00)395))
(253
D41 (XC)
10:66099)
0.241990)
1:00 (200)
35.01 (1200
0.10
(1.8
4.34 (290)
12.00 (100)
(100
(1.6
22.07
0.37
2000
30.62
42.42 991
(2.40
42851333
42.43 13AM
4143-1.00
42.53 (1.01
42.43
43.45
BA
500
5:21 (19)
(1,00
(100
39165 13.59
15 (55)
422.58
43251
0.25 1090
010 1000
452.59 (100)
000 (100
0.02 1900
HK
10-10C
0351 (100)
43480 (1/80
3-50/500)
428
0.75 1900
0 (500)
0100-1900
(500)
(290
3EA9 11 99
CLAR
3741 (38))
3877000000
363807000
(250)
330
700-00
(100
0.34 00000
52.912200
HRG
134
28423 (1,0)
0.90 10010
SATLIB
1006 1347
426 0000
(279
15.41
11100000
423.4 0099
(996
VC-BM
143.00
480
195.3
135
9639
DIMACS
(753
57.8103
45.0
79296 6
as Caida
1907 (T (o0w)
14.09
-1
15.05 (122
543 1122
222
1224
PPI
991-3400
875 (34)
31.5 (3)
3
1,97
515
110000
REDDITER
1000
(980
19631 13.3)
REDDIT-SK
19422
205.3 (00%)
25224 (2.3)
2000
12D
12KA1
39911400 (149)
178.28 (1/00
5000
13655 (3.02)
9534467)
176.38
wiki-RAA
-1
12/8
Wilti-Voee
7115
4846.00 (1000
-19
PubMed
1972
18912.00 (1A00
-10
15858 DO 1EAR
21.14
Cura
2008
5.6
13.0
-13
1886.0 CLARO
-19
bitcoin-alpha
5083
10
211000 (LAB0
-00
3016 90
12
4093.00 1ER8R
hitcoin-ote
2982
6.86
-00
13.47
ggo-facebook
-9
1846.00
11.31
roadnet-berite berlin
-9
20643.00 (D09)
-89
20054000 (3ANS
22

---

Published as a conference paper at ICLR 2022
E DATASETS
In this section, we give some details on the datasets, groups of datasets, and random graphs models used in this paper. For all datasets, we treat all graphs undirected. The data generation module of our benchmarking suite integrates the download/generation and conversion of these graphs. We delete all self-loops, if there are any. because the solvers deal with self-loops differently (for example, with silent failures, errors, or just ignoring the vertex).
Génós-Rééyi. This well-known random graph model by Erdōs & Rényi 1960) connects each pair of vertices with probability p. We use p 0.15 and for testing, generate 500 graphs with 50 to 100 vertices and 100 graphs with 700 to 800 vertices.
Barabási-Albert.
This random graph model by Albert & Barabási (2002) iteratively adds nodes, connecting them to m already existing nodes. We use m = 2 and for testing, generate 500 graphs with 50 to 100 vertices and 100 graphs with 700 800 vertices.
Holme-Kim. A random graph model by Holme & Kim (2002) similar to the BA-model, with an extra step for each randomly created edge that creates a triangle with probability p. We use m = and p 0.05 and for testing, generate 500 graphs with 50 to 100 vertices and 100 graphs with 700 to 800 vertices. For the large-scale experiments, we test on one graph per fixed amount of vertices, c.f. Table 4
Watts-Strogatz. A random graph model by Watts & Strogatz 1998) that starts with well-
structured ring-lattice with mean degree k and in the following step replaces each edge with probability p with another edge sampled uniformly at random. This way it tries to keep "small-world properties" while maintaining a random structure similar to Frdōös-Réníi graphs. We use & = 2 and p = 0.15. For the large-scale experiments, we test on one graph per fixed amount of vertices, c.f. Table 4
Hyperbolic Random Graph. A random graph model by Krioukov et al. (2010), which generates graphs by randomly putting nodes in a disk in the hyperbolic plane, and connecting them if their (hyperbolic) distance is below a certain threshold. Recent works have it described to be the best model for modeling real-world networks, due to their heterogeneity and interdependency (Friedrich) 2019). As generation parameters, we use a = 0.75, T = 0.1, deg = 10 and for testing, generate 500 graphs with 50 100 vertices and 100 graphs with 700 to 800 vertices. For the large-scale experiments, we test on one graph per fixed amount of vertices, c.f. Table 4
This is well-known set of SAT instances in CNF commonly used as a benchmark for SAT solvers (Hoos & Stützle, (000). A SAT instance easily be reduced to graph, which has a MIS as large as the number of clauses, should the SAT instance be satisfiable. In short, for each clause clique is created, each node of which stands for variable its negation, e.g., or -v. Afterwards, for each variable z, all its nodes are connected to nodes referring to its negation -r. We use the "Random-3-SAy Instances with Controlled Backbone Size" datase which consists of 40 000 instances, of which we train on 39 500 and test on 500. Each instance has between 403 to 449 clauses.
SATLIB.
PPL.
The PPI dataset, introduced by Hamilton et al. (2017), contains of 24 graphs whose nodes
describe proteins and edges describe interactions between them. They contain 591 to 3 480 nodes. We the data set provided by DGI [8] as it provides more easily understandable separation between the graphs than the original source by GraphSAGHHD
The REDDIT datasets, introduced by Yanardag & Vishwanathan (2015), contain graphs constructed from online discussion threads on Reddi Vertices represent users and edges represent at least one response by one of the users to the other. The difference between REDDIT-BINARY,
REDDIT.
wBw.cCCS..... html
https://reddit.com
23

---

Published as a conference paper at ICLR 2022
REDDIT-MULTI-SK and REDDIT-MULTI- 112 is how many subreddits have been crawled, and whether the classification task that is usually associated with these datasets is binary or multi-class classification. We obtain the data from TU Dortmund's s data set collection For each dataset, sample 500 graphs for testing, and they contain 41-3 648 nodes.
as- as-Caida. The as-Caida dataset of autonomous systems, introduced by Leskovec et al. 20005), consists of 122 graphs derived from of Route Views BGP table snapshots. They contain 8 020 26 475 nodes. We obtain the data from Stanford's 's SNAP repository 22
Citation, The Citation dataset consists of the three citation network graphs Cora (McCallm al. 2000), Citeseer (Giles et al. 1998) and PubMed (Sen et al. 2008). We obtain all data from NetworkRepository (Rossi & Ahmed 2015).
This dataset contains the com-DBLF Yang & Leskovec 2013) graph. Vertices represent authors and an edge exists two authors have published at least one paper together.
DBLP-Coauthorship.
The Road Networks dataset contains two road networks of different sizes. The net- work roadNet-PA obtained from SNAF represents the state of Pennsylvania (Leskovec 2009).
Road Networks.
The other network maps the city of Berlin, Germany, and is extracted from OpenStreetMap OOpn
StreetMap Contributors 2017) using OSMnx (Boeing 2017).
Social Networks. The Social Networks dataset contains of social network graphs we gathered. Vertices represent users and edges represent some kind of relationship between them. The exact kind relationship depends on the graph. The ego- Ego-FacebooR and ego-Gplus graphs represent "friendships" between users (Leskovec & Mcauley/ (012)). The bitcoin-old and bitcoin-alphy 28 graphs represent Bitcoin's 's web-of-trust network (Kumar et al. 2016 2018). The wiki- and wiki- Mili-RfA" graphs are derived from interactions in the governing process of Wikipedia (Leskovec
et al. 2010
West et al. 2014).
VC-Benchmark (VC-BM). A dataset consisting of 40 graphs of different sizes from 450 to 534 nodes, on which finding the maximum independent is synthetically made hard (Xu et al. 2007). Li et al. (2018) call this dataset BUAA-MC, and sometimes it also called BHOSLIE As the original download is not available anymore, we use GitHub mirro
DIMACS. Graphs used for the evaluation of the second DIMACS implementation challenge in 1992, which is particular hard to solve the MIS problem. The dataset consists of 37 graphs from 125 to 4 000 nodes. We use the complementary benchmark as the original graphs were build for the CLIQUE problem.
35
cn/-k
ex
24

---

Published as a conference paper at ICLR 2022
Amazon, The Amazon data sets several vehicle routing data sets provided for MWIS re- search (Dong et al. (021). We test the smaller MT (6 graphs, 979- 12 320 nodes), MR (5 graphs, 1405--30467 nodes), and MW (8 graphs, 079-447 504 nodes) data sets 56
25


Reviews:
[{"review_id": "pQgoimM1NHL", "reviewer": "Reviewer_m13R", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n- Clarity: The paper is generally very well-written, although the presentation of the results can be improved substantially.\n- Motivation: Li et al.’s paper is being cited and compared against in tens of papers yearly, and so understanding its limitations and apparently fundamental issues is useful for the community.\n- Reproducibility: The authors are very systematic and transparent in how they generate datasets, implement the various methods, and evaluate them. I can see their code becoming widely used and built on in the development of ML-based methods for MIS.\n\n**Weaknesses**\n\n1. Presentation of experimental results: Tables 1 and 2 should be part of the paper’s appendix for sure, but you really need to find better ways of presenting those thousands of statistics in the main text. As things currently stand, the reader needs to zoom-in to read the numbers; there are so many columns that it’s hard to track which one corresponds to which method or what the trends are in terms of best method for a given dataset. Additionally, please label the paragraphs of section 3.1 so that the reader can immediately understand which aspect of the results you’re discussing. As things stand, I’ve had to decipher which columns I should query in the tables to see what you’re saying in the paragraphs of 3.1.\n\n2. Statistical metrics: The average optimality ratios and running times in Tables 1 and 2 are certainly indicative of some trends. However, some box plots of the distributions of the optimality ratios/running times might shed more light into the robustness of the methods. For instance, the running time average may be biased by outliers whereas a box plot factors that in. Combining this suggestion with the one above, you could consider moving the tables to the appendix and replacing them in the main text with two box plots per datasets, one for optimality ratio and another for running time. This way, the reader can visually compare different methods without having to zoom-in and read hundreds of numbers. Since this paper’s contributions are largely software/empirical results, you can also consider performing statistical testing for each pair of methods; see the two-sided Wilcoxon Signed Rank Test for example.\n\n3. Datasets: Please consider additional datasets which may be a bit more standard for MIS papers, e.g.:\n- http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm\n- http://lcs.ios.ac.cn/~caisw/graphs.html\n\nIn particular, the DIMACS implementation challenge graphs have been used in the KaMIS paper for example, among others. Also, this very recent dataset of large-scale instances may be of interest (even if only to evaluate and not train): https://arxiv.org/abs/2105.12623\n\n4. MIS heuristics and mathematical programming formulations: Please check Butenko’s dissertation (Butenko, Sergiy. Maximum independent set and related problems, with applications. University of Florida, 2003.), particularly chapters 2-3 and the experimental results later on. The binary linear programming formulation you used with Gurobi is not the only one possible; there are quadratic formulations (see eq. (2.3) in Butenko) which may be easier to solve in practice than the linear one. Also please check the famous GRASP heuristic for MIS and consider implementing it: Feo, Thomas A., Mauricio GC Resende, and Stuart H. Smith. \"A greedy randomized adaptive search procedure for maximum independent set.\" Operations Research 42.5 (1994): 860-878.\n\n5. Where do your results leave us? I would’ve expected you to identify datasets (existing or new) for which KaMIS and Gurobi underperform in some respect. Perhaps that is tricky; you’ve tried many datasets (though there are more you could try as mentioned earlier) and the two solvers did very well. You might then want to consider other harder versions of MIS, for example the Generalized Independent Set Problem, see (Colombi, Marco, Renata Mansini, and Martin Savelsbergh. \"The generalized independent set problem: Polyhedral analysis and solution approaches.\" European Journal of Operational Research 260.1 (2017): 41-55.) and (Hosseinian, Seyedmohammadhossein, and Sergiy Butenko. \"Algorithms for the generalized independent set problem based on a quadratic optimization approach.\" Optimization Letters 13.6 (2019): 1211-1222.). In this variant, some edges may be “purchased” and their endpoints may violate the independence requirement. This makes the problem much harder than MIS for integer programming solvers. Your paper should really push the community to advance the field.\n\n6. Solver parameter tuning as a baseline: Please consider adding a baseline in which KaMIS/Gurobi are “trained” on the same datasets as the ML-based methods by tuning their parameters using off-the-shelf tools like SMAC (https://www.automl.org/automated-algorithm-design/algorithm-configuration/smac/). Such a baseline combines the best of both worlds in a sense: the stability and generality of these solvers with the potential benefits of leveraging the instance distribution.\n\nMinor comments:\n\n- page 8, “Overall, we see that … cannot deal with some graphs”, this is not true for Gurobi though, correct? ", "summary_of_the_paper": "This paper proposes a software package for generating data and training/evaluation some ML and non-ML approaches for the Maximum Independent Set (MIS) problem in its both its unweighted and weighted versions. It is shown that a highly-cited method that combines supervised learning using a graph neural network (GCN) with a (complete) tree search does not actually need the GCN if the MIS instance is preprocessed appropriately using existing non-ML based codes. On the other hand, a recent deep reinforcement learning (DRL) approach for the same problem is shown to actually use its GCN’s predictions, obtaining better results overall. Last, non-ML solvers such as KaMIS and Gurobi are shown to find better solutions in a short amount of time for most instance datasets, putting into question the potential for ML-based approaches in general for MIS.", "summary_of_the_review": "Overall, I like this paper and think it makes a solid contribution to the intersection between deep learning and combinatorial optimization. However, I think a paper that “debunks” a highly-cited work should also establish convincing avenues for future research which are currently beyond the scope of (ML or non-ML) existing methods; I argue that this is missing at this stage. I would like to see the authors’ responses to my questions and concerns before making a final decision, but am generally positive about this submission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Vskx9sgapOR", "reviewer": "Reviewer_BEvM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe empirical results of the paper have the potential to redirect (some) research in \"ML for combinatorial optimization\" to more fruitful directions in which it is indeed the learned components playing a vital role. I think this is fundamentally valuable.\n\nWeaknesses: \n\nI have multiple concerns regarding the presentation and methodology which I will list below. \n\n* Overall presentation\n\nFirst of all, Table 1 contains about 700 numbers none of which are legible on printed paper due to tiny font size (is it 3?). Given how strictly ML conferences force authors to respect font sizes, margins, and appropriate whitespace, I would almost think such a table merits a desk rejection. More importantly, even after zooming in, it is extremely hard for readers to navigate and draw meaningful conclusions from it. I suggest to a) decide on a subset of the most informative datasets (some are clearly too easy for all methods) and focus on that -- the rest can be in the appendix; b) similarly decide on the key subset of columns; surely the point isn't to compare all the heuristical components; c) This should win enough space to illustrate each of the main conclusions in a plot/table of its own (while displaying precisely the relevant information). d) Introducing a visual distinction between learning-based and classical method would be helpful.\n\nThe write-up assumes a lot of familiarity with tree-search methods and as a result, is uninviting even (!) to researchers from the wider MLxCombOpt community. I suggest the authors consider the following suggestions:\n\na) explaining tree-search basics in the main text\n\nb) explaining (some of) the heuristics in the main text -- it is important for the analysis of the results anyway.\n\nc) restructuring the related work (and introduction?) to categorize different ways ML is applied to NP-Hard combinatorial problems and explaining the place of \"tree-search\" in it (definitely add a discussion of learning to branch-and-bound as well as some details of (Nair 2021)). Categorizing by the degree of interaction between learned and algorithmic components is an option to consider. \n\nWith all of this in place, the paper would put itself in a position to frame its claims in much wider relevance (which I believe the claims deserve).\n\n* Confusion about the promise of DL for comb. opt.\n\nThe second paragraph of the introduction claims that learning-based approaches give a chance to learn to solve a *specific problem* (unlike Gurobi that doesn't make a distinction). I find this inaccurate. For one, there are obviously dedicated solvers to concrete problems; this feature isn't specific to DL. But mainly, the promise of DL, as I see it, is to learn solvers specialized to a *family of instances*. This view is well-motivated by industrial reality (e.g. Amazon's routing instances are almost the same every day) and it appears in the literature (see for example the introduction to (Khalil, 2017)).\n\nThe authors should be more explicit about evaluating the methods in a \"harder\" setup where the learned components are expected to generalize *across* families of instances (it seemed that training happens only on SATLIB). Evaluating the more favorable setting might also be interesting.\n\n* Treatment of Gurobi as a baseline\n\nThis paper has a unique chance to highlight a common issue with Gurobi comparisons. It has a lot of internal parameters that can be tuned to specific problems -- and in fact, they should, if other baselines are allowed to do it. Other than establishing the practice, it could further strengthen the points made by the authors.\n\n* Clarity about GPU utilization\n\nI assume that Gurobi and KaMIS do not utilize GPU whereas other methods do? Does rand use GPU? It seems it wouldn't need to. Given the massive computational advantage that 8 V100s give, the runtime comparisons should be very clear about it. Again, this clarity should go in favor of the main message: e.g. \"even with such computational advantage tree-search doesn't outperform traditional solvers\" or \"since tree search is comparable to rand; it is basically just a powerful GPU-friendly heuristical algorithm that is independent of any machine learning\".", "summary_of_the_paper": "The paper conducts a thorough experimental evaluation of a line of work on \"deep-learning guided tree search in combinatorial optimization\". This line of work iterates on a relatively generic greedy-style algorithm for NP-Hard graph optimization problems; with a neural network -- trained on a training set of instances -- guiding the greedy decisions. The popularity of this approach is anchored in the premise of \"deep learning will help us solve NP-Hard problems.\n\nFindings of the experimental evaluation are the following:\n1) Some earlier work is not reproducible\n2) Traditional dedicated solvers are comparable or better; particularly on harder/larger problem instances\n3) Performance of data-driven methods barely changes when outputs of trained neural nets are replaced by random values (i.e. all the algorithmic power comes from explicit and traditional heuristical components)", "summary_of_the_review": "Despite the paper being purely experimental, its main point can have significant net-positive impact within the wider research area. Not only by casting doubt on the entire \"DL based tree-search\" but also by serving as a long-term warning -- claims about \"outperforming SOTA of classical combinatorial optimization\" can fall apart under proper experimental methodology.\n\n For this reason, I am comfortable disregarding the usual demands for technical novelty, beating benchmarks, or providing theory.\n\nHowever, in its current form, I do not believe the paper would realize its potential impact due to the issues listed above. I believe they require significant changes in the paper structure so I cannot, at this point, recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "EYQ5agHzK8r", "reviewer": "Reviewer_oh3B", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- I think the paper addresses interesting and important questions. Understanding what work and what does not work, and which parts of a solution actually contribute to the performance, is important.\n- The paper provides interesting insight on the performance and reproducibility of a previous work (Li et al. [2018]) based on thorough experiments.\n- The paper presents a new benchmark suite for MIS that includes a large number of benchmark instances and implementations of several popular approaches.\n\nWeaknesses:\n- All experiments are done on one problem type, MIS, while there is a lot of work on other graph-related problems such as TSP, VRP, etc. For example, Li et al. [2018] that is discussed in this work have considered other problems. It is hard to draw conclusions on combinatorial optimization from one problem.\n- The paper focuses on a single work (Li et al., 2018) that the authors were unable to reproduce and a single work that showed promising results (Ahn et al. [2020]). A study of a larger sample of deep learning solutions would be useful to support claims about the value of GNNs, neural-guided tree search, or reinforcement learning for combinatorial optimization.\n- The result that specialized solvers and even classical solvers are often better than deep learning solutions, especially on larger problems, has been reported for other computational problems (e.g., TSP [1]). Ahn et al. [2020] already reported that KaMIS outperforms Li et al. [2018] and that reduction and local search lead to improvements. Further, other works have looked at generalization of GNNs (e.g., [2]). These need to be cited and the similarities and differences with this work should be discussed.\n- While providing open-source benchmark suite, including implementations of several popular approaches, is important, as far as I understand this suite is primarily a collection of existing problems and randomly-generated graphs and does not introduce new benchmark datasets. I am not sure this is an important contribution of the work.\n\n\n\n[1] Joshi, C. K., Cappart, Q., Rousseau, L. M., Laurent, T., & Bresson, X. (2020). Learning TSP requires rethinking generalization. arXiv preprint arXiv:2006.07054.\n\n[2] Xu, K., Zhang, M., Li, J., Du, S. S., Kawarabayashi, K. I., & Jegelka, S. (2020). How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009.11848.\n", "summary_of_the_paper": "The paper presents an evaluation of deep learning-based tree serch solutions (that are based on graph neural networks) for solving combinatorial optimization problems. They present an open-source benchmark suite for the maximum independent set (MIS) problem (both weighted and unweighted) that includes instances from multiple random graph models, known benchmark suites (e.g., SATLIB) and other graphs from the literature. They conduct experiments on different configurations of neural-guided tree search and show that the results by Li et al. [2018] are not reproducible. They also show that general and tailored classical solvers outperform deep learning solutions.", "summary_of_the_review": "Overall, I think this type of works is important and can lead to important insight. However, I think experiments with more problem types and more solutions are needed to draw general and interesting conclusions. Also, the paper needs to discuss some relevant works that are currently not mentioned.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7Iq3ynMr-7f", "reviewer": "Reviewer_Qd1X", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The primary strength of the paper is it is opening up an important direction towards scientific accuracy. Citation counts often work as a proxy for the perceived importance of a paper. A paper with 200+ citations in less than 3 years of publication is thus likely to be considered as highly influential in the field. Through re-looking at the claimed results, this paper makes a significant contribution towards a research philosophy that seeks to validate influential papers. \n\nThe benchmark data set is an important contribution and the detailed results presented in Table 2 can immensely benefit future performance comparisons. \n\nThe writing of the paper is excellent and the paper and the literature review is extensive.  \n\nThat said, one potential risk in this paper is what if the current implementation is wrong and indeed the guided tree search is effective? ", "summary_of_the_paper": "The paper looks at an important problem: combinatorial optimization that arises in several real-world settings. Next, the paper focuses on a influential paper in the field (Li et al. 2018, 200+ citations so far) that presents a GNN approach and reports impressive performance numbers. Next, the paper presents investigates if these results are reproducible by (1) running the publicly available implementation after fixes; and (2) re-implementing the algorithm as described in the paper and documentation. None of these versions replicates the reported performance. The paper also presents a benchmark suite to make comparison of this task easier.   ", "summary_of_the_review": "Our field is producing papers at a fast rate. Reviewers can provide scientific checks and balances only up to a certain level. This type of rigorous effort can offer valuable information about highly influential papers to the scientific community. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: I would like to thank the authors for having managed a thorough discussion despite the complexity of the task at hand (e.g. BEvM). during discussion, the reviewers clearly converged to accepting the paper, praising the importance of the problem tackled and the setup put in place to effectively tackle the challenge at hand.

All this makes the paper an important contribution and a clear accept (and an enjoyable read), for which I can only recommend a further polish before camera ready to follow the latest inclusions.

AC.
Decision: Accept (Poster)