Title: DEEP AUTO-DEFERRING POLICY FOR APPROXIMATING MAXIMUM INDEPENDENT SETS

Abstract: Designing efficient algorithms for combinatorial optimization appears ubiquitously in various scientific fields. Recently, deep reinforcement learning (DRL) frameworks have gained considerable attention as a new approach: they can automatically train a good solver while relying less on sophisticated domain knowledge of the target problem. However, the number of stages (until reaching the final solution) required by existing DRL solvers is proportional to the size of the input graph, which hurts their scalability to large-scale instances. In this paper, we seek to resolve this issue by proposing a novel design of DRL's policy, coined auto-deferring policy (AutoDP), automatically stretching or shrinking its decision process. Specifically, it decides whether to finalize the value of each vertex at the current stage or defer to determine it at later stages. We apply the proposed AutoDP framework to the maximum independent set (MIS) problem and its variants under various scenarios. Our experimental results demonstrate significant improvement of AutoDP over the current state-of-the-art DRL scheme in terms of computational efficiency and approximation quality. The reported performance of our generic DRL scheme is also comparable with that of the existing solvers for MIS, e.g., AutoDP outperforms them for the Barabási-Albert graph with two million vertices.

1. INTRODUCTION:

Combinatorial optimization is an important mathematical field addressing fundamental questions of computation, where its popular examples include the maximum independent set (MIS, Miller & Muller 1960) , satisfiability (SAT, Schaefer 1978) and traveling salesman problem (TSP, Voigt 1831) . Such problems also arise in various applied fields, e.g., sociology (Harary & Ross, 1957) , operations research (Feo et al., 1994) and bioinformatics (Gardiner et al., 2000) . However, most combinatorial optimization problems are NP-hard to solve, i.e., exact solutions are typically intractable to find in practical situations. To alleviate this issue, there have been huge efforts in designing fast heuristic solvers (Biere et al., 2009; Knuth, 1997; Mezard et al., 2009) that generate approximate solutions for such scenarios.

Recently, the remarkable progress in deep learning has stimulated increased interest in learning such heuristics based on deep neural networks (DNNs). Such learning-based approaches are attractive since one could automate the design of approximation algorithms with less reliance on sophisticated knowledge. As the most straight-forward way, supervised learning schemes can be used for training DNNs to imitate the solutions obtained from existing solvers (Vinyals et al., 2015; Li et al., 2018; Selsam et al., 2019) . However, such a direction can be criticized, for its quality and applicability are bounded by those of existing solvers. An ideal direction is to discover new solutions in a fully unsupervised manner, potentially outperforming those based on domain-specific knowledge.

To this end, deep reinforcement learning (DRL) schemes have been studied in the literature (Bello et al., 2016; Khalil et al., 2017; Deudon et al., 2018; Kool et al., 2019) as a Markov decision process (MDP) can be naturally designed with rewards derived from the optimization objective of the target problem. Then, the corresponding agent can be trained based on existing training schemes of DRL, e.g., Bello et al. (2016) trained the so-called pointer network for the TSP based on actor-critic training. Such DRL-based methods are especially attractive since they can even solve unexplored problems where domain knowledge is scarce and no efficient heuristic is known. However, the existing methods struggle to compete with the existing highly optimized solvers. In particular, the gap grows larger when the problem requires solutions with higher dimensions or more complex structures.

Our motivation stems from the observation that existing DRL-based solvers lack efficient policies for generating solutions to combinatorial problems. Specifically, they are mostly based on emulating greedy iterative heuristics (Bello et al., 2016; Khalil et al., 2017) and become too slow for training on large graphs. Their choice seems inevitable since an algorithm that generates a solution based on a single feed-forward pass of DNN is potentially hard to train due to large variance in reward signals coming from high dimensional solutions.

Contribution. In this paper, we propose a new scalable DRL framework, coined auto-deferring policy (AutoDP), designed towards solving combinatorial problems on large graphs. We particularly focus on applying AutoDP to the MIS problem (and its variants) which attempts to find a maximum set of vertices in the graph where no pair of vertices are adjacent to each other. Our choice of the MIS problem is motivated by its hardness and applicability. First, the MIS problem is impossible to approximate in polynomial time by a constant factor (unless P=NP) (Hastad, 1996) , in contrast to (Euclidean or metric) TSP which can be approximated by a factor of 1.5 (Christofides, 1976) . Next, it has wide applications including classification theory (Feo et al., 1994) , computer vision (Sander et al., 2008) and communication algorithms (Jiang & Walrand, 2010) .

The main novelty of AutoDP is automatically stretching the determination of the solution throughout multiple steps. In particular, the agent iteratively acts on every undetermined vertex for either (a) determining the membership of the vertex in the solution or (b) deferring the determination to be made in later steps (see Figure 1 for illustration). Inspired by the celebrated survey propagation (Braunstein et al., 2005) for solving the SAT problem, AutoDP could be interpreted as prioritizing the "easier" decisions to be made first, which in turn simplifies the harder ones by eliminating the source of uncertainties. Compared to the greedy strategy (Khalil et al., 2017) which determines the membership of a single vertex at each step, our framework brings significant speedup by allowing determinations on as many vertices as possible to happen at once. Based on such speedup, AutoDP can solve the optimization problem by generating a large number of candidate solutions in a limited time budget, then reporting the best solution among them. In such a scenario, it is beneficial for the algorithm to generate diverse candidates. To this end, we additionally give a novel diversification bonus to our agent during training, which explicitly encourages the agent to generate a large variety of solutions. Specifically, we create a "coupling" of MDPs to generate two solutions for the given MIS problem and reward the agents for a large deviation between the solutions. The resulting reward efficiently stimulates the agent to explore high-dimensional input spaces and to improve the performance at the evaluation.

We empirically validate the AutoDP method on various types of graphs including the Erdös-Rényi (Erdős & Rényi, 1960) model, the Barabási-Albert (Albert & Barabási, 2002 ) model, the SATLIB (Hoos & Stützle, 2000) benchmark and real-world graphs (Hamilton et al., 2017; Yanardag & Vishwanathan, 2015; Leskovec & Sosič, 2016) . Our algorithm shows consistent superiority over the existing state-of-the-art DRL method (Khalil et al., 2017) both in terms of speed and quality of the solution, and can compete with the existing MIS solver (ReduMIS, Lamm et al. 2017 ) under a similar time budget. For example, AutoDP even outperforms ReduMIS in the Barabási-Albert graph with two million vertices using a smaller amount of time. Furthermore, we also show that our fully learning-based scheme generalizes well even to graph types unseen during training and works well even for other variants of the MIS problem: the maximum weighted independent set (MWIS) problem and the prize collecting maximum independent set (PCMIS) problem (see Appendix B). This sheds light on its potential of being a generic solver that works for arbitrary large-scale graphs.

