A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
Authors: Runzhong Wang
Zhigang Hua
Gan Liu
Jiayi Zhang
Junchi Yan
Feng Qi
Shuang Yang
JUN ZHOU
Xiaokang Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Combinatorial Optimization
Reinforcement Learning
Graph Neural Network
Bi-level Optimization

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.


A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
Runzhong Wang"* Feng Qi
Zhigang Hua?
Gan Liu
Jiayi Zhang!
Junchi Yan (X)
Shuang Yang² Jun Zhou?
Xiaokang Yang'
Department of CSE and MoE Key Lab of AI, Shanghai Jiao Tong University (runzhong.wer wang, zhangj layirr, yanjunchi, xkyang) &aj eut.ttu.dd... edu. cn {z. tua liugan. 1g, feng.egggg.. shuang. yang, jun. zhoujun) Santgroup.ccoo
2 *nt Group
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 single-level optimization by directly learning the end-to-end solutions, which are hard to scale up and mostly limited by the capacity of MI models given the high complexity of CO. In this paper, we propose hybrid approach combine the best of the two worlds, in which a bi-level framework developed with an upper-level learning method 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 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 https: / thub. cww hamm/Thinkaaab... Btt.a/abDDSTUUPP-BBBBA..
Introduction
Combinatorial Optimization (CO) is family of long-standing optimization problems. 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 acceptable time, and there is growing trend adopting modern data- driven 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
30
33
57 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 non-trivial, leading to the following two aspects of challenges. On the one hand, it is challenging design model with enough capacity with limited computational resources, and existing models are usually tailored for specific problems which require heavy trail- and-error [25] 55 [5]. On the other hand, training such heavy model requires either supervision from high-quality labels BT (7 600 which are infcasible to obtain for large-sized problems due to
the ha-hard nature, reinforcement learning (RL) 8 30 38 39 which might be unstable due
the challenges of large action space and sparse reward especially for large-sized problems [22
Part of the work done while the first author working intern at Ant Group.
Junchi Yan is the corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

An altermative approach resorts to hybrid machine learning and traditional optimization pipeline []]
18
26
31
5T
60 61 hoping to utilize the power of traditional optimization methods. However,
designing general hybrid MI.CO approach is still non-trivial, as existing methods [1 60] usually require domain-specifie knowledge for the model design.
again challenging to obtain high-
quality 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 [1]...
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 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
mitigated for the resulting RI. problem compared to previous RI.-based methods g 30 38 39
Specifically, our model is built with standard building blocks: the input graph is encoded by Graph
Convolutional Network (GCN) 22. 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 bi-level optimization formulation for learning to solve CO on graphs. The upper-level optimization adopts a reinforcement learning agent adaptively modify the graphs, while the lower- level optimization involves traditional learning- -areen 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.
2
Related Work
Here we discuss related works listed in recent surveys and compare with method.
4 62 63
We present their methodologies
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 55
The pioneering work [57] is designated for traveling salesman problem (TSP), whereby Pointer Network (PtrNet) model is learned with supervised learning. In 30
the soquencce-t-ssqueeee
a craph-to-scquence 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 [66, and job shop scheduling (64]. 33
extends 30) by problem reduction and supervised learningbbased tree search. The framework in 33
is treated as the RL baseline in this paper. Our approach differs from these single- end-to-end
RL methods 30 36 38 39), which lack the flexibility 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 strategics 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-base local search heuristics also fall within the lingle-level paradigm, while our method incorporates another optimization over the graph structure. The sparse reward issue also exists for 38), as a long episode is usually required for searching for satisfying result.
One-shot unsupervised end-to-ent 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
2

---

Upper level: actor net (ccmmed PPO)
acllio oóge)
NINZ
dell odge!
impuigragh ?
action probehiities
optiniznd grapd:
aclion probacilties
optiniced graph
?
?
heuristic
solution
hauristic
solution
hauristic
solation
Lower level: keeming heuristic
Figure I: An overview of our bi-level hybrid MLCO solver. The graph structure is optimized at the upper level by RI agent, and the optimized graphs are solved by heuristics the lower level. The actions can be any modifications of the edges (i.e. adding, deleting edges and modifying edge attributes), and edge deletion is presented in this example.
encoded in the network's prediction. Moreover, such 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 end-
to-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-ban -nd-buund with either supervised learning [8] 31 reinforcement learning [51]. [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 develop a more general framework, where the learning part and heuristic module are two peers alternatively performed.
Bi-level optimization. Our method is based bi-level optimization, which is family of optimiza- tion problems where a lower-level optimization nested inside an upper-level optimization. Bi-level optimization is in general NP-hard [27] (56], and the applications of bi-level optimization be found ranging from multi-player games 27 to vision tasks (37). and there is a loosely relevant attempt 2 adopting supervised learning solve a bi-level optimization for transportation.
3 Our Approach
In this paper, we propose Bi-level Hybrid (BiHyb) machine learning and traditional heuristic approach. Sec. [.1 shows both single-level and bi-level formulations of CO, and Sec. shows the RL approach to the bi-level CO.
3.1 Bi-level Reformulation of Combinatorial Optimization
Without loss of generality, we consider the classic single-level CO with single graph & as: h,,xx, 9) < for 1.../
min f((1g)
where x denotes the decision variable (i.e. solution), fx([g) denotes the objective function given represents the set of constraints. For example, in DAG scheduling.
input graph G and h2 g) < the constraints enforce that the solution 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 MI.O methods regards Eq. aa a straight-forward end-to-end learning task, and various training methods have been developed, including: 1) supervised learning [1] obtaining training labels by solving small-scaled Eq. with traditional solvers, however is nearly infeasible solve larger NP-hard problems; 2) unsupervised learning 22 59) adopting the continuous relaxation of
Eq. Tas as the learning objective, but existing methods face challenges when dealing with complicated constraints; and 3) reinforcement learning g 30 by predicting x sequentially, but the reward signal unavailable until reaches 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 capable of handling CO on graphs all constraints can be encoded by the graph structure, and 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.
go <g;
for k 0... (K -) do
Predict P(ai), P(a2 ai) on G and sample a ag; upper-level optimization for learning
gh+l add, delete modify the edge (a1, ag) in Gh; # state-transition
x t solve arg min f(**+1gght) by heuristic algorithm; # lower-level optimization
r + f(x1g)) f(x** [ # reward
Output: A list of rewards fro...TK11
The optimal solution x" to 9 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 as the set of all graphs that can be modified from G, and " as the set of all feasible solutions of G. If the heuristic algorithm is surjection from G to X. for G and its optimal solution x", there must exist G E G, such that x" is the output of the heuristic by solving G¹.
Proof. By the definition of surjection, since x* E X, there must exist at least one graph G" E 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 feasible solution. Then, we can modify the graph as follows: if the edge connecting i + does not exist, it is added. After adding all edges from to n. processing the nodes from 1 to 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. 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'9
1(x1g)
s.l. H2 for I...J
(2)
x x' arg min (S(''l'') h,, 0, 1.../
where (()'l9), (x'('') 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 the upper-level problem, whose objective [x'()) denotes the original CO objective computed by x'. The upper-level constraints (9', 9) < ensure that the feasible space g' a subset of G. and G has most K modification steps from G. The upper-level problem optimizes G' by an RL agent, by regarding Eq. 2 as the environment.
3.2 Reinforcement Learning Algorithm
We resort to reinforcement learning to optimize G' in Eq. which can be viewed as a data-driven embodiment of the classic bi-level optimization method by solving two levels of problems alterna- tively [53]. In Sec. 3.2. we present the Markov Decision Process (MDP) formulation of the bi-level optimization in Eq. Sec. 3.2.2 we describe the PPO learning algorithm our approach.
3.2.1 The MDP Formulation
Eq. 2 is treated as the learning objective and optimized by RL a data-driven manner. In this section, we discuss the Markov Decision Process (MDP) formulation for adopting RI. to this bi-level optimization problem. The policy roll-out steps are summarized in Alg. [ the following, G equals G meaning the original graph, and G (k * equals G' mcaning the modified graph after action k.

---

criginel graphh
aftoradtion (ookledgg))
odiginai graptes
aftoraatoo (did edgga
original grapks
adge)
Slate eiocode
KH Heuditic
LKH Heuatstic
Hausstcc
Haantii
Heuistic
Heuntalic
schechiing orders (5) (bel())
cdit pachss
baseling lours
(5) (6)
(a) DAG Scheduling
(b) Graph Edit Distance
(c) Hamiltonian Cycle Problem
Figure 2: Illustration of the state, action and reward for all problems discussed in this paper.
State. The current graph G treated as the state, whose nodes and edges encode both the problem input and the current constraints. The starting state g represents the original CO problem.
Action. The action is defined adding, removing or modifying an edge in gh. Since there are most m edges if G has m nodes, we shrink the action space to ((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, G* transforms to g with one edge modified. The new graph g is regarded as the new state and is adopted for reward computation. The episode ends max number of actions K. our implementation, we empirically set s 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).
when it reaches
Reward. The new graph g results in modified lower-level optimization problem whose objective becomes fx (x**+1 ((**+ ) and x is solved by an existing heuristic. The reward is computed as the decrease of upper-level objective function given x reward f(x* (xx++1(g).
3.2.2 Proximal Policy Optimization (PPO)
We resort to the popular Proximal Policy Optimization (PPO)
48 the RI. framework. PPO is the simplified version of Trust Region Policy Optimization (TRPO) 47 where the model update restricted within "trust region" to avoid model collapse. PPO is easier to implement than TRPO with comparative performance [48), maximizing the objective: (0) = min(re A,, clip(re, 1- 1-c, -))) where is the importance sampling ratio parameterized by model parameter 0, A is the advantage value computed by the discounted accumulative reward minus the critic network prediction, and e is hyperparameter controlling the boundary of trust region. Some common volicy-grading 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.
Experiments and Case Studies
We show the implementations and experiments three challenging CO problems: DAG scheduling in Scc. |.I 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-fres heuristics, and single-level RL peer method namely PPO-Single following the general framework (30], which also covers the majority of RL-based methods [15] 25
39 64). We also implement Random-BiHy which performs random graph modification under our bi-level optimization framework. The model capacity and training/inference time of PPO-Single kept in line with PPO-BiHyb for fair comparison.
33
36,
4.1 Case DAG Scheduling
The Directed Acyelic 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 computation job with running time and 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 general NP-hard [14], and the objective is to minimize the makespan of all jobs, i.c. finish all jobs soon possible.
5

---

4.1.1 Implementation Components
MDP Formulation. As shown in Fig. 2(a) state is the current DAG g², action is defined as adding an edge to G², resulting in a new DAG the decision space is cut down to elevate the heuristic's s performance. Here x represents the scheduled execution order, and the Critical Path heuristic is adopted on G to compute x The reward is computed by subtracting the previous makespan by the new makespan: [(x [G) ((x
The added edge enforces additional constraints such that
State Encoder. We adopt GCN [32] 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 graph-level embedding.
n = | ||
GCN2(reversel ) g = At((n)
where n (# of nodes x 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(ResNeels [n| g))), P(az|a1)= = softmax CaaimaxxxeeNeeee (ResNetz((1 || n[ai)] gl))
(4)
the subscript of n/ar] denotes the embedding for node a1. For training, we sample a1, ag according to their probabilities P(a1), P(ay/a1) respectively. For testing, beam search is performed with width 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.
(iCh) = ResNets ([maxpool (n)
(5)
Heuristic Methods. Solving DAG schedul- ing with hundreds of nodes is nearly infeasible for existing commercial solvers, and real-world scheduling problems are usually tackled by fast
2500
PRO-BiHyb (1PL-H-55 tmin)
Improvement wel Critical Palls
PPO Billyb (IPC-HL
PPO-BiHyb (TPC-H-1S0
2000
heuristics e.g. Shortest Job First which sched-
1500
ules the shortest job greedily and Critical Path algorithm which prioritizes jobs on the critical path. We also consider the novel Tetris schedul- ing (20 where jobs are arranged as a Tetris game on the two-dimension space of makespan and resource. Since Critical Path empirically ef- fective, we use it as the lower level optimization algorithm in our PPO-BiHyb learning method.
1000
500
50
100
200
250 300
TPC-H problem size
Figure 3: Generalization result TPC-H dataset.
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- immpleenn the single-level RL baseline
PPO-Single following [30] where the model details are in line with our PPO- IPO-BiHyb. To validate the
effectiveness of PPO, we also compare Random- Random-BiHHy which performs random search instead of PPO when modifying the graph, and its search steps are equal to PPO-BiHyb.
4.1.2 Experimental Results
Results are reported for scheduling jobs from TPC-H d which is composed of business- oriented queries and concurrent data modifications, represented by Directed Acyelic 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
http:://tpc.org/tpcc//eee

---

Table I: Experimental results on DAG scheduling problems from TPC-H dataset with the average number of nodes reported in brackets. The dataset name TPC-H-X means X jobs are jointly scheduled. The upper half is learning-free heuristics, and the lower half is RL-based methods where PPO-Single
can be viewed as our implementation of the peer single-level RL methods [39 c4. Note "objective"
means the objective score i.e. the total makespan time (in seconds, the smaller the better) to finish all
jobs, and "relative" is computed by the solved makespan time w.r.t. Critical Path heuristic.
datasct
TPC-H-50 (#nodcs=467.2) objective
IPC-H-100 (#nodes=929.8)
TPC-H-150 (#nodes=1384.5)
method
relative
objective 4
relative 4
objective
relative
Shortest Job First
12818++2214
30.5%
19503+33260
15.3%
27409+27748
12.2%
Tetris 20
12113:11398
23.3%
18291
8.1%
25325:+2822
3.7%
Critical Path
9821#1176
0.0%
1691442499
0.0%
24429:42484
0.0%
PPO-Single 3D] 39
10578:12092
7.7%
17282-13821
2.2%
24822:12707
1.6%
Random-Bithi BiHyb
9170:+1143
-5.6%
15580++2409
-7.9%
22930++2408
-6.1%
PPO-BiHyb (ours)
8906:1.922
-9.3%
15193::2275
-10.2%
22371::2538
-8.4%
125.8, and the minimum is I 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- real-world business scenarios. We build 50 training and 10 testing samples for all experiments, where each sample is composed of number of DAGs (e.g. 50, 100, 150) which are randomly sampled from the TPC-H dataset with fixed random seed.
Table reports the result on scheduling jobs from TPC-H dataset, where our PPO-BiHyb outperforms learning-free 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 10x longer than ours, but its performance is still inferior to the heuristic Critical Path method. Random-Biite 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- weal-world applications. As shown in Fig. [}] our models are learned with TPC-H-50/ 100-H-55011000 100/00/011111111111111000 00/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 casier compared to directly learning the solution, and the strength of heuristics is exploited with our approach.
can improve the lower-level heuristic
4.2 Case 2: Graph Edit Distance
The graph edit distance (GED) problem is NP-hard I 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 M. 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 mroblem-specifte 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).
4.2.1 Implementation Components
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 f(x1(9192))
(, < 0, for j 1...J s.t.
x x'.0
(6)
x E arg min (f(x'(( G2) 1x(x''9992 S for 1...
where fxx' (xx'),,. 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 H, (C 91) < 0 ensure that G/ has at most K modification steps from G1- The lower-level GED problem is defined between G2 and the modified G/. where [(''[] (9,92) G2) is the lower-level objjetttvv and (x,,,, Gi G2) < 0 are the constraints of the lower-level GED.
7

---

MDP Formulation. As shown in Fig. 2(b) since there are two graphs, we discriminate the graphs by subscripts G192, and the MDP formulation a generalized version of Sec. [.2.1 More specifically, the RI. agent is restricted to modifying 91 and keeping G2 fixed. The state is defined as the current version of first graph gf, and action is defined as adding or removing an edge from g The new graph - is designed to better align with G2 where the node-to-node alignment is encoded by the decision variable x which obtained by solving s' [(x 92) with IPFP heuristic. The upper-level objective f(x 1xx*"11,00 G2) is computed as the edit distance between the original graphs G1, G2 using x².
State Encoder. The state encoder is built with GCN [2] to aggregate graph features and Sinkhorn- Knopp (SK) network
[4] for propagation across two graphs. Following [58]. the SK module accepts a similarity matrix (by inner-product of nı and ny), and outputs a doubly-stochase can be utilized the cross posss-graph propagation weights. As the action is taken the first graph, compute the difference of the node features of graph I and the propagated features from graph 2 through SK net. Similar the DAG model, graph-level features obtained via attention pooling.
matrix which
GCF(
GCN(G2),
-SK(n)n)) n2; gi = Att(nn). g2 = Att( (7)
Actor Net. The action of selecting edge 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, added otherwise. The beam width is set as 3 during evaluation.
P(ai) = softmax (ResNet(n)), P(azlai) = softmax(n (n- tanh(Linear (n(ai))))
(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 fully-connected regression layers whose output is one-dimensional:
vight 92) fc (NTN (g))g)))
Heuristic Methods. Based on the comprehensive evaluation on different GED heuristics by [5]. we select best-performing heuristics: Hungarian (44) which simplifies the original problem to bipartite matching problem, RRWM [9] which solves GED via relaxed quadratic programming, Stungarian-Seare (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 -iHyb 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- 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 datase 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 also
20:30
29.1
63.2
78.6
training size
define an edit cost of 1 for different node types. Besides, 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
33.3
61.1
84.4
50+
32.0
61.6
77.0
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.
20/30
30/50
50+
testing size
Figure 4: Sensitivity by train- ing and testing sizes AIDS.
The evaluation for GED on AIDS is presented Tab. where our method surpasses all learning-free heuristics and also performs better than single-level RL baseline PPO-Single. We also conduct
htttp:://wik.. mci. nih. hwt.u//wwwwaaaaoa/aaaaaaaa//a/aa

---

The Hamiltonian cycle problem (HCP) arises from the notable problem of seven bridges of Königsberg proposed by Leonhard Eule [1]. Given a graph, the HCP arises as a decision problem on whether there exists 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 non-existing edges are with length then it is a Hamiltonian cycle. worth noting that HCP which focus on the special case of Table 2: Results on graph edit distance (GED) problems from AIDS dataset with the average number of nodes reported brackets. The naming convention here AIDS-X/Y means the number of nodes are within the range of X and Y. PPO-Single can be viewed as our implementation of the peer RL method [36.. Here "objective" means the objective score i.e. the solved edit distance between two graphs, and "relative" is computed by the solved edit distance w.r.t. the best heuristic IPFP.
dataset
AIDS-20/30 (fhodes==226)
AIDS-30/50 (#nodes=37799)
AIDS-500 50+ (fnoddes599.6 relative +
method
objective 4
relative +
objective 4 relative
objective 4
Hungarian
44
72.9+19.2
94.9%
153.4+28.00
117.9%
225.6-334
121,4%
RRWM 9
72.1+23.7
92.8%
139.84+3199
98.6%
214.6=41.3
110.6%
Hungarian-Searre Searrhh
45
44.6+8.5
19.3%
103.9::22.7
47.6%
143.8=31.5
41.1%
IPFP 66
37.4+8.5
0.0%
70.4+15.1
0.0%
101.9=13.1
0.0%
PPO-Single (36]
56,5+14.4
51.1%
110.0:19.2
56.3%
183.9=16,9
80.5%
Random-BiHyb
33.149.0
-11.5%
66.0=15.2
-6.3%
82.4+:00.3
-19.1%
PPO-BiHyb (ours)
29.1488.9
-22.2%
61.1=11.2
-13.2%
77.0=19.4
24.44
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.
4.3 Case Hamiltonian Cycle Problem
If tour found whose length has not been discussed by most ML-TSP works [15 28 33 57 Euclidean TSP with 2D coordinates.
4.3.1 Implementation Components
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 defined as the current graph G and action is defined as increasing an edge length in 9 resulting in new graph g++1, The increase of edge length softly prohibits the heuristic from traveling this edge and the LKH method (23] is adopted on graph g to obtain the new tour *+1 The reward is the decrease of the current tour length w.r.t.
the previous tour length: fxx [g] (xx++|g) (g).
State Encoder. We encode HCP graph with GCN (32]- The node embeddings from GCN modules then processed by attention pooling layer to extract graph-level embedding.
n = GCN((*)
Au(n)
(10)
Actor Net. After obtaining the tour solved by the hcuristic algorithm, we increase the length of any selected edge by 10 from the tour (10 is randomly set, and our approach seems sensitive 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(ar) softmax (Retsae(ReeNett( g)), P(az|an a1) = softmax (n tanh(Linner(((aaa))]
(11)
For training, we sample a1, a2 according to P(ar), P(az a1). For evaluation, we perform beam search with width of 12 and maintain the t2p-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- feature from the state encoder, which are finally processed by a 3-layer ResNet.
V(g*) ResNeta ([maxpool(n) ||
(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 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- iin-Kennghhan Heuristic (I.KH3) (33 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 LKI13-fast which is also adopted for lower-level optimization in our PPO-BiHyb for its time-efficiency, and we also compare with LKI13-accu with 100 random restarts.
Learning Methods. Most deep learning TSP mod- els are designated to handle fully connected 2D Eu- clidean TSP [1] 28, 33 571, which is 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 Handom-BiHyb baseline.
Table 3: Tests on FHCP with mean number of nodes in brackets. FHCP-X/Y means the number of nodes is in the range of and Y.
dataset
FHCP-500600 (#rodes= I)
method
TSP objective
found eycles
Nearest Neighbor
32
19.6+=13.4
0%
Farthest Insertion
46
133.0431.7
0%
LKH3-fast
23
13.842252
0%
LKH3-accu
6,3+13.0
20%
PPO-Single
9.5.1:5..6
0%
4.3.2 Experimental Results
Random BiHly
10.0+-21.9
0%
PPO-BiHlyb (ours) 6.7.114.0
25%
We use the FHCP henchmark (1 composed of 1001 hard HCP instances. All instances are known to have valid Hamiltonian cycles, however, finding them non-trivial for standard HCP/TSP heuristics. TableB]shows the result from a subset of FHCP benchmark. As mentioned in Sec. [43.1] we convert HCP instances binary TSP instances, whose tour lengths are denoted as "TSP objective". When the TSP objective is O, 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 10x longer than ours, but its performance is still inferior to our bi-level PPO- BiHyb. The Randon-BiHyb baseline also improves the performance of --3sffatt which adopted for solving the lower-level problem.
Discussions
Limitations model design. In this paper, we adopt the vanilla GCN implemented by TorchGeo- metric [13], and the detailed configuration 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 agree that there are room for further improvement. One possible direction may be adopting GNN-neural architecture search methods [16 655.
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 (2000AAA0107600), Shanghai Municipal Science and Technology Major Project (201SHHZDZX0102), NSFC (U19B2035, 61972250, 72061 127003), 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.
10

---

References
[1] Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, and P. Martineau. An exact graph edit distance algorithm for solving pattern recognition problems. Int. Conf. Pattern Recog, 2015.
S. A. Bagloee, M. Asadi, M. Sarvi, and M. Patriksson. A hybrid machine- and optimization method to solve bi-level problems. Expert Systems with Applications, 05:142-152, 2018.
33 Y. Bai, H. Ding. S. Bian, T. Chen, Y. Sun, and Wang. Simgnn: neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 384-392, 2019.
[4] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: a methodological tour d' l'horizon. European Journal of Operational Research, 2020.
[5] D. B. Blumenthal, N. Boria, J. Gamper, S. Bougleux, and L. Brun. Comparing heuristics for graph edit distance computation. The VLDB journal, 29(1):419-453)) 2020.
[6] S. Bougleux. B. Gaüzere, and L. Brun. Graph edit distance as quadratic program. In Int. Conf. Pattern Recog.. pages 1701-1706. IEEE, 2016.
[7] L. Chen, G. Lin. S. Wang, and Q. Wu. Graph edit distance reward: Learning to edit scene graph. Eur. Conf. Comput. Vis., 2020.
[8] X. Chen and Y. Tian. Learning to perform local rewriting for combinatorial optimization. Neural Info. Process. Systems, 32:6281-6292, 2019.
[9] M. Cho, J. Lee, and K. M. Lee. Reweighted random walks for graph matching. In Eur. Conf. Comput. Vis., pages 492-505. Springer, 2010.
[10] H. Dai, B. Dai, and L. Song. Diseriminative embeddings of latent variable models for structured data. In Ins. Conf. Mach. Learn., pages 2702-2711. PMLR, 2016.
[11] L. Duan, H. Hu, Qian, Y. Gong. X. Zhang, J. Wei, and Y. Xu. A multi-task selected learning approach for solving 3d flexible bin packing problem. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 3386-1394, 2019.
[12] L. Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanue, pages 128-140, 1741.
[13] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
[14] A. Forti DAG Scheduling for Grid Computing Systems. PhD thesis, University of Udine, Italy, 2006.
[15] Z.-H. Fu, K.-B. Qiu, and H. Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. AAAI Conf. Artificial Intell., 2021.
[16] Y. Gao, H. Yang, P. Zhang, C. Zhou, and Y. Hu. Graph neural architecture search. In C. Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 1403-1409, International Joint Conferences on Artificial Intelligence Organization, 2020. Main track.
[17] M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of XP-Completenesss 1990.
[18] Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convolutional neural networks. Neural Info. Process. Systems, 2019.
[19] R. Gomory, Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem. In 50 Years of Integer Programming 1958-2008, pages 77-103. Springer, 2010.
[20] R. Grandl, G. Ananthanarayanan. S. Kandula, S. Rao, and A. Akella. Multi-resource packing for cluster schedulers. SIGCOMM Comput. Commun. Rev., 44(4):455- 466.46555666,6 Aug. 2014.
[21] M. Haythorpe. Fhep challenge set: The first set of structurally difficult instances of the hamiltonian cycle problem. arXiv preprint urXiv: 10352,0352, 2019.
[22] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Comput. Vis. Puttern Recog., pages 770-778, 2016.

---

[23] K. Helsgaun. An effective implementation of the lin inn-eerighhn traveling salesman heuristic. European Journal of Operational Research, 126(1):106-130, 2000.
[24] K. Helsgaun. An extension of the lin-keriighan-helkaann tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
[25] R. Hu, J. Xu, B. Chen, M. Gong, H. Zhang, and H. Huang. Tap-net: transport-and- and-pack using reinforcement learning. ACM Transactions on Graphics (TOG), 39(6):1115, 2020.
[26] F. Hutter, H. H. Hoos, and K. Leyton-Brown. Automated configuration of mixed integer programming solvers. In Proceedings of the Conference Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming (CPAIOR), pages 186-202, 2010.
[27] R. G. Jeroslow. The polynomial hierarchy and simple model for competitive analysis. Mathematical programming, 32(2):146- (100):466-14444 164, 1985.
[28] C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint urXiv:1906.01227 2019.
[29] N. Karalias and A. Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Neural Info. Process. Systems, 2020.
[30] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In Neural Info. Process. Systems, pages 6351 6351-6361, 2017.
[31] F. Khalil, P. Le Bodic, I.. Song, G. Nemhauser, and B. Dilkina. Learning to branch in mixed integer programming. In AAAI Conf. Artificial Intell., volume 30, 2016.
[32] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. Int. Conf. Learn. Rep., 2017.
[33] W. Kool, H. van Hoof, and M. Welling. Attention, learn to solve routing problems! In Int. Conf. Learn. Rep.. pages 1-25, 2019.
[34] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. In International Conference on Machine Learning, pages 3835-3845, 2019.
[35] Z. Li, Q. Chen, and V. Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[36] C. Liu, R. Wang. 7. Jiang, and J. Yan. Deep reinforcement learning of graph matching, arXiv preprint arXiv:2012.08950, 2020.
[37] R. Liu, J. Gao, J. Zhang, D. Meng, and Z. Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. arXiv preprint arXiv:2101. 2021.
[38] H. Lu. X. Zhang, and S. Yang. A learning- based iterative method for solving vehicle routing problems. In Int. Conf. Learn Rep., 2019.
[39] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan. Z. Meng, and M. Alizadeh. Learning scheduling algorithms for data processing clusters. Proceedings of the ACM Special Interest Group on Data Commanication pages 270-288, 2019.
[40] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
[41] A. Nowak, S. Villar, A. Bandeira, and J. Bruna. Revised note on learning quadratic assignment with graph neural networks. In Data Science Workshop, 2018
[42] G. Reinelt. The traveling salesman: computational solutions for TSP applications, volume 840. Springer, 2003.
[43] K. Riesen and H. Bunke. lam graph database repository for graph based pattern recognition and machine lcarning. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 287-297. Springer, 2008
[44] K. Riesen and H. Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 27(7) 0000099922229 2009.
12

---

[45] K. Riesen. S. Fankhauser, and H. Bunke. Speeding up graph edit distance computation with a bipartite heuristic. In Mining and Learning with Graphs, pages 21-24, 2007.
[46] D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM journal on compuding. 6(3):563-581, 1977.
[47] Schulman, S. Levine, Abbeel, M. Jordan, and Moritz. Trust region policy optimization. In Int. Conf. Mach. Learn., pages 1899.1897. PMLR, 2015.
[48] J. Schulman, F. Wolski, Dhariwal, A. Radford, and O, Klimov. Proximal policy optimization algorithms. arXiv preprint arXi::100700634, 2017.
[49] R. Sinkhorn and A. Rangarajan. A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Statistics, 1964.
[50] R. Socher, D. Chen, C. D. Manning, and A. Y. Ng. Reasoning with neural tensor networks for knowledge base completion. In Neural Info. Process. Systems, page 926-934, Red Hook, NY, USA, 2013. Curran Associates Inc.
[51] H. Sun, W. Chen, H. Li, and Song. Improving learning to branch via reinforcement learning. NewrlPS Workshop, 2020.
[52] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[53] E.-G. Talbi. A Taxonomy of Metaheuristics for Bi-level Optimization, pages 1-39. Springer Berlin Heidelberg, Berlin, Heidelherg, 2013.
[54] Y. Tang, S. Agrawal, and Faenza. Reinforcement learning for integer programming: Learning to cut. In Int. Conf. Mach. Learn., pages 9367-9376. PMIR, 2020.
[55] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, I., Jones, A. N. Gomez, I., Kaiser, and I. Polosukhin. Attention all you need, arXiv preprint arXiv:1706.03762. 2017.
[56] L. Vicente. G. Savard, and J. Júdice. Descent approaches for quadratic bilevel programming. Journal of Optimization Theory and Applications, 81(2):379339, 1994.
[57] O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. In Neural Info. Process. Systems, pages 2692-2700, 2015.
[58] R. Wang. Yan, and X. Yang. Combinatorial learning robust deep graph matching: an embedding based approach. IEEE TPAMI, 2020.
[59] R. Wang. J. Yan, and X. Yang. Neural graph matching network: Learning lawler's quadratic assignment problem with extension hypergraph and multiple- gerpll matching. Trans. Pattern Anal. Mach. Intell., 2021.
[60] R. Wang, T. Zhang. T. Yu, J. Yan, and X. Yang. Combinatorial learning of graph edit distance via dynamic embedding. Comput. Vis. Pattern Recog., 2021.
[61] L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown Hydra-mip: Automated algorithm configuration and selection for mixed integer programming. In RCRA workshop Experimental Evaluation of Algorithmss for Solving Problems with Combinatorial Explosion the International Joint Conference on Artificial Intelligence (ICCAI). 2011.
[62] J. Yan, S. Yang, and E. R. Hancock. Learning for graph matching and related combinatorial optimization problems. In Int. Joint Conf. Artificial Intell., 2020.
[63] Y. Yang and A. B. Whinston. A survey on reinforcement learning for combinatorial optimization. CoRR, abs/2008. 12248, 2020.
[64] C. Zhang, W. Song, Cao, Zhang. P. S. Tan, and X. Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Neural Info. Process. Systems, 33, 2020.
[65] H. Zhao, Q. Yao, and W. Tu. Search aggregate neighborhood for graph neural network. In ICDE, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? (Yes] See discussions in Section 5 and
Appendix [A]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
discussions in Section5Jann Appendix G
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes] See Sec. 3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See the proposition and proof in Sec. 3.1
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? Yes] The code is publicly available at /ectps://gitann
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See experiment details Sec. and Appendix C
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix FF]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
We do not include any assets.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes] See Appendix H and all assets are publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Appendix H and all assets not contain human information offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We do not use crowdsoureing conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "eiAeU_RIq7M", "reviewer": "Reviewer_RkUB", "summary": "This paper proposes a hybrid bi-level method for combinational optimization problems on graphs, which combines traditional heuristics for combinational optimization and machine learning including reinforcement learning, graph neural networks, etc. ", "questions": "", "limitations": "", "rating": 4, "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": "Pro：\n1. The problem is important and meaningful. \n2. This paper proposes a bi-level hybrid solver for graphs, which can be used for several tasks on graphs. \n3. The authors conducted experiments on several different datasets for various tasks, which demonstrates that the model is general and effective. \n\nCons:\n1. The codes are not submitted, which raises concerns about reproducing the results. \n2. This paper overclaims on this point: “we take an initiative for developing a general hybrid approach that integrates traditional heuristic solvers with machine learning algorithm”\n3. It is not clear about the range of the problems that the framework is useful for. \n\nDetails:\n\nThe idea of combining heuristics for combinational optimization and machine learning for solving combinational optimization problems on graphs is interesting. I agree that although deep learning is powerful, it is usually unfeasible to use deep learning to directly solve some hard combinational optimization problems on graphs. The experimental results show that this model has the advantages of two parts: automated editing the graph with reinforcement learning and efficiently solving the remaining problem by heuristics for combinational optimization. \n\nHowever, I am confused about the following issues, and I hope the authors can answer these questions in the rebuttal stage,\n1. It would be better if the authors can provide several examples for the proposition (line 119) for understanding. What is the exact meaning of “If all constraints are encoded by the graph structure”? Can it be formally defined? What problems can be solved and what cannot? The related statements are vague. \n\n2. Furthermore, the proof states that given G and G’, we can find constraints that make x* is the output of a given heuristic algorithm. In my opinion, it’s different from given G and constraints, we can find G* that x* would be the solution (what the proposition proposes). \n\n3. It would be better if the authors can provide more details about the training process and plot the learning curves which can help us understand how the convergence process is. \n\n4. The authors should provide more examples in experiments as case studies.\n\n5. The following is overclaimed, “we take an initiative for developing a general hybrid approach that integrates traditional heuristic solvers with machine learning algorithm”. Actually, there are existing works that combine these two things. For example, meta-learning for heuristic algorithm search can combine them. This area starts in 1970 and has many papers. For recent ones, please check Frank Hutters' papers which are published around 2010.\n\n6. It seems RL is not the only method for searching for the graph, the authors should compare their RL-based method with evolutional search and stochastic search, etc., which can be used for the graph search/modification. \n\n7. The motivation of some designs is not clear, e.g., the design of the GCN module in Sec. 4.1.1 (maybe because of the page limit). Because the problem is defined based on graphs, how to use or design GCN would be key, but the description in this paper about GCN design is very short.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see \"Cons\" above.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dx6-UoiaQgy", "reviewer": "Reviewer_wSnT", "summary": "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 5, "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": "Originality\nCombinatorial optimization on graphs is very broad and authors focus on conventional problems -- DAG scheduling, graph edit distance, and HCP. And the proposed framework to combine MDP and heuristic algorithms is novel because of apply the RL to modify graphs in a certain direction. This direction is very different from a lot of work using RL that directly solves a given problem.\n\nQuality\nWhile the proposed idea is interesting, some technical aspects are unclear or unconvincing. Four main unclear points are following.\n\n1) Proposition in Page 3 does not seem proven. There is no guarantee that x* is the only feasible solution of G* when it is solved by a given heuristic algorithm. Without the proof of that unique solution guarantee, x* is not necessarily a solution of the heuristic solution. While it is not a trivial proof, authors skip this part and conclude.\n\n2) Intuitively, adding more constraints is likely to make the problem harder even for a given heuristic algorithm. Hence, we can imagine that the heuristic algorithm is likely to find a worse solution when more constraints are added. Given the counterintuitive situation (at least apparently), the explanation why the proposed framework will result in a better solution with a fair probability is missing. \n\n3) Experimental setting is not very convincing. Since heuristic algorithms result in local optimal solutions typically depending on initial settings, more trials with memorization of best results are likely to produce better performance. For a fair comparison, the proposed framework should be also compared with any heuristic MDP replacement such as identity (just more trials), random modifications (perturbations), and so on by equalizing the number of runs of heuristic algorithms.\n\n4) In the Graph Edit Distance (GED) problem, MDP is designed to modify \\mathcal{G}_{1} to be more aligned with \\mathcal{G}_{2}. This direction seems different from the other cases where the constraints become worse. How the GED problem fulfills Eq.(2) is not straightforward because constraints in matching two graphs are different from running algorithms on one graph.\n\n\nClarity\nThe manuscript is clearly written and easy to follow.\n\nSignificance\nIf all the technical issues described above are resolved, the proposed approach is worth considering, because the proposed framework can envision the direction that RL can boost the performance of many heuristic or state-of-art algorithms by exploiting such algorithms.\n\nOther weakness\nWhen the three problems are implemented, authors use all different neural network structures. While it is non-trivial to design neural network structure for MDP on graphs, authors do not suggest any guidance or ablation study when using different kinds of network structure.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors provide enough limitations societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aDf68hIYuLQ", "reviewer": "Reviewer_ovsi", "summary": "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. \n", "questions": "", "limitations": "", "rating": 7, "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": "To my knowledge, the idea of using RL to modify the input graph is novel. It represents a nice way to combine data-driven and algorithmic means of solving optimization problems. The experimental results show an improvement over the individual heuristics used, indicating that learning to modify the structure of the graph can actually improve the performance of the heuristic. Accordingly, I think that the paper does make a valuable contribution. \n\nA few comments/questions:\n\nFirst, test sets are often small (10-20 instances). Error bars should be reported to see if the improvements are significant (and/or more instances should be added to the test set). This is important to assess the validity of the results, aside from other comments about adding new content to the paper. \n\nSecond, it would be preferable to show results on at least one domain for which an existing RL method can be applied exactly. Developing and tuning a RL solver for an optimization problem can require a lot of effort, so to provide the most informative comparison between the single and bi-level frameworks, it would be good to see an example where another set of authors has produced a strong baseline. \n\nThird, how does the inference time compare to the runtime of the heuristics? I.e., does RL add significantly to the runtime cost?\n\nFourth, is it possible to develop an understanding of how RL tends to modify the input graph? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "5y_2On7BPV", "reviewer": "Reviewer_aSHH", "summary": "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.", "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": "I like the idea to mix RL with a heuristic algorithm but there are some points which need to be clarified:\n1- in each case, a GCN is used in Algorithm 1 to predict P(a_1) and P(a_2|a_1) for adding/removing//modifying edge (a_1,a_2) but I do not understand how the weights of this GCN can be learned? The reward is not a differentiable function?\n2- I do not understand how a ResNet block can be used on graphs? On page 5, the authors refer to [20] the Mask R-CNN paper. I do not see the connection, CNN are used on images not graphs?\n3- I had a look at the TPC-H dataset but it is not clear at all from the website how this is related to the task. Since the authors are using datasets which are not standard in the ML community, they should explain them and give at least basics statistics.\n4- on page 5, the authors say that they use GCN on the graph and on its complement. This is rather surprising as GCN are typically used on sparse graphs. Can they comment on this?\nIt would have been much better to provide the code associated with the experiments.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "OK", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This interesting paper explores a bilevel approach to solving combinatorial optimization
problems by using a learning algorithm to edit the graph until a 
(non-learning-based) heuristic can return the solution. 
The exposition should be improved, experiments should show ablation studies to understand 
the effect of network structure, and of course, it would be much better for code to be made available;
but the effort taken by the authors in the review period increases my confidence that 
the camera-ready version will address these issues.
Decision: Accept (Poster)