MaxCutBench: Revisiting and Benchmarking Graph Neural Networks for Maximum Cut
Authors: Ankur Nath
Alan Kuhnle
Venue: Accepted by TMLR ()

Abstract: Recently, there has been much work on designing general heuristics for graph-based, combinatorial optimization problems via the incorporation of Graph Neural Networks (GNNs) to learn distribution-specific solution structures. However, there is a lack of consistency in evaluating these heuristics in terms of the baselines and instances chosen, making it difficult to assess the relative performance of the algorithms. In this paper, we introduce \textbf{MaxCutBench}—an open-source benchmark suite dedicated to the NP-hard Maximum Cut problem. The suite offers a unified interface for $16$ algorithms, both traditional and machine-learning-based. Using our benchmark, we conduct an in-depth analysis of the implemented algorithms on a carefully selected set of hard instances from diverse graph datasets. Our main finding is that classical local search heuristics can outperform several highly cited learning-based approaches, including S2V-DQN (Khalil et al., 2017), ECO-DQN (Barrett et al., 2020), among others, in terms of objective value, generalization, inference time, and scalability. Additionally, we find that the performance of ECO-DQN either remains the same or improves when the GNN is replaced by simple linear regression. We hope our benchmark will contribute to the efforts of the community to standardize the evaluation of learned heuristics for combinatorial optimization. Code, data, and pre-trained models are available at: \url{https://github.com/ankurnath/MaxCut-Bench}.

Published in Transactions on Machine Learning Research (04/2025)
MaxCut Revisiting and Benchmarking Graph Neural Networks for Maximum Cut
Ankur Nath
anath Stath&ttmm...o edu
Deportment of Computer Science Engineering
Teras ABM University
Alan Kuhnle
kuhnle &tama edu
Deportment of Computer Science Engineering
Texas ABM University
Reviewed on OpenReview: https: // optprevie......ee.. net/ pet/ffrum? id= 322Pp
Abstract
Recently, there has been much work designing general heuristics for graph-based, com- binatorial optimization problems via the incorporation of Graph Neural Networks (GNNs) to learn distribution-specificc solution structures. However, there is lack of consistency in evaluating these heuristics in terms of the baselines and instances chosen, making it difficult to assess the relative performance of the algorithms. In this paper, we introduce Max CutBench an open-source benchmark suite dedicated to the NP-hard Maximum Cut problem. The suite offers a unified interface for 16 algorithms, both traditional and machine- learning-based. Using our benchmark, we conduct in-depth analysis of the implemented algorithms a carefully selected set of hard instances from diverse graph datasets. Our main finding is that classical local search heuristics can outperform several highly cited learning- based approaches, including S2V-DQN (Khalil et al. 2017), ECO-DQN (Barrett ct al. 2020), among others, in terms of objective value, generalization, inforence time, and scalability. Additionally, we find that the performance of ECO-DQN either remains the same or improves when the GNN is replaced by simple linear regression. We hope our benchmark will contribute to the efforts of the community to standardize the evaluation of learned heuristics for combinatorial optimization. Code, data, and pre-trained models are available at: httts:///ithh/: comm//nkkuraaattaaaatt-taaaaaa
1 Introduction
The design of effective heuristics or approximation algorithms for NP-hard combinatorial optimization (CO) problems is a challenging task, often requiring domain speccfc knowledge alongside a rigorous process of empirical refinement. Typically, the precise probability distribution of a particular are needed for a given application is complex or unknown and may deviate far from the of worst-case instances that give rise to the computational complexity of the problem at hand. For example, consider shipping company that must solve a presumably similar optimization problem each day for the routing of its delivery vehicles. Consequently, there has been significant interest among researchers in automating this demanding and tedious design process using machine learning to develop algorithms that exploit the inherent structure of these distributions (Khalil et al. 2017 Barrett et al.) 2020 2022 Zhang et al. 2023 Tönshoff et al. 2022).. Empirical evidence suggests that learned heuristics (Barrett et al. 2020 Tönshoff et al. 2022 can be competitive with thee--fftheeart (SOTA) heuristics tailored to individual problems.
of instances that
However, along with the surge of automated, general heuristics for CO problems, it is necessary to have a standardized way to evaluate these heuristics to determine what gains, any, are achieved over more traditional houristics. The current status of the field that each work formulates heuristic and then selects its own baselines, problems, and instance distributions evaluate the heuristic. Often, combination of weak traditional heuristics and expensive exact. algorithms is employed baselines, such as the Greedy

---

Published in Transactions on Machine Learning Research (04/2025)
algorithm (weak) exact IP solvers such GUROBI (Gurobi Optimization, LLC 2023 and CPLEX IBM- IT.OG 2023 More discussion and details can be found in Appendix A.3
In this paper, we analyze several highly cited and recently proposed learned heuristics for the Maximum Cut (MaxCut) problem. MaxCut is one of the fundamental W/P-hard optimization problems (Karp 1972 and has been intensely studied for decades (Darvariu et al. 2024). It has numerous real-world applications, such as portfolio optimization (Venturelli & Kondratyev 2019 Elsokkary et al., 2017), protein folding (Perdomo-
Ortiz et al. 2012), VLSI design [Barahona et al. 1988), and finding the ground state of the Ising Hamiltonian in physics Barahona
1982] Signilicant commercial and research efforts have been devoted to developing
MaxCut solvers using classical (Goto et al. 2019) and quantum annealing (Teleeu et al.
2019
Tiunov et al.
2019)
approaches, as well as classical Goeemans & Williamson, 1995 Rehfeldt et al., 2023
Benlic & Hao
2013
Marti et al. 2009 Festa et al., 2002 Burer et al., 2002] and learned (Barrett et al.
2022 Zhang 2023) algorithms. These efforts underscore the combination of intractability and broad applicability
2020
ct al.
that motivates our focus on this problem.
To address these gaps and promote fair and comprehensive evaluation for CO, carefully select distributions of instances for MaxCut and evaluate the performance of several highly cited and recently proposed heuristics on these instances. We pose the following research questions:
In this setting, can reproduce corroborate the performance of learned heuristics as compared to their traditional counterports? Is there any obsolule performance gain, perhaps with trade-off in computational efficiency, when using learned heuristics compared to reasonably effective traditional baselines? Finally, how well do algorithms trained with one distribulion generalize to another distribution?
Contributions.
We provide an open-source benchmark suite MaxCut-Bench for the Maximum Cut problem. The software currently supports several highly eited or recently proposed, learned heuristics such as S2V- DQN (Khalil et al. 20117) ECO-DQN (Barrett et al. 2020 , ANYCSP (Tönshoff et al. 2022), GFLOW- CомBÔPT (Zhang et al. 2023). Our modern re-ippeementation of several algorithms, using efficient graph learning packages, is designed with a focus on reproducibility and scalability, enabling the handling of larger instances. Our evaluation suite is designed to support research on combinatorial problems on graphs and aims to provide a fair and comparable environment for future evaluations.
Using MaxCut-Bench, we compare the learned hcuristies to classical heuristics across multiple datasets that have previously been used to benchmark SOTA traditional heuristics. Our results reveal that classical local search heuristies, TABU SEARCH and EXTREMAL OPTIMIZATION, consistently match or outperform all evaluated learned hcuristics in terms of objective value, scalability, and generalizatinn
for ANYCSP. This finding is particularly surprising given that S2V-DQN, for instance, is widely regarded as a strong heuristic, frequently used as a baseline, and cited thousands of times.
Using our re-implemennation of learned local search heuristics, we analyze deep learning techniques de- signed to enhance local search and conduct an exhaustive evaluation of these heuristics on hard instances. Our results demonstrate that the strong performance of the highly cited heuristic ECO-DQN can be replicated by selecting subset of its features related to TABU SEARCH and replacing the GNN with linear regression model, whether using the original code or our re-implementttion.
The main goal of our work is to provide fair and comparable enviromment for evaluating machine learning algorithms in combinatorial optimization, specifically for the Maximum Cut problem. We believe our work highlights the lack of standardized datasets and baselines necessary to demonstrate significant improvements. We hope that MaxCutBendh can address this gap. In addition to our negative results, we also find that classic algs such as local search, can be significantly enhanced with deep learning (Khalil et al. 2017] Yao et al. 2021). This suggests that more research is needed on replacing handcrafted rules with machine learning and standardization in datasets and baselines.
This requires exact solution the MaxCut problem, and the 2021 Nobel Prize in Physics was awarded for work on spin glasses.
2

---

Published in Transactions on Machine Learning Research (04/2025)
Organization. The rest of this paper is organized as follows. In Section 2 We present the MaxCut-Bench instance distributions and algorithms in Section 3 In Section | we use the benchmark to answer the motivating questions above. Finally, in Section
discuss relevant related work.
we conclude the paper.
2 Related Work
In the following, we review two categories of related works: benchmarking learned heuristics for CO, which aligns with our work, and algorithms for MaxCut.
Benchmarking Learned Heuristics for CO. With the growing interest in using GNNs to tackle CO problems, several recent works revisit their effectiveness compared to traditional heuristics. For the MaxCut problem, Yao et al. (2019) show that a simple local search algorithm, EXTREMAL OPTIMIZATION (Boettcher & Percus 2001), consistently outperforms their adapted GNN baseline (Chen et al., 2017) across various con- figurations of dense and sparse random regular graphs. However, their study does not compare these results with existing solvers from the literature. To the best of our knowledge,
the first to comprehensively
compare SOTA-learnee heuristics from the literature against classical heuristics for MaxCul.
For the MAXIMUM INDEPENDENT SET (MIS) problem, Böther al. 2022 show that the performance of the popular guided tree search algorithm (Li et al. 2018) is not reproducible, and the GNN used in the tree scarch does not play any meaningful rolc. Instead, the various classical algorithms are responsible for the good performance, especially on hard instances. This is analogous to our result for the ECO-DQN algorithm (details in section 4.2). where we show that the GNN does not appear to play a meaningful role in the algorithm, and instead, the good performance of ECO-DQN for MaxCut may come from its Tabu Search- related features. Similarly, Angellnii & Ricci- Ricci-Tersenghi (2023 show that simple greedy algorithm, running almost in linear time, finds solutions of better quality than a physics-inspired unsupervised GNN-based heuristic (Schuetz et al. 2022). In the context of the TRAVELING SALESMAN PROBLEM (TSP), Joshi et al. (2020) note that GNNs achieve promising results for relatively small instances, typically up to a few hundred algorithm (Helsgaun 2000 Taillard & Helsgaun [209)) consistently finds solutions close to optimal. More recently, Liu et al. (2023) demonstrate that learned heuristies still lag behind traditional solvers in effectively solving TSP. For the MINIMUM VERTEX COVER. problem, [aato et al. (2019) shows that the best approximation ratio achievable by a large class of GNNs is 2, which is suboptimal Karakostas 2009).
cities. However, for instances involving millions of cities, the classical Lin- Kernighan-HHesgeee
Other Algorithms for MaxCut. In addition to the algorithms included in this paper, several other algorithms are available for solving MaxCut. Dumning et al. (2018) systematically evaluate ten classical heuristics for MaxCut on a library of large instances and use machine learning to predict which heuristic works best on a previously unseen problem instance, Abe et al. (2019) combine a GNN with a Monte Carlo tree scarch approach to learn a hcuristic for MaxCut. [eloborodov et al. (2020) use reinforcement lcarning in conjunction with a quantum-inspired algorithm to solve the Tsing energy minimization problem, which is equivalent to the MaxCut problem. [aralias & Loukas (2020) propose an unsupervised approach with possible solution to MaxCut. To address scalability challenges, Barrett et al. (2022) limits the costly GNN to a pre-processing step and introduces a recurrent unit for fast action selection. Schuetz et al.
theoretical guarantees to produce a distribution over subsets of nodes
(2022) reformulate MaxCut as a quadratic unconstrained binary optimization problem, removing binary constraints to create a differentiable loss func-
tion. Readers may refer to Mazyavkina et al. (2021) : Cappart et al. (2023) for further insights into learned
heuristics for MaxCut.
3 The MaxCut-Bench Benchmark
In this section, we formally introduce the Maximum Cut (MaxCut) problem as follows. Given an undirected graph G(V, E, w), where V represents the set of vertices, E denotes the set of odges and weights w(u, v) on the edges (u, u) E, the goal is to find subset of nodes S V that maximizes the objective function, f(S) Enes.ve'ss w(u, v). Next, present comprehensive overview of the setup for MaxCut-Bench. We provide the general selection criteria and considerations for algorithms (Section 3.1 and datasets (Section 3.2
3

---

Published in Transactions on Machine Learning Research (04/2025)
Table 1: Categorization algorithms and datasets used in our evaluation.
Algorithms
IP solver
CPLEX, GUROBI
Classical Heuristics
SEMIDEFINITE PROGRAMMING, GREEDY, TABU SEARCH, EXTREMAL OPTIMIZATION S2V-DQN, ECO-DQN, LS-DQN, RUN-CSP, ANYCSP, GrLOWwCOMBOOPI
GNNs
Quantum Annealing
Leleu al. 2019
Leleu et al. (2021
Datasets
Random Instaces
Rénüs,Rényi, Barabási-Albert, Holme-Kim, Watts-Strogatz
Hard Instances
Gset, SK spin glass, Optsicom, Phase transition, Big Mac Library, MaxCut and BQP Instance Library
3.1 Benchmark Algorithms
Table the overall 16 algorithms integrated into our benchmark. They are divided into four categories and we briefly introduce each category in the following, and more details are provided in Appendix A.2
Classical methods. We include common classical algorithms, such as SEMIDEFINIE PROGRAMMING (SDP) and GREEDY, along with two local search algorithms: TABu SEARCH (TS) Glover 1990b and EXTREMAL OPTIMIZATION (EO) (Boettcher & Percus (2001). Both TS and EO incorporate strategies to escape local minima and explore the search space more effectively.
Mixed-Integer program solver. We select two commonly used commercial mixed-integer programming solvers: CPLEX and GUROBI.
GNN-based heuristics. We focus on works selected based on three primary criteria: being highly cited, recently introduced, widely used as benchmarks for evaluating learned heuristics. S2V-DQN, introduced by[Kaa Khalil et al. 20177) is seminal algorithm with thousands of citations and serves
baseline in numerous
subsequent studics (Li et al.
2018 Manchanda et al., 2019 Barrett et al. 2020 Sun et al. 2023). In addition
to replicating S2V-DQN, we include its extensions, ECO-DQN (Barrett et al. 2020) and LS-DQN (Yao el al.
2021). Furthermore, we incorporate RUN-CSI CSP (Tenshoff et al. 2021). a common baseline for recent neural
solvers (Schuetz et al.] 2022 Sun et al. 2022 Toenshoff et al.] 2021). Finally, we include two recent works:
GFLOW-COMBOPT (Zhang et al. 2023). highlighted at NeurIPS 2023, and ANYCSP (Tönshoff et al. 2022) published in TJCAT 2023.
Quantum annealing. We use two SOTA quantum annealing algorithms (eeleu et al. 2019 2021 to obtain the best (possibly optimal) solutions within a cutoff time of hour. All approximation ratios reported the paper are based on the best solution found by either of the two solvers.
3.2 Benchmark Datasets
We have gathered a diverse collection of instances from both real-world datasets and random graph distri- butions, as detailed Table which are based on the following criteria:
Random Instances. To ensure thorough comparison, we use commonly employed random graph models
for instance generation, including Erdös et al. (1960) (ER), Albert & Barabási (2002) (BA), Holme & Kim 22002) (HK) and Watts & Strogatz (1998) (WS).
Hard Instances. We select datascts that have been employed for evaluating the performance of sev-
eral SOTA (raditional heuristics (Benlic & Hao 2013 Leleu et. al. 2019 2021 Hamerly et al. 2019). Kirnhttoon-Kikartiiickkk (SK) spin glass (Sherrington & Kirkpatrick 1975). dense
These datasets include
unweighted instances at their phase transitions (Coppersmith et al.) (2004). Optsicom project (Corberán
et al. 2006). Big Mac Library (Rendl et al. 2010), MaxCut and BQP Instance Library (Bonn] 2010) and
Stanford Gset dataset
YYe 2003).
4

---

Published in Transactions on Machine Learning Research (04/2025)
For more comprehensive description of all mentioned datasets and the hyperparameters used for graph generation, please refer to Appendix A.1
4 Experiments and Analysis
In this section, we use the benchmark to investigate the objective value, inference time, scalability and generalization of algorithms by answering the following specific questions:
How effective are the algorithmms frequently used as baselines in the literature? We observe that commonly used baselines for evaluating learned heuristics, such CPLEX, SDP, and GREEDY, often fail to pro- vide strong comparisons, as their performance is frequently surpassed by simple stochastic local search algorithms, such as TS and EO (Section 4.1..
Does deep learning combined with clossical heuristics improve the performance of classical heuristics? While S2V-DQN and LS-DQN demonstrate improvements over local search by incorporating GNNs, we have noted that the GNN ECO-DQN can be effectively replaced by lincar regression without any loss in performance. (Section 1.2..
Can learned heuristies consistently outperform simple, general-purpor purpose heuristics? Except for ANYCSP, the answer is generally no. We demonstrate that several learned heuristics do not outperform TS and EO (Section 4.3
Can learned heuristics mainlain their effecliveness when applied to vul-of-distribuul inslances beyond their training data? Again, except for ANYCSP, the answer is no. We observe a substantial decline in performance when learnod heuristics are tested on graph distributions different from the training set, with ANYCSP being a notable exception (Section 4.4).
How efficient are these algorithms in terms of time and space on large hard instances? Classical local search heuristics tend to outperform most learned heuristics while using minimal computing resources and inference time, although their performance does decrease as the problem size increases (Section 4.5)
All learned algorithms in our benchmark are implemented using PyTorch (Paszke et al., 2019). All experi- ments were conducted a Linux server with GPU (NVIDIA RIX A6000) and CPU (AMD EPYC 7713),
using PyTorch 2.3.0, DGL 2.2.1 (Wang, 2019) and Python 3.11.9. We clearly state the changes necessary to update previous implementations and ensure that our reimplementations align with the results published in the literature. We provide all the details of these changes in Appendix [A.4
Evaluation settings. All training is performed on randomly 4000 generated graphs and the validation is performed on a fixed set of 50 held-out graphs from the same distribution. For synthetic datasets, testing is performed on 100 instances drawn from the same distribution; or upon the test instances provided in the original resource (see details in Appendix A.Ij. We evaluate the algorithms using the average approximation ratio as a performance metric. Given an instance, the approximation ratio for an algorithm is computed by normalizing the objective value of the best-known solution for the instance. As S2V-DQN is deterministic at test time, we use a single optimization episode for cach graph. For all other algorithms, algorithm for 50 randomly initialized episodes with 2|V| number of search steps per episode and select the best outcome from these runs following the experimental setup of Barrett et al. (2020) and Yao et al. (2021). Experimentally, we have found that the performance of all algorithms saturates within this number of search steps (we refer the reader to Appendix A.6 for more details).
run cach
Summary of results. In Figure 1 we present an overview of the performance of all heuristics, excluding the two quantum annealing algorithms specifically used to find the best-known solutions with one-hour cutoff time. Our key findings include the following: classical heuristics are often faster while providing solutions of similar or better quality; the GNN used in ECO-DQN can be replaced by lincar regression without any performance degradation; and a recent solver, ANYCSP, based on global search, can provide competitive solution quality but requires significantly greater computational resources.
4.1 Effectiveness of Common Baselines in Evaluating Learned Heuristics
In this section, we analyze the performance of the common classical basclines that are used for comparing the performance of learned heuristies for MaxCut. The main question we address whether outperforming certain heuristics is significant. For this evaluation, we use the dataset. from Barrett et al. 2020), where
5

---

Published in Transactions on Machine Learning Research (04/2025)
Unweighted Datasets
Weighted Datasets
ANYCSP
1.00
Gurobi
ANYCSP
ECO+LR
Mean Approximation Rabio
Gurobi
0.98
TS
ECO+LR
ECO-DQN
0.99
ECO-DON
EO
LS-DQN
Mean Approximation
0.96
EO
LS-DQN
S2V-DQN
CPLEX
RUN-CSP
0.94
RUN-CSP
SDP
S2V-DQN
Greedy
0.90
Gflow-CombOPT
0.88
Greedy
CPLEX
SDP
10"
10a
10
10a
Mean Time (s)
Mean Time (s)
Figure 1: Comparison of the performance between learned and classical heuristics. Classical heuristics, such as EO and TS, often outperform most learned heuristics while being faster. Note that we include GREEDY, which starts with a random solution rather than an empty one, as opposed to Zhang et al. 2023
1.0
1.0
Mean Approx. Ratio
Mean Approx. Ratio
0.8
0.8
0.6
0.4
0.4
Gurobi
TS
Greedy
EO
0.2
0.2
SDP
CPLEX*
20
40
100
200
500
20
40 60
100
200
500
Graph Size,|V|
Graph Size.
(a) ER (Brrettt et 2020
(b) BA Barrett al. 2020
Figure Performance comparison of classical baselines. The most common basclines, GREEDY, SDP, and CPLEX, can be easily oulperformed by classical local search heuristics *Values (10-minute cut-off time) reported in Barrett et al. (2020)
optimal or best-known solutions are publicly available. This dataset consists of ER and BA graphs up to 500 vertices.
As shown in Fig. CPLEX performs relatively well on graphs with up to 60 vertices but shows a significant drop in performance for graphs with 200 and 500 vertices due to the large solution space. similar drop in CPLEX performance for larger graphs was reported by Khalil et al. (2017). The GREEDY algorithm is robust across distributions but typically performs 20% worse than the best-known solutions. Similarly, SDP performs slightly better than GREEDY but still exhibits an optimality gap of 10-15%. In contrast, GUROBI finds solutions close to the best-known values very quickly, within 10-second time limit.
F.O and TS consistently outperform match GREEDY, SDP and CPLEX, demonstrating their competitive- ness as heuristics. However, their performance declines as instance size increases (see Fig. 3
Final Considerations. We conclude that while improvements over commonly used baselines, such as GREEDY, SDP, and CPLEX, are incremental, simple modifications to local search can outperform these baselines by a significant margin. This highlights the need for more work to standardize baseline selection for the empirical evaluation of CO problems.

---

Published in Transactions on Machine Learning Research (04/2025)
Table 2: Summary of the learned algorithms that improve upon local search.
Algorithm
Initial Solution
Node Features
Action
Reward
Termination
Simplified Algorithm
all marginal gains
Greedily add, starting with
S2V-DQN
Empty
Vertex State
Add
Marginal gain
are negative
empty solution
Ardd or Delete
Self- termittmminnion or
Grodily add/delete, starting with random solution
LS-DQN
Random
Vertex State
-Marginal gain
2/V] stepe
Vertex State
max (eurrent objective value-
Marginal Gain
Add Delete
best objective value).0) small reward if new
ECO-DQN
Random
2/V] sleps
TABU SEARCH
Time Since Flip
local minima is found
4.2 Impact of Integrating Deep Learning with Local Search
In this subsection, we examine whether deep learning heuristics that combine local scarch with a neural network provide any improvement over local search alone. The pipeline of this category of algorithms is as follows: handcrafted node features are generated at each step of the algorithm, and passed through a GNN to generate node embeddingg.. These embeddings are fed into a reinforcement learning (RL) algorithm, which selects the action take. The action involves either selecting a node to add to delete from the solution. Taable@summat
the key differences between these algorithms. Next, we discuss each algorithm and investigate the causes of some of the unexpected outcomes presented in our paper.
S2V-DQN. S2V-DQN starts with an empty solution and incrementally adds a vertex, guided by a GNN until no greedy actions remain. The concept can be simplified to greedily adding the node that results in the largest improvement in objective value; we refer to this as S2V-Simplified. From Fig. g we observe that S2V. DQN outperforms GREEDY and S2V-Simplifid in four out of five distributions from the well-known Gset benchmark dataset, typically by margin of 10-20%. Since GREEDY was reported as the best competitor to S2V-DQN by Khalil et al. (2017), this confirms that our implementation successfully reproduces the performance reported in the original work (See more details in A.4.I). This improvement is impressive, showing the promisc of using GNNs to improve classical hcuristics.
However, from Fig. 3 and Table 3 we observe that TS and EO two simple local search houristics with a single parameter outperform S2V-DQN in almost all cases, typically by a margin of 5-10%. In fact, even starting from a random solution and applying the GREEDY algorithm outperforms S2V-DQN on certain distributions, usually by a small margin, such as ER (weighted and unweighted), BA (unweightod), and Phase Transition networks, as shown in Table 3 This demonstrates the power of stochasticity when combined with local search.
LS-DQN. Following in the footsteps of S2V-DQN, LS-DQN starts with a random solution and adds or deletes from a node from the solution at each step guided by a GNN. LS-DQN improves the performance of its simplified version as shown in Table B especially for weighted instances.
However, our analysis contradicts the claim of Yao et al. 20211 that LS-DQN matches the performance of ECO-DQN. This may be explained by observing that Yao et al. (2021] compared the performance of ECO- DQN and LS-DQN only on complete graphs, which underscores the importance of comparing algorithms across a range of instances.
ECO-DQN. While S2V-DQN and LS-DQN use the current solution as the state-space representation for the RL agent, ECO-DQN proposes six additional handcrafted features per vertex for its state space. We observe that two of these features are closely related to the traditional hcuristic, TABU SEARCH (TS): 1) Marginal Gain: the change in the objective value when a vertex is added to removed from the solution set (we refer this action as a flip) 2) Time Since Flip: steps since the vertex has last been flipped to prevent short looping trajectories.
We first describe how the TS algorithm works to clarify why TS can be considered a simpler version of ECO-DQN. TS selects the node flip that results in the maximum increase in the objective value, provided the time since the last flip of the node exceeds specified hyperparameter. This approach helps TS actively
7

---

Published in Transactions on Machine Learning Research (04/2025)
Toroidal (Weighted)
ER (Weighted)
Planar (Weighted)
Mean Approx, Ratio
Mean Approx, Ratio
Mean Approx, Ratio
0.95
0.95
0.9
0.90
0.90
0.8
0.85
0.85
0.80
0.80
0.7
2000
4000
6000 80001000
2000
4000
6000
2000
4000
6000
Graph Size,/V|
Graph Size,
Graph Size,
Planar (Unweighted)
ER (Unweighted)
Mean Approx. Ratio
0.99
Mean Approx. Ratio
1.000
S2V-Simplified Greedy
0.975
0.98
TS
0.950
SZV-DQN
0.97
0.925
EO
0.900
0.96
0.875
2000
4000
6000
2000 4000 6000 800010000 Graph Size,
Graph Size.
Performance comparison of S2V-DQN and classical approaches. S2V-DQN outperforms its sim- plified version and GREEDY by significant margin, consistent with Khalil et al. (2017). See Table 11
Figure 3:
Performance comparison of learned heuristics with their simple counterparts (best in bold): The first and second halves of the table show results for unweighted and weighted instances, respectively.
Table 3:
S2V-DQN
LS-DQN
ECO-DQN
Graph
Nodes
S2V Simplified
S2V+GNN
GREEDY
LS+GNN
TS
ECO+LR
ECO+GNN
Gaet (ER)
800
0.970=00000
0.970
0.985
0.99220.001
0.999:0.00 001
0.996
0
Gset (Planer)
0.960
0.980=0.001
0.96g40.002
0.984=0.002
0.992=0.000
0.991 #00001
0.990=0.00
BA
800
0.938+0.007
0.951+0.000
0.952#0.008
0.983=0.008
0.992#0.002
0.993=0.00
0.991 0.991 #0.002
WS
800
0.911#0.000
0.97340.000
0.92749.002
0.971#0.000
0.990
0.988 4:0000
0.988
0 0.9922:00
HK
800
0.939
0.966
0.951
0. 0.98.1t0.008
0.992
0.992=0.002
0. 7..922
Phose Transition
100-200
0.982
0.985+0.000
0.906-00.00
0. 0.900=00002
1.000=0.000
1.000=0.000
1.000 000
Geet (ER)
800
0.856250.026
0.906#0.017
0.911 1000022
0.95320.0m
0.995 ons
1:00000000 0.981
0.981
0.984
Cset (Planar)
800
0.863
0.890=0.027
0.871#0.013 #00.03
0.9.2=00000
0.980=0.000 000
0.975 +00006
0.9 0.966=00000
Geet (Toroidal)
800
0.838
0..60
0.793
0.963=0.007 007
0.98g20.00o
0.993
0.994 002
BA
0.853#n.019
0.88G=0.0lD
0.855+900122
0.93J40.011
0.97840.007
0.979=0.00s
0.972=0.009
WS
20.014
0.919
0.833:20.010
0.92320.00
2.907
0.973=0.006
0.96120.00s
0.857
0.908
0.855
0.93720.000
0.977
0.978=0.006 0.0
0.97.=0.000
Barrett (ER)
0.866
0.95140.024
0.9544400044
0.987220000
1.000=00.0 001
1.000=0.001
1.000 001
Barrett (BA)
0.849:00.64
0.93740.043
0.903
0.977#0.032
0.984=00.0 oua
0.98-4=0.08z
0.983=0.00 053
SK spiu-glass
70-100
0.805
0.939
0.994
0.999
1.000
1.000
1.000
Optsicom
125
0.709
0.962#0.028
0..022
0.991
1.000=0.00m
1.000
1.000 000
avoid revisiting previously explored points in the search space. However, if flipping a node results in the best objective value found so far, TS overrides this restriction and flips that node.
Now looking at the reward function defined in ECO-DQN, we see the algorithm trains its agent to avoid revisiting the same local minima by providing small reward (referred as the immediate reward in the original paper) when the agent discovers new local minimum. Additionally, ECO-DQN encourages the agent to select. the node that gives the best objective value found far. Intuitively, this reward mechanism
8

---

Published in Transactions on Machine Learning Research (04/2025)
should encourage the selection of nodes with high time since the last flip and those that yield the best objective value.
To better understand the performance of ECO-DQN, we compare it with TS and an ablated version of ECO-DQN, called Tabu (ECO+LR). SoftTabu replaces the GNN with linear regression and omits the features not related to TS, that is, all but the two features described above.
From Table 3 we observe that and Soft often match or even outperform ECO-DQN (ECO+GNN) in terms of performance. To further validale this observalion, we conduct empirical experiments based on the original paper, using the publicly available implementation of ECO-DQN provided by the authors without any modifications. The results are then compared with TS and ECO+LR (sce Appendix A.4.2).
We use a paired t-test to compare different methods and conclude that there no significant performance difference between ECO-DQN and simpler counterparts (as shown in Table 12 In fact, adding the GNN adversely affects the generalization performance of ECO-DQN (as discussed in Section 4.4
Mean Approx. Ratio
1.00
Planar (Unweighted)
Mean Approx Ratio
0.98
Planar (Weighted)
Mean Approx. Ratio
1.00
Toroidal (Weighted)
0.95
0.96
ECO-DQN
0.95
0.90
0.94
ECO+LR
0.85
LS-DON
0.92
0.90
0.80
TS
0.90
0.85
2000
4000
6000
2000
4000
6000
2000
6000
8000
Graph Si
Graph Size,IV|
Graph Size.
Mean Approx. Ratio
ER (Weighted)
Mean Approx. Ratio
ER (Unweighted)
1.0
1.00
0.95
0.8
0.90
0.6
0.85
2000
4000
6000
2000 4000 6000 8000 10000 Graph Size.
Graph Size.
Figure Performance comparison of ECO-DQN, LS-DQN, and classical approaches. Replacing GNN ECO-DQN with linear regression does not hurt performance, underscoring the need for ablation studies. Results are also shown in Table 11
Ablation Studies in Algorithm Design. We observe that the highly cited ECO-DQN does not exhibit performance gains from the inclusion of deep learning. To clearly establish the contribution of the deep learning component, we strongly recommend conducting ablation studies for any proposed algorithm.
A New Approach to Heuristic Optimization. S2V-DQN and its subsequent refinement, LS-DQN, serve as proof of concept that, despite not surpassing all baselines, they introduce a novel paradigm for improving heuristics by replacing handcrafted rules with machine learning. At the same time, our extensive analysis using MaxCutBench underscores the importance of benchmarking against simple heuristics to gain meaningful insights and measure progress comprehensively.
Final Considerations. As instance sizes increase, the performance gap between the best-known solutions across learned heuristics grows significantly. This limitation highlights the challenge of enabling agents reason effectively about larger systems, creating opportunities for future research.

---

Published in Transactions on Machine Learning Research (04/2025)
Table 4: Average Approximation ratios of classical and learned heuristics (best in bold);" denotes no reasonable result is achioved by the corresponding algorithm and the first and second halves of the table show results for unweighted and weighted instances, respectively.
Classical Heuristãcs
Learned Heuristics
Graph
Nodes
BO
TS
S2V-DQN
LS-DQN
EC0-DQN
RUN- CUP-
CFLOW-COMBEE
ANYCSP
Gaet (EIR)
800
0.095
0. 0.999-0.001
0.970=90001
0.9 0.970440.00
0
0.982440.011
0.979
0.999=0.000
Gset (Planar)
0.002
0.880=4.20
0.900
4.967
0.997
BA
800
+.983+
0,99246.00
0.951=0.905
0 0.961 0.961#0.00s -0000s
0.991 =0.002
0.97
0
1 000000000
WS
800
0.979
0.97g 0.973=20.05
0.902
0.978
0.55g to0.00
0. 1..99 1999-0.00
HK
0.98g.o..0s Lo.0c3
0,982 Lo
0.966 10..0
1.900 10.000
0.902
0.977 Lo.003
0.930 0.933-10.005 10.005
0,000 0 o0n
Phuse Transition
100-200
4.000
1.0000.000
0.983=0.005
0 4.985-
1.000*0.000
4.994
0.99g
1 1.000=0.00
Gaet (ER)
800
0.973+0.006
0.995+50.088
0.90g=0.0L7
0090e0.0177
0,98-j50.00
0.90940.007
0 1..99-00000
Gset (Planar)
800
0.954
0.800=w..at
0.800 0.800-40.co7 10000r
0.908
0.925
0.995 2. 0.000
Gees (Toroidal)
800
0.94g
0,989 Lo.00
0.900-9..03
0. 0.900-10.o0
0.90g_10.002
0.976-12.00
0. 1.999- 002
BA
0,919
0.978
0.886=0.013
088
0.97220.00p
0..01
1.000000000
WS
800
0.943 0.943-60.07
0.967
0.919-0.212
0.3 0.919-10.002
0.961
0,950-1.007
O. 1.999-
HK
800
0,919
0.977 oor
0.90g=0.017
0 0000-000177
0,97:/20.00 000.00
0.937
1 0.0000 000
Barrest (FR)
200
Lo.0s
1.000 u.
0:951 119.000
0.961 110.00
1.000 1.0. 001
0,940-1..ur
0,000 000
Barrett et sl. (BA)
200
0.969440.035
0.93729.003
0 0,937400.0x oes
0
0.95g
O. 989 032
spin-glase glass
0.995
1.000 0.0000.000
0.939-2u.oup
2.939 10.000
1.000-.0.00
0.96240.0u
1..000-0.00 -0.00000
Plysies (Regular)
125
0.98644.001
1 1.000-0000
0,902-10.es
0.902-10.oo
1.000
0,989-10.0
1 1.000
4.3 Performance Comparison of Learned Heuristics and Simple Heuristics
In this section, we evaluate the algorithms to assess whether any of the deep learning heuristics can achieve the SOTA objective value on the instances in the MaxCut benchmark. While it may be too early to expect Icarned hcuristics to beat SOTA heuristics tailored for specific problems, the question of how learned heuristics fare against simple heuristics remains unanswered. One of the main reasons for this is the variely of baselines and instances used in existing work (more details can be found in Appendix A.3
Gset(ER800)
Gset(Planar8000
BA800
WS800
1.000
1.00-
1.00
1.00
Mean Approx, Ratio
0.995
0.99
0.98
0.99
0.98
0.990
0.98-
0.97
0.985
0.96
0.96
0.97
0.980
0.94
0.95
0.975
0.96
0.94
0.92-
0.93
0.970
0.95-
Greedy
ECO ECO-DON DON
RUN- CSP
Gflow- CPMbOPT
EO
TS
ANYCSP
Greedy
ECO DQN
RUN- CSP
Gflow Gflow-Combl CPM
EO
TS
ANYCSP
Greedy
ECO ECO-DQN DQN
RUN- CSP
Gflow COmbOPT
EO
TS
ANYCSP
Greedy
ECO DQN
RUN-CSP
EO
TS
ANYCSP
Gflow Gfow-CombOPt
Figure 5: Violin plots of mean approx. ratio for learned and classical heuristics on a selection of unweighted instances. Among the learned heuristics, onlo only ANYCSP outperforms the classical heuristics.
Impact of findings. We compare learned local search heuristics (S2V-DQN, ECO-DQN and LS-DQN), COP RUN-CSP, and ANYCSP with the traditional heuristics EO and TS. Our results show that EO and TS can either outperform or achieve comparable solution quality to learned local search heuris- tics. Additionally, we observe that EO and TS can outperform GFLOW-COMBOPT and RUN-CSP, especially on larger instances, while ANYCSP usually outperforms them by a margin of 2-5%. Next, we discuss our empirical observations for each algorithm.
Learned Local Search Heuristics. Similar our observation for TS in Section 4.2 EO can match or even surpass the performance of learned local search heuristics. While ECO-DQN performs slightly better
10

---

Published in Transactions on Machine Learning Research (04/2025)
than EO, this outcome is expected, TS also outperforms EO, and significant differences observed between these methods.
From Table 4 observe that TS outperforms RUN-CSP on all distributions, while EO out- performs RUN-CSP on most distributions. Although RUN-CSP is commonly used as a baseline in recent
RUN-CSP.
neural CO solvers (Karalias & Loukas 2020: Sun et al. 2022 Schuetz et al., 2022 Tönshoff et al. 2022) it is worth noting that its performance can be readily exceeded by classical heuristics. This underscores the importance of choosing robust baselines to highlight meaningful improvements.
We restrict our empirical evaluation of GFLOW-COMDOPT to unweighted instances because Zhang et al. (2023) only evaluated SFLOW-COMBONE for MaxCut on unweighted BA graphs, fol- lowing Sun al. (002)), and our attempt to adapt GFLOW-COMBER
Gflow-Comble
to handle weighted graphs performed poorly and did not surpass GREEDY. From Table and Figure 5 we observe that TS and EO consistently outperform GFLOW-COMBE
In our opinion, this example highlights the need for more standardization in evaluation, as GFLOW-COMBOPT is often outperformed by naive local search heuristics.
We analyze ANYCSP in its default configuration and observe that it consistently finds near- optimal solutions (that is, solutions near the value found by the Quantum Annealing algorithms), and is superior in value to TS and the other traditional local search algorithms. These promising results demonstrate that ANYCSP can effectively learn the solution structure across diverse graph distributions and remains robust across multiple distributions.
ANYCSP.
Final considerations. The empirical findings suggest that benchmarking against weak heuristics on a very particular of instances may establish low standard, potentially leading a misleading sense of achievement. Hence, selecting appropriate baselines is crucial to accurately assess the effectiveness of learned heuristics. At minimum, recommend that any work should at least include simple algorithms that improve upon GREEDY failure to consistently beat the naive baselines suggests that the algorithı may need further development.
4.4
Generalization Capabilities of Learned Heuristics
Trained on ER(weighted) distribution
ER(unweighted)
ER(weighted)
Skew(unweighted)
Skew(weighted)
Torodia([weighted)
1.0
1.0
1.0
1.0
Aрprox. Ratio
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.0
Trained on Torodial(weighted) distribution
1.0
1.0
1.0
1.0
1.0
Approx. Ratio
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
ECO-DON
LS-DON
SoftTabu:
52V-DQN
ANYCSP
RUN-CSP
EO
15
0.0
LS-DON
SoftTabu
52V-DON
ANYCSP
RUN-CSP
EO
ECO DON
LS-DON
SoftTabu
S2V-DON
ANYCSP
RUN-CSP
0.0
ECO-DON
LS-DON
SoftTabu
$2V-DON
ANYCSP
RUN-CSP
EO
19
0.0
ECO DON
LS-DON
SoftTabu
S2V-DON
ANYCSP
RUN-CSP
EO
T5
ECO-DOn
Figure 6: Generalization of algorithms for unseen distribution. The inclusion of GNN in ECO-DQN hurts
generalization, and except for ANYCSP, all other heuristics perform poorly.
The ability of learned heuristics to perform well on wide range of distributions, even if these distributions not represented during training, is highly desirable characteristic for practical CO problems (Cappart
11

---

Published in Transactions on Machine Learning Research (04/2025)
Many works include experiments to assess how well the heuristic generalizes. Often, this is in the form of training on smaller instances and generalixing to test on larger ones, although cross-distribution performance is also frequently assessed.
et al. 2023
Several learned heuristics such as ECO-DQN, LS-DQN, and S2V-DQN are claimed to exhibit promising performance across a diverse range of graph structures, including those not present in their training data. In this section, we evaluate the generalization performance using MaxCut-Bench.
Impact of Findings. From Figure we notice that there can be a substantial decline in performance when the learned heuristics are tested on graph distributions other than train distributions, with the notable exception of ANYCSP. In particular, observe that when trained the toroidal distribution (second row), the test performance of ECO-DQN, LS-DQN, S2V-DQN, and RUN-CSP may fall below 25% on several distributions. This outcome may be anticipated. Intuitively, we would expect a network trained on instances of a particular structure to adapt toward this class of instances and perform poorer for different structures. We observe that TS, SofuTabu, and EO seem to generalize well across wider distributions. Both TS and EO have a single parameter, which we optimized for the training distribution assess its generalization performance.
These results raise the possibility that the generalization of learned heuristics from learning over small and easy instances to testing on larger and more complicated ones may not be as robust the literature [Khaiil et al. 2017; Barrett et al. 2020 2022 Yao et al. 2021 suggests. This feature is often touted as an amelioration of the expensive training process required for the learned heuristics. Additional results from our generalization experiments on BigMac, MaxCut, and the BQP Instance Library can be found in A.5
4.5 Efficiency and Trade-offs in Large-Scale Instances
In this section, we analyze the efficiency and scalability of learned heuristics over ER graphs of size |V| 800 from the Gset dataset. For time efficiency, we evaluate the efficiency of the algorithms by mcasuring the wall-clock time. For scalability, we evaluate the average GPU and CPU usage per second of these learned algorithms. Due to space constraints, we report run-time and performance of each algorithm across datasets in Appendix 10
1.000
Mean Approximatio Ratio
0.975
Usage (MB)
6000
Meen GPU Usage
Usage Type
0.950
Mean CPU Usage
4000
0.925
2000
0.900
Algorithm
EO
LS-DQN
ECO+LR
S2V-DQN
Gflow- Coo--ComOOpt
ECO-DQN
ANYCSP
RUN-CSP
LS-DON
EO
TS
TS
ECO+LR
ECO-DQN
RUN-CSP
0.825
S2V-DON
ANYCSP
0.800
10-1
10a
10
10'
Time (seconds)
Figure 7: Comparison of the wall-clock time and average GPU and CPU memory utilization among heuristics. Iterative approaches, such as ANYCSP, ECO-DQN, and LS-DQN, take significantly more time.
we observe that algorithms that use multiple randomly initialized episodes (iterative approaches) require significantly more time and memory. We observe that ANYCSP takes the longest to complete and consumes the most memory, while classical heuristics are order of magnitude faster. This demonstrates a clear trade-off where the more accurate algorithms come with longer run-time.
Impact of Findings. From Figure i
5 Conclusion
In this paper, we introduce MaxCut-Bench, comprehensive benchmark for evaluating deep learning- based algorithms for the Maximum Cut problem, consisting of carefully selected instance distributions and
12

---

Published in Transactions on Machine Learning Research (04/2025)
implemented algorithms. We intend that BaxCuut-Bench will foster further research and refinement of learning-based algorithms, enabling more informed evaluations and comparisons. We regard our work as a long-term evolving project and are dedicated to its continuous development. Our roadmap for the future includes expanding its scope to cover a broader spectrum of CO problems, incorporating more cutting-edge models, and integrating newer and more challenging distributions of instances.
While one might expect that extensively tailored heuristics can outperform learned approaches, our empirical findings suggest that simple local search heuristics frequently outperform complicated GNN-based heuristics, Specifically, TARU SEARCH, a local search heuristic that tries to avoid solutions previously encountered, outperforms all but one of the evaluated learned heuristics across broad range of instance distributions. In addition, we show that ablating the GNN from ECO-DQN does not hurt its performance, and show evidence that ECO-DQN may simply be learning heuristic similar to TABU SEARCH. On the positive side, ANYCSP did show a modest improvement over TABU SEARCH, although it uses many times the computational resources. Further, we observe that in some cases using a GNN to guide a traditional heuristic can improve the performance of the original heuristic.
References
Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving np- ha-d problems on graphs with extended alphago zero. arXiv preprint 1rX:: 16623, 2019.
Réka Albert and Albert-László Barabési. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Maria Chiara Angelini and Federico Ricci- diece-Tersnnghi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29-31, 2023.
Francisco Barahona. On the computational complexity of ising spin glass modcls. Journal of Physics A: Mathematical and General, :511))3324,, 1982.
Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt, An application of combina- torial optimization to statistical physics and circuit layout design. Operations Research, 36(3):493 513, 1988.
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, pp. 3243 1230,250,22 2020.
Thomas D Barrett, Christopher WF Parsonson, and Alexandre Laterre. Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv preprint arXiv:2205. 1410,, 2022.
Dmitrii Beloborodov, Alexander E Ulanov, Jakob N Foerster, Shimon Whiteson, and AI Lvovsky. Reinforce- ment learning enhanced quantun-inspired algorithm for combinatorial optimization. Machine Learning: Science and Technology, 2(2):025000, 2020.
Una Benlic and Jin-Kao Hao. Breakout local search for the max-cutproblem. Engineering Applications of Artificial Intelligence, 2662)111 2013.
Stefan Boettcher and Allon G Pereus. Extremal optimization for graph partitioning. Physical Review E, 64 (2):026114, 2001.
Bonn. Benchmark library for qubo instances. http://bgp.cr cs. www.bo/m////bbarrt/a////ssneee html 2010.
Maximilian Böther, Otto KiBig, Martin Taraz, Sarel Cohen, Karen Scidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. arXiv preprint orXiv:2201.1049, 2022.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Samuel Burer, Renato DC Monteiro, and Yin Zhang. Rank-two relaxation heuristics for max-cut and other binary quadratic programs. STAM Journal on Oplimizalion, 12(2):503-58) 521, 2002.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1 2023.
Francis Chen, Brian Isakov, Tyler King, Timothée Leleu, Peter McMahon, and Tatsuhiro Onodera. cim- optimizer: simulator of the Coherent Ising Machine, October 2022. URL htttps://github.com mcmahon-late htt/ciimmppiizz/
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks. arXiv preprint Xrv: 170..10000000 000508845, 2017.
Don Coppersmith, David Gamarnik, MohammadTaghi Hajiaghayi, and Gregory B Sorkin. Random max sat, random max cut, and their phase transitions. Random Structures & Algorithms, 24(4):502 545, 2004.
Á Corberán, J Peiró, V Campos, Glover, and R Martí. Optsicom project. 2006.
Victor-Alexandru Darvariu, Stephen Hailes, and Mirco Musolesi. Graph reinforcement learning for combi- natorial optimization: A survey and unifying perspective. orXiv preprint arXiv:2404.064.9 2024.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embeddde modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1 5, 2016.
Iain Dunning, Swati Gupta, and John Silberholz. What works best when? a systematic evaluation of heuristics for max-cut and qubo. INFORMS Journal on Computing, 30(3):608 624, 2018.
Nada Elsokkary, Faisal Shah Khan, Davide La Torre, Travis $ Humble, and Joel Gottlieb. Financial portfolio management using d-wave quantum optimizer: The case of abu dhabi securities exchange. Technical report, Oak Ridge National Lab.(ORNL) Oak Ridge, TN (United States), 2017.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad, sci, 5(1): 17-60, 1960.
Paola Festa, Panos M Pardalos, Mauricio GC Resende, and Celso C Ribeiro. Randomized heuristics for the max-cut problem. Optimization methods and software, 17(6):1033-1006 2002.
Fred Glover. Tabu scarch: A tutorial. Interfaces, 20(4):74-94, 1990.
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):11115 1145, 1995.
Hayato Goto, Kosuke Tatsumura, and Alexander R. Dixon. Combinatorial optimization by simulating adia- batic bifurcations in nonlincar hamiltonian systems. Science advances, 5(4):caav3372, 2019.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL
Ryan Hamerly, Takahiro Inagaki, Peter L McMahon, Davide Venturelli, Alireza Marandi, Tatsuhiro Onodera, Edwin Ng, Carsten Langrock, Kensuke Inaba, Toshimori Honjo, al. Experimental investigation of performance differences between coherent. ising machines and quantum annealer. Science advances, 5 (5):eaau0823, 2019.
Christoph Helmberg and Franz Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10(3))673 696, 2000.
Keld Helsgaun. An effective implementation of the lin kernigan traveling salesman heuristic. European journal of operalional research, 126(1) (00(1)100-113)) 2000.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Petter Holme and Beom Jun Kim. Growing scale-free networks with tunable clustering. Physical review 65(2):026107, 2002.
IBM-ILOG. Oplex.
2023.
Chaitanya Joshi, Quentin Cappart, Maris-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. arXiv preprint arXiv:2006.0700 07054, 2020.
George Karakostas. A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms (TALG), 5(4):1-8, 2009.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for com- binatorial optimization on graphs. Advances in Newral Information Processing Systems, 33:6659 -672, 2020.
Richard M. Karp. Reducibility among Combinatorial Problems, pp. 85-103. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. 978-1-4684-2001-22
doi:
9. URL http:://doo..rg/..... 1007/
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Timothée Leleu, Yoshihisa Yamamoto, Peter T. McMahon, and Kazuyuki Aihara. Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity, Physical review letters, 122(4)) 040607, 2019.
Timothée Leleu, Farad Khoyratee, Timothée Levi, Ryan Hamerly, Takashi Kohno, and Kazuyuki Aihara. Scaling advantage of chaotic amplitude control for high-performance combinatorial optimization. Com- munications Physics, 4(1):266, 2021.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advonces in neural information processing systems, 31, 2018.
Shengcai Liu, Yu Zhang, Ke Tang, and Xin Yao. How good is neural combinatorial optimization? systematic evaluation on the traveling salesman problem. IEEE Computational Intelligence Mogazine, 18 13::14-28, 2023.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Learning heuristics over large graphs via deep reinforcement learning. arXie preprint orXiv:1903. 033339,3.033,, 2019.
Rafael Martí, Abraham Duarte, and Manuel Laguna. Advanced scatter scarch for the max-cut problem. INFORMS Journal on Computing, 21(1):26 38, 2009.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combi- natorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Alejandro Periomo-Ortiz, Neil Dickson, Marshall Drew-Brook, Geordie Rose, and Alán Aspuru- Guzik. Find- ing low-energy conformations of lattice protein models by quantum annealing. Scientific reports, 2(1):1-7, 2012.
Daniel Rehfeldt, Thorsten Koch, and Yuji Shinano. Faster exact solution of sparse maxcut and qubo prob- lems. Mathematical Programming Computation, 4553)4445-470, 2023.
Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele. Solving Max- Cut optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming, 121 12):3033 2010.
15