2. RELATED WORKS:

The maximum independent set (MIS) problem is a prototypical NP-hard task where its optimal solution cannot be approximated by a constant factor in polynomial time (unless P = NP) (Hastad, 1996) , although it admits a nearly linear factor approximation algorithm (Boppana & Halldórsson, 1992) . It is also known to be a W [1]-hard problem in terms of fixed-parameter tractability (Downey & Fellows, 2012) . Since the problem is NP-hard, existing methods (Tomita et al., 2010; San Segundo et al., 2011) for exactly solving the MIS problem often suffers from a prohibitive amount of computation in large graphs. To resolve this issue, a wide range of solvers have been developed for approximately solving the MIS problem (Grosso et al., 2008; Andrade et al., 2012; Dahlum et al., 2016; Lamm et al., 2017; Chang et al., 2017; Hespe et al., 2019) . Notably, Lamm et al. (2017) developed a combination of an evolutionary algorithm with graph kernelization techniques for the MIS problem. Later, Chang et al. (2017) and Hespe et al. (2019) further improved the graph kernelization technique by introducing new reduction rules and parallelization based on graph partitioning, respectively.

In the context of solving combinatorial optimization using neural networks, Hopfield & Tank (1985) first applied the Hopfield-network for solving the traveling salesman problem (TSP). Since then, several works also tried to utilize neural networks in different forms, e.g., see Smith (1999) for a review of such papers. Such works were mostly used for solving combinatorial optimization through online learning, i.e., training was performed for each problem instance separately. More recently, (Vinyals et al., 2015) and (Bello et al., 2016) proposed to solve TSP using an attention-based neural network trained in an offline way. They showed promising results that stimulated many other works to use neural networks for solving combinatorial problems (Khalil et al., 2017; Selsam et al., 2019; Deudon et al., 2018; Amizadeh et al., 2018; Li et al., 2018; Kool et al., 2019) . Importantly, Khalil et al. (2017) proposed a reinforcement learning framework for solving the minimum vertex cover problem, which is equivalent to solving the MIS problem. They query the agent for each vertex to add as a new member of the vertex cover at each step of the Markov decision process. However, such a procedure often leads to a prohibitive amount of computation on graphs with large vertex covers. Next, Li et al. (2018) aim for developing a supervised learning framework for solving the MIS problem. At an angle, their framework is similar to ours since they use hand-designed rules to defer the solution generation procedure at each step. However, it is hard to fairly compare with ours since the supervised learning scheme is highly sensitive to the quality of solutions obtained from existing solvers and is often too expensive to apply, e.g., for the MIS-variants.

3. DEEP AUTO-DEFERRING POLICY:

In this paper, we focus on solving the maximum independent set (MIS) problem. Given a graph G = (V, E) with vertices V and edges E, an independent set is a subset of vertices I ⊆ V where no two vertices in the subset are adjacent to each other. A solution to the MIS problem can be represented as a binary vector x = [x i : i ∈ V] ∈ {0, 1} V with maximum possible cardinality i∈V x i , where each element x i indicates the membership of vertex i in the independent set I, i.e., x i = 1 if and only if i ∈ I. Initially, the algorithm has no assumption about its output, i.e., both x i = 0 and x i = 1 are possible for all i ∈ V. At each iteration, the agent acts on each undetermined vertex i by either (a) determining its membership to be a certain value, i.e., set x i = 0 or x i = 1, or (b) deferring the determination to be made later iterations. The iterations are repeated until all the membership of vertices in the independent set is determined. Such a strategy could be interpreted as progressively narrowing down the set of candidate solutions at each iteration (see Figure 1 for illustration). Intuitively, the act of deferring could be seen as prioritizing to choose the values of the "easier" vertices first. After the decisions are made, decisions on "hard" vertices become easier since the decisions on its surrounding easy vertices are better known. We additionally provide an illustration of the whole algorithm in Appendix A.

3.1. DEFERRED MARKOV DECISION PROCESS:

To train the agent via reinforcement learning, we formulate the proposed algorithm as a Markov decision process (MDP).

State. Each state of the MDP is represented as a vertex-state vector s = [s i : i ∈ V] ∈ {0, 1, * } V , where the vertex i ∈ V is determined to be excluded or included in the independent set whenever s i = 0 or s i = 1, respectively. Otherwise, s i = * indicates the determination has been deferred and expected to be made in later iterations. The MDP is initialized with the deferred vertex-states, i.e., s i = * for all i ∈ V, and terminated when there is no deferred vertex-state left.

Action. Actions correspond to new assignments for the next state of vertices. Since vertex-states of included and excluded vertices are immutable, the assignments are defined only on the deferred vertices. It is represented as a vector

a * = [a i : i ∈ V * ] ∈ {0, 1, * } V * where V * denotes a set of current deferred vertices, i.e., V * = {i : i ∈ V, x i = * }.

Transition. Given two consecutive states s, s and the corresponding assignment a * , the transition P a * (s, s ) consists of two deterministic phases: the update phase and the clean-up phase. In the update phase, the assignment a * generated by the policy is updated for the corresponding vertices V * to result in an intermediate vertex-state s, i.e., s i = a i if i ∈ V * and s i = s i otherwise. In the cleanup phase, the intermediate vertex-state vector s is modified to yield a valid vertex-state vector s , where included vertices are only adjacent to the excluded vertices. To this end, whenever there exists a pair of included vertices adjacent to each other, they are both mapped back to the deferred vertex-state. Next, any deferred vertex neighboring with an included vertex is excluded. If the state reaches the pre-defined time limit, all deferred vertices are automatically excluded. See Figure 2 for a more detailed illustration of the transition.

Reward. Finally, reward R(s, s ) is defined as the increase in cardinality of included vertices, i.e., R(s, s ) = i∈V * \V * s i , where V * and V * are the set of vertices with deferred vertex-state with respect to s and s , respectively. By doing so, the overall return of the MDP corresponds to the cardinality of the independent set returned by our algorithm.

3.2. TRAINING WITH DIVERSIFICATION REWARD:

Next, we introduce an additional reward term for encouraging diversification of solutions generated by the agent. Such regularization is motivated by our evaluation method which samples multiple candidate solutions to report the best one as the final output. For such scenarios, it would be beneficial to generate diverse solutions of high maximum score, rather than ones of similar scores. One might argue that the existing entropy regularization (Williams & Peng, 1991) for encouraging exploration over MDP could be used for this purpose. However, the entropy regularization attempts to generate diverse trajectories of the same MDP which does not necessarily lead to diverse solutions at last, since there exist many trajectories resulting in the same solution (see Section 3.1). We instead directly maximize the diversity among solutions by a new reward term. To this end, we "couple" two copies of MDPs defined in Section 3.1 into a new MDP by sharing the same graph G with a pair of distinct vertex-state vectors (s, s). Although the coupled MDPs are defined on the same graph, the corresponding agents work independently to result in a pair of solutions (x, x). Then, we directly reward the deviation between the coupled solutions in terms of 1 -norm, i.e., xx 1 . Similar to the original objective of MIS, it is decomposed into rewards in each iteration of the MDP defined as follows:

R div (s, s , s, s ) = i∈ V |s i -s i |, where V = (V * \ V * ) ∪ ( V * \ V * ),

where (s , s ) denotes the next pair of vertex-states in the coupled MDP. One can observe that V denotes the most recently updated vertices in each MDP. In practice, such reward R div can be used along with the maximum entropy regularization for training the agent to achieve the best performance. See Figure 3 for an example of coupled MDP with the proposed reward. performs the following transformation on input H:

h (n) (H) = ReLU HW (n) 1 + D -1 2 AD -1 2 HW (n) 2

.

Here A, D correspond to adjacency and degree matrix of the graph G, respectively. At the final layer, the policy and value networks apply softmax function and graph readout function with sum pooling (Xu et al., 2019) instead of ReLU to generate actions and value estimates, respectively. We only consider the subgraph that is induced on the deferred vertices V * as the input of the networks since the determined part of the graph no longer affects the future rewards of the MDP. Features corresponding to the vertices are given as their node degrees and the current iteration-index of MDP.

To train the agent, proximal policy optimization (Schulman et al., 2017) is used. Specifically, networks are trained for maximizing the following objective:

L := E t min A(s (t) ) i∈V r (t) i (θ), A(s (t) ) i∈V clip(r (t) i (θ), 1 -ε, 1 + ε) , r (t) i (θ) = π θ (a (t) i |s (t) ) π θold (a (t) i |s (t) ) , A(s) = T t =t R (t ) + R (t ) div -V φ (s),

where s (t) denotes the t-th vertex-state vector and other elements of the MDP are defined similarly.

In addition, clip(•) is the clipping function for updating the agent more conservatively and θ old is the parameter of the policy network from the previous iteration of updates.

4. EXPERIMENTS:

In this section, we report experimental results on the proposed auto-deferring policy (AutoDP) described in Section 3 for solving the maximum independent set (MIS) problem. We also provide evaluation of our AutoDP framework on variants of the MIS problem in Appendix B, which demonstrates that our framework is applicable to problems different from the original MIS problem.

Experiments were conducted on a large range of graphs varying from small synthetic graphs to large-scale real-world graphs. We evaluated our AutoDP scheme by sampling multiple solutions and then reporting the performance of the best solution. The resulting schemes are coined AutoDP-10, AutoDP-100, and AutoDP-1000 corresponding to the number of samples chosen from 10, 100 and 1000, respectively. We compared our framework with the deep reinforcement learning (DRL) algorithm by Khalil et al. (2017) , coined S2V-DQN, for solving the MIS problem. Note that other DRL schemes in the literature, e.g., pointer network (Bello et al., 2016) , and attention layer (Kool et al., 2019) are not comparable since they are specialized to TSP-like problems. We additionally consider three conventional MIS solvers as baselines. First, we consider the theoretically guaranteed algorithm of Boppana & Halldórsson (1992) , 2000) , protein-protein interactions (Hamilton et al., 2017) , social networks (Yanardag & Vishwanathan, 2015) and road networks (Leskovec & Sosič, 2016) , respectively. See the appendix for more details on the datasets. The time limit of the CPLEX and ReduMIS are set to 30 seconds on ER and BA datasets and 1800 seconds on the rest of the datasets to provide comparable baselines. 3 The corresponding results are reported in Table 1 and 2. Note that the ES method was excluded from comparison in large graphs since it required a prohibitive amount of computation.

In Table 1 and 2 , one can observe that our AutoDP algorithms significantly outperform the deep reinforcement learning baseline, i.e., S2V-DQN, across all types of graphs and datasets. For example, AutoDP-10 is always able to find a better solution than S2V-DQN much faster. The gap grows larger in more challenging datasets, e.g., see Table 2 . It is also impressive to observe that our algorithm can find the best solution in seven out of ten datasets in Table 1 and four out of five datasets in Table 2. Furthermore, we observe that our algorithm achieves better objective than the CPLEX solver on ER-(100, 200) and ER-(400, 500) datasets, while consuming a smaller amount of time. The highly optimized ReduMIS solver tends to acquire the best solutions consistently. However, it is often worse than ours given a limited time budget, as described in what follows.

We investigate the trade-off between objective and time for algorithms in Figure 4 . To this end, we evaluate algorithms on ER-(400, 500) and SATLIB datasets with varying numbers of samples for AutoDP and time limits for ReduMIS and CPLEX. It is remarkable to observe that AutoDP achieves a better objective than the CPLEX solver on both datasets under reasonably limited time. Furthermore, for time limits smaller than 10 seconds, AutoDP outperforms ReduMIS on ER-(400, 500) dataset.

4.2. ABLATION STUDY:

We ablate each component of our algorithm to validate its effectiveness. We first show that "stretching" the determination with deferred MDP indeed helps for solving the MIS problem. Specifically, we experiment with varying the maximum number of iterations T in MDP by T ∈ {2, 4, 8, 16, 32} on ER-(50, 100) dataset. Figure 5a reports the corresponding training curves. We observe that the performance of AutoDP improves whenever an agent is given more time to generate the final solution, which verifies that the deferring of decisions plays a crucial role in solving the MIS problem.

