Unsupervised Learning for Combinatorial Optimization Needs Meta Learning
Authors: Haoyu Peter Wang
Pan Li
Venue: ICLR 2023 poster (2023)
Keywords: combinatorial optimization
unsupervised learning
meta learning
graph neural networks

Abstract: A general framework of unsupervised learning for combinatorial optimization (CO) is to train a neural network whose output gives a problem solution by directly optimizing the CO objective. Albeit with some advantages over traditional solvers, current frameworks optimize an averaged performance over the distribution of historical problem instances, which misaligns with the actual goal of CO that looks for a good solution to every future encountered instance. With this observation, we propose a new objective of unsupervised learning for CO where the goal of learning is to search for good initialization for future problem instances rather than give direct solutions. We propose a meta-learning-based training pipeline for this new objective. Our method achieves good performance. We observe that even the initial solution given by our model before fine-tuning can significantly outperform the baselines under various evaluation settings including evaluation across multiple datasets, and the case with big shifts in the problem scale. The reason we conjecture is that meta-learning-based training lets the model be loosely tied to each local optimum for a training instance while being more adaptive to the changes of optimization landscapes across instances.

Published as a conference paper at ICLR 2023
UNSUPERVISED LEARNING FOR COMBINATORIAL OP- TIMIZATION NEEDS META LEARNING
Haoyu Wang', Pan Li
1. Department of Electrical and Computer Engineering, Georgia Institute of Technology
2. Department of Computer Science, Purdue University hwang3028@ edu, panl malli@gatecc... edu, panli@purdue, edu
ABSTRACT
A general framework of unsupervised learning for combinatorial optimization (CO) is to train neural network whose output gives a problem solution by di- rectly optimizing the CO objective. Albeit with some advantages over traditional solvers, current frameworks optimize averaged performance over the distri- bution of historical problem instances, which misaligns with the actual goal of CO that looks for good solution to every future encountered instance. With this observation, we propose a new objective of unsupervised learning for CO where the goal of learning to search for good initialization for future problem instances rather than give direct solutions. We propose meta-learning based training pipeline for this new objective. Our method achieves good performance. We observe that even the initial solution given by our model before fine-tuning can significantly outperform the baselines under various evaluation scttings in- cluding evaluation across multiple datascts, and the case with big shifts in the problem scale. The reason we conjecture is that meta-learning-batt based training lets the model be loosely tied to each local optimum for training instance while being more adaptive to the changes of optimization landscapes across instances.
INTRODUCTION
Combinatorial optimization (CO), aiming to find out the optimal solution from discrete search space, has pivotal position in scientific and engineering fields (Papadimitriou & Steiglitz 1998 Crama
1997]. Most CO problems are NP-complete or NP-hard. Conventional heuristics or approximation requires insightful comprehension of the particular problem. Starting from the seminal work from Hopfield & Tank (1985), researchers apply neural networks (NNs) (Smith) 1999) Vinyals et al.] 2015) solve CO problems. The motivation is that NNs may learn heuristics through solving historical problems, which could be useful to solve similar problems in the future.
Many NN-based methods (Selsam et al. 2018 Joshi al. 2019 Hudson al. 202 Gasse al., Khalil et al., 2016) require optimal solutions to the CO problem as supervision in training. However, optimal solutions are hard to get in practice and the obtained model often does not gener-
2019
alize well (Ychuda et al. 2020). Methods based on reinforcement learning (RL) (Mazyavkina et al.)
2021 Bello al. 2016 Khalil et al. 2017: Yolcu Póczos 2019 Chen & Tian [2019] Yao al.
2019 K Kwon et al. 2020
2021 Delarue et al. 2020 Nandwani et al. 2021) do not need labels while they often suffer from notoriously unstable training. Recently, unsupervised learning methods have
attracted much attention (Toenshoff et al. 2021 Amizadeh et al., 2018 Yao et al. [019 Karalias &
Loukas 2020 Wang et al.] (002). A common strategy of these methods is to design an NN whose output gives solution the CO problem and then train the NN via gradient descent by directly optimizing the CO objectives over a set of training instances. This strategy is superior in its faster training, good generalization, and strong capability of dealing with large-scale problems.
Despite the prominent progress, current unsupervised learning methods always optimize NNs to- wards averaged good performance over training instances. This means if testing instance comes from the same distribution of the training instances, the solution to this single instance may have good quality, let alone the case when the testing instance is out-of-distiiiuttio (OOD). This
Our code is available at:

---

Published as a conference paper at ICLR 2023
Asprokination
9.08
2.72-
6.00
Jome Uieb
201
Mau PD2
ECM
1-15
Begrns the RiGG with 10n3 nodes
Degres the BUGG 10"4 nodee
Degree the RilG 10t5 nodes
Figure 1: Approximation Rates of different methods in the MIS problem. Meta-EGN and EGN (Karalias & Loukas 2020) are trained on RRGs with 1000 nodes and with node degree randomly sampled from 3, 10, 20. Meta-EGN and EGN are evaluated over larger RRGs with 10 ~v 10" nodes. More details about the setting are in Secs. 5. and 5.4 Meta-EGN outperforms DGA (Angelini & Ricei-Tersenghi 2019 by about 0.3% 0.5%
in approximation rates average.
induces a concern when we apply NNs in practice because practical problems often expect to have a good solution to every encountered instance. For example, allocating surveillance cameras is crucial for each-time exhibition in every art gallery. Solvers when applied to this problem (0 r'ouur 1987, Yabuta & Kitazawa 2008) should output good solution every time. Traditional CO solvers are designed toward this goal. However, it is tine-consuming and unable to learn heuristics from his- torical instances. So, can we leverage the benefit of learning from history with the goal of achieving an instance-wise good solution instead of an averaged good solution?
This motivates to study new formulation of unsupervised learning for CO. We regard the objec- tive of learning from history as to search for a good initialization for each future instance rather than give direct solution. Since practice, future instances are unavailable during the training stage, we propose to view each training instance as a pseudo-new instance for the rest training instances. Then, our learning objective is to learn good initialization of this model, such that further opti- mization of the initialization could achieve good solutions on each of these pseudo-new new instances. We observe meta learning is suitable to implement this idea and propose adopt MAML (Finn) et al. 2017) in our training pipeline as proof of concept. Note that the step of optimization on each pseudo-new instance shares similar spirit with fine-tuning a model over each down-streaming task as traditional meta learning does. However, each task in our case corresponds to optimization over each training instance.
We name our method Meta-EGN by extending the previous framework EGN (Karalias & Loukas 2020) via meta learning. Our key observation is that with this new objective, even the initial solution given by Meta-EGN (before fine-tuning on test instance) is substantially better than the solution given by EGN and other methods that optimize the averaged performance over training instances. Our conjectured reason is that the new objective, by taking into account fine-tuning the model over new instances, trains the model to avoid heing trapped into a local minimum induced by each training instance while being more adaptive to the changes of optimization landscapes across instances.
We demonstrate the benefits of Meta-EGN via experiments within three benchmark CO problems (max clique, vertex cover, and max independent set) on multiple synthetic graphs and three real- world graph datasets, with the number of nodes ranging from 100 to 5000. Meta-EGN significantly outperforms otate-of-the-art learning-basc based baselines (Karalias & Loukas 2020) Toenshoff et al.) 2021], greedy algorithms, and the commercial CO solver Gurobi9.5 (Gurobi Optimization] (2022) in most cases. Meta-EGN also shows super OOD generalization performance when the training and test datasets are different or have graphs of entirely different sizes.
Moreover, recently, Angelini & Ricei--Tesenngee (2022) have shown that the learning-based method in (Schuetz et al. (022) could not achieve comparable results with the degree-based greedy algo- rithm (DGA) (Angelini & Ricci- Tersengi) 2019) in the max independent set (MIS) problem on large-scaled random-regulat graphs (RRGs), which raises attentions from machine learning com- munity. We observe the issues come from two aspects: (I) graph neural networks (GNNs) used to encode the regular graph suffer from the node ambiguity issue due to their limited expressive power (Xu et al. 2019]; (2) the model in (Schuetz et al.) 2022) did not learn from history but was directly optimized over each testing case, which tends to be trapped into a local optimum. By ad- dressing these two issues, Meta-EGN can consistently outperform DGA while maintaining the same time complexity to generate solutions. Fig. T show the results.
2

---

