Deep Auto-Deferring Policy for Combinatorial Optimization
Authors: Sungsoo Ahn
Younggyo Seo
Jinwoo Shin
Venue:  (2020)
Keywords: deep reinforcement learning
combinatorial optimization

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 learn the design of a good solver without using any sophisticated knowledge or hand-crafted heuristic specialized for 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 (ADP), 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 ADP framework to the maximum independent set (MIS) problem, a prototype of NP-complete problems, under various scenarios. Our experimental results demonstrate significant improvement of ADP 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 state-of-the-art solvers specialized for MIS, e.g., ADP outperforms them for some graphs with millions of vertices. 

Under review as a conference paper at ICLR 2020
DEEP AUTO-DEFERRING POLICY FOR APPROXIMATING MAXIMUM INDEPENDENT SETS
Anonymous authors Paper under double-blind review
ABSTRACT
Designing efficient algorithms for combinatorial optimization appears ubiquitously in various scientific fields. Recently, deep reinforcement learning (DRL) frame- works have gained considerable attention as a new approach: they can automatically train good solver while relying less on sophisticated domain knowledge of the target problem. However, the number of stages (until reaching the final solution) re- quired by existing DRL solvers is proportional 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-Alle Albert graph with two million vertices.
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 lcarning- 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 fully unsupervised manner, potentially outperforming those based on -peaiff 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 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

---

Under review as a conference paper at ICLR 2020
rachodad
state
ixceaed
dedereed
available
solutions
Figure 1: Illustration of the proposed Markov decision process.
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 DRI-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-forwad 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 new scalable DRL framework, coined auto-deferring policy (AutoDP), designed towards solving combinatorial problems on large graphs. We particularly focus applying AutoDP to the MIS problem (and its variants) which attempts to find 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 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 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 for illustration). Inspired by the celebrated survey propagation (Braunstein et al., 2005) for solving the SAT problem, AutoDP could be interpreted as prioritizing the "casier" 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 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 scenario, is beneficial for the algorithm to generate diverse candidates. To this end, we additionally give novel diversification bonus to 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 large deviation between the solutions. The resulting reward efficiently stimulates the agent to explore high- nigh-dimensional input spaces and 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-ar DRI, 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 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 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

---

