Year: 2019

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.

text: 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 Barabási-Albert graph with two million vertices.

heading: 1 INTRODUCTION
text: 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 Erdös-Rényi (Erdős & Rényi, 1960) model, the Barabási-Albert (Albert & Barabási, 2002) model, the SATLIB (Hoos & Stützle, 2000) benchmark and real-world graphs (Hamilton et al., 2017; Yanardag & Vishwanathan, 2015; Leskovec & Sosič, 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 Barabá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.

heading: 2 RELATED WORKS
text: 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 & Halldó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.

heading: 3 DEEP AUTO-DEFERRING POLICY
text: 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 = [xi : i ∈ V] ∈ {0, 1}V with maximum possible cardinality∑ i∈V xi, where each element xi indicates the membership of vertex i in the independent set I, i.e., xi = 1 if and only if i ∈ I. Initially, the algorithm has no assumption about its output, i.e., both xi = 0 and xi = 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 xi = 0 or xi = 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.

heading: 3.1 DEFERRED MARKOV DECISION PROCESS
text: 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 = [si : i ∈ V] ∈ {0, 1, ∗}V , where the vertex i ∈ V is determined to be excluded or included in the independent set whenever
si = 0 or si = 1, respectively. Otherwise, si = ∗ 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., si = ∗ 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∗ = [ai : i ∈ V∗] ∈ {0, 1, ∗}V∗ where V∗ denotes a set of current deferred vertices, i.e., V∗ = {i : i ∈ V, xi = ∗}. Transition. Given two consecutive states s, s′ and the corresponding assignment a∗, the transition Pa∗(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 = ai if i ∈ V∗ and ŝi = si 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.

heading: 3.2 TRAINING WITH DIVERSIFICATION REWARD
text: 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., ‖x− x̄‖1. Similar to the original objective of MIS, it is decomposed into rewards in each iteration of the MDP defined as follows:
Rdiv(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 Rdiv 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.
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 hn with n = 1, · · · , N where the n-th layer with weights W(n)1 and W (n) 2 performs the following transformation on input H:
h(n)(H) = ReLU ( HW
(n) 1 + D − 12AD− 1 2HW (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 := Et [ 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.

heading: 4 EXPERIMENTS
text: 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 AutoDP10, 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 & Halldórsson (1992) 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 by Lamm et al. (2017), coined ReduMIS. Note that we use the implementation of ReduMIS equipped with graph kernelization proposed by Hespe et al. (2019). We additionally provide evaluation of the AudoDP framework compared to the supervised learning framework of Li et al. (2018) in Appendix C. Further details of the implementation and datasets are provided in Appendix E and F, respectively.

heading: 4.1 PERFORMANCE EVALUATION
text: We now demonstrate the performance of our algorithm along with other baselines on various datasets. First, we consider experiments on randomly generated synthetic graphs from the Erdös-Rényi (ER, Erdős & Rényi 1960) and Barabási-Albert (BA, Albert & Barabási 2002) models. Following Khalil
1Note that CPLEX is able to provide proof of optimality in addition to the solution for the MIS problem. 2 The authors of S2V-DQN only reported experiments with respect to graphs of size up to five hundred.
et al. (2017), 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 & Stützle, 2000), protein-protein interactions (Hamilton et al., 2017), social networks (Yanardag & Vishwanathan, 2015) and road networks (Leskovec & Sosič, 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
3 The solvers occasionally violate the time limit due to their pre-solving process.
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.

heading: 4.2 ABLATION STUDY
text: 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, si 6= s̄i}|. 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.

heading: 4.3 GENERALIZATION TO UNSEEN GRAPHS
text: 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 & Sosič 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.

heading: 5 CONCLUSION
text: 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.

heading: A GRAPHICAL ILLUSTRATION OF AUTODP
text: B VARIANTS OF THE MAXIMUM INDEPENDENT SET PROBLEM
In this section, we provide experimental results of the proposed AutoDP framework on variants of the original MIS problem. From the empirical results, we show that the AutoDP framework is flexible enough to be trained even when some settings of the original MIS problem are modified. To this end, we consider two variants of the MIS problem: the maximum weighted independent set (MWIS) problem and the prize collecting maximum independent set (PCMIS) problem. We compare our algorithm to the generic integer programming solver CPLEX. Note that the ReduMIS and the ES considered in Section 4 are unavailable for comparison on such variants of the MIS problem. Experiments are conducted on the ER graphs with varying sizes of graphs as in Section 4.1.
B.1 MAXIMUM WEIGHTED INDPENDENT SET PROBLEM
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′iw(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.
B.2 PRIZE COLLECTING MAXIMUM INDEPENDENT SET 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 6= 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′is ′ j + ∑ j∈V\V∗ s′is ′ 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.

heading: C ADDITIONAL COMPARISON TO SUPERVISED LEARNING
text: 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
4https://github.com/intel-isl/NPHard
authors, e.g., graph convolutional networks are built with 20 layers and channel size of 32. For the evaluation of models from GTS, the performance of the best solutions among 1000 samples were reported. We also note that Li et al. (2018) optionally introduced a “classic element” of introducing local search and graph reduction between intermediate decisions. Although such an idea is applicable to all of GTS, AutoDP and S2V-DQN, we disable it to compare the vanilla performance of the supervised and the reinforcement learning frameworks.
The corresponding comparisons are reported in Table 6. Here, one observes that AutoDP performs better than the GTS algorithms even though they additionally require solutions to the MIS problem on the training graphs. It is also interesting to observe that GTS-SATLIB underperforms compared to GTS-ER in the ER-(100, 200) and the ER-(400, 500) datasets even though they were trained using much more graphs. We hypothesize that such a gap comes from the GTS-SATLIB failing to generalize on unseen graphs.

heading: D GENERALIZATION BETWEEN SYNTHETIC GRAPHS
text: In this section, we report experiments on generalization between ER and BA graphs, where we evaluate the generalization capability of our method on different types and sizes of graphs from the training dataset. As shown in Table 7, our algorithm generalizes excellently across different sizes of graphs, e.g., the model trained on BA-(50, 100) dataset achieves the best performance even on BA-(400, 500) dataset. On the other side, models evaluated on unseen types of graphs tend to work slightly worse as expected. However, the results are still remarkable, e.g., the model trained on ER-(40, 50) dataset almost achieves the best score in BA-(400, 500) dataset.
E IMPLEMENTATION DETAILS
In this section, we provide additional details for our implementation of the experiments.
Normalization of feature and reward. The iteration-index of MDP used for input of the policy and value networks was normalized by the maximum number of iterations. Furthermore both the MIS objective and the solution diversification rewards were normalized by maximum number of vertices in the corresponding dataset.
Hardware. Computations for our method and S2V-DQN were done on an NVIDIA RTX 2080Ti GPU and an NVIDIA TITAN X Pascal GPU, respectively. Experiments for ES, CPLEX, and ReduMIS were run in AWS EC2 c5 instances with Intel Xeon Platinum 8124M CPU. We additionally let the CPLEX use 16 CPU cores as it allows multi-processing.
Hyper-parameter. Every hyper-parameter was optimized on a per graph type basis and used across all sizes within each graph type. Throughout every experiment, policy and value networks were parameterized by graph convolutional network with 4 layers and 128 hidden dimensions. Every instance of the model was trained for 20000 updates of proximal policy optimization (Schulman
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.

heading: F DATASET DETAILS
text: 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,
5https://github.com/Hanjun-Dai/graph_comb_opt 6https://networkx.github.io/ 7https://www.ibm.com/products/ilog-cplex-optimization-studio 8http://algo2.iti.kit.edu/kamis/
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
9https://www.reddit.com/ 10https://kddcup2016.azurewebsites.net/
Web network datasets. The web-NotreDame, web-Stanford, and web-BerkStan are graphs with vertices represent web-pages obtained from the University of Notre Dame, Stanford University, and Berkeley & Stanford University domains, respectively (Leskovec & Sosič, 2016). Edge is added for each pair of web-pages with links between them.
Social network dataset. The soc-Pokec is a graph representing friendships between users from a social network in Slovakia (Takac & Zabovsky, 2012).
Wikipedia network dataset. The wiki-topcats graph is constructed by collecting connected pages which belong to top categories containing at least 100 pages, starting from the most connected component of Wikipedia (Klymko et al., 2014).
We further provide the statistics of the dataset used in experiments corresponding to Table 2 and 3 in Table 10 and 11, respectively.

Review summaries:
This paper aims at solving graph-based combinatorial optimization problems using a new paradigm for Deep Reinforcement Learning. In contrast with standard Markov Decision Processes used for combinatorial DRL, the authors advocate the use of “deferred” MDPs capturing more complex actions (which can choose a subset of nodes), and more sophisticated transitions, which combine an update phase together with a cleanup phase. For the DRL architecture, an Actor-Critic framework is trained using a proximal policy optimization approach. The paper specifically focuses on the Maximum Independent Set (MIS) problem. Comparative results on various instances reveal that this approach clearly outperforms the S2V-DQN algorithm and is competitive with some usual combinatorial solvers (CPLEX, ReduMIS).

The paper proposes a Deep RL approach called Auto-Deferring Policy (ADP) to learning a policy for constructing solutions for the Maximum Independent Set (MIS) problem. Rather than constructing a solution one variable per episode step, the policy can make decisions about multiple variables per step, as well as defer decisions to later steps. At each step the MIS constraints of a valid solution are checked and decisions that violate the constraints are reverted, and any additional decisions that are automatically implied by the decisions so far and the MIS constraints are taken. The policy and value function are parameterized as a graph convolutional network to make use of the graph structure of the problem. A diversity regularizer that encourages the policy to generate diverse final solutions is used for training. Results show that the approach is able to match the objective value of the state-of-the-art solvers on several datasets, and is able to outperform S2V-DQN on several datasets when neither approach is trained on them.