A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
Year: 2021

Abstract:
Combinatorial Optimization (CO) has been a long-standing challenging research topic featured by its NP-hard nature. Traditionally such problems are approximately solved with heuristic algorithms which are usually fast but may sacrifice the solution quality. Currently, machine learning for combinatorial optimization (MLCO) has become a trending research topic, but most existing MLCO methods treat CO as a single-level optimization by directly learning the end-to-end solutions, which are hard to scale up and mostly limited by the capacity of ML models given the high complexity of CO. In this paper, we propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph (e.g. add, delete or modify edges in a graph), fused with a lower-level heuristic algorithm solving on the optimized graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity. The experiments and results on several popular CO problems like Directed Acyclic Graph scheduling, Graph Edit Distance and Hamiltonian Cycle Problem show its effectiveness over manually designed heuristics and single-level learning methods. Code available at https://github.com/Thinklab-SJTU/PPO-BiHyb.

heading: 1 Introduction
text: Combinatorial Optimization (CO) is a family of long-standing optimization problems. A large portion of CO problems is NP-hard due to the combinatorial nature, raising challenges for traditional (exact) solvers on even medium-sized problems. Heuristic algorithms are often adopted to approximately solve CO problems within an acceptable time, and there is a growing trend adopting modern datadriven approaches to solve CO problems that achieve better and faster results [30].
The major line of works solving CO with machine learning (ML) is single-level [8, 25, 29, 30, 39, 41, 57, 59, 64], where the prediction of ML module lies in the solution space, assuming the model has enough capacity learning the input-output mapping of the CO problem. However, achieving such an assumption is non-trivial, leading to the following two aspects of challenges. On the one hand, it is challenging to design a model with enough capacity with limited computational resources, and existing models are usually tailored for specific problems which require heavy trailand-error [25, 57, 59]. On the other hand, training such a heavy model requires either supervision from high-quality labels [31, 57, 60] which are infeasible to obtain for large-sized problems due to the NP-hard nature, or reinforcement learning (RL) [8, 30, 38, 39] which might be unstable due to the challenges of large action space and sparse reward especially for large-sized problems [52]. ∗Part of the work was done while the first author was working as an intern at Ant Group. †Junchi Yan is the corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021), virtual.
An alternative approach resorts to a hybrid machine learning and traditional optimization pipeline [11, 18, 26, 31, 51, 60, 61] hoping to utilize the power of traditional optimization methods. However, designing a general hybrid MLCO approach is still non-trivial, as existing methods [11, 60] usually require domain-specific knowledge for the model design. It is again challenging to obtain highquality supervision labels, and existing methods are based on either problem-specific surrogate labels [18, 31, 60], or learned with RL while the challenges of RL still exist [11, 51].
In this paper, we propose a general hybrid MLCO approach over graphs. We first reduce the complexity of deep learning model by reformulating the original CO into a bi-level optimization, whose objective is to minimize the long-term upper-level objective by optimizing the graph structure, and the lower-level problem is handled by an existing heuristic. We resort to RL and the traditional heuristic can be absorbed as part of the environment, and it is shown that the sparse reward issue is mitigated for the resulting RL problem compared to previous RL-based methods [8, 30, 38, 39]. Specifically, our model is built with standard building blocks: the input graph is encoded by Graph Convolutional Network (GCN) [32], and the actor and critic modules are based on ResNet blocks [22] and attention models [55]. All modules are learned with the Proximal Policy Optimization (PPO) algorithm [48]. The contributions of this paper include:
• To combine the best of the two worlds, we propose a general hybrid approach that integrates traditional heuristic solvers with machine learning algorithm.
• We propose a bi-level optimization formulation for learning to solve CO on graphs. The upper-level optimization adopts a reinforcement learning agent to adaptively modify the graphs, while the lowerlevel optimization involves traditional learning-free heuristics to solve combinatorial optimization tasks on the modified graphs. Our approach does not require ground truth labels.
• The experiments for graphs up to thousands of nodes on several popular tasks such as Directed Acrylic Graph scheduling (DAG scheduling), Graph Edit Distance (GED), and Hamiltonian Cycle Problem (HCP) show that our method notably surpasses both traditional learning-free heuristics and single-level learning method. Our method generalizes well to graphs of different sizes while having comparable overhead to the single-level learning methods.