Under review as a conference paper at ICLR 2020
2 RELATED WORKS
The maximum independent set (MIS) problem is a prototypical NP-hard task where its optimal solu- tion 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 also known to be a W[1] problem in terms of fixed- parameeer tractability (Downey & Fellows, 2012). Since the problem is NP-hard, existing methods (Tomita et al., 2010; San Segundo et al., 201 1)
for exactly solving the MIS problem often suffers from a prohibitive amount of computation in large graphs. To resolve this issue, 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 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-netwon 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 review of such papers. Such works were mostly used for solving combinatorial optimization through online learning, i... 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 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 new member of the vertex cover at each step of the Markov decision process. However, such a procedure often leads to 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.
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 ε, an independent set is a subset of vertices I C 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 [z; i E V] E (0, 1) with maximum possible cardinality Eiey Ii, where each element x; indicates the membership of vertex i in the independent set I, i.e., I; = 1 if and only if E I. Initially, the algorithm has no assumption about its output, i.e.. both I, = and z; = are possible for all E V. At each iteration, the agent acts on each undetermined vertex i by either (a) determining its membership to be certain value, i.e., set z, 0 or z; 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 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 Markoy decision process (MDP).
State. Each state of the MDP is represented as a vertex-state vector s = [s i E VJ E 10, where the vertex i V is determined to be excluded or included in the independent set whenever
3

---

Under review as a conference paper at ICLR 2020
upslate plane
choo--up plane
STDIRA
apply action
peacess tritial miggnncets
solutioe
rollback vielated cdya
diversly mrnard
R
2
R
Figure 2: Illustration of the transition function with Figure 3: Illustration of coupled MDP with the corresponding solution diversity reward.
the update and the clean-up phases.
st = 0 or & = 1, respectively. Otherwise, & = * indicates the determination has been deferred and expected to be made in later iterations. The MDP is initialized with the deferred vertex-states, i.c. 8 = * for all i E V, and terminated when there is no deferred vertex-state left.
Action. Actions correspond 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 vector a, [a; : i V.] E {0, 1, +) where V. denotes set of current deferred vertices, i.e., V. = {i 2. +].
Transition. Given two consecutive states s, s' and the corresponding assignment a., the transition Pa. (8. 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 intermediate vertex-state 8, i.e., 8; a; if E V. and 6; 8; otherwise. In the cleanup phase, the intermediate vertex-state vector is modified to yield a valid vertex-state vector s', where included vertices 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 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, 8') DievAy s', 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 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 pair of distinct vertex-state vectors (s, 8). Although the coupled MDPs are defined on the same graph, the corresponding agents work independently to result in a pair of solutions (æ, T). Then, we directly reward the deviation between the coupled solutions in terms of f--orm, i.e., ||æ: æ i. Similar to the original objective of MIS, it is decomposed into rewards in each iteration of the MDP defined as follows:
Rai (s,
Σ 16/-8%b where = (V.\V) ( VV), IED
where (s', ss') denotes the next pair of vertex-stater in the coupled MDP. One can observe that 4 denotes the most recently updated vertices in each MDP. In practice, such reward Raw be used along with the maximum entropy regularization for training the agent to achieve the best performance. See Figure 3 for example of coupled MDP with the proposed reward.
4

---

Under review as a conference paper at ICLR 2020
Our algorithm is based actor-critic training with policy network To(als) and value network (s(s) parameterized by the graph convolutional network (GCN, Kipf & Welling 2017). Each GCN consists of multiple layers hi, with n 1,..., .V where the n-th layer with weights w!n) and w performs the following transformation on input H:
h !m) H (eW +D A H
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 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 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) used. Specifically, networks are trained for maximizing the following objective:
: E,
min
A(s (9)
II
(0 (0). A(s())
II clip(r:((0), 10011-,,,10 -,,1+ c,,+ -
KEV
KEV
no(a: (1) (s(?)
ri (0)
A(s) Σ (R + R(())) Vs),),
Now (1) (s())'
where s()) denotes the f-th vertex-state vector and other elements of the MDP are defined similarly. In addition, clip(-) the clipping function for updating the agent more conservatively and lai 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 Section for solving the maximum independent set (MIS) problem. We also pro- vide evaluation of our AutoDP framework 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 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 coined AutoDP- 10, AutoDP-100, and AutoDP- 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 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) based on iterative exclusion of subgraphs, coined ES, having an approximation ratio ((V2)/(og (V))) for the MIS problem. Next, we consider the integer programming solver IBM ILOG CPLEX Optimization Studio V12.9.0 (ILO, 2014), coined CPLEX. We also consider the MIS heuristic proposed by Lamm et al. (2017), coined ReduMIS. Note that 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.
4.1 PERFORMANCE EVALUATION
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 Erdös-Rényí (ER, Erdös & Rényi 1960) and Barabási-Alber (BA, Albert & Barabási 2002) models. Following Khalil
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 five hundred.
5

---

Under review as a conference paper at ICLR 2020
Table 1: 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.
Traditional
DRI
Type
y|
Value
F8
CPLEX
ReduMMS
S2V-DQN
AutoDP-10
AutoPP-100
AntoOP-1000
(15, 20)
Time
Obj.
0.005
7,800
8,844
0.003
0.024
8.844
0.004
8,840
8.844
0.002
(+0.15)
(-00.7%)
8.844
0.005
(415.63)
(+00.1)
8.844
0.056
(+1186.0%)
(++0.1%)
(40. 50)
Obj.
Time
13.83
0.033
16.57
0.062
16.57
12.374
0.015
16.42
0.004
16.55
(+0.7%)
(-73,1%)
0.016
16:57
(+9.6%)
(+0.9%)
0.164
(+ (+1002.09%)
(+0.9%)
ER
(50, 100)
Time
0.117
17.01
0.137
24.387
21.11
0.030
20.61
0.007
21.04
(-77.8%)
(12.9%
0.028
21.10
(12.4%)
(-4.3%)
0,283
21.11
(+2.4%%
(+852.6%)
(100, 200)
Time
Obj.
0.608
21.59
27.87
10.748
27.95
30.109
0.078
26.27
27.67
(+5.3%%
(-63.5%)
27.87
(++.1%)
(+8.5%)
27.93
(++644%)
(+748.79)
(400, 500)
Time
Obg.
29.28
10.823
35.76
30.085
39.83
30.432
0.633
35.05
0.158
38.29
(-76.15)
(19.2%)
0.407
39:11
[-35,73)
(1 (1.66)%
2,768
39.54
(+336 8%6)
(1.12.8%)
(15, 20)
Obj.
6.06
7,019
7,019
7
7.019
(+-0.1%)
7,019
(4-0.1%)
7,019
(4-0.1%)
Time
0.003
0.004
0.041
0.005
0.002
60.2%)
0.006
(119.4)
0.064
(1003.4)
(40, 50)
Obj.
Time
14.81
18.91
0.396
18.91
18.87
0.003
18.91
(+0.23)
(-79.2%
0.011
18.91
(+0.2%)
(-18.4%)
0.118
18,91
(++.22%)
(+778.15%
BA
(50, 100)
Obj.
Time
0.130
24.77
0.038
32.07
0,739
32,07
0.022
31,96
0.003
32,07
( 84.7%)
(+0.3%)
0.018
32.07
{ 19.0%%
(+1.3%)
0.199
32,07
{ (794.3%)
(+-0.3%)
(100, 200)
Obj.
Time
49.87
0.938
0.088
66.07
2.417
66.07
0.047
65.52
66:05
0.007
(+0.8%)
(85.2%)
0.038
66.07
(+0.8%)
19.6%)
0.380
66.07
(++.88%)
(+ +703.65)
(400,500)
Time
Obj.
23,277
148.51
0.322
204.14
15,080
204.14
0.177
202.91
0.024
204.04
(+00.6%)
86.4%)
0.131
204.10
(++0.6%)
25.8%)
204.12
1.111
(1527.59)
(4-0.6)%
Table 2:
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-DON, except for the case of as as-Caida dataset where S2V-DQN underperforms significantly.
Traditional
DRL-bused
Type
M
Value
CPLEX
ReduMIS
S2V-DON
AutaDP-10
AutoDP-100
AutoDP- -000
SATLIB
(1209, 1347)
Obj.
Time
9,490
426.8
426.9
30.110
2.260
413.8
0.311
423.8
( (-86.2%)
(+2.1%)
424.8
1.830
(+2.7%)
19.0%%
425,4 (+2288%)
16.409 (1626.11))
PPI
(591)3480) 3480)
Time
Ots.
24.685
1147.5
1147.5
30.23
6.285
$93.0
0.786
1144.3 (4-28.2)))
(-87.5%)
1,770
11-6,55
(+28 4%0
(-71.8%)
11,469 (-82.3%)
(4-28.44488.4 44)
(MULTI-5K)
REDINT
(22, 3648)
Time
Ohj.
0.008
370.6
0.159
370.6
0,076
370.1
370.6
0.071
(40.11)
(-6.6%)
370.6
0.551
(+0.11)
(+625.09)
370.6
5,500
(4-0.1%)
(-7136.89)
(MULTI-12K)
REDDIT
(2. 3782)
Time
Obj.
0.007
303.5
0.188
303.5
1.883
302.8
0.003
257.4
(-91.8)
15.0%)
292.6
0.025
(-98.7%)
3.4%)
0:451
303.5
(-76.1%6
(10.2%
REDDIT (BINARY)
(6. 3782)
Oly
329,3
329.3
328.6
329.3
(+0.22%
329.3
(+-0.2%)
329.3
(++0,2%)
Time
0.007
0.306
0.055
0.020
63.6%)
0.173
(1214.8%)
2.627
(1467664%)
as-Caida
(8020, 26 475)
Time
Ohj.
0,477
20 049.2
20 049.2
1,719
601.351
324.0
20 049,2
0.812
6.106
20 049.2
62.286
20 049.2
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 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, 2000), protein-protein interactions (Hamilton 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 basclines. 3 The corresponding results are reported in Table I 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 AutoDD algorithms significantly outperform the deep reinforcement learning baseline. i.c., S2V-DQN, across all types of graphs and datasets. For example, AutoDP-10 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 observe that our algorithm can find the best solution in seven out of ten datasets in Table and four out of five datasets in Table
The salvers occasionally violate the time limit due to their pre-solving process.
6

---

Under review as a conference paper at ICLR 2020
4.0
425
Objective
30
Chijentive
120
Kotshits
413-
Artwote CHLLLX
BAV-DON
410
10"
10
10
10
10'
Time (scoond)
Time (sccond)
(a) ER- 500) dataset
(b) SATLIB dataset
Figure 4: Evaluation of tra between time and objective (upper-left side is of better trade-off).
30:00
20.52
Objective
21.0
Objicdive
20.30
f--dvvation
0.2
20.4
20.64
201
31.00
Ti-eo Estropy
Divere Estrogy
0.1
Diverse Entimpy-Dvvrre Divens
Falmpy
0.0
0.5
10
20.76
0.0
X10
Iieration
(a) Performance with varying T (b) Contribution of cach regularizers (c) Deviation in intermediate stages
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 runs respectively Note that the standard deviation in (c) was enlarged ten times for better visibility.
Furthermore, we observe that our algorithm achieves better objective than the CPLEX solver on ER-(100, 200) and ER-(400, 500) datasets, while consuming smaller amount of time. The highly optimized ReduMIS solver tends to acquire the best solutions consistently. However, it is often worse than given limited time budget, described in what follows.
We investigate the trade-off between objective and time for algorithms in Figure 4. To this end, we evaluate algorithms ER-(400 500) and SATLIB datasets with varying numbers of samples for AutoDP and time limits for ReduMIS and CPLEX. It remarkable to observe that AutoDP achieves a better objective than the CPLEX solver 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, experiment with varying the maximum number of iterations T in MDP by T E (2, 2, 16, 32} on ER-(50, 100) dataset. Figure 5a reports the corresponding training curves. We observe that the performance AutoDP improves whenever an agent is given more time to generate the final solution, which verifies that the deferring of decisions plays crucial role in solving the MIS problem.
Next, we inspect the contribution of the solution diversity reward used 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 E 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 -dddeiiations between the coupled intermediate vertex-states s and 8, defined as [f E V, + 3.1l- 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.
7

---

Under review as a conference paper at ICLR 2020
Table 3: 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.
Traditional
DRL-bosed
Type
[4]
CPLEX
ReduMIS
S2V.DQN
AutoDP-10
AmtoDP-100
AutaDP-1000
0.0 000
Time
Obj.
434 896
5967.82
1802.35
457 349
0B
457 753
324.02
457 772
5112:25
QB
BA
2000000 000
Time
Obj.
OB
909 988
4276.43
OB
915
772.18
915
7662.88
OB
Citation
(Cora)
2708
Time
Obj.
1451
0.08
0.04
1451
2.57
1393
1451
1.63
(444.2%))
(-30.5%)
2.71
(+4.22%)
(+5.3%)
1451
13.82
(44.22%
(-187.79)
Citation (Citeseer)
3327
Obj.
Time
0.08
0.03
3.07
1867
1.80
(+11.5%)
(-41-4%6
2.74
1867
(+-1.5%)
(-10.9%)
1867
19.00
(-01844%)
(+1.3%
Amazon
(Photo)
7487
Obj:
Time
2733
80
39.02
2733
66.53
725
2705
2,00
(42273.15 196)
(-97.0%)
4,91
(-92.6%)
(4.273.5%)
2712
32,96
(4-274.15)
(-50.5%)
(Computers)
13 381
Obj.
Time
188.61
61.78
235.80
1281
3.02
4773
(+2272.65 6%)
(-98.7%))
8.63
(+273.3%) 3%)
(-96.3%)
79.19
4783
(-06.4%)
(4273.4%)
(CS)
Coauther
18 333
Ohj.
Time
7506
1.50
7506
0.09
6635
197.39
7479
(4-12.7%)
(-98.5%6)
7479
13:23
(+12.75)
(-93.3%)
7483
122.44 (-38 056)
(4-12.8%)
Coauthor (Physics)
34 493
Obj.
Time
11 151
1802 80
81.34
11 353
2156
1564.13
8.63
11 176 (+-11844%)
(-99.596)
38.71
11 186
(-97.5%%
(+1118 8%)
385.93
11 190 (4-119.0%)
(-75.3%)
SNAP (web-Stanford)
281 903
Obj.
Time
163 385
996.25
44.85
163 391
160
13.35
160 837
137.98
160 872
1357.11
SNAP
Webe-NoteDDame)
325 729
Obj
251 846
64.97
251 850
1802.34
OB
250 365
11.81
250 384
119.48
250 409
1046.48
SNAP
(web-BorkStan)
685 230
Obj
Time
125 194
1875.96
100.17
408 483
OB
403 166
$8.67
975.35
403 189
9940.99
403 231
SNAP
(80c-Pokec)
632 803
Obj.
Time
OB
788 907
1805.95
OB
784 843
770.58
7512.06
891
OB
SNAP
(wiki-topeats)
791 489
Ohjj
Time
0B
1060.00
986 180
OB
958
850.80
9121.85
051
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, Leskovee & 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 10 outperforms the ReduMIS (state-of-tt ohett--rttttttt solver) in BA graph with 2M vertices, but six times faster. It also outperforms the CPLEX 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 result strongly supports the potential of Au being 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.
CONCLUSION
In this paper, we propose 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 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.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. 2018.
Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525 547, 2012.
Egon Balas and Chang Sung Yu. Finding maximum clique in arbitrary graph. SIAM Journal on Computing, (04):1005--06, 1986.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1..9900 2016.
Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009.
Ravi Boppana and Magmús M Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2):180-199) 1992.
Alfredo Braunstein, Mare Mézard, and Riccardo Zecchina. Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms, 27(2):001-226, 2005.
Lijun Chang, Wei Li, and Wenjie Zhang. Computing a near-maximum independent set in linear time by reducing peeelingg.. In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1181-1196. ACM, 2017.
Nicos Christofides. Worst-case analysis of heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976.
Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato Werneck. Accelerating local search for the maximum independent set problem. In International symposium on experimental algorithms, pp. 118-133. Springer, 2016.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International Conference on the Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pp. 170-181. Springer, 2018.
Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & Business Media, 2012.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Thomas A Feo, Mauricio GC Resende, and Stuart H Smith. A greedy randomized adaptive search
procedure for maximum independent set. Operations Research, 42(55)860-8875 1994.
Eleanor Gardiner, Peter Willett, and Peter Artymiuk. Graph-theoretic techniques for macro- molecular docking. Journal of Chemical Information and Computer Sciences, 40(2):273-279, 2000.
Andrea Grosso, Marco Locatelli, and Wayne Pullan. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics, 14(6))587-612, 2008.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Frank Harary and lan C Ross. A procedure for clique detection using the group matrix. Sociometry, 20 1957.

---

Under review as a conference paper at ICLR 2020
Refael Hassin and Asaf Levin. The minimum generalized vertex cover problem. ACM Transactions on Algorithms (TALG), 2(1)x66-78, 2006.
Johan Hastad. Clique is hard to approximate within n/sup 1-/spl epsiv. In Proceedings of 37th Conference on Foundlations of Computer Science, pp. 627-636. IEEE, 1996.
Demian Hespe, Christian Schulz, and Darren Strash. Scalable kernelization for maximum independent sets. Journal of Experimental Algorithmics (JEA), 24(1):1-16, 2019.
Holger H Hoos and Thomas Stützle. Satlib: An online resource for research on sat. Sat, 2000: 283-292, 2000.
John Hopfield and David W Tank. neural computation of decisions in optimization problems. Biological cybernetics, 52(3):141-152, 1985.
Cplex optimization studio. ILOG, IBM, 2014. URL http:://ww. wbw. com/ http://www.cooooott//aeeeee software/ imiizerr
Libin Jiang and Jean Walrand. A distributed esma algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Transactions Networking (ToN), 18(3):960-972) 2010.
Elias Khalil, Hanjun Dai, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, pp. 6348 6358, 2017.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL URL.nttps://opeeeeelee net/ / Eorum? -dd SJU4ayYgl.
Donald Ervin Knuth. The art of computer programming, volume 3. Pearson Education, 1997.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019. URL https::/
net/forum? 1- BFxBB
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. Journal of Heuristics, 23(4):207-229, 2017.
Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph- miii-miiing library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1,
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp. 339-548, 2018.
Mare Mezard, Mare Mezard, and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Raymond Miller and David E Muller. A problem of maximum consistent subsets. Technical report, IBM Research Report RC-240, JT Watson Research Center, Yorktown Heights, NY, 1960.
Pablo San Segundo, Diego Rodríguez-Losade and Agustín Jiménez. An exact bir-parallel algorithm for the maximum clique problem. Computers & Operations Research, 38(2):571-581, 2011.
Pedro Sander, Diego Nehab, Eden Chlamtac, and Hugues Hoppe. Efficient traversal of mesh edges using adjacency primitives. ACM Transactions Graphics (TOG), 27(5): 2008.
Thomas Schaefer. The complexity of satisfiability problems. Proceedings of the tenth annual ACM symposium Theory of computing, pp. 216-226. ACM, 1978.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
10

---

Under review as a conference paper at ICLR 2020
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning SAT solver from single-bi bit supervision. In International Conference on Learning Representations, 2019. URL https: : / openreview net.
wtwpeerreeeeeeeeeeeeeeeeeee Ftteee//ooommmmddiieeeeee 1A5tm.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprinl / 2018.
Kate A Smith. Neural networks for combinatorial optimization: a review of more than decade of research. INFORMS Journal on Computing. 11(1):15-34, 1999.
Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, and Mitsuo Wakatsuki. A simple and faster branch-and- bound algorithm for finding maximum clique. In International Workshop on Algorithms and Computation, pp. 191-203. Springer, 2010.
Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Bernhard Friedrich Voigt. Der handlungsreisende, wie er sein soll und was er zu thun hat, um aufträge zu erhalten und eines glüücklichen erfolgs in seinen geschäften gewiss zu sein. Commis- Commis-Voageur, Ilmenau, 1831.
Ronald J Williams and Jing Peng. Function optimization using connectionist reinforcement learning algorithms. Connection Science, 3(3):241-268, 1991.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openreview net/ forummid=ryyes..... 6 61A5km.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.

---

Under review as a conference paper at ICLR 2020
A GRAPHICAL ILLUSTRATION OF AUTODP
Agent
Policy
Actor
Temporal Difference
Critic
Value
Function
Reward: R
Rdiv
GCN
apply action
States
Figure 6: Illustration of the overall AutoDP framework.
B VARIANTS OF THE MAXIMUM INDEPENDENT SET PROBLEM
In this section, we provide experimental results of the proposed AutoDP framework variants of the original MIS problem. From the empirical results, we show that the AutoDP framework flexible enough to be trained even when some settings of the original MIS problem modified. To this end, we consider two variants 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 unavailable for comparison such variants of the MIS problem.
ES considered in Section Experiments are conducted on the ER graphs with varying sizes of graphs as in Section 4.1.
12

---

Under review as a conference paper at ICLR 2020
Table 4: 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.
Type
|
Value
CPLEX
AutoDP-10
AutoDP-100
AutoDP-1000
Obj.
9.00
9.00
(-0.0%)
9.00
( (-0.0%)
9.00
(-0.0%)
(15, 20)
Time
0.013
0.003
(6.99%%
0.006
(- 53.8%)
0.045
(+246.2%)
Obj.
16.86
16.82
(0.2%%
16.86
(0.0%%
16.86
(-0.0%)
(40, 50)
Time
0.083
0.006 (-92.8%)
0.019
(-77.1%)
0.168 (+102.4%)
Obj.
21.46
21.29
-0.8%)
21.44
-0.1%)
21.46
-000%)
ER
(50, 100)
Time
0.159
0.013
(-91.%%)
0.038
(-76.1%)
0.316
(+98.7%)
Obj.
28.41
28.09
(-1.1%)
28.39
(00.1%)
28.45
(+0.1%)
(000,200
Time
12.357
0.040
99.7%)
0.098
99.2%)
0.699
94.3%%
Obj.
37.66
38.08
(+1.1%)
39.21
(+4.1%)
39.99
(+6.2%)
(400,
Time
30.083
0.277
99.1%)
0.537
98.2%)
3.025
89.9%)
Table 5: 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 measured with respect to CPLEX.
Type
M
Value
CPLEX
AutoDP-10
AutoDP-100
AutoDP- 1000
Obj.
10.54
10.53
10.53 (-0.1%)
10.53 (-0.1%)
10.53 (-0.1%)
(15, 20)
Time
0.014
0.002 (-85.7%)
0.004 (-71.4%)
0.019 (+35.7%)
Obj.
17.94
17.64
(-1.7%)
17.68 (-1.4%)
17.71 (-1.3%)
50)
Time
0.217
0,004
(-98.2%)
0.006 (-97.2%)
0,032 85.3%%
Obj.
22.64
21.66
(-4.0%)
21.77 (-3.8%)
21.84 3.5%%
ER
(50, 100)
Time
1.829
0.002
(-99.9%)
0.008 (- -99.5%)
0.069
-96.2%)
Obj.
27.12
29.17
(+7.6%)
29.56 (+9.0%)
29.69
(+9.5%)
(100, 200)
Time
29.837
0,019
(- 99.9%)
0.107 (- 99.6%)
0,958
(96.8%)
Obj.
4.56
37.17
1715.1%)
38.39
(+741.8%)
39.41
(+764.3%)
(,00,500)
Time
30.122
0.068
- 99.7%)
0.421
-98.6%
3,956
86.9%)
B. MAXIMUM WEIGHTED INDPENDENT SET PROBLEM
First, we report experimental results on solving the MWIS problem. Consider a graph 9 = (V. E) associated with positive weight function V - R+ The goal of the MWIS problem is to find the independent set I C V where the total sum of weight Eiez w(1) 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... R(s, 8') = Eiev.yy \vz 81)(()). The weights are randomly sampled from normal distribution with mean and standard deviation fixed to 1.0 and 0.1, respectively. We report the corresponding results in Table 4. Here,
observes that AutoDP always achieves performance at least 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 smaller amount of time. Such result confirms that our framework is generalizable to the WMIS problem.
13

---

Under review as a conference paper at ICLR 2020
Table 6: 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.
SL-based
DRL-based
Type
M
Value
GTS-ER
GTS-SATLIB
S2V-DQN
AutoDP-10
AutoDP-100
AutoDP-1000
(15,
Obj.
Time
8.829
1,707
8,838
1.749
0.004
8,840
0.002 (-99.9%)
8.844
(++011%)
0.005
8.844
(+0.11%)
(-99.7%)
0.056
8.844
(+0.11%)
(-96.8%)
Obj.
16.46
16.47
16.42
16.55 (40.5%)
16.57
(+0066%)
16.57
(+0.6%)
(40, 50)
Time
2,660
3.583
0.015
0.004
(-99.9%)
0.016
(-99.6%)
0,164
(55.4%))
ER
(50, 100)
Obj-
Time
3.222
20.70
20.83
3,914
3.767
20.61
0.007
21.04
(+1.0%)
(-99.8%)
21.10
0.028
(+1.2%%
(-99.4%)
0,283
21.11
(+1.3%)
92.8%)
(100, 200)
Obj.
Time
26.17
6,846
4,964
26.11
0.078
26.27
0.029
27.67
(+-5.6%
(9.66%)
0.085
27.87
(++6.5%)
(99.8%)
0.666
27.93
(+6.77%
90.3%)
(400, 500)
Obj.
36.48
34.99
35.05
38.
(++5.0%)
39.11
(+7.2%)
39.54
(+88.4%)
Time
10.598
8.609
0.633
0.158
98.5%)
0.407
96.2%%
2.768
73.9%)
B.2 PRIZE COLLECTING MAXIMUM INDEPENDENT SET PROBLEM
Next, we introduce the PCMIS problem. To this end, consider graph G = (V,E) and a subset of vertices I C V. Then PCMIS problem is associated with the following the "prize" function f to maximize:
1Ø) - M((.)) i,j 5I)
where > 0 is the penalty function for including two adjacent vertices. We set À = 0.5 in the experiments. Such 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(s8, 8') as the increase in prize function at each iteration, expressed as follows:
R(s,s') = Σ E (
E iEVA JEVAAVA
Σ
5/S5
VV
JEVIV.
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 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 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
hhttps://gi thub. www.b.ccoooo...ccccmmmmmooo....o catomminnell-a 1
14

---

Under review as a conference paper at ICLR 2020
Table 7: Generalization performance of AutoDP-1000 across synthetic graphs with varying types and sizes. Rows and columns correspond to datasets used for training and evaluating the model, respectively.
BA
Type
(40, 50)
(50, 100)
(100, 200)
(00))
(40, 50)
(50, 100)
(100, 200)
(400, 500)
(15, 20)
16.57
21.06
26.50
30.36
18.91
32.07
66.00
200.96
(40.50)
16.57
21.11
27.88
36.95
18.91
32.07
66.07
204.09
ER
(50, 100)
21.11
27.94
38.20
32.07
66.07
204.07
(100, 200)
27.93
39.39
66.07
204.08
(400, 500)
39.54
203.90
(15, 20)
16.57
21.10
27.28
33.87
18.91
32.07
66.05
202.47
(40, 50)
16.57
21.11
27.89
37.01
18.91
32.07
66.07
204.03
BA
(50, 100)
21.11
27.89
37.01
32.07
66.07
204.11
(100, 200)
27.86
36.52
66.07
204.11
500),
35.31
204.12
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 et al. (2018) optionally introduced "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 Table 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.
also interesting to observe that GTS- underperforms compared 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 unseen graphs.
D GENERALIZZTION BETWEEN SYNTHETIC GRAPHS
In this section, we report experiments on generalization between ER and BA graphs, where we evaluate the generalization capability our method on different types and sizes of graphs from 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- 500) dataset. On the other side, models evaluated unseen types of graphs tend to work slightly worse as expected. However, the results are still remarkable, c.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 feature and reward. The iteration-index of MDP used for input 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 vertices in the corresponding dataset.
Hardware. Computations for our method and S2V-DQN were done on an NVIDIA RTX 2080Ti GPU and 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 16 CPU cores it allows multi-processing.
Hyper-parameter. Every arper-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 trained for 20000 updates of proximal policy optimization (Schulman
15

---

Under review as a conference paper at ICLR 2020
al., 2017), based on the Adam optimizer with 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 syper-parameter, provided in the respective codes.
Table 8: Choice of hyperparameters for the experiments performance evaluation. The REDDIT column indicates hyperparameters used for the REDDIT (BINARY, MULTI-5K, MULTI-12K) datasets.
Parameters
ER
BA
SATLIB
PPI
REDDIT
as-Caida
Maximum iterations per episode
32
32
128
128
64
128
Number of unrolling iteration
32
32
128
128
64
128
Number of environments (graph instances)
32
32
32
10
64
Batch size for gradient step
16
16
8
8
16
8
Number of gradient steps per update
4
4
8
8
16
8
Solution diversity reward coefficient
0.1
0.1
0.01
0.1
0.1
0.1
Maximum entropy coefficient
0.1
0.1
0.01
0.001
0.0
0.1
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 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). First, for the ER-(100, 200) and BA-(100, 200) datasets, we fine- tuned 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., 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 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 used the subgraph induced from the sampled vertices. We run ES algorithm based on NetworkX package. Next, we CPLEX (ILO, 2014) provided the official homepage." ? We set the optimality gap used for the stopping criterion to 10 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." Note that our implementation of ReduMIS is different from the original work (Lamm et al., 2017) since it employs 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 popular benchmark for evaluating SAT algorithms. We specifically use the syuthetic problem instances from the category of random 3-SAT instances with controlled backbone size (Singer et al., 2000). Next, describe the procedure for reducing the SAT instances to MIS instances. To this end, a vertex is added to the graph for each literal 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,
'https://gi com http://www....aaaaaaaaaaaaagggaa hhttts::/netwerkx.ggteeee io/
"https://www, ibm, com wwtpp/odoctossee///ooooooooooect s/ oo- httpl///pppp..oppoiiiimmom/ zat ion studio 'nttp://algo2. it iti kit.edu eettkedu/kaiiss /ami s/
16

