Controlling Continuous Relaxation for Combinatorial Optimization
Authors: Yuma Ichikawa
Venue: NeurIPS 2024 poster (2024)
Keywords: Combinatorial Optimization
Unsupervised Learning for Combinatorial Optimization
Learning for Combinatorial Optimization
Graph Neual Networks
Primary area: optimization
TL;DR: Overcoming a local optima issue and rounding issue for unsupervised learning based combinatorial optimization solvers

Abstract: Unsupervised learning (UL)-based solvers for combinatorial optimization (CO) train a neural network that generates a soft solution by directly optimizing the CO objective using a continuous relaxation strategy. These solvers offer several advantages over traditional methods and other learning-based methods, particularly for large-scale CO problems. However, UL-based solvers face two practical issues: (I) an optimization issue, where UL-based solvers are easily trapped at local optima, and (II) a rounding issue, where UL-based solvers require artificial post-learning rounding from the continuous space back to the original discrete space, undermining the robustness of the results. This study proposes a Continuous Relaxation Annealing (CRA) strategy, an effective rounding-free learning method for UL-based solvers. CRA introduces a penalty term that dynamically shifts from prioritizing continuous solutions, effectively smoothing the non-convexity of the objective function, to enforcing discreteness, eliminating artificial rounding. Experimental results demonstrate that CRA significantly enhances the performance of UL-based solvers, outperforming existing UL-based solvers and greedy algorithms in complex CO problems. Additionally, CRA effectively eliminates artificial rounding and accelerates the learning process.

