Learning to Solve Combinatorial Problems via Efficient Exploration
Authors: Thomas D Barrett
Christopher William Falke Parsonson
Alexandre Laterre
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
combinatorial optimisation
graph neural network
maximum cut

Abstract: From logistics to the natural sciences, combinatorial optimisation on graphs underpins numerous real-world applications.  Reinforcement learning (RL) has shown particular promise in this setting as it can adapt to specific problem structures and does not require pre-solved instances for these, often NP-hard, problems.  However, state-of-the-art (SOTA) approaches typically suffer from severe scalability issues, primarily due to their reliance on expensive graph neural networks (GNNs) at each decision step.  We introduce ECORD; a novel RL algorithm that alleviates this expense by restricting the GNN to a single pre-processing step, before entering a fast-acting exploratory phase directed by a recurrent unit.  Experimentally, we demonstrate that ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem, whilst also providing orders of magnitude improvement in speed and scalability.  Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73% on 500 vertex graphs with a decreased wall-clock time.  Moreover, ECORD retains strong performance when generalising to larger graphs with up to 10000 vertices.

Under review as a conference paper at ICLR 2022
LEARNING TO SOLVE COMBINATORIAL GRAPH PAR- TITIONING PROBLEMS VIA EFFICIENT EXPLORATION
Anonymous authors Paper under double-blind review
ABSTRACT
From logistics to the natural sciences, combinatorial optimisation on graphs un- derpins numerous real-world applications. Reinforcement learning (RL) has shown particular promise in this setting as it can adapt to specific problem struc- tures and does not require pre-solved instances for these, often NP-hard, problems. However, state-of-the-art (SOTA) approaches typically suffer from severe scala- bility issues, primarily due to their reliance on expensive graph neural networks (GNNs) at each decision step. We introduce ECORD; a novel RL algorithm that alleviates this expense by restricting the GNN to a single pe-processing step, be- fore entering a fast-acting exploratory phase directed by recurrent unit. Experi- mentally, we demonstrate that ECORD achieves new SOTA for RI. algorithms on the Maximum Cut problem, whilst also providing orders of magnitude im- provement in speed and scalability. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73 % 500 vertex graphs with decreased wall-clock time. Moreover, ECORD retains strong performance when generalis- ing to larger graphs with up 10000 vertices.
INTRODUCTION
Combinatorial optimisation (CO) problems seek to find the ordering, labelling, or subset of discrete elements that maximises some objective function. Despite this seemingly abstract mathematical for- mulation, CO arises at the heart of many practical applications, from logistics (Yanling et al.) 2010) to protein folding (Perdomo- Ortiz et al. 2012) and fundamental science (Barahona) 1982). However, with these tasks often being Na-hard, solving CO problems becomes increasingly challenging for all but the simplest of systems. This combination of conceptual simplicity, computational complexity, and practical importance has made CO a canonical challenge, and motivated significant efforts into developing approximate and heuristic algorithms for these tasks. Whilst approximate methods can offer guarantees on the solution quality, practice they frequently lack sufficiently strong bounds and have limited scalability (Williamson & Shmoys. 2011). By contrast, well-designed heuristics offer no such guarantees but can prove highly efficient (Halim & Ismail 2019).
As a result, recent years have seen a surge in the application of automated learning methods that parameterise CO heuristics with deep neural networks (Bengio et al. 2021). In particular, rein- forcement learning (RL) has become a popular paradigm, as it can facilitate the discovery of novel heuristics without the need for labelled data. Moreover, many CO problems as Markov decision processes (MDPs) graphs, where vertices correspond to discrete variables and edges denote their interaction or dependence. Accordingly, graph neural networks (GNNs) have be- come the de-facto function approximator of choice as they reflect the underlying structure of the problem whilst seamlessly handling variable problem sizes and irregular topological structures.
naturally formulated
However, despite the demonstrated success of RL-GNN approaches, scalability remains an outstand- ing challenge. Running a GNN for every decision results in impractical computational overheads for anything beyond small- to medium-sized problems. This is exacerbated by the fact that directly pre- dicting the solution to an NP-hard problem is typically unrealistic. As such, leading approaches often utilise stochastic exploration
structured search to generate multiple candidate solutions (Chen &
Tian 2019; Joshi et al.) 2019 Gupta et al.] 2020 Barrett et al. 2020 Bresson & Laurent 2021)
which ultimately requires longer solving times and an increased computational burden.

---

Under review as a conference paper at ICLR 2022
The notion of exploratory combinatorial optimisation - reframing the task from predicting single solution to exploring the solution space using reversible single-vertex actions (Barrett et al. (020) also hints at a mitigation to the scalability issue it highlights. Intuitively, when any decisions can be reversed, the quality of any single decision is less critical, so long as overall improvements are made over the course of many such actions. In this work, we leverage this notion to introduce new algorithm, ECORD (Exploratory Combinatorial Optimisation with Rapid Decoding), that combines single GNN preprocessing step with fast action-decoding that replaces further geometric inference with simple per-vertex observations and a learnt representation of the ongoing optimisation trajec- tory. The result is a theoretical and demonstrated speed-up over expensive GNN action-decoding with the action-selection time of ECORD being independent of the graph topology and, in practice, near constant regardless of graph size.
Experimentally, we consider the Maximum Cut (Max-Cut) problem, a canonical CO problem chosen because of its generality (11 of the 21 NP-complete problems presented by Karp (1972) can be reduced to Max-Cut, including graph coloring, clique cover, knapsack and Steiner Tree) and the fact that it presents a challenging problem for scalable CO as the optimal solution requires every vertex to be correctly labelled (rather than simply a subset). This combination of wide-ranging applicability and intractability has motivated significant commercial and research efforts into Max-Cut solvers, from bespoke hardware based on classical (Goto al. (019) and quantum annealing (Yamamoto 2017: Djijjev et al.] (018)) to hand-crafted (Goemans & Williamson 1995: Benlic & Hao 2013 or learnt (Barrett al. 2020) heuristic algorithms.
et al.
ECORD is found to equal or surpass the performance of expensive SOTA RL-GNN methods on graphs with up to 500 vertices (where all methods are computationally feasible), even when com- pared on number of actions instead of wall-clock time. Moreover, the low computational overhead of ECORD is seen to provide orders of magnitude improvements in speed and scalability, with strong performance, and a nearly 300 x increase in throughput when compared to conventional RL-GNN methods, demonstrated on graphs with up to 10 000 vertices.
2 RELATED WORK
The application of neural networks to graph-based CO problems dates back to Hopfield & Tank (1985) who considered the Travelling Salesman Problem (TSP). However RL techniques were not applied until a decade later in the work of /Zhang & Dietterich (1995) on the NP-hard job-shop problem. More recently, the advancement of deep learning and RL has triggered a resurgence in the ML community's interest in developing CO solvers, with multiple reviews providing detailed taxonomies (Bengio et al. 2021 Mazyavkina et al. 2020 Vesselinova et al.) 2020).
Learning to solve non- Euclidenn CO. This resurgence began by considering Euclidean approaches that did not not reflect the underlying graph structure of the problems. In this context, Bello et al. (2016) used RL to train pointer networks (PNs), which treat the discrete variables of the CO problem as a sequence of inputs to a recurrent unit (Vinyals et al.) 2015) to solve TSP. By avoiding the need for labelled data sets, they were able to scale beyond the 40 vertex limit of Vinyals al. (201)), inferring on 20 to 100 vertex graphs. Gu & Yang (2020) further scaled this approach to instances of up 300, using a hybrid supervised--rinfooceemme learning framework that combined PNs and A3C (Miih et al. 2016). However, although PNs can handle graphs of different sizes (with the help of manual input/output engineering, such as zero padding). these Euclidean approaches fail to capture the topological structures and intricate relationships contained within graphs, and typically require: a large number of training instances order to generalise.
This issue was addressed by Dai et al. (2017), who trained Structure-to- Vector (S2V) GNN with DQN to solve TSP and Max-Cut. The resulting algorithm, S2V-DQN, generalised to graphs with different size and structure to the training set and achieved excellent performance across range of problems without the need for manual algorithmic design, demonstrating the value in exploiting underlying graph structure.
Advances in optimality. Various works since Dai et al. 2017) have sought to harness GNN embed- dings to improve solution quality. [Abe et al. (2019) combined GNN with Monte Carlo tree search approach to learn a high-quality constructive heuristic. Ultimately, they demonstrated a greater abil- ity to generalise to more graph types than S2V-DQN on Max-Cut, but their method could only scale
2

---

Under review as a conference paper at ICLR 2022
to 100 vertex Erdös-Rényi and Barabasi-Alber graphs. Li al. (2018) combined graph convo- lution network (GCN) with guided tree search to synthesise a diverse set of solutions and thereby more fully explore the space of possible solutions. However, they used supervised learning and so required labelled data which limits scalability, and they did not consider Max-Cut. |Barrett et al. (2020) proposed ECO-DQN, the SOTA RI. algorithm for Max-Cut, which reframed the role of the RL agent to looking to improve on any given solution, rather than directly predict the optimal so- lution. The key insight that exploration at test time beneficial, since individual sub-optimal decisions (which are to be expected for NP-hard problems) need not matter so long as the final solution is of high quality. However, ECO-DQN utilises an expensive GNN each decision step and extends the overall number of decisions taken to be theoretically limitless, thereby restricting its scalability to be even worse than that of S2V-DQN. ECORD remedies this by using an initial GNN embedding followed by recurrent unit to balance the richness provided by graph networks with fast-action selection.
Advances in scalability, Manchanda et al. (020)) furthered the work of Dai et al. (2017) by first training an embedding GCN in a supervised manner, and then training a Q-network with RL to predict per-vertex action values. By using the GCN embeddings to prune nodes unlikely to be in the solution set, their method provided significantly more scalability than S2V-DQN on the the Maximum Vertex Cover problem. However, was not applicable problems whose nodes cannot be pruned, which precludes it from solving some of the most fundamental CO problems such as Max-Cut. Drori al. (2020) took a different approach, proposing a general RL-GNN framework that uses graph attention network to create a dense embedding of the input graph followed by a recurrent attention mechanism for action selection. They achieved impressive scalability, reaching instance sizes of 1000 vertices on the minimum spanning tree problem and TSP. However, unlike ECORD, the Drori et al.] (2020) framework restricts the decoding stage condition only on the previously selected action, and considers only node ordering problems in a non-exploratory setting.
METHODS
3.1 BACKGROUND
Max-Cut problem. The Max-Cut problem seeks binary labelling of all nodes in graph, such that the number (or cumulative weight) of edges connecting nodes of opposite labels is maximised. Concretely, for a graph, G(V, E), with vertices V and edges E, we wish to find a subset of vertices, S C V that maximises the 'cut-value', C(S, G) = -iEs.Jenis w(es)), where w(es)) is the weight of an edge eij E F.
Q-learning. We formulate the optimisation as a Markov Decision Process (MDP) defined by tuple {S, S, 7. where S and A are the state and action spaces, respectively, T S x A - [0, 1] is the transition function, R : + R the reward function and 7 E [0, 1] the discount factor. Q-learning methods seek to directly learn the Q-value function mapping state-action pairs, (s e S.a E A), to the expected discounted sum of immediate and future rewards when following a policy
7 (r(((()())))))))))))))))))))(( (()) =a). Conventional DQN (Mnih cet al. 2015) optimises Qe by minimising the mean- qura--squared-errrr between the network predictions and a bootstrapped estimate of the Q-value. By definition, an optimal policy maximises the true Q-value of every selected action, therefore, after training, an approximation of an optimal policy is obtained by acting greedily with respect to the learnt value function, (s)s) arg max, Qa(s, a').
: S + A, Q" a) = E, 12 1
Munchausen DQN. Munchausen DQN (M-DQN) (Vieillard et al., 2020) makes two fundamental adjustments to conventional DQN. Firstly, the Q-values are considered to define stochastic policy temperature parameter. Secondly, M-DQN adds the log-probability of the selected action to the reward at each step. All together, the regression target for the Q-function modified to
with action probabilities given by To (=(ss) = softmax( @o(s:)), ), where
Qm-den (s((), (0) sl s((+1) = ((1()))) + at In To (()))))))))
(I)
( Le (ttt)) ,a') - T in (
where a scales the additional log-policy contribution to the reward. Note that as a + 0 and T - recover the standard DQN regression target.
3