Published as a conference paper at ICLR 2023
2 RELATED WORK
In the following, we review two groups of works: unsupervised learning for CO and meta learning.
2019) and TSP objectives. Some works have investigated satisfaction problems (Amizadeh et al.,
Previous works on unsupervised learning for CO have studied max-cut (Yao et al.
problems (Hudson et al. 202T), while these works depend on carefully selected
2018 Toenshoff
et al.] 2019). Applying these approaches to general CO problems requires problem reductions.
The works most relevant to us are (Karalias & Loukas 2020), (Wang et al.] 2022) and (Schuetz et al. 2022). Karalias & Loukas (2020) propose an unsupervised learning framework EGN for general CO problems based on the Erdós probabilistic method, which bonds the quality of the final solutions with probability. [Wang et al. (2022) generalize EGN and prove that if the CO objective can be relaxed into an entry-wise concave form, a solution of good quality can be deterministically achieved. This further inspires the design of proxy objectives for CO problems that may not have closed-form objectives, such as those in circuit design. [Schuetz et al. (2022) have recently extended EGN to large-scale max independent set problems on random-regular graphs.
Meta learning is proposed to learn hyper-parametert or initialization from historical tasks and achieve fast adaption to new tasks. [Finn al. (2177) propose model-agnostic meta learning (MAML), which aims to obtain good parameter initialization and be accommodated to few-shot learning with limited steps of fine-tuning, Nichol al. (2018) accelerate MAML by adopting first- order approximation on the gradient estimation. Rajeswaran et al. (2019) introduce implicit-MAMI that adopts an objective with fine-tuning till the stationary points on new tasks. Implicit-MAMI does not fit our case because we try to avoid long-time fine-tuning, [Hsu et al. (2018) study unsupervised learning under the meta learning framework and focus exclusively on vision tasks. To the best of our knowledge, our work is the first to apply meta learning to unsupervised learning for CO.
PRELIMINARIES, NOTATIONS AND PROBLEM FORMULATION
Combinatorial Optimization on Graphs. We follow the settings considered in (Karalias & Loukas 2020 Wang et al.) 2022; Schuetz et al.] 2022) and study CO problems on graphs whose subset of nodes of the input graph instance, although our method could be applied to a broader range of problems. Suppose G is the universe of graph instances. Let G(V, E) E denote a graph instance where V == [1, ...: n is the node set and E is the edge set. Let X = (X,)ssinn E {0, 133h denote the discrete optimization variables defined on V, where X; denotes that node i selected in the output node subset. A CO problem on G consists of a cost function f(:; : {0, 1)" + R>0 and feasible set Q S {0, 13" that stands for the finite set of all feasible X's, and asks to solve
solutions can be represented
min XEf0,11
G(X;G) s.t. X
(1)
Unsupervised Learning for CO. The Erdös-Goes- Goce--oeseaaa (EGN) framework of unsupervised learn- ing for CO proposed in (Karalias & Loukas 2020) is reviewed as follows. Here, we use the notation system in a follow-up work (Wang et al. 2022) as it is more clear. Learning for CO problem is to
learn algorithm Ao(-) g + {0, 11ah typically parameterized by NN where A denotes the parameters of the NN such that given a graph instance G, X = Ao gives a solution of Eq. [ In practice, directly optimizing the parameters 0 is hard in general.
Therefore, we may consider a relaxed cost function f+(:;)) : [o, 1]m - Rzo where fx(X;G) = f(X; G) on any discrete points X 10, and a relaxed constraint gr
[0, 1j" + R>0 where {X E {0, (x; G) = 0} and {X E [0, gx; G) 2 1} defines the feasible set Z and the infeasible set Ω respectively. Also, suppose the NN in Ao can give soft solutions X E [0, 1lm.. Then, we may train 0 by minimizing a label- label-independen loss function:
min ((:G)) & G)(;;)) + (g; X == Ag(),, for some 3 >>0 0.
The significant observation made by (Wang et. 2022), which generalizes the argument in (Karalias) & Loukas| 2020), is type of performance guarantee on the condition that fr and gr are entry-wise concave, which is satisfied in all the cases studied in this work: If the loss that achieves I(0; G) < B for some 3 m f(X; G), then the discrete solution X obtained by rounding the soft solution X (G) according to Def. iis feasible X Ω and of good quality f(X; G) & ((0:G).
3

---

Published as a conference paper at ICLR 2023
Algorithm Train Meta-EGN and Test Meta-EGN with/without Fine-tuning
Require:
Training instances =\ {G1, G2, Gm Hyperparameters: a, 7
1: Randomly initialize ((0)
2: for each randomly sampled mini-batch B, C. = 0, 1, 1,.,, K do
> Training starts
3: For each G₃ By, compute the adapted parameter: 0,5) 003) aV ginl 100))
4: Update: g(++1) + g(3) Vov EG.B, (0,))
5: end for
6: return ((K)
P Training ends Testing starts
7: For given testing instance G²:
8: if fine-tuning is allowed then
9: Fine-tune the parameters: B.y 0 VVl(0f G')
10: Use Def. to round the relaxed solution given by Ar (G')
With fine-tuning
11: else
12: Use Def. D to round the relaxed solution given by (G')
Without fine-tuning
end if
Testing ends
Definition 1 (Rounding). For soft solution X 10, and arbitrary order of the tries (w.llo.g II),...,I,, fix all the other entries unchanged and round X, into O or 1 as X; = arg min i. fr (X,,,. Xi-1,3, Xi+1y Xn) + Bgg (X,, X1,,,, Xi-1,3 Xi41s (n))) Xn), replace X; with X; and repeat this operation until all the entries are discrete.
META LEARNING FOR ERDÖS GOES NEURAL (META-EGN)
The above performance guarantee lays the theoretical foundation for EGN. However, the following practical issue motivates us to incorporate meta learning into EGN.
4.1 MOTIVATION: WHAT NEEDED IS LEARNING FOR INSTANCE- WISE GOOD SOLUTIONS
It is often time-consuming to perform online optimization of I(0: G) for each encountered instance G. This also mismatches the goal of learning, i.e., learning heuristics from history/data. Therefore, pipeline commonly adopted is as follows. Suppose there is set of training instances G,, 1 S m, IID sampled from a distribution Pg. We optimize by following
min Σ ((B:G.),
which is similar to empirical risk minimization (ERM) in standard supervised learning. When test instance G' appears, we apply the learned As to get soft solution and round it to the final solution.
This pipeline cannot guarantee the quality for this instance G. Even if the training instances Gü, 1 isis S.nm m are in a large quantity (so in-distribution generalization is not a problem), and even if the test instance G also follows Pg. we may not guarantee low 1(0: G) for one particular G because ERM only guarantees a low averaged performance EG-Pg [1( G)]. This issue may also violate the condition to have a performance guarantee as reviewed in Sec. 3 as instance-wist Here, we highlight that in practice even the minimal averaged loss ming EG [1(0; G)] is often strictly greater than averaged instance-wise minimal loss EG-P, [ming I(0; G)), because practical NNs are not expressive enough to remember the optimal solution to every instance.
Unfortunately, many practical CO problems actually expect instance-wise good solutions. This because every instance in practice is crucial. A terrible solution for one instance may raise security issue (c.g., the surveillance-camera allocation problem) or cause huge economic losses (e.g., the routing problem in transportation system). With this observation, our work is to address the problem by studying unsupervised learning for instance-wise good solutions to CO problems.
4.2 TRAINING TOWARDS INSTANCE- WISE OPTIMALITY VIA META LEARNING
Our idea to address the problem is to regard the goal of learning from history as to search for good initialization for future instances rather than give direct solutions. Such good initialization
4

---

Published as a conference paper at ICLR 2023
HeraCok-iree Hira
Sea dis
3324
-190
30r
-124
.20
8823
-21-
DOX Tracte
-20
MILUION Parraao
1000
300g
Spochs
Spocka
Epecia
(a) Training Loss
(b) Validation Loss
(c) Validation Approximation Rate
Figure 2: Training/validaatnn dynamics Meta-EGN and EGN Karalias & Loukas 2020) for the MIS prob-
lem. Detailed experiment settings follow Sec. 5.1
can be quickly fine-tuned by further optimizing the model for each instance, which ultimately gives instance-wise good solutions. However, in practice, we do not have access to any future/test in- stances. So, can we just use historical/training instances implement the above idea? Our strategy is to view each training instance G; as a pseudo-test instance to test and optimize the quality of initialization given by the model. Specifically, this strategy gives us an objective
min Σ 4(0), where (40)) = min I(0gs G2) with 0, = as initialization.
(4)
Eq. has some abuse of notations. The minimum (0) depending on the initialization 0 is because of the non-convex nature of mine, [(0;; Gi), where the initialization 0; = 0 matters significantly.
We further simplify Eq. 4 with some practical consideration. In fact, may not allow further optimizing 9 with so many gradient-descent steps for each instance, especially during the online test stage. As a proof of concept, we consider the case with only one-step gradient descent, which already gives good empirical results. Specifically, our training objective follows
Our Objective: min Σ 4()), where (()) I(0,; G.) with 0, = -0 aVV(o).( (5)
Here, O is to give good initialization Ao(G,) over each instance G, while 6, is with one-step fine-tune to achieve a G,-specified good solution Ag, (G,).
Optimization in Eq. can be implemented via the meta learning pipeline MAMI (Finn al. 2017
We name the obtained model Meta-EGN and summarize its training and testing in Alg. | In step 3, Meta-EGN performs the one-step gradient descent on each training instance. Note that consider two testing cases with or without fine-tuning because the latter saves much inference time. A simple extension of Theorem in (Wang et al. 2022) gives performance guarantee for Meta-EGN in Theorem I as follows. Here, for a test instance G, we even allow [(6: G) to violate the original condition (0:G) < in (Wang al. 2022) some extent. After one-step fine-tuning step 9, the performance guarantee still achievable. The detailed proof is in Appendix. A
Theorem (Performance Guarantee). Suppose the relaxations fo and are entry-wise concave as required in (Wang al. (2022) Let 0 denote the learned parameter after training. Given a fest instance G, suppose locally 1:; G) is L-smooth at 0, i.e. V G) VoI(0; G) S L 0|) for all 0' that satisfies ||0' Ø11 I e. Then, if L(0:G) < B + A (even if [00 G) 2 3), for any a (0, ()) Meta-GNN with one-step finetuning outputs a feasible solution of good quality G(XG)) < ((0:G) - A. Here, A = [Vel((O G)lle+ + 2o if al/Vol(0; G) or 4 = (a VV o.w.
To better understand Meta-EGN, we show its training/testing dynamics in Fig. As we expected, the training loss of EGN is somewhere in-between the losses of Meta-EGN before and after the fine-tuning step. Training EGN stabler and converges faster than training Meta-EGi, EGN. However, what is unexpected is that in validation, Meta-EGN has much lower loss and achieves much better performance than EGN even before fine-tuning.
This implies that Meta-EGN holds better generalization than EGN. We conjecture the reasons as follows. First, the optimization landscape for CO problems is extremely non-convex (Mezard & Montanari 2009) due to the intersected feasible-iffeasible regions and the high penalty coefficient
5

---

Published as a conference paper at ICLR 2023
Table 1: Comparison between different unsupervised frameworks. G denotes test instance and G., i m are training instances. The standard EGN pipeline does not adopt any fine-tuning.
EGN
P- GNN
Meta-EGN
Classical Solver
Karalias & Loukus 2020
Schuetz et al.
2022
(Ours)
Gurobi Optimization 2022
Obj. to optimize the NN Training or not
>x [0; Gt)
[(0 G)
Ee 110 V.l(8;G)):
((X;G) X ?
Yes
No
Yes
Fine-tune timing
No Good
1 Long
Short/No
Long
Generalization
Better
Table 2: The discrete objectives (Eq. I and their relaxations (Eq. for the three problems to be studied.
Figure 3: Performance v.s. hyper-
parameter p of the RB model
Discrete Ohj.
= (0: C) (34 1) EmIIE XxX; + + X.X; minx Eisien X; 8.t. X,+ X2 2 (
maxx Eisisn X, S.L.
MC
Relaxation
Discrete Obj.
MVC
Relaxation
lvvel; A Eisisn X. 1. Eusnn X.)(1 X,) X,X;- = (L.))E
Discrete Obj.
maxx Eisten X;
BRN RB500
MIS
Meta ECN on RB300
Relaxation
(an((; -Eisis X. ++ x Duiice X.X,
Gurebl9.3 or RB500
2.5 sin eán cb: 6n elo The
p RB model
3. EGN that has low losses for training instances may give high loss even when the optimization landscape is just slightly shifted (from training to a test instance). However, the parameters of Meta- EGN are loosely tied to local minimum for each training instance. Instead, those parameters, being aware of follow-up instance-wise fine-tuning steps, are likely to fall into some location close to a local minimum for each instance while being not trapped in any one them, which makes the model robust to landscape shifts across instances. Second, CO problem could vary a lot across graph instances even for those generated from the same distribution, especially when the instances large. So, it is reasonable to view the problem over each instance separate but relevant task. Meta learning has shown good generalization when data distributions shift across tasks, which has empirical evidence in CV and NI.P applications (Jeong & Kim 2020 Conklin al. 2021
As a summary, we provide a comparison between different unsupervised frameworks to solve CO problems in Table [ Note that PI-GNN (Schuetz al.) (022) is directly fine-tuned on each test instance without training so the fine-tuning time is long. Also, although PI-GNN also pursues instance-wise good solutions, its performance could be bad because it does not learn from train- ing instances. The mnstancewwise solutions could be just bad local minima.
EXPERIMENTS
We study three CO problems, namely max clique (MC) to find the largest set of nodes where each pair of nodes connected, minimum vertex covering (MVC) to find the smallest set of nodes that every edge is connected to at least one nodes in the set, and max independent set (MIS) to find the largest where any two vertices in the set are not adjacent. Their objectives (Eq. TT and relaxations (Eq. ( are listed in Table For the detailed derivation, see Appendix
5.1 SETTINGS
Datasets: We conduct experiments on the MC and MVC problems over three real datasets Twit- ter (Leskovec & Krevl 2014), COLLAB and IMDB (Yanardag & Vishwanathan 2015) and two synthetic datasets with 200 and 500 nodes generated by the RB model (Xu) 2007). We name them RB200 and RB500, respectively. We make RB200 and RB500 extremely hard by setting small hyper-parameter م = 0.25 of the RB model (x 2007). The difficulty-p relationship on the MVC problem with 500 vertices is shown in Fig. where the models are pre-trained on the RB graphs with uniformly sampled y E [0.3, 1.0] and tested on different RB graphs generated with single p's. We keep all the other hyper-parameters the same. As p increases, Meta-EGN and Gurobi9.5 .5 all tend to achieve better performance. Meta-EGN could outperform Gurobi9.5 in hard instances p E (0, 0.55] while remaining gap the easy ones. To verify performances for data-scale generalization, also generate large-gran datasets RB1000, RB2000, and RB5000 with p = 0.25. As for the MIS problem, random-regular graphs (RRGs) are often used as benchmarks because they are challenging.

---

Published as a conference paper at ICLR 2023
Table 3: ApR (time: second/graph) on the MC problem. ApR is the larger the better. 'report' denotes the
reported performance in Karalias & Loukas (2020). 're-impl' denotes re re-inplementation. 'f-t' stands for fine- tune. Pareto- results are in bold.
Twitter
COLLAB
IMDR
RB 200
RB 500
EGN (report)
0.924 1: 0.133 (0.17) 0,982 1: 0.066 (0.10)
1,000 (0.08)
EGN (re-impl)
0.92-+0.113000
0.962 (0. 10)
1,000 (0.08)
0.882 (0.13)
0.852 (0.33)
EGN (re-impl) f-t
0.949 0.102(0.99)
1.000 (0.20)
0.926=001158 (0.49)
0.899 (0.91)
RUN-CSP
0.909 0.145 (0.21)
0.912 (0.14)
0.823
(0.11)
0.926 (0:47)
0.854 (2.09)
Mela-EGN
0.976 11 0.044800.1))
0,988 1 0.059 (0.10)
1.000 (0.08)
0.930
0.143 (0.13)
0.875 L 0.213 (0.33)
Meta-BGNN Fit
0.990 0.028(0:49)
0.993 0.038 (0.27)
1,000 (0.20)
0.976
0.139 (0.49)
0.917 0.208 (0.91)
Toenshoff-Greddy
0.917 = 0.126 (0.08)
0.969 = 0,087 (0.06)
0.987 = 0.050 (Ie-3)
0.841 = 0.139 (0.23)
0.846 0.19 (3.83)
Gurobi9.5 (55.
0.737 = 0.267 (0.17)
0.871 + 0.242 (0.04)
1.000 (1e-3)
Gurobi9.5 ($1.00s)
1.000 (0.37)
0.979 + 0.117 (0.06)
1.000 (1e-3)
0.898 0.092 (0.36)
Gurohi9.5 5 (x2.50<)
1,000 (0.37)
0.997 1 0,036 (0.06)
1.000 (le 3)
0.987 0.039 (1.65)
0,778 1 0.209 (1.68)
Gurohi9.5 (g4.00s)
1.000 (0.37)
L,000 (0.06)
1.000 (le-3)
1.000 (2.61)
0.820 0.211 (2.86)
Table 4: ApR (time: second/graph) the MVC problem. one-step fine-tune. Pareto-optimal results are bold.
ApR is the smaller the better.. 'f-t' stands for
Twitter
COLLAB
IMDB
RB 200
RB 500
EGN
1003 1.551000000 0.023(0.29
1013 0.022 (0.15)
1,000 (0.08)
1.031 0.0004 (0.26)
1.021 1.0002 (0.48)
EGN F4t
1.028 0.022 80)
1.008 + 1.015 (0.38)
1,000 (0.32)
1.030 4.0005 (0.80)
1.021 4-0002 (1.59)
RUN CSP
1,180 0.435 (0.16)
1,208 0.119 (0.19)
1.188 0.178 (0.08)
1.124 1 0.001 (0.28)
1.062 1.000 (1.65)
Meta-RGN
1.019 +.019+..1770.99
1.003+0.000 (0.
1,000 (0.08)
1.028 + 0.005 (0.26)
1.016 + 0.002 (0.48)
Meta EGN Ft
L..710.01700.80
1.002 1 0.010 (0.38)
1,000 (0.32)
1.027 1 0.005 (0.80)
1.016 0.0002 (1.59)
Greedy
1.014 0.014 (1.95)
1,209 1: 0.198 (1.79)
1.180 1: 0.077 (0.02)
1.124 1 0.002 (5.02)
1.062 1 0.005 (15.59)
Gurob99.5 (g0.254)
1.028 + 0.054 (0.09)
1.002 (0. 10)
1,000 (0.01)
Gurob99.5 (50)50s)
I+le.3 1 0.001 (3.1
1.000 (0.10)
1.000 (0.01)
Gurob99.5 (g 000e)
1.000 (0.13)
(0.10)
1,000 (0.01)
1011+ 0.003 (0.63)
1.019 + 0.003 (0.69) 1.019 0.003 (1.68)
Gurobi9.5 (22.00)
1.000 (0.13)
1.000 (0.10)
1.000 (0.01)
1.088 1 0.002 (1.16)
Our experiments also use RRGs by following the settings of (Schuetz et al.
2022)
with the node 10, 10,20). Here,
number ranging from 102 to 10 and the node degree selected from the set D node degree equaling 20 is the hardest setting (Angelini & Ricci-Tersengle 2022). A summary of
[3.
7,
these datasets is in Table, in Appendix.
Data Splitting& & The Evaluation Metric: For the real datasets, training/validationneest instances are randomly divided with the ratio of 7:1:2; For RB200 and RB500, 2000/100/100 graphs are generated for training/validationnnes instances; For RB 10000 RB2000. RB5000, we generate 100 test instances. As to RRG datasets. the training set contains 3000 RRGs, of which each has 1000 nodes and the node degree is uniformly sampled from D. We generate 15 graphs for validation and 20 graphs for each node degree configuration in D for test. Our evaluation metric uses the approximation rate (ApR). All results are summarized based on 5 times independent experiments with different random seeds.
Baselines: Our baselines include unsupervised learning methods, heuristics, and traditional CO solvers. For the MC and MVC problems, we take our direct baseline EGN (Karalias & Loukas) 2020), and also take RUN-CSP (Toenshoff et al.) [022]) as another baseline. We do not consider other learning-bast baasedg-basedii methods because they generally perform worse than EGN (Karalias & Loukas] (2020). As to the heuristics, we greedy algorithms as heuristic baselines. For traditional CO solvers, compare against the best commercial CO problem solver Gurobi9.5 (Gurobi Optimization] (022) via converting the problems into integer programming form. We track the time that the models use from the start of inferring to the end of rounding to output feasible solutions. We set this time t as the time budget of Gurobi9.5 55 for purely solving the integer programming, and list the actual time usage of Gurobi9.5 which includes pre-processing plus t. As to the MIS problem, we take PI- GNN (Schuetz et al. 2022) and EGN Karalias & Loukas (2020) as the learning- based baselines. We take the random greedy algorithm (RGA) and reggre-bbaed, greedy algorithm (DGA) as introduced in Angelini & Ricei- Tersengie (2019) as the heuristic baselines. When we consider fine-tuning
based
EGN and Meta-EGN over test instance, use 1-step gradient descent as fine-tuning.
For the MC and MVC problems, we use 4-layer GIN (Xu et al., 2019 as the backbone network for both meta-EGN and EGN. We use le-3 as both the outer learning rate (7) of Meta-EGN and the learning rate of EGN. Here, the backbone and the learning rate are the same as those in (Karalias & Loukas 2020). For the MIS problem, we use 6-layer GIN. The outer learning rate (7) of Meta-EGN and the learning rate of EGN are set as lc-4. The inner learning rate (a) of Meta-EGN is always set as 5e-5. We run all experiments by using Xeon(R) Gold 6248 CPU with
Implementation:
7

---

Published as a conference paper at ICLR 2023
Table 5: Scale generalization on the MC and MVC. ApR the larger the better for MC while the smaller the better for MVC. All the models are trained on RB500 training data. "aas/Meediu//Accuratte denotes GNNs (without fine-tuning) using 1/4/8 random single node seed(s) per testing instance. FFne-tuningg use 1-step Fine-tuning the best trial among the 8 node sced(s). 'Gap' represents the averaged gap defined as (# of nodes in the optimal solution # of nodes by the given method) where c for MC and = -1 for MVC. 'Rank" is the average rank of solutions among the three methods. Optimal solutions are generated via Gurobi9.5 with a time limit 3000 seconds. Approximation rate for MC larger than 1, highlighted by *, indicates the model outperforms Gurobi9.5 solver with 3000s time budget. Pareto-optimal results are in bold.
(i)(O)
Accarae (8)
Fice-lasc
Apllogg
cop
Apllowg)
Gap
Rynt
ApRicgg
Rank
AgRinggi
Bank
BGN
Foltinn 26200 n5)
0.84300 22400117)
5.47
D.509eG 315
4.86
2.005
D. 1.5Gee Roon 963
GroN6955
0 8885-n 19716-111
5.85
0,88550
19716.18)
5.05
0.88546 19776
5.06
015856n 1977
BGN
0.77 20000 (0)
12.58
2,426
0.89600 (54/0.25)
5:23
2.156
D154e0. 16010.55
5.81
2.208
0.577 1542 083
3.61
1,583
Veta
1007551111 100
3.45
3
0.951 (5512 56)
0551 1451250013
3.01
1-5: 25.66)
3.01
RXN
1o-0- M9N0 53)
2.130
100HA 15N1 I2y"
-1.26
2.000
107-0 1401 10y
-1.68
1.500
(307 189/9
2.86
1.920
RB5000
1.0000511.00 51)
00000
7,050
1000 160
0/50
2.170
100007705 64
0.00
0.250
10000214 05)
01.00
2.500
1000010000
0.00
103001900)
2453
1.000 V0570
8.00
1 3000
01000
10035a0
10135=60000311
R31000
Mota
L0le5-n 10166 200
14.51
13:40
1,700
TA135e8 0012/1337 37)
12.75
1412449-8013:1065
12:69
1 0042000001110000 M2)
14.59
1,835
1 0143500 001 8/2.58)
14.56
2.350
10014700 000000001330000 (6)
14.58
2.505
1.14260000186 (6)
14.55
2.585
MVC
R0000
Mer BCN
19.94
1,340
18.41
17.82
1,500
1,800 0.000-000000.2207
17.38
1.360
1 10005-4 2005--220002477 67)
30 15
2,410
701 15
2,400
10000460 100.000000000000000 D4)
50.15
2.725
1100 (0110) 1534
20.18
3.790
155000
Mato BUN Opob48.3
1806730000050000 1013)
32.51
1.845
LIM6220 13.99
29.66
1.400
29.44
1.585
LIMORR (04211444)
19.15
1,470
100850) 200866000000240000 60)
31.58
1.755
$1.38
2415
1.00M0LL 32.101
31.85
2.500
1 1005 (00614222)
31.85
2.500
Table 6: Generalization from Twitter RB2000 on the MC and MVC. Pareto-optimal results are in bold.
Method
Fost (I)
MC [Apressimniion Raiz " (fmee))
Mediumi (4)
Accurate (8)
Fire tane
(3)
MWg.eooooinnnii Rai: - (fime))
Medium (4)
Accurzz (8)
Pinc auze
1100000
0,768.0 20169.16
0:1199 195:0.29)
0.33 192/0.89)
L005en.00000011 11)
105350000440021 .7)
L050300040.500
Cumi69.5
0.66800
0.66200
0.660 19103.00
0,742:022133
L019:0.0001113
L019:0.0011.00
1019:8.8001133
2017:0.000/2.440
26 threads and Quadro RTX 6000 GPU, All codes run on the PyTorch platform (Paszke et al., 2019). For more details, see Appendix. C
Overcoming the limited expressive power of GNNs: GNNs are known with limited expressive power (Xu et al.] 2019 Morris et al., 2019). Specifically, over RRGs, the GIN backbone will asso- ciate each node with the same representation, unless node representations are initialized not equally. To keep a fair comparison, for the MC and MVC problem, we follow Karalias & Loukas (2020) and adopt the initialization based on a single random node seed (one selected node is initialized as
1. others as 0). We use 8 single random node seeds for EGN and Meta-EGN in the experiments of
Sec. 5.2 and report the best among the 8 trials. We try different numbers of random node seeds in the experiments of Sec. [.3 For the large-scale MIS problem studied in Sec. Sec.55.4 we find such single node initialization is too local to generate valid global solutions. So, we adopt initialization based on the solutions of greedy algorithms DGA (for Figs. 4 and RGA (for Fig. 4. Then, EGN and Meta-EGN can be viewed as learning heuristics to improve the greedy solutions. Note that learning heuristics to tune these solutions is non-trivial (Andrade et al., 2012 Rahman & Virag. 2017).
5.2 META-EGN BOOSTS THE PERFORMANCE WITHOUT DISTRIBUTION SHIFTS
We first compare the performances of different methods when the datasets used for training and test- ing are from the same distribution. Table and Table show the results for the MC problem and the MVC problem respectively. In both problems and across the five datasets, Meta-EGN significantly outperforms EGN and RUN-CSP, both before and after the fine-tuning step. In comparison with the traditional CO solvers, Meta-EGN narrows the gap from Gurobi9.5 on those real small graphs. For RB graphs, Meta-EGN outperforms Gurobi9.5 55 on RB500 for both the MC and MVC problems.
We notice that both EGN and Meta-EGN perform generally well the MC problem while not as competitive on the MVC problem. This results from the initialization of GNN inputs. The MC problem outputs clusters that are more local while MVC asks for global assignments, which makes such single-seed based initialization less fit for the MVC problem.
5.3 META-EGN BOOSTS THE PERFORMANCE WITH DISTRIBUTION SHIFTS
Problem Scale Shift: Here, we use large-scale RB graphs of 1000-5000 nodes to test EGN and Meta-EGN that is trained based on RB500. Table 5 shows the results. Both methods show good generalization while Meta-EGN is always better. As the scale increases, Meta-EGN outperforms Gurobi9.5. For example, it takes Meta-EGN with 4 random initializations only 1.02s to beat
8

---

Published as a conference paper at ICLR 2023
1-6
090
Appronttoonn www.oootttttooooooooooooooooo rade
Agg sugrootteaatiium 1230
Appo wyg.owimaccooo
3.00
Vork C.1
Votto ESN
Meda ECV
2.7
Kott Thaadass
Meaa-DH Pheeze
2013 Degres of the BRCs with 10"3 nodes
8000
Dugree of RRCS with 10"4 modes
Degroe of RBCa with 10 modea
Figure 4: ApRs in the MIS problem RRGs. Meta-EGN and EGN both trained with the output of
Random Greedy Algorithm (RGA) as initialization.
Gurobi9.5 that runs for 3000 seconds on RB5000 dataset in the MC problem. Moreover, Meta- EGN can even outperform Gurobi9.5 on the MVC problem when the problem scale becomes large.
Real-Synthetic Distribution Shift: Here, we train EGN and Meta-EGN on Twitter and test them on We observe better generaliza- tion performance of Meta-EGN compared to EGN. For example. for the MC, Meta-EGN has almost the same performance whether there is a dataset shift or not (0.833 v.s. 0.834 before fine-tuning, 0.876 v.s. 0.878 after fine-tuning) while EGN has a bigger gap in performance when there a shift (0.819 v.s. 0.829 before fine-tuning, 0.831 v.s. 0.864 after fine-tuning). For the MVC, although the performance drop of Meta-EGN is larger, such a drop is still much smaller than that of EGN.
RB500. Table 6 shows the results. Compare Table 6 with Tables 3 4
5.4 MAX INDEPENDENT SET: A RESPONSE TO (ANGELINI & RICCI- TERSSNHERS 2022)
For the MIS problem on large-scale RRGs, Angelini & Ricci- Tersenghi (2022) have recently posted a concern on learning-based methods by arguing that PI-GNN in (Schuetz ct al.] (2022) could not achieve comparable results with the heuristic algorithm DGA (Angelini & Rerei-Tersenghi 2019). We see the reason comes from improper usage of learning-based methods in (Schuetz et al. (2022) as stated in
DKA
10"2-
Time begroppha
10"1
107-1
Sec. [ 1) PI-GNN is trained directly on each single test- ing instance without learning from the training dataset that contains varies graphs, which is likely to be trapped into the local optima; 2) GNN generally suffers from a node ambi- guity issue RRGs. To resolve the problem, initialization of GNN inputs (EGN, Meta-EGN) and expect to learn heuristics from historical data to further tune the solutions given by the greedy algorithms. We train GNN models on RRGs with 1000 nodes with node degrees randomly sampled from 3, 7, 10, 20, and test on larger RRGs (up to 10s nodes). Experiments show that Meta-EGN can further improve DGA (in Fig. I and RGA (in Fig. while EGN fails to better tune DGA. Note that here EGN and Meta-EGN adopt the exactly same backbones. We attribute the improvement to leaannge based training as adopted by Meta- EGN. See Table 7 in Appendix for more details of the numerical improvement by Meta-EGN. We also see in these cases, one-step fine-tuning does not contribute much to the performance of EGN or Meta-EGN, indicating the model before fine-tuning has been very close to local minimum.
10"-2
10"2
10-3
10"4
10"5
Number of Nodes (degree=
Figure 5: Time cost v.s. Graph Scales.
utilize the outputs of DGA and RGA as the
We also check the extra time cost by running Meta-EGN to improve DGA solutions in Fig. 5 and Fig. in Appendix. The extra time cost is just 1% (without fine-tuning) - 30% (with fine-tuning) of the time cost of DGA. In theory, the extra time cost without fine-tuning should be O(E)) for GNN inference plus O(IV)) for rounding, which is in the same order as DGA, while the GNN parallel inference substantially reduces the time.
6 CONCLUSION
This work proposes an unsupervised learning framework Meta-EGN with the goal of optimizing NNs towards instance-wise good solutions to CO problems. Meta-EGN leverages MAML to achieve the goal. Meta-EGN views each training instance for all these tasks. Meta-EGN significantly improves the performance of its baseline and has shown good generalization when the data used for training and testing has different scales distributions. In addition, Meta-EGN can learn to improve the greedy heuristics while paying almost no extra time cost in the problem of maximum independent set on large-scale random regular graphs.
separate task and learns good initialization

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENT
We would like to express our deepest appreciation to Dr. Tianyi Chen for the insightful discussion on the meta-learning framework from a theoretical aspect and Dr. Ruqi Zhang for the constructive advice on the fine-tuning strategies. We would also like to extend our deepest gratitude to Dr. Hanjun Dai and Dr. Jialin Liu for sharing their invaluable insights into the general ideas of learning for combinatorial optimization. Also many thanks to our funding, H. Wang and P. Li are partially supported by 2021 JPMorgan Faculty Award and the NSF award OAC-2117997.
REFERENCES
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An un- supervised differentiable approach. In International Conference on Learning Representations, 2018.
Diogo V Andrade, Mauricio GC Resende, and Renato Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525-54) 547, 2012.
Maria Chiara Angelini and Federico Ricci-Tersenghi. Monte carlo algorithms very effective in finding the largest independent set in sparse random graphs. Physical Review E, 100(1):01300,, 2019.
Maria Chiara Angelini and Federico Ricci-Tersenghi. Cracking nuts with sledgehammer. when modern graph neural networks do worse than classical greedy algorithms. arXiv preprint arXiv:2206. 1 13211, 2022.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 161 1.09940, 2016.
Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 32, 2019.
Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. Meta-learning to compositionally gen- eralize. ACL/JCNLPP (1), 2021.
Yves Crama. Combinatorial optimization models for production scheduling in automated manufac- turing systems. European Journal of Operational Research, 99(1):136-153, 1997.
Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with com- binatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems, 33, 2020.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International conference on machine learning, pp. 1112-11135 PMLR, 2017.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
LLC Gurobi Optimization. Gurobi optimizer reference manual, 2022.
John J Hopfield and David W Tank. "neural" computation of decisions in optimization problems. Biological cybernetics, 52(3):141-152, 1985.
Kyle Hsu, Sergey Levine, and Chelsea Finn. Unsupervised learning via meta-learning. Interna- tional Conference on Learning Representaatinss 2018.
Benjamin Hudson, Qingbiao Li. Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint 10.05921,, 2021.
10

---

Published as a conference paper at ICLR 2023
Taewon Jeong and Heeyoung Kim. Ood-maml: Meta-learning for few-shot cut-of-distribution de- tection and classification. Advances in Neural Information Processing Systems, 33:3907-3916, 2020.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 19X.:::9060012,,,, 2019.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization graphs. Advances in Neural Information Processing Systems, 33: 2020.
Elias Khalil, Pierre Le Bodic, Le Song. George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Yeong-Dae Kwon, Jinho Choo, I1joo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34, 2021.
Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnevv. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings the AAAI conference on artificial intelligence, volume 33, pp. 1600-46000 2019.
Yatin Nandwani, Deepanshu Jindal, Parag Singla, al. Neural learning of one-of one-of-many solutions for combinatorial problems in structured output spaces. In International Conference on Learning Representations, 2021.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-leaming algorithms. arXiv preprint arXiv:1803.0020 2018.
Joseph O'rourke. Art gallery theorems and algorithms, volume 57, Oxford New York, 1987.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and com-
plexiry. Courier Corporation, 1998.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems 32. 2019.
Mustazee Rahman and Balint Virag. Local algorithms for independent sets are half-optimal. The Annals of Probability, 45(3):1543-1577, 2017.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-leaming with im- plicit gradients. Advances in neural information processing systems, 32, 2019.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.

---

Published as a conference paper at ICLR 2023
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Perey Liang, Leonardo de Moura, and David L
Dill. Learning a sat solver from single-bit supervision. arXiv preprint
2018.
Kate Smith. Neural networks for combinatorial optimization: a review of more than a decade of research. Informs journal on Computing, 11(I):15-34 1999.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Run-csp: unsupervised learning of message passing networks for binary constraint satisfaction problems. 2019.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maxi- mum constraint satisfaction. Frontiers in artificial intelligence, 3:580607, 2021.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural informa-
tion processing systems, 28, 2015.
Haoyu Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. Advances in neural information processing systems, 35, 2022.
K BHOSLIB Xu. Benchmarks with hidden optimum solutions for graph problems. URL http://www. nlsde. buaa. edu. culkeew/bencumarkkfggapp www.hraarp-becmmakk..... htm, 2007.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Kenichi Yabuta and Hitoshi Kitazawa. Optimum camera placement considering camera specification for security monitoring. In 2008 IFEE International Symposium on Circuits and Systems (ISCAS), pp. 1177-2117. IERE, 2008
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Weichi Yao, Afonso S Bandeira, and Soledad Villar. Experimental performance of graph neural networks on random instances of max-cut. In Wavelets and Sparsity XVIII, volume 11138, pp. 242-251 2019.
Gal Yehuda Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what we cannot teach. In International conference on machine learning, pp. 10831-10844 PMLR, 2020.
Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. Ad- vances in Neural Information Processing Systems, 32, 2019.
A PROOF OF THEOREM
We first prove Theorem 1 then we specify the value of a to obtain Theorem 2 as a specific case of Theorem I
The proof of Theorem I is divided into two parts.
In part 1, we prove that if I(0; G) < B + A (even if I(0; G) 2 B), for any a E (0, 2/L. Meta-GNN with one-step finetuning outputs feasible solution X of good quality f(X; G) - 1(0: G) AA
Here, A | (0; Ic+ 21 to 2² if < a (e) G) or A = (a La² ] G)Il² o.w..
1
In part 2, we prove that once Meta-EGN achieves the loss value 1(0'; G*) after the one-step finetuning, the rounding process would output a feasible whose objective satisfies f(x; G) < G(
Part 1:We could get
(a) G((':)) & ((0:)) + Vol(O: - 0) +
1
2 - - 0112
( ((0::) }
1 _ 012 all alVV)((0GG)1
(6)
= =[((;G) + La² - a)) G)
2
12

---

Published as a conference paper at ICLR 2023
where (a) is due the local L-smoothness of; G); (b) due to the definition of one-step finetuning = 8 (V) If E < V.l
Let = Vol(0; G)lle+ 2T. 4n e², we have:
La² a Vo((o;
min - min
2² Vol[O;
( 2
2La² 4a
thus
1(0'; S ((: A.
(8)
If 2f Vll
Let A = (a (a²)aa) La² Vol(O; ?) we would directly have:
1(0'; G) < ((0 - A.
(9)
By this, finish the first part of the proof for Theorem !
The proof in this part follows the rounding analysis in Wang et al. (2022). Consider the rounding procedure from continuous space X Ac( X [0, 0, into the discrete feasible solution E {0, 13". Let X,, X,, = {0, 1,., n denote their entries. W.L.ogg suppose the rounding order is from 1 to and have finished the rounding before the 1-th node, we now analyze the rounding of 1-th node:
Part 2:
5.([X1,-.. X1-1, Xx, X 4+1, G,):G) + 8gr ( X X,, X, ++1 X,):G)
(4)
(f X 1, Xx+II...NIICC.. + 3g, (I, 1, X Xnl:
+ (1- (f) X,- 0, X X,] G) + Bg, ( ([,,, 0,-1, G,);
2 2Xx( min Fr([X1, X,- Jr X, X Xmli G) + 3g, (1X1, X,- Ne Xn]; G))
(0.1)
+ (1 - Xe)( min
fr((X, X )==(0,1)
1: jr,
G)
+ (g Je X Gn);
@ ((X1, Xt-1, X1, Xe, ... x, G) (IX, X1-1, Xe, X,,, X.]:GG)
(10)
where (d) is due (0: G)'s entry-wise concavity w.r.t X and Jensen's inequality, (e) is due
to X, = arg miny=0.1 [x X,-1,f, 1, Xx+1,-.,,,,, X,,) + (X, Xt-1,4, X Xx+1,-... Xx,) (the
definition of our rounding process). The loss value is monotonically non-increasing through the whole rounding process according to the equation above, thus we could get:
1(0') f(X;G) G)
(11)
By this, we finish the proof of the second part.
A. A SPECIFIC CASE
Note that in the first part of the proof above, if we specify the value of in equation (6), could have:
Vol(( G)
1(8'; < I(((;))
(12)
2L
If < 7, [o
Let A |V 2e2, have:
min A min 2 Gol( -/ G)
(13)
2
2L
thus
(0';G) 1(00 G) A.
(14)
13

---

Published as a conference paper at ICLR 2023
2 1 If c
VV(( Let A G)) would directly have:
I((':G) (() -
(15)
By this, we obtain Theorem
a specific case of Theorem aas follows:
Theorem (A Specific case of Theorem D}. Suppose the relaxations fr and gr are entry-wise con-
cave as required in (Wang et al. 2022). Let 0 denote the learned parameter after training. Given
G) I LI|0' -0]] for all 8' that satisfies ||6' - 01 I c. Then, if ()0 < 3 A (even (f; G) 2 3). there ex-
test instance G. suppose locally (=; G) L-smooth
i.e., G)
ists a such that Meta-GNN with one-step finetuning outputs feasible solution X of good quality
f(X;G) < 1(0 A. Here, A [Val(0; G))le _e² if [VVo(( G) or A IV G)ll² o.w.
B SUPPLEMENTARY EXPERIMENT RESULTS
B. SUPPLEMENTARY TIME COST V.S. GRAPH SCALE IN THE MIS
we show the degree 3, 7, 10 in the following Fig. 6 They show the same time-cost vs scale relation
as that Fig. 5 The extra time cost of GNN O(IEI) for inference plus O(VVI for rounding. which is in the same order of DGA.
DGA
DGA Sota FOX Plan-em
DGA
10"2-
Natx 2024 Plani
1072
10"2
Kike Z0N HuRe
(0graght
10"1
10
1
100-1
105-1
10"-2
10"-2
1072
107g
10"4
1005
1072
19h3
10"4
10"5
12*2
1073
104
10"5
Number Nodee (degma-33)
Number Nodie (degres-7)
Nomthe Nodex, (degrew
Figure 6: Time cost v.s. Graph Scales degrce 3,7,10
B.2 How MUCH DOES META-EGN MODIFY DGA AND RGA HEURISTICS IN THE MIS
We display the average approximation rate improvement and the average node number increase by Meta-EGN over DGA and RGA in Table. 7
Table 7: Improvement of Meta-EGN over DGA and RGA in the MIS RRGs, 'Imp ApR denotes the
average improvement in approximation rate, and 'Imp in #Nde' denotes the average number of nodes that Meta-EGN could find more than the heuristics.
Degeee
Inp ApR
Inp &Noll
Imp in ApR
Imp @Nonk
Imp ApR
#/Nokk
ApR
NNoll
10
0.0099
2,014
1.254
010084
1,657
McN+-EONN improwes DGIA by
improves RGA by
3966.172
0,1045
3507.731
1912.000
B.3 TRAINING THE MODELS ON SUBSETS OF THE TRAINING DATA
We display the average approximation rates the models that are only trained on subsets of the original training data in the max clique problem on Twitter. The training dataset is randomly sampled from the original training dataset and the testing dataset remains the same as that in Table. 3 Both methods have worse performance the number of training instances reduces, while Meta-EGN only has a 0.6% performance decrease from the full-size training dataset with 695 samples to the training subset with only 64 instances. In contrast, EGN decreases its performance by 1.7%.
14

---

Published as a conference paper at ICLR 2023
Table The approxination rate the max clique problem on Twitter. Models are only trained on subsets of the dataset, 'training subset' denotes the number of instances in the training data.
training subset
128
256
512
Full (665)
EGN
0.909+0. 122
0.911=0.118 0.973=0.055
0.914=0.118 0.975=0.055
0.92240. 115
0.926#0.115 113 0.976#0.048
Meta-EGN
0.970=0.058
0.975#0.051
B.4 TRAINING THE MODELS ON RRGs WITH SINGLE DEGRBES IN THE MIS
We train the EGN and Meta-EGN models on RRGs with only 3 or 20 degrees and test them on RRGs with the rest degrees from {3, 7, 10, 20). Models take the output of DGA as the initialization graph node feature. We show the performance of both the models without fine-tuning in Fig. 7 When only trained on RRGs with degree 3 (See the left two figures in Fig. both the models could not generalize well, neither of them could outperform the initialization input of DGA. Note that Meta-EGN still achieves better performance than EGN in this case. As to the models only trained on RRGs with degree 20 (See the right two figures in Fig. 7. we observe that both the model have relatively good generalization ability across different degrees, yet Meta-EGN could still marginally outperform EGN in this case. We attribute this phenomenon RRGs with degree 20 is much more complicated than those with degree 3 and thus may contain adequate heuristics for solving RRGs with lower degrees.
the fact that solving the MIS on
Of 2801 wihh Sndda
Degice of 10Ge vib aodes
Dopns of af te
Figure 7: The left two figures show the ApRs RRGs with 10 and 10" nodes of the models trained only on RRGs with degree The right two figures show the ApRs on RRGs with 10 and 10* nodes of the models trained only on RRGs with degree 20.
B.5 COMPARISON ON THE TRAINING TIME OF THE MODELS
We display the wall clock training time for the two methods to converge Table. 9 (from start to the best epoch validation set). We observe that Meta-EGN generally takes two to three times to converge compared with EGN, but their training time cost basically remains on the same order of magnitude.
Table 9: The wall clock training time convergence of EGN and Meta-EGi in different problems.
Dataset/Time (min:second)
MC
MVC RB200
MIS RRGs
Twitter
RB200
RB500
Twitter
RB500
EGN
46:50
104:37
282:57
100:58
83:27 168:25
128:39
733:02 1088:55
Meta-EGN
101:55
210:04
609:47
276:38
282:15
C SUPPLEMENTARY IMPLEMENTATION DETAILS
C.1 EXPERIMENT DETAILS
All the codes run on the Py Torch platform 1.9.0 (Paszke et al. 2019) and Py Torch Geometric frame- work 1.7.2 (Fey & Lenssen 2019). The details of each dataset is shown in Table. 10 all of the real datasets are publicly available, and we follow the code in (Toenshoff et al. (202T) to generate the RB model. The real-world dataset split follows that in Karalias & Loukas (2020).
To balance the training time per epoch of EGN and Meta-EGN, EGN, we define the epoch as follows: For each epoch of EGN training, the whole dataset is split into mini-batches. EGN performs standard
15

---

Published as a conference paper at ICLR 2023
The number instances each dataset. "20scaal//degeee means that we generate 20 testing instances for each different scale-degree pair. We generate RB RB1000, RB2000, and RB5000 only for testing.
Table 10:
Dataset
Twitter
COLLAB
IMDB
RB200
RB500
RB1000
RB2000
RB5000
RRGs
Training
665
3150
700
2000
2000
3000
Validation
95
450
100
100
100
15 20/scale degree
Testing
190
900
200
100
100
100
100
100
mini-batch training along these batches and optimizes over each mini-batch. As to Meta-EGN, for each training epoch Meta-EGN only randomly samples a single batch and does the meta learning algorithm the batch. The batch sizes of the methods are controlled the same.
C.2 DETAILED DERIVATION OF THE LOSS FUNCTION RELAXATION
In this part, we display the detailed loss function relaxation of the three problems in our study (the MC. the MVC, and the MIS). The basic idea of training loss design and relaxation follow (Karalias & Loukas 2020; Wang et al. 2022). In the following derivation, we use i,j to represent the nodes graphs, we use Xj {0. 1] to denote the discrete assignment of the binary optimization vari- ables, and use Xú, X3 [0, 1] denote the relaxed soft assignment of the binary optimization variables.
The maximum clique (MC): A clique is set of nodes S E such that any two distinct nodes in the set are adjacent. The MC aims to find out the clique with the largest number of nodes. We could formulated the optimization objective as follows:
max
Σ X. ISSA
s.t. Ei, =1
(16)
X, denotes whether to take the node into the clique set (X, = 1) or not (X; = 0). By setting a proper penalty coefficient B, could formulate the loss function relaxation as follows (the detailed derivation follows the corresponding case study in Karalias Loukas (2020))
8 Σ X,X,. + 2 171
(0; G) a (B++1)
Σ X,X, (KJ)EE
(17)
The minimum vertex covering (MVC): A vertex cover is a of nodes V that any edge in the graph is connected to at least a node from the set. The MVC aims to find out the cover set with the smallest number of nodes. The optimization objective could be summarized as follows:
min Σx,
s.t. X, 21 if (i.)) E,
(18)
ISiSn
where X,, X, denotes whether to take the node into the cover set (X; = 1) or not (X; = 0). We design the constraint function g to represent the total number of edges that have not been covered given a set of variable assignment X, and thus we write g as:
9MvC (avc(X:0r G) A (1- x,)(1 xx))
(19)
(KJEEE
Then we relax the constraint g and add it into the training objective by multiplying a proper penalty coefficient B, following the relaxation principle in Wang et al. (2022):
(Mv G) A Σ X (1- X,).
(20)
IsiSn
(K,))E
By this, we aim to minimize the value of the loss function above in order minimize the node number of the cover set as well as consider the covering property in the constraint.
The maximum independent set (MIS): An independent set is of nodes where any two distinct nodes in the set are not adjacent to each other. The MIS aims to find out the independent set with the largest number nodes. We could formulate the objective of the MIS as follows:
Σ 1si5n
X;
s.t. X,X, 0 if (i,5) F,
(21)
16

---

Published as a conference paper at ICLR 2023
where X,, X, denotes whether to take the node into the independent set (X; 1) not (X; 0). We formulate the constraint as the total number of edges whose two connected nodes at the end points are both assigned into the independent set. Therefore we could write the constraint as follows:
JMIS
Σ X,X,
(22)
((J)E
We then relax the constraint into continuous space and add it into the function with a proper penalty coefficient 3, following the relaxation principle in (Wang al. 2022), and thus could write the training loss function as:
MIS (0; G)
Σ 18i5n
X, +
Σ X,X, (iJ)EE
(23)
By this, we aim to minimize the value of the loss function above in order to maximize the node number of the independent set well consider the independent property in the constraint.
C.3 SEPARATED ALGORITHM TABLES
We separate the algorithm table of Meta-EGN into training and testing parts make it clearer. The algorithm table is shown in Alg. for training and Alg.
Algorithm Train Meta-EGN
Require:
Training instances = (G1, G2, Gm): Hyperparameters: (t;
1: Randomly initialize g(0)
2: for each randomly sampled mini-batch B, E 0,1...., do
Training starts
3: For each G; E Bj. compute the adapted parameter: 0.5) = 015) - aV oun av (00)) ((00) G.)
4: Update: g(++1) ((3) Vani Ec.eB, 1(0(");C G.)
5: end for
6: return 0 + O(K)
D Training ends
Algorithm Test Meta- EGN with/without Fine-tuning
Require: Testing instance G"; Hyperparameter: a; Pre-trained parameter initialization
1: For given testing instance G²:
Testing starts
2: if fine-tuning is allowed then
3: Fine-tune the parameters: Ogr 0 a Vol((0; G')
4: Use Def. to round the relaxed solution given by Ae (G')
With fine-tuning
5: else
6: Use Def. D to round the relaxed solution given by Ao
Without fine-tuning
7:
end if
8:
return the rounded solution
Testing ends
C.4 IMPLEMENTATION OF THE HEURISTICS
run all of the greedy algorithms with PyThon 3.8 in this paper. potential method boost time cost of these greedy algorithms is to use c++
Random Greedy Algorithm for MIS (RGA): RGA takes a time to reach a solution that is linear in the problem size It starts from empty independent set S. At each step < S node i chosen at random from the graph G, and added to the independent set. Then all the neighbors graph G.41. The process iterates until G is empty
of are removed from G2 to formulate step t", the solution S.
Degree-based Greedy Alforithm for MIS (DGA): DGA modifies RGA by sorting the degrees of the nodes before each iteration starts, and always put the node with the smallest degree into the independent set.
17

---

Published as a conference paper at ICLR 2023
Teonshoff Greedy for MC: Toenshoff et al. (2021) convert the testing instances into its complement graph, and then run DGA to solve the MIS problem. takes the solution to the MIS problem on the complement graph the solution for MC on the original graph.
Greedy for MVC: Greedy for MVC starts from an empty covering set S. At each step - t S n, first sorts the degrees of the nodes in the graph G2 and always adds the node with the largest degree into the covering set S. Then all the edges that connect with are removed from G₃ to formulate a new graph Gr+1. The process stops until Gt- empty step t", the solution is S.
D DISCUSSION ON LIMITATIONS
As mentioned the end of Sec. 5.1 both EGN and Meta-EGN perform generally well in MC, which outputs the cliques that are more local in comparison with the vertex covering in MVCs that require more global assignments. The random initialization seed with one node randomly and the others as 0 would potentially limit the performance of EGN and Meta-EGN in more global CO tasks.
We use Meta-EGN and EGN to modify the solution of DGA and RGA in the MIS problem. In addition, there are also many other Monte Carlo (MC) algorithms (i.e. simulated annealing and parallel tempering) that could produce better results than DGA or RGA in RRGs (Angelini & Ricci- Tersenghi 2022). An intuitive idea to test whether we could learn Meta-EGN further fine-tune these more advanced MC algorithms in the MIS problem on RRGs.
We leave the research on modifying Meta-EGN to better deal with the CO problems that require global assignments and using Meta-EGN improve other advanced MC algorithms future study.
18


Reviews:
[{"review_id": "nbyyh1N2mQo", "reviewer": "Reviewer_oMcq", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This work suggests a framework of unsupervised learning for combinatorial optimization, which uses generally good initializations that determine via a meta-learning scheme. In particular, the authors propose a new objective of unsupervised learning that is capable of providing good initializations rather than direct solutions. Finally, the authors demonstrate the empirical results that show the effectiveness of the proposed method.", "summary_of_the_review": "Please see the above text boxes.", "strength_and_weaknesses": "## Strengths\n\nThis paper is generally well-written, and the main message of this work is clear. Moreover, the proposed algorithm shows good performance in many benchmarks.\n\n## Weaknesses\n\nThe novelty of this work is somewhat limited. However, I think that this does not degrade the quality of the paper much.\n\nMoreover, I think the sentence\n\n> our learning objective of a model is to make further optimization of the initialization given by this model over each of these pseudo-new instances yield good solutions\n\nshould be proved. I think that the reasoning for this statement is not provided appropriately.\n\nAlso, this work heavily relies on the recent work (Wang et al., 2022). Some parts of this work are very similar with the work (Wang et al., 2022).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OprwYHxnDa", "reviewer": "Reviewer_uyeg", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes an application of Model-agnostic meta learning (MAML) (Finn et al., 2017) for the Erdos-Goes-Neural (EGN) framework (Karalias and Loukas, 2020). This will allow faster learning of novel combinatorial optimization tasks through learning better model initialization. The method is applied to several classical problems such as Max clique (MC), Minimum vertex covering (MVC) and Max independent set (MIS). The empirical result is promising.", "summary_of_the_review": "This paper presents an interesting application of meta-learning on the EGN framework. There are some positive results, although they are not quite surprising. I have no major concerns about the quality of the paper. Overall, I would recommend a marginal acceptance.", "strength_and_weaknesses": "Strengths: Interesting application with a straight-forward solution. The authors provide a theoretical guarantee and obtain significant result on several classical problems.\n\nWeaknesses: \n\n-- Some missing important details, please check the questions below.\n\n-- Running time, including the pretraining time, should be thoroughly reported for fair comparison.\n\n-- It is unclear what should be the take away insight of this paper. EGN has been shown to be a robust CO solver that can generalize. Meta learning has been shown to improve generalization in many applications. While the results in this paper are mostly positive, I feel that they only serve to confirm previous insights. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NiFznOheSFV", "reviewer": "Reviewer_sUXy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a meta learning framework Meta-EGN that produces a good initialization for a neural CO solver. The authors build upon the work of Karalias & Loukas, (2020) and extend it to provide a performance guarantee for Meta-EGN as well.", "summary_of_the_review": "Overall I found the paper interesting and it poses some fun questions for future work. The novelty is a little incremental since it builds on top of recent work but the results are interesting.", "strength_and_weaknesses": "As demonstrated in the experiments section, Meta-EGN works well compared to all relevant baselines, except for Gurobi of course, which is known to be in a league of its own compared to any neural CO solver. It is fascinating that such a general parameter $\\theta$ can even exist for these problems.\n\nThe ability to extend the performance guarantees of EGN toMeta-EGN is also a good win.\n\nOne drawback is missing ablation studies about the technique - some questions that I would be interested in are\n\n- How does Meta-EGN perform as a function of %of the training data used? i.e., if we initialize algorithm 1 with random subsets of the full training dataset of size N/2 instead N and training Meta-EGN to convergence, how does the algorithm perform?\n- How does Meta-EGN generalize if it is trained on graphs with certain statistics i.e. average node degree < 3 and then evaluated on graphs with avg node degree > 3? Or similar studies.\n\nAblation studies like these would help answer how sensitive Meta-EGN is to the quality of the training data set, my hypothesis is that if the training data set is not diverse enough, Meta-EGN wont work as well.\n\n>  the current framework optimizes an averaged performance over the distribution of historical problem instances, which misaligns with the actual goal of CO that looks for a good solution to every future encountered instance'\n\nA note on this comment - in practice - we don't wont want to solve the general case problem cause often CO problems can be intractable (eg NP Hard). Instead, practitioners would develop a heuristic to try to exploit a property that is only true in the distribution of instances that they are interested. eg. TSP is hard in general but approx algos exist in a metric space -- It is unclear from the paper what a practitioner should do in this case - should they use a training dataset that matches the distribution of instances that they are interested in OR should they use a more general distribution of instances since it will allow Meta-EGN to learn general case properties about the problem which wont be visible in the specific distribution.\n\nAn excellent version of the paper would offer more direction to practitioners on how to use the framework, however this could be tackled in future work.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-_0ubWFWBm", "reviewer": "Reviewer_5Wy8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to automatically solve combinatorial optimization by leveraging unsupervised learning, learning from historical data and \nachieving an instance-wise good solution simultaneously. In order to do so, the authors propose a methodology for warm-starting future combinatorial optimization problem instances. The methodology is based on meta-learning. The authors show that warm-staring is beneficial indeed across multiple datasets and shifts. \n", "summary_of_the_review": "The reviewer finds this work interesting and promising with sufficient empirical validation.", "strength_and_weaknesses": "This is an interesting work with promising results. Would the author please comment on whether the methodology can also be casted as a multi-task learning? Moreover, what are other applications/extensions of the proposed framework? There several discrete black-box expensive potentially noise-corrupted discrete optimization applications which can benefit from this methodology. One such example is chip design and the other is NAS (amongst many other). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster