Learning to Solve Quadratic Unconstrained Binary Optimization in a Classification Way
Authors: Ming Chen
Jie Chun
Shang Xiang
Luona Wei
Yonghao Du
Qian Wan
Yuning Chen
Yingwu Chen
Venue: NeurIPS 2024 spotlight (2024)
Keywords: quadratic unconstrained binary optimization
combinational optimization
machine learning
classification
neural solver
Primary area: optimization
TL;DR: We propose a neural solver to solve quadratic unconstrained binary optimization in a classification way, which can achieve near-optimal solutions in milliseconds,  even for instances comprising thousands of variables.

Abstract: The quadratic unconstrained binary optimization (QUBO) is a well-known NP-hard problem that takes an $n\times n$ matrix $Q$ as input and decides an $n$-dimensional 0-1 vector $x$, to optimize a quadratic function. Existing learning-based models that always formulate the solution process as sequential decisions suffer from high computational overload. To overcome this issue, we propose a neural solver called the Value Classification Model (VCM) that formulates the solution process from a classification perspective. It applies a Depth Value Network (DVN) based on graph convolution that exploits the symmetry property in $Q$ to auto-grasp value features. These features are then fed into a Value Classification Network (VCN) which directly generates classification solutions. Trained by a highly efficient model-tailored Greedy-guided Self Trainer (GST) which does not require any priori optimal labels, VCM significantly outperforms competitors in both computational efficiency and solution quality with a remarkable generalization ability. It can achieve near-optimal solutions in milliseconds with an average optimality gap of just 0.362\% on benchmarks with up to 2500 variables. Notably, a VCM trained at a specific DVN depth can steadily find better solutions by simply extending the testing depth, which narrows the gap to 0.034\% on benchmarks. To our knowledge, this is the first learning-based model to reach such a performance.