Next, we inspect the contribution of the solution diversity reward used in our algorithm. To this end, we trained agents with four options: (a) without any exploration bonus, coined Base, (b) with the conventional entropy bonus (Williams & Peng, 1991) , coined Entropy, (c) with the proposed diversification bonus, coined Diverse, and (d) with both of the bonuses, coined Entropy+Diverse. The corresponding training curves for validation scores are reported in Figure 5b . We observe that the agent trained with the proposed diversification bonus outperforms other agents in terms of validation score, confirming the effectiveness of our proposed reward. One can also observe that both methods can be combined to yield better performance, i.e., Entropy+Diverse.

Finally, we further verify our claim that the maximum entropy regularization fails to capture the diversity of solutions effectively, while the proposed solution diversity reward term does. To this end, we compare the fore-mentioned agents with respect to the 1 -deviations between the coupled intermediate vertex-states s and s, defined as |{i : i ∈ V, s i = si }|. The corresponding results are shown in Figure 5c . One can observe that the entropy regularization leads to large deviations during the intermediate stages, but converges to solutions with smaller deviations. On the contrary, agents trained on diversification rewards succeed in enlarging the deviation between the final solutions. 

4.3. GENERALIZATION TO UNSEEN GRAPHS:

Now we examine the potential of our method as a generic solver, i.e., whether the algorithm's performance generalizes well to graphs unseen during training. To this end, we train AutoDP and S2V-DQN models on BA-(400, 500) dataset and evaluate them on the following real-world graph datasets: Coauthor, Amazon (Shchur et al., 2018) and Stanford Network Analysis Platform (SNAP, Leskovec & Sosič 2016) . We additionally evaluate on BA graphs with millions of vertices. We also evaluate the generalization of the algorithm across synthetic graphs with different types and sizes in Appendix D. Similar to the experiments in Table 2 , we set the time limit on CPLEX and ReduMIS by 1800 seconds. The ES method is again excluded as being computationally prohibitive to compare. As reported in Table 3 , AutoDP successfully generates solutions for large scale instances which scale up to two million (2M), even though it was trained on graphs of size smaller than five hundred vertices. Most notably, AutoDP-10 outperforms the ReduMIS (state-of-the-art solver) in BA graph with 2M vertices, but six times faster. It also outperforms the CPLEX in the graphs with more than 0.5M vertices, indicating better scalability of our algorithm. Note that CPLEX also fails to generate solutions on graphs with more than 1M vertices. Such a result strongly supports the potential of AutoDP being a generic solver that could be used in place of conventional solvers. On the contrary, we found that S2V-DQN does not generalize well to large graphs: it performs worse and takes much more time to generate solutions as it requires the number of decisions proportional to the graph size.

5. CONCLUSION:

In this paper, we propose a new reinforcement learning framework for the maximum independent set problem that is scalable to large graphs. Our main contribution is the auto-deferring policy, which allows the agent to defer the decisions on vertices for efficient expression of complex structures in the solutions. Through extensive experiments, our algorithm shows performance that is both superior to the existing reinforcement learning baseline and competitive with the conventional solvers. First, we report experimental results on solving the MWIS problem. Consider a graph G = (V, E) associated with positive weight function w : V → R + . The goal of the MWIS problem is to find the independent set I ⊆ V where the total sum of weight i∈I w(i) is maximum. Similar to the original MIS problem, the MWIS problem has many applications including signal transmission, information retrieval and computer vision (Balas & Yu, 1986) . In order to apply the AutoDP framework to the MWIS problem, we simply include the weight of each vertex as its feature to the policy network and modify the reward function by the increase in weight of included vertices, i.e., R(s, s ) = i∈V * \V * s i w(i). The weights are randomly sampled from a normal distribution with mean and standard deviation fixed to 1.0 and 0.1, respectively. We report the corresponding results in Table 4 . Here, one observes that AutoDP always achieves performance at least as good as that of CPLEX. It even achieves a better objective than CPLEX on the ER-(100, 200) and ER-(400, 500) datasets while using a smaller amount of time. Such a result confirms that our framework is generalizable to the WMIS problem. Next, we introduce the PCMIS problem. To this end, consider a graph G = (V, E) and a subset of vertices I ⊆ V. Then PCMIS problem is associated with the following the "prize" function f to maximize:

f ( I) := | I| -λ|{{i, j} : i, j ∈ I, i = j}|,

where λ > 0 is the penalty function for including two adjacent vertices. We set λ = 0.5 in the experiments. Such a problem could be interpreted as relaxing the hard constraints on independent set to a penalty function in the MIS problem. Especially, one can examine that optimal solution of the PCMIS problem becomes the maximum independent set when λ > 1. The PCMIS problem also corresponds to an instance of the generalized minimum vertex cover problem (Hassin & Levin, 2006) .

For applying the AutoDP framework on the PCMIS problem, we remove the clean-up phase in the transition function of MDP and modify the reward function R(s, s ) as the increase in prize function at each iteration, expressed as follows:

R(s, s ) :

= i∈V * \V * s i -λ i∈V * \V * j∈V * \V * \{i} 1 2 s i s j + j∈V\V * s i s j .

We report the corresponding results in Table 5 . Here, one observes that AutoDP underperforms compared to the CPLEX at smaller graphs, but eventually outperforms it on ER-(100, 200) and ER-(400, 500) datasets. Especially, CPLEX shows underwhelming performance on the ER-(400, 500) dataset. We hypothesize this observation to arise from the fact that the PCMIS problem is modeled as a hard integer quadratic programming. Note that the MIS problem was previously modeled by CPLEX as an integer linear programming, which is easier to solve.

C ADDITIONAL COMPARISON TO SUPERVISED LEARNING:

In this section, we additionally report the performance of the supervised learning framework for the MIS problem proposed by Li et al. (2018) , coined GTS, evaluated on the ER datasets used in Section 4.1. To this end, two types of models trained from the GTS framework are considered. First, we consider the GTS trained on ER graphs, coined GTS-ER. For supervision, we generate solutions of 2000 graphs from the corresponding ER datasets using ReduMIS. Note that the training scheme for GTS-ER was designed to match the computational requirement of GTS-ER and AutoDP. For example, it takes 16 and 8 hours to generate solutions and train the models for GTS-ER on the ER-(400, 500) dataset. AutoDP takes 24 hours to train the model on the same dataset. In addition, we consider the model trained on the SATLIB dataset with 38 000 graphs, coined GTS-SATLIB. This model was obtained from the code provided by Li et al. (2018) . 4 We use the default hyperparameters from the et al., 2017), based on the Adam optimizer with a learning rate of 0.0001. The validation dataset was used for choosing the best performing model while using 10 samples for evaluating the performance. Reward was not decayed throughout the episodes of the Markov decision process. Gradient norms were clipped by a value of 0.5. We further provide details specific to each type of datasets in Table 8 .