---

Published in Transactions on Machine Learning Research (04/2025)
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics- inspired graph neural networks. Nature Machine Intelligence, 4(4):367-37,, 2022.
David Sherrington and Scott Kirkpatrick. Solvable model a spin-glass. Physical review letters, 35(26): 1792, 1975.
Haoran Sun, Etash K Guha, and Hanjum Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint arXim:2077115522 2022.
Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference Machine Learning, pp. 32859 32874. PMLR, 2023.
Eric D) Taillard and Keld Helsgaun. Popmusic for the travelling salesman problem. European Journal of Operational Research, 272(2):420 429, 2019.
Egor Tiunov, Alexander E Ulanov, and AI Lvovsky. Annealing by simulating the coherent ising machine. Optics express, 27(7):10288-1000 2019.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:580607, 2021.
Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe. One model, any esp: Graph neural networks as fast global search heuristics for constraint satisfaction. arXiv preprinl arXic:2208. 10227, 2022.
Davide Venturelli and Alexei Kondratyev. Reverse quantum annealing approach to portfolio optimization problems. Quantum Machine Intelligence, 1(1-2):17-30, 2019.
Minjic Yu Wang. Deep graph library: Towards efficient and scalable deep learning on graphs. In ICLR workshop on representation learning on graphs and manifolds, 2019.
Duncan J Watts and Steven H Strogatz. Collective dynamics of wsold networks...... nature, 393(6)84): 440-442, 1998.
Yoshihisa Yamamoto, Kazuyuki Aihara, Timothee Leleu, Ken-ichi Kawarabayashi, Satoshi Kako, Martin Fejer, Kyo Inoue, and Hiroki Takesue. Coherent ising machines optical neural networks operating at the quantum limit. npj Quantum Information, 3(1):49, 2017.
Fan Yao, Renqin Cai, and Hongning Wang. Reversible action design for combinatorial optimization with reinforcement learning. arXio preprint orXiv:2102.07211 2021.
Weichi Yao, Afonso S Bandeira, and Soledad Villar. Experimental performance of graph neural networks on random instances of max-cut. In Wavelets and Sparsity XVIII, volume 11138, pp. 242-251. SPIE, 2019.
Yinyu Ye. The gset dataset. hutps//webbsaanforleed// xyye/xyye/Gsuu 2003.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial optimization problems with gflownets. arXiv preprint arXiv:2305.17010 2023.
A Appendix
A.1 Detailed Description of Datasets
In this section, we provide details on the datasets, groups of datasets, and random graph models used this paper.
16