---

Under review as a conference paper at ICLR 2022
ONN eubeeiting of mode
CRU
GRU
mode cbs, at
global ols.
pie-werixx action mnauaatoo
RNN
Fglo
(#08-)
(6) t=::; Graph eabedding
(6) r>0: Recurrent decoding
Figure 1: Diagram of the proposed ECORD architecture applied to solving Max-Cut instance. (a) A GNN generates initial embeddings for each vertex at 0. (b) At each step in the episode, a recurrent unit takes as input the initial graph embedding, the node-level observation from the previous time step, and the global observation from the current time step, and updates the hidden state vector. To select an action (node to flip), the hidden state is concatenated with the node-level observation the current time step and passed Q-network.
3.2 ECORD
MDP formulation. The state, s(() = E), E S, at given time-step corresponds to the graph and binary labelling of all vertices. An action selects single vertex and 'flips' its label to the opposite state, adding or removing it from the solution subset. Rewards correspond to the (normalised and clipped) increase in best cut-value, r(s(9) = max((C(s()) - where C(s*) is the the best solution found in the episode thus far. This choice of reward structure motivates the agent to maximise the cut-value at any step within the episode, without discouraging from searching through unseen solutions. Naturally, the transition function is known and fully deterministic for our mathematically defined optimisation problem.
Concretely, we represent the state, s(1), with per-vertex observations, of ERS for iEV, and global
observation of the current state, 0g ER?. For each vertex, we provide: (i) the current label, (ii) the immediate change in cut-value if the vertex is flipped (which we refer to 'peek') and (iii) the number of steps since the node was last flipped. Our global observations are the (normalised) difference in cut-value between the current and best observed state, and the maximum peek of any vertex in the current state.
Importantly, these features are readily available without introducing any significant computational burden. Indeed, even the peeks one-step look-aheads for each action - can be calculated for all vertices once at the beginning of each episode, after which they can be efficiently updated quickly at each step for only the flipped vertex and it's immediate neighbours (details can be found appendix A.3). Besides this being cheap operation, this approach is also the most efficient way to track the cut-value over the course of multiple vertex flips, and thus is necessary calculation to evaluate each environmental state regardless of whether the peeks form part of the observation.
Architecture. ECORD splits an optimisation into two stages (see figure 1 for an overview of the entire architecture). (i) A GNN prepares per-vertex embeddings conditioned on only the geometric structure (i.e. weighted adjacency matrix) of the graph itself. (ii) Starting from random labelling of the vertices, ECORD sequentially flips vertices between subsets, with each action conditioned on the static GNN embeddings, the previous trajectory steps (through the hidden state of an RNN) and simple observations of the current state (described above). Full details of the architecture can be found in appendix A. with this section providing a higher level summary.
4

---

Under review as a conference paper at ICLR 2022
To generate the per-vertex embeddings, we use gated graph convolution network (Li et al. 2015 The final embeddings after L rounds of message-passing are linearly projected to per vertex embed- dings, 2; Wp.;" (L) where denotes the vertex, that remain fixed for the remainder of the episode.
To select an action at time I, we first combine the GNN outputs with the observation to obtain per- vertex embeddings of the form u/ = [ Woo J J. where square brackets denote concatenation. This local information is then used in conjunction with the RNN hidden state. A(9,, to predict the Q-value for flipping vertex i. The Q-network itself uses a duelling architecture (Wang et al. 2016), where separate MI.ss estimate the value of the state, (.), and advantage for each action, A())
Q(u ,) ((h + A(u
( (1) = MLPv ( + MLPA ((U W).4")).
(2)
(+))) is shared across each vertex when calculating the advantage function as reward function depends on the current best score within the trajectory's 's history. a global feature contained in the state-level embedding. However, before concatenating them together, we project the high dimen- sional (1024 in our case) hidden state to match the lower dimensional (32) per-vertex embeddings.
Finally, we update the RNN using the embedding of the selected action, t. and our global obser- vation after taking it, og (t+1)
h (++1) GRU( (00(() (t)))), where m (++1) (LP
(0) .G ()
(3)
Training. ECORD is trained using M-DQN. As the Q-values are conditioned upon the internal state of an RNN, see eq. (2). we train using truncated backpropagation through time (BPTT). Concretely, when calculating the Q-values at time during training. we reset the environment and the internal state of the RNN to their state at time t - kBPTT and replay the trajectory to time t. In doing so, we only have to backpropagate through the previous KBPTT time steps when minimising the loss.
The intuition behind M-DQN's modifications are (i) the entropy of the policy is jointly optimised with the returns, in the spirit of maximum entropy RL (Haarnoja et al. (018), and (ii) the agent is rewarded for being more confident about the correct action. The second point is based on the assumption that an optimal policy is deterministic, since it will always take the action with maximum Q-value. One could observe that as ECORD's 's action space is large (equal to the number of vertices in the graph, [V] the structured exploration of M-DQN's stochastic policy may allow for more approaches used in DQN. Moreover, the
meaningful trajectories than the standard epsilon-greet underlying postulate of M-DQN, that despite the stochastic exploration policy, the true optimal policy is deterministic, aligns exactly with our problem setting.
4 EXPERIMENTS
Baselines. We compare ECORD to the previous two SOTA RL-GNN algorithms for Max-Cut, S2V- DQN (Khalil et al. 2017 and ECO-DQN (Barrett et al. 2020 Our implementation of ECORD contains several speed improvements in comparison to the publicly available implementation of ECO-DQN (e.g- parallelised optimisation trajectories, compiled caleulations, sparse matrix opera- tions). To ensure the fairest possible comparison, when directly comparing performance independent of speed (section 4.1]. we use the public implementation, however when comparing scalability (sec- we use a re-implementation of ECO-DQN within the same codebase as ECORD.
tion 4.2 and 4.3)
Additionally, a simple heuristic, Max-Cut Approx (MCA), that greedily selects actions that max- imise the immediate increase in cut value is also considered. Besides from providing surprisingly strong performance, the choice of MCA baselines is motivated by the observation that the one-step look-ahead 'peek" features make learning a greedy policy straightforward. Moreover, whilst MCA terminates once a locally optimal solution is found (i.e. one from which no single action can further increase the cut value), network learning to only approximate a greedy policy may fortuitously escape these solutions and ultimately obtain better results. To address this concern, we introduce a simple extension of (and significant improvement over) MCA called MCA-soft, where actions selected by a soft- coft-greedy policy with the temperature tuned to maximise performance on the target dataset (see appendix A.4 for details).
(..4
Datasets. We consider graph datasets for which the optimal (or best known) solutions are publicly available. The dataset published by BBrrett et al. (2020) consists of Frdös-Rény: (Erdös & Rényi
5

---

Under review as a conference paper at ICLR 2022
1960) and Barabasi-Albert (Albert & Barabási 2002) graphs (ER and BA, respectively) with edge weights w(et)) E }1} and up to 500 vertices. Each graph type and size is represented by 150 random instances, with 50 used for model selection and results reported the remaining 100 at test time. We refer to these distributions as ER40/BA40 to ER500/BA500.
To test on larger graphs multiple distribution, from which we focus on random (ER) graphs with binary edge weights and 800 10 000 vertices. To aide model selection and parameter tuning, generate 10 additional graphs for each distribution in the GSet. We refer to these validation sets as ER800 to ER 10000.
the GSet (Benlic & Hao 2013), well-studied dataset containing
Metrics. Our analysis considers the raw performance, wall-clock speed, and memory usage of algorithms. Following prior work, we use the approximation ratio, given by AR(ss) = C(s*)/Cop where Copt is the best known cut value, as metric of solution quality, All experiments were performed on the same system with an Nvidia GeForce RTX 2080 Ti 11 GB GPU and 80 processors (Rn Xeon(R) Gold 6248 CPU @ 2.50 GHz).
Reproducability. All datasets considered in this work are either available or linked in the supporting code at htttps://githut thub. com/ (MASKED- FOR- BLIND BELIND-REVIIEE along with source code and scripts to reproduce the reported results.
4.1 COMPARISON TO SOTA RL METHODS
Table I: Agent scores trained on ER40 (best in bold). Error bars denote 68 % confidence intervals. RL baseline scores are taken directly from Barrett et al. (2020) for fair comparison. Results are averaged across 5 random seeds for the RL baselines and 3 random seeds for ECORD.
Heuristics
RL baselines
MCA
MCA-soft
S2V-DQN
ECO-DQN
ECORD
ER60
ER40
0.991 18.01
0.997799000
000000
0.999
1.000+..00
m00
0.980
0.973
1.000 1:000:0:00
1.000+0.000 mo0
1.000
1.000-0000
c00
ER
0.977
8:815
0.973 8%
0.993
8 099
0.961 88
1.000 18000
8:02
1.000
0:90A
ER200
0.959
0.951
0.999=6-91 001
1.000
-0
ER500
0.941 10.03
0.958 -o 1005
0.921 -0.00000000 019
0.985 10006
0.996 0.996*9.00
00.00
BA40
BA60
0. 0.989 190007
0.999.00.00
1. 1.000
0.997
0.968
0.967
040
1.000
1.000
1.000 1.000*Ba00
1.000*0.000
BA100
0.96511805
1.06511.000 18:00
0.984
18 012
0.940
0 082
1. 1.000 0.000
1. 0.000 8:000
BA200
0.911 105T
0.929
+0 4s5
0.865 20 063
0.97820.05 00.00
0. 0.983 0.983-00011 U015
BA500
0.889 0.018
0.003
0.899 0.014
0.744 0.052
0.967 0J015
0.963 0.012
Methods, Our first set of experiments compares ECORD to both heuristic node-flipping, and SOTA RL, baselines. To facilitate fair and direct comparison, we exactly the models, datasets, and re- sults published by Barrett et al. (2020) for S2V-DQN and ECO-DQN. All RL algorithms are trained both ER and BA graphs with up to 500 vertices. S2V. DQN is deterministic and incrementally constructs the solution set one vertex at a time, therefore each optimisation trajectory consists of [V] sequential actions. MCA-soft, ECO-DQN and ECORD allow any vertex to be 'llpped' at each step, and therefore can in principle run indefinitely on target graph. The baselines presented are chosen as they consider the same sequential node-flipping paradigm as ECORD, however their exits multiple algorithms for solving Max-Cu that do not fit this paradigm notably simulated annealing (SA) (Tiunov et al. 2019 Leleu et al., 2019), semidefi- nite programming (SDP) (Goemans & Williamson 1995) and mixed integer programming (CPLEX,) ILOG 2007). We provide additional results using SOTA or commercial algorithms spanning these paradigms in appendix A.5] where ECORD is found to outperform SDP and MIP and either beat or be competitive with SOTA SA methodologics.
on 40 vertex ER graphs and evaluated
In practice, use ECORD and the MCA heuristics with ECO-DQN's default settings; 50 optimisa- tion trajectories per graph, each starting from a random node labelling. acting greedily with respect to the learnt Q-values, and terminating after 2| sequential actions. We note that this disadvantages ECORD as (i) despite learning a stochastic policy, ECORD acts deterministically at test time, and (ii) ECORD's significant speed and memory advantages over ECO-DQN are not accounted for.
Results. Despite the disadvantages described above, ECORD either outperforms or essentially matches ECO-DQN on all tests (see table I], whilst significantly improving over all other baselines
6

---

Under review as a conference paper at ICLR 2022
125
Num. traj. Step time. (ms)
10
Action time (1ts)
100-
BCORD ECO-DQN
10-4
50-
40
1000
2000
10a
10a
10a
10
100
300
1000
3000
10000
Graph size,
[V]
Graph size, [V]
(a) Inference speed for single action.
(b) Practical throughput for batched trajectories.
Figure 2: ECORD (blue) vs. ECO-DQN (orange) scaling performance. (a) Action selection time when running a single trajectory. (b) Step time (action selection and environment update time) when running the maximum number of tradjectories that fit on the GPU. ECORD's relative throughput at [ {30. 100, 300, 1000, 3000, 10 000} is { {1.8, 3.0, 12.2, 39.3, 104.5, 298.9) x ECO-DQN's (beyond V 10 000, ECO-DQN no longer fits the GPU).
and generalising to unseen graph topologies and sizes. This seems surprising when we consider that, in contrast ECO-DQN, ECORD does not directly condition per-node decisions on the state of other nodes. However, ECORD does have access to the optimisation trajectory via the RNN hid- den state, suggesting that in exploratory settings, the temporal structure (in addition to the geometric structure of the graph) is highly informative. This experiment was repeated for a model trained instead on BA40 with the results (provided in appendix A.5 being qualitatively the same.
4.2 COMPUTATIONAL COMPLEXITY AND PRACTICAL SCALING PERFORMANCE
Whilst ECORD has already been shown to match or surpass SOTA RL baselines when ignoring computational cost, this is not a sufficient metric of algorithmic utility. In this section, we consider the theoretical complexity and practical scaling cost of ECORD.
Theoretical complexity. The runtime complexity of any optimisation trajectory scales linearly with the number of actions. In CO problems where every vertex must be correctly labelled, such as Max- Cut, episode length scales at best linearly with the number of nodes. A typical approach, which encapsulates both S2V-DQN and ECO-DQN, for applying RL to CO graphs parameterises the policy or value function with GNN. The precise complexity of a GNN depends on the chosen ar- chitecture and graph topology. however, typically the per-layer performance scales linearly with the number of edges in the graph, as this is the number of unique communication channels along which information must be passed. In practice, this results a (worst case and typical) polynomial scaling of O(VV 3) per-action and ((VV) ?) per optimisation, which makes even modest sized graphs with the order of hundreds of nodes very computationally expensive in practice.
In contrast, ECORD only runs the GNN once, regardless of the graph size or episode length, and then selects actions without any additional message passing between nodes. As a result, per-action computational cost scales linearly as O(V)). regardless of the graph topology, and the entire opti- misation scales O(V) 2). Moreover, action selection in ECORD also has a far smaller memory footprint than using GNN over the entire graph, and each vertex can be processed in parallel up to the limits of hardware. Therefore, in practice, we typically obtain a constant, O(1, scaling of the per-action computational cost and, as the single graph network pass is typically negligible compared to the long exploratory phase, complete the entire optimisation in ((V)).
Practical performance. Figure (ggure?dennen demonstrates the practical performance realised from these theo- retical improvements. In 2a the action time of ECORD and ECO-DQN are compared on graphs with up to 500 k vertices. Whilst ECORD is always faster, both take near constant time for small graphs where batched inference across all nodes is still efficient. However, even when ECO-DQN begins to increase in cost (V) =5500) and eventually fills the entire GPU memory (V) =)0 ECORD retains fixed low-cost inference which only appreciably begins to increase for large graphs (V) >100 k).
7

---

Under review as a conference paper at ICLR 2022
Moreover, the reduced memory footprint of ECORD also allows for more (randomly initialised) op- timisation trajectories to be run in parallel. Figure 2b contrasts ECORD and ECO-DQN by running many parallel trajectories possible for single graph with up [V] =Vkkk. and plotting the effective step time (action selection plus environmental step) per trajectory. The practical increase in throughput of ECORD compared to ECO-DQN increases with graph size from modest 1.8x
with [ =30 to 100x for |V|=3 =3 k and 298.9x x for | |V|=100k.
4.3 SCALING LARGE GRAPHS
Methods. ECORD is trained graphs with binary edge weights, w(eay) {0,1) and |V| 500. The optimal parameters are selected according to the performance of the greedy policy on the generated ER10000 set. For the computational reasons discussed previously, ECO-DQN was trained on ER200 graphs with binary edge weights, and used ER500 graphs for model selection. The temperature of MCA-soft was tuned independently on each graph, as detailed in appendix [A.4
Stochastic exploration. Despite ECORD using a stochastic soft-greedy policy during training, at test time we previously used deterministic policy (which, ultimately, still provided near optimal performance small and intermediate graphs). To investigate the performance of a soft-greedy policy, we evaluated ECORD on the large-graph datasets ER5000, ER7000 and ER 10000 using 20 trajectories of | steps for all graphs in the test sets across a range of temperatures.
The results are summarised in figure 3 The key points are that non-zero temperature is optimal for larger graphs, and that the optimal temperature decreases with graph size. The in- terpretation is that even an exploratory agent such as ECORD still eventually get stuck in closed trajectories when acting determinis- tically. Therefore, introducing some stochas- ticity allows ECORD to escape these regions of the solution space and ultimately continue to search for improved configurations. How- ever, this must be balanced with the need for sufficiently deterministic policy that a good solution is found with high probability. Intu- itively, longer sequences of actions required to reach a good configuration for larger graphs, which aligns with the observed dependence of the optimal temperature with graph size.
1.00
AR(ARmas
0.99
0.98
ER5000
ER7000
ER10000
0.97
0.0002
0.0004
0.0006
0.0008
0.0010
Figure 3: Effeec of temperature on ECORD's ' per- formance for [V| (5000, 7000, 10 1000 graphs. The dashed lines are simply to guide the eye.
GSet results. We validate ECORD's performance large graphs by testing it on all GSet graphs with random binary edges, as summarised in table For each graph we run 20 parallel optimisation trajectories for maximum of s80 For G5000, G7000 and G10000 we tuned temperatures, T, of 3.5e-4, 2e-4 and 1e-4 respectively, and set 7=5e-4 for all other graphs.
ECORD shows consistently strong performance, matching or beating ECO-DQN and MCA-soft on every instance by a margin that increases with graph size. The speed of ECORD is emphasised by the fact that it obtains approximation ratios of above 0.99 on all graphs with [V| < 2 in under 10s. Whilst in principle it is possible to reach the optimal solution in [V| actions, on larger graphs the obtained cut values consistently increase with longer exploration (for reference, ECORD takes 288 k actions in s when [V]=) This clearly demonstrates that ECORD learns to search through the solution space without getting stuck, rather than generating a single mode of solutions.
A natural final question is whether the slight decrease in performance on the largest graphs is due to an insufficient time budget, or the learnt policy being less suitable for these problems. To test this, ECORD was allowed to continue optimising G70 for 1 h. Whilst the obtained solution improved to have an approximation ratio of 0.978 (obtained in only 233 s), the optimal solution was not found. find
Ultimately, whilst previous RL-GNN methods were limited by the scalability of GNNs, ourselves limited by the ability of the agent to reason about larger systems - opening the door to, and defining a challenge for, future research.
8

---

Under review as a conference paper at ICLR 2022
Table 2: ECORD, ECO-DQN and MCA-soft performance on the GSet graphs given time budget of 10, 30, and 180 s (best in bold).
MCA- soft
ECO- ECO-DQN
ECORD
Graph
[V]
10s
30s
180
10s
30s
180s
10s
30
180s
G1
800
0.994
0.999
0.999
0.903
0.993
0.998
0.998
1,000
G2
800
0.995
0.996
0.908
0.986
0.995
0.906
0.908
0.998
1.000
G3
800
0.996
0.999
0.999
0.992
0.993
0.996
0.999
1.000
G4
800
0
0.997
0.999
0.983
0.992
0.998
0.999
1,000
G5
0.996
0.997
0.997
0.993
0.994
0.908
1.000
G43
1000
0.990
0.997
1.000
0.985
0.992
0.908
0.996
0.997
1.000
G44
1000
0.992
0.995
0.999
0.987
0.904
0.906
0.909
0.999
1.000
G45
1000
0.995
0.998
0.998
0.988
0.992
0.996
0.998
0.999
0.999
G46
1000
0.992
0.991
0.998
0.990
0.992
0.997
0.998
0.999
1.000
G47
1000
0
0.997
0.998
0.958
0.983
0.994
0.997
0.998
0.998
G22
2000
0.985
0.980
0.995
0.966
0.981
0.991
0.990
0.985
0.997
G23
2000
0.985
0.992
0.996
0.967
0.963
0.989
0.991
0.995
0.997
G24
2000
0,986
0.991
0.997
0.967
0.983
0.989
0.992
0.991
0.997
G25
2000
0.985
0.993
0.997
0.966
0.985
0.900
0.991
0.996
0.998
G26
2000
0.987
0.993
0.995
0.963
0.982
0.984
0.991
0.996
0.999
G55
5000
0.952
0.968
0.969
0.832
0.873
0.939
0.947
0.969
0.985
G60
7000
0.934
0.963
0.968
0.764
0.847
0.930
0.916
0.960
0.981
G70
10000
0.865
0.931
0.957
0.677
0.818
0.898
0.837
0.941
0.972
Ablations. ECORD's key components are: (i) the use of a single (GNN) encoding step to embed the problem structure, (ii) rapid decoding steps where per-vertex actions are conditioned on only local observations and an (RNN) leant embedding of the optimisation trajectory, and (iii) an ex- ploratory CO setting where actions can be reversed. Ablations (detailed in appendix A..) of the GNN and RNN show that both are necessary for strong performance. ECORD's 's contribution to the exploratory CO setting evidencing that suitably stochastic policy outperforms a deterministic one. To emphasise that this is not simply because of algorithmic improvements in M-DQN com- pared to DQN, a deterministic-acting ECORD trained with DQN is shown to also not match the performance reported in table 2
5 DISCUSSION
We present ECORD, new SOTA RL algorithm for the Max-Cut problem in term of both perfor- mance and scalability. ECORD's demonstrated efficacy on graphs with up 10 vertices, and highly favourable computational complexity, suggests even larger problems could be tackled. By replacing multiple expensive GNN operations with a single embedding stage and rapid action-selection di- rected by a recurrent unit, this work highlights the importance of, and method achieve, efficient exploration when solving CO problems, all within the broader pursuit of scalable geometric learning.
Algorithmic improvements are possible direction for further research. An adaptive (or learnt) tem- perature schedule could better trade-off stochastic exploration and deterministic solution improve- ment. ECORD also runs multiple optimisation trajectories in parallel, and so utilising information from other trajectories to either better inform future decisions or ensure sufficient diversity between them, would be another approach for improving performance.
With regards to further scaling improvements, any algorithm that labels vertices sequentially will at best have O(VV) complexity. An interesting prospect for future work would be to note that ECORD does not rely on observing the current state of the neighbourhood of vertex to evaluate the action quality - therefore one could envisage flipping multiple vertices in a single step, with a single centralised, or decentralised multi-agent, system.
An alternative direction would be to apply our algorithm to other complex problems and, in principle, ECORD could be applied to any vertex-labelling CO problem defined on graph. However, its use of 'peeks' (one-step look aheads for each action), does not directly translate to problems where the quality of intermediate actions are not naturally evaluated (e.g. those where arbitrary node labelling may be invalid such as maximum clique). Considering only valid actions or utilising indirect metrics of solution quality are possible solutions, but this remains topic for future research.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge. arXiv: /623,, 2019.
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47, 2002.
Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physies A: Mathematical and General, 15(10):3241, 1982.
Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3243-3333 3243-3250, 2020.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. arXiv: 1611.999000990,, 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: A methodological tour d' l'orrizo.. European Journal of Operational Research, 290(2): 405-421, 2021. ISSN 0377-2217.
Una Benlic and Jin-Kao Hao. Breakout Local Search for the Max-Cut problem. Engineering Appli- cations of Artificial Intelligence, 26(3):1162 1173, 2013. ISSN 0952-1976.
Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv:2103.03012, 2021.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion, arXiv: 1810.00337, 2019.
CPLEX, ILOG. 11.0 user's manual. ILOG SA, Gentilly, France, pp. 32, 2007.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6351-6361, Red Hook, NY, USA, 2017.
Curran Associates Inc. ISBN 9781510860964.
Hristo N Djidjev, Guillaume Chapuis, Georg Hahn, and Guillaume Rizk. Efficient combinatorial optimization using quantum annealing. arXiv preprint 1xXiv:801.08653 2018.
Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning solve combina- torial optimization problems real-world graphs in linear time. arXiv:2006.0377 2020.
Paul Erdös and Alfréd Rényi. On the Evolution of Random Graphs. Publ, Math. Inst. Hung. Acad, Sci, 5(1):17-600 1960.
Michel X Goemans and David P Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming. Journal of the ACM (JACM), (2(6))1115-111 1995.
Hayato Goto, Kosuke Tatsumura, and Alexander R Dixon. Combinatorial optimization by simulat- ing adiabatic bifurcations in nonlinear hamiltonian systems. Science advances, 5(4):eaav2372, 2019.
Shenshen Gu and Yue Yang. A Deep Learning Algorithm for the Max-Cut Problem Based on Pointer Network Structure with Supervised Learning and Reinforcement Learning Strategies. Mathemal- ics, 8(2), 2020. ISSN 2227-7390.
Prateck Gupta, Maxime Gasse, Elias B. Khalil, M. Pawan Kumar, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. arXiv:2006. 1.51 2020.
10

---

Under review as a conference paper at ICLR 2022
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforeement learning with a stochastic actor. In International Confer- on Machine Learning, pp. 1861-1870. PMLR, 2018.
A. Halim and I. Ismail. Combinatorial optimization: Comparison of heuristic algorithms in travel- ling salesman problem. Archives of Computational Methods in Engineering, 26:367-380, 2019.
Sung-Pil Hong. Inapproximability of the Max-cut Problem with Negative Weights. International Journal of Management Science, 14(1), 2008.
John J Hopfield and David W Tank. "Neural" Computation of Decisions in Optimization Problems. Biological Cybernetics, 52(3):141-12, 1985.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network
technique for the travelling salesman problem. arXiv: 002200000022..... 2019.
Richard M Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Com-
putations, pp. 85-103. Springer, 1972.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Op- timization Algorithms over Graphs. In Advances in Neural Information Processing Systems, pp- 6348-6358, 2017.
Timothée Leleu, Yoshihisa Yamamoto, Peter L. McMahon, and Kazuyuki Aihara. Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity. Phys. Rev. Lett., 122:040607, 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv:1511.05490 2015.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun, Combinatorial Optimization with Graph Convolu- tional Networks and Guided Tree Search. Advances in Neural Information Processing Systems, pp. 539-548, 2018.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. 100iv0/500.02997 2015.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Learning heuristics over large graphs via deep reinforcement learning. arXiv:1903.03332. 2020.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. 0XXi:2003.03360 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540)):22, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforeement learning. In International Conference Machine Learning, pp. 1928-1937. PMLR, 2016.
Alejandro Perdomo-Ortiz, Neil Dickson, Marshall Drew-Brook, Geordie Rose, and Alán Aspuru- Guzik. Finding low-energy conformations of lattice protein models by quantum annealing. Sci- entific Reports, 2:571, 2012.
Imre Pólik and Tamás Terlaky. Interior Point Methods for Nonlinear Optimization, pp-
215-276. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. ISBN 978-3-642- 11339-0. doi: 11.10079978-3--4--1133999
URL httppss//ccc..or/////.0
978 3 642 11339-01
Ilya Sutskever. Training Recurrent Neural Networks. PhD thesis, CAN, 2013. AAINS22066.
Egor Tiunov, Alexander E Ulanov, and AI Lvovsky. Annealing by simulating the coherent Ising machine. Optics Express, 10288-0088 2019.

---

Under review as a conference paper at ICLR 2022
Natalia Vesselinova, Rebecca Steinert, Daniel F. combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8:120388-12044 120416,, 2020.
and Magnus Boman. Learning
Nino Vieillard, Olivier Pietquin, and Matthieu Geist. 1440:00007.14300, 2020.
Munchausen reinforcement learning.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer Networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International Conference on Machine Learning, pp.
PMLR, 2016.
Werbos. Backpropagation through time: what it does and how to do Proceedings of the IEEE, 78(10):1500-1560 1990. doi: 10.1109/5.58337.
David P. Williamson and David Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0-521-19527-0.
Yoshihisa Yamamoto, Kazuyuki Aihara, Timothee Leleu, Ken-ichi Kawarabayashi, Satoshi Kako, Martin Fejer, Kyo Inoue, and Hiroki Takesue. Coherent Ising machines optical neural networks operating at the quantum limit. npj Quantum Information, 3(1):49, 2017.
Wang Yanling, Yang Deli, and Yan Guoqing. Logistics supply chain management based on multi- constrained combinatorial optimization and extended simulated annealing, In 2010 International Conference on Logistics Systems and Intelligent Management (ICLSIM), volume pp. 188-192, 2010.
Wei Zhang and Thomas G. Dietterich. A reinforcement learning approach to job-shop scheduling. In Proceedings of the 14th International Joint Conference on Artificial Intelligence Volume 2, IJCAI'95. pp. 1114-1120, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603638.
A APPENDIX
A.1 ARCHITECTURE DETAILS
Here we provide further details on the network architecture described section 3.2 and figure To the main text. For simplicity, implicitly drop any bias terms in the below equations.
Graph Neural Network. The gated graph convolution network of oi et al. (2015) is modified to include layer normalisation, LN(-), where the 16-dimensional embedding of node i at layer (+ 1 is given by,
1 (1+1) (N(GRU(" m ((+1)))
((+1) m
Σ JEN(S
w((e;)
(4)
N(O)
where Wg 16x16 The final embeddings after rounds of peessage-passing are linearly projected to per-vertex embeddings, = Wp with W, RR1xx1 that remain fixed for the remainder of the episode.
Value network. Recall from the main text that Q-values at time t are predicted
Qu ,n = (() + A(v!) (0) (i)) = (L + MLPA ((u W,,
(5)
where (0)) E 1024 is the hidden state the RNN and (c) = [ay, Woo (0) E R23 are the por-node embeddings with 2; R 6, W. IR 16x3 and W,, 3222 1014
The value head, MLP 1024 + R, is 2-layer network that applies tanh activation to the input and leaky ReL.U to the intermediate activations.
12

---

Under review as a conference paper at ICLR 2022
The advantage head, MLPA(-) R - R. is 2-layer network that applies layer and leaky ReLU to the intermediate activations.
Recurrent network. The RNN hidden state is 1024-dimensional and initialised to zeros. It is updated using the embedding of the selected action, v.",, and our global observation from the next step,
((+11) = -RU(A -RU((),,,(tt)) ((+)))) where (1+1) = LeakyReL. o0++))))
(6)
where Wm E RR1x31
A.2 TRAINING DETAILS
The ECORD pseudocode is given algorithm 1 Note that update the network time we make use of truncated backpropagation through time (BPTT) (Werbos, 1990, (utskever] (013) using the previous (вPтт experiences. We perform network updates every Jupt time steps, where we update the online network parameters 0 using stochastic gradient descent (SGD) on the M-DQN loss and the target network parameters 0 using soft update (Lillicrap et al. 2015) with update parameter Tupd The hyperparameters used are summarised in table
Table 3: Parameters used for ECORD unless otherwise stated.
Parameter
Value
Number training steps Batch size
40000
64
Update frequency (fupa)
8
Learning rate
le-3
Optimizer
Adam (3: 0.9,
0.999)
Soft update rate (Tupd)
0.01
BPTT length (ABPTT)
5
Buffer size (lM))
40 000
Discount factor (t)
0.7
Initial exploration probability (e (t==0))
Final exploration probability (t(t))
0.05
Time of exploration decay (fz)
5000
M-DQN temperature (r)
0.01
M-DQN bootstrap (ax)
0.9
M-DQN clipping (la)
A.3 EFFICIENT RE-CALCULATION OF CUT VALUE AND PEEKS
Given a graph, G(V, E),, with edge weights wy = w(ei)) for eij E E. and a node labelling repre- sented as binary vector, E {0, 1} VI, the cut value is given by.
C(=IG)
Σ wiy (2+(1 - 222) (1 =2))z))
2
1
Σ Wiy(2: (2: + + - 22;2))-
2
is straightforward to decompose this into the sum of 'local' cuts
C(=IG) = - Σ C.. C.
Σ wis(2 + 2j 2242)), JEN(()
where Ct, the cut value of the sub-graph containing node only i and its (V))))) Similarly, we can define the total weight of un-cut edges connected each vertex as
C
Σ JEN())
Wiz(1
2ÿ 22,2,)-
(9)
13

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Training ECORD
Initialise experience replay memory M. each batch of episodes do Sample Ba graphs G(V, E) from distribution Calculate per-vertex embeddings using GNN Initialisc random solution set for each graph, Su V for each step
the episode do k' min(t (t kBPTT, 0)
for each graph Gj in the batch do // Flip vertex.
randomly from V with prob.
a0))>
softmax (oldlor)) with prob. 1 -
(tt)) (a sit (a(0),
(f & 5()
g(++1)
if 5t0
// Aad experience to butter.
Add tuple m (s (s(t (1+1) a (1=R) , , (d M if f mod fupd
then
// Sample batch of experiences from buffer.
M C.M
// Update online network.
Update with one SGD step using BPTT from down to k on fa (??)
/ Update target network.
Oaa 0(1 Tupa)
end
end
end
end
return 8
The change in cut value (referred to as the 'peek' feature in the main text) if the label of vertex i is flipped then then given by
AC, -,==7,00 Ci
Σ
wiy(42z4) - 2(2 + 2z) 1),
JEN(1)
(10)
= Σ
Way Wiy(22; - 1)(2zz - 1).
JEN())
Calculating these one-step look-aheads to the change in cut for each action clearly the same complexity as calculating the cut-value itself (equation (7). Moreover, they only have to be calcu- lated once at the start of each episode, as when vertex is flipped from z; to E,, only the 'pecks' of vertrices i and Niii) need to be updated. These updates follow directly from the above and are given by
AC, + AC, AC, AC, W1,(22; 1)(22, 1).
(11)
A.4 MCA-SOFT
MCA-soft attempts to upper bound the performance simple policies that condition actions based solely on the provided 'pecks' for each action. Denoting the known change in cut value if vertex was to be flipped as AC; (see eq. (IT),, MCA-soft follows a stochastic policy given by
AC
softmax
(12)
Tmea
To maximise the performance of MCA-soft, the temperature, Tica E R. is independently tuned to maximise performance every set of graphs considered. In practice, this process is grid search over Tiea E {o, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1,3} for results in table and and Tinea E (0, 0.0001, 0.001, 0.01, 0.1, for results in table
14

---

Under review as a conference paper at ICLR 2022
A.5 EXTENDED RESULTS
Training BA graphs. For completeness, repeat the experiments shown in the main manuscript but now training on 40-vertex BA graphs and evaluating on both ER and BA graphs with up to 500 vertices, with the results shown in Table 4
Table 4: Scores for agents trained BA40. Error bars denote 68 % confidence intervals. RL base- line scores are taken directly from Barrett et al. (2200) to provide the fairest possible comparison. ECORD results averaged across seeds.
Hcuristics
RL basclines
MCA
MCA-soft
S2V-DQN
ECO-DQN
ECORD
BA40
0.999
0.999-9.000
+9.000
1.000 1.000-0.000
0.961 18
1.000 10
1.000-9.000
BA60
0.989
0.989-9.00
0.007
0.997 10 0.000
0.959
026
1.000
10 000
1.000 -0.000
-0.000
BA100
0.965
8.050
0.984
008
0.941
037
1.000
000
1.000
0.000
8:33
-8 833
134
18 096
BA200
0.911
0.929
0.808
0.983
0.980 0.980-1.00
BA500
0.889
0.005
8.825
0.899
-0.014
824
0.499
119
114
0.990
-0 008
8 00
0.967
00 010
0.122
ER40
0.997
0.000
1.000
+0 0000
0.970
020
1.000 +0 000
1.000
000
0
ER60
0.994
0,00S
0.999
001
0.951
+0 038
1.000
+9 00D
1.000
ER 100
0.977
0007
0.993 D0T
0.941 +0 033
1.000 +0 000
1.000 820
ER200
0.959
0.034
0.97310 012
0.933 1 024
0.004 0.994
1.000 0,000
ER500
0.941 0.022
0.012
0.958 00.00
10.00.0000 009
0.905
10 019
0.979 0000
0. 1999667 00.00-
0.004
Baseline comparison. Here we conduct a thorough solver comparison by training and inferring on both ER and BA graphs of up to 500 vertices. We compare ECORD seven baselines; six taken directly from [Barrett et al.] (2020) (ECO-DQN, S2V-DQN, MCA, CPLEX, SimCIM, and Leleu cet al. 2019); refer to Barrett al. (2220) for implementation details), and one an extension of MCA (MCA-soft, as described in this manuscript). The results are summarised in Table [ with the approximation ratios shown taken from averaging the solvers' performances across 100 BA and ER graphs of up to 500 vertices.
Table 5: Comparison of the approximation ratios for the Greedy (MCA and MCA-soft), branch-and- bound (CPLEX), simulated annealing (SimCIM and Leleu), and RL (S2V-DQN and ECO-DQN) Max-Cut solver baselines.
MCA
MCA-soft
CPLEX
SimCIM
Lelcu
S2V-DQN
ECO-DQN
ECORD
ER40
0.997
L.000
1.000
1.000
1.000
0.980
1.000
1.000
ER60
0.994
0.999
1.000
1.000
1.000
0.973
1.000
1.000
ER 100
0.977
0.993
0.870
1.000
1.000
0.961
1.000
1.000
BR200
0.959
0.973
0.460
0.990
1.000
0.951
0.999
1.000
ER500
0.941
0.958
0.160
0.990
1.000
0.921
0.985
0.996
BA40
0.990
1.000
1.000
1.000
1.000
0.961
1.000
1.000
BA60
0.989
0.997
1.000
1.000
1.000
0.959
1.000
1.000
BA 100
0.965
0.984
1.000
0.990
1.000
0.961
1.000
0.996
BA200
0.911
0.929
0.830
0.990
0.940
0,808
0.983
0,980
BA500
0,889
0.899
0.170
0.970
1.000
0.499
0.990
0.967
Semidefinite programming comparison. In addition to heuristics, another important branch of Max-Cut solver research is that of approximation algorithms. Such algorithms can offer theoretical guarantee on the approximation ratio while still solving a relaxed formulation of the original problem in polynomial time. One such approximation method is the canonical semidefinite programming (SDP) approach of Goemans & Williamson (1995). Goemans & Williamson (1995) first formulate Max-Cut as an SDP by framing the objective as linear function of a symmetric matrix subject to linear equality constraints (as in linear programme) but with the additional constraint that the matrix must be positive semidefinite (whereby, for an n X n matrix A, Vz E R x² Az 2 O). This relaxed Max-Cut SDP formulation can be solved efficiently using algorithms such as a generalised Simplex method (Pólik & Terlaky 2010 The insight of Goemans & Williamson (1995) was to then apply geometric randomised rounding technique to convert the SDP solution into feasible Max-Cut solution. Crucially, the randomised rounding method gives a guarantee to be within at least 0.87856 times the optimal Max-Cur value.
15

---

Under review as a conference paper at ICLR 2022
To the best of our knowledge, no open-access Goemans handle Max-Cut Cut problems with negatively weighted edges [Hong]200) However, G1-5 of the GSet graphs used in Table of this manuscript have possiivie edge weights, therefore we the open- source CVX solver tht.pps: :/: t chub. . com hwtp/herisshh wwtccssgracppp...oooccoaaaa a gor t. hmms), which implements Goemans & Williamson (1995), on these 5 problems to obtain approximation ratios of 0.971, 0.970, 0.975, 0.970, and 0.967 in 449, 484, 496, 521, and 599s s respectively. In addition to ECORD outperforming Goemans & Williamson (995) on these GSet graphs (see Table 2 in both solving time and optimality, we note that ECORD also exceeds the 0.87856 approximation ratio guarantee across all the GSet, ER, and BA graphs examined in our work (see Tables
open-aceessCoommmn & Williamson 1995 solver exists which can
and [
Ablations. We provide ablations to further investigate the key components of ECORD, highlighted in the main text as
1. GNN encode the spatial structure of the problem,
2. a rapid decoding conditioned on local per-node observations and an RNN's internal state that represents the optimisation trajectory.
3. an exploratory CO setting.
We ablate the GNN and RNN by using fixed zero- vectore in in-place of the static per-node embeddings, Ty and the RNN hidden state, (((t), respectively. As the advantage of exploratory CO has already been demonstrated in prior works (Barrett et al. 2020), we instead ablate the stochastic policies we find provide further improved exploration at test time (see section 4.3 of the main tex(). Specifically, we train the agent using DQN instead of M-DQN, as this optimises for a deterministic policy.
For all ablations, we otherwise use the same procedure the full ECORD agent from section 4.3 of the main text, including tuning temperature of the agents policy with a grid-search. DQN is, unsur- prisingly, found to be best at 7 = 0, as is the agent with the GNN ablated. The agent with the RNN ablated uses T of 1c-4, 5.5e-5 and 5e-5 for For G55, G60 and G70, respectively, with 5050-4 for all other graphs. Results are presented in table 6 with ECORD significantly outperforming all ablations on larger graphs.
Table 6: ECORD, including both a GNN and RNN trained with M- M-DQN, and ablations (as described in the text) on the GSet graphs given a time budget of 10, 30, and 180s s (best in bold).
No GNN
No RNN
DQN
ECORD
Graph
[V|
10s
30s
180s
10s
30s
180
10s
30
180
10s
30s
180
G1
800
1.000
0.998
1.000
0.996
0.999
0.999
0.998
1.000
G2
800
0.999
1.000
0.998
0.998
0.999
0,998
0.998
0.999
0.998
0.998
1.000
G3
800
0,999
1.000
0.998
0,999
0.989
0.996
0.999
0.999
0.999
1.000
G4
800
1.000
0.999
1.000
0.998
0.999
0.999
0.999
1.000
G5
800
1. 1.000
0.999
0.999
0.999
0.998
0.998
0.998
1.000
G43
1000
0.997
0.998
0.999
0.996
0.999
0.999
0.991
0.991
0.991
0.996
0.997
1.000
G44
1000
0.997
0.998
1.000
0.909
0.999
0.989
0.995
0.995
0.995
0.999
0.999
1.000
G45
1000
0.995
0.997
0.999
0.997
1.000
0.994
0.994
0.994
0.998
0.999
0.999
G46
1000
0.997
0.998
0.999
0.995
0.996
0.998
0.995
0.995
0.995
0.998
0.999
1 1.000
G47
1000
0.996
0.998
1.000
0.996
0.996
1.000
1.9922
0.993
0.993
0.997
0.998
0.998
G22
2000
0.990
0.991
0.994
0.990
0.995
0.999
0.987
0.959
0.989
0.990
0.995
0.997
G23
2000
0.990
0.995
0.997
0.989
0,993
0.998
0.987
0.991
0.991
0.991
0.995
0.997
G24
2000
0.993
0.998
0.990
0.993
0.996
0.987
0.959
0.989
0.992
0.991
0.997
G25
2000
0.991
0.995
0.996
0.969
0.994
0.997
0.968
0.993
0.993
0.991
0.996
0.998
G26
2000
0.989
0.984
0.997
0.991
0.994
0.908
0.991
0.994
0.994
0.991
0.996
0.999
G55
5000
0.924
0.949
0.951
0.950
0.971
0.981
0.951
0.953
0.956
0.947
0.969
0.985
G60
7000
0.796
0.933
0.950
0.900
0.953
0.972
0.918
0.949
0.951
0.916
0.960
0.981
G70
10.000
0.703
0.703
0.931
0.766
0.837
0.879
0.761
0.929
0.933
0.837
0.944
0.972
Graph network timing. As stated in the main text, the single pass of the graph neural net- work is negligible compared to the overall run time of ECORD. To be concrete, on the largest graph for which results are reported (G70 with [V] = 10k nodes), our embedding stage takes (1.96 + 0.09) ms, compared to the tens of seconds of exploratory decoding.
16


Reviews:
[{"review_id": "yAM5e-LvTNM", "reviewer": "Reviewer_5Z4N", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The proposed approach is solid. I think this algorithm can easily extended for solving combinatorial optimization problems other than the maximum cut problem.  \n2. The empirical comparison is thorough with respect to the considered baselines. \n\nCons:\n1. I am mainly concerned with the empirical comparison. \n- The maximum cut problem is a representative application of semi definite programming solvers. See [1] for an example. I think this baseline is necessary for practitioners to see whether if the proposed algorithm has any useful-ness in real-world applications. \n- Gset (considered in this paper) is a popular benchmark for the maximum cut problem and there are several non-DNN-based results that can easily compared with the proposed solvers. For example, the authors can compare with [2]. \n- To my knowledge, [3] is a relatively new GNN-based combinatorial solver that can solve maxcut. Their algorithm can be applied to maximum cut with a minor changes (they solve graph partitioning problem). This comparison is important since [2] is also a GNN-based solver with running time linear with respect to the problem size. They use a single GNN-pass and decode the solution. \n2. It seems that this paper is very similar to [4] in a sense that they both use a GNN to extract node embeddings for the given problems and applies DQN-based training for a node-wise predictor to generate solutions. I think the authors can provide a more thorough comparison between two methods. My current understanding is that [4] pretrains a GNN using supervised learning and ECORD use end-to-end truncated backpropagation.\n\nMinor comments:\n1. Ablation studies on using DQN over M-DQN would be useful to see whether if the empirical improvement comes from the proposed scheme, or simply using a better RL algorithm.\n2. I hope the authors could provide more reference and related works on ways to solve the maximum cut problem without using DNN.\n\n[1] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, 1995\n[2] Breakout Local Search for the Max-Cut Problem, 2012\n[3] Erdos Goes Neural: an Unsupervised Learning ˝ Framework for Combinatorial Optimization on Graphs, 2020\n[4] Learning heuristics over large graphs via deep reinforcement learning, 2019", "summary_of_the_paper": "This paper proposes a scalable deep neural network (DNN)-based solver for the maximum cut problem. The main idea is to use (1) a single graph neural network (GNN) pass to acquire node embeddings and (2) use sequential decoding (without using GNN) to acquire the maximum cut solution. The experiments demonstrate good performance of the proposed algorithm, in particular for speeding up the generation of solutions.    ", "summary_of_the_review": "I think this paper is based on a solid idea and shows good empirical performance. However, at the current state, it is hard to access the significance of this paper since baseline algorithms used in real-world is missing. Furthermore, I would like to see description on the proposed algorithm's difference to existing work of Manchanda et al., (2019) to further support novelty of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qBix5QCmLp", "reviewer": "Reviewer_B7TT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n- Well written paper, it was nice and easy to read\n- The paper presents a sensible approach and good motivation, where it specifically designs an architecture to minimize the computational burden of the algorithm\n- The paper addresses scaling, which is an important challenge in neural combinatorial optimization\n- The paper applies reasonable baselines such as the heuristic strategy (MCA/MCA-soft)\n- The paper takes care to conduct fair comparison (e.g. own implementation with optimizations also for ECO-DQN baseline)\n\n**Weakness**\n- The paper only considers maximum cut, while title suggests general combinatorial optimization. As multiple aspects (flipping, peek feature) are specific to max-cut it is unclear how the proposed method can generalize to other problems. I think 'Learning to Solve Maximum-Cut' would be a more suitable title for this work.\n- The approach, presented as novel RL algorithm, is very similar to ECO-DQN, but the differences are not explained, so it is unclear what are contributions and what is 'reused' from ECO-DQN. From skimming the ECO-DQN paper it seems the major differences are the architecture (GNN 'encoder' + cheap RNN policy rather than expensive GNN for every step) and algorithm (different DQN variant).\n- The term SOTA is confusing, maybe even misleading. I don't think RL/GNN is clearly SOTA for maximum cut in general (see e.g. the Leleu et al. baseline in the ECO-DQN paper), which is suggested in the abstract and title of section 4.1. To avoid confusion, I think the authors should use 'best RL-based method' and keep the term SOTA for the best exact/heuristic/RL solver in general. When claiming SOTA, I think the paper should also refer to relevant max-cut literature.\n- The experiments do not support the strong claims: generalization is only compared against ECO-DQN and not against heuristic baselines. Also, some general baselines are missing, especially LeLeu et al. from the ECO-DQN paper.\n- The theoretical novelty is limited as the 'learning to explore' idea and max-cut setup is from ECO-DQN (Barrett et al.). The idea of encoder + (rapid) decoder architecture for combinatorial problems is similar to Drori et al. (and some earlier works on neural combinatorial optimization).\n\nOverall, I like the paper but I think it is too incremental and too narrowly focused on max-cut to be published at ICLR.\n\n**Detailed comments/questions/suggestions:**\n- 'to equal or surpasses' -> 'to equal or surpass'\n- Do MCA-soft and MCA also use 50 trajectories? (I assume so but it is not mentioned)\n- Fig 2b displays linear step time, but you also run 2|V| steps so more steps for larger graphs so overall time is quadratic? Also, does blue correspond to ECORD? (labels in Fig 2a?)\n- If you did a reproduction of ECO-DQN (which is a great thing!) I think it would be helpful to list both original and reproduced results for clarity in Table 1 (unless they are very similar)\n- 'Heurisitcs' typo Table 1\n- It may be good to mention other solution strategies are possible as well, e.g. rounding a relaxed solution (https://www.cl.cam.ac.uk/teaching/1617/AdvAlgo/maxcut.pdf)\n- How does MCA and MCA-soft perform in Table 2?\n- What defines exactly ECORD when claiming/suggesting that 'in principle it could be applied to any CO problem defined on a graph' (in discussion)?\n- For the GNN 'encoder', is the input graph fully connected? If so, how does the 'encoder' scale?\n- Given the focus on max-cut only, I think some more related work on max-cut (non-RL) could be included.", "summary_of_the_paper": "This paper describes an RL based method for learning to solve the weighted maximum cut problem. Specifically, it proposes to process an input (fully connected?) graph using a gated graph recurrent network, and use the resulting embeddings as input for a computationally cheap RNN based policy that starts from a random cut (partition of nodes into two subsets) and subsequently 'flips' one of the nodes to move it to the other subset/other side of the cut. This policy ('encoder' + RNN) is trained using a variant of DQN to maximize the result obtained after 2*|V| flips, where V is the number of nodes in the graph. The policy makes use of a so called 'peek', a one-step lookahead of the result of each flip action on the current objective. At test time, the policy constructs multiple (deterministic) trajectories in parallel starting from different (random) initial solutions, where (I assume) the best overall result is returned. In experiments, the resulting algorithm, which is called ECORD, is shown to perform favorably when compared against ECO-DQN (Barrett et al. 2020), which, from skimming the paper, is very similar in strategy but uses a less efficient architecture and a different variant of DQN.", "summary_of_the_review": "Overall, I like the paper, which is quite nice to read and presents a sensible and effective approach for solving the maximum cut problem using RL. Especially, the authors specifically addressed scaling to larger instances by making the architecture more efficient, which is an important and challenging topic.\n\nUnfortunately, I still think the paper should be rejected given that\n1) it is too much focused on max-cut and unclear how this framework can solve general combinatorial problems, as the title suggests\n2) it is quite incremental to Barrett et al. (2020) AND not clear about the differences and\n3) some important baselines are missing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "T9qhV2GnXVb", "reviewer": "Reviewer_m4dC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Postiive points:\n\n+ Combinational problem is very general and could have many applications.\n+ ECORD is shown to be able to generalize to larger graphs.\n+ ECORD is shown to be more efficient than the previous methods\n+ The neural architecture is well designed with both GNN to learn vertex embeddings and value network with GRU to learn state embedding.  \n+ The paper is very well written.\n\nNegative points:\n\n- It is unclear to me how general the Max-Cut problem is. The Max-Cut is based on graph and only considers two labels. It is unclear whether ECORD can be applied to problems without graph structure or with more than two labels. In particular, when there are more than two labels, the actions space can be ill-defined since flipping will not make sense with more than two labels.\n- It is unclear whether Max-Cut is hard enough to use RL. In table 1, even greedy heuristics can have very strong performance. In terms of efficiency, the greedy heuristics should be even more efficient than ECORD.\n- It is unclear how ECORD improves the efficiency of ECO-DQN. The methodology section only introduces how ECORD is trained but never compares it with ECO-DQN.", "summary_of_the_paper": "This paper presents a RL-based algorithm for solving the graph-based combinational optimization problem of Max-Cut. The key idea is to formulate the problem as an MDP, where the state is the embedings of all the vertices and the actions are the vertices to be flipped. The idea is implemented with a graph neural network to learn the embeddings and a recurrent encoding to encode the state representations. The network is trained with M-DQN. The proposed algorithm, named ECORD, is shown to be comparable to the previous state-of-the-art ECO-DQN and be significantly faster than ECO-DQN.", "summary_of_the_review": "Overall, it remains unclear what combinational problems ECORD can address. The improvement over ECO-DQN or heuristics is not significant. It is unclear how ECORD improves ECO-DQN in terms of efficiency, which is the major contribution of this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MmvPxhY7rvK", "reviewer": "Reviewer_3ifn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although this paper has excellent motivation for improving the efficiency of current GNN based RL for CO problems, I have some concerns about the approach and experiments. \n(1)\tAlthough Maximum Cut problem is one of classic CO problem, it cannot represent all CO problem. For this reason, the title is much larger than the content of this paper, unless the authors can show the generalization of their method for other CO problem.\n(2)\tRestricting the GNN in the preprocessing step for embedding is a good idea for reducing the complexity in running time. According to experimental results, the paper states the performance is better than ECO-DQN. Then, it is very natural to raise the question: whether is the contribution of GNN very little for the performance? To answer this question, the authors should give some evidence of comparison with GNN-free graph embedding methods. \n(3)\tIn the experiments, the paper only compared with ECO-DQN and two simple heuristics, which cannot support to claim that the proposed method is better than current SOTA of approximate algorithms. Some of them are efficient for large-scaled problem too.\n(4)\tIf a max-cut problem has multiple best solutions, I wonder whether the convergence of proposed approach can be guarantee with limited learning steps? Are there some test cases for this point in experiments?\n(5)\tThe terminating condition will affect the convergence and performance of the given approach largely. The authors used 2|V| for small-scaled instances and 4|V| for large-scaled ones. Could the authors give some theoretical analysis for the necessary number of learning steps. If could not, the algorithm is hard to be used in practice.\n(6)\tThe largest problem targeted in experiments is about just 10000 nodes. In the era of big data, the scale for testing the scalability is not enough. Many real problem graphs have millions of nodes.\n", "summary_of_the_paper": "To deal with the efficiency and scalability issues in current RL approaches for Max-Cut problem, this paper proposes a new method called ECORD, based on Munchausen DQN’s exploration with GNN pre-computed embedding of each vertex. Running Time Complexity is analyzed. Compared with current baselines, time complexity is reduced from O(|V|^3) to O(|V|^2). Experiments, are conducted on published dataset, show its superiority in efficiency and performance. ", "summary_of_the_review": "Although this paper has excellent motivation for improving the efficiency of current GNN based RL for CO problems, I have some concerns about the approach and experiments. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an efficient RL-based approach for solving the weighted maximum cut problem. The proposed approach shares high-level insights with prior work such as ECO-DQN (Barrett et al.) and S2V-DQN; the key contribution is to demonstrate that the proposed cheap action decoding and stochastic policy strategy can improve the scalability without sacrificing much of the quality of the solution on the tasks considered in this paper.

The reviewers in general find the paper well presented, and especially note that the clear motivation for improving the efficiency of current GNN-based RL baselines, particularly represented by ECO-DQN. 

A common concern among the reviewers is that the original title is misleading; the authors acknowledge that they should properly position the paper to avoid confusion that they were to address general combinatorial optimization problems (as the current title suggests). Notably, many combinational optimization problems can be reduced to max-cut as suggested in the authors’ responses; demonstrating the performance in (some of) these problems via a max-cut reduction would be helpful to support the significance of this work.

Beyond the title and positioning of this work, there were also initial confusions among the committee in terms of the choice of both (RL or supervised) learning-based and heuristic-based baselines. The authors did an excellent job in clarifying many of the questions in terms of related work and baselines (the clarity of the work has improved over the rebuttal phase). However, despite the additional ablation study and newly added baselines, there remain concerns/questions in the choice of task domains (lack of hard problem instances where existing solvers, learning- or heuristics -based may fail due to (possibly higher) computational complexity). Given the empirical focus of the paper, this appears to be an important concern, and not all reviewers are convinced the current empirical results are significant to warrant acceptance of this work.
Decision: Reject