For the compared baselines, we used the default hyper-parameters provided in the respective codes. Baselines. We implemented the S2V-DQN algorithm based on the code (written in C++) provided by the authors. 5 For ER and BA models, S2V-DQN was unstable to be trained on graphs of size from (100, 200) and (400, 500) without pre-training. Instead, we performed fine-tuning as mentioned in the original paper (Khalil et al., 2017) . 2 , we were unable to train on the raw graph under available computational budget. Hence we trained S2V-DQN on subgraphs sampled from the training graphs. To this end, we sampled edges from the model uniformly at random without replacement, until the number of vertices reach 300. Then we used the subgraph induced from the sampled vertices. We run ES algorithm based on NetworkX package. 6Next, we use CPLEX (ILO, 2014) provided on the official homepage. 7 We set the optimality gap used for the stopping criterion to 10 -4 . For comparison, we also report the performance of CPLEX for other values of the optimality gap is in Table 9 . Finally, we use the ReduMIS algorithm implemented in the code provided by the authors.8 Note that our implementation of ReduMIS is different from the original work (Lamm et al., 2017) since it employs a better graph kernelization technique (Hespe et al., 2019) .

F DATASET DETAILS:

In this section, we provide additional details on the datasets used for the experiments.

ER and BA datasets. For the ER and BA datasets, we train on graphs randomly generated on the fly and perform validation and evaluation on a fixed set of 1000 graphs.

SATLIB dataset. The SATLIB dataset is a popular benchmark for evaluating SAT algorithms. We specifically use the synthetic problem instances from the category of random 3-SAT instances with controlled backbone size (Singer et al., 2000) . Next, we describe the procedure for reducing the SAT instances to MIS instances. To this end, a vertex is added to the graph for each literal of the SAT instance. Then edges are added for each pair of vertices satisfying the following conditions: (a) that are in the same clause or (b) they correspond to the same literals with different signs. Consequently, the MIS in the resulting graph corresponds to the truth assignment to the optimal assignments of the SAT problem (Dasgupta et al., 2008) .

PPI dataset. The PPI dataset is the protein-protein-interaction dataset with vertices representing proteins and edges representing interactions between them.

REDDIT datasets. The REDDIT (BINARY, MULTI-5K, MULTI-12K) datasets are constructed from online discussion threads in reddit9 where vertices represent users and edges mean at least one of two users responded to the other user's comment.

Autonomous system dataset. The as-Caida dataset is a set of autonomous system graphs derived from a set of RouteViews BGP table snapshots (Leskovec et al., 2005) .

Citation dataset. The Cora and the Citeseer are networks constructed by vertices and edges representing documentation and citation links between them, respectively (Sen et al., 2008) .

Amazon dataset. The Computers and Photo graphs are segmented from the Amazon co-purchase graph (McAuley et al., 2015) , where vertices correspond to goods and edges represent goods which are frequently purchased together.

Coauthor dataset. The CS and Physics graphs represent authors and the corresponding coauthorships by vertices and edges, respectively. It was collected from Microsoft Academic Graph from the KDD Cup 2016 challenge3.10 

:

Note that CPLEX is able to provide proof of optimality in addition to the solution for the MIS problem.

The authors of S2V-DQN only reported experiments with respect to graphs of size up to five hundred.

The solvers occasionally violate the time limit due to their pre-solving process.

https://github.com/intel-isl/NPHard

https://github.com/Hanjun-Dai/graph_comb_opt

https://networkx.github.io/

https://www.ibm.com/products/ilog-cplex-optimization-studio

http://algo2.iti.kit.edu/kamis/

https://www.reddit.com/

https://kddcup2016.azurewebsites.net/

Figures and Tables:

Figure 1: Illustration of the proposed Markov decision process.

Figure 2: Illustration of the transition function with the update and the clean-up phases.

Figure 3: Illustration of coupled MDP with the corresponding solution diversity reward.

Figure 4: Evaluation of trade-off between time and objective (upper-left side is of better trade-off).

Figure 5: Illustration of ablation studies done on ER-(50, 100) dataset. The solid line and shaded regions represent the mean and standard deviation across 3 runs respectively Note that the standard deviation in (c) was enlarged ten times for better visibility.

First, for the ER-(100, 200) and BA-(100, 200) datasets, we finetuned the model trained on ER-(50, 100) and BA-(50, 100), respectively. Next, for the ER-(400, 500) and BA-(400, 500) datasets, we performed "curriculum learning", e.g., a model was first trained on the ER-(50, 100) dataset, then fine-tuned on the ER-(100, 200), ER-(200, 300), ER-(300, 400) and ER-(400, 500) in sequence. Finally, for training S2V-DQN on large graphs used in Table

Our algorithm is based on actor-critic training with policy network π θ (a|s) and value network V φ (s) parameterized by the graph convolutional network (GCN, Kipf & Welling 2017). Each GCN consists of multiple layers h n with n = 1, • • • , N where the n-th layer with weights W

Table content: <table><tr><td>(n) 1 and W 2 (n)</td></tr></table>

based on iterative exclusion of subgraphs, coined ES, having an approximation ratio O(|V|/(log |V|) 2 ) for the MIS problem. Next, we consider the integer programming solver IBM ILOG CPLEX Optimization Studio V12.9.0 (ILO, 2014), coined CPLEX.1  We also consider the MIS heuristic proposed byLamm et al. (2017), coined ReduMIS. Note that we use the implementation of ReduMIS equipped with graph kernelization proposed byHespe et al. (2019). We additionally provide evaluation of the AudoDP framework compared to the supervised learning framework ofLi et al. (2018) in Appendix C. Further details of the implementation and datasets are provided in Appendix E and F, respectively. Performance evaluation on ER and BA datasets. The bold numbers indicate the best performance within the same category of algorithms. The relative differences shown in brackets are measured with respect to S2V-DQN.

Table content: <table><tr><td>4.1 PERFORMANCE</td></tr></table>