---

Published in Transactions on Machine Learning Research (04/2025)
Barrett et al. (2020). This dataset consists of Erdös-Rényi and Barabási-Albert graphs (ER and BA respectively) with edge weights E {0, +1) and up to 500 vertices. We set the same parameters from the paper and generate ER graphs using p = 0.15 with edge weights w E {0, =1} for training and validation. Similarly, for BA graphs we use m = 4 with edge weights w E =00==1}. For testing, we use 100 test graphs from this distribution from this dataset.
Erdös-Rényi (ER). This well-known random graph model by |Erdö et al. (1960) connects each pair of vertices with a probability p. Following Yel (2003), we set the same parameters from the paper and generate graphs of size [V| 800 using p 0.06 with edge weights w E {0, and {0, for training and validation.
Barabási-Allers (BA). This random graph model by Albert & Barabási (002) iteratively adds nodes, connecting them to m already existing nodes. For our experiments, we generate graphs of size [V] = 800 using m = 4, with edge weights w E {0, =1 and w E {0, 13.
Holmo-Kini (HK). This random graph model by Holme & Kim (2002) similar to the BA model, includes an extra step for each randomly created edge that forms a triangle with probability p. We generate graphs of size |V| = 800 using m 4 and p p= 0.10, with edge weights E {0, and w E {0,1].
Watts-Strogatz (WS). The random graph model by Watts & Strogatz (1998) starts with a well-
structured ring lattice with a mean degree of k. In the next step, each edge is replaced with probability p by another edge sampled uniformly at random. This approach aims to preserve "small-world properties" while maintaining a random structure similar to ER graphs. We generate graphs of size [V] = 800 using
k= 4 and p = 0.15, with edge weights w E 10, and w E 1).
Gset. This dataset Ye 2003) is extensively used to benchmark classical heuristics (Benlic & Hao 2013
Leleu et al.] 2019 2021 for MaxCut. The dataset comprises three types of weighted and unweighted random graphs: ER graphs with uniform edge probabilities, Planar graphs with decaying connectivity, and regular Toroidal graphs. For generating training and validation distributions, we use the independent graph generator Rudy by Giovanni Rinaldi, which is used for generating Gset graphs as sourced from Ye (2003). For training and validation, we gencrate ER, the union of Planar, and regular Toroidal graphs for training and validation. The arguments for generating the graphs with Rudy are collected from HHllmeeg
& Rendl (2000).
Optsicom. This distribution comes from publicly available library of MaxCut instance and includes synthetic and realistic instances that are widely used in the optimization community (see references the library website). For training and validation, we generate similar distribution, and for testing, we make use of a subset of the instances available, namely ten problems from Ising Spin glass models in physics (the first 10 instances in Sct2 of the library) following Khalil et al. (017)) All ten instances have 125 nodes and 375 edges, with edge weights w E +1. Mnterrington-Kirkpattt
spin glass. This distribution contains dense Sherington-Kirkpatrinn in- stances with elements Jij E [-1,1] generated from ER graphs based on examples from Hamerly et al. (2019). We generate graphs of size 70 to 100 vertices for training and validation. For testing, we use instances with the best-known value provided in CIM-OPtimizer (Chen et al.) 2022).
Phase transition. This distribution contains dense unweighted instances from ER graphs at the phase transition (p = 0.5) (Coppersmith et al. 2004), based on examples from Hamerly et al. (2019). We generate graphs with 100 to 200 vertices for training and validation and make use of test instances provided in CIM-Optimizer (Chen et al.] (2022).
Big Mac Library. We select MaxCut instances from this dataset generated with Rudy, using edge weights E (0, +1). These instances were collected during the development of the Big Mac.
MaxCut and BQP Instance Library. This distribution comes from publicly available library of MaxCut instances 3 For testing, we select Ising spin glass instances with edge weights w E +1) and vertices ranging from 1000 to 2744.
A.2 Detailed Description of Benchmark Algorithms
All algorithms make use of 50 attempts, and the best solution found is reported, except for S2V, which is deterministic. Next, we provide details about each algorithm discussed in our paper.
17

---

Published in Transactions on Machine Learning Research (04/2025)
Mixed-Interger program solver.
Gurobi. GUROBI is a commercial mathematical optimization solver. In our experiments, we limit the number of threads to 10 and set cut-off time of 10 seconds.
Cplex. CPLEX is another popular optimization solver. We use similar settings as GUROBI for the experiments.
Classical Heuristics.
Greedy. The algorithm starts with an empty solution and groedily moves the node which results in the largest improvement in cut weight. until greedy actions are left.
Semdifinite Programming (SDP). SEMIDEFINITE PROCRAMMING is subset of convex optimization that involves optimizing a linear objective function over the intersection of the cone of positive semidefinite matrices and an affine space. In our experiments, we use cvxpy (Diamond & Boyd 2016) with default settings and limit the number of threads to 10 to ensure consistency with other methods.
Tabu Search (TS). The algorithm begins with an arbitrary solution and, at each step, selects a node to flip (either including or excluding it from the solution set) that results in the greatest increase in objective called Tabu Tenure.
value among the nodes that have not been selected for a specified However, if selecting node results in the best objective value found so far, TS disregards that rule. This algorithm continues searching for fixed number of steps even when no further immediate improvements can be made, thereby enhancing the search process by exploring a broader solution space and potentially discovering better solutions over time. Varions improved versions of this algorithm have been proposed Glover [990): we consider the vanilla version of the algorithm (sce Algorithm D. Further details can be lound in Glover (1990).
Extremal optimization (EO). The algorithm begins with an initial arbitrary solution and sorts the vertices by their descending marginal gain. It then defines probability distribution Pk k= where 1 k < [V] for given value of the parameter 7 to determine the likelihood of selecting each verlex based on its rank in the sorted list. At each step, an index k is sampled according to this probability distribution, and the membership of the selected vertex is flipped. This method allows the algorithm to escape local optima and explore the search space more effectively, thereby increasing the chances of finding better solutions. Similar to TS, it stops after a fixed number of iterations (see Algorithm 2 Further details can be found in Boettcher & Percus (2001).
GNN-based heuristics
The algorithm starts from an empty solution and incrementally constructs solutions by adding one vertex at each step to the current solution, guided by a GNN Once a vertex is added to the solution, it cannot be removed; other words, the algorithm does not reverse its earlier decisions. The state space of its RT. agent represented by the current solution. The algorithm stops when no action can improve the objective value. The reward function of the algorithm is simply the change in the objective value. Further details can be found in Khalil al. (2017).
S2V-DQN.
ECO-DQN. Unlike S2V-DQN, this algorithm starts with an arbitrary partition of vertices and allows reversible actions. Barrett et al. (2020) provides seven handcrafted features per node to represent the state space of its RL agent. At each step, it selects vertex and flips its membership. The RL agent often chooses vertices that do not correspond to the greatest immediate increase in the objective value (non-greody). Thus, it aims to strike a balance between exploitation and exploration of the search space. The algorithm stops after fixed number of iterations. It provides reward the RL agent only when a new solution has been found, which equals the difference between the new best solution and the previous best solution. Since the reward can be very sparse, the algorithm also provides small intermediate reward to the agent when the agent reaches a new locally minimal solution. Further details can be found in Barrett et al. (2020).
LS-DQN. Similar to ECO-DQN, LS-DQN allows reversible actions and starts with an arbitrary solution instcad of an empty onc. The state space of its RL agent represented by the current solution. At cach step, it selects a vertex and flips the membership of the selected vertex. It stops after a fixed number of iterations or can terminate its own. The reward function of this algorithm is defined as the negative
18

---

Published in Transactions on Machine Learning Research (04/2025)
Algorithm Tabu Search
1: Input: Instance G(V, E), Oracle f, Tabu Temure y, Maximum number of iterations moziter
2: Output: bestobj
Initialize current solution S random solution Initialize tabu list T' an empty dictionary Initialize best objective value bestobj +- f(S)
6: Initialize iteration counter iter <- 0
7: while iter < mariter do
8: bestmove + None
bestvalue + -00
10: for each vertex v V do
11:
Flip the membership of in to obtain S'
12:
Calculate objective value f(S")
13:
if f(S") > bestobj or (o T and f(8") bestvalue) then
14:
bestmove +-
15:
bestvalue < S(S")
16:
end
17:
end for
18:
Flip the membership of bestmove in
19:
Insert update bestmove in tabu list T with value equal to the tabu tenure y
20:
if f(S) > bestobj then
21:
bestobj < S(S)
22:
end
23:
for each vertex v in tabu list do
24:
Decrease labu tenure of e by
25:
if tabu tenure of is 0 then
Remove from 27: end
28: end for
29:
Increment iteration counter iter +- iter +
30: end while
31:
return bestobj
19

---

Published in Transactions on Machine Learning Research (04/2025)
Algorithm 2 Extremal Optimization Algorithu
Input: oracle f. graph G(V, E), initial solution So, tam т, maximum iterations mariter
1: Initialize current solution S Sn
2: Initialize probability distribution Ps x K- where 1 S s
3: Initialize best objective value bestobj +- f(5)
4: Initialize iteration counter iter t- while iter < mariter do Initialize list marginal gains for each vertex v V do Flip the membership of in S to obtain S' Calculate objective value f(S")
9:
10:
Calculate gain + - -
11:
Append gain to marginal_gainn end for
12:
13:
Sort vertices in descending order of marginal gains Select index &o according to the probability distribution Pk. Select the vertex Up that is in the k-th position in the sorted list
14:
15:
16:
Flip the membership of Uk in S to obtain new solution S
17:
if ((S) > bestobj then
18:
bestobj < f(5)
19: end
20:
Increment iteration counter iter + iter +
21:
end while
22:
return bestobj
value change of the objective function at each step. It generalizes to a variety of CO problems, like MaxCut and TSP. Further details can be found Yao et al. (2021).
Gflow-CombOpt. The algorithm begins with an empty solution. The formulation of the Markov decision process (MDP) for the generative flow network proceeds as follows: each step, it adds one vertex to the solution. After each action, it checks if adding the vertex would decrease the cut value. If so, it excludes the vertex, ensuring it is never added back to the solution. Despile starting with emply solution, the algorithm generates diverse solution candidates by sampling from a probability distribution in sequential decision-making process. Further detaíls can be found in Zhang et al. (2023)
RUN-CSP. The algorithm solves CO problems that can be mapped to binary constraint satisfaction problems (CSP). It employs a graph neural network as message-passingg protocol, with the CSP instances modeled a graph where nodes correspond variables and edges represent constraints. Like other GNN-based heuristics, it is not reinforcement learning approach; rather, the loss function optimize this algorithm is designed to satisly as many constraints as possible. The results show that it performs effectively on significantly larger instances, even when trained on relatively small ones. Further details can be found in Toenshoff et al. (2021).
ANYCSP. The algorithm is an end-to-end search heuristic for any constraint satisfaction problem. Tönshoff et al. (2022) introduced a novel representation of CSP instances, called the constraint value graph, which allows for direct processing of any CSP instance. The state space of the RL agent is represented by both the current solution and the best solution found far. At each step, the algorithm generates a soft assignment of variables within the CSP instance, enabling transitions between any two solutions in single step. To encourage exploration and prevent the scarch from getting stuck in local maxima, a reward scheme similar to ECO-DQN is employed. Notably, the RL agent does not receive a reward upon reaching an unseen local minimum. Empirical evidence has shown that this approach can compete with or even surpass classical SOTA problem-specific heuristics. Further details can be found in Tönshoff 2022
Quantum Annealing
20

---

Published in Transactions on Machine Learning Research (04/2025)
Quantum annealing algorithms start by framing the optimization problem an energy landscape of quantum system, with the solution being the state of the lowest energy. Initially, the quantum system is set in superposition of all possible solutions, which represents a high-energy state. The objective is to steer the system towards the lowest energy state, which corresponds to the optimal or near-optimal solution for the problem. Nexi, we describe two SOTA quantum annealing algorithis used in our benchmark.
Amplitude Heterogencity Correction (AHC). The algorithm maps the objective function of CO problems to the energy landscape of physical system called Coherent Ising Machine (Yamamoto el al., 2017). It relaxes the bimary vertex states of the MaxCut problem to continuous values and finds low- energy states efficiently. It finds solutions of better equal quality for GSet instances compared to those previously known from the classical SOTA heuristic Breakout Local Search (Benlic & Hao 2013). Chaotic Amplitude Control (CAC). To improve the scalability, this algorithm makes use of non- relaxational dynamics that can accelerate the sampling low-energy states to reduce the time to find optimal solutions. Further details can be found in Leleu et al. (2021).
A.3 Baseline and Instance Bias
In this section, we continue our discussion on the lack of consensus regarding instances and basclines. This inconsistency leads to a situation where empirical results in different research papers are oflen not comparable. We present an overview of common baselines used to evaluate the performance of learned heuristics for MaxCut in Table 5 In Section 4.1 our empirical analysis shows that classical local search heuristics such as TABU SEARCH (Glover 1990), EXTREMAL OPTIMIAAIION (Boettcher & Percus (2001) often outperform common baselines like GREEDY, SEMIDEFINTTE PROGRAMMING (SDP) (Goemans & Williamson, 1995) and CPLEX (IBM-ILOG gain insights into the performance improvements that learned heuristics offer.
2023 in practice. A comparison with these local search heuristics will help
Similarly, we observe from Table 0 that few heuristics actually evaluate their performance on hard instances that are used to benchmark SOTA houristics.
A.4 Reproducibility
In this section, we list all the changes we made to the previous implementations of algorithms and provide implementation details of the algorithms.
A.4.1 S2V-DQN
We use the publicly available implementation of S2V-DQN by Barrett et al. (2020) as our initial codebase for implementing S2V-DQN. This implementation had poor scalability because it used dense representations of graphs. It also could not handle distributions containing graphs of different sizes because dense repre- sentations of graphs of different sizes cannot. be batched together. Therefore, we reimplement it to ensure it scale up easily to larger instances. To ensure a fair comparison, we evaluate the performance of our implementation against pre-trained models provided by Barrett et al. (2022) From Figure observe that we have successfully reproduced the performance reported in the literature.
*Code available at:
Table 5: Overview of common baselines to evaluate the performance of learned heuristics.
Basclines
Operation Research
Classical Heuristics
Learned Heuristics
Approach 4
CPLEX
GUROBI
SDP
GREEDY TS EO S2V-DQN
ECO-DQN RUN-CSP
S2V-DQN
ECO-DQN
LS-DQN
RUN-CSP
ANYCSP
Gflow-Comb
21

---

Published in Transactions on Machine Learning Research (04/2025)
Algorithms +
S2V-DQN ECO-DQN
LS-DQN
RUN-CSP
ANY-CSP
GFLOW-COMBOPT
Datasets +
ER
BA
Regular
Gset
Table 6: Overview of common datasets to evaluate the performance learned heuristics.
Mean Approx. Ratio
1.00
Mean Approx. Ratio
1.0
0.95
0.9
S2V-DQN (OURS)
0.90
S2V-Simplified Greedy
0.85
S2V-DON (Pre-trained)
0.8
0.80
0.75
50
100
150
200
50
150 Graph Size,
100
200
Graph Size,
(a) (Barrett
2020
(b) Barrett al. (220
Figure 8: Performance comparison of S2V-DQN for reproducibilit;; Note that for BA graphs with 60 vertices, were unable to load the pre-trained model for S2V-DQN.
A.4.2 ECO-DQN
Similar to S2V-DQN, we use the publicly available implementation of ECO-DQN and make similar im- provements we did for S2V-DQN. To ensure reproducibility, we compare our implementation with the pre-trained networks provided by [Brrett et al. (2020). From Figure 9 we observe that we have successfully reproduced the performance reported in the original paper.
Mean Approx. Ratio
1.000
Mean Approx. Ratio
1.000
0.995
0.995
0.990
0.990
ECO-DQN (OURS)
0.985
0.985
ECO+LR
0.980
ECO-Simplified ECO-DQN (Pre-trained)
0.980
0.975
50
100
150
200
50
100
150
200
Graph Size
Graph Size,
(a) BA |Brrettt et al. 2020
(b) ER
Barrett al. 2020
Figure 9: Performance comparison of ECCO-DQN for reproducibility
22

---

Published in Transactions on Machine Learning Research (04/2025)
Finally, tested agents trained weighted ER graphs with |V] = 200 on real-world datasets and hard instances, following the experimental setup of Barrett et al. (2020). From Table 7 we observe that ECO+LR outperforms ECO-DQN, except for ER graphs where ECO-DQN performs slightly better than ECO+LR.
Table 7: Average approximation ratios on known benchmarks: The second half of the table shows results for extended experiments.
Dataset
Type
Nodes
BC0-Simplified
ECO+LR ECO-DQN((re-trineel) ECO-DQN(OURS)
Physics
Regular
125
1.000
1.000
1.000
1.000
G1-10
ER
800
0.989
0.984
0.994
0.990
G22-31
ER
2000
0.953
0.977
0.974
0.981
A.4.3 LS-DQN
Since the LS-DQN codebase was not publicly available initially, we contacted the authors. Unfortunately, their codebaso" is designed specifically for clustered graphs and is not suitable for training on arbitrary graph distributions. The authors did not provide details about their configuration and hyper-paraneter settings in the paper. However, we were able to replicate similar improvements over RG using the GNN, as reported in the paper (see Table 3
A.4.4 Gflow-CombOpt
For unweighted instances, we utilize the original implementation of CFL.OWCCOBORS with the default configuration. For weighted instances, we incorporate weighted graph convolution to utilize edge weights and make necessary adjustments to ensure that vertex is added to the solution set only if it improves the cut value compared to not including it. However, we observe poor empirical performance of the algorithm for weighted instances. Therefore, we restrict our empirical evaluation of Wrrlow-ComOOTTT to unweighted instances.
A.4.5 RUN-CSP and ANYCSP We use the PyTorrc implementation of RUN-CSP[ and ANYCSI with the default configuration.
A.4.6
CAC and AHC
We use the implementations of these two algorithms provided by Chen et al. (2022) and tune their hyper- parameters using Bayesian Optimization Hyperband.
A.4.7 TS
To tune the value of tabu tenure, we run grid search with step size of 10, starting from 20 to 150, over the validation dataset and use the tuned tabu tenure for testing. We report the parameters used for our experiments in Table g
A.4.8 EO
To tune the value of tau, we run a grid search with a step size of 0.1, starting from 1.1 to 1.9, over the validation dataset and use the tuned tau for testing. We report the parameters used for our experiments in Table
A.5 Additional results on generalization
Due to space constraints, we present the results of the generalization of learned and classical hcuristics that are trained on skewed graph distribution of size |V]= 800 from Gset and tested various distributions of size V 2000 from Gset. From Figure 10 we observe that simple heuristics match or outperform the performance of learned heuristics. In addition, we train all learned heuristics on ER graphs from Barrett
ct al. 2020) dataset and test on BigMac MaxCut, and BQP Instance Library. From Figure we observe
"Code available at:
6Code available at:
"Code available http::///..hbbbbbmoooo////////ss
&Code available atchtips:
23

---

Published in Transactions on Machine Learning Research (04/2025)
Table 8: Parameters used for Tabu Search (TS) and Extremal Optimization (EO).
Graph
Nodes
Tabu Tenure (TS)
Tau (EO)
Gset (ER)
800
80
1.4
GSet (Skew)
800
90
1.4
BA
800
110
1.3
WS
800
140
1.4
HK
800
100
1.4
Phase Transition
100-200
20
1.8
GSet (ER)
800
100
1.7
GSet (Skew)
800
90
1.4
GSet (Torodial)
800
100
1.4
BA
800
120
1.2
WS
800
110
1.3
HK
800
110
1.2
Barrett et al. (ER)
200
10
1.9
Barrett et al. (BA)
200
20
1.6
SK spin-glass
70-100
20
1.8
Physics (Regular)
125
20
1.4
that ECO-DON and Soft (ECO+IR) achieve comparable performance, while S2V-DQN and RUN-CSP perform significantly worse.
Trained on Skew(weighted) distribution
ER(unweighted)
ER(weighted)
Skew(unweighted)
Skew(weighted)
Torodial(weighted)
1.0
1.0
Approx. Ratio
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.4
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.2
0.0
ECO-DON
LS-DON
SoftTabu
52V-DON
ANYCSP
RUN-CSP
tO 15
0.0
ECO-DON
LS-DON
SoftTabu
S2V-DON
ANYCSP
RUN-CSP
EO
ECO- DON
LS-DON
SoftTabu
52V-DON
ANYCSP
RUN-CSP
DO
0.0
ECO-DON
LS-DON
Softtabu
52V-DON
ANYCSP
RUN-CSP
0.0
ECO-DON-
LS-DON
SoftTabu
S2V-DON
ANYCSP
RUN-CSP
EO
T5
Figure 10: Generalization of agents to unseen graph sizes and structures.
A.6 Additional details on Evaluation settings
Since we are using the previous codebase from several works, and they are not equally optimized, we use the number of search steps instead a timcout. As both S2V-DQN and Gflow-CombOpt are irreversible (only add to the solution set), these algorithms can run for a maximum of [V] steps. For other learned algorithms, we run the experiments for 4|V| steps and find no significant improvement in the objective value. We present the results of the learned heuristics in Table g
A.7 Efficiency and Trade-offs in Large-Scale Instances
In this subsection, we present the run-time and mean approximation ratio of each algorithm evaluated across multiple datasets in Table 10
24

---

Published in Transactions on Machine Learning Research (04/2025)
1.0
Mean Approx. Ratio
Mean Approx. Ratio
0.8
0.8
0.6
0.6
0.4
0.4
0.2
EO
TS
S2V-DON
ECO-DOM
ECO+LR
ANYCSP
RUN-CSP
EO
TS
52V-DON
ECO-DON
ECO+LR
ANYCSP
RUN-CSP
(a) BigMac
(b) MaxCut and BQP Instance Library
Figure 11: Additional experiments on generalizations on BigMac and MaxCut and BQP Instance Library.
Table 9: Average approximation ratios of learned heuristics optimized for 4 steps: The first and second halves of the table show results for unweighted and weighted instances, respectively.
Graph
Nodes
ECO-DQN
LS-DQN
RUN-CSP
ANYCSP
Gset (ER)
800
0.997#0.001
0.903+00001
0.979=0.008
0.999+0.000
GSet (Planar)
800
0.989+0.001
0.983
0.954=0.001
0.997#0.001
BA
800
0.992-0.002
0.983-10.003
0.980
1..00
WS
800
0.992-0.002
0.972 10.2:10.003
0.979 000003
1.000 100000
HK
800
0.991 #00002
0.983=00.00 000
0.979=00003
1.000
Phase Transition
100-200
0.000000000
0.998=00001
0.984
1.000
GSet (ER)
800
0.981 #0.006
0.950=00.008
0.912=0.009
0.998=00.022
GSet (Planar)
800
0.967=0.008
0.946=0.018
0.914=0.018
00000
GSet (Torodial)
800
10.004
0.964
0.974 0.002
10.002
BA WS
800
0.973+0.008
0.933=0.010
0.937=0.009
1.000+0.000
800
0.961 000007
0.922
0.954
1.00040.000
HK
800
0.975=0.009
0.937=0.008
0.944=0.007
1.000
Barrett et al. (ER)
200
1.000#0.001
0.988
0.945=0.012
1.000#0.000
Barrett et al. (BA)
200
0.983=0.031
0.977
0.960=#.016
0.989
SK spin-glass
70-100
1.00000.000
0.999
0.962=0.019
1.000
Physics (Regular)
125
1.000=0.000
0.995
0.982=0.008
1.000
25

---

Published in Transactions on Machine Learning Research (04/2025)
0.986 (2.28 2.298)
1.000 (34 234.663)
1.000 (34 (41.555)
(1.867
(112-258)
(112.278)
1.000 (51.735)
0.996 (8.073)
1.000 (8.111
1.000 (0.922)
0.997 (41.041)
0.998 (41 (11.81)
1.000 (2.464)
0.995 (6.580)
0.998 (27-125) 125)
ANYCSP
1,000 (27.
0.998
RON- CSP
0.913 (1.151)
0.980 (14. (2.520
0.936 (14. (.880)
(1.378)
0.982 (03 5785778)
0.876 (00. 6411
0.979 (14.100)
0.940 (3.722)
0.985 (3.117)
0.080 (0.343)
0.954 (19. (79))
0.914 (19.619
0.884 (2.748)
0.075 (2.431)
0.07S (94444)
0.951 (9.877)
Table 10: A comparsion of run- time and performance of all learned and classical heristics across all datasets.
0.055 (3-586)
0,030 (3.4411
0.924 (0.271)
0.967 (3.694)
0.957 (2.043)
Giiowr
Na.
NoN
N&N
(8.
N&N
NoN
NaN
NaN
NoN
N&N
NaN
0.981 (1.887)
0.933 (10.579)
0.978 (11.179) 179)
1.908 (2. (2.122)
(23-740)
0.987 (26. 11.114))
448)
0.975 (11 (1.3))
1.000 (3.984)
1.000 (1.147)
0.990 (14.206)
0.978 15.0-18
1.000 (1:347)
0.902 (9.013)
0.988 (8.728)
0.970 (9.009)
ECO+LR
0.993
ECO-DQN
0.922 (3.021)
0.991 (23.814)
0.972 25.524)
0.999 (4.508)
0.985 (72.546)
0.991 (24.561)
0.970 (24.603)
1.000 (7.523)
1000 (1.700]
(29-583)
0.967 (32.551)
1.000 (2 22.)
0.993 (18. 850)
0.990 (18. 403)
(5.550
0.985 (72
0.989
0.957
0.978 (2.117)
0.084 (20 208)
0.960 (23 73.7788)
0.988 (3.880)
0.917 (66. 036)
0.983 (20 500)
0.947 (20 (19)
0.998 (6.379)
0.906 (1.189)
0.984 (24 553
0.936 (26 057)
0.909 (2. 1641
0L.))
0.975 355)
0.981 (16. (3.399)
LS-DON
0.962
S2V-DQN
0.937 (0.338)
0.950 (1.079)
0,583 1.190)
0.951 (0.659)
0,906 (1.63)
22508)
0,904 (1.125)
0,985 (0.210)
0,362 (0.187)
0.980 (1.118)
0,390 (1.154)
0.939 (0:284)
0.900 (1.110)
0,972 (1.064)
0.915 (1.105).
0.970
0,966
0.970 (1.22) 0.969 [1 .200
0.002 (1.766]
0.976 1..997
0.980 2611
523
0.986 -951
0.002 (1 5311
0.971 (1.801)
0.999 1..87)
0.978 (1.257]
0.991 1.862)
0.973 11.930
0.909 (1.746)
0.985 1.111)
0.089 (1.7 .244
0.964 (1.788)
T8
0.007
0.982 (2:216)
0.944 (2.344)
0.986 (1.83)
1088
0.963 (2.402)
0.982 (2.287)
0.945 (2.356)
1.999 (22216
0.996 (2077)
0.985 (2.342)
0.938 (2.3-00
0.993 (1.847
0.947 (2.113)
0.978 (22233)
01989 (2.763)
EO
0.994
0.892 (0.511)
0.053 (0-447)
0.859 (0.4 409)
0.916 (0.514)
0.915 08.528
0.052 (0-447)
0.858 4544
7.9995 (0. 409
0. 08686 (0.519)
0.962 (0.525)
0.570 (0.305)
0.093 (0-56))
0.804 (0.615)
0.027 (0-448)
Gready
0.082
02829
Phoae Transition (Unweightes)
BA200 (Welghted)
BAS00 (Unwoigghted ltted)
BA800 (Weighted)
ER200 (Weighted)
Elts00 Unweiglted)
ERS00 Weighted) htteed
HKS00 Unwwighted)
HIS800 (e)ggtte))
Physies (Weighteed)
Phana800 (Unwesightdd) ht
Planar500 500 (Wiihhte))
(Weigh SK70- 100 100
Turodials00 (Weighted)
N'8800 (Unwveighted)
WeSS00 (Weighteei)
26

---

Published in Transactions on Machine Learning Research (04/2025)
A.8 Additional Tables
Table 11: Performance of learned local search heuristics.
Closscal Heuristics
Learned Heuristics
Graph
Nodes
Greedy
S2V-Stmplifiee
S2V-DQN
LS-DQN
ECO-DQN
ECO+LR
0.98 0.984400.0
0.998
0290:200001
0,9749.00 ona
0.9749.00
0.99229..01
0.984
0.9974...om
0.971 40.000
0.906##0.00
0.99=0.001 o01
0.95g 20.000
0.94750.00 003
0.968
0.972#0.002
0.995+0.002
ER (Unweighted)
2000
5000
0,922=00
0.90440.000
0.965400
0.98840001
0.9740.0
0.900
0,932 0,932490
0.945 20.001
0,924
0.963 0.963
0,838400
0.96750.001
0.918
0.9044..000
0.977490
7000
0.92
0.962
0.964=0.0
0.931 0,931490 #0.0
0.918
0.8344000
0.916
0.974
10000
0.901 =0.0
0.922000
0.932=0.0
0.931 aaa
0.873
0. 0.828:09.
0.806
0.96-0.0
800
0.
0.986=00.002
0.965 #0.007
0.834
0.906#0.015
0.95
0.981 20.005
0.0.0
2000
0.87
0.977
2..0000004
0.8240.011
0.809
0 0.8552200.00
0,91720.00s
0.976
ER (Weighted)
0.809=0.
0,91#000
0,912=0.0
0.781
0.80g#0.0
0.43=0.0
0,923#0.0
0,942
7000
0.803=00
0.91 0.91
0.91
0.784
0.819#0.0
0.436
0.924
0.945
800
29.002
0.9824..00s
0.94220.03
0.728
0.96+.0.00
0.964
0.99220.00:
0.903
2000
0.766 467
0.95540.004
0.920 0.926
0.73440001
0,958 0.95820.00
0.95
0,98120.002
0.98749.00m
Tomidal (Weighted)
5000
0.759=00
0.89740.0
0.905=0.0
0. 0.72640.0
0.954#0.0
0,937#000
0.976
0.979
7000
0.757=00
0.00git..
0.g
0.731 0.731 da.
0.954
0.9434000
0.978
0.979
10000
0. 00055
0.86:220.012
89200.02
0.731
0.95422.002
4.99999.000
0.975
0.979490
20000
0.986 20002
0.96
0.98
0. 20.00
0.99
0.99 29.001
0.002+00001
0.99
00000
0.957
0.978=0.0m1
0.984
0.989=0.001
0.99
Planar (Unwrighted)
2000
0.959=6.
0.983+0.001
0.98240.001
0.956 t.0000
0.981 $0.001
0.979
0.983#0.002
0.985
5000
0.956=60
0.979:0.
0.98
0.956
0.972
0.775
0.976
0.98
7000
0.958=0.0
0,98=0.0
0.98*0.0
0,937
0.972
0.773
0.975
0.978
800
008
0.977
0.94930.008
0.816440.22
0.89+40.02
4.943440000
0.965=0.002
0.97849.000
2000
0. 0.86=6.00s
0.94420.001
0.90310001
0. t0.020
0.889
0. 0.923
0.94720.005
0.961 1...0o
Planar (Weighted)
5000
0.845=00
0.92540.
0,925=00
0.82=00
0.889
0.904
0.931
0,956499
0.845=00
0.918
0.918=00
0.815#000
0.882#0.0
0.894
0.937#0.0
0.956
Table 12: T-test results between different methods.
Comparison
t-statistic
p-value
Significance
TS & ECO+LR TS & ECO+GNN
0.218
0.829
No
0.602
0.551
No
ECO+LR & ECO+GNN
0.425
0.674
No
27


Reviews:
[{"review_id": "SRLSNRi4uV", "reviewer": "Reviewer_949y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The paper proposes a benchmark to address performance evaluation inconsistencies in the research community on maximum cut problem families.\n- The authors present an extensive collection of problem sets and evaluate a diverse range of algorithms.\n- The experimental setup provides insights into performance characteristics of classical and learned methods.\n\n\n## Weaknesses\n\n### Comments on experiments\n- The metric of time to solve is missing from all the tables and plots, making it unclear how computational efficiency compares across methods. Ideally, there should be a plot of time on the x-axis and a number of problems solved on the y-axis to give a measure of computational efficiency of a method. Ignore this point, if time budget is kept constant across the methods and please mention it explicitly in the experiments. \n\n- In Section 4.1, CPLEX and Gurobi are not tuned, although they belong to the family of exact optimization solvers. It is unclear why a 10s cutoff was chosen.\n\n- Inconsistent naming conventions for baseline algorithms make interpretation difficult. For example:\n    - Greedy is renamed LS-Simplified, giving the impression that they are different methods.\n    - Tabu Search (TS) is called ECO-Simplified in Section 4.2, which is misleading.\n\n- I do not completely agree with the conclusions regarding ECO-DQN in Section 4.2:\n     - p-values are missing to show whether differences between methods are statistically significant.\n     - Table 3 shows significant overlap in confidence bands for ECO-LR and ECO-GNN, suggesting their performance is nearly identical. This point can be raised in a separate section to highlight the need for proper ablations. \n     - The claim that ECO-DQN holds dominance over TS is questionable without additional statistical tests. It seems both are equally winning across the problem families, and the claim that TS is superior doesn’t sound valid. \n     - The relative standing of EO against ECO-DQN is not explicitly discussed.\n \n- The inclusion of S2V-DQN and LS-DQN in Section 4.2 is unclear. The only meaningful comparison appears to be ECO-DQN.\n- Section 4.3 should have been the focal point, as it directly addresses the paper’s research question. However, the comparisons in this section are not extensive enough.\n     - All of the DQN methods are missing. \n     - Quantum Annealing is mentioned but not used anywhere in the paper\n     - This section should have included the performance on all the problem families across all the methods.\n\n- Section 4.5 lacks a detailed discussion of factors affecting memory and efficiency.\n      - The observed memory usage might be an artifact of implementation rather than an inherent limitation of the algorithm.\n      - Time to solve should have been one of the metric in previous sections anyway.\n\n\n\n### Broader comments\n\n- The paper appears to be discussing two distinct issues:\n     - The lack of a unified evaluation criterion in the MaxCut research community.\n     - The presentation of MaxCutBench as a new benchmark to standardize evaluation.\n\n- The focus is heavily skewed toward the first point, while the second point is not convincingly presented. To make MaxCutBench more compelling, the authors should:\n     *  Show performance of all methods across all datasets in a single visualization.\n     *  Provide a clearer justification for why MaxCutBench should be adopted as a standard benchmark. Other than providing an unified evaluation, what are the pros and cons of using this benchmark? What insights does this benchmark reveal about where the community currently lacks progress? Based on these findings, what are the key open challenges and future research directions?\n\n\n- Additionally, the authors could mention the role of proof-of-concepts (POCs) and iterative refinements in algorithmic research. For example:\n    - S2V-DQN can be viewed as a POC, which, despite not outperforming all baselines, introduced a new paradigm for solving MaxCut.\nWhile iterative refinements have since improved upon it, such improvements might be evaluated relative to the original POC rather than meaningful real-world progress.\n    - In contrast, MaxCutBench provides an extensive benchmark where improvements are directly compared against state-of-the-art (SOTA) traditional heuristics, ensuring that advances are substantive rather than incremental. \n\n- Sections 4.1, 4.2, and 4.3 could be consolidated into a single section for better readability and presentation of results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces MaxCutBench, an extensive benchmark suite for evaluating algorithms on the Maximum Cut (MaxCut) problem. This benchmark addresses inconsistencies in evaluation practices for comparing both classical and deep learning-based heuristics. The paper highlights the lack of strong baselines in the research community, which limits the ability to measure real improvements in neural network-based approximation methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Questions / Clarifications about experiments:\n- How are CPLEX and Gurobi tuned for hyperparameters?\n   - These solvers perform extra work to prove optimality, so it should be clearly stated that they belong to a different class of optimization methods.\n   - Using default parameters for both solvers may not be fair; just as heuristics are hand-tuned, solver parameters should be tuned for fair comparisons.\n\n- Are deep learning heuristics retrained on each problem set?\n    - This is assumed but not explicitly mentioned in the Evaluation section.\n    - Is S2V-DQN retrained for each plot in Figure 2?\n\n- Experimental setup for Section 4.4 is unclear.\n    - How are out-of-distribution (OOD) graphs selected?\n    - Are deep learning heuristics retrained for each dataset?\n\n## Minor comments \n- Figure 2: Legends are poorly placed and should be adjusted for clarity.\n- Figure captions: Should be more descriptive, summarizing key findings instead of just stating the experiment type.\n- Table 2: \"Summery\" → \"Summary\" (Typo).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nDlb3y6cwj", "reviewer": "Reviewer_r9Re", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The motivation is clear, and the experimental settings are reasonable in most cases. \n2) This writing is clear and easy to understand.\n3) The conclusion is somehow interesting and may give new insight into this community.\n\nWeaknesses/Questions:\n1) Does S2V-DQN is a constructive method? If so, it may be unfair for S2V-DQN to compare with the local search method Tabu Search. In other words, S2V-DQN should be compared with the heuristic Greedy. The conclusion that S2V-DQN is beaten by Tabu Search may not be sound. Further, refining the categories of the methods will be better.\n2) Why ANYCSP performs so well? This paper describes the phenomenon but does not give further insights.\n3) In ECO-DQN's origin paper, does it ablate the effect of GNN? If yes, what is the conclusion in their paper? Do they also find the uselessness of GNN?\n4) Is there any other recently proposed learning-based method for solving the Maximum Cut problem? For example, the methods that are published in 2024.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary: This paper rethinks the baselines of the current GNN-based learning method for solving the Maximum Cut problem. This paper selects several recently proposed/highly cited GNN-based methods (S2V-DQN, ECO-DQN, ANYCSP, and Gflow-CombOpt) and classical heuristics (such as Tabu Search and Greedy), and compares them on several frequently used datasets. The results show that the GNN module does not provide an effect on performance for some GNN-based methods in many cases. The simple local search heuristics (such as Tabu Search) frequently outperform complicated GNN-based heuristics. However, the  ANYCSP (a learning method) does perform well.\n\nContribution: 1) This paper proposes MaxCut-Bench, a benchmark suite that provides a fair and comparable environment for evaluations of GNN-based learning methods on the Maximum Cut problem. 2) Using the proposed MaxCut-Bench, this paper reveals that local search heuristics such as Tabu Search can outperform most learning methods. 3) this paper also reveals that the GNN in some GNN-based methods may not play a role in performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "none", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ieKFVPF7FR", "reviewer": "Reviewer_xnth", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nMany of the findings are interested and some of them are surprising. For instance that classical results are outperforming GNNs; that replacing GNN-components with Linear regression does not lead to loss of performance; and that GFlowNets perform so poorly in the context of weighted graphs. \n\nWeaknesses:\n\nIt is unclear how generalizable these findings would be to CO problems more broadly, beyond MaxCut.\n\nWork is purely empirical. In an ideal world, it would be nice having some theory relating the statistical properties of the network / generating model to the performance of various algorithms.\n\nUnclear how the performance of the algorithms is related to run-time. There is some exploration of computational efficiency in Section 4.5, but this needs to be further developed by a table directly showing run-time and performance together. Is there a trade-off where the more accurate algorithms come with a longer run-time.\n\nSome of the performance charts are hard to read. Please also include the results in tabular form. If needed, these can be in the appendix, but they should be mentioned in the main body, e.g., ``results are also shown in Table 7 in Appendix A\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper seeks to benchmark a bunch of GNNs and other methods for the MaxCut problem, i.e., finding a subset $S$ of the vertices of a weighted graph $G=(V,E,w)$ such that $\\sum_{v\\in S,w\\notin S} w(u,v)$ is as large as possible. Towards this end, they contribute an open source code base and compare several classical heuristics with more modern methods.  In their experiments, they find several surprising and interesting results.\n\nMy opinion is that this work will be suitable for publication in TMLR, but only after the requested changes are made.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the run-time issues discussed in ``weaknesses\" as well as charts being hard to read. (If you can address the other two weaknesses, that would be great, but not required.)\n\nFor Quantum Annealing, it says that you report the best of the two solvers. It would be better to report both results in the interest of transparency (possibly in appendix if there are spatial constraints).\n\nMinor: \n\nPage 3, Start of Section 3 Should write G=(V,E,w) rather than G(V,E) since th graph is weighted\n\nPage 3, ``section 4.2\" should be capitalized (since it is a proper noun). Please check throughout.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers found the proposed MaxCutBench useful for the research community with clear motivation, and the experimental findings were interesting with valuable insights. While the reviewers identified several weaknesses and requested changes in their comments, most of these concerns were adequately addressed during the rebuttal. In the official recommendation, two reviewers vote to accept this work, and one reviewer leans toward acceptance.

I read the paper in detail and fully agree with the reviewers' consensus that this work clearly satisfies the TMLR acceptance criteria (solid and well-supported claims, potential audience). I therefore recommend accepting this work. 

In the camera-ready version, please ensure that all promised changes are meticulously incorporated into the paper.
Decision: Accept (poster)