Learning to Solve Quadratic Unconstrained Binary Optimization in a Classification Way
Ming Chen',, Jie Chun Shang Xiang 2, Luona Wei', Yonghao Du', Qian Wan', Yuning Chen 1 Yingwu Chen'
!College of Systems Engineering, National University of Defense Technology
School Public Administration, Xiangtan University
Coolleee of Electronics and Information Engineering, South-Central Minzu University
National Engineering Research Center of Educational Big Data,
Central China Normal University
{cmself, chunjie0720 xiangshang165, wlnelysion, duyonghao15, wanq8228)8163. com, cynnudt@ho tamoootmall..... com, cywnudt com
Abstract
The quadratic unconstrained binary optimization (QUBO) well-known NP-hard problem that takes an n x n matrix Q as input and decides an n-dimensional O-1 vector æ, to optimize quadratic function. Existing learning-based models that always formulate the solution process as sequential decisions suffer from high computational overload. To overcome this issue, we propose neural solver called the Value Classification Model (VCM) that formulates the solution process from a classification perspective. applies Depth Value Network (DVN) based on graph convolution that exploits the symmetry property in Q to auto- grasp value features. These features are then fed into Value Classification Network (VCN) which directly generates classification solutions. Trained by highly efficient model- tailored Greedy-guided Self Trainer (GST) which does not require any priori optimal labels, VCM significantly outperforms competitors in both computational efficiency and solution quality with a remarkable generalization ability. It can achieve near-optimal solutions in milliseconds with an average optimality gap of just 0.362% on benchmarks with up to 2500 variables. Notably, VCM trained at specific DVN depth can steadily find better solutions by simply extending the testing depth, which narrows the gap to 0.034% on benchmarks. To our knowledge, this is the first learning- beasengg-bssed model to reach such performance.
Introduction
Nonlinear integer programming is highly challenging subject mathematical programming and operations research, where the Quadratic Unconstrained Binary Optimization (QUBO) problem is one the most well-known cases. Due to its extensive applicability and computational intricacies, the QUBO continues to receive widespread attention [I]. The purpose of the QUBO problem is to optimize an unconstrained quadratic function:
max / min OFV = f(x) x TQ
where Q is symmetric matrix with n coefficients, while x is binary (0-1) n-dimensional column vector, i.e., E {0, 1). i = 1,.., n. OFV is short for objective function value.
'These authors contributed equally. Correspondence
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This simple formulation is able to represent a remarkable spectrum of applications in Combinatorial Optimization (CO), including those from quantum computing asset exchange problem
[2]
financial analysis 3 transaction settlement [4], set packing problem [ linear ordering problem 6
etc. A large number of classic graph problems and constrained quadratic problems can re-casted
into QUBO through simple transformations 77 9 [0], for which QUBO solving methods can be
easily applied. From a computational perspective, the QUBO problem belongs to the NP-hard family, Typical solving methods for the QUBO include exact methods and heuristic methods. Due to its NP-hardness, the QUBO is not expected to be solved by any exact method in polynomial time. For this reason, intensive research has been devoted to developing heuristic methods.
In recent years, the research on learning- based Neural CO (NCO) methods for solving CO problems has become a hot topic in this field [2]. This type of data-driven method has strong scalability and high efficiency for problems of different types and scales, as opposed to traditional search- based metaheuristics which often require substantial computational effort when problem size is large. These works typically model the solution of CO problems as a Markov Decision Process (MDP) [3], and then use deep reinforcement learning (DRL) to train an advanced policy network, Pointer Network (PN) [14] and Graph Neural Network (GNN)-based [15) models for instance, to support dynamic decision-making at each MDP step. Despite the remarkable performance of these models in addressing certain classical CO problems such as the Vehicle Routing Problem (VRP) [16].
their applications to QUBO encounter significant limitations:
1) PN-based DRL models. PN-based models require problem data represented by a n x C matrix to satisfy its fixed C embedding channels, where n is the number of tasks and C is fixed number of features per task. For instance, the Travelling Salesman Problem (TSP) can be represented by n nodes and their coordinates (each node described by an (z,, y) pair), forming an x 2 matrix. Due to such a requirement, PN-based models encounter difficulties in processing n x n-dimensional input matrix of the QUBO directly since it is not able to handle problem data where both dimensions are variable, resulting in weak scalability of the model for problems of different scales.
2) GNN-based DRL models. Conversely, GNN-based models [1] excel at encoding x n graph data by graph embeddings. Despite this advantage, GNNs incur significant computational and storage costs due to the repeated updating of node and edge hidden states at each MDP step, particularly for large problem sizes. For instance, the GNN in [15] requires an n. X n x h-dimensional hidden matrices to store edge encodings, which is n times the storage of the PN needed at the same hidden size h. Our preliminary tests revealed that the machine we used for this work could not handle the storage demands of GNNs for large-scale instances (see the results of P7000 in Table Additionally, 17 reported that GNNs are not able to compete with greedy heuristics in certain graph combinatorial optimization problems, aligning with our QUBO experimental results.
The limitations encountered by these networks in solving QUBO are closely related the MDP- solving paradigm attached to them. When addressing QUBO via an MDP, each step involves flipping the assigned value of selected binary variable (see the top of Figure [ According to [18. it is critical to evaluate the impact of each flip on the OFV to ensure the high quality of the resulting solution. However, the repeated OFV evaluation throughout the MDP leads to significant computational overhead, which may be unacceptable for large-scale instances.
Contributions. Given the above limitations, radical improvement would require revolutionizing the solution paradigm to compensate for the limitations of DRL models by not using MDP and avoiding repeated OFV computations. Considering the binary nature of QUBO variables, a novel solution paradigm based on classification is proposed, which can provide the binary values of all variables directly at once, rather than following sequential decision-male making to determine values one by one.
To operationalize the concept of this innovative QUBO classification solution paradigm, we propose a Value Classification Model (VCMF) which is neural solver comprised of three key components: an Extractor, the Depth Value Network (DVN), for feature extraction; a Classifier, the Value Classification Network (VCN), for solution determination; and Trainer, the frreddy-guide, Self Trainer (GST), for solver training. Based on graph convolutional, DVN exploits the symmetry property of input data of QUBO efficiently extract the value features, with performance steadily improving as depth increases. These resulting value features of each variable enable VCN to directly generate the solutions in a classification way. For effective model training, we propose the GST, which does not
TTe code is available at htttss://gtthub.....
2

---

need any prior optimal labels. Extensive experiments demonstrate the effectiveness of the proposed VCM and GST. well-trained VCM can directly generate near-optimal solutions for QUBO within milliseconds and exhibit remarkable generalization capabilities across both instance sizes and data distributions. For example, a VCM trained on instances of size 10 can produce near-optimal results for instances of size 7,000 in milliseconds. Furthermore, simply by increasing the testing DVN depth, a VCM trained at a specific depth can attain even better solutions. To our knowledge, this represents the first learning-based classification model for solving QUBO with such a performance.
2 Related Works
The literature on QUBO dates back to [99] which introduced pseudo-boolean functions and binary quadratic optimization. Due to the combinatorial complexity, QUBO has been proven NP-hard in 1979 [20]. Over the decades, large number of methods for solving QUBO have emerged in the
literature. The research on exact methods primarily employed branch-and-bound 21 22 2 24 25
or branch-and-cut [23]. Since the exact methods are prohibitívely expensive when applied to large- size instances, various heuristic methods have extensively emerged, which are designed for high- quality solution discovery within acceptable timeframes. Noteworthy ones include Tabu Search
(TS) [26 27 28]. Simulated Annealing (SA) 229.. Local Search (LS) [30, Ant Colony Optimization (ACO) 31, Memetic Algorithm (MA)
32 and hybrid algorithms 33
Recently, learning-basc based neural CO methods have exhibited significant promise in addressing CO challenges. Successful applications include 3-D Bin Packing Problem [44, Maximum Cut [5)
40 41, etc. Unlike traditional search-based methods, these approaches aim to autonomously acquire solution policies from significant amount of problem data. Nevertheless, the integration of these learning-
Routing Problems [14 36 37
38
39
16
heuristies into QUBO-specific applications still in its infancy, with only a handful of studies exploring this direction and they all adopted the solving paradigm based on MDP. Based on PN, [18] designed hand-crafted features, such as row sum, diagonal elements, and OFV values. These feature values can only reflect small number of characteristics of the problem data, making it difficult to characterize the overall picture of the problem, leading to unsatisfactory results. In addition, since this method models the problem solution process as an MDP, it requires repeated calculation of OFV values, resulting in low solving efficiency.
3 The Neural Solver VCM
General scheme. The general scheme of our proposed Value Classification Model (VCM) is outlined in Figure [ at the bottom, with the detailed neural architecture provided in Appendix A The neural solver VCM comprises three key components: an Extractor, the Depth Value Network (DVN), for feature extraction; Classifier, the Value Classification Network (VCN), for solution determination; and a Trainer, the Greedy- guided Self Trainer (GST), for solver training.
The Extractor DVN. The Extractor is responsible for automatically grasping variables and their correlation features from Q matrix to support the Classifier. The efficacy of the Extractor essentially determines the performance of the VCM. We notice that the Q matrix is graph-like data. It is known that the Graph Convolutional Network (GCN) 42 is a robust technique for graph representation, which learns hidden layer representations that encode both local graph structure and features of nodes. 1/2(A
The extraction of the (-th layer is summarized as (++1) o(D 1/2 (A + IN DD 1/2 H(W(() w()). Here, A, IN. and D are the adjacency matrix, identity matrix, and the degree matrix of the undirected graph G. W(I) is layer-specific trainable weight matrix, and (1) is the matrix of activations in the 1-th layer. The core operation in graph convolution is AH. In QUBO, the is instantiated as Q. while H is the set of extracted features of the variable vector
However, directly using GCN as the Extractor for QUBO poses several insurmountable challenges. First, transforming QUBO into graph typically results in a fully connected Q matrix, leading to n² real-valued edges, with each edge qiy directly affecting the OFV of the problem. It is essential to manage the extraction of large-scale edges and discern their distinctions. As stated in [5), the graph convolution in GCNs is a special form of Laplacian smoothing, key factor for their effectiveness. This smoothing could diminish the influence of high-weight edges, which is not required in QUBO since their original weight differences are essential for the model to accurately identify their impact on the objective function. Also, GCN performance significantly degrades when its depth exceeds
3

---

Components policy models
Flip
Flip
Flip
Xo
Comppnaznts of Our netral savver
Variitle Nodi of X,
Decison
Decisson
Deceson
Decaton
Decision
Fouture Frrbedilings
MDP-based DRL policy models
PNN NN-hasedd Noural Policy
Solution
Valae Festures
Uplate
m
Our Neural Solver VCM
Trwalideaed Gu in OTV
Fraiieer
33
Invaliatted g, and on in OTV
L'pdate
Updato
Extraciee DVN
Chassfier VCN
Validated CPV
Vandatad by By In OFV
Qlastance
Graph
Value Features
Sobution
Figure I: The processes DRL-based policy models and our QUBO solver. Both PN and GNN- based DRL policy models construct solutions sequentially by capturing environmental embeddings at each step to support decision decision-making. In contrast, our neural solver VCM outputs solutions directly in classification way, without any additional decision steps.
two layers 42
even when employing residual connections. This is because when GCN contains numerous convolutional layers, the resulting output features may become excessively smoothed, making it difficult to differentiate vertices from various clusters. To address these issues and based on the principles of graph convolution, we propose QUBO-tailored Depth Value Network (DVN).
In QUBO, each variable zj directly affects the elements of the corresponding j-th row and column in Q. Given that Q is symmetric, i.e., Q = Q",, the features associated with each row should be unified with those of the corresponding column. We first define the features of each variable 2i to be extracted as value feature, accompanied by value feature vector vj RR where h denotes the hidden size. Let 2y be the value features of the j-th column of Q (denoted as ogol). Each element in row j can then be expressed as qtz uty Consequently, the value features for the i-th row can be computed as w. = Σy= (91) To ensure unified row and column features, the value of each column, oçol should match the value of its corresponding row, v,e". This requirement translates to unifying V and QV. where the computation of QV mirrors the core operation of GCN. This alignment may be an additional reason why GCN exhibits effective performance.
In DVN, we take the QV and current V as inputs and employ learning function FF to iterate the value feature. The iteration at depth d is updated as follows:
((++1) FF(((d) QU(4))
Here, V [ is the value feature matrix for all variables æ (i.e., the nodes in the graph). Each V. 1x the value feature vector for I; with all initial values set 1. Fg consists of specific neural networks and activation functions tailored for pattern recognition and features processing. Specifically, obtains the new value features V DD) based on the current and QV convolution value features follows:
( = My ((); (
Where M,, M2 E R are learnable memory units that capture specific feature interactions. ReLU and tanh are the activation functions used to filter the extracted features and compress the value features within a limited threshold, respectively. [:] is the horizontal concatenation operator and M3 R is a learnable memory unit that connects the current and convolution value features. Finally, (d+1) is then obtained as follows.
y (d+1) 1) tanh( (anh(V(())))
The output value of tanh, within symmetric range [-1, 1), can effectively represent the features of distinct variables. An ablation study activation functions and memory units demonstrates the

---

effectiveness of our neural architecture design (see Appendix E). These filtering and compression processes allow DVN to iteratively extract features from Q at any depth, which effectively avoids the problem of decreased performance caused by the convolutional layer increase of GCN. Additionally, during data initialization, we scale the data by XQ to enhance the efficiency of value compression (see Appendix A), where À represents the scaling factor with specific value. Experimental results verify that the performance of our solver steadily improves when the iteration depth of the DVN increases. Notably, without incurring additional training costs, our solver can find better solutions simply by extending the iteration depth (see Section
The Classifier VCN. Based the obtained value features (dd, we propose a Value Classification Network (VCN) which serves as the classifier to generate the solution x for the QUBO.
x Fc(((d)))
(5)
Where Fo is a learning function that maps the value feature of each variable into a binary value. To this end, we calculate the state of each 2; and use the activation function tanh to obtain the state of each z4. The classification result is then determined based on the state of ø4.
{ {state; = (anh(utanh(( (M4 (M4 ())
(6)
{ 1, state, > 0 44 = 0, state, S 0
Where M4 E Rixh is a learnable memory unit and u IR 1x k is the learnable uniform vector to integrate the value features of each variable. VCN can produce complete solution directly by simultaneously considering all variables through single classification action. Compared to other DRL policy models that rely on sequential decisions, solver significantly reduce the computational complexity from (An²) (where the sequence length &s can potentially expand to 2 when the flip of all variables is enumerated) to On?)).
The Trainer GST. It is known that the classification model usually requires labeled solutions for training. Unfortunately, in the case of QUBO, acquiring optimal solutions is rather expensive and may be infeasible for large-size problems. For this reason, we propose a Greedy -eiiddd Self Trainer (GST), which effectively avoids the need for pre-labeled optimal solutions. The GST is outlined in Algorithm| I and its working logic is shown in Figure 2 which consists of three components: a VCM, a Batch Greedy Flip (BGF) algorithm, and a historical best solution set (HB) X4, where the BGF and HB are two featured ingredients of the GST.
Output
Solation
Initial
Batch Greedy Flip (BGF) Algorithm
Problem Q₁
1/00
1.0
Inpul
DVNKVCN
OFV
Updale
Problem Qxams
Trainng
BCE Loss
Label
Historical Best
Solution
Figure
Working logic of the GST.
The Greedy Flip algorithm employs a flip operation to change the assignment for each variable between and (dctailed in Appendix B.I]. At each step, the algorithm first calculates the Objective Function Value Increment (OFI) for each variable, which quantifies the change of OFV resulting from flipping x; (detailed in Appendix B.2). The flip operation with the highest positive OFI is selected. The above process continues until all variables are processed. However, computing the OFI at each step is computationally expensive, making it impractical for batch training.
To overcome this computational bottleneck, we propose a batch OFI calculation technique (detailed in Appendix(B) () that leverages matrix computation acceleration to significantly enhance efficiency. Based on this, we develop Batch Greedy Flip (BGF) method (detailed in Appendix C GPU-accelerated heuristic that improves on the VCM (termed VCM-BGF) by identifying and correcting obvious sub-optimal classification in the current VCM solution.
5

---

Algorithm 1 The Greedy-guided Self Trainer
Input:
The training dataset D with Naata instances, the epoch size E, the batch size B, the training steps per epoch Nateps = (Natta/ B))
Output: The trained VCM with parameters 6*
Initialize the VCM parameters 8, Adam optimizer and the label set X stops = X U... U.X.
Nataps
for epoch = to E do Nateps do datastep + SampleInput(D)
for step
Xhep + Sumple/ steps)
statesteps X + VCM (datastep)
XG stepp + BatchGreedyyPing XVCM ddalsstp)
2teep + arg (A, (X)
Loss LC step: (statestep + 1)/2)
0 + Adam(0, Loss)
end for end for
Finally, we introduce a historical best solution set X During the multi-epoch training process, the training dataset is fixed, ensuring that each instance is used once in each training epoch. This allows us to use the VCM-BGF solution X at each epoch to maintain and update the historical best solution set XL_ The updated historical best solutions serve the training labels for our neural solver. This VCM-based, data-driven tahel-generating process yields adaptive, high-quality labels at low cost. The Binary Cross Entropy (BCE) is applied to calculate the training loss, with the optimization handled by the well-known Adam optimizer [44).
4 Experiments
4.1 Experimental Details
The datasets used in our experiments include generated instances (G), benchmarks (B), and well-known instances (P), described in the format: dataset+instance (ize+er of instances). For the G set, the Q matrix is uniformly generated at random within [-100,100], following the benehmark data format. The B set is B2500(10) (10) consisting of ten ORLIB instances of size 2500 [45). The P set includes 21 very-large instances (46) including P3000(5), P4000(5), P5000(5), P6000(3), and P7000(3). The average OFV gap to the current optimal baseline (GAP in %) and the average running time (ART in milliseconds for default, ms) are used as the evaluation indicators.
Datasets.
Parameter setting. Following the Parameters Study (see Appendix F). the default values for VCM parameters are set
128, a 4, and d = 40. VCM is trained for 100 epochs under four sets of small-size instances (with 10, 20, 50, and 100 variables) with a batch size of 512, resulting in 400 VCMs. Each set includes 512,000 G instances (limited by memory). For fair validation, the test batch size is fixed at 1. Each model is initialized with Xavier initialization [77, and the Adam optimizer applied with 10-4 learning rate and 0.975 decay factor. Experiments were run on an NVIDIA GeForce RTX 3090 and an Intel 19-9900K CPU with 64GB RAM and Ubuntu 18.04 using Pytorch 1.90 in a Python 3.7 environment.
Competitors. Our evaluation includes several types of competitors: 1) The exact optimizer Gurobi 48 We set the max allowed time Is and 1h. Heuristic classification methods, Diag and SR. proposed in [18]. 3) Heuristic construction algorithm BGF, part of GST. 4) The physics-inspired neural solver, PI-GNN 49]. with varying numbers of layers. 5) Three learning-based sequential- decision construction models: one PN-based model called DRLH [8] (which is the state-of thh-----rr. two GNN- models called S2V-DQN (I5] and ECO-DQN 335 (which are the most relevant -tate-of-the-as models for solving optimization problems over graphs). These models use the same parameter setting as VCM and are accelerated by our batch OFI calculation technique, resulting in competitors DRLH-B, S2V-DQN-B, and ECO-DQN-B. To assess the stability of VCM, we also include its enhanced version VCM-BGF as a competitor. In addition, for each instance of the datasets, obtain high-quality reference solution using an integrated model (called VCM-BGF-HID

---

composed of 400 trained VCM- under depth d = 100. VCM-BGF-HB is deemed a high-quality baseline since it is able achieve an average 0.012% deviation from benchmark optimality (see Table TT.
4.2 Experimental Results
We use the B set and P set validate the performance of the trained VCMs. The results in Table [ show that PN-based DRLH-B requires seconds to obtain suboptimal solutions. In terms of solution quality, DRLH-B is outperformed by the ECO-DQN-B, yet it incurs substantial time increases and computational costs due to graph embedding, resulting in an insurmountable GPU memory limitation to preclude their execution on P7000. Among the learning- bassdd competitors, the 2-layer PI-GNN demonstrates the best performance in terms of solution quality. Interestingly. our proposed BGF easily outperforms these learning-baid basen models in both solution quality and speed. Yet is still dominated by the VCM which is the best solver. Indeed, it surpasses all competitors across the whole instance set in both quality and computational efficiency with the highest Wilcoxon P-value of 3.09E-03 (see Appendix D) Taking VCM50 as an example, it can achieve near-optimal solutions with an average gap of only 0.362% within 8ms for benchmarks. Such a solution speed is rather impressive. The results of the very large instances from the P set show that our proposed VCM maintains near-optimal performance. Partieularly, the VCM trained on instances with 10 variables achieves an average gap of 0.569% P7000, displaying significant generalization ability. The results of the optimal or near-optimal solutions. However, Gurobi can only solve problems in sequential way and incurs substantial time cost (over Ih for each G100 instance in Appendix G
and Gurobi are also presented as reference to the VCM. They produce
Table 1: Results on benchmarks and large well-known instances.
B2500(10)
P3000(5)
P4000(5)
P5000(5)
P6000(3)
P7000(3)
FUNCTION VALUE BASTLINE (OPTIMAL)
ALGORITHM
1479921.4
5134727.2
7869134.2
10973791.1
13950582.0
17725010.33
GAP("))
ART (MS) (S) ART (MS)
GAP (5)
ART (MS)
GAP (5)
ART (MS)
(A)(
ART [MS]
GAP (%)
ART (AS))
DIAG
11.542
0.7
99. 262
1.7
97.374
2.9
98.256
4.4
99. 22.223
11.1
98 843
14.3
SR
26.867
(0.1
32.861
0.0
33.510
0.1
33.428
0.2
33. 676679
0.0
32.758
0.4
VCM10
0.566
7.9
0.508
0.569
VCM20
0.488
7.7
0.598
7.9
0.673
0.657
8.3
0.712
0.646
9.1
VCM50
0,362
7.7
0.861
7.9
0.669
8.1
0.783
8,1
0
8.7
0.702
9.1
VCM100
0.401
7.8
0.763
7.9
0.668
$.0
0.803
8.0
0.914
8.7
0.772
9.1
BGF
0.807
800.8
0.979
984.4
0.834
999.4
0.914
994.7
0.966
999.9
0.730
983.6
DRLH-B
1.640
1.5E403
2,044
2.4E:03
1.884
5:0
1,853
8.9E403
1.5E404
1,825
2.2E+04
S2V.DON.B
21.657
1.68404
13.172
2.7k+04
14,050
0.2
14.403
2.15
ECO DQN-B B
0.937
2.3E+04
1.371
5.4E+04
1.333
1.20-05
1,270
2.35+05
1.467
4,0E+05
XCMIO-BGF
0.230
40.8
0.582
70.6
0.297
107.4
0.322
196.3 3
0.374
444.4
0.335
613.6
VCM20-BGP
0.260
87.8
0.310
282.6
506.8
0.512
634.7
VCM50 BGF
0.136
0.277
100.2
0.214
170.0
0.262
326.0
523.3
0.224
770.2
VCM100-BGE
0.139
49.2
0.203
106.0
0.178
186.7
0.245
298.2 2
0.271
549.7
0.212
770.4
P1-GNN(2-LAYER)
1.689
4.4E+04
2.13
6. 6.26+04
1.636
7.1E-04
1.418
8.6E404
1.986
1.40
1.437
1.6E+05
PI-GNN((1-LAN AVER))
1,909
5.7F.04
2.523
7 7.2F-004
2.092
8.0F-04
1.945
1.0F.405
2. 18
1.15405
2. 3.076
1.9F-05
PI-GNNIS- LAYER)
3,28
1.2E+05
3.047
1.0E+05
2.761
1.1E-05
2.463
1.3E+05
2.584
1.5E+05
2.289
2.7E+05
GUROBI-IS
1.0F403
0.070
1.0--03
1.05-03
1.0E403
1.0E+03
1,0E+03
GUROBI- 1H
0.0023
3.6E+06
0.0028
3.6E+06
0.0109
3.6E-06
0.0096
3.6E+06
0.0144
3.6E+06
0.0169
3.6E+06
VCM BGF-IIB
0.012
1.9E+04
0.020
3.6E+04
0.027
6.0E-04
0.040
1.1E+05
0.030
2.0E+05
0.057
2. 2.8E+05
1 The Bold indicates the best average result in different classes of methods
To further investigate the generalization ability of the VCM, we conduct experiments on an additional 1 1,000 generated G instances with 20, 50, 100, 200, 500, and 1, 1,000 variables. We use VCM-BGF-HB as the optimal bascline. The results, illustrated in Figure and detailed in Appendix G demonstrate that VCM trained at a specific size performs well on instances of other sizes. For example, the gap between VCM10 and VCM100 on G100 instances is merely 0.056%, demonstrating the remarkable generalization ability of VCM. The results also show that BGF can further enhance the performance of the VCM, with a solution quality improvement of 0.27% on average. Meanwhile, this improvement afforded by BGF is limited, reflecting the inherent stability of VCM.
In comparison to MDP-based methods, VCM replaces this complex sequential decision-making process with simple classification process, providing an inherent advantage in solving efficiency that becomes more pronounced as the instance size increases. Notably, the VCM achieves this performance without using OFI (which is essential in sequential decision- methods), thereby
7

---

Visen 2.000 0.10
3:111
0.240
0:338
2:44
0:40
1.000
0:44
0,000
0640
0.900
VOMTO
0.03 0.000
9.28
2.50
0.23
0335
-00
ViDe 3.121
0.207
0:42
1:57
6:40
0.077
6.792
D010 0337
0.000
0 0JET
2216
0312
VOMSE OGT
5106 0.01 5:44 0/001
0.134
03777 2214
0220
VOM19 1.344 0.117
0.297
0.817
457
0.80
0.772
VOUMS 6GF
D/R2 0.827 BCC 0,00 18M 110 0.139 9.200 CITH 02:49
1L271
0.212
.299
0200
003 01000 B28
O2E (180))
060
GRESS BODE
-20
Datasons
Datosets
(a) The average gap in VCMs.
(b) The average gap in % VCM-BGFs.
Figure 3: The size generalization ability of VCM and VCM-BGF under different datasets.
considerably reducing computational overhead. The computing time is thousands of times less on average. Also, the computing time increases moderately the problem size enlarges (see Figure 4 Across the whole datasets (with variables ranging from 20 to 7000), the computing time is always under 10ms. In contrast, other sequential-decision competitors, especially GNN-based models, exhibit excessive time growth as the problem size grows, since the number of decision-making steps increases significantly.
ECO-DQN
SIV DQN
DRLH-B B
BGF
VCM
VCM
ART ART (8) ART ART (
200
7.5
5.0
2.5
0.0
10.0
7.5
50
1000)
G5001000)
G000 G200(1000) G500/1000 G1000/1000) B2500(10) Datasets
P1000(
(4000:5)
P5000155
P6000()
P7000(3)
Figure 4: Avearge running time of different datasets in seconds and milliseconds.
4.3 Model Study
Efficiency of GST. We introduce three training competitors, UnS [49]. LHB, and LGF, to validate our Trainer GST. The UnS is an unsupervised training method that directly uses the optimization objective function as the loss function and relaxes the 0-1 variables for optimization. The labels for LHB are obtained by VCM-BGF-HB. The LHB can be considered supervised learning with optimal labels. The labels for LGF are obtained using the current VCM-BGF, which is GST without the historical best solution set. We adopt VCM-BGF-HB as the optimal baseline and illustrate the training curves in Figure The results indicate that GST outperforms competitors in terms of both efficiency and stability. Specifically, GST demonstrates a more efficient and stable training process compared to the unsupervised trainer UnS, which suffers from considerable fluctuations. GST achieves the same performance as the supervised LHB in the early stages of the training process while requiring at least 50% fewer epochs. Although LGF can reach local optimum from time to time, its training process experiences fluctuations due to the unstable quality of the labels outputted by VCM-BGF alone. Therefore, the integration of BGF and historical solutions within GST enables rapid, stable, and adaptive formation of VCM, and circumvents the substantial costs associated with supervised learning.
Distribution Generalization of VCM. The G set, whose default distribution is denoted as R-1, with all elements of the matrix non-zero. To assess the generalization ability of VCM across diverse data distributions, we generate new datasets by following a standard normal random distribution (RN-1) and deactivating the matrix elements to 0 with probabilities of 10% (R-0.9), 40% (R-0.6), 70% (R-0.3), and 90% (R-0.1). I). We conduct tests on these instances of diverse distributions with 20, 50, and 100 variables using our trained corresponding-sizes VCMs. For each distribution, we generate 1,000 G instances and apply VCM-BGF-HB as the optimal baseline to measure the gap. The results (summarized in Figure 6 and detailed in Appendix H demonstrate that VCM maintains
8

---

VCM-Las VOM-LGE VCM-GST
(20(10007)
GSU (000)
(1000/0001
1.0
(up
0.5
12
14
0.6-
L.
1--
08
0.4
144
0.2
0.0
20
40
80 100
10
Epocch
Datanels
Figure 5: VCM training process under different Figure 6: VCM results under different distribution methods instance size 50.
instances.
near-optimal across various data distributions. The VCM performance on the R-0.1 instance set with 100 variables, where 90% matrix elements are zero, manages to sustain a performance gap no larger than 0.15%. Besides, since the MaxCut problem can be re-casted into UQBO, with the difference in the data distribution, we extend our evaluation to MaxCut benchmarks to validate our findings. Results detailed in Appendix fuurther confirm the practical applicability of VCM. These observations imply that the Extractor in VCM can be considered a generic module with cuuriuttion-iddeenniie and problem-specife in QUBO, therehy bringing VCM remarkable generalization ability and wide-spread applicability.
The Study of DVN Depth. The depth is crucial for ensuring interaction and coherence between row and column features in DVN graph convolution. As shown in the Parameter Study in Appendix F.2 increasing the training depth of DVN improves feature extraction precision, leading to consistent enhancement in VCM performance. It logical hypothesize that VCM trained depth d would perform better at deeper testing depths. To investigate this hypothesis, we evaluate six VCMs on benchmark B2500 across eight testing depths. The results (illustrated in Figure (aa) and detailed in Appendix J show that all VCMs exhibit significant performance gains as testing depth increases. Even at the training depth of 10, VCM already learns an iterative feature extraction pattern. However, when the testing depth retracts below the training depth, VCM presents perceptible but tolerable performance degradation, reinforeing the premise that reaching the training depth threshold is essential for DVN stabilization.
particular
To further investigate the rationale behind this performance, we apply the t-SNE (50) on the output (d). of Extractor DVN from the trained VCM50-d10 with varying testing depths. Figure 8 shows that as d increases, clustering transitions into binary clusters gradually. When d = 1, it converges to number of lines, and when d >> 100, the binary clustering occurs. This demonstrates that DVN overcomes the limitation of GCN (i.e., its performance degrades as the depth increases, as shown our evaluation Appendix K). thus effectiiely supporting the Classifier VCN. For instance, the default VCM50-d40 achieves an average gap of merely 0.034% when the testing d hits 300, as opposed its original gap of 0.362%. This performance enhancement can be generalizable to very large instances, as demonstrated by our evaluations on well-knou instances (see Appendix (] and instance with 10,000 and 20,000 variables (see Appendix [). and is achieved without additional training costs. As shown in Figure ([b) the computational time increases linearly (on average 0. 7ms per depth) as the testing depth enlarges, which verifies the remarkable performance of the VCM and extends its applications.
1d20 Lasi
50
VCM50-d40
Gip (%)
1.5
40
30
1.0
0.5
0.0
50
100
150
2001
250
300
VCM50-
Testing Depth
(a) Different testing depth d on B2500(10).
(b) Computational time of VCM50-640 on B2500(10).
Figure 7: VCM results under different testing depth d.

---

Figure 8: The I-SNE visualizations of (d), the first instance of B2500 under VCM50-d10.
5 Conclusions and Future Work
Our neural solver VCM is new state-of-the-ar learning-based model designed for efficiently solving QUBO from classification perspective. It applies the Extractor DVN based on graph convolution and exploits the symmetry property in Q to value features of each variable, VCM generates solutions directly through the Classifier VCN in classification way. Trained by highly efficient model-tailored Trainer GST which does not require any priori optimal labels, VCM shows near-optimality, high efficiency, and generalization ability in mroleen-oolving In particular, it can achieve an average gap to benchmark optimality of 0.362% in milliseconds and stcadily narrow it down to 0.034% by simply extending the testing depth, which brings only linearly increased computational time (average 1ms per depth).
value features. Utilizing these resultant
Although VCM reaches such performance by single classification prcision-makinge its optimality may be potentially limited by the VCN utilization of value features from DVN. This limitation poses challenges in achieving the optimal solution. Future research could explore enhancing VCM capabilities, including the development of more accurate classification networks and more efficient trainers, as well as adapting it to address other combinatorial optimization problems and real-world applications.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation China (No. 72271240. 72201272, 62307015 and 62437002); in part by the Natural Science Foundation of Hunan Province (No. 2022JJ3067 1 and 2024JJ4047); in part by the Hubei Provincial Natural Science Foundation of China (No. 2024AFB 169, 2023AFB295 and 2023AFA020); in part by the China Postdoctoral Science Foundation (No. 2023M7413044 3004); and part by the Scientific Research Foundation of Hunan Provincial Education Department (No. 22C0050).
References
Fred Glover, Gary Kochenberger, Rick Hennig, and Yu Du. Quantum bridge analytics i: tutorial formulating and using qubo models. Annals of Operations Research, 314(1):141-183, 2022.
[2] Fred Glover, Gary Kochenberger, Moses Ma. and Yu Du. Quantum bridge analytics ii: Qubo-plus, network optimization and combinatorial chaining asset exchange. Annals of Operations Research, 3 314(1):185-25) 212. 2022.
[3] Seo Woo Hong, Pierre Miasnikof, Roy Kwon, and Yuri Lawryshyn. Market graph clustering qubo and digital annealing. Journal of Risk and Financial Management, 14(1):34, 2021.
Lee Braine;Danicl Egger,Jennifer Steck; Woerner. Quantum algorithms for mixed binary op- timization applicd to transaction settlement. IEEE Transactions on Quantum Engineering, pages 1-8, 2021.
[5] Bahram Alidace, Gary Kochenherger, Karen Lewis, Mark Lewis, and Haibo Wang. A new approach for modeling and solving set packing problems. European Journal of Operational Revearch, 186(2):504-51,, 2008.
[6] Mark Lewis, Bahram Alidace, Fred Glover, and Gary Kochenberger. A note on xqx as a modelling and solution framework for the linear ordering problem. International Journal of Operational Research, 5(2):152 162, 2009.
10

---

[7] lain Dunning, Swati Gupta, and John Silberholz. What works best when? a systematic evaluation of heuristics for max-cut and qubo. INFORMS Journal Computing, 30(3):608-624, 2018
[8] Gary Kochenberger, Jin Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, and Yang Wang. The unconstrained binary quadratic programming problem: a survey. Journal of combinatorial optimization. 28:58-81, 2014.
[9] Endre Boros and Peter L Hammer. Secudo-booleat optimization. Discrete applied mathematics, 123(1- 35:155-225, 2002. 2002.
[10] Pierre Hansen. Methods of nonlinear 0-1 programming. In Annals of Discrete Mathematics, volume 5, pages 70. Elsevier, 1979.
[11] Cong Zhang, Yaoxin Wu, Yining Ma. Wen Song, Zhang Le. Zhiguang Cao. and Jie Zhang, A review on learning solve combinatorial optimisation problems in manufacturing. IET Collaborative Intelligent Manufacturrnng 5(1))e 2023.
[12] Zhixiao Xiong, Fangyu Zong, Huigen Ye, and Hua Xu. Neuralqn: A general hoyyperrrphh-aseeeee based optimization framework for large-scale qoqps, 2024.
[13] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. Robotica, 17(2);229-235, 1999.
[14] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[15] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms graphs. Advances in neural information processing systems, 30, 2017.
[16] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards onni-generalizable neural methods for vehicle routing problems. arXiv preprint arXiv:2305. /9587, 2023.
[17] Maria Chiara Angelini and Federico Ricci- Tersenghi. Modern graph neural networks do worse than classical greedy algorithms solving combinatorial optimization problems maximum independent set. Nature Machine Intelligence, 5(1):29 31, 2023.
[18] Ming Chen, Yuning Chen, Yonghao Du, Luona Wei, and Yingwu Chen. Hcuristic algorithms based on deep reinforcement learning for quadratic unconstrained binary optimization. Knowledge-Baat Systems, 207: 007:106366, 2020.
[19] Peter L Hammer and Sergiu Rudeanu. Pseudo-boolean programming. Operations Research, 17(2):333261, 1969.
[20] Panos M Pardalos and Somesh Jha. Complexity of uniqueness and local search in quadratic 0-1 program- ming. Operations research letters, 11(2):119-22) 19-123, 1992.
[21] VP Gulati, SK Gupta, and AK Mittal, Unconstrained quadratic bivalent programming problem. European Journal of Operational Research, 15(1):121 1125, 1984,
[22] Francisco Barahona, Michael Jünger, and Gerhard Reinelt. Experiments quadratic 0-1 programming. Mathematical Progranming, 44(1-3) 44(1-3):127-337 1989.
[23] Christoph Helmberg and Franz Rendl. Solving quadratic (0. 1)-problems by semidefinite programs and cutting planes. Mathematical programming. 82:291 -15,, 1998.
[24] Panos M Pardalos. Oleg A Prokopyev, and Stanislav Busygin. Continuous approaches for solving discrete optimization problems. Handbook on modelling for discrete optimization, pages 39-60, 2006.
[25] Hong- Xuan Huang. Panos M Pardalos, and Oleg A Prokopyev. Lower bound improvement and forcing rule for quadratic binary programming. Computational Optimization and Applications, 33:187-208, 2006.
[26] Yang Wang. Zhipeng Lü, Fred Glover, and Jin-Kao Hao. Effective variable fixing and scoring strategies for binary quadratic programming. In Evolutionary Computation in Combinatorial Optimization: 11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011. Proceedings 11, pages 72-83. Springer, 2011.
[27] Yang Wang, Zhipeng LU, Fred Glover, and Jin-Kao Hao. Backbone guided tabu search for solving the ubqp problem. Journal of Heuristics, 19:679 695,, 2013.

---

[28] Jialong Shi, Qingfu Zhang. Bilel Derbel, and Arnaud Liefooghe. A parallel tabu search for the unconstrained binary quadratic prograniming problem. In 2017 IEEE Congress on Evolationayy Computation (CEC). pages 557-564. IEEE, 2017.
[29] Kengo Katayama and Hiroyuki Narihisa. Performance of simulated annealing- based heuristic for the unconstrained binary quadratic programming problem. European Journal of Operational Research, 134(())103-119, 2001.
[30] Arnaud Liefooghe, Sébastien Verel, Luis Paquete, and Kin-Kao Hao. Experiments on local search for bi-objective unconstrained binary quadratic programming. In International Conference on Evolutionary Multi- Criterion Optimization, pages 171-186. Springer, 2015.
[31] Murilo Zangari, Aurora Pozo, Roberto Santana, and Alexander Mendiburu. A decomposition- hased binary aco algorithm for the multiohjective uhqp. Neurocompurting. (666JUL.11):55 68, 2017.
[32] Zhipeng Lü, Jin-Kao Hao, and Fred Glover. A study of memetic search with multi-parent combination for ubqp. Evolutionary Computation in Combinatorial Optimization: 10th European Conference, EvoCOP 2010, Istanbul, Turkey, April 7-9, 2010. Proceedings 10, pages 154-165. Springer, 2010.
[33] Yang Wang, Zhipeng Lüi, Fred Glover, and Jin-Kao Hao. Probabilistic grasp-tabu search algorithms for the ubqp problem. Computers and Operations Research, 00:3100-3107, 12 2013.
[34] Yuan Jiang, Zhiguang Cao, and Jie Zhang. Learning to solve 3-d bin packing problem via deep reinforce- ment learning and constraint programming. IEEE transactions on cybernetics, 2021.
[35] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial opti- mization with reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3243-3250 3250,, 2020.
[36] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. International Conference on Learning Representations, 2017.
[37] Wouter Kool, Herke van Hoof, and Max Welling. Attention, lear to solve routing problems! International Conference on Learning Representations, 2019.
[38] Yeong-Dec Kwon, Jinho Choo, Byoungjip Kim, I1joo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 18:21186 11812111111111 21 198, 2020.
[39] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 35:31226 31238, 2022.
[40] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36, 2024.
[41] Jinbiao Chen, Zizhen Zhang, Zhiguang Cao. Yaoxin Wu, Yining Ma, Ye, and Jiahai Wang. Neural multi-objective combinatorial optimization with diversity enhancement. Advances in Neural Information Processing Systems, 36, 2024.
[42] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[43] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-superviied learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[44] D Kinga, Jimmy Ba Adam, et al. A method for stochastic optimization. International conference on learning representations (ICLR), volume 5, page 6. San Diego, California 2015.
[45] John E Beasley. Obtaining test problems via internet. Journal of Global Optimization, 8:429-433, 1996.
[46] Gintaras Palubeckis. Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Annals of Operations Research, 131:259-282, 2004.
[47] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics. pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
12

---

[48] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2024.
[49] Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics- inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
[50] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
[51] Ankur Nath and Alan Kuhnle. benehmark for maximum cut: Towards standardization of the evaluation of learned heuristics for combinatorial optimization. arXiv preprint arXiv:2406. 1897, 2024.
13

---

A The Neural Architecture within VCM
The overall neural architecture of solver VCM is plotted in Figure 9
Value Classificttio Network
Depth Value Networkk
Depth d
tanh- 2
M2
M2
P13
P33
[:1
tanh
911
912
91m
Cover
Q21
422
tanh
M2
Un
On2
Qvm
Instance Input
AQ Scaling
Value Feature
Compressed Value Festure
Operation
Learaable Parameter
Solution
Figure 9: The neural architecture within VCM. The input Q is initially scaled by a scaling factor À improve value compression efficiency for the post-order Extractor DVN. Subsequently, DVN utilizes problem-tailored convolution to iteratively auto-grasp value features for each variable based on the specified iterative depth d and hidden size h. Finally, leveraging the acquired value features, the Classifier VCN generates the solution directly through a classification way.
Initially, in the Extractor DVN VCM, the value feature V of tasks is denoted as V with elements initialized to 1, so that all elements of the first QV" represent the sum of Q's row rs. These values are significantly influenced by the instance size and dataset distribution, which may vary in magnitude. Therefore, preprocessing of the input data is crucial. To enhance value compression efficiency in DVN, we scale Q using a scaling function. For each Q, we take XQ to perform uniform scaling, where À is the scaling factor calculated as:
8 argmax argmax(abs(rs), 182; r8n))
A A= a/ s8)
Here, a is a handcrafted scaling constant, and is the mean of in each training batch. The proposed scaling function proves effective and plays significant role in the performance of VCM (refer to the experimental results in Appendix
B Batch Calculation of Objective Function Increment
B.1
The Flip Operation
In the MDP for QUBO, the flip operation is fundamental, wherein a binary variable within the current solution transforms between 0 and based on a specific strategy. The diagram of the flip operation is shown Figure TO The key basis for performing the flip operation the calculation of the Objective Function Value Increment (OFI) after each variable is flipped, which is also essential element of iterative search algorithms.
Hdp::
[tipx
Hipp
0
0
Figure 10: The flip operation in the MDP of QUBO.
14

---

B.2 Batch OFI Calculation Method
Traditional OFI computation, however, as depicted on the left side of Figure 11 suffers from inefficiency and resource wastage due its instance-by-instancc serial execution. To address the computational inefficiencies inherent in the traditional OFI computation and to accommodate batch instance requirements pivotal for the existing deep learning model, we propose an innovative batch OFI calculation method. As depicted on the right side of Figure [T] the batch OFI calculation allows for simultaneous OFI calculations across n variables in instances.
Xi
X
Flipxt
Ripxs
Flipxi
xi,r
X
x1
Traditional Proces
Batch Calcultionn Process
X5
X
Xn
Qs
OPV
OPV
D2Y
OPN
OF!
Figure 11: The OFI calculation process at each decision step of the traditional process and the proposed batch process instance approach in which the OFI for each variable is serially and independently calculated at every decision step. In contrast, our proposed batch calculation process exploits the matrix computation to simplify and speed up the calculation process, enabling the determination of the OFI for n variables across batch B instances, with the potential for further acceleration through GPU.
instances. The traditional process entails sequential, instance-by-
We utilize matrix computation, presenting detailed derivation process accordingly. We consider an X r--iimensional symmetric QUBO matrix Q = BRin where qiz = qjí, = 1..n, j = 1..n.
Q11
412
Qn
02
422
42n
Q
(10)
Am1
4n2
Gan
The current QUBO solution {x1, 32, ... indexes the elements of and both the rows and columns of Q. Thus, Equation expanded as follows.
Fnd } is an n-dimensional vector.
{1, 2, ..., n)
f (x)
2 +
Kyayy +
(11)
j=i-1
We examine the effect of flipping the k-th variable on the solution, yielding new solution x' in which 2 is defined by:
Fi, i = Fz + k
x/
(12)
The OFV for x' is then determined.
f(x)= -
Σ g
(13)
j=l
i=1 j=i-1
15

---

Subsequently, the OFI of the variable Fą is calculated as follows:
OFI(#)) - -(x²)= - [(x) = (2 Iiae)
(14)
Uck (I + xkk
+
Σ
TikTs +
Σ
Pejtj
iEN,
JEN
Because of x +2 = 1 and di = Ojir the function simplifies to:
OFI(T)) = (ark - xx) qkk +
Σ
(15)
iEN
In this case, define the sum of the k-th row Qk follows:
guum Dkj2j
(16)
JEN
All the Q across all variables can calculated as follows:
Q Q
(17)
Then, the flip of OFI((x) can be divided into two cases: 0 to 1 and 1 to 0. In the first case where Jk = 0 and r'x 1, the difference x' - 2i. which modifies Equation (15) to:
OFI(*)) Takk +2
Σ
qkjJz
(18)
jENjjK
Since 25 = 0, we have Qkk22 0, thereby expanding OFI (2))
as:
OFI(xx) = qkk. +
Σ
4kj
jEN.jæk
Okk Σ
4kjJ.j
2
(19)
JEN.jæk
= akk: + 2Q
Conversely, when 2y = and 2/ = 0, the difference x' - I2 = 11 adjusting Equation 15 to:
OFI(ax) -Qck - Σ
Qkjoy
(20)
JENJ
Because of Uu 9ak when 2₁ = 1. The OFI(xx) can be expanded as follows.
OFI(*t) = -9ks -
Σ
4kjzi
jEN.jæk
Tak -2 2 > 4gg
(21)
JEN
Tbk 202aum
Hence, the caleulation of OFT(2) can be concluded follow:
[ quR + 2Q)amm Ih
OFI(x))=
(22)
quk 20
Finially, we define the diagonal elements of the matrix Q as Qdiag e Nx1 and propose the OFI batch calculation follows:
OFI(x) = ddiag + 2(1 - 2rm
(23)
We evaluate the effectiveness of the proposed batch calculation of OFI using the following Greedy Flip method.
16

---

C Batch Greedy Flip Algorithm
During the MDP of QUBO, we execute the flip with the highest positive OFI at each state in greedy manner to derive the Greedy Flip algorithm. Figure we provide a comprehensive illustration of the Greedy Flip algorithm's s execution within specific QUBO instance comprising four variables. Notably, variable y undergoes two repeated flips.
Graph
Qnstanne
Transform
35
48
-8
Geedy
-2
154
-12
-88
-22
4B1
-26
-11
-154
OF4,
GFiy
OFl,
0%
65
9Fl,
0P
OFh
6Fs
0Fi,
OFL,
6Fr
0F%
0%
OFL.
6%%
OFl,
0F%
0FF.
Flipo:
Flipa
Flipx,
Rip xs
Step
Step
Shep
Step
Figure 12: The Greedy Flip algorithm of QUBO.
Enhanced by the proposed OFI batch calculation method, we propose the Batch Greedy Flip (BGF) method for supporting the proposed GST. Besides, BGF is only used as competitor to validate the effectiveness of VCM but also as an enhancement component for VCM to integrate a powerful hybrid construction method VCM-BGF. The pseudo-code of BGF is presented in Algorithm It worth noting that the length of the solution for the batch calculation N + 1, consisting of the problem solution with set-aside point. In the OFI of all variables in the current solution is non-positive OFI, the value of this set-aside point will be flipped.
Algorithm 2 The Batch Greedy Flip (BGF) algorithm
Input: the batch size B, the matrix of the batch Q = (Qil 1001=110 1,.., B), Q. E ((N+1)X(N+1)
the initial solution of the batch æ = {zylt 1,..., B}, In E [N++))x1
Output: the improved solution x² Calculate Qding R (N+11)x
while True do
OFT, < Qiiig + 2(1 2r, *u
if VOFO. S 0, = (1,..., B). (1,..., N) then
break
else
for to B do
if VVOF I, < 0, [1,...N N) then
NN+1 +1
else
< arg max (1,...,N) OF
end if
= 1 Ztk
end for
end if end while
17

---

C.1 The Efficiency of Batch Calculation
To investigate the effectiveness of the proposed OFI batch caleulation, we conduct tests on 1,000 generated G instances with 20, 50, 100, 200, 500, and I 1,000 variables, using BGF with batch sizes of I, 32, 64, 128, and 256. For comparative validation, we apply the Traditional Greedy Flip (TGF) method as the competitor, which calculates the OFI in sequential and instance-by-instance way. We plot the running time curve Figure 13 and detail the data Table 2 The results reveal that the OFI batch calculation can significantly enhance the computing efficiency of the Greedy Flip method, which brings orders of magnitude efficiency improvement. With batch size of BGF-01 operates similarly to TGF, calculating instance by instance, where the difference between these two methods lies in OFI calculation process of all variables each decision step. Based on the batch calculation, BGF distinguishes itself by calculating the OFI for all variables simultaneously within single step, as opposed to the sequential approach of TGF. This capability affords BGF marked efficiency edge which grows with problem size, exemplified by its requirement of only 0.696% of the traditional calculation time for G1000 instances. The efficiency gains from OFI batch calculation are even more pronounced when dealing with hatch instance computing. This improvement stems from the lower computational complexity afforded by the matrix computation process and the GPU acceleration. Consequently, the proposed OFI batch calculation method represents potent computational tool for QUBO research, with promising applications beyond the scope of this work to potentially expedite broad range of existing QUBO methods.
TGF
BGF-8]
BGF B32
BGF-B64
SGF-B128
BGF-B256
20000
10000
Total Running Tims (6)
100
75
50
25
1.00
0.75
0.50
0.25
0.00
G20(1000)
GS001000)
G100(1000)
1200(1000)
G500<1000)
G 11000(1000)
Datascts
Figure 13: Total running time (s) of TGF and BGFs in different instances.
Table 2: Total running time of TGF and BGFs in different instances.
TGF
BGF-BI B1
BGF-B32
BGF-B64
BGF-B12
BGF-B256
INSTANCE
TIME (S)
TIME (8)
TIME (S)
TIME (S)
TIME (S)
TIME (S)
G20C (20(1000)
21.92
5.01
0.30
0.18
0.13
0.04
350(1000)
106.08
11.34
0.58
0.34
0.24
0.10
G100(1000)
428.49
21.20
1.02
0.56
0.40
0.16
G200| 1000)
1549.55
56.41
2.38
1.37
0.92
0.59
G500 1000)
92833.51
144.51
8.94
6.62
5.66
5.10
G1000(1000)
37365.85
260.11
40.04
36.87
36.42
35.32
C.2 BGF with Different Initial Solution
To investigate the effect of the initial solution on the BGF, we apply various initial solutions with different percentages 1, including 25%, 50%, 75%, and 100%. We set test batch size to 256 and take the generated instances for testing, including G20(1000), G50(1000), G100(1000),
18

---

1000))000), G500()000), and G1000(1000). Except for and 100%, all BGFs are run ten times on average. The results of average OFV and total running time are shown Table where we can find that the BGF with 100% of outperforms all other test sizes in terms of both quality and speed. Therefore, we take the BGF-100% as the default BGF.
Table 3: Average OFV and total running time of BGF with different initial solutions.
BGF-0
BGF-25%
BGF-50%
BGF-75%
BGF-100%%
INSTANCE
OFV
TIME (S)
OFV
TIME (5)
OFV
TIME (8)
OFV
TIME (8)
OFV
TIME (S)
020(1000)
2838
0.09
2841
0.06
2859
0.05
2888
0.05
2916
0.04
G50(1000)
11659
0.18
11687
0.13
11736
0.12
11800
11901
0.10
3100(1000
33381
0.34
33460
0.27
33522
0.26
33679
0.22
33892
0.16
G200C1000
94907
1.21
95036
1.04
95251
0.91
95556
0.76
96022
0.59
6500 1000)
379096
11.75
379624
9.74
380133
8.16
380816
6.65
382412
5.10
G (1000(1000)
1075398
88.50
1076710
71.81
1077693
59.09
1079293
48.13
1082420
35.32
D Wilcoxon Signed-rank Tests
We perform Wilcoxon signed-rank tests on the gap results obtained from the trained VCMs in comparison other algorithms across 31 instances from the B and sets. The results are summarized in T which clearly show significant differences between the VCM results and those of other algorithms, with the highest P-value being 3.09E-03 between VCM100 and BGF.
Table 4: The P-value results of Wilcoxon signed-rank test between VCMs and other algorithms.
VCM10
VCM20
VCM50
VCM100
DIAG
1.17E-06
1,30--06
4.53E-06
4.97E-06
1.77E-05
1.43E-06
5.46E-06
2.56E-06
1.17E.06
1.94E-05
2.12B-04
3.09E-01
DRLH-B
1.17E-06
1.17E-06
1.17E-06
1.17E-06
S2V-DON-B
3.79E-06
3,79E-06
4.23E-06
3.79E-06
ECO-DQN-B
3,79E-06
3.79E-06
3.79E-06
3,79E-06
VCMIO BGF
1.17E.06
1.17E-06
1.30B-06
2.56E-06
VCM20-RGE
2.56F-06
1.17F-06
2.56F-06
1.43F-06
VCM50-BGF
1.17E-06
1.17E-06
1.17E-06
1.17E-06
VCM100-BGE
1.17E-06
GNN(2 LAYER)
1.17E-06
1.17E-06
1.17B-06
1.17E-06
PI-GNN(3-LAN) LAYER)
1.17E.06
1.17-006
1.17E-06
1.17E-06
PI-GNN(S-LAYER)
1.17E-06
1.17E-06
1.17E-06
1.17E-06
GUROBI-IS
1.17E-06
1.17E-06
1.17E-06
L,17E-06
GUROBI-IE I
1.17E-06
1.17E-06
1.17E-06
L.1E-006
BGF
2.52E.05
1.30E.06
E
Ablation Study
To validate the rationally designed network architecture of our VCM, we the training performance of VCM by selectively ablating specific modules. We employ the VCM-() with the ablation module to distinguish different VCMs. Specifically, we select the VCM-(ReLU), VCM-(tanhi VCM-(tanh2), VCM-(M1) and VCM-(M2) for validation. The ablation module can be quickly queried in Figure 9 The corresponding impacts these ablations are captured in Figure 14. illustrating that any deficient module degrades VCM performance, notably ReL.U and tanh2 modules. ReLU is pivotal for extracting value features, while tanh2 normalizes value features within a range of (-1, 1), essential for the unification of DVN extraction.
19

---

0.6
VCM UCM-(ReLU) VCM-(ann-II (CM-(aan-2)
0.4
VCM-(MI)
OFV Clpp
0.3
VCM-(M2)
0.1
0.0
20
40
60
80
100
Epoch
Figure 14: The VCM training process of ablation study instance size 50.
F Parameter Study
F1
The Scaling Parameter a
We train the VCM with a of 2, 4 (default), 6, and None (without scaling function) at instance size 50. The training process is shown in Figure [5] where observe that the can improve the performance of the VCM. Notably, the default VCM (a = 4) achieves most of the training lead. We believe the scaling function of data compression makes tanh-1 more sensitive to input processing in the early stages. According to Equation (9). the optimal a = 4 can compress the first input value (sum each average of about 2, regardless of instance size and dataset distribution. It should
row) of DVN be noted that when the input value exceeds 2, there is a negligible difference in the output by tanh. Therefore, using tanh-1 in the first depth of the default VCM can better compress and distinguish features, thereby accelerating model learning.
0.5
VCM-aNone
VCM-02
VCM
OFV Gap (56)
VCM-a6
0.3
0.1
0.0
20
40
60
80
100
Epoch
Figure 15: Training process of VCM with different a at instance size 50.
F22
The DVN Depth
certain depth of DVN extraction mandatory for ensuring interaction and coherence between the row and column features. To assess the impact of varying depths on the performance of VCM, we set the training d of VCM50 10, 20, 30, 40 (default), 50, and 100 within an instance size of 50 for validation. As depicted in Figure 16 in Appendix E. the training trajectories of these six VCMs demonstrate that increasing depth (within our test range) enhances feature extraction precision, yielding consistent improvement in VCM performance. Notably, the performance gain is pronounced as the depth extends from 10 to 30, but plateaus thereafter. This trend suggests that certain threshold of DVN depth is required to accomplish thorough value feature extraction from Q. While deeper d can enhance performance, the training costs also incur greater. Therefore, we elected to set d at the most cost-efficient value of 40 by default.
20

---

0.6
VCM-d10
0.5
VCM-020
VCM-030
OFV Gap (%6
VCM-040
VCM-d50
0.3
VCM-d100
0.1
0.0
40
60
100
Epach
Figure 16: Training process of VCM with DVN depth d at instance size 50.
F33 The Value Feature Size h
To evaluate the impact of on VCM performance, we train the model with various values =32,
64, 128 (default), and 256 for instance size of 50. As shown in Figure [7] the results indicate significant improvement in VCM performance with the increase of h. Notably, the default setting of = 128 achieves the highest training advancement, indicating that increasing the value feature size within a reasonable range enhances model performance effectively.
0.6
VCM-h32
VCM-h64
VCM-h129
0.4
VCM h256
OFV Cap
0.3
0.1
0.0
20
40
60
100
Epoch
Figure 17: Training process of VCM with value feature size h at instance size 50.
G Results of Size Generalization
This section details the results of the size generation experiment. We conduct tests additional 1,000 generated G instances with 20, 50, 100, 200, 500, and 1,000 variables. The VCM-BGF is applied as the current optimal baseline for gap calculation. The detailed results are depicted in Table Notably, Gurobi incurs significant time cost, and the results for G set with over 100 variables are omitted each instance takes more than hour.
5
H Results of Distribution Generalization
This section details the results of the distribution generation experiment in the Model Study. We conduct tests with five different distributions on these G instances with 20, 50, and 100 variables using our trained corresponding-sized VCMs, including the standard normal random (RN-1) and the uniform random with probabilities of 0 for 10% (R-0.1), 30% (R-0.3), 60% (R-0.6), 90% (R-0.9). For each test dataset, we generate 1,000 G instances and also apply VCM-BGF-HB as the current optimal baseline to measure the gap. The results are detailed in Table with heatmaps provided in Figure 18
21

---

Table 5: Results generated datasets.
G20(1000)
G50(1000)
(100)1000)
(200L1000)
G500
G10000 1O00)
OBRECTIVE FUNCTION VALAIR BASELINE
2965 095
12070:455
34550. 38
97260.38 38
386638,
1093972,99
GAP (R)
ART (MS)
[AP (S)
ART (MS/GAAP (S) ART (M5) GAP (%) ART (M5)
GAP (5)
ART (MS) GAP (5)
ART (MS)
0.1
97.632
0.9
SR
$1.637
1.5E-02
594
3.9E-02
$2.628
5.5E-00
35.189
4.5E-02
32,915
4.6E-02
33.054
4.6E-02
VCMIO
0,060
4.4
0.108
4.4
0.151
4.8
0.248
7.4
0,338
7.4
0.414
7.5
VCM20
0.121
4.4
0.112
0.257
7.3
0.409
7.4
0.507
7.5
VCM50
0:200
0.382
7.4
0.523
7.5
VCM100
0.244
4.4
0.117
4.4
0.207
4.8
0.207
7.3
0.557
7.4
0.508
7.5
1.642
5.2
1.401
11.7
1.335
1.273
60.8
1.093
294.2
DRLIE-D D
2.034
8.4
1.871
17.8
1,348
34.3
1.926
91.5
1 1,930
220.4
1.914
397.3
ECO- ICO-DQN-B
0.321
43.2
0.362
109.5
0.471
216.6
0.731
636.2
1 1,004
2.3E+03
1.160
1.3E-04
S2V-DQN-B
4.007
22.9
7.173
1.2E+00
7.567
6.4B-02
VCM10 BGG
0.025
5.1
0.058
5.2
0.089
0.148
9.3
0.209
11.6
0.258
16.5
VCM20-BGF
0.010
5.1
0.037
5.5
0.066
3.7
0.107
9.3
0.173
12.6
0.223
18.8
VCM50 BGF
0.036
5.1
5.2
0.064
0.113
12.4
0.163
19.6
VCM100-DGFF
0.052
GUROSI
54.3
3.78-03
VCM-BOF-HR
0.0003
509.1
0.0005
$36.0
926
1,2F403
1.9F403
The Bold indicates the best average result in different classes of methods.
2 The indicates the provider of the applied OFV baseline.
Table 6: Distribution generalization results on generated datasets.
INSTANUE:
G-RN-1
G-R-0.1
G-R-0.3
G-R-D.6
G-R-0.9
Sizh
METTGD
OFV
GAP
ART (MS)
OPV
GAP
ART (MS)
OPV
GAP (%)
ART (MS)
OPV
GAP (56
ART
OPV
GAP
ART
BGF
5089.9
1.34
5.9
793.9
1.32
3.7
1560.5
1.74
4.7
2234.4
1.55
4.7
2770.7
1.49
4.8
VCM
3154,2
803.4
4.4
4.4
0.13
VCM-BGF
5157.8
804.4
0.02
0.01
2269.0
0.02
2811.9
VCM-BGF-HH
5158,9*
2.28:05]
804.5"
2,08403
1588.1
2.0E405]
2269.5
2.0Ev05]
2812.57
2.08.103
20457.5
12.3
3557.7
1.64
10.1
1.64
10.6
9121.7
1.51
10.8
11280.1
11.1
0.07
VCM BGF
20743.0
0.02
5.5
3616.2
0.02
5.2
6498.4
0.02
5.1
9259.3
0.03
5.1
11433.4
0.02
VVMM-GG-HHL
20747.9
2.28:003
3617.1
2.18:03
6499.8
2.0E403
9261.6"
0.18:05|114355
RGF
58031.7
10805.5
1.64
20.7
18462.2
1.48
24.4
26199.1
32279.1
22.4
100
VCM-BGF
VCM
58756.3
58824.2
0.15
0.04
5.0
6.0
10676.8
10664.7
0.15
0.04
5.6
4.8
18713.00
18732.2
0.14
0.04
4.8
5.7
26556.2
16584.
0.13
0.03
5.2
6.2
32641.2
32683.1
0.16
0.03
4.7
5.7
VCM BGF HB 58844,9
2.4E+03|
10680.6*
2.2E+03
18739.1
2.3 2.39+0326651.2-
2.59403/32093.5-
2.36+03
The Bold indicates the best average result in different datasets.
2
The indicates the provider of the applied OFV baseline.
G2011000)
0.381
0.144
0.082
0.128
0.118
0.121
0.8
620/1000)
0.023
0.022
0.012
0.021
0.023
0.010
-008
Gep 0%0
Gop
(5901000)
0.111
0.167
0.073
0.154
0.122
0.129
65901000)
0.024
0.025
0.021
0.025
0.018
0.019
-0.4
(100/1000)
0.22
0100/1000)
0.2
G-RN-1
G..00.1
G-R.0.3 0-8.08 Distributions
GR.09
G.R-1
G-RN-1
G-R.111 G-R.03 GRR-SS
G-.11
Distributions
(a) The average gap in % VCMs.
The average gap in % VCM-BGFs.
Figure 18: Heatmaps of distribution generalization obtained by VCMs under G-R-1 with correspond- ing instance size.
I Results of MaxCut Benchmarks
We extend our evaluation to MaxCut benchmarks, with the results presented below. Utilizing data
from (15), compile the results shown in Table 7 using the average objective function value as
22

---

the key indicator. Additionally, based on data from [II, we present the results in Table where the average approximation ratios serve the performance indicator.
The results confirm that VCM outperforms other methods, consistent with the advantages demon- strated in our test instances. This validates the applicability and robustness of our VCM in problems that can be recasted as QUBO across different scales and distributions.
Table 7: Results on MaxCut benchmarks.
INSTANCE
OPT [S2V-DQN] VCM50-d100
G54100 65410000 (10 INSTANCES) 110.6]
108.2 109.6(5MS)
Table 8: Results on large MaxCut benchmarks.
INSTANCE
TABU [SOFTTABU] (SV-DQN ECO-DQN] VCM-2100 VCM-BCF-4100
(2000 NODES) 0.915]
|0. [0.990(16x5)
0.991(23
Results of DVN depths
This section details the results of the DVN depth experiment in the Model Study. We train VCM50s across various depths d including 10, 20, 30, 40, 50, and 100. Each trained specific-size VCM is tested across an extended range of depths, including 10, 20, 30, 40, 50, 100, 200, and 300. The average gap (GAP) and average running time (ART) benchmarks B2500(10) are listed in Table
The corresponding heatmap is illustrated in Figure 19
VCM50-810
0.633
0.255
0.152
0.110
0.097
0.090
0.088
0.086
VCM50-020
0.096
0.080
VCM50-000
1.588
0.724
0.386
0.251
0.150
0.077
0.072
0.071
GFV Gop
VCM50-040
0.482
0.084
-0.4
VCM50-053
1.494
1.046
0.686
0.482
0.391
9.093
0.085
0.061
-0.
VCM50-0100
0.918
0.089
-0.0
d10
d20
d/o
d40
dbo
d'00
d200
d300
Testing
Depth
Figure 19: Heatmaps test depths under VCM50 models with different training depths
Table 9: Results of DVN depths on benchmarks B2500(10).
METHOD
10
20
40
50
100
200
300
GAP
ART
GAP
ART
GAP
ART (X5)
GAP
ART
GAP (%)
ART
GAP
ART
GAP
ART
GAP
ART
(X5)
(%6
(MS)
(9k
(%)
(MS)
VCM50-410
0.633
2.6
0.255
4.4
0.152
6.1
0.110
7.8
0.097
9.6
0.090
18.2
0.088
35.5
0.086
53.1
VCM50-520
0.609
6.0
0.0%
0.080
53.1
1.586
53.2
VCM50-440
1.543
2.6
0,874
4.4
0.492
6.1
0.362
7.8
0.273
9.6
0.087
18.5
0.045
35.5
0.034
52.8
VCM50-450
1.494
2.6
1.046
4.1
0.666
6.1
0.462
7.8
0.391
9.5
0.093
18.4
0.056
35.5
0.051
52.8
VCM50-2100
23

---

In addition, we evaluate the VCM50 and VCM50-BGF at the default testing depth of d = 40 and deeper depth of d 300. The results on benchmarks and large well-known instances are presented in Table 10
We use Gurobi-1s Is as the baseline for comparison.
Table 10: Results on benchmarks and large well-known instances.
B2500(10)
P3000(5)
P4000(5)
P500015)
P6000(3
F700DX3)
OBJECTIVE FUNCTION VALUE BASELINT (OPTIMAL)
ALGORITHM
1479921.4
5134727.2
7869134.2
10973791,4
13950582.0
17725010.33
GAP (MS)
(MS)
(R) (X5) GAP (R)
(MS) GAP (MS)
(M6)
GUROBI-Is
1.0E403
1.04403
1.0E+03
0.122
1.0E-03
1.04403
0.669
VCMS0-J300
0.034
52
0.066
0.115
52
0.099
53
0.144
76
01.144
116
VCM50-BGF
0.136
44
0.277
100
0.214
170
0. 0.262
326
0.267
523
0.224
770
VCMSO-ES00-BGIF
0.088
K Results of Degradation in GCN
We apply GCN [42] to replace the DVN in VCM and confirm performance degradation with increased layers, consistent with [42). We train GCN and VCM by GST size 50 under the same settings. The training details are shown in Figure 20 and the optimal training gaps are shown in Figure 21
Obviously, the GCN suffers from performance degradation, which is consistent with the conclusion in [42. However, the performance of VCM steadily improves with increasing depth. Besides, the neural parameters in GCN layers are independent, whereas neural units in VCM depth are consistent, resulting lower training costs under the same neural settings.
70
GCN-L
GCN-L3
GCN-L4
GCN-I LS
GCN-LI0
VCM-d
VCM
VCM-d3
VCM-d4
VCM d5
VCM-d10.
OFV Gap(
40
10
%
40
80
100
Epoch
Figure 20: The training processes of GCN and VCM under different training layer T. depth at
instance size 50.
L Results of Very Large Instances
This section presents the results obtained from testing very large instances. We conduct experiments on a single generated G instance with sizes of 10,000 and 20,000, using distributions R-0.1 and R-0.3.

---

Optimal OFV Capp%%)
40
GCN
VCM
30
20
2
3
7
10
Training Depth or Layer
Figure 21: The optimal training OFV gap of GCN and VCM under different training layer T. or depth at instance size 50.
The model VCM50-d300 is evaluated against Gurobi, which served as the baseline with maximum allowable runtime of second, referred to as Gurobi-ls.
To assess performance, we utilize the OFV gap between Gurobi- Is and VCM50-1300 as the metric. The results are summarized Table [T Notably, VCM50-d300 consistently outperforms Gurobi- Is in terms of both solution quality and execution speed, demonstrating its effectiveness on very large instances across various distributions.
Table 11: Results on generated large size instances.
G10m00-R0.1C)
G18000-80.3(1
G20000- k0.3(11
(220000R0.3311
METHOD
[GAP (%) T (MS)
[GAP (8)
T (MM))
[GAP (9)
T (MS)
GAP (8) T (MS)
GUROBI-1S
0.183
1.0E+03
0.045
1.0+003]
0.091
1.0E-03
0.108
1.0E+03
VCM50-6300
0
169
172
0
637
0
676
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the abstract and introduction, we have provided a detailed and accurate description of the scope of the research, related works in QUBO, limitations of current research on learning-baas based models, and the contributions this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 to 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 the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations of our neural solver VCM in the Section Conclusion and Future Work. The optimality of VCM may be potentially limited by the utilization of value features from the Extractor DVN by the Classifier VCN.
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in 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-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.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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, worse outcome might be that reviewers discover limitations that aren't acknowledged
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
26

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We have provided the full set of assumptions and a complete (and correct) proof in Section 3 and Appendix B. We detailed the proposed neural solver VCM in Section 3 and the derivation procedure of the proposed Batch Calculation of Objective Function Increment (OFI).
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have fully disclosed all the information needed reproduce the main exper- imental results of the paper to the extent, including the neural architecture, hyperparameters our VCM, and the dataset generation format.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
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 a 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 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 NeurIPS 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 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 a new model (e.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 instructions for how to construct the dataset).
27

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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 (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
If the paper is accepted, the data and code will be considered for public release.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "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
//nips.cc/publl wttpccccpppcccccceecccc haaplliccggiieeee /Codeeeeeeemmmieeeeecc. www.ibmmssssoPPee ssionPoicy 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 in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: 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 understand the results?
Answer: [Yes]
Justification:
We have specified all the training and test detail in Section 4.1, Experimental
Details.
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 level of detail that is necessary to 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have performed Wilcoxon signed-rand tests and detailed the results in Appendix D.
Guidelines:
28

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at 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
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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one 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 not to show in tables or figures symmetric error that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided sufficient information on the computer resources in Section 4. 1, Experimental Details, specifically in the subsection on Hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neuurpps http://wrrappppoooooooooaaccaaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
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., there a special consid- eration due to laws 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]
29

---

Justification: We have discussed the potential impacts of the work performed in the Section 1, Introduction. The QUBO studied this work able represent a remarkable spectrum of applications in combinatorial optimization.
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 partieular 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 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.
If 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or 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?
Answer: [Yes]
Justification:
They are properly credited and respected in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
30

---

The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.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 souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com/ comddatasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are 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 encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the datasct/code/model 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not 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 to the NeurIPS Code of Ethics, workers involved 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
Question: 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?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects
Guidelines:
31

---

The answer NA means that the paper does not involve crowdsoureing 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 expect authors adhere the NeurIPS 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.
32


Reviews:
[{"review_id": "d7LHsTwQKn", "reviewer": "Reviewer_GWxe", "summary": "This paper presents a novel approach, the Value Classification Model (VCM), for tackling the challenging Quadratic Unconstrained Binary Optimization (QUBO) problem. VCM improves by offering a classification-based solution, addressing limitations faced by existing deep reinforcement learning (DRL) methods. It directly outputs the binary solution without the need for complex policy learning steps in DRL.\n\nThe paper proposes a novel self-training strategy using a greedy flip algorithm. This approach eliminates the requirement for pre-labeled optimal solutions, which can be scarce for QUBO problems.\n\nThe paper demonstrates significant performance gains by VCM compared to existing methods.\n\nOverall, the VCM approach presents a compelling new direction for solving QUBO problems. The paper effectively addresses limitations of existing methods and showcases promising results.", "questions": "see weakness", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overcomes DRL Limitations: The paper effectively highlights the computational burdens of DRL for QUBO and overcomes through classification based method.\n\n Direct Solution Output: VCM directly outputs the binary solution, eliminating the need for complex policy learning steps often required in DRL.\n\nGreedy-Guided Self-Training: The training strategy using a greedy flip algorithm and past solutions and bypasses the need for pre-labeled optimal solutions, which can be scarce for QUBO problems.\n\nVCM shows near-optimality, high efficiency, and generalization ability in problem-solving.", "weaknesses": "1. Could the authors describe the datasets? what problems exactly are getting solved?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and the opportunity to clarify our work regarding the datasets and specific problems solved. We are grateful for the chance to provide a more comprehensive description.\n\n**1. Datasets**\n\nOur study utilized datasets described in the format \"dataset+instance size+(number of instances)\". The instance size here represents the nodes in the graph.\n\nThese datasets include:\n\n1\\) Generated Dataset (G):\n - Q matrix elements are integers uniformly randomized within [-100, 100], following the benchmark data format [1].\n - Used for training (512,000 instances), validation (1,000 instances), and test (1,000 instances) for various instance sizes (10, 20, 50, 100 for training and validation, and 20, 50, 100, 200, 500, 1000 for test).\n - To further evaluate VCM's distribution generalization ability, we regenerated 1,000 test instances by invalidating matrix elements in G instances to zero with probabilities of 10% (R-0.9), 40% (R-0.6), 70% (R-0.3), and 90% (R-0.1). Additionally, we generated G-RN-1 following a standard normal random distribution (RN-1).\n\n2\\) Well-known Datasets (31 instances):\n\n - B2500(10) from ORLIB [1].\n - P3000(5), P4000(5), P5000(5), P6000(3) and P7000(3) from [2].\n - Q matrix elements are integers within [-100, 100], with varying percentages of zero elements across instances. These 31 instances from well-known datasets represent diverse task distributions and we have included a visualization of distributions in Figure 4 the submitted **PDF file**.\n\nThe test instances adopted in this study cover various variable sizes and data distributions, posing significant challenges to model performance.\n\n**2. Applicability**\n\nThe QUBO problem is a classical nonlinear optimization problem fundamental to many combinatorial optimizations. Numerous combinatorial optimization problems can be recast into standard QUBO formulations, which can be solved using QUBO methods. In recent years, researchers have actively promoted related research [3], [4]. It can introduce the penalty function P to liberate constraints and establish QUBO formulations [5]. For several simple constraint examples, appropriate quadratic penalties can be used directly.\n$$\n\\displaystyle f(x)= {x^T}Qx + P(Ax-b)^T(Ax-b)={x^T}Qx + xDx+c={x^T}\\hat{Q} x +c\n$$\n\nFollowing your comment and those of other reviewers, we extended our evaluation to include several MaxCut problem benchmarks. We applied the VCM50 under testing depth 100 for validation and the results are shown below. The results obtained demonstrate that VCM's solving performance is consistent with the advantages shown in our test instances, further validating its applicability.\n\nResults from [6], using the average objective function as the indicator:\n|Instance|OPT|S2V-DQN|VCM50-$d$100|\n|-|-|-|-|\n|G54100|110|108|108(5ms)|\n|G54200|112|108|108(5ms)|\n|G54300|106|104|104(5ms)|\n|G54400|114|108|**114(5ms)**|\n|G54500|112|112|**112(5ms)**|\n|G54600|110|110|**110(5ms)**|\n|G54700|112|108|**112(5ms)**|\n|G54800|108|**108**|106(5ms)|\n|G54900|110|108|**110(5ms)**|\n|G5410000|112|108|**112(5ms)**|\n|Avg.|110.6|108.2|**109.6(5ms)**|\n\nResults from [7], using the average approximation ratios as the indicator:\n|Instance|Tabu|SoftTabu|S2V-DQN|ECO-DQN|VCM-$d$100|VCMG-$d$100|\n|-|-|-|-|-|-|-|\n|G32-G34 (2000 nodes)|0.915|0.983|0.923|0.969|**0.990(16ms)**|**0.991(23ms)**|\n\nAdditionally, we provide comparison results with GCN to verify that GCN’s performance degrades as the layer increases in QUBO problems. We also demonstrate that our trainer GST outperforms the unsupervised trainer (UnS) from [8], emphasizing the effectiveness of self-driven and heuristic guidance for VCM training. These results are presented in our overall response, with figures included in the submitted **PDF file**.\n\n**Overall**\n\nWe believe these additions significantly improve the clarity and impact of our work, providing readers with a more comprehensive understanding of VCM's performance across various QUBO problem instances. Thank you again for your valuable feedback. We look forward to your further comments and are prepared to address any additional questions or concerns you may have.\n\n[1] Beasley, J. E.,1996. Obtaining test problems via internet. Journal of Global Optimization, 8, 429-433. \n\n[2] Palubeckis, G., 2004. Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Annals of Operations Research, 131, 259-282.\n\n[3] Glover, F., Kochenberger, G., Hennig, R., & Du, Y., 2022. Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Annals of Operations Research, 314(1), 141-183. \n\n[4] Glover, F., Kochenberger, G., Ma, M., & Du, Y., 2022. Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange. Annals of Operations Research, 314(1), 185-212. \n\n[5] Kochenberger, G., Hao, J. K., Glover, F., Lewis, M., Lü, Z., Wang, H., & Wang, Y., 2014. The unconstrained binary quadratic programming problem: a survey. Journal of combinatorial optimization, 28, 58-81. \n\n[6] Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L., 2017. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30. \n\n[7] Nath, A., & Kuhnle, A., 2024. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization. arXiv preprint arXiv:2406.11897.\n\n[8] Schuetz, M.J., Brubaker, J.K. and Katzgraber, H.G., 2022. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4), pp.367-377.", "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": "6uhKp1nIZn", "reviewer": "Reviewer_VEhe", "summary": "The article introduces a novel neural solver named Value Classification Model (VCM) for solving the Quadratic Unconstrained Binary Optimization (QUBO) problem. Leveraging a Depth Value Network (DVN) that exploits the symmetry of the problem's matrix, VCM captures value features effectively. The solver uses these features in a Value Classification Network (VCN) for direct solution classification, bypassing the inefficiencies of sequential decision-making models. This approach significantly reduces computational overhead and achieves near-optimal solutions rapidly.", "questions": "1. Have the authors considered comparing the proposed VCM with models designed for hypergraph neural networks, especially in the context of solving Quadratic Optimization problems[1]? Recent works in this area could provide a valuable benchmark.\n2. The paper focuses solely on unconstrained quadratic binary optimization problems. Have the authors considered how the framework might be adapted to address constrained optimization problems, which are more prevalent in practical applications?\n\n[1] Xiong Z, Ye H, Zong F, et al. NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale Quadratically Constrained Quadratic Programs[J].", "limitations": "1. The article only discusses the application of VCM to unconstrained quadratic binary optimization problems. Many practical optimization scenarios involve constraints that might affect the solution space significantly.\n2. While the model reduces computational overhead, the dependency on specific architectural choices and hyperparameters may affect its performance across diverse scenarios not covered in the experiments.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The introduction of the Depth Value Network that utilizes the symmetry property of the Q matrix is innovative and effectively captures valuable features without the performance degradation seen in traditional GCN models due to increased convolution layers.\n2. The VCM demonstrates impressive computational efficiency and quality of solutions, achieving near-optimal results in milliseconds, which is commendable.\n3. The model's ability to generalize across various instance sizes without retraining is particularly notable, showing robustness and adaptability.", "weaknesses": "1. While the model performs exceptionally well on the datasets tested, the scalability and adaptability to even larger datasets or different types of QUBO instances remain to be fully validated.\n2. The paper could benefit from a more detailed comparison with existing state-of-the-art models specifically designed for hypergraph networks, which might provide a clearer picture of the model's relative performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable feedback on our paper. Your comments are crucial for improving the quality of our work. We would like to address each of your points and suggestions.\n\n**1. Comparison**\n\nWe appreciate your suggestion to discuss NeuralQP [1], a nice work targeting Quadratically Constrained Quadratic Programs (QCQPs). NeuralQP significantly enhances solution efficiency and convergence speed for large-scale QCQPs by utilizing a hypergraph-based neural prediction and iterative neighborhood optimization. It provides a new insight into the solver horizon which is very interesting, and we will discuss it in our revised manuscript. \n\nSpecifically, NeuralQP addresses a class of constrained QCQPs with continuous variables, while our work focuses more on providing a fast near-optimal solver for QUBOs, which is a novel attempt to improve computational efficiency and solution quality in unconstrained binary settings. Consequently, it is currently challenging to reformulate NeuralQP’s hypergraph problems into the QUBO formulation, making them difficult to solve with our VCM. However your remarkable suggestion has intrigued us a lot, and NeuralQP provides valuable insights for potential future applications of our VCM, which we intend to explore in future research. \n\nTo provide as valuable a benchmark as possible, we have added additional validations with Gurobi within 1s. \n\n|Method|B2500||P3000||P4000||P5000||P6000||P7000||\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n||GAP(%)|T(ms)|\n|Gurobi-1s|0.034|1E3|0.065|1E3|0.108|1E3|0.104|1E3|0.123|1E3|0.148|1E3|\n|VCM50-$d$300|0.034|52|0.066|53|0.115|52|0.099|53|0.144|76|0.144|116|\n|VCMG50-$d$300|**0.027**|64|**0.040**|79|**0.088**|108|**0.078**|145|**0.109**|249|**0.108**|331|\n\nFor larger datasets, we generated G instances with 10,000 and 20,000 nodes under two distributions for validation.\n|Method|G10000-R0.1||G10000-R0.3||G20000-R0.1||G20000-R0.3||\n|-|-|-|-|-|-|-|-|-|\n||GAP(%)|T(ms)|\n|Gurobi-1s|0.183|1E3|0.045|1E3|0.091|1E3|0.108|1E3|\n|VCM50-$d$300|**0**|169|**0**|172|**0**|637|**0**|676|\n\nThe results demonstrate that our VCM and VCMG represent more efficient QUBO solvers under the same time situation.\n\nFurthermore, we tested VCM50 under test depth 100 with the SOTA exact algorithm QuBowl [2]. \n|Solved|Gurobi|Qwul|VCM|VCMG|\n|-|-|-|-|-|\n|B100(10)|10(0.1s)|10(0.1s)|**10(4.5ms)**|**10(5.6ms)**|\n|B250(10)|0(3600s)|7(610.6s)|**9(7.3ms)**|**9(9.9ms)**|\nThe results show that VCM and VCMG outperform the two exact solvers.\n\nWe have also supplemented the validation test results of GCN and we can see its performance degrades in QUBO problems as depth increases. Besides, we compared our proposed GST trainer with the unsupervised trainer from [3], highlighting the need to use self-driven and heuristic guidance in VCM training. These results are presented in our overall response, with figures included in the submitted **PDF file**.\n\n**2. Scalability**\n\nThe test instances adopted in this study cover various variable sizes (20 to 7000) and data distributions (5 distributions in G instances and 31 benchmark instances represent diverse task distributions). VCM demonstrates consistent advantages across these instances, showcasing its strong scalability.\n\n**3. Hyperparameters**\n\nTwo main hyperparameters include hidden size ($h$) and depth ($d$). Our experiments in Appendix F, show that increasing $h$ has a limited impact on model performance (less than 0.1% difference for sizes ranging from 32 to 256). On the contrary, the impact of $d$ is quite significant. VCM’s performance steadily improves as depth increases.\n\n**4. Applicability**\n\nThe QUBO problem is a classical nonlinear optimization problem that is fundamental to many combinatorial optimization challenges. The proposed VCM aims to provide a new insight to solve this fundamental formulation. However, the way to recast other combinatorial optimization problems into a QUBO formulation is a significant yet challenging work. Over the past decades, researchers have actively advanced this area of study. Some linear or quadratic problems with linear constraints and bounded integer variables can be re-formulated as QUBO using quadratic penalties P [4]. For several simple constraint examples [4], appropriate quadratic penalties can be directly applied.\n\nTherefore, a feasible approach to applying the VCM to solve various problems is to explore methods for reformulating these problems into QUBO.\n\nIn response to your feedback and that of other reviewers, we have expanded our evaluation to MaxCut benchmarks. It is clear that both VCM and VCMG outperform state-of-the-art methods on these benchmarks, validating their practical applicability.\n\nData from [5], using the average objective function as the indicator:\n|Instance|OPT|S2V-DQN|VCM50-$d$100|\n|-|-|-|-|\n|G54100-G5410000(10)|110.6|108.2|**109.6(5ms)**|\n\nData from [6], using the average approximation ratios as the indicator:\n|Instance|Tabu|SoftTabu|S2V-DQN|ECO-DQN|VCM-$d$100|VCMG-$d$100|\n|-|-|-|-|-|-|-|\n|G32-G34 (2000 nodes)|0.915|0.983|0.923|0.969|**0.990(16ms)**|**0.991(23ms)**|\n\n**Overall** \n\nWe appreciate your thorough review and remain open to addressing any additional questions or concerns you may have.\n\n(Character limit, omitting part of ref information)\n\n[1] Xiong Z, et al. NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale Quadratically Constrained Quadratic Programs.\n\n[2] Rehfeldt, D., et al. Faster exact solution of sparse MaxCut and QUBO problems. \n\n[3] Schuetz, M.J., et al. Combinatorial optimization with physics-inspired graph neural networks. \n\n[4] Kochenberger, G., et al. The unconstrained binary quadratic programming problem: a survey.\n\n[5] Khalil, E., et al. Learning combinatorial optimization algorithms over graphs. \n\n[6] Nath, A., et al. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization.", "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": "SVULAM3D3J", "reviewer": "Reviewer_dxsN", "summary": "This article introduces the Value Classification Model (VCM), a neural solver for the quadratic unconstrained binary optimization (QUBO) problem. VCM utilizes a Depth Value Network (DVN) and a Value Classification Network (VCN) to efficiently generate solutions without optimal labels. It outperforms existing models in computational efficiency and solution quality, achieving near-optimal solutions in milli-seconds.", "questions": "- In the DVN section, does the model suffer from the performance degradation seen in GCNs as the number of layers increases\n\n- I'm wondering why using a greedy approach to obtain local optima as labels for supervised learning is superior to unsupervised methods.", "limitations": "The authors discussed the limitation explicitly.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This article focuses on employing learning-based approaches to solve the Quadratic Unconstrained Binary Optimization (QUBO) problem. \n- An innovative graph feature extractor, DVN, is proposed. Compared to the commonly used GCN, the DVN model presented in this work overcomes the degradation issue that occurs when the number of GCN layers increases. Experimental results demonstrate that the model's performance improves as the number of DVN layers increases. \n\n- Additionally, the authors introduce the VCN model, which directly generates solutions and achieves higher efficiency compared to other deep reinforcement learning-based methods. Furthermore, this article proposes the GST training approach, which uses solutions generated by BGF as labels for supervised model training, thereby avoiding the need to obtain the optimal solutions of the problem in advance.", "weaknesses": "In recent year, there are lots of research about solving QUBO problems. My major concerns are about whether the proposed approach outperforms the SOTA algorithms.\n\n- Besides GNN-based DRL models, there are also works that directly solve the QUBO problem using GNNs, particularly [1]. That study also employs GNNs to address the QUBO problem, handling problem sizes up to tens of thousands of nodes. I think such a relevant paper should be cited. The unsupervised method in [1] directly uses the optimization objective function as the loss function and relaxes the 0-1 variables for optimization. Intuitively, this training method, which is directly guided by the loss function, might be more effective than using local optima generated by GST as labels for training. The article should provide further explanation on this matter. Additionally, it is crucial to perform ablation studies comparing this unsupervised method with the method that uses local search solutions as labels. This is important because it pertains to the key point of the article, viewing the QUBO combinatorial problem from a classification perspective.\n\n- The authors should consider more advanced methods as baselines, and these comparisons should be conducted on practical problems such as MaxCut or Maximum Independent Set. The reason for this is that in practical problems like MaxCut, some methods even have performance guarantees, such as the Goemans-Williamson Max-cut algorithm, which provides a bound of 0.878. \n\n-- From https://plato.asu.edu/ftp/qubo.html, the SOTA exact algorithm for QUBO problems is QuBowl. The authors should also consider this one as a baseline. Also, Gurobi is an exact solver for QUBO, one can also run Gurobi for a few seconds (no need to run it for hours) and obtain near-optimal solutions. I think the authors should present a more fair comparison.\n\n[1] Schuetz, M.J., Brubaker, J.K. and Katzgraber, H.G., 2022. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4), pp.367-377.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and constructive feedback on our manuscript. We are grateful for your insights and will address your concerns comprehensively in our revision.\n\nTo better illustrate our work and to improve the manuscript based on your comments and suggestions, we have added the following improvements:\n\n**1. Comparison with Exact Algorithm**\n\nWe have added comparisons with QuBowl from [1], and the results are as follows, where VCM and VCMG outperform two exact solvers and can achieve almost all optimal solutions (19/20) within 10ms.\n\n|Solved|Gurobi|Qwul|VCM|VCMG|\n|-|-|-|-|-|\n|B100(10)|10(0.1s)|10(0.1s)|**10(4.5ms)**|**10(5.6ms)**|\n|B250(10)|0(3600s)|7(610.6s)|**9(7.3ms)**|**9(9.9ms)**|\n\nWe have also added comparisons with Gurobi within 1s, and the results are as follows.\n\n|Method|B2500||P3000||P4000||P5000||P6000||P7000||\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n||GAP(%)|T(ms)|GAP(%)|T(ms)|GAP(%)|T(ms)|GAP(%)|T(ms)|GAP(%)|T(ms)|GAP(%)|T(ms)|\n|Gurobi-1s|0.034|1E3|0.065|1E3|0.108|1E3|0.104|1E3|0.123|1E3|0.148|1E3|\n|VCM50-$d$300|0.034|52|0.066|53|0.115|52|0.099|53|0.144|76|0.144|116|\n|VCMG50-$d$300|**0.027**|64|**0.040**|79|**0.088**|108|**0.078**|145|**0.109**|249|**0.108**|331|\n\nClearly, compared to QuBowl and Gurobi, our VCM and VCMG are more efficient QUBO solvers.\n\n**2. Validation of practical problem**\n\nWe extended our evaluation to include several MaxCut problem benchmarks. \nData from [2], using the objective function as the indicator:\n|Instance|OPT|S2V-DQN|VCM50-$d$100|\n|-|-|-|-|\n|G54100-G5410000 (10 intances)|110.6|108.2|**109.6(5ms)**|\n\nData from [3], using the average approximation ratios as the indicator:\n|Instance|Tabu|SoftTabu|S2V-DQN|ECO-DQN|VCM-$d$100|VCMG-$d$100|\n|-|-|-|-|-|-|-|\n|G32-G34 (2000 nodes)|0.915|0.983|0.923|0.969|**0.990(16ms)**|**0.991(23ms)**|\n\nThe results show that VCM provides impressive performance in MaxCut benchmarks, which validates its applicability to QUBO-related problems.\n\n**3. Comparison with Unsupervised Method**\n\nWe appreciate your bringing this significant related work [4] to our attention, and we will include a citation and discussion of this paper in our revision. The unsupervised method, which directly uses the optimization objective function as the loss function, is intuitively appealing. We have trained VCM by the well-known supervised learning method [4] on size 50 under the same dataset and neural settings, which we call VCM-UnS. Its batch loss function in VCM can be concluded as follows.\n$${p_i}( \\theta_{VCM}) = ({state}_i (\\theta\\_{VCM})+1)/2.$$\n\n$$L(\\theta_{VCM})=\\frac{1}{B} \\sum_{b=1}^B \\sum_{k=1}^N{p}_i (\\theta\\_{VCM})  Q\\_{ij}{p}_j(\\theta\\_{VCM})$$\n\nDetails on the training process are shown in Figure 1 in the submitted **PDF file** and the optimal training GAP (%) of VCM and VCM-UnS are obtained as follows.\n||VCM-UnS|VCM-GST|\n|-|-|-|\n|Optimal Training Gap (%)|0.231|**0.113**|\n\nIt is evident that GST provides a more efficient training process compared to UnS. UnS experiences significant fluctuations. In contrast, the GST training process is remarkably smooth. Compared to the unsupervised trainer UnS, which relies on self-driven model training, GST offers the following advantages in QUBO:\n- Integration of both self-driven and heuristic-guided training processes.\n- Current labels based on VCM’s performance.\n- Provision of a clear learning target guided by heuristic, enabling the creation of more suitable labels for training and facilitating quicker and more stable model convergence.\n- The ability to train the VCM without requiring global optimal solutions as labels.\n\n**4. The degradation in GCN**\n\nWe used the GCN [5] to replace the DVN of VCM. In GCN, we used residual connections between hidden layers to facilitate the training of deeper models. The $l$-th layer in GCN is calculated as follows.\n\n$$\nH^{l+1}=\\sigma\\left(\\tilde{D}^{-1/2}(Q)\\tilde{D}^{-1/2}H^{(l)}W^{(l)}\\right)+H^{(l)}\n$$\n\nAfter the $L$ layer, the solution can be generated as follows.\n$$\nx=VCN(H^{L})\n$$\n\nWe have trained GCN and VCM by GST on size 50 under the same settings. Details and optimal training gap trends are shown in Figure 2 and Figure 3 in the submitted **PDF file** and the best training GAPs (%) are obtained as follows.\n\n||GCN-L1|GCN-L2|GCN-L3|GCN-L4|GCN-L5|GCN-L10|\n|-|-|-|-|-|-|-|\n|Optimal Training Gap (%)|37.85|24.15|16.23|15.91|31.33|46.29|\n||VCM-$d$1|VCM-$d$2|VCM-$d$3|VCM-$d$4|VCM-$d$5|VCM-$d$10|\n||**18.18**|**7.02**|**3.54**|**2.08**|**1.36**|**0.35**|\n\nObviously, the GCN suffered from performance degradation, which is consistent with the conclusion in [5]. However, the performance of VCM steadily improves with increasing depth. Besides, the neural parameters in GCN layers are independent, whereas neural units in VCM depth are consistent, resulting in lower training costs under the same neural settings.\n\n**Overall**\n\nWe are grateful for your in-depth review and valuable suggestions and hope these improvements will significantly enhance the quality and impact of our work. We remain open to addressing any additional questions or concerns you may have and sincerely invite you to reassess the contributions of our paper.\n\n(Character limit, omitting part of ref information)\n\n[1] Rehfeldt, D., et al. Faster exact solution of sparse MaxCut and QUBO problems. \n\n[2] Khalil, E., et al. Learning combinatorial optimization algorithms over graphs. \n\n[3] Nath, A., et al. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization.\n\n[4] Schuetz, M.J., et al. Combinatorial optimization with physics-inspired graph neural networks. \n\n[5] Kipf, T. N., et al. Semi-supervised classification with graph convolutional networks.", "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:
**Overall Response**

Dear Reviewers,

We sincerely appreciate your thorough reviews and constructive feedback on our manuscript. Your insights have been invaluable in improving the quality and impact of our work. Below, we address your comments and outline the improvements made in response to your suggestions.

**1. Comparison with Exact Algorithm**

For a fair comparison, we have added validations with Gurobi within 1 second and the results are shown below.
|Method|B2500||P3000||P4000||P5000||P6000||P7000||
|-|-|-|-|-|-|-|-|-|-|-|-|-|
||GAP(%)|T(ms)|
|Gurobi-1s|0.034|1E3|0.065|1E3|0.108|1E3|0.104|1E3|0.123|1E3|0.148|1E3|
|VCM50-$d$300|0.034|52|0.066|53|0.115|52|0.099|53|0.144|76|0.144|116|
|VCMG50-$d$300|**0.027**|64|**0.040**|79|**0.088**|108|**0.078**|145|**0.109**|249|**0.108**|331|

For larger datasets, we generated G instances with 10,000 and 20,000 nodes under two distributions for validation.
|Method|G10000-R0.1||G10000-R0.3||G20000-R0.1||G20000-R0.3||
|-|-|-|-|-|-|-|-|-|
||GAP(%)|T(ms)|
|Gurobi-1s|0.183|1E3|0.045|1E3|0.091|1E3|0.108|1E3|
|VCM50-$d$300|**0**|169|**0**|172|**0**|637|**0**|676|

Besides, we have added validations with the SOTA exact algorithm QuBowl [1] and the results are shown below.
|Solved|Gurobi|Qwul|VCM|VCMG|
|-|-|-|-|-|
|B100(10)|10(0.1s)|10(0.1s)|10(4.5ms)|**10(5.6ms)**|
|B250(10)|0(3600s)|7(610.6s)|**9(7.3ms)**|**9(9.9ms)**|

Clearly, the above results **further verify the high efficiency of our VCM, which can provide optimal or near-optimal solutions in milliseconds**.

**2. Validation of Practical Problem**

We extended our evaluation to MaxCut benchmarks and the results are shown below.

Data from [2], using the average objective function as the indicator:
|Instance|OPT|S2V-DQN|VCM50-$d$100|
|---|---|---|---|
|G54100-G5410000 (10 instances)|110.6|108.2|**109.6(5ms)**|

Data from [3], using the average approximation ratios as the indicator:
|Instance|Tabu|SoftTabu|S2V-DQN|ECO-DQN|VCM-$d$100|VCMG-$d$100|
|---|---|---|---|---|---|---|
|G32-G34 (2000 nodes)|0.915|0.983|0.923|0.969|**0.990(16ms)**|**0.991(23ms)**|

The results confirm that VCM outperforms other methods, consistent with the advantages demonstrated in our test instances. This **validates the applicability and robustness of our model in problems that can be recasted as QUBO across different scales and distributions**.

**3. Scalability and Performance**

Our study covers various variable sizes (20 to 7000) and data distributions, demonstrating VCM's **consistent performance advantages**. We also investigated the impact of hyperparameters in Appendix F, particularly the depth of the DVN, on model performance. Our findings indicate that **deeper models yield better performance, whereas variations in hidden size have a negligible impact**.

**4. GST vs. Unsupervised Method**

We have compared our trainer GST with an unsupervised trainer UnS [4] under the same VCM settings. The results of optimal training gaps are shown below (while details can be found in Fig 1 in the submitted **PDF file**).
||VCM-UnS|VCM-GST|
|-|-|-|
|Optimal Training Gap (%)|0.231|**0.113**|

We found that the GST training process offers significant advantages over the unsupervised method. **GST integrates both self-driven and heuristic-guided training**, enabling **quicker and more stable** model convergence without requiring global optimal solutions. This results in more efficient training and better performance for VCM in solving QUBO problems. 

**5. Addressing Degradation in GCN**

We applied GCN [5] to replace the DVN in VCM and confirmed performance degradation with increased $L$ layers, consistent with existing literature [5]. The additional results of optimal training gaps are shown below, with details and optimal training gap trend shown in Figure 2 and Figure 3 in the submitted **PDF file**. 
||GCN-L1|GCN-L2|GCN-L3|GCN-L4|GCN-L5|GCN-L10|
|-|-|-|-|-|-|-|
|Optimal Training Gap (%)|37.85|24.15|16.23|15.91|31.33|46.29|
||VCM-$d$1|VCM-$d$2|VCM-$d$3|VCM-$d$4|VCM-$d$5|VCM-$d$10|
|Optimal Training Gap (%)|**18.18**|**7.02**|**3.54**|**2.08**|**1.36**|**0.35**|

**VCM's performance steadily improves with increasing depth**, highlighting the robustness of our approach. The **consistent neural units** across every DVN depth result in lower training costs and better scalability.

**Conclusion**
We have meticulously addressed your comments and made significant improvements to our manuscript. We believe these enhancements will greatly improve the quality and impact of our work and we remain open to any additional questions or concerns. While QUBO has been studied for many years, **it is the first time that a learning-based model can stably achieve near-optimal solutions on large instances in milliseconds**, and we do believe that our work is innovative and incremental. We sincerely invite you to reassess our contributions.

Reference

[1] Rehfeldt, D., Koch, T., & Shinano, Y., 2023. Faster exact solution of sparse MaxCut and QUBO problems. Mathematical Programming Computation, 15(3), 445-470. 

[2] Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L., 2017. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30. 

[3] Nath, A., & Kuhnle, A., 2024. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization. arXiv preprint arXiv:2406.11897. 

[4] Schuetz, M.J., Brubaker, J.K. and Katzgraber, H.G., 2022. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4), pp.367-377. 

[5] Kipf, T. N., & Welling, M., 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.

Meta-review: This paper focuses on the use of machine learning to solve the widely applicable combinatorial QUBO problem. In this regard, the submissions makes various advances:

- Different from the current ML based schemes utilizing a RL based approach to generating candidate solutions sequentially, the proposed approach uses a classifier to directly output candidate solutions, making the candidate solution generation step significantly more efficient.
- Identifying the limitations of GNN based variable representations of existing schemes, the paper proposes a representation that (i) leverages the symmetry of the QUBO problem, (ii) can be applied to problems of any size at training time, and (iii) is recursive in nature, and has been shown to perform better with more recursions at test time.
- The proposed model is trained without the need for high-quality solutions for the training problems by utilizing a GPU-accelerated greedy flip algorithm that efficiently generates progressively improving solutions that the model is evaluated against during training.


Overall the empirical results, highlighting the strong performance of the proposed scheme against various ML based schemes and off-the-shelf solvers (Gurobi). During the author-reviewer discussion, additional baselines (such as Gurobi-1, PI-GNN, QuBowl) and benchmarks (MaxCut) were brought up, and the new results continue to highlight the strong performance of the proposed scheme. Furthermore, the authors clearly evaluate the ability of the model to be trained on small instances, and tested on larger instances, highlighting the (size) generalization capability of the proposed scheme. The submission also contains thoughtful ablations, highlighting the effect of the different choices made in the overall pipeline.
Decision: Accept (spotlight)