Performance evaluation on SATLIB, PPI, REDDIT, and as-Caida datasets. The bold numbers indicate the best performance within the same category of algorithms. The relative differences shown in brackets are measured with respect to S2V-DQN, except for the case of as-Caida dataset where S2V-DQN underperforms significantly. 2 , the edge ratio of ER graphs and average degree of BA graphs are set to 0.15 and 8, respectively. Datasets are specified by their type of model and an interval for choosing the number of vertices uniformly at random, e.g., ER-(50, 100) denotes the set of ER graphs generated with the number of vertices larger than 50 and smaller than 100. Next, we consider experiments on more challenging datasets with larger sizes, namely the SATLIB, PPI, REDDIT, and as-Caida datasets constructed from SATLIB benchmark (Hoos & Stützle

Table content: <table><tr><td/><td/><td colspan="2">Traditional</td><td/><td/><td>DRL-based</td><td/></tr><tr><td>Type</td><td>|V|</td><td>Value CPLEX</td><td>ReduMIS</td><td>S2V-DQN</td><td>AutoDP-10</td><td>AutoDP-100</td><td>AutoDP-1000</td></tr><tr><td>SATLIB</td><td>(1209, 1347)</td><td>Obj. Time 9.490 426.8</td><td>426.9 30.110</td><td>413.8 2.260</td><td colspan="2">423.8 (+2.4%) 0.311 (-86.2%) 1.830 (-19.0%) 424.8 (+2.7%)</td><td>425.4 (+2.8%) 16.409 (+626.1%)</td></tr><tr><td>PPI</td><td>(591, 3480)</td><td>Obj. Time 24.685 1147.5</td><td>1147.5 30.23</td><td>893.0 6.285</td><td colspan="2">1144.5 (+28.2%) 1146.5 (+28.4%) 0.786 (-87.5%) 1.770 (-71.8%)</td><td>1147.0 (+28.4%) 11.469 (+82.3%)</td></tr><tr><td>REDDIT (MULTI-5K)</td><td>(22, 3648)</td><td>Obj. Time 0.008 370.6</td><td>370.6 0.159</td><td>370.1 0.076</td><td colspan="3">370.6 (+0.1%) 370.6 (+0.1%) 0.071 (-6.6%) 0.551 (+625.0%) 5.500 (+7136.8%) 370.6 (+0.1%)</td></tr><tr><td colspan="2">REDDIT (MULTI-12K) (2, 3782)</td><td>Obj. Time 0.007 303.5</td><td>303.5 0.188</td><td>302.8 1.883</td><td colspan="2">257.4 (-15.0%) 292.6 (-3.4%) 0.003 (-99.8%) 0.025 (-98.7%)</td><td>303.5 (+0.2%) 0.451 (-76.1%)</td></tr><tr><td>REDDIT (BINARY)</td><td>(6, 3782)</td><td>Obj. Time 0.007 329.3</td><td>329.3 0.306</td><td>328.6 0.055</td><td colspan="3">329.3 (+0.2%) 329.3 (+0.2%) 0.020 (-63.6%) 0.173 (+214.6%) 2.627 (+4676.4%) 329.3 (+0.2%)</td></tr><tr><td>as-Caida</td><td>(8020, 26 475)</td><td colspan="2">Obj. Time 0.477 20 049.2 20 049.2 1.719</td><td>324.0 601.351</td><td>20 049.2 0.812</td><td>20 049.2 6.106</td><td>20 049.2 62.286</td></tr><tr><td>et al. (2017)</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Performance evaluation for large-scale graphs. Out of budget (OB) is marked for runs violating the time and the memory budget of 10 000 seconds and 32 GB RAM, respectively. The bold numbers indicate the best performance within the same category of algorithms. The relative differences shown in brackets are measured with respect to S2V-DQN.

Table content: <table><tr><td/><td/><td/><td colspan="2">Traditional</td><td/><td/><td>DRL-based</td><td/></tr><tr><td>Type</td><td>|V|</td><td colspan="3">Value CPLEX ReduMIS</td><td>S2V-DQN</td><td>AutoDP-10</td><td>AutoDP-100</td><td>AutoDP-1000</td></tr><tr><td>BA</td><td>1 000 000 2 000 000</td><td colspan="3">Obj. Time 5967.82 1802.35 434 896 457 349 Obj. OB 909 988 Time 4276.43</td><td>OB OB</td><td>457 753 324.02 915 553 772.18</td><td>457 772 5112.25 915 573 7662.87</td><td>OB OB</td></tr><tr><td>Citation (Cora)</td><td>2708</td><td colspan="2">Obj. Time 0.08 1451</td><td>1451 0.04</td><td>1393 2.57</td><td>1451 (+4.2%) 1.63 (-36.5%)</td><td>1451 (+4.2%) 2.71 (+5.3%)</td><td>1451 (+4.2%) 13.82 (+437.7%)</td></tr><tr><td>Citation (Citeseer)</td><td>3327</td><td colspan="2">Obj. Time 0.08 1867</td><td>1867 0.03</td><td>1840 3.07</td><td>1867 (+1.5%) 1.80 (-41.4%)</td><td>1867 (+1.5%) 2.74 (-10.9%)</td><td>1867 (+1.5%) 19.00 (+518.4%)</td></tr><tr><td>Amazon (Photo)</td><td>7487</td><td colspan="2">Obj. Time 38.80 2733</td><td>2733 39.02</td><td>725 66.53</td><td colspan="3">2705 (+273.1%) 2708 (+273.5%) 2712 (+274.1%) 2.00 (-97.0%) 4.91 (-92.6%) 32.96 (-50.5%)</td></tr><tr><td>Amazon (Computers)</td><td>13 381</td><td colspan="2">Obj. Time 188.61 4829</td><td>4829 61.78</td><td>1281 235.80</td><td colspan="3">4773 (+272.6%) 4782 (+273.3%) 4783 (+273.4%) 3.02 (-98.7%) 8.63 (-96.3%) 79.19 (-66.4%)</td></tr><tr><td>Coauthor (CS)</td><td>18 333</td><td colspan="2">Obj. Time 1.50 7506</td><td>7506 0.09</td><td>6635 197.39</td><td>7479 (+12.7%) 3.03 (-98.5%)</td><td>7479 (+12.7%) 13.23 (-93.3%)</td><td>7483 (+12.8%) 122.44 (-38.0%)</td></tr><tr><td>Coauthor (Physics)</td><td>34 493</td><td colspan="2">Obj. Time 1802.80 11 351</td><td>11 353 81.34</td><td>2156 1564.13</td><td colspan="3">11 176 (+418.4%) 11 186 (+418.8%) 11 190 (+419.0%) 8.63 (-99.5%) 38.71 (-97.5%) 385.93 (-75.3%)</td></tr><tr><td>SNAP (web-Stanford)</td><td>281 903</td><td colspan="2">Obj. Time 996.25 163 385</td><td>163 391 44.85</td><td>OB</td><td>160 784 13.35</td><td>160 837 137.98</td><td>160 872 1357.11</td></tr><tr><td colspan="2">SNAP (web-NotreDame) 325 729</td><td colspan="2">Obj. Time 64.97 251 846</td><td>251 850 1802.34</td><td>OB</td><td>250 365 11.81</td><td>250 384 119.48</td><td>250 409 1046.48</td></tr><tr><td>SNAP (web-BerkStan)</td><td>685 230</td><td colspan="2">Obj. Time 1875.96 125 194</td><td>408 483 100.17</td><td>OB</td><td>403 166 88.67</td><td>403 189 975.35</td><td>403 231 9940.93</td></tr><tr><td>SNAP (soc-Pokec)</td><td>1 632 803</td><td>Obj. Time</td><td>OB</td><td>788 907 1805.95</td><td>OB</td><td>784 843 770.55</td><td>784 891 7512.06</td><td>OB</td></tr><tr><td>SNAP (wiki-topcats)</td><td>1 791 489</td><td>Obj. Time</td><td>OB</td><td>986 180 1060.09</td><td>OB</td><td>958 980 850.80</td><td>959 051 9121.85</td><td>OB</td></tr></table>

Performance evaluation on the MWIS problem for the ER datasets. The bold numbers indicate the algorithm with the best performance. The relative differences shown in brackets are measured with respect to CPLEX.

Table content: <table><tr><td>Type</td><td>|V|</td><td>Value</td><td>CPLEX</td><td>AutoDP-10</td><td>AutoDP-100</td><td>AutoDP-1000</td></tr><tr><td/><td>(15, 20)</td><td>Obj. Time</td><td>9.00 0.013</td><td colspan="3">9.00 (-0.0%) 0.003 (-76.9%) 0.006 (-53.8%) 0.045 (+246.2%) 9.00 (-0.0%) 9.00 (-0.0%)</td></tr><tr><td/><td>(40, 50)</td><td>Obj. Time</td><td>16.86 0.083</td><td colspan="3">16.82 (-0.2%) 0.006 (-92.8%) 0.019 (-77.1%) 0.168 (+102.4%) 16.86 (-0.0%) 16.86 (-0.0%)</td></tr><tr><td>ER</td><td>(50, 100)</td><td>Obj. Time</td><td>21.46 0.159</td><td colspan="3">21.29 (-0.8%) 0.013 (-91.8%) 0.038 (-76.1%) 0.316 (+98.7%) 21.44 (-0.1%) 21.46 (-0.0%)</td></tr><tr><td/><td>(100, 200)</td><td>Obj. Time</td><td colspan="4">28.41 12.357 0.040 (-99.7%) 0.098 (-99.2%) 0.699 (-94.3%) 28.09 (-1.1%) 28.39 (-0.1%) 28.45 (+0.1%)</td></tr><tr><td/><td>(400, 500)</td><td>Obj. Time</td><td colspan="4">37.66 30.083 0.277 (-99.1%) 0.537 (-98.2%) 3.025 (-89.9%) 38.08 (+1.1%) 39.21 (+4.1%) 39.99 (+6.2%)</td></tr></table>

Performance evaluation on the PCMIS problem for the ER datasets. The bold numbers indicate the algorithm with the best performance. The relative differences shown in brackets are measured with respect to CPLEX.

Table content: <table><tr><td>Type</td><td>|V|</td><td>Value</td><td>CPLEX</td><td>AutoDP-10</td><td>AutoDP-100</td><td>AutoDP-1000</td></tr><tr><td/><td>(15, 20)</td><td>Obj. Time</td><td>10.54 0.014</td><td>10.53 (-0.1%) 0.002 (-85.7%)</td><td>10.53 (-0.1%) 0.004 (-71.4%)</td><td>10.53 (-0.1%) 0.019 (+35.7%)</td></tr><tr><td/><td>(40, 50)</td><td>Obj. Time</td><td>17.94 0.217</td><td>17.64 (-1.7%) 0.004 (-98.2%)</td><td>17.68 (-1.4%) 0.006 (-97.2%)</td><td>17.71 (-1.3%) 0.032 (-85.3%)</td></tr><tr><td>ER</td><td>(50, 100)</td><td>Obj. Time</td><td>22.64 1.829</td><td>21.66 (-4.0%) 0.002 (-99.9%)</td><td>21.77 (-3.8%) 0.008 (-99.5%)</td><td>21.84 (-3.5%) 0.069 (-96.2%)</td></tr><tr><td/><td>(100, 200)</td><td>Obj. Time</td><td colspan="2">27.12 29.837 0.019 (-99.9%) 29.17 (+7.6%)</td><td>29.56 (+9.0%) 0.107 (-99.6%)</td><td>29.69 (+9.5%) 0.958 (-96.8%)</td></tr><tr><td/><td>(400, 500)</td><td>Obj. Time</td><td colspan="4">4.56 30.122 0.068 (-99.7%) 37.17 (+715.1%) 38.39 (+741.8%) 39.41 (+764.3%) 0.421 (-98.6%) 3.956 (-86.9%)</td></tr><tr><td colspan="5">B.1 MAXIMUM WEIGHTED INDPENDENT SET PROBLEM</td><td/><td/></tr></table>

Additional evaluation of the supervised learning (SL) based framework on ER datasets. The bold numbers indicate the best performance within the same category of algorithms. The relative differences shown in brackets are measured with respect to the best performing SL-based model.

Table content: <table><tr><td/><td/><td/><td/><td>SL-based</td><td/><td colspan="2">DRL-based</td></tr><tr><td>Type</td><td>|V|</td><td>Value</td><td colspan="2">GTS-ER GTS-SATLIB</td><td>S2V-DQN</td><td>AutoDP-10</td><td>AutoDP-100</td><td>AutoDP-1000</td></tr><tr><td/><td>(15, 20)</td><td>Obj. Time</td><td>8.829 1.707</td><td>8.838 1.749</td><td>8.840 0.004</td><td colspan="3">8.844 (+0.1%) 8.844 (+0.1%) 8.844 (+0.1%) 0.002 (-99.9%) 0.005 (-99.7%) 0.056 (-96.8%)</td></tr><tr><td/><td>(40, 50)</td><td>Obj. Time</td><td>16.46 2.660</td><td>16.47 3.583</td><td>16.42 0.015</td><td colspan="3">16.55 (+0.5%) 0.004 (-99.9%) 0.016 (-99.6%) 0.164 (-95.4%) 16.57 (+0.6%) 16.57 (+0.6%)</td></tr><tr><td>ER</td><td>(50, 100)</td><td>Obj. Time</td><td>20.70 3.222</td><td>20.83 3.914</td><td>20.61 3.767</td><td colspan="3">21.04 (+1.0%) 0.007 (-99.8%) 0.028 (-99.4%) 0.283 (-92.8%) 21.10 (+1.2%) 21.11 (+1.3%)</td></tr><tr><td/><td>(100, 200)</td><td>Obj. Time</td><td>26.17 6.846</td><td>26.11 4.964</td><td>26.27 0.078</td><td colspan="3">27.67 (+5.6%) 0.029 (-99.6%) 0.085 (-98.8%) 0.666 (-90.3%) 27.87 (+6.5%) 27.93 (+6.7%)</td></tr><tr><td/><td>(400, 500)</td><td>Obj. Time</td><td>36.48 10.598</td><td>34.99 8.609</td><td>35.05 0.633</td><td colspan="3">38.29 (+5.0%) 0.158 (-98.5%) 0.407 (-96.2%) 2.768 (-73.9%) 39.11 (+7.2%) 39.54 (+8.4%)</td></tr><tr><td colspan="7">B.2 PRIZE COLLECTING MAXIMUM INDEPENDENT SET PROBLEM</td><td/></tr></table>

Choice of hyperparameters for the experiments on performance evaluation.

Table content: <table><tr><td>The REDDIT</td></tr></table>

Performance comparison of CPLEX with different optimality gap used for the stopping criterion.

Table content: <table><tr><td/><td/><td/><td colspan="2">Optimality gap</td><td/><td/></tr><tr><td>Type</td><td>|V|</td><td>Value</td><td>10 -4</td><td>10 -3</td><td>10 -2</td><td>10 -1</td></tr><tr><td/><td>(15, 20)</td><td>Obj. Time</td><td>8.84 0.003</td><td>8.84 0.003</td><td>8.84 0.004</td><td>8.84 0.003</td></tr><tr><td/><td>(40, 50)</td><td>Obj. Time</td><td>16.57 0.062</td><td>16.57 0.064</td><td>16.57 0.063</td><td>16.43 0.043</td></tr><tr><td>ER</td><td>(50, 100)</td><td>Obj. Time</td><td>21.11 0.137</td><td>21.11 0.141</td><td>21.11 0.141</td><td>20.938 0.138</td></tr><tr><td/><td>(100, 200)</td><td>Obj. Time</td><td colspan="4">27.87 10.748 11.008 10.917 9.888 27.87 27.87 27.81</td></tr><tr><td/><td>(400, 500)</td><td>Obj. Time</td><td colspan="4">35.76 30.085 30.090 30.083 30.089 35.72 35.73 35.74</td></tr></table>

Number of nodes, edges and graphs for each dataset used in the Table 2. Number of graphs is expressed as a tuple of the numbers of training, validation and test graphs, respectively.

Table content: <table><tr><td>Dataset</td><td colspan="2">Number of nodes Number of edges</td><td>Number of graphs</td></tr><tr><td>SATLIB</td><td>(1209, 1347)</td><td>(4696, 6065)</td><td>(38 000, 1000, 1000)</td></tr><tr><td>PPI</td><td>(591, 3480)</td><td>(3854, 53 377)</td><td>(20, 2, 2)</td></tr><tr><td>REDDIT (BINARY)</td><td>(6, 3782)</td><td>(4, 4071)</td><td>(1600, 200)</td></tr><tr><td>REDDIT (MULTI-5K)</td><td>(22, 3648)</td><td>(21, 4783)</td><td>(4001, 499, 499)</td></tr><tr><td>REDDIT (MULTI-12K)</td><td>(2, 3782)</td><td>(1, 5171)</td><td>(9545, 1192, 1192)</td></tr><tr><td>as-Caida</td><td>(8020, 26 475)</td><td>(36 406, 106 762)</td><td>(108, 12, 12)</td></tr></table>

Peer review (iclr2020):
The paper introduces auto-deferring policies (ADPs) for deep reinforcement learning (RL). ADPs automatically stretching or shrinking their decision process, in particular, deciding whether to finalize the value of each vertex at the current stage or defer to determine it at later stages. ADPs are evaluated on maximum independent set problems. The paper is in principle well written and structured. Some statements of the paper appear a little bit too strong. For instance, saying that deep RL approaches *can automatically learn the design of a good solver without using any sophisticated knowledge or hand-crafted heuristic specialized for the target problem* is misleading as thee designer of the RL setup is putting a lot of knowledge into the design. Likewise the statement *without any human guidance* is not true, at least at the current stage. It would be great to acknowledge this by softening this statement. The basic idea is also fine, learning to expand or not nodes in the current fringe of the combinatorial solver. However, being an informed outsider, I would like to understand more why encoding NP-hard problem using an (discrete, finite) MDP, which is rather efficient to solve, is a good idea. Moreover, while the focus on MIS is justified in the paper, showing the (potential) benfit on other tasks such as TSP is useful to convince the reader that ADPs apply across different problem classes. Without, it is not clear whether ADPs work fine on other problem classes (even if one may expect that this is the case). Anyhow, the main idea of implementing two independent agents/networks to implement a reward signal that rewards deviation is interesting. Moreover, the experimental results show that the approach works. It actually manages to be on par with ReduMIS. However, it does not really improve upon this well-known heuristic. Hence some experiments across different problems would really be beneficial. Without, it is just interesting to see that RL can also come up with good heuristics but the existing heuristic already works pretty well. To sum up, a very nice idea that shows promise but experiments on other problems is missing for a complete picture. Also some statements should be soften.