Controlling Continuous Relaxation for Combinatorial Optimization
Yuma Ichikawa
Fujitsu Limited, Kanagawa, Japan Department of Basic Science, University of Tokyo
Abstract
Unsupervised learning (UL)-based solvers for combinatorial optimization (CO) train neural network that generates soft solution by directly optimizing the CO objective using a continuous relaxation strategy. These solvers offer several advantages over traditional methods and other learning- -based methods, particu- larly for large-scale CO problems. However, UL-based solvers face two practical issues: (I) optimization issue, where UL-bbaed solvers are easily trapped local optima, and (II) rounding issue, where UL-bbaee solvers require artificial post-learning rounding from the continuous space back to the original discrete space, undermining the robustness of the results. This study proposes Continuous Relaxation Annealing (CRA) strategy, an effective rounding- -fren learning method for UL-based solvers. CRA introduces penalty term that dynamically shifts from prioritizing continuous solutions, effectively smoothing the non-convexity of the objective function, to enforcing discreteness, eliminating artificial rounding. Experimental results demonstrate that CRA significantly enhances the performance of UL-based solvers, outperforming existing UL-based solvers and greedy algo- rithms in complex CO problems. Additionally, CRA effectively eliminates artificial rounding and accelerates the learning process.
Introduction
The objective of combinatorial optimization (CO) problems is to find the optimal solution from discrete space, and these problems are fundamental many real-world applications (Papadimitriou and Steiglitz| 1998). Most CO problems are NP-hard or NP-complete; making it challenging to solve large-scale problems within feasible computational time. Traditional methods frequently depend on heuristics to find approximate solutions, but they require considerable insights into the specific problems. Alternatively, CO problems can be formulated as integer linear programming (ILP) and solved using ILP solvers. However, ILP solvers lacks scalability for large-scaled problems.
Recently, several studies have used machine learning methods handle CO problems by learning heuristics. Most of these studies focus supervised learning -SL.)-based solvers [Hudson et al. [021 Joshi et al., 2019 Gasse et al. 2019 Selsam et al. 2018 Khalil et al.) 2016), which require optimal solutions to CO problems supervision during training. However, obtaining optimal solutions is challenging in practice, and SL-based solvers often fail to generalize well (Yehuda et al., 2020)
Reinforcement learning (RL)-based solvers Yao et al. 2019 Chen and Tian 2019 Yolcu and Póczos 2019 Nazari et al. 20188] Khalil et al.) [001]] Bello et al. [0166] avoid the need for optimal solutions but often suffer from notoriously unstable training due to poor gradient estimation and
hard explorations MMnih et al. 2015 Tang et al.) [017 Espeholt et al. 2018). Unsupervised learning
(UL))baseed solvers [Schuetz al. 2022a Karalias and Loukas 2020 Amizadeh al. 2018 have
'The code is available at htthtttss//gthhhe /uipi
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

recently attracted much attention. UL-based solvers follow a continuous relaxation approach, training a UL model to oulput a soft solution to the relaxed CO problem by directly optimizing a differentiable objective function, offering significantly stable and fast training even for large-scale CO problems. Notably, the physies-inspired GNN (PI-GNN) solver [Schuetz et al., 2022a employs graph neural networks (GNN) to automatically learn instance-specific heuristics and performs on par with or outperforms existing solvers for CO problems with millions of variables without optimal solutions.
While these offer some advantages over traditional and other machine learning-based solvers, they face two practical issues. The first issue is an optimization issues where UL-based solvers are easily trapped at local optima. Due to this issue, Angelini and Ricci- Tersenghi (2023) demonstrated that the PI-GNN solver [Schuetz et al. 2022a] could not achieve results comparable to those of the degree- based greedy algorithm (DGA) [Angelini and Ricci- TersenTessnghh [2019] on maximum independent set (MIS) problems in random regular graphs (RRG). Wang and Li [023] also pointed out the importance of using dataset or history, and initializing the GNN with outputs from greedy solvers to help the PI-GNN solver overcome optimization challenges. This issue a crucial bottleneck to the applicability of this method across various real-world applications. The second issue relates to the inherent ambiguity of the continuous relaxation approach. This approach necessitates artificial rounding from the soft solution, which may include continuous values, back to the original discrete solution, potentially undermining the robustness of the results. While linear relaxation can provide an optimal solution for original discrete problems bipartite graphs [Hoffman and Kruskal 2010) it typically leads to solutions with 1/2 values, which is known to balf-integrality [Nemhauser and Trotter Jr [974]. in which existing rounding methods [Schuetz al. 2022b Wang al. 2022 completely lose their robustness. For NP-hard problems with graph structures, such as the MIS and MaxCut, semidefinite programming (SDP) relaxations have been proposed effective approximation
methods [Lovász] 1979, Goemans and Williamson 1995]. However, these approaches rely on rounding techniques, such as spectral clustering [Von Luxburg 2007], to transform relaxed solutions into feasible ones, which often fails to obtain optimal solutions.
To address these issues, we propose the Continuous Relaxation Annealing (CRA). CRA introduces penalty term to control the continuity and discreteness of the relaxed variables, with a parameter y to regulate the intensity of this penalty term. When the parameter is small, the relaxed variable tends to favor continuous solutions, whereas a large y biases them toward discrete values. This penalty term also effectively eliminates local optimum. Moreover, small forces the loss function approach a simple convex function, encouraging active exploration within the continuous space. CRA also includes annealing process, where " is gradually increased until the relaxed variables approach discrete values, eliminating the artificial rounding from the continuous to the original discrete space after learning. In this study, the solver that applies the CRA to the PI-GNN solver is referred to as the CRA-PI-GNN solver. We also demonstrate the benefits of the CRA through experiments on benchmark CO problems, including MIS, maximum cut (MaxCut). and diverse bipartite matching (DBM) problems across graphs of varying sizes and degrees. The experimental results show that the CRA significantly enhances the performance of the PI-GNN solver, outperforming the original PI- GNN solver, other state-of-the-arr learming-basse based basclines, and greedy algorithms. This improvement achieved by directly optimizing each instance without any history, e.g., previous optimal solutions and the information of other instances. Additionally, these experiments indicate that the CRA accelerates the learning process of the PI-GNN solver. Notably, these results overcome the limitations pointed out by Angelini and Ricci-Tersengle 2023). Wang and Li 2023), highlighting the further potential of UL-based solvers.
Notation. We use the shorthand expression [AV] = (1, N1. where N N. IN E R denotes an N x N identity matrix, 1x denotes the vector (I...., 1) E R. and ON denotes the undirected graph, where V is the set of nodes with cardinality [V] = N, and E C V x V denotes the set of edges. For a graph GVV, Asy denotes the adjacency matrix, where Ag 0 if an edge (i,j) does not exist and Aij > 0 if the edge is present.
vector (0...... .o.....00 0)T e N. G(V, E) represents
2 Background
The goal of this study is to solve the following CO problem. Combinatorial optimization.
min f(x; C) s.t. x E (C),
=E(0,1)
2

---

where C' E C denotes -pstafcc-specific parameters, such graph G = (V, E). and C represents the set of all possible instances. f x C + R denotes the cost function. Additionally, (zi) E {0, 1 is binary vector to be optimized, and ((C) S (0, 1 denotes the feasible solution space, typically defined by the following equality and inequality constraints.
X(C) = ( E 10, Vi E [7] (a; C) S O, Vj E [J), (, = 00, I,JEN,
where, for i E [.. 9i : 10, x + R denotes the inequality constraint, and for i
h; (0. 1 x C R denotes the equality constraint. Following UL.-based solvers [Wang et al.
2022, Schuetz et al.) 2022a| Karalias and Loukas 2020), we reformulate the constrained problem
into equivalent unconstrained form using the penalty method (Smith et al. 1997|:
I+J
min (a;; A), 1(x; C, f(a; C)
+
Σ
Xeve(ar; C).
=
where, for all i E +J+
[0,1] C + R is the penalty term, which increases when the constraints are violated. For example, the penalty term is defined as follows:
vi E [7.j E [J], (;(2;C) C) = max(0. 9i (x; C)), Vj E [J], by(x; C) = (h,(2;
and À = (5) E I denotes the penalty parameters that control the trade-off between constraint satisfaction and cost optimization. Note that, as À increases, the penalty for constraint violations becomes more significant. In the following, we provide an example of this formulation.
Example: MIS problem. The MIS problem fundamental NP-hard problem Karp 2010).
defined as follows. Given undirected graph GVV, E), an independent set (IS) is a subset of nodes V where any two nodes are not adjacent. The MIS problem aims to find the largest IS, denoted as It In this study, p denotes the IS density, defined as a binary variable 2; assigned to each node E
[Z] Following Schuetz et al. [0022a] The MIS problem can be formulated as tollows:
V.
[(:; (a:;GA) A) =
Σx x4 Cx+
Σ T,
iEV
(KJ)
where the first term maximizes the number of nodes assigned value of 1, and the second term penalizes adjacent nodes assigned 1 according to the penalty parameter X.
2.1 Unsupervised learning based solvers
Learning for CO problems involves training an algorithm A.(-) C. - {0, 13 parameterized by neural network (NN), where denotes the parameters. For a given instance E C, this algorithm generates valid solution å AC(C) E (C)) and aims to minimize fát; C). Several approaches have been proposed to train Ag. This study focuses on UL-bbaed solvers, which do not use labeled
solution x= argmin ge x(C)) (x: C') during training [Wang et al.) 2022 Schuetz et al. 2022a
Karalias and Loukas 2020 Amizadeh et al., 2018 In the tollowing, we outline the details of the OL-based solvers.
The UL-based solvers employ continuous relaxation strategy to train NN. This continuous relaxation strategy reformulates CO problem into continuous optimization problem by converting discrete variables into continuous ones. A typical example of continuous relaxation is expressed as follows:
min i(p: C, p
f(p: C)+
Σ Aeta(p: C).
where p = (p.)isiSN E [0, 1 represents set of relaxed continuous variables, where each binary variable v, E 1) is relaxed to continuous counterpart P; E [0, 1], and f [0, 1 C IR denotes the relaxed form of such that f(x; C*) = [(x; C) for æ E {0, 1 The relation between each constraint and its relaxation é; is similar for E [[.]]. meaning that vi E [T+J), 0z (æ;; C* va(:;; C) for x E {0, 1)M Wang et al. [2022 and Schuetz al. [2022a] formulated Ao as the relaxed continuous variables, defined Ag(-) C I In the following discussions, denote
3

---

Ag as pe to make the parametrization of the relaxed variables explicit. Then, po is optimized by directly minimizing the following aubel-independent function:
i(0; C, E F(po(C):C)+ + Σ (.((pp(O))))).
After training, the relaxed solution pe is converted into discrete variables using artificial rounding pe. where Vi E [A], 2, int(po (C)) based on threshold (Schuctz et al. 2022a], or alternatively, greedy method [Wang et al., 2022 Two types of schemes for Ul-bbased solvers have been developed based on this formulation.
(Type 1) Learning generalized heuristics from history/data. One approach, proposed by Karalias and Loukas 22200. , aims to automatically learn effective heuristics from historical dataset instances g= and then apply these learned hcuristics to a new instance C*, through inference. Note that this method assumes that either the training dataset is easily obtainable or that meaningful data augmentation is feasible. Specifically, given a set of training instances D = (Cw). sampled independently and identically from distribution P(C), the goal is to minimize the average loss function ming Ep=1 I(0; Cn. A). However, this method does not guarantee quality for a test instance,
D D= [C 1/
C². Even the training instances D are extensive and the test instance C follows P(C), low average performance Pre [((: C'] may not guarantee low 1(0; C') for on a specific C. To address this issue, Wang and Li [023] introduced a meta-learning approach where NNs aim to provide good initialization for future instances rather than direct solutions.
(Type II) Learning effective heuristics on specific single instance. Another approach, known as the PI-GNN solver [Schuetz et al. 2022a b). automatically learns instance-specific heuristics for a single instance using the instance parameter C. by directly applying Eq. 2. This approach addresses CO problems on graphs, where C = G(V, E), and employs GNNs for the relaxed variables GG)) Here, an L-layered GNN is trained to directly minimize i(0; C, A), taking as input graph G and the embedding vectors on its nodes, and outputting the relaxed solution po (G) E [0. 1J A detailed description of GNNs is provided in Appendix E.2 Note that this setting is applicable even when the training dataset D is difficult to obtain. The overparameterization of relaxed variables is expected to smooth the objective function by introducing additional parameters to the optimization problem, similar to the kernel method. However, minimizing Eq. [2. Eq. for a single instance can be time-consuming compared to the inference process. Nonetheless, for large-scale CO problems, this approach has been reported to outperform other solvers in terms of both computational time and solution quality [Schuetz al. 2022a b).
Note that, while both UL-based solvers for multiple instances (Type I) and individual instances (Type II) are valuable, this study focuses advancing the latter: a UL-based solver for single instance. Both types solvers are applicable to cost functions that meet a particular requirement due their reliance on gradient-based algorithm to minimize Eq 22.1
Assumption 2.1 (Differentiable cost function), The relaxed loss function i(0;; C, A) and its partial derivative a((e:cAAl/oo accessible during the optimization process.
These requirements encompass a nonlinear cost function and interactions involving many-body interactions, extending beyond simple two-body interactions.
3
Continuous relaxation annealing for UL-based solvers
In this section, we discuss the practical issues associated with UL--based solvers and then introduce continuous relaxation annealing (CRA) proposed solution.
3.1 Motivation: practical issues of UL.-based solvers
UL-based solvers (Type II) (Schuetz et al. 2022a b) are effective in addressing large-scale CO problems. However, these solvers present following two practical issues, highlighted in several recent studies [Wang and Lij, 2023 Angelini and Ricci-Tersseghh 2023). Additionally, we numerically validate these issues; see Appendix for detailed results.

---

(I) Ambiguity in rounding method after learning. UL-based solvers employ continuous re- laxation strategy to train NNs and then convert the relaxed continuous variables into discrete binary values through artificial rounding as discussed in Section 2. This inherent ambiguity in continuous relaxation strategy often results in potential discrepancies between the optimal solutions of the original discrete CO problem and those of the relaxed continuous one. Continuous relaxation expands the solution space, often producing continuous values that lower the cost compared to an optimal binary value. Indeed, while linear relaxation can provide an optimal solution for discrete problems on bipartite graphs [Hoffman and Kruskal, 2010], typically results in solutions with 1/2 values, which is known to interrityyyylity [Nemhauser and Trotter Jr. 1974]. Existing rounding methods (Schuetz et al. 2022b, Wang et al. [022] often lose robustness in these scenarios. In practice, PI-GNN solver often outputs values near 1/2, underscoring the limitations of current rounding techniques for UL--based solvers.
(II) Difficulty in optimizing NNs. Recently, Angelini and Kicci-Tersenge 2023 demonstrated that PI-GNN solver falls short of achieving results comparable to those of the degree- greedy algorithm (DGA) [Angelini and Ricci- Ricei-Tersenghi [019] when solving the MIS problems on RRGs.
Angelini and Ricci-Tersenge [2023] further emphasized the importance of evaluating UL-based solvers complex CO problems, where greedy algorithms typically perform worse. A representative example is the MIS problems on RRGs with a constant degree d >> 16, where a clustering transition in the solution space creates barriers that impede optimization. Moreover, [Wang and Li 2023) emphasized the importance of using training/historical datasets, D = (Cwhgss which contain various graphs and initialization using outputs from greedy solvers, such as DGA and RGA for MIS problems. Their numerical analysis indicated that PI-GNN solver tends to get trapped in local optima when directly optimized directly for a single instance without leveraging a training dataset DD. However, in a practical setting, systematic methods for generating or collecting training datasets D to effectively avoid local optima remains unclear. Additionally, training on instances that do not contribute to escaping local optima is time-consuming effective UL-based solver that can operate on a single instance without relying on training data, D. Our numerical experiments, detailed in Appendix F.1 also confirmed this optimization issue. They demonstrated that as problem complexity increases, the PI-GNN solver often drawn into trivial local optima, Po = Ov. in certain problems. This entrapment results in prolonged plateaus that significantly slow down the learning process and, in especially challenging cases, can render learning entirely infeasible. Our numerical experiments, detailed in Appendix F.I also validated this optimization issue, demonstrating that as the problem complexity increases, PI-GNN solver tends to be absorbed into the trivial local optima pe Oy in some problems, resulting in prolonged plateaus which significantly decelerates the learning process and, in particularly challenging cases, can render learning entirely infeasible.
Therefore, it is crucial to develop an
3.2 Continuous relaxation annealing
Penalty term to control discreteness and continuity. To address these issues, we propose a penalty term to control the balance between discreteness and continuity in the relaxed variables, formulated as follows:
N Σ (1- a E {2m | n E N+),
f(p: (()
4(p) A
where y R is penalty parameter, and the even number denote rate. When y is negative, ie., y < 0, the relaxed variables tend to favor the continuous space, smoothing the non-convexity of the objective function [(p; C, A) due to the convexity of the penalty term (p)). In contrast, when is positive, i.e., 7 O. the relaxed variables tend favor discrete space, smoothing out the continuous solution into discrete solution. Formally, the following theorem holds as X approaches too.
Theorem 3.1. Assuming the objective function i(p; C`) is bounded within the domain [o, 1|N, as y + +oc, the relaxed solutions p' E arrmiin, ((p; C, X,7) converge to the original solutions x E argming!((x; C, A). Moreover, as r + -00, the loss function f(p; C, X,7) becomes convex, and the relaxed solution 1x/2 /22 argmin, f (p, C. x,7) is unique.
For the detailed proof, refer to Appendix B. Theorem 3.1 can be generalized for any convex function (pp C') that has unique maximum at 1w/2 and achieves global minimum for all {0, 1 an
5

---

example is binary cross entropy CE i= (pr 1o (1-g)) introduced by Sun
al. 2022]. Sanokowski et al. 2024] for the UL-based solvers (Type 1). Additionally. the penalty term eliminates the stationary point p' ON descrited in Section 3.1 preventing convergence to
plateau. For Ul.-based solvers, the penalty term is expressed as follows:
r(0; A. 7) = 1(0 C, + -
where ( C) A (C)) According to Theorem 3.1 setting sufficiently large value cases the relaxed variables to approach nearly discrete values. We can also generalize this penalty term (0;; C)), to Potts variables optimization, including coloring problems [Schuetz et al. 2022bb] and mixed mixed-integer optimization; refer to Appendix C.I
Annealing penalty term. We propose an annealing strategy that gradually anneals the penalty parameter in Eq. (3.2). Initially, negative gamma value, i.e.,
GNN
Y Y<0 << 0 Smoothing
y < O, is chosen to leverage the properties, facilitating broad exploration by smoothing the non-convexity of i(;; C, X) and eliminating the stationary point p ON to avoid the plateau, as discussed in Section 3.1 Subse- quently, the penalty parameter is gradually increased to a positive value, > 0, with each update of the trainable parameters (one epoch), until the penalty term approaches zero, i.e., (0, C*) ze O, to automatically round the relaxed variables by smoothing out subopti- mal continuous solutions oscillating between or 0. A conceptual diagram of this annealing process is shown in Fig.
(0.0)
(1.0)
= 0
Y y>0 0 Smoothing & Automatic Rounding
y
Optimal
Note that employing the binary cross-entropy PCE(p) (p) is infeasible for UL-based solvers when 7 > O, as the gradient (Pcc(p)/op diverges #oo at 0 or 1. In deed, when y = 0, most relaxed variables typically approach binary values, with relatively small number of vari- ables oscillating between 0 and 1. This gradient diver- gence issue in (P) makes the learning infeasible without additional techniques, such as gradient clipping. In contrast, the gradient of the penalty term in Eq. [3.2] o is bounded within [-2a, 20x] for any pre-
Value
Figure 1: Annealing strategy. When y < O. it facilitates exploration by reducing the non-convexity of the objective function. As 7 increases, promotes optimal dis- crete solutions by smoothing away subop- timal continuous ones.
venting the gradient divergence issue seen in (P)(P). Additionally, by increasing a, the absolute value of the gradient near 1/2 becomes smaller, allowing for control over the smoothing strength toward a discrete solution near 1/2.
We also propose an early stopping strategy that monitors both the loss function and the penalty term, halting the annealing and learning processes when the penalty term approaches zero, i.c., (0; C) R O. Various annealing schedules can be considered; in this study, we employ the following scheduling: 7(T + 1) + 7(7 + e, where the scheduling rate E TR4
small constant, and denotes the update iterations of the trainable parameters. We refer to the PI-GNN solver with this continuous relaxation annealing as CRA-PI-GNI solver. Here, two additional hyperparameters are introduced: the initial scheduling value 70) and the scheduling rate e. Numerical experiments suggest that better solutions are obtained when 70) set to small negative value and a kept low. The ablation study are presented in Appendix F55
4 Related Work
Previous works on UL-based solvers have addressed various problems, such as MaxCut problems Yao et al., 2019 and traveling salesman problems [Hudson et al. [021]. using carefully tailored problem- specific objectives. Some studies have also explored constraint satisfaction problems (Amizadeh et al.) 2018 Toenshoff et al. 2019], but applying these approaches to broader CO problems often requires problem-specifie reductions. Karalias and Loukas (2020) proposed Erdōs Goes Neural (EGN) solver, an UL-based solver for general CO problems based on Erdös' probabilistic method. This solver

---

generate solutions through an inference process using training instances. Subsequently, Wang et al. [022] proposed an entry-wise concave continuous relaxation, broadening the EGN solver to a wide range of CO problems. In contrast, SSchuetz et al. [202aa] b] proposed PI-GNN solver, an Ul--based solver for a single CO problems that automatically ly learns problem-specific heuristics during the training process. However, Angelini and Ricci- Tersenghi [223). [Boettcher] (2023) pointed out the optimization difficulties where PI-GNN solver failed to achieve results comparable to those of greedy algorithms. Wang and Li [2023] also claimed optimization issues with PI-GNN solver, emphasizing the importance of learning from training data and history to overcome local optima. They then proposed Meta-EGN solvers, a meta-learning approach that updates NN network parameters for individual CO problem instances. Furthermore, to address these optimization issue, [in et al. (2023), Sun et al. [022]. J. Sanokowski al. (2024) proposed annealing strategy similar to simulated annealing KKirkpatrick et al. 1983
5
Experiments
We begin by evaluating the performance of CRA-PI-GNN solver on the MIS and the MaxCut benchmark problems across multiple graphs of varying sizes, demonstrating that CRA effectively overcomes optimization challenges without relying on data/history 'D. We then extend the evaluation to the DBM problems, showing the applicability to more practical CO problems. For the objective functions and the detailed explanations, refer to Appendix E.I
5.1
Experimental settings
Baseline methods. In all experiments, the baseline methods include the PI-GNN solver (Schuetz
al. 2022a] as the direct baseline of UL-based solver for a single instance. For the MIS problems,
we also consider the random greedy algorithm (RGA) and DGA [Angelini and Ricci- Sesci-TTereene Tersenghi
2019] as heuristic baselines. For the MaxCut problems, RUN-CSP solver [Toenshoff et al. 2019 is considered as an additional baseline, and a standard greedy algorithm and SDP based approximation
algorithm [Goemans and Williamson 1995] are considered as an additional classical baseline. The
parameters for the Goemans- Williamson (GW) approximation are all set according to the settings in Schuetz et al. (202b)). The implementation used the open-source CVXOPT solver with CVXPY P as the modeling interface. Note that we do not consider UL-bbasd solvers for learning generalized
heuristics (Karalias and Loukas) 2020) Wang et al., [022] Wang and Li| 2023], which rely on training instances D = [C u=1 The primary objective of this study is to evaluate whether CRA-PI-GNN
solver can surpass the performance of both PI-GNN solver and greedy algorithms. However, for the
MIS problem, EGN solver (Karalias and Loukas 2020 and Meta-EGN solver [Wang and Li 2023
are considered to confirm that CRA can overcome the optimization issues without training instances.
The objective of the numerical experiments to compare the CRA-PI-GNN solver with the PI-GNN solver. Thus, we follow the same experimental configuration described as the experiments in [Shuetzz et al.] 2022a), employing a simple two-layer GCV and GraphSAGE (Hamilton
Implementation.
eet al. (017 implemented by the Deep Graph Library (Wang et al. 2019]; Refer to Appendix D. for the detailed architectures. We use the Adam [Kingma and Ba
2014 optimizer with learning
rate of = 10-1 and weight decay of 10-2 The GNNs are trained for up to 5 x 10' epochs with early stopping, which monitors the summarized loss function Σ i(P...) and the entropy term ((Pr,, a) with tolerance 10-5 and patience 10xs epochs; Further details are provided in Appendix D.2 We set the initial scheduling value to 7() = -20 for the MIS and matching problems, and we set (0) = -6 for the MaxCut problems with the scheduling rate 10 and curve rate 2 in Eq. 3.2 These values are not necessarily optimal, and refining these parameters can lead to better solutions: Refer to Appendix F.5 and Appendix F.6 for ablation study of these parameters. Once the training process is complete, we apply projection heuristics to map the obtained soft solutions back to discrete solutions using simple projection, where for all i E [N]. we map pa.; into if Pa.i < 0.5 and pa.; into 1 if po.: > 0.5. However, due to the early stopping in Section 3.2 the CRA-PI-GNN solver ensures that for all benchmark CO problems, the soft solution at the end of the training process became 0 or within the 32-bit Floating Point range in Pytorch GPU; thus, it is robust against a given threshold, which we set 0.5 in our experiments. Additionally, no violations
httpp:://gtthub..oo//bmmmms/ wwwp://sssss....pab.ob..a www.:owwwwaaaaaaaaaaaaaoaa. algorithms
7

---

15.0
16.0
12.3
CaL FALF-ihbl
12.5
10.0
1..00
Indeytadent
Degavo the KB0a wil. 10B0 aodes Degroo 0Z RRGs with 20.00 codos
Degros the RRGs with 10B0 audrs Doggze RB00 50 with 20.8 codes
Figure 2: Independent set density of the MIS problem on d-RRG. Results for graphs with N 10,000 nodes (Left) and N 20,000 nodes N 10,000 (Left) and N 20,000 (Right). (Right). the dashed lines represent the theoret- ical results [Barbier et al. 2013).
Cut ratio of the MaxCut problem d-RRG as a function of the degree Results for
Figure 3:
The dashed lines represents the theoretical upper bounds (Parisi 1980
Table I: ApR in MIS problems on RRGs with 10,000
x10
nodes and node degree 20, 100. "CRA" represents the CRA-PI-GNN solver.
CRA CNN (GCV) CRAPI-CNN
T N1
Solution Runtime (s)
0.7
Instance
Method
ApR
~ -
RGA
0.776 0.001
0.5
DGA
0.891 0.001
0.3
EGN
0.775 (2023)
20-RRG
META-EGN
0.887 (2023)
PI-GNN (GCV)
0.000 + 0.000
PI-GNN (SAGE)
0.745 0.003
0.1
CRA (GCV)
0.937 + 0.002
Number of Nodes (N)
x10
CRA (SAGE)
0.963 0.001
Figure 4: (Right) computational runtime (in seconds) of the CRA-PI-GNI solvers with the GraphSage and Conv architectures on 100- RRG with varying numbers of nodes N W.Error bars represent the standard deviations of the results.
RGA
0,663 + 0.001
DGA
0.848 0.002
PI-GNN (GCV)
0.000 + 0.000
100-RRG
PI-GNN (SAGE)
0.000 0.000
CRA (GCV)
0.855 + 0.004
CRA (SAGE)
0.924 + 0.001
of the constraints were observed in our numerical experiments. Thus, following results presented in are feasible solutions.
Evaluation metries. Following Karalias and Loukas 2020), We use the approximation ratio (ApR), formulated as ApR fæ; C)/ f(x"; C), where x is optimal solution. For the MIS problems, we evaluate the ApRs using the theoretical optimal cost [Barbier al. [013 and the independent set density relative to the theoretical results. For the MaxCut problems on RRGs,
adopt the cut ratio v against the theoretical upper bound [Parisi] 1980 Dembo et al.) 2017): see Appendix [E. for the details. All the results for the MIS and MaxCut problems are summarized based on RRGs with different random seeds. the case the MaxCut Gset problem, the ApR is calculated compared to the known best cost functions. Regarding the DBM problems, calculate the ApR against the global optimal, identified using Gurobi 10.0. solver with default settings.
5.2 MIS problems
Degree dependency of solutions using CRA. First, we compare the performance of the PI-GNN and CRA-PI-CA -I---P- solvers using GCV, as in Schuetz density Pa as function of degree d obtained by the PI-GNN and CRA-PI-GNN solvers compared with the theoretical results [Barbier al. 2013). Across degrees d, the CRA-PI-GNN solver outperformed the PI-GNN solver and approached the theoretical results, whereas the PI-GNN solver fail to find valid solutions, especially for 2 15, as pointed by the previous studies (Angelini and
[202aa]. Fig. 2 shows the independent set
Ricci-Tersenghi 2023
Wang and
2023
2023 MIS problems Response to Angelini and Ricci- Tercengerssnghi 2023] and Wang and Li
on RRGs with degree d larger than 16 known be hard problems Barbier et al.) 2013). As

---

discussed in Section 3.1 Angelini and Ricci- Tersenghi [203), Wang and Li [2023] have posted
the optimization concerns on UL-based solvers. However, we call these claim into question by
substantially outperforming heuristics DGA and RGA for the MIS on graphs with d = 20, 100, See Appendix (6 for the results of solving all other Gsets, where consistently, CRA-PI-GNN provides better results as well. A comparison of the sampling-base solvers, RL-based solvers, SL-based solvers, Gurobi, and MIS-specific solvers is presented in Appendix F2
without training/historical instances D = {G*} as shown in Table [
Acceleration of learning speed. We also compared the learning curve between PI-GNN and CRA-PI-GNN solver to confirmed that the CRA-PI-GNT
solver does not become trapped in the plateau, pv = ON, as discussed in Section 3.1 Fig. [] sishows the dynamics of the cost functions for the MIS problems with N 10,000 across d = 3, 5, 20, 100. Across all degrees, CRA-PI-GNN solver achieves a better solution with fewer epochs than PI-GNN solver. Specifically, PI-GNN solver becomes significantly slower due to getting trapped in the plateau even for graphs with low degrees, such as d = 3. 5. In contrast, CRA-PI- -I-GNN solver can effectively escape from plateaus through the smoothing and automatic rounding of the penalty term when the negative parameter 7 > 0.
Computational scaling. We next evaluate the computational scaling of the CRA-PI-GNN solver for MIS problems with large-scale RRGs with a node degree of 100 in Fig. 4 following
MIS BRR)
MIS C5 RRG)
40.2
2000
previous studies Schuetz et al. [202aa] Wang
Like 1is
1030
and Li 2023 Fig. 4 demonstrated moder- ate super-linear scaling of the total computa- tional time, approximately
NIS (INHUN
5006
MIB (1UD HUML)
4000
11. for GCN
and ~ N1.7 for GraphSage. This performance nearly identical to that of the PI-GNN solver [Schuetz et al.] [202a]] for problems on RRGs with lower degrees. It is important note that the runtimes of CRA-PI-GNN solver heavily depend on the optimizer for GNNs and anneal- ing rate e; thus this scaling remains largely un- changed for problems other than the MIS on 100 RRG. Additionally, CRA demonstrate that the runtime remains nearly constant as graph order and density increase, indicating effective scalability with denser graphs which is presented in Appendix F2
2000
10003
30000
3008
33000 33000
Figure 5: The dynamics of cost function for MIS problems on RRGs with N = 10,000 nodes vary- ing degrees d as function of the number of pa- rameters updates NEPOCH-
5.3 MaxCut problem
Degree dependency of solutions. We first compare the performances of PI-GNN and CRA-PI- GNN solvers with GCV, following Schuetz et al. [2022a] Fig. 3 shows the cut ratio 1/ function of the degree d compared to the theoretical upper bound Parisi 1980 Dembo et al. 2017]. Across all degrees d, CRA-PI-GNN solver also outperforms PI-GNN solver, approaching the theoretical upper bound. In contrast, PI-GNN solver fails to find valid solutions for d > 20 as with the case of the MIS problems in Section 5.2
Standard MaxCut benchmark test. Following Schuetz al. [202a]], we next conducted additional experiments on standard MaxCut benchmark instances based on the publicly available Gset dataset (Ye] 2003). which is commonly used to evaluate MaxCut algorithmss Here, we provide benchmark results for seven distinct graphs with thousands of nodes, including Erdös- Renyi graphs with uniform edge probability, graphs in which the connectivity decays gradually from node 1 to N, 4-regular toroidal graphs, and a very large Gset instance with N 10,000 nodes. Table 2 shows, across all problems, CRA-PI-GNN solver outperforms both the PI-GNN, RUN-CSP solvers and other greedy algorithm.
1.20
ApR
3.50
523450
9 1001112
Instance ID
ApR
3.50
3.90
PHONN
10::1222 415.11 20022202222000000
Instance ID
Figure 6: ApR on DBM problems.
9

---

Table 2: ApR for MaxCut on Gset
GRAPH
(NODES, EDGES)
GREEDY
SDP
RUN-CSP
PI-GNN
CRA
G14
(800, 4,694)
0.946
0.970
0.960
0.988
0.994
GI5
(800, 4,661)
0.939
0.958
0.960
0.980
0.992
G22
(2,000, 19,990)
0.923
0.77
0.975
0.987
0.998
G49
(3,000, 6,000)
1.000
1.000
1.000
0.986
1.000
G50
(3,000, 6,000)
1.000
1.000
1.000
0.990
1.000
G55
(5,000, 12,468)
0.892
0.982
0.983
0.991
G70
(10,000, 9,999)
0.886
0.970
0.982
0.992
See Appendix @ the results of solving all other Gsets, where CRA-PI-GNN consistently provides better results as well.
5.4 Diverse bipartite matching
To evaluate the applicability of the CRA-PI-GNN solver to more practical problems not on graphs. we conducted experiments on DBM problems [Ferber et al., 2020) Mulamba al. [020 Mandi et al.)
2022]; refer to Appendix[E.] E..1 for details. This problems consists of 27 distinct instances with varying properties, and each instance comprises 100 nodes representing scientific publications, divided into two groups of 50 nodes N1 and N2. The optimization is formulated as follows:
1(:; C, M, Eij Cajait A1 E, ReLU ES any - 12 ReLU (E -1)
+ *3RReLU [i (ApReLU(DE.f
Eij Mijais) + AaRLLL ( Ei Tis -
Mo)).as))
where C' E &N represents the likelihood of link between each pair of nodes, indicator Ma; set to article and j share the same subject field (1 otherwise) Vi N1, and j E 22. The parameters p, [0, 1] represent the probability of pairs sharing their field and of unrelated pairs, respectively. As in Mandi et al. [2022], we explore two variations of this problem, with p = q being 25% and 5%, respectively, and these variations
referred to Matching- I and Matching-2 respectively. In this experiment, we set Å = A2 = 10 and X3 da = 25. Fig 6 shows that the CRA-PI-GNN solver find better solutions across all instances.
6
Conclusion
This study proposes CRA strategy to address the both optimization and rounding issue in UL-based solvers. CRA strategy introduces penalty term that dynamically shifts from prioritizing continuous solutions, where the non-convexity of the objective function is effectively smoothed, to enforcing discreteness, thereby eliminating artificial rounding. Experimental results demonstrate that CRA-PI- GNN solver significantly outperforms PI-GNN solver and greedy algorithms across various complex CO problems, including MIS, MaxCut, and DBM problems. CRA approach not only enhances solution quality but also accelerates the learning process.
Limitation. In these numerical experiments, most hyperparameters were fixed to their default values, as outlined Section [5.]] with minimal tuning. However, tuning may be necessary for specific problems further enhance performance.
References
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: complexity. Courier Corporation, 1998.
algorithms and
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.052.0 2021.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.0122: 2019.
10

---

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.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning sat solver from single-bit supervision. arXiv preprint arXiv:
2018.
Elias Khalil, Pierre Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It' not what machines can learn, it' s what we cannot teach. In International conference on machine learning, pages 10831-10841. PMLR, 2020.
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, pages 242-251. SPIE, 2019.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems, 32, 2019.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: /6/ I. 1.09940, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 51 518(7540):529-533, 2015.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International conference on machine learning. pages 1407-1416. PMLR, 2018.
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, 2022a.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve eircuit-sat: unsupervised differentiable approach. In International Conference on Learning Representations, 2018.
Maria Chiara Angelini and Federico Ricci-Tersennhi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29-31, 2023.
11

---

Maria Chiara Angelini and Federico Ricci- Merci-Tersenhhi Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs. Physical Review E. 13003) 2019.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta-leaming. arXiv preprint arXiv:2301 10000010111111 16, 2023.
Alan J Hoffman and Joseph B Kruskal. Integral boundary points of convex polyhedra. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-AMe pages 49-76, 2010.
George Nemhauser and Leslie E Trotter Jr. Properties of vertex packing and independence system polyhedra. Mathematical programming. 6(1):48 61, 1974.
Martin JA Schuetz, J Kyle Brubaker, Zhihuai Zhu, and Helmut G Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):043131, 2022b.
Haoyu Peter 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:31444 31458, 2022.
László Lovász. On the shannon capacity of graph. IEEE Transactions on Information theory, 25(1): 1-7, 1979.
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Ulrike Von Luxburg. tutorial on spectral clustering. Statisties and computing, 17:395 416, 2007.
Alice Smith, David W Coit, Thomas Baeck, David Fogel, and Zbigniew Michalewicz. Penalty functions. Handbook of evolutionary computation, 97(1):C5, 1997.
Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
Haoran Sun, Etash K Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint arXiv:2207.11542, 2022.
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Variational annealing on graphs for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Run-csp: unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, 0tt//1999.08389 2019.
Stefan Boettcher. Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems. Nature Machine Intelligence, 5(1):24-25, 2023.
Xi Lin, Zhiyuan Yang, Xiaoyuan Zhang, and Qingfu Zhang. Continuation path learning for homotopy optimization. In International Conference on Machine Learning, pages 21288-21311. PMLR, 2023.
Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. science, 280,,59 1983.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.013. 19911199,,,,,,,. 2019.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
12

---

Jean Barbier, Florent Krzakala, Lenka Zdeborová, and Pan Zhang. The hard-core model on random graphs revisited. In Journal of Physies: Conference Series, volume 473, page 012021. IOP Publishing, 2013.
Giorgio Parisi. A sequence of approximated solutions to the sk model for spin glasses. Journal of Physics A: Mathematical and General, 13(4):L115, 1980.
Amir Dembo, Andrea Montanari, and Subhabrata Sen. Extremal cuts of sparse random graphs. 2017.
Y. Ye. The gset dataset. https://wwb..
stanf http://wbbsaaafrddeeee..
2003.
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2020.
Maxime Mulamba, Jayanta Mandi, Michelangelo Diligenti, Michele Lombardi, Victor Bucarey, and Tias Guns. Contrastive losses and solution caching for predict-and-optimize arXiv preprint arXiv:201 1.053544 2020.
Jayanta Mandi, Victor Bucarey, Maxime Mulamba Ke Tchomba, and Tias Guns. Decision-focused learning: through the lens of learning to rank. In International Conference on Machine Learning, pages
PMLR, 2022.
Mohsen Bayati, David Gamamii, and Prasad Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 105-114, 2010.
Amin Coja-Oghlan and Charilaos Efthymiou. On independent sets in random graphs. Random Structures & Algorithms, 47(3):436-48,, 2015.
Bahram Alidace, Gary A Kochenberger, and Ahmad Ahmadian. 0-1 quadratic programming approach for optimum solutions of two scheduling problems. International Journal of Systems Science, 25 (2):401-408) 1994.
Hartmut Neven, Geordie Rose, and William G Macready. Image recognition with an adiabatic quantum computer mapping to quadratic unconstrained binary optimization. arXiv preprint arXiv:0804.4455 2008
Michel Deza and Monique Laurent. Applications of cut polyhedra -i. Journal of Computational and Applied Mathematics, 55(2):217-247 1994.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93-93, 2008
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1272. PMLR, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems 35, 2022.
Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning, pages 32859-32874. PMLR, 2023.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Grathwohl. Dale Schuurmans, and Hanjun Dai. Discs: A benchmark for discrete sampling, In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 79035-79066. Curran Associates, Inc., 2023. URL https: httpps://proceedingg neurips cc paper happpprrrrllle___eeeppppeeeeeeee wwwes//ppeeee/////0 19ad87 BaatlrrccceaaaSaaaaacccccct. Paper Patterrratssaetpee-aattttttt and Ben pdf
Holger H Hoos and Thomas Stützle, Satlib: An online resource for research on sat. Sat, 2000: 283-292, 2000.
13

---

A Overview
This supplementary material provides extended explanations, implementation details, and additional results.
B Derivation
B.1 Proof of Theorem 3.1
First, we present three lemmas, and then we demonstrate Theorem 3.1 based on these lemmas.
Lemma B.1. For any even natural number a {2n n E N+ the function o(p) 1- (2p 1)
defined on [0, 1] achieves its maximum value of 1 when p = 1/2 and its minimun value of 0 when p or
Proof. The derivative of p(p) relative to do(r\/dp 2a 1), which zero when p = 1/2. This is point where the function is maximized because the second derivative d'dlp/dpp -4a S 0. In addition, this function is concave and symmetric relative to p = 1/2 because a is an even natural number, i.e.,
Φ(p) o01 p). thereby achieving its minimum value of 0 when 0 or p 1. O
Lemma B.2. For any natural number {2n N+). +00 minimizing the penalty
term 7b(p) = ? Σi= (1 (2p: - 1))) = =E (p:)) enforces that the for all E [N], ps is either or and, if 7 oo, the penalty term enforces p = 1x/2.
Proof. From Lemma B.I as 7 + +o0, p(p) is minimal value when, for any i E [W]. p: 0 or P: As + - -C, Up, a, 7) is minimal value when, for any [N], = 1/2.
Lemma B.3. For any even number a {2n E N+ pP(p) is concave when X > 0 and is foncetfunction when X < O.
(2p; 1)a) is separable across its com- ponents P.. Thus, sufficient to prove that each 70: (p:; a concave or convex in ps because the sum of the concave convex functions is also concave (and vice versa). Thus, we consider the second derivative of (p:) with respect to p::
Proof. Note that pp(p) - >>> > = (1 7
d (p)( 470. dp
If > O, the second derivative is negative for all ps e [o, 1). and this completes the proof that > a concave function when y is positive (and vice versa).
Combining Lemma B.I Lemma B.2 and Lemma B.3 one show the following theorem.
Theorem B.4. Under the assumption that the objective function i(p; C`) is bounded within the domain [0, 1) as > +0, the soft solutions p" E argmin, ((p: C, x,,,)) converge to the original solutions xx E argminn.!(x: C, A). In addition, as y - -00, the loss function f(p: C, C, becomes convex, fariiinfppp.
and the soft solution 1w/2 argmin f(p. C, 2. 7) is unique.
Proof. As A + +00, the penalty term (pp) dominates the loss function f(p; C, X, 7). According to Lemma B.2 this penalty term forces the optimal solution p" to binary vector whose components, because any non-binary value results in an infinitely large
for all [ P that are either penalty. This effectively restricts the feasible region to the vertices of the unit hypercube, which correspond to the binary vector {0, 11 Thus, as - co, the solutions to the relaxed problem converge to those of the original problem. As -c,, the penalty term Φ(p) also dominates the loss function fp: C, X, 7) and the i(p: C) convex function from Lemma B.3 According to
Lemma B.2 this penalty term forces the optimal solution p" 1x/2.
14

---

The theorem holds for the cross entropy penalty given by
N
+ (p))
(p: log(p:) + (00-pp))lp log(1 -p:))
the UL-based solver using data or history Sun et al. 2022 Sanokowski et al. 2024 because & (p)
can similarly satisfy Lemma B.1 Lemma B.2 and Lemma B.3
Corollary B.5. Theorem B.4 holds for the following penalty term:
((p) Σ (p.log(pi) + (1- p.) log(1 - pi))
C
Generalization of CRA
C.1
Generalization for to Potts variable optimization
This section generalize the penalty term ((0; C) introduced for binary variables to K K-Potts variables.
K-Potts variable is the Kronecker delta 6(2,, 22) which equas one whenever 2ạ = 2j and zero otherwise and a decision variable takes on K different values, Vi [N], I; 1,... K. For example, graph K-colloiig problems can be expressed as
(w; G(V, E))
Σ 8(11, 25)= (1,))E
For Potts variables, the output of the GNN is h = P(O: E R N.k and the penalty term can be generalized follows:
( C)
Σ (KP, (KP),(0;))-1))
D Additional implementation details
D.1 Architecture of GNNs
We describe the details of the GNN architectures used in all numerical experiments. The first convolutional layer takes Ho-dimensional node embedding vectors, h2 for each node, as input, yielding Hi-dimensional feature vectors hj. Then, the ReLUU function is applied wise nonlincar transformation. The second convolutional layer takes the Hi H1-dimensional feature vectors, hg. as input, producing a (2) dimenniinll vector h2. Finally, sigmoid function is applied to the dimeeeiimlll vector h2g and the output is the soft solution pa E [0, 1 As in (Schuetz ctt al. 2022a]. we set Ho = int( or H1 = int (2) and H² = for both GCN and GraphSAGE.
component-
D.2 Training settings
For all numerical experiments, we use the AdamW [Kingma and Ba 2014 optimizer with learning rate of 10-1 and weight decay of 10-2, and we train the GNNs for up to 10 epochs with early stopping set to the absolute tolerance 10-5 and patience 103. As discussed in Schuetz et al. [2022a] the GNNs are initialized with five different random seeds for a single instance because the results are dependent on the initial values of the trainable parameters; thus selecting the best solution.
E Experiment details
E.1 Benchmark problems
MIS problems. There are some theoretical results for MIS problems on RRGs with the node degree set to d, where each node is connected to exactly other nodes. The MIS problem is
15

---

2010] defined as follows. Given an undirected graph G(V, E), an independent set (IS) a subset of nodes I V where any two nodes in the set are not adjacent. The MIS problem attempts to find the largest IS, which is denoted T". In this study, p denotes the IS density, where p = [V]. To formulate the problem, a binary variable I, assigned each node i E V. Then the MIS problem is formulated as follows:
fundamental NP-hard problem [Karp
f(æ; G, -
Σ x4 C
Σ プز
iEV
(S.)EE
where the first term attempts to maximize the number of nodes assigned 1, and the second term penalizes the adjacent nodes marked 1 according to the penalty parameter A. In our numerical experiments, we set 2. following followingScchuttz
al. [2022a], no violation is observed as in [Schuetz iet al. 2022a]. First, for every d, specifiic value Pa. which is dependent on only the degree d, exists such that the independent set density [/V] converges to p with high probability as N approaches infinity (Bayati et al.] 2010]. Second, statistical mechanical analysis provides the typical MIS density Pd undergoes a clustering transition, which Is associated with hardness in sampling [Barbier et al. [013] because the clustering is likely to create relevant barriers that affect any algorithm searching for the MIS It, Finally, the hardness is supported by analytical results in a large d limit, which indicates that, while the maximum independent set density is known to have density P 2 log(d)/ /d, to the best of our knowledge, there is no known algorithm that can find an independent set density exceeding Pa-+oo = log(d)/ [Coja-Oghlan and Efthymiou 2015).
Theory, as shown in Fig. 2 and we clarify that for d > 16, the solution space of I
MaxCut problems. The MaxCut problem is also a fundamental NP-hard problem KKrrp) 2010 with practical application in machine scheduling [Alidaee et al. 1994), image recognition Neven
eet al. 2008) and electronic circuit layout design [eza and Laurent. 1994] The MaxCut problem is also a fundamental NP-hard problem [Karp] 2010] Given an graph = (V, E), a cut set C E E is defined as subset of the edge set between the node sets dividing (V1, V/2 V1VV2
V,, VinV, 0). The MaxCut problems aim to find the maximum cut set, denoted C*, Here, the cut ratio is defined as = CC///// where (C] is the cardinality of the cut set. To formulate this problem, each node is assigned a binary variable, where I; = 1 indicates that node belongs to V1, and x; = 0 indicates that the node belongs to V22 Here, I2 + 23 20,r, holds if the edge (i, E C. As result, we obtain the following:
f(x: G)= Σ (22,z zzz).
xz).
This study has also focused on the MaxCut problems on d-RRGs, for which several theoretical results have been established. Specifically, for each d, the maximum cut ratio is given by V/ s d/4+ P. /d O(vd), where P. 0.7632... with a high probability as N approaches infinity Parisi 1980 Dembo et al. 2017]. Thus, we take o = d/4+ Ps /./d/ d/4 as an upper bound for the maximum cut ratio in the large n limit.
DBM problems. Here, the topologies are taken from the Cora citation network (Sen et al., 2008). where each node has 1,433 bag-of-words features, and each edge represents likelihood, as predicted by a machine learning model. Mandi et al. [2022] focused on disjoint topologies within the given topology, and they created 27 distinct instances with varying properties. Each instance comprises 100 nodes representing scientific publications, divided into two groups of 50 nodes N1 and N2. The optimization task is to find the maximum matching, where diversity constraints ensure connections among papers in the same field and between papers of different fields. This is formulated using a penalty method as follows.
Tij - I(x; M, = Eij Cijaiy + A1 E, ReLU ReLU E5
11 + d2 E, ReLUU rij (E,
Myjuy) + RRRLLU q D., E T.y - Ei, -., (p (ooReLUpDI,,
+ +XgReLU
where C' e Mix represents the likelihood of link between each pair of nodes, an indicator Mig is set to 0 if article i and j share the same subject field (1 otherwise) Vi E N1, and j E N2. The parameters p, E [0, 1] represent the probability of pairs sharing their field and of unrelated pairs, respectively. As in Mandi et al. 2202], we explore two variations of this problem, with p = 4 being 25% and 5% respectively, and these variations are referred to as Matching- and Matching-2,
respectively. In this experiment, we set λ₁ X2 10 and X b4 = 25.
16

---

E.2 GNNs
GNN [Gilmer et al. 2017 Scarselli et al., 2008 is specialized neural network for representation learning of graph-structure data. GNNs learn a vectorial representation of each node in two steps, i.., the aggregate and combine steps. The aggregate step employs a crrmuuaaionninvaiiann function to generate an aggregated node feature, and in the combine step, the aggregated node feature is passed through a trainable layer to generate a node embedding, known as "message passing" or the "readout phase." Formally, for given graph G = (V, E), where each node feature hg E To is attached to each node E V, the GNN updates the following two steps iteratively. First, the aggregate step at each (-th layer is defined as follows:
a Aggregated (fh Vu E Noo)).
where the neighborhood of v E V is denoted N₁ {u E V (v, u) E E), h is the node feature of the neighborhood, and at, is the aggregated node feature of the neighborhood. Then, the combined step at each I-th layer is defined as follows:
h = Combine (h',) ..a)):
where h. E Hi denotes the node representation at the 1-th layer. Here, the hyperparameters for the total number of layers L and the intermediate vector dimension N' are determined empirically, Although numerous implementations of GNN architectures have been proposed to date, the most basic and widely used architecture is the GCN [Scarselli et 2008), which is given as follows:
h [(x]] + B'ht'1
h
W Σ
(EN(()
where W and B' are trainable parameters, [W()] serves as normalization factor, and or : R + Rd is some component-wise nonlinear activation function, e.g., the sigmoid ReLU function.
F
Additional experiments
F.
Numerical validation of practical issues presented in Section 3.1
In this sectioin, we will examine the issue (l) with continuous relaxations and the issue (II), the difficulties of optimization, as pointed out by previous studies [Wang and Li 2023 Angelini and Ricci-Terseenhii 2023). in the NP-hard problems of MIS and the MaxCut problem. Therefere, conducted numerical experiments using the PI-GNN solver for MIS and MaxCut problems on RRGs with higher degrees. To ensure the experimental impartiality, we adhered to the original settings of the PI-GNN solver (Schuetz et al. 2022b.. Refer to Section for the detailed experimental settings. Fig. 7 (top) shows the solutions obtained by the PI-GNN solver as a function of the degree d for the MIS and MaxCut problems with varying system sizes N. These results indicate that finding independent and cut sets becomes unfeasible as the RRG becomes denser. In addition, to clarify the reasons for these failures, we analyzed the dynamics of the cost function for MIS problems with N 10,000, with specific focus on a graph with degrees d = and d = 20, as depicted in Fig. 7 (bottom). For the = 5 case, the cost function goes over the plateau of i(0; G, A) = with CC ON, investigated in the histogram, eventually yielding solution comparable to those presented by [Schuetz et al. [2022a]. Conversely, in the d = 20 case, the cost function remains stagnant on the plateau of 1(0: G, A) = O with (G) = ON, thereby failing to find any independent nodes. Interpreting this phenomenon, we hypothesize that the representation capacity of the GNN sufficiently large, leading to consider the optimization of Lans (0: ;0; G, A) and LMaxCut (0; G) as a variational optimization problem relative to pa. In this case, P7 = ON satisfies the first-order
variational optimality conditions 6iMIs/ /opo pa=p' Ml /8po p==p" O,v, which implics potential reason for absorption into the plateau. However, this does not reveal the conditions for the convergence to the fixed point p' during the early learning stage the condition to escape from the fixed point p". Thus, an extensive theoretical evaluation through stability analysis remains an important topic for future work.
In summary, Ul-based solver, minimizing 0 can be challenging and unstable. In particular, the PI-GNN solver, which is one of the UL-based solvers employing GNNs, fails to optimize 0 due to
17

---

x1.0
2505
1.2
250
Inde pendent Set Size (2))
N=
N= 500
N500
N=7500
N- 10000
N- 10000
12500
Cut. Set, Size
0.8
12500
N500
Na 15000
N= 17500
0.6
N= 11900
Nw20000
20000
0.2
20
0.40
30
Degree of each node (d)
Degrse
each node (d)
1.5 K10
100 Epoch
2500 Epach
7000 Epock
15000 Epock
5
10
10
1.0
d= 20
10: G.A)
0.0
660
0.0
100 Epuch
2500 Epuch
Spocks
15000 Eyoch
20
20
20
0.0
18
10
10
-0.5 0.
6.0 6.0
NgFOOH
Figure 7: The top graph shows the independent set density for MIS problems (left) and the cut ratio for MaxCut problems (right) as a function of degree using the PI-GNN solver with varying system size N. Each data point represents the average result of five different graph instances, with the error bars indicating the standard deviation of those results. The bottom graph shows the cost as a function of the number of parameter updates NEPOCH, for N = 10000 MIS problems on 5-RRG and 20-RRG. The histogram represents the relaxed vector distribution with varying numbers of parameter updates NEPOCH- Each point in the bottom-left plot is linked to the corresponding bottom-right histogram.
local solution in complex CO problems on relatively dense graphs where the performance of greedy algorithms worsens. This issues can be potential bottleneck for more practical and relatively dense problems, making it challenging to employ the PI-GNN solver confidently.
F.2 Additional results of MIS
We evaluate our method using the MIS benchmark dataset from recent studies [ooshvadi et al. 2023 Qiu al. 2022]. which includes graphs from SATLIB (Hoos and Stützle, 2000) and Hrdös Rényi graphs (ERGs) of varying sizes. Following [Sun et al. [2023]. our test set consists of 500 SATLIB graphs, each containing between 403 and 449 clauses with up 1,347 nodes and 5,978 edges, 128 ERGs with 700 to 800 nodes each, and 16 ERGs with 9,000 to 11,000 nodes each. We conducted numerical experiments on PQQA using four different configurations: parallel runs with S = 100 or S = 1000 and shorter steps (3000 steps) or longer steps (30000 steps), similar to the approach in iScO (Sun et al. 2023]. Table F2 presents the solution quality and runtime results. The results show that CRA, which optimizes the relaxed variables as an optimization of GNN parameters, takes extra time for smaller ER-[700-800] instances due to the smaller number of decision variables. However, for larger instances, CRA achieves results comparable to iSCO. Although limited space makes it difficult to present other benchmark results employed by iSCO, such as MaxCut and MaxClique, numerical experiments on these benchmarks also show that CRA is less effective for small problems. However, for larger problems, the results are comparable to or slightly inferior to those iScO.
F.2
We also investigated the relationship between the order of the graph and the solving time of the solver, and the results are shown in Table F2 and F2 The results demonstrate that the runtime remains nearly constant as graph order and density increase, indicating effective scalability with denser graphs
F.3 Additional results of Gset
We conducted experiments across the additional GSET collection to further validate that including CRA enhances PI-GNN results beyond previously achievable in Table 6
18

---

Table 3: ApR and runtime are evaluated on three benchmarks provided by DIMES (Qiu et al. 2022 The ApR is assessed relative to the results obtained by KaMIS. Runtime is reported the total clock time, denoted in seconds (s), minutes (m), or hours (h). The runtime and solution quality are sourced from iSCO [Sun al. 2023]. The baselines include solvers from the Operations Research (OR) community, as well as data data-driven approaches utilizing Reinforcement Learning (RL), Supervised Learning (SL) combined with Tree Search (TS), Greedy decoding (G), or sampling (S). Methods that fail to produce results within 10 times the time limit of DIMES are marked as N/A.
FR-[700-800)
ER-[9000- 11000)
Method
Type
ApR
Time
ApR
Time
KaMIS
OR
1.000
52. 13m
1.000
7.6h
Gurobi
OR
0.922
50.00m
N/A
N/A
SL+TS
0.865
20.00m
N/A
N/A
Intel
SL+G
0.777
6.06m
0.746
5.02m
DGL
SL+TS
0.830
22.71m
N/A
N/A
LwD
RL+S
0.918
6.33m
0.907
7.56m
RL+G
0.852
6. m.
0.841
5.21m
DIMES
RL+S
0.937
12.01m
0.873
12.51m
fewer steps more steps
0.998
1.38m
0.990
9.38m
iSCO
1.006
5.56m
1.008
1,25h
CRA
UL-based
0.928
47.30m
0.963
1.03h
Table 4: ApR of the MIS problem on (R, d). All the results are averaged based on 5 RRGs
with different random seeds.
Problem
ApR (CRA)
ApR (PI)
Time (CRA)
Time (PI)
RRG(11000) 10)
0.95
0.78
108 (s)
98 (s)
RRG(1,000, 20)
0.95
0.56
103 (S)
92 (S)
RRG[[1,000,30
0.94
0.00
102 (s)
88 (s)
RRG 40)
0.93
0.00
101 (S)
82 (S)
RRG 50)
0.92
0.00
102 (s)
82 (S)
RRG(1,000, 60)
0.91
0.00
101 (S)
91 (S)
RRG 70)
0.91
0.00
101 (s)
86
RRG
0.91
0.00
102
93 (s)
RRG(5,000, 10)
0.93
0.77
436 (s)
287 (s)
RRG(5,000,
0.95
0.74
413
280
RRG(5,000,30)
0.95
0.00
(1)
(8)
RRG 40)
0.94
0.00
429 (8)
(9)
RRG((5000,50)
0.94
0.00
418 (s)
324
RRG
0.93
0.00
321 (S)
302 (S)
RRG(5,000, 70)
0.92
0.00
321 (s)
325
RRG 80)
0.92
0.00
330 (S)
305 (S)
F.4 Additional results of TSP
We conducted additional experiments on several TSP problems from the TSPLIB datase presenting results that illustrate the a-dependency.
Experiments calculated the ApR as the ratio of the optimal value to the CRA result, with the ApR representing the average and standard deviation over 3 seeds. The "_" symbol in PI-GNN denotes cases where most variables are continuous values and where no solution satisfying the constraint was found within the maximum number of epochs. The same GNN and optimizer settings were used in the main text experiments in Section 5.1
http://comopt.ct ifi uni- mmi-heidelberg htaag//////ottwae//sPPL..SS.
19

---

Table 5: The ApR of the MIS problem ERG(N, d) is evaluated against the results of KaMIS. Due to time limitations, the maximum running time for KaMIS was constrained. The results below present the average ApRs and runtimes across five different random seeds.
Problem
CRA (ApR)
Pl (ApR)
Time (CRA)
Time (PI)
Time (KaMIS)
ERG(11000,0000 0.05)
0.97
0.01
103 (S)
98
100 (s)
ERG(11000,0.10)
0.95
0,00
100 (S)
98 (s)
210 (s)
ERG
0.94
0.00
100 (S)
92
315 (S)
(RG(,,,00,00200
0.91
0,00
99
88 (s)
557 (s)
ERG 0.25)
0.93
0.00
(8)
82 (s)
733 (s)
ERG((1000, 0.30)
0.90
0.00
(8)
82 (8)
1000 (8)
ERG(1,000, 0.35)
0.92
0.00
99 (8)
91 (8)
1000 (S)
ERG((1000, 0.40)
0.91
0.00
97 (8)
86 (s)
1000 (8)
SAGE
GCV
0-
0.07
Initial Value (y()))
Initial Value (y(0))
-5
0.06
Podepent enl Set Densin by
0.05
-10
0.04
-55
-15
0.03
-00
-20
0.02
-5
-25
0.01
-30
1x Scheduling Rate (e)
5x
1x10-
-30
1x10
5x10
1x10-
0.00
Scheduling Rate (e)
Figure 8: (Top) IS density of N 10,000 MIS problems 100-RRG a function of initial scheduling 7(0) and scheduling rate s values obtained by the CRA-PI-GNN solver using GraphSage (Left) and GCV (Right). The color of the heat map represents the average IS over five different instances.
Table F.4 shows that the CRA approach yielded solutions with an ApR exceeding 0.9 across various instances. Notably, for the burmal4 problem, our method identified the global optimal solution (3,323) multiple times. However, the optimal value can vary based on the specific GNN architecture and problem structure, indicating that more comprehensive ablation study could provide valuable insights in future work.
F.5 Ablation over initial scheduling value and scheduling rate
We conducted an ablation study focusing on the initial scheduling value (0) and scheduling rate This numerical experiment
conducted under the configuration described in Section 5 and E Fig. S shows the IS density of N 10000 MIS problems on 100-RRG as a function of the initial scheduling value (0) and the scheduling rate using the CRA-PI-GNT with both GraphSage and GCV. As can be seen, smaller initial scheduling (0) and scheduling rate values typically yield better solutions. However, the convergence time increases progressively the initial scheduling (0) and scheduling rate values become smaller. In addition, GraphSage consistently produces better solutions with relatively larger initial scheduling (0) and scheduling rate values, which implies that the GNN architecture influences both the solution quality and the effective regions the initial scheduling (0) and scheduling rate values for the annealing process.
F.6 Ablation over curve rate
Next, we investigated the effect of varying the curvature in Eq. 3.2 Numerical experiments were performed on MIS problems with 10,000 nodes and the degrees 5 and 20, as well as MaxCut problems with 10, 0000 nodes and the degrees of 5 and 35. The GraphSAGE architecture employed,
20

---

Table 6: ApR for MaxCut on Gset
GRAPH
(NODES, EDGES)
GREEDY
SDP
RUN-CSP
PI-GNN
CRA
G1
(800, 19,176)
0.942
0.970
0.979
0.978
1.000
G2
(800, 19,176)
0.951
0.970
0.981
0.976
0.998
G3
(800, 19,176)
0.945
0.972
0.982
0.972
1.000
G4
(800, 19,176)
0.949
0.971
0.980
0.978
0.999
G5
(800, 19,176)
0.949
0.970
0.980
0.978
1.000
G14
(800, 4,694)
0.946
0.952
0.956
0.988
0.994
GIS
(800, 4,661)
0.939
0.958
0.952
0.980
0.992
G16
(800, 4,672)
0.948
0.958
0.953
0.965
0.990
G17
(800, 4,667)
0.946
0.956
0.967
0.990
G22
19,999
0.923
0.972
0.987
0.998
G23
(2,000, 19,990)
0.927
0.973
0.968
0.997
G24
(2,000, 19,990)
0.927
0.973
0.959
0.998
G25
(2,000,
0.929
0.974
0.974
0.998
G26
(2,000, 19,990)
0.924
0.974
0.965
0.998
G35
(2,000, 11,778)
0.942
0.953
0.968
0.990
G36
(2,000, 11,766)
0.942
0.953
0.966
0.991
G37
(2,000, 11,785)
0.946
0.950
0.966
0.997
G38
(2,000, 11.779)
0.943
0.949
0.966
0 0.991
G43
(1,000, 9,990)
0.928
0.968
0.976
0.966
0.995
G44
(1,000, 9,990)
0.920
0.955
0.978
0.968
0.998
G45
(1,000, 9,990)
0.930
0.950
0.979
0.961
0.998
G46
(1,000, 9,990)
0.930
0.960
0.976
0.974
0.998
G47
(1,000, 9,990)
0.931
0.956
0.976
0.972
0.997
G48
(3,000, 6,000)
1.000
1.000
1.000
0.912
1.000
G49
(3,000, 6,000)
1.000
1.000
1.000
0.986
1.000
G50
(3,000, 6,000)
1.000
1.000
0.999
0.990
1.000
G51
1,9000.59909
0.949
0.960
0.954
0.964
0.991
G52
(1,000, 5,916)
0.944
0.957
0.955
0.961
0.990
G53
(1,000, 5,914)
0.945
0.956
0.950
0.966
0.992
G54
(1,000, 5,916)
0.900
0.956
0.952
0.970
0.988
G55
(5,000, 12,498)
0.892
0.978
0.983
0.991
G58
(5,000, 29,570)
0.945
0.980
0.966
0.989
G60
(7,000, 17,148)
0.889
0.980
0.945
0.991
G63
(7,000, 41,459)
0.948
0.947
0.968
0.989
G70
(10,000, 9,999)
0.886
0.970
0.982
0.992
Table 7: Comparison of ApR performance across different values of for various TSPLIB instances.
burmal4 14
ulysses22
st70
gr96
ApR (p 2)
0.91 0.08
0.89 = 0.03
0.96 + 0.01
0.81 + 0.05
ApR (p = 4)
0.98 = 0.10
0.92 - 0.02
0.85 + 0.03
0.82 = 0.03
ApR (p 6)
0.97 = 0.14
0.88 = 0.07
0.88 # 0.04
0.90 0.05
ApR (p 8)
0.99 = 0.06
0.89 + 0.05
0.80 + 0.02
0.86 + 0.05
ApR (PI)
0.736 1.21
Optimum
3,323
7,013
675
5,5209
with other parameters set as Section adn As shown in Fig. yielded the best scores across these problems.
we observed that 2 consistently
21

---

Independent. density (pd)
10
MAXCUT (d-5)
MAXCUT
0.3
Cut Ratio (6x)
0.2
0.1
MIS (d-
0.0
MIS (d=
2
10
12
4
6
10
Curve rate (a)
Curve rate (a)
Figure 9: (Left) Independent density as a function of curveture rate a in Eq. (3. (Right) Cut
ratio as a function of curveture rate a in Eq. (3.2). Error bars represent the standard deviations of the results
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction clearly state the main claims of the paper, including the advantages of the proposed CRA strategy over greedy algorithm without training dataset and the experimental results demonstrating its effectiveness.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses the limitations of the existing UL-based solvers, including optimization and rounding issues. It also mentions the limitations of the proposed CRA strategy, such as the need for parameter tuning and the reliance on specific graph structures for testing.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
22

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
The paper provides a full set assumptions and complete proof' the theoretical results presented, particularly for Theorem 3.1 and its supporting lemmas in Appendix B
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
The paper includes detailed descriptions of the experimental setups, including the types of graphs used, the parameters for the algorithms, and the performance metrics. This information sufficient for reproducing the main experimental results (Section 5 and Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
23

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: This paper is accompanied by the code, along with detailed instructions to reproduce the experimental results. This will ensure that other researchers can faithfully reproduce the findings reported in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https http://giideee/eeeeeeeeeeeeeeeee
/ //nips wwwpcccppppcpuooccceccocc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
24

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
The paper specifies all the necessary details about the experimental settings, including data splits, hyperparameters, optimizer types, and training procedures (Section and Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars and provides information about the statistical sig- nificance of the experimental results, including confidence intervals and standard deviations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The paper provides information on the computational resources used, including
the type of compute workers (e.g., GPU) Appendix E
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
25

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics ftctpa://neuriig httppp/s..pppppcccctiiiiceeeeeee inee
Answer: [Yes]
Justification: The research conforms to the NeurlPS Code of Ethics, ensuring responsible conduct and consideration of ethical implications.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses the potential positive impacts of the proposed CRA strategy, such as improving the efficiency of solving CO problems, as well as the potential negative impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
26

---

Justification:
The paper does not involve the release of high-risk data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The paper does not use any existing assets, so this question is not applicable.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasete has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
27

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "lMxD1L8eMK", "reviewer": "Reviewer_fKtw", "summary": "This paper presents a heuristic method for producing solutions to combinatorial optimization problems, which is based around solving a continuous relaxation of the problem. The main focus of the paper is on an additional penalty term to add to the objective of this relaxation which aims to reward solutions that are closer to satisfying the integrality constraints on the decision variables.", "questions": "The main contribution of the paper is an additional penalization term to induce solutions that are feasible w.r.t. the binary constraints on the decision variables, but I do not see explicit discussion in the Experiments section about the feasibility of the solutions produced (wr.t. both the integrality constraints and the other equality/inequality constraints). Are all of the solutions used in the computational study feasible for the \"true\" problem? If there are numerical tolerances used to \"fudge\" exact feasibility, what are these tolerance values?", "limitations": "N/A", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The computational study seems relatively comprehensive in that it studies a number of different problem settings in a fair amount of detail.", "weaknesses": "The paper is very dense and hard to follow, with little context provided to the reader. The method presented and evaluated in the computational study is ultimately an extension of the \"PI-GNN\" solver, but this fact is oddly kind of buried, with only an indirect reference in the introduction (\"the solver that applies the CRA to the PI-GNN solver is referred to as the CRA-PI-GNN solver\", with no indication that this is a main takeaway from the work), and then again at the end of Section 3.2. The paper does not explain in detail or formality what the PI-GNN solver is or how it works (how, specifically, does the CGA actually hook into PI-GNN?), and so a reader without prior familiarity cannot really understand or assess the new contributions laid out in Section 3. Ultimately, I do not feel confident that I can understand, and thus evaluate, the contributions proposed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and thoughtful review. We appreciate the time and effort you have invested in providing valuable feedback.\n\n**Understanding Difficult Sections:**\nThank you for your insightful feedback and for pointing out the areas that need clarification. \nWe understand the importance of addressing any difficulties you encountered while reading our paper. After introducing combinatorial optimization and continuous relaxation methods, Section 2.1 explains UL-based solvers, categorizing them into Type I (line 127) and Type II (line 138), explicitly stating that PI-GNN is Type II. Lines 149-151 explicitly state that this paper focuses on Type II UL-based solvers, specifically PI-GNN. Furthermore, Section 3.2 explains how CRA integrates into Type II UL-based solvers and why it is effective.\nAdditionally, we have shared all the relevant codes for review to support our explanations further. Appendix E2 provides a detailed explanation of GNN, enhancing our understanding of its role and implementation within our framework. Please specify the exact parts that remain unclear. We would greatly appreciate detailed pointers to enhance our revisions and ensure our explanations are as clear and comprehensive as possible.\n\n**Question:**\nThank you for pointing out, \"I do not see explicit discussion in the Experiments section about the feasibility of the solutions produced.\" \nThis comment is invaluable in improving the clarity of our presentation.\nThe Experiments section needs to discuss the feasibility of the solutions and binary constraints more explicitly. \nAs stated in lines 234-236, \nthe annealing is performed until $\\Phi(\\theta; C) \\approx 0$ for all numerical experiments. \nAccordingly, after the annealing, the values of the relaxed decision variables $p_{\\theta}(C)$ became 0 or 1 within the 32-bit Floating Point range in Pytorch GPU. \nAdditionally, as stated in lines 597-599, no violations of the constraints were observed in our numerical experiments. \nThus, all results presented in Section 5 (Experiments) are feasible solutions.\nHowever, this have needed to be clarified in Section 5 (Experiments). \nConsidering your comment, we will ensure that these clarifications are explicitly stated in the revised version's main text. \n\nConsidering our responses, we kindly request you to reconsider your score. Additionally, please let us know if any specific parts remain difficult to understand.", "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": "", "extra_scores": {}}, {"review_id": "x9M5ZRQCV6", "reviewer": "Reviewer_qMFs", "summary": "This paper aims to tackle shortcomings of the existing unsupervised learning-based solvers for combinatorial optimization, namely the local optima issue and the rounding issue. It proposes a novel technique called continuous relaxation annealing (CRA) strategy which introduces an additional penalty term to smooth the non-convexity of the objective function. This strategy is empirically shown to not only enhance the solution quality but also accelerate the learning process.", "questions": "N/A", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is an interesting study on the unsupervised-learning based approaches on CO problems. The proposed method is simple but proves to be quite effective.\n2. The empirical evaluation shows that CRA achieves a consistent improvement over PI-GNN \n3. The authors have conducted extensive qualitative and quantitative analysis to help understand the proposed method", "weaknesses": "1. My main concern lies in the technical contribution from this paper. The whole framework and empirical evaluation is built upon PI-GNN, which makes the observation and conclusion from this paper not generalizable.\n2. I feel the research from this paper is kind of out-of-date. Check https://openreview.net/forum?id=ZMP0Bki9aK for SOTA results on the CO problems considered in this paper. In fact, [1] also mention that simulated annealing would perform better than GNN, but only greedy methods are used as baselines.\n\n\n[1] Maria Chiara Angelini and Federico Ricci-Tersenghi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29–31, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper; we appreciate your recognition of the simplicity and effectiveness of our proposed method, the consistent improvement of CRA over PI-GNN, and the extensive qualitative and quantitative analysis. \n\n**Weakness (Contribution):**\nPlease refer to \"Main Contribution and Novelty\" of the Unified Response for a detailed explanation of our contributions.\n\n**Weaknesss (Comparison with SOTA):**\nPlease refer to the \"Numerical Experiments\" section of the Unified Response for a comprehensive discussion.\n\n**Regarding Paper [1]:**\nYou referenced the paper [1] by Angelini and Ricci-Tersenghi, which reports results for regular random graph problems ($d=3$ and $d=5$) with $\\mathrm{ApR}(d=3)=0.984$ and $\\mathrm{ApR}(d=5)=0.981$ using SA. we indeed observed $\\mathrm{ApR}(d=3) \\approx 0.95$ and $\\mathrm{ApR}(d=5)=0.93$. However, with CRA-PI-GNN, we achieved $\\mathrm{ApR}(d=3)=0.983$ and $\\mathrm{ApR}(d=5)=0.981$ for $N=10{,}000$ MIS problems, which are comparable to the SA's results reported by Angelini and Ricci-Tersenghi. However, with CRA-PI-GNN, we achieved $\\mathrm{ApR}(d=3)=0.983$ and $\\mathrm{ApR}(d=5)=0.981$ for $N=10{,}000$ MIS problems, which are comparable to the SA's results reported by Angelini and Ricci-Tersenghi. \n    Moreover, for $d=20$, SA's results are $\\mathrm{ApR}(d=20)=0.968$, while our results show $\\mathrm{ApR}(d=20)=0.963$, which is also comparable to SA's performance. Although a more detailed comparison with SA is essential, it is worth noting that SA relies on single bit-flip local transitions and cannot leverage GPU parallel computation, which exhibits notoriously poor efficiency in high dimensional spaces, e.g., $10^6 \\sim 10^7$ variables. \n   In contrast, CRA-PI-GNN performs gradient-based optimization and thus efficiently utilizes GPUs and state-of-the-art optimizers, which can solve bigger problems with sub-linear computational costs, as shown in Figure 4 in the main text.\n\nGiven the additional experiments we conducted and our significant contribution in addressing the limitations of data-independent UL-based solvers, as pointed out by the influential paper Wang (2023), we kindly request you to reconsider your score.", "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": "", "extra_scores": {}}, {"review_id": "rjIxqlU24v", "reviewer": "Reviewer_BuGW", "summary": "The proposed approach is an optimization method for each graph over GNN parameters where each output corresponds to the likelihood of the node belonging to the solution. The objective function consists of a penalty term along with a parameter scheduled to control the non-convexity of the objective.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1- The convex annealing approach proposed in training that controls the level of non-convexity. This is a valid approach to avoid getting trapped in local minima where the solution sizes are not large. \n\n2- Theoretical results of the limiting points of the proposed objective with different \\gamma. \n\n3- The \"no-data\" requirement makes this method mostly generalizable, depending on tuning a set of hyper-parameters for each graph distribution.", "weaknesses": "[Major Comments]\n\n1- The need to solve graph-based NP-hard problems that are originally formulated as ILPs stems from the unscalability of these solvers. For example, the scalability of the MIS problem depends on the number of nodes and the number of edges in the graph. This needs to be the motivation instead of the issues encountered in UL-based solvers.\n\n2- While the proposed approach does not require training data (labeled or unlabeled), there are several hyper-parameters. Tuning these hyper parameters is a challenge. Further discussion is needed here. \n\n3- Getting trapped in local minima is not only the case in GNNs or PI-GNNs. It exists for any continuous relaxation of Problem 1. This is due to the non-convexity inherited in these formulations. For example, if we re-write Problem (3) in matrix form, we can see that the objective has a constant hessian equal to the adjacency matrix of the graph. If the magnitudes and signs of the eigen values vary significantly, then this indicates possible positive and negative curvatures in the loss landscape. Replacing x in Problem (3) with the output of a GNN does not guarantee changes. Although it may be possible that it will make some local minima avoidable by adaptive optimizers (such as ADAM), there is a possibility that this type of overparameterization would create unwanted local minima that do not result in any feasible solutions. Theoretically analyzing this is very complicated due to the use of a GNN. However, empirical investigation can be used to better motivate and understand the proposed approach. \n\n4- Similar to the previous point, rounding issues existed even before GNNs. See the SDP relaxations of MIS [1] and MaxCut [2] and how their dependence on rounding techniques (e.g. spectral clustering [3]) often fails to obtain optimal solutions. Rewriting is needed here. \n\n5- The Stationary point p* = 0_n was not discussed in Section 3.1. Furthermore, in line 208, it is 0_n, whereas in line 2016, it is 0_N. \n\n6- How was the GW approximation applied for the MaxCut problem? This approximation requires a normalized random vector drawn from the standard Gaussian distribution. How many samples were drawn? Given the SDP solution, one can simply draw multiple samples and pick the best where the only requirement is matrix-vector multiplication. This runs extremely fast with (i) no parameters of a NW, and (ii) no hyper-parameters to tune. The scenarios where such approaches fail need to be the motivation to propose the over-parameterized approach with convex annealing. \n\n7- Missing many \"data-independent\" baselines (methods that do not require pre-trained models (such as DIFUSCO [4]) or training data such as RL-based solvers (LwD [5])) for comparison such as ILP solvers (Gurobi, CPLEX, or CP-SAT [6]), sampling methods such as iSCO [7], SOTA heuristics such as ReduMIS [8], and differentiable solvers such as [9]. \n\n8- Why does the paper only consider d-regular graphs? How about the performance on other graphs? How does the run-time of this method scale in terms of the graph order and density? This is a major limitation of this work.\n\n[Minor Comments]\n\n1- What is script C in line 83?\n\n2- What is I and J in the equation after line 86?\n\n3- \"nural\" in line 106.\n\n4- Cite equation 3. An example is [10]\n\n5- Paragraph 149 to 151 is ill-sentenced.\n\n6- “Indeed” in line 232.\n\n7- Cite Potts variable optimization.\n\n8- This study “employs” in line 237.\n\n9- \"are\" in Appendix F.3 in line 247.\n\n[References]\n\n[1] On the shannon capacity of a graph. IEEE TIT, 1979.\n\n[2] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM, 1995.\n\n[3] A tutorial on spectral clustering. Springer, 2007.\n\n[4] Difusco: Graph-based diffusion solvers for combinatorial optimization. NeurIPS, 2023.\n\n[5] Learning What to Defer for Maximum Independent Sets. ICML, 2020.\n\n[6] https://developers.google.com/optimization\n\n[7] Revisiting sampling for combinatorial optimization. ICML, 2023.\n\n[8] A differentiable approach to the maximum independent set problem using dataless neural networks. Neural Networks, 2022.\n\n[9] A branch and bound algorithm for the maximum clique problem. Computers & operations research, 1992.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reviewing our paper, appreciating the strengths in our approach, particularly noting the validity of the convex annealing method to control non-convexity and avoid local minima, as well as the theoretical results of the limiting points with different $\\gamma$ and the generalizability due to the \"no-data\" requirement.\n\n**Strengths 1:**\nWe are grateful for your recognition of the validity of our approach to avoiding local minima. As you commented, \"This is a valid approach to avoid getting trapped in local minima where the solution sizes are not large.\" We appreciate your positive feedback. Our solver has demonstrated that its solution performance (ApR) does not deteriorate even as the problem size increases. In fact, as shown in Figure 4, the computational time increases sub-linearly, similar to PI-GNN, indicating good scalability compared to other solvers such as Gurobi.\nFurthermore, the ApR does not significantly deteriorate even with increasing problem size. CRA-PI-GNN has shown significant improvements for the largest MaxCut problem G70. Therefore, we believe that scalability for larger problem sizes is not an issue. Could you please clarify what size you consider large? We will present results and solution times for MIS and MaxCut problems of the sizes you expect during the discussion time or in the revised version. We will include further discussion in the revised version of the manuscript.\n\n**Weakness 1:**\nThank you for pointing out that \"the need to solve graph-based NP-hard problems that are originally formulated as ILPs stems from the unscalability of these solvers.\" \nWe agree this is an important issue, even more so than the problems encountered in UL-based solvers. We will consider your comments in the revised manuscript.\n\n**Weakness 2:**\nRegarding the comment, \"While the proposed approach does not require training data (labeled or unlabeled), there are several hyper-parameters. Tuning these hyper-parameters is a challenge. Further discussion is needed here.\" As you pointed out, our solver includes hyper-parameters related to the annealing start point and the annealing rate. As shown in Appendix Figure 8, better solutions can be obtained by starting the annealing process from a lower point and slowing down the annealing rate. This annealing mechanism is similar to those used in simulated annealing and its derived algorithms, which face similar issues. Therefore, we consider this problem common to our solver. Developing methods to determine these hyper-parameters adaptively is an important future work. Additionally, other GNN architectures and other hyper-parameter settings can potentially yield better results, but our default settings demonstrate that many problems can be solved with reasonable accuracy.\n\n**Weakness 3:**\nThank you for your insightful comment, \"if we re-write Problem (3) in matrix form, we can see that the objective has a constant hessian equal to the adjacency matrix of the graph. If the magnitudes and signs of the eigenvalues vary significantly, then this indicates possible positive and negative curvatures in the loss landscape.\" This observation is indeed correct. As you noted, non-convexity arises at the stage of continuous relaxation of the objective function in the main text (line 114) before introducing GNN. While formulating with GNN may introduce new undesirable local minima, we intuitively expect the objective function to be smoother by over-parameterizing the optimization problem of the relaxed variables with a higher-dimensional neural network. However, as you correctly pointed out, theoretically verifying this is very challenging due to the non-linearity of GNNs. Therefore, we use empirical studies to discuss the issues arising from parameterizing relaxed variables with GNNs and the plateau problem at $0_{N}$ in Appendix F1. Such empirical research has not been conducted by other studies using UL-based solvers such as PI-GNN or Wang (2022, 2023), and we consider this one of our contributions. While our empirical studies are not comprehensive, we acknowledge the importance of more extensive numerical experiments and examining the solution paths in high-dimensional spaces traversed by GNNs using techniques like PCA for dimension reduction. We consider this an important direction for future work.\n\n**Weakness 4:**\nIn lines 49-55, we explain the rounding issues in general linear programming (Hoffman-Kruskal theorem). However, we agree that adding explanations regarding SDP relaxations for MIS and MaxCut would be beneficial. We will revise the introduction to include this context in the revised version.\n\n**Weakness 5:**\nDue to space constraints, detailed explanations of the stationary point $p^{\\ast}=0_{N}$ are provided in Appendix F1, as mentioned in lines 186-187. In the revised version, we will ensure the main text includes sufficient details about the stationary point to be self-consistent. We are also grateful for pointing out the inconsistent use of $0_{N}$ and $0_{n}$.\n\n**Weakness 6:**\nThe parameters for the Goemans-Williamson (GW) approximation are all set according to the settings in the PI-GNN paper's (approximate) polynomial-time GW algorithm. \nThe implementation used the open-source CVXOPT solver with CVXPY as the modeling interface. In the revised version, we will provide detailed parameter settings in the Appendix to address your concerns.\n\n**Weakness 7:**\nPlease refer to the \"Numerical Experiments\" section of the Unified Response for a comprehensive discussion.\n\n**Weakness 8:**\nPlease refer to the \"Runtime Scalability with Varying Graph Density\" section of the Unified Response.\n\nGiven this evidence, we have adequately addressed your concerns and kindly request you to reconsider your score based on these results.", "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": "", "extra_scores": {}}, {"review_id": "LQrPt7pnIZ", "reviewer": "Reviewer_J6G3", "summary": "This article finds that the existing UL-solvers will trap into local optima and face rounding issues. This study proposes a continuous relaxation annealing (CRA) strategy and an auxiliary function to facilitate training.", "questions": "1. Figure 8 provides parameter analysis for the N=10000 MIS problem. Can parameter sensitivity analysis be provided for other CO problems to demonstrate that CRA can be widely applied to general CO problems without special parameter design?\n2. I am also concerned about the convergence speed under different parameter settings. Could you provide it as a function of the initial\nscheduling and scheduling rate?\n3. Can CRA be applied to routing problems such as TSP? If I understand correctly, the current $\\phi$ function will have very small $p$-values in solving TSP, which may probably lead to a failure situation of CRA.", "limitations": "Well discussed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The method proposed in the article is sound, easy to implement, and effective.\n2. The article is well-written.", "weaknesses": "There are no major drawbacks in this article. There should be more reviews on neural combinatorial optimization solvers that apply annealing ideas as well (such as [1] provides annealing on the distance matrix of TSP).\n\n[1] Lin, Xi, et al. \"\"Continuation path learning for homotopy optimization.\"\" International Conference on Machine Learning. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and thoughtful review. We appreciate your recognition of our method's strengths, noting that it is \"sound, easy to implement, and effective.\" Additionally, we are grateful for your comment that this article has no major drawbacks.\n\n**Weakness:**\nThank you for your valuable suggestion regarding including a broader discussion on annealing methods. We acknowledge the importance of situating our work within the context of existing annealing-related research. The revised version will incorporate a comprehensive review of relevant annealing methods in the Related Work section, including the paper [1] you mentioned.\n\n**Question 1:**\nThank you for your valuable question regarding parameter sensitivity analysis for other CO problems. For the MaxCut problem, we observed a similar sensitivity to parameters as in the MIS problem. Specifically, slower annealing rates result in better solution performance for Gset problems and MaxCut problems on RRGs, like simulated annealing. The revised version will include sensitivity analysis results for MaxCut and other non-d-regular random graphs in the Appendix. Ablation studies will accompany these results to demonstrate the robustness of CRA across various problem settings.\n\n**Question 2:**\nThank you for your insightful question regarding the parameter sensitivity analysis. For the MIS problem, we confirmed that a linear change in $\\gamma$ results in corresponding convergence speeds. To address your concern, we will include detailed results in the revised version showing the stopping time for different parameter settings and initial schedules. This will provide a clearer understanding of how the parameter settings affect the convergence speed across different problem instances.\n\n**Question 3:**\nThank you for your insightful question regarding the applicability of CRA to the Traveling Salesman Problem (TSP). Our method can indeed be extended to this domain. However, the optimal $p$ value for solving TSP is unclear. In this study, our primary focus was on addressing the challenges of UL-based solvers highlighted by Wang et al. (2023) and achieving consistent results with PI-GNN. Consequently, we did not conduct experiments on TSP. Nonetheless, we recognize the importance of comprehensive comparisons for TSP and other problems. We plan to explore these areas in our future work, ensuring that our method's applicability and performance are thoroughly evaluated across a broader range of combinatorial optimization problems.\n\nWe believe these revisions and the additional analyses will significantly enhance the robustness and comprehensiveness of our work. We kindly request you to consider this in your final evaluation.", "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": "", "extra_scores": {}}]

Author rebuttal:
## Unified response to all reviewers 

We sincerely thank the reviewers for their thorough and insightful reviews. Reviewer J6G3 found our idea interesting and promising, and Reviewer fKtw appreciated the comprehensiveness of our numerical experiments. However, Reviewer qMFs and Reviewer BuGW expressed some confusion about our contributions and raised insightful questions. We apologize for any confusion caused and will do our best to address these issues in the revised manuscript.
We will first address the common question of two reviewers (Reviewer qMFs and Reviewer BuGW) in the unified response. 

**Main Contribution and Novelty:**
Our primary contribution is the introduction of CRA to overcome the limitations of UL-based solvers (Type II), as highlighted by Wang et al. (ICLR 2023). 
As mentioned in the introduction, Section 5.4 of (Wang et al. ICLR2023) highlights that UL-based solvers (Type II), which do not use training data or past history, face significant challenges due to local minima issues, making it difficult to obtain reasonable solutions without such data. 
Our numerical results demonstrate that by using CRA and removing the rounding step, we can achieve better solutions than those obtained by meta-learning-based UL solvers that use training data and history. This result is expected to reignite interest and further development in data-independent UL-based solvers.
Moreover, while our study focuses on applying CRA to UL-based solvers (Type II), CRA can be easily generalized to UL-based solvers (Type I) and other relaxation-based solvers, potentially addressing the rounding issue in these methods. Theorem 3.1 can also be easily generalized for UL-based solvers (Type I). 
We plan to explore these general applications of CRA in future work. 

**Numerical Experiments:**
We first respectfully disagree with Reviewer qMFs' statement that "the research from this paper is kind of out-of-date."
Different from sampling-based methods like simulated annealing, UL-based solvers have significant potential for further improvement through black-box optimization (Wang et al., 2022) and advancements in optimizers and GNNs. While it is important to compare our work with the SOTA method (iSCO) and other data-independent solvers with different learning methods, our main contribution is to break through the limitations of independent UL-based solvers (Type II), as pointed out by Wang et al. (2023). Our numerical experiments demonstrate that CRA approach outperforms UL-based solvers (Type I) using meta-learning with training data and history proposed by Wang et al. (2023) and PI-GNN, the typical method of UL-based solvers (Type II). We believe that the benchmark problems and the baseline are sufficient to confirm our findings. However, recognizing the importance of thorough comparisons, we conducted additional numerical experiments using the default parameters from our main text. We compared our solver with the SOTA method (iSCO) and other data-independent solvers with different learning methods. 
 Although the test was conducted in different execution environments, the average ApR for each instance is shown below for your reference, where we benchmarked CRA against a total of 144 instances and compared the ApR and runtime with SOTA (iSCO) and other solvers. Following iSCO's evaluation, we used the results from KaMIS to calculate ApR. Each value represents the average across multiple instances. 

| Method  | Type | GPU  | ER-[700-800]      | ER-[9000-11000]  |
|---------|------|------|-------------------|------------------|
| KaMIS   | OR   | --   | 1.000 (52.13m)    | 1.000 (7.6h)     |
| Gurobi  | OR   | --   | 0.922 (50.00m)    | --               |
| Intel   | SL+TS| A100 | 0.865 (20.00m)    | --               |
|         | SL+G | A100 | 0.777 (6.06m)     | 0.746 (5.02m)    |
| DGL     | SL+TS| A100 | 0.830 (22.71m)    | --               |
| LwD     | RL+S | A100 | 0.918 (6.33m)     | 0.907 (7.56m)    |
| DIMES   | RL+G | A100 | 0.852 (6.12m)     | 0.841 (5.21m)    |
|         | RL+S | A100 | 0.937 (12.01m)    | 0.873 (12.51m)   |
| DIFUSCO | Diffusion | V100 | 0.916 (26.67m) | --             |
| iSCO    | fewer steps | A100 | **0.998** (5.85m) | 0.990 (9.38m) |
| iSCO    | more steps  | A100 | **1.001** (1.28m) | **1.008** (1.25h) |
| **CRA**     | UL-based | V100 | 0.928 (47.30m) | 0.963 (1.03h)   |

The results show that CRA, which optimizes the relaxed variables as an optimization of GNN parameters, takes extra time for smaller ER-[700-800] instances due to the smaller number of decision variables. However, for larger instances, CRA achieves results comparable to iSCO. Although limited space makes it difficult to present other benchmark results employed by iSCO, such as MaxCut and MaxClique, numerical experiments on these benchmarks also show that CRA is less effective for small problems. However, for larger problems, the results are comparable to or slightly inferior to those of iSCO. These results will be added to our revised version's main text or appendix. 
Note that our solver and sampling-based solvers involve numerous hyperparameters, making it challenging to claim superiority definitively. While we understand the importance of a comprehensive comparison of several other solvers in various hyperparameter settings, we kindly request you reconsider the scores in light of our significant contributions to the advancement of UL-based solvers in this study.

**Runtime Scalability with Varying Graph Density**
We are grateful of Reviewer BuGW's insight full comment, "How about the performance on other graphs? How does the run-time of this method scale in terms of the graph order and density? This is a major limitation of this work."
As shown in the attached PDF, our experiments demonstrate that the runtime remains nearly constant as graph order and density increase, indicating effective scalability with denser graphs. We will include these findings in the revised manuscript.

Meta-review: While the original submission exhibited some minor flaws (such as writing issues, lack of comparison on a routing problem like the TSP, more discussion in the experiments section),  the authors have already dealt with one (TSP) and committed to fixing the others in a camera ready version. I expect them to follow through on this commitment. 

This paper presents a nice, simple idea, that works very well. I further emphasize that the writing quality is not good enough, but a quick check with a professional proofreader or LLM ought to fix that easily. Reviewer BuGW also provides a number of small corrections. The experiments, especially with the addition of the TSP in the review phase, provide a convincing argument that the simple annealing mechanism introduced is effective at solving a simple, but diverse set of combinatorial optimization problems. The unsupervised learning technique is a fascinating way forward that stands in contrast to many of the other learning-heavy proposals for neural combinatorial optimization.
Decision: Accept (poster)