heading: 2 Related Work
text: Here we discuss related works listed in recent surveys [4, 62, 63]. We present their methodologies and compare with our method.
Learning the end-to-end solution as a sequence. The major line of existing MLCO works mainly focus on tackling the problem end-to-end by predicting a sequence of solutions [25, 29, 30, 35, 39, 41, 57, 59, 64]. The pioneering work [57] is designated for traveling salesman problem (TSP), whereby the sequence-to-sequence Pointer Network (PtrNet) model is learned with supervised learning. In [30], a graph-to-sequence framework is proposed with graph embedding [10] and Q-learning [40] for general CO over graphs, and this general framework inspires the major line of MLCO works with applications to DAG scheduling [39], graph matching [36], and job shop scheduling [64]. [35] extends [30] by problem reduction and supervised learning-based tree search. The framework in [30] is treated as the RL baseline in this paper. Our approach differs from these single-level end-to-end RL methods [30, 36, 38, 39], which lack the flexibility to borrow the power of traditional methods and often suffer from the fundamental issues in RL: sparse reward and large action space.
Learning to rewrite end-to-end solutions. Another line of end-to-end learning works predicts rewriting strategies of an existing solution [8, 38], where the model predictions also lie in the solution space. The agents learn to improve an existing solution in a decision sequence, and problems like job scheduling, expression simplification and routing problems have been studied. These learning-based local search heuristics also fall within the single-level paradigm, while our method incorporates another optimization over the graph structure. The sparse reward issue also exists for [8, 38], as a long episode is usually required for searching for a satisfying result.
One-shot unsupervised end-to-end learning. There is also a growing trend applying one-shot unsupervised methods for the input-output mapping of CO, with maximum clique and graph cut solved by [29], and quadratic assignment problem solved by [59]. However, the generalization ability of these methods is still an open question, and complicated constraints are often non-trivial to be
encoded in the network’s prediction. Moreover, such a one-shot end-to-end network often calls for much higher model capacity compared with our multi-round alternating optimization paradigm.
Hybrid of machine learning and traditional solvers. Different from learning the solution endto-end, researchers also propose hybrid machine learning and traditional solver approaches. ML modules are studied as sub-routines for traditional solvers, especially predicting branching strategies for branch-and-bound with either supervised learning [18, 31] or reinforcement learning [51]. In [60], the heuristic routine in A* algorithm is replaced by graph neural network to solve graph edit distance. However, these methods are tailored for special problems, and our aim is to develop a more general framework, where the learning part and heuristic module are two peers alternatively performed.
Bi-level optimization. Our method is based on bi-level optimization, which is a family of optimization problems where a lower-level optimization is nested inside an upper-level optimization. Bi-level optimization is in general NP-hard [27, 56], and the applications of bi-level optimization can be found ranging from multi-player games [27] to vision tasks [37], and there is a loosely relevant attempt [2] adopting supervised learning to solve a bi-level optimization for transportation.

heading: 3 Our Approach
text: In this paper, we propose a Bi-level Hybrid (BiHyb) machine learning and traditional heuristic approach. Sec. 3.1 shows both single-level and bi-level formulations of CO, and Sec. 3.2 shows the RL approach to the bi-level CO.

heading: 3.1 Bi-level Reformulation of Combinatorial Optimization
text: Without loss of generality, we consider the classic single-level CO with a single graph G as: min x f(x|G) s.t. hi(x,G) ≤ 0, for i = 1...I (1)
where x denotes the decision variable (i.e. solution), f(x|G) denotes the objective function given input graph G and hi(x,G) ≤ 0 represents the set of constraints. For example, in DAG scheduling, the constraints enforce that the solution x, i.e. the execution order of the DAG job nodes, lies in the feasible space and does not conflict the topological dependency structure of G. The popular framework of existing MLCO methods regards Eq. 1 as a straight-forward end-to-end learning task, and various training methods have been developed, including: 1) supervised learning [41, 57] obtaining training labels by solving small-scaled Eq. 1 with traditional solvers, however it is nearly infeasible to solve larger NP-hard problems; 2) unsupervised learning [29, 59] adopting the continuous relaxation of Eq. 1 as the learning objective, but existing methods face challenges when dealing with complicated constraints; and 3) reinforcement learning [8, 30] by predicting x sequentially, but the reward signal is unavailable until x reaches a complete solution, leading to the sparse reward issue.
To ease the challenges introduced by the single-level formulation, we resort to the classic idea of modifying the original problem to aid problem solving, e.g. adding cutting planes for integer programming [19, 54]. Our proposed framework is capable of handling CO on graphs if all constraints can be encoded by the graph structure, and our motivation is described by the following hypothesis:
Algorithm 1: Policy Roll-out for Bi-level Learning of Hybrid MLCO Solver (BiHyb) Input: Original graph G; Max number of actions K.
1 G0 ← G; 2 for k← 0 ... (K − 1) do 3 Predict P (a1), P (a2|a1) on Gk and sample a1,a2; # upper-level optimization for learning 4 Gk+1← add, delete or modify the edge (a1,a2) in Gk; # state-transition 5 xk+1← solve argminxk+1 f(xk+1|Gk+1) by heuristic algorithm; # lower-level optimization 6 rk ← f(xk|G)− f(xk+1|G); # reward
Output: A list of rewards {r0...rK−1}.
The optimal solution x∗ to G can be acquired by modifying G. And we show the feasibility of this hypothesis for a family of problems by introducing the following proposition:
Proposition. We define G as the set of all graphs that can be modified from G, and X as the set of all feasible solutions of G. If the heuristic algorithm is a surjection from G to X, for G and its optimal solution x∗, there must exist G∗ ∈ G, such that x∗ is the output of the heuristic by solving G∗.
Proof. By the definition of surjection, since x∗ ∈ X, there must exist at least one graph G∗ ∈ G such that x∗ is the output of the heuristic algorithm by solving G∗.
We take DAG scheduling as an example to clarify this Proposition. Without loss of generality, we define processing the nodes 1 to n sequentially as a feasible solution. Then, we can modify the graph as follows: if the edge connecting i to i+ 1 does not exist, it is added. After adding all edges from 1 to n, processing the nodes from 1 to n sequentially is the only feasible solution, which is also the output of any heuristic algorithm. The above construction method applies for all solutions in X. Some Remarks. Our hypothesis and proposition provide the theoretical grounding of developing graph-modification methods to tackle combinatorial problems. It is worth noting that G∗ only suggests that graph modification is a promising direction and finding G∗ given G is usually NP-hard in practice. In this paper, we propose to improve the solving quality for heuristic algorithms by finding optimized (not necessarily optimal) graphs by learning based on the bi-level reformulation of the original single-level problem. Due to practical reasons, we restrict the max number of modifications.
In the bi-level reformulation of the original single-level problem, an optimized graph G′ is introduced:
min x′,G′
f(x′|G) s.t. Hj(G′,G) ≤ 0, for j = 1...J
x′ ∈ argmin x′ {f(x′|G′) : hi(x′,G′) ≤ 0, for i = 1...I}
(2)
where f(x′|G), f(x′|G′) are the objectives for upper- and lower-level problems, respectively. The lower-level problem is the CO given the optimized graph G′, which is solved by a heuristic algorithm. The solved decision variable x′ is further fed to the upper-level problem, whose objective f(x′|G) denotes the original CO objective computed by x′. The upper-level constraints Hj(G′,G) ≤ 0 ensure that the feasible space of G′ is a subset of G, and G′ has at most K modification steps from G. The upper-level problem optimizes G′ by an RL agent, by regarding Eq. 2 as the environment.

heading: 3.2 Reinforcement Learning Algorithm
text: We resort to reinforcement learning to optimize G′ in Eq. 2, which can be viewed as a data-driven embodiment of the classic bi-level optimization method by solving two levels of problems alternatively [53]. In Sec. 3.2.1 we present the Markov Decision Process (MDP) formulation of the bi-level optimization in Eq. 2, in Sec. 3.2.2 we describe the PPO learning algorithm in our approach.

heading: 3.2.1 The MDP Formulation
text: Eq. 2 is treated as the learning objective and optimized by RL in a data-driven manner. In this section, we discuss the Markov Decision Process (MDP) formulation for adopting RL to this bi-level optimization problem. The policy roll-out steps are summarized in Alg. 1. In the following, G0 equals G meaning the original graph, and Gk(k 6= 0) equals G′ meaning the modified graph after action k.
State. The current graph Gk is treated as the state, whose nodes and edges encode both the problem input and the current constraints. The starting state G0 represents the original CO problem. Action. The action is defined as adding, removing or modifying an edge in Gk. Since there are at most m2 edges if Gk has m nodes, we shrink the action space to O(m) by decomposing the edge selection as two steps: firstly selecting the starting node, and then selecting the ending node.
State transition. After taking an action, Gk transforms to Gk+1 with one edge modified. The new graph Gk+1 is regarded as the new state and is adopted for reward computation. The episode ends when it reaches the max number of actions K. In our implementation, we empirically set K ≤ 20 for graphs up to thousands of nodes, therefore the sparse reward issue is mitigated compared to single-level RL methods (20 actions v.s. 1000+ actions per episode).
Reward. The new graph Gk+1 results in a modified lower-level optimization problem whose objective becomes f(xk+1|Gk+1), and xk+1 is solved by an existing heuristic. The reward is computed as the decrease of upper-level objective function given xk+1: reward = f(xk|G)− f(xk+1|G).

heading: 3.2.2 Proximal Policy Optimization (PPO)
text: We resort to the popular Proximal Policy Optimization (PPO) [48] as the RL framework. PPO is the simplified version of Trust Region Policy Optimization (TRPO) [47] where the model update is restricted within a “trust region” to avoid model collapse. PPO is easier to implement than TRPO with comparative performance [48], maximizing the objective: J(θ) = min(rθ ·A, clip(rθ, 1− , 1+ )·A) where rθ is the importance sampling ratio parameterized by model parameter θ, A is the advantage value computed by the discounted accumulative reward minus the critic network prediction, and is a hyperparameter controlling the boundary of trust region. Some common policy-gradient training tricks are also adopted: we normalize the accumulated rewards during model update, and we add an entropy regularizer to encourage exploration beyond local optimums.

heading: 4 Experiments and Case Studies
text: We show the implementations and experiments on three challenging CO problems: DAG scheduling in Sec. 4.1, graph edit distance (GED) in Sec. 4.2, and Hamiltonian cycle problem (HCP) in Sec. 4.3. Our bi-level RL method PPO-BiHyb is compared with learning-free heuristics, and a single-level RL peer method namely PPO-Single following the general framework [30], which also covers the majority of RL-based methods [15, 25, 33, 36, 39, 64]. We also implement Random-BiHyb which performs random graph modification under our bi-level optimization framework. The model capacity and training/inference time of PPO-Single are kept in line with PPO-BiHyb for fair comparison.

heading: 4.1 Case 1: DAG Scheduling
text: The Directed Acyclic Graph (DAG) is the natural representation of real-world jobs with dependency, and the DAG scheduling problem is the abstraction of parallel job scheduling in computer clusters: each node represents a computation job with a running time and a resource requirement, and the node may have several parents and children representing data dependency. The cluster has limited total resources, and jobs can be executed in parallel if there are enough resources and the concurrent jobs do not have data dependency. Such an optimization problem is in general NP-hard [14], and the objective is to minimize the makespan of all jobs, i.e. finish all jobs as soon as possible.

heading: 4.1.1 Implementation Components
text: MDP Formulation. As shown in Fig. 2(a), state is the current DAG Gk, action is defined as adding an edge to Gk, resulting in a new DAG Gk+1. The added edge enforces additional constraints such that the decision space is cut down to elevate the heuristic’s performance. Here x represents the scheduled execution order, and the Critical Path heuristic is adopted on Gk+1 to compute xk+1. The reward is computed by subtracting the previous makespan by the new makespan: f(xk|G)− f(xk+1|G). State Encoder. We adopt GCN [32] to encode the state represented by DAG. Considering the structure of DAG, we design two GCNs: the first GCN processes the original DAG, and the second GCN processes the DAG with all edges reversed. The node embeddings from two GCN modules are concatenated, and an attention pooling layer is adopted to extract a graph-level embedding.
n = [ GCN1(Gk) || GCN2(reverse(Gk)) ] , g = Att(n) (3)
where n (# of nodes × embedding dim) is the node embedding, [· || ·] means concatenation. Actor Net. To reduce action space, the edge selection is decomposed into two steps: first selecting the starting node and then the ending node. The action probabilities of selecting the starting and ending nodes are predicted by two independent 3-layer ResNets blocks [22], respectively, and the input of the second ResNet contains additionally the feature vector of the selected starting node.
P (a1) = softmax(ResNet1([n || g])), P (a2|a1) = softmax(ResNet2([n || n[a1] || g])) (4) the subscript of n[a1] denotes the embedding for a node a1. For training, we sample a1,a2 according to their probabilities P (a1), P (a2|a1) respectively. For testing, beam search is performed with a width of 3: actions with top-3 highest probabilities are searched, and all searched actions are evaluated by the improvement of makespan, and only the top-3 actions are maintained for the next search step.
Critic Net. It is built by max pooling over all node features, and the pooled feature is concatenated with the graph feature from state encoder, and finally processed by another ResNet for value prediction.
Ṽ (Gk) = ResNet3 ([maxpool(n) || g]) (5)
Heuristic Methods. Solving DAG scheduling with hundreds of nodes is nearly infeasible for existing commercial solvers, and real-world scheduling problems are usually tackled by fast heuristics e.g. Shortest Job First which schedules the shortest job greedily and Critical Path algorithm which prioritizes jobs on the critical path. We also consider the novel Tetris scheduling [20] where jobs are arranged as a Tetris game on the two-dimension space of makespan and resource. Since Critical Path is empirically ef-
fective, we use it as the lower level optimization algorithm in our PPO-BiHyb learning method.
Learning Methods. There are some efforts to train a scheduler in data centers with RL [39] and learning a job shop scheduler with RL [64]. They can be viewed as embodiments with tailored techniques for specific problems based on the end-to-end single-level pipeline [30]. Since the problem settings in [39, 64] are different with ours, we re-implement the single-level RL baseline PPO-Single following [30], where the model details are in line with our PPO-BiHyb. To validate the effectiveness of PPO, we also compare Random-BiHyb which performs random search instead of PPO when modifying the graph, and its search steps are equal to PPO-BiHyb.

heading: 4.1.2 Experimental Results
text: Results are reported for scheduling jobs from TPC-H dataset3, which is composed of businessoriented queries and concurrent data modifications, represented by Directed Acyclic Graphs (DAGs). Each DAG represents a unique computation job, and each node in DAG has two properties: execution time and resource requirement. The DAG in TPC-H dataset has 9.18 nodes in average, and the smallest job has 2 nodes and the largest one has 18 nodes. The average resource requirement is
3http://tpc.org/tpch/default5.asp
125.8, and the minimum is 1 and the maximum is 593. The average task duration is 1127.2 sec, and the minimum is 16.3 sec and the maximum is 4964.5 sec. We jointly schedule multiple DAGs and assume there are 6000 total resources (i.e. the heaviest job node consumes around 10% of total resources), to reflect real-world business scenarios. We build 50 training and 10 testing samples for all experiments, where each sample is composed of a number of DAGs (e.g. 50, 100, 150) which are randomly sampled from the TPC-H dataset with fixed random seed.
Table 1 reports the result on scheduling jobs from TPC-H dataset, where our PPO-BiHyb outperforms learning-free heuristics and the single level learning method. We control the beam search width of PPO-Single as 10 allowing its inference time to be 10× longer than ours, but its performance is still inferior to the heuristic Critical Path method. Random-BiHyb can improve the lower-level heuristic algorithm but its performance is still inferior to PPO-BiHyb, suggesting the effectiveness of both our bi-level optimization framework and PPO training. We also study the generalization of our learning approach, which is critically important for real-world applications. As shown in Fig. 3, our models are learned with TPC-H-50/100/150 datasets, and we report their test results on the unseen datasets ranging from TPC-H-50 to 300 at 50 interval. The plotted results are the improvement of makespan w.r.t. Critical Path. All our learning models generalize well with unseen data, even on larger problems with up to 300 DAGs (∼2800 nodes). The generalization results of PPO-Single are omitted because they are consistently inferior to the Critical Path heuristic. The reason that our method generalizes soundly, in our analysis, is because learning the graph-optimization strategy is easier compared to directly learning the solution, and the strength of heuristics is exploited with our approach.

heading: 4.2 Case 2: Graph Edit Distance
text: The graph edit distance (GED) problem is NP-hard [1] and can be readily used in modeling a family of pattern recognition tasks requiring to measure the similarity between graphs, with applications to drug discovery [43], malware detection [34] and scene graph edition [7]. Given two graphs, the objective is finding the cheapest edit path from one graph to the other, and the costs of edit operations are defined by problem-specific distance metrics. For example, for molecule graphs, we may define an edit cost between different atom types (i.e. different node types), and also an edit cost for creating/removing a chemical bound (i.e. adding/removing an edge).

heading: 4.2.1 Implementation Components
text: Bi-level Optimization Formulation. Since GED involves two graphs, the formulation of the bi-level optimization of GED is a generalization from Eq. 2:
min x′,G′1
f(x′|G1,G2) s.t. Hj(G′1,G1) ≤ 0, for j = 1...J
x′ ∈ argmin x′ {f(x′|G′1,G2) : hi(x′,G′1,G2) ≤ 0, for i = 1...I}
(6)
where f(x′|G1,G2) is the upper-level objective: the graph edit cost given G1,G2 and x′. The decision variable x′ encodes the node editions from G1 to G2, based on which the edge editions can be induced. The upper-level constraints Hj(G′1,G1) ≤ 0 ensure that G′1 has at most K modification steps from G1. The lower-level GED problem is defined between G2 and the modified G′1, where f(x′|G′1,G2) is the lower-level objective, and hi(x′,G′1,G2) ≤ 0 are the constraints of the lower-level GED.
MDP Formulation. As shown in Fig. 2(b), since there are two graphs, we discriminate the graphs by subscripts G1,G2, and the MDP formulation is a generalized version of Sec. 3.2.1. More specifically, the RL agent is restricted to modifying G1 and keeping G2 fixed. The state is defined as the current version of first graph Gk1 , and action is defined as adding or removing an edge from Gk1 . The new graph Gk+11 is designed to better align with G2, where the node-to-node alignment is encoded by the decision variable xk which is obtained by solving f(xk|Gk1 ,G2) with IPFP heuristic. The upper-level objective f(xk|G1,G2) is computed as the edit distance between the original graphs G1,G2 using xk. State Encoder. The state encoder is built with GCN [32] to aggregate graph features and SinkhornKnopp (SK) network [49] for propagation across two graphs. Following [58], the SK module accepts a similarity matrix (by inner-product of n1 and n2), and outputs a doubly-stochastic matrix which can be utilized as the cross-graph propagation weights. As the action is taken on the first graph, we compute the difference of the node features of graph 1 and the propagated features from graph 2 through SK net. Similar to the DAG model, graph-level features are obtained via attention pooling.
n1 = GCN(Gk1 ), n2 = GCN(G2), n = n1 − SK(n1n>2 ) · n2; g1 = Att(n1), g2 = Att(n2) (7)
Actor Net. The action of selecting an edge to add or delete is also decomposed by two node-selection steps. The starting node selection is predicted by 3-layer ResNet module, and the ending node selection is predicted by an attention query. The edge is deleted if it already exists, or added otherwise. The beam width is set as 3 during evaluation.
P (a1) = softmax (ResNet(n)) , P (a2|a1) = softmax(n · tanh(Linear (n[a1]))>) (8)
Critic Net. We follow the graph-wise similarity learning method [3] to implement the critic net, where the graph-level features are processed by a neural tensor network (NTN) [50] followed by 2 fully-connected regression layers whose output is one-dimensional:
Ṽ (Gk1 ,G2) = fc (NTN (g1,g2)) (9)
Heuristic Methods. Based on the comprehensive evaluation on different GED heuristics by [5], we select 4 best-performing heuristics: Hungarian [44] which simplifies the original problem to a bipartite matching problem, RRWM [9] which solves GED via relaxed quadratic programming, Hungarian-Search [45] which is a search algorithm guided by Hungarian heuristic, and IPFP [6] which combines searching and quadratic programming. We empirically find IPFP best performs among all heuristics, therefore we base our PPO-BiHyb method on it.
Learning Methods. There are efforts to learn graph-wise similarity via deep learning [3, 34], which are regression models and ignores the combinatorial nature of graph similarity problems. [60] proposes neural-guided A* search, however, the learning is supervised. In this paper, we compare with PPO-Single by reimplementing [36] for GED. The model details and RL algorithm are kept in line with our PPO-BiHyb for fair comparison. The beam search width of PPO-Single is set to 20 so that the inference time of PPO-Single is comparable with our hybrid method. We also compare with Random-BiHyb which performs equal step numbers of random search w.r.t. PPO-BiHyb.
4.2.2 Experimental Results
Results on GED are reported on AIDS dataset4 containing chemical compounds for anti-HIV research [43]. The atoms are treated as nodes, and the atom types are encoded by one-hot features and we define an edit cost of 1 for different node types. Besides, we also define the cost for node/edge addition/deletion as 1. The AIDS dataset is split into three subsets w.r.t. the size of graphs, namely AIDS-20/30, AIDS-30/50, and AIDS-50+, and we exclude graphs smaller than 20 nodes because they are less challenging and can be solved exactly within several hours. We randomly build 50 training and 10 testing samples for all tests with fixed random seed.
The evaluation for GED on AIDS is presented in Tab. 2, where our method surpasses all learning-free heuristics and also performs better than single-level RL baseline PPO-Single. We also conduct a
4https://wiki.nci.nih.gov/display/NCIDTPdata/AIDS+Antiviral+Screen+Data
generalization study among different problem sizes, and Fig. 4 shows the objective scores from the sensitivity test for training/testing on GED problems with different sizes. The color map represents the percentage of improvement w.r.t. IPFP, where the darker color means more improvement. Our model can generalize to problem sizes unseen during training, but the generalized performance is usually inferior compared to training and testing with the same problem size.

heading: 4.3 Case 3: Hamiltonian Cycle Problem
text: The Hamiltonian cycle problem (HCP) arises from the notable problem of seven bridges of Königsberg proposed by Leonhard Eule [12]. Given a graph, the HCP arises as a decision problem on whether there exists a Hamiltonian cycle, which is known to be NP-complete [17]. We handle HCP by transforming it into the more general traveling salesman problem (TSP) in a fully-connected graph, where the existing edges in HCP are defined with length 0, and non-existing edges are with length 1. If a tour is found whose length is 0, then it is a Hamiltonian cycle. It is worth noting that HCP has not been discussed by most ML-TSP works [15, 28, 33, 57], which focus on the special case of Euclidean TSP with 2D coordinates.

heading: 4.3.1 Implementation Components
text: MDP Formulation. The HCP instances are converted to TSP as discussed above, to leverage existing powerful TSP heuristics. As shown in Fig. 2(c), state is defined as the current graph Gk and action is defined as increasing an edge length in Gk, resulting in a new graph Gk+1. The increase of edge length softly prohibits the heuristic from traveling this edge and the LKH method [23] is adopted on graph Gk+1 to obtain the new tour xk+1. The reward is the decrease of the current tour length w.r.t. the previous tour length: f(xk|G)− f(xk+1|G). State Encoder. We encode HCP graph with GCN [32]. The node embeddings from GCN modules are then processed by an attention pooling layer to extract a graph-level embedding.
n = GCN(Gk), g = Att(n) (10)
Actor Net. After obtaining the tour solved by the heuristic algorithm, we increase the length of any selected edge by 10 from the tour (10 is randomly set, and our approach seems not sensitive to this number), which empirically makes the edge harder to be selected in a tour later. The first action probabilities of selecting the starting node are predicted by a 3-layer ResNet block [22]. The second action is selecting the ending node, which is adjacent to the starting node on the tour and is predicted by an attention query.
P (a1) = softmax(ResNet1([n || g])), P (a2|a1) = softmax ( n · tanh(Linear(n[a1]))> ) (11)
For training, we sample a1,a2 according to P (a1), P (a2|a1). For evaluation, we perform a beam search with a width of 12 and maintain the top-12 actions by the improvement of the LKH algorithm.
Critic Net. It is built by max-pooling from all node features, and the pooled feature is concatenated with the graph-level feature from the state encoder, which are finally processed by a 3-layer ResNet.
Ṽ (Gk) = ResNet2 ([maxpool(n) || g]) (12)
Heuristic Methods. The performance of heuristics varies with the sizes and characteristics of instances. We choose three algorithms, Nearest Neighbour [42] who greedily travels to the next nearest node, Farthest Insertion [46] who repeatedly insert the non-traveled node with the farthest distance to the existing tour, and the third version of Lin-Kernighan Heuristic (LKH3) [23] which succeeds in discovering the best-known solutions for many TSP instances. For LKH3, we can set the number of random restarts (5 by default) to trade-off time for accuracy. We name the default LKH config as LKH3-fast which is also adopted for lower-level optimization in our PPO-BiHyb for its time-efficiency, and we also compare with LKH3-accu with 100 random restarts.
Learning Methods. Most deep learning TSP models are designated to handle fully connected 2D Euclidean TSP [15, 28, 33, 57], which is a different setting compared to our HCP testbed. Therefore, we implement PPO-Single following the most general framework [30], and the model details are kept in line with our PPO-BiHyb. We also compare with the Random-BiHyb baseline.

heading: 4.3.2 Experimental Results
text: We use the FHCP benchmark [21] composed of 1001 hard HCP instances. All instances are known to have valid Hamiltonian cycles, however, finding them is non-trivial for standard HCP/TSP heuristics. Table 3 shows the result from a subset of FHCP benchmark. As mentioned in Sec. 4.3.1, we convert HCP instances to binary TSP instances, whose tour lengths are denoted as “TSP objective”. When the TSP objective is 0, it means that a Hamiltonian cycle is found. We use 50 training instances and 20 testing instances, and the model is trained on graphs of sizes from 250 to 500. Our method is comparative with the novel heuristic LKH3-accu and can even surpass in terms of found Hamiltonian cycles, which is the objective of HCP. We set the beamwidth of PPO-Single as 12 allowing its inference time to be 10× longer than ours, but its performance is still inferior to our bi-level PPOBiHyb. The Random-BiHyb baseline also improves the performance of LKH3-fast which is adopted for solving the lower-level problem.

heading: 5 Discussions
text: Limitations in model design. In this paper, we adopt the vanilla GCN implemented by TorchGeometric [13], and the detailed configurations can be found in Appendix C. The main purpose of our model design is to validate the effectiveness of the proposed bi-level optimization framework, and we adopt standard building blocks without heavy engineering, from which perspective we agree that there are room for further improvement. One possible direction may be adopting GNN-neural architecture search methods [16, 65].
Potential negative impacts. Our approach may potentially decrease the job opportunities and burden the workload of employees in companies, and it calls for the companies and social groups to take more responsible roles when facing the negative effects that come along with optimization tools.
Conclusion. We present a bi-level optimization framework based on hybrid machine learning and traditional heuristics, where the graph structure is optimized by RL to narrow down the feasible space of combinatorial problems. The new optimization problems are solved by fast heuristics. Experiments on large real-world combinatorial problems show the effectiveness of our approach. Our method also shows good generalization ability from small training instances to larger testing instances.
Acknowledgments and Disclosure of Funding
This work was partly supported by National Key Research and Development Program of China (2020AAA0107600), Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102), NSFC (U19B2035, 61972250, 72061127003), and Ant Group through Ant Research Program. The author Runzhong Wang was also partly supported by Wen-Tsun Wu Honorary Doctoral Scholarship, AI Institute, Shanghai Jiao Tong University. We would also like to thank Chang Liu, Jia Yan and Runsheng Gan for their valuable discussions when we were working on this paper.

Review summaries:
This paper presents an interesting idea to solve Combinatorial Optimization on Graphs by using Reinforcement Learning in order to modify the underlying graph in order to make it easier for a heuristic algorithm. The reward for the RL algorithm is simply the increase found by the heuristic algorithm between the original graph and the modified one. The authors test their algorithm on several real-world dataset related to DAG scheduling, graph edit distance and hamiltonian cycle problem.

While many approaches have been proposed for the combinatorial optimization on graphs, authors propose a bi-level framework that incorporates the conventional heuristic solvers into MDP setting. In particular, three kinds of combinatorial problems -- DAG scheduling, graph edit distance, and Hamiltonian cycle problem (HCP) -- are solved by the proposed framework. The main idea of the framework is to apply RL to modify a given (constraint) graph so that a heuristic algorithm over the modified graph can result in the (near-)optimal solution of the original problem. For the framework to work well, the modification of the graph should occur in the direction that 1) the feasible space needs to be reduced and 2) the updated objective function value should be minimized in the end. Experimental results show that the proposed method outperform baseline models on DAG scheduling and graph edit distance problem, while showing comparable performance with the best baseline model on HCP.  The main contributions of the paper is as follows. First, the idea of modifying original graph constraints to find better solutions by using heuristic algorithms is very unique and worth checking. Second, the combination of heuristic algorithms and RL is also a nice direction of solving the combinatorial problem. Finally, authors formulate the three kinds of typical combinatorial problems into the proposed framework and show experimental results on benchmark datasets.

This paper is part of the newly emerging literature on solving combinatorial optimization problems using machine learning approaches (particularly reinforcement learning). It focuses on problems on graphs. It proposes a new hybrid approach which uses RL to modify the structure of the input graph into a surrogate graph, which is then given to an existing heuristic. The idea is that this simplifies the task for RL (since it only needs to modify the original graph instead of solving the problem) while allowing us to improve the performance of the heuristic. Experiments are given on three example tasks, showing that the proposed method improves over the heuristics on their own in terms of solution quality, and also outperforms an attempt to solve the entire task with RL.