---

Under review as a conference paper at ICLR 2020
Table 9: Performance comparison of CPLEX with different optimality gap used for the stopping criterion.
Optimality gap
Type
[
Value
10-*
10-3
10
10
Obj.
8.84
8.84
8.84
8.84
(15,
Time
0.003
0.003
0.004
0.003
Obj.
16.57
16.57
16.57
16,43
(40,50)
Time
0.062
0.064
0.063
0.043
Obj.
21.11
21.11
21.11
20.938
ER
(50, 100)
Time
0.137
0.141
0.141
0.138
Obj.
27.87
27.87
27.87
27.81
(100, 200)
Time
10.748
11.008
10.917
9.888
Obj-
35.76
35.72
35,73
35.74
(400, 500)
Time
30.085
30.090
30.083
30.089
Table 10: Number 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.
Dataset
Number of nodes
Number of edges
Number of graphs
SATLIB
(1209, 1347)
(4696, 6065)
(38 000, 1000, 1000)
PPI
(591, 3480)
(3854, 377)
(20, 2, 2) (1600, 200)
REDDIT (BINARY)
(6, 3782)
(4, 407
REDDIT (MULTI-5K)
(22, 3648)
(21, 4783)
(4001, 499, 499)
REDDIT (MULTI-12K)
(2, 3782)
(1, 5171)
(9545, 1192, 1192)
as-Caida
(8020, 26 475)
(36 406, 106 762)
(108, 12, 12)
the MIS in the resulting graph corresponds to the truth assignment to the optimal assignments of the SAT problem (Dasgupta al., 2008).
PPI dataset. The PPI dataset is the protein-protein www.-pp--niotnncciiieee interaction dataset with vertices representing proteins and edges representing interactions between them.
REDDIT datasets. The REDDIT (BINARY, MULTI-SK, MULTI-12K) datasets are constructed from online discussion threads in reddit 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 set of autonomous system graphs derived from a set of Views BGP table snapshots (Leskovec et al., 2005).
Citation dataset. The Cora and the Citeseer are networks constructed by vertices and edges repre- senting 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 authorships by vertices and edges, respectively. was collected from Microsoft Academic Graph from the KDD Cup 2016 challenge3.
Pttpps: http:///wwwwddddded/ com/ "https://kddouu www.://ppp....aa.eeeeeeebbe azurewebsi tes. net./
17

---

Under review as a conference paper at ICLR 2020
Table 11: Number of nodes and edges for each dataset used in the Table 3.
Dataset
Number of nodes
Number of edges
Citeseer
3327
3668
Cora
2708
5069
Pubmed
19 717
324
Coauthor CS
333
894
Coauthor Physics
34 493
247 962
Amazon Computers
13 381
245 778
Amazon Photo
7487
119 043
web-Stanfor Stanford
281 903
2 312 497
web-NotreDame
325 729
497 134
web-BerkStan
685 230
600 595
soc-Pokec
632 803
30 622 564
wiki-topeats
791 489
28 511 807
BA-IM
000 000
999 984
BA-2M
300 000
7 1999 984
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 & Sosič, 2016). Edge is added for each pair of web web-pages with links between them.
Social network dataset. The soc-Pokec is graph representing friendships between users from social network Slovakia (Takac & Zabovsky, 2012).
Wikipedia network dataset. The wiki-topeats 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 statisties of the dataset used in experiments corresponding to Table and in Table 10 and 11, respectively.
REFERENCES
Sanjoy Dasgupta, Christos H Papadimitriou, and Umesh Virkumar Vazirani. Algorithms. McGraw- Hill Higher Education, 2008
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, pp. 03488-355,, 2017.
Christine Klymko, David Gleich, and Tamara G Kolda. Using triangles to improve community detection in directed networks. arXiv preprint arXiv: arXiv:1404.5877 2014.
Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 177-187. ACM, 2005.
18

---

Under review as a conference paper at ICLR 2020
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-base based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 43-52. ACM, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9)) 93, 2008
Josh Singer, Ian P Gent, and Alan Smaill. Backbone fragility and the local search cost peak. Journal of Artificial Intelligence Research, 12:235-270, 2000.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International Scientific Conference and International Workshop Present Day Trends of Innovations, volume 1, 2012.
19


Reviews:
[{"review_id": "HkxCFnOTFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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.  \n\nThe 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). \n\nAnyhow, 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.\n\nTo 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. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkghsm4cFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nThe overall approach is interesting and the experimental results look promising, but it is quite difficult to accept the paper in its current state due to the following reasons:\n\n(a) Though the paper is comprehensible, it is littered with spelling mistakes (just take the first sentence: problem -> problems). For the camera-ready version, it would be nice to use a spell/grammar checker.\n\n(b) The authors focus on the MIS problem, but in the introduction, they claim that their approach can be applied to “any” combinatorial optimization task. Well, that is a bit of an overstatement, due to the immense variety of NP-hard optimization tasks! On the one hand, the MIS problem is already taking an important place in many areas of computer science, and I would suggest concentrating on this task - by changing the title and the summary of the paper, and by just pointing out in the conclusion that the present DRL approach might be applicable to other problems. On the other hand, if the authors are convinced that their DRL approach is generic, then the paper should include other well-known APX-hard problems such as, for example, Min Feedback Node Set, Min Balanced Cut, or Min Set Cover. \n\n(c) The paper is missing a related-work section. To this point, the MIS problem should be presented in more detail with some theoretical results about its approximability (to within a linear factor, as shown by Boppana and Halldorsson, 1992), and its fixed-parameter tractability (it is W[1]-hard). From an algorithmic viewpoint, the ReduMIS technique is mentioned, but there are many other heuristic approaches and kernelization methods. Notably, OnlineMIS (Dahlum et. al. ESA’16) is orders of magnitude faster than ReduMIS on various large instances. Furthermore, the kernelization technique developed by Chang et. al. (SIGMOD’17) and its parallel version (Hespe et. al., JEA’19) is known to be much more efficient than the kernelization algorithm (VC-Solver) suggested in ReduMIS. Besides heuristic algorithms, very little is said about deep learning approaches for solving MIS. To this point, a more detailed presentation of  Dai et. al.’s approach  (NIPS-17) would be relevant, by explaining the similarities and differences with your approach. Finally, nothing is said about the recent deep architecture proposed by Li et. al. (NIPS’18) for solving MIS. Though they adopt a supervised learning approach, their GCN architecture shares strong similarities with the Actor-Critic framework in the present paper.\n\n(d) The deep auto-deferring policy, presented in Section 3 looks interesting, but it is quite unclear. The main idea lies in deferred MDPs, for which the size of the action space is in $\\Omega(3^N)$ because any subset of nodes can be chosen at each state. For such huge MDPs, it is not clear that we can converge to a stable policy in polynomial time. Furthermore, the authors are mixing Actor-Critic (using a graph convolution net) and Proximal Policy Optimization, together with diversification rewards, which makes the overall framework unintelligible. A graphical representation for explaining this complex framework would be welcome. Furthermore, I don’t see how the notion of diversification reward is implemented in the PPO approach for training the agent.\n\n(e) In the experiments, some competitors are missing. As mentioned above, ReduMIS is nowadays dominated by more efficient kernelization/heuristic techniques for solving MIS. I would suggest to instead use OnlineMIS. Moreover, the choice of S2V-DQN is relevant as an RL competitor, but it would be interesting to also use the GCN architecture (Li et. al., NIPS’18) as a supervised competitor. Finally, the SMT solver Z3 is known to be quite efficient for MIS instances (as already observed by Li et. al.), and a comparison with it would indicate whether ADP is competitive (or not) with the best generic solvers.\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1g_kS26YH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nPros:\n- Extensive experiments have been done on several datasets, both synthetic and real. The ablation and generalization experiments are particularly valuable for getting insight into the performance of the algorithm.\n- Comparison to CPLEX and ReduMIS strengthens the results.\n- The paper is reasonably well-written and easy to follow. Figures 2 and 3 are especially useful for quickly understanding key ideas.\n\nCons:\n- The update and clean-up phases inject significant domain knowledge about MIS into the policy. At a high level the idea is similar to unit propagation in Boolean Satisfiability (SAT) solvers or domain propagation in Mixed Integer Programming (MIP) solvers, i.e., the hard constraints of the problem can be used to make decisions in the search for a solution. Both SAT and MIP solvers have been shown to rely on it to significantly improve their search. Improvements over S2V-DQN could be due to this extra built-in domain knowledge, rather than any improvements related to learning. For a fairer comparison, either this knowledge should be removed from ADP as an additional ablation study, or it should somehow be given to S2V-DQN as well. Without such a comparison, it is not clear that the improvements are really due to the new ideas like auto-deferring, diversity regularizer, etc.\n- A comparison to Li, Chen, and Koltun, NeurIPS’18 is needed since they have shown strong results for MIS and they have made the code available online. Although their approach is supervised learning, it would still be useful to assess an RL approach’s performance relative to SL.\n\n\nAdditional comments:\n- It is not clear what encourages the policy to defer decisions, rather than making all the {0,1} decisions for all variables in one step or a small number of steps. Does this behaviour of the policy arise naturally via training, or does some regularization need to be applied to ensure that the policy doesn’t prematurely fix all variables? For example, as a way to avoid/reduce variance in the reward signal, the policy may learn to fix all variables in just one step -- does this issue arise?\n\n- The abstract says \"The reported performance of our generic DRL scheme is also comparable with that of the state-of-the-art solvers specialized for MIS, e.g., ADP outperforms them for some graphs with millions of vertices.\" Can you please point out the specific results in the paper that this sentence is referring to?\n\n- Comparison to CPLEX:  The paper mentions that “we observe that our algorithm outperforms the CPLEX solver on ER-(100, 200) and ER-(400, 500) datasets, while consuming a smaller amount of time”, and “It is remarkable to observe that ADP outperforms the CPLEX solver on both datasets under reasonably limited time.” Note that CPLEX not only optimizes the objective, but also proves a bound on the objective, while ADP only does the former. So this is not a fair comparison. A fairer comparison would be to set CPLEX hyperparameters to give higher priority to optimizing the objective and then measure the time CPLEX took to first reach a particular objective value rather than the time to “solve” an instance. It can be the case that a given objective value is achieved quickly but then proving a bound requires much longer. Also there is no mention of the optimality gap used as a stopping criterion for CPLEX.\n\n- One potential advantage of making one decision per step is that the credit assignment problem may be simpler compared to making many decisions simultaneously. It would be insightful to explore this tradeoff in more detail.\n\n- The acronym ADP is somewhat well-known in the optimization community as Approximate Dynamic Programming (http://adp.princeton.edu/), so it would be helpful to use a different one.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new way to formulate the design of the deep reinforcement learning that automatically shrinks or expands decision processes.

The paper is borderline and all reviewers appreciate the paper and gives thorough reviews. However, it not completely convince that it is ready publication. 

Rejection is recommended. This can become a nice paper for next conference by taking feedback into account. 
Decision: Reject