Learning to Explore and Exploit with GNNs for Unsupervised Combinatorial Optimization
Authors: Utku Umur ACIKALIN
Aaron M Ferber
Carla P Gomes
Venue: ICLR 2025 Poster (2025)
Keywords: combinatorial optimization
unsupervised learning
graph neural networks
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: X^2GNN iteratively refines (exploit) a solution pool (explore) using GNN for combinatorial optimization, generalizing across problem distribution and size. % , and outperforming ML and traditional OR baselines.

Abstract: Combinatorial optimization (CO) problems are pervasive
across various domains, but their NP-hard nature often necessitates problem-specific
heuristic algorithms. Recent advancements in deep learning have led to the development of learning-based heuristics, yet these approaches often struggle with limited search capabilities.
We introduce  Explore-and-Exploit GNN ($X^2$GNN, pronounced x-squared GNN), 
a novel unsupervised neural framework that combines exploration and exploitation for combinatorial search optimization:
i) Exploration - $X^2$GNN generates multiple  solutions simultaneously, promoting diversity in the search space; 
(ii) Exploitation - $X^2$GNN  employs neural stochastic iterative refinement to exploit partial existing solutions, guiding the search toward promising regions and helping escape local optima.
By balancing exploration and exploitation, $X^2$GNN achieves superior performance and generalization on several graph CO problems including Max Cut, Max Independent Set, and Max Clique. Notably, for large Max Clique problems, $X^2$GNN consistently generates solutions within 1.2\% of optimality, while other state-of-the-art learning-based approaches struggle to reach within 22\% of optimal. Moreover, $X^2$GNN consistently generates better solutions than Gurobi on large graphs for all three problems under reasonable time budgets. Furthermore, $X^2$GNN exhibits exceptional generalization capabilities. For the Maximum Independent Set problem, $X^2$GNN outperforms state-of-the-art methods even when trained on smaller or out-of-distribution graphs compared to the test set.  Our framework offers a more effective and flexible approach to neural combinatorial optimization, addressing a key challenge in the field and providing a promising direction for future research in learning-based heuristics for combinatorial optimization.

Published as a conference paper at ICLR 2025
LEARNING TO EXPLORE AND EXPLOIT WITH GNNS FOR UNSUPERVISED COMBINATORIAL OPTIMIZATION
Utku Umur Acikalin' ua458cornell.
Aaron Ferber'
Carla P. Gomes'
amf2722cornell..cm
gome cs www.eoo.ne.ooooooo
'Cornell University, Department of Computer Science
ABSTRACT
Combinatorial optimization (CO) problems are pervasive across various domains, but their NP-hard nature often necessitates problem-specific heuristic algorithms. Recent advancements in deep learning have led to the development of learning- based heuristics, yet these approaches often struggle with limited search capabilities. GNN (NN,,N, pronounced x- x-squared GNN), novel unsupervised neural framework that combines exploration and exploitation for combinatorial search optimization: i) Exploration G generates multiple solutions simultancously, promoting diversity in the search space; (ii) Exploitation
We introduce Explore-and-Exxpe
X employs neural stochastic iterative refinement to exploit partial existing solutions, guiding the search toward promising regions and helping escape local optima. By balancing exploration and exploitation, X2GNN achieves superior performance and generalization
several graph CO problems including Max Cut, Max Independent Set, and Max Clique. Notably, for large Max Clique problems, X²GNN consistently generates solutions within 1.2% of optimality, while other fate-of--hhe-rt art learning- based approaches struggle to reach within 22% of optimal. Moreover, X consistently generates better solutions than Gurobi on large graphs for all three problems under reasonable time budgets. Furthermore, X2NNN exhibits exceptional generalization capabilities. For the Maximum Independent Set problem, X GNN outperforms state-of-the-ard methods even when trained on smaller or out-o--dittribution graphs compared to the test set. Our framework offers a more effective and flexible approach to neural combinatorial optimization, addressing a key challenge in the field and providing a promising direction for future research in bearning-based based heuristies for combinatorial optimization.
INTRODUCTION
Combinatorial optimization (CO) problems aim to find discrete solution that optimizes objec- tive function from a discrete set of feasible solutions constrained by specific problem parameters. These optimization problems frequently emerge in commercial, governmental, and scientific con- texts, prompting extensive study in fields such as mathematics, computer science, and operations research. Many combinatorial optimization problems are NP-hard, indicating no polynomial-tine exact algorithm exists unless P NP.
Exact algorithms, which achieve optimality by implicitly explicitly considering all possible solutions, are typically only tractable for small instances due to their exponential worst-case time complexity. Consequently, another body of work focuses on heuristic algorithms that quickly attain high-quality solutions without optimality guarantees. Work here seeks to balance computational time and solution quality, often exploring search space through multiple different solutions, and exploiting promising ones (Eiben and Schippers] 1998).
Heuristics are often hand-crafted for specific problem, exploring problem intricacies to achieve peak performance for given problem distribution, requiring time and domain expertise. The rise of deep
Code available at httppp////gtttaa...cmmo/uuoouu//

---

Published as a conference paper at ICLR 2025
learning has enabled new learning-bast -bsedd heuristics that can be automatically tuned for performance using data.
However, current approaches often limited in their search capabilities, often only iteratively improving a single solution, or naively restarting and forgetting previously generated solutions.
In this paper, introduce Explore-and-Exploor GNN (X*GNN, pronounced X-squared GNN), a novel unsupervised neural combinatorial optimization framework. X'GNN combines effective exploration of the solution space with intelligent exploitation of partial solutions.
Our Main Contributions are:
1. We propose GNN,,, which combines exploration and exploitation for combinatorial search optimization: (i) Exploration G*NNN simultaneously generates multiple coupled solutions, promoting diversity in the search space; (ii) Exploitation X employs neural stochastic iterative refinement to exploit partial existing solutions, guiding the search toward promising regions and helping escape local optima.
2. State-of-the-ar performance: G outperforms existing learning- based approaches on benchmark datasets for the maximum cut, maximum independent set, and maximum clique problems. Additionally, GNNN is competitive with general OR approaches like Gurobi, and problem specific heuristics like KaMIS, offering improved or comparable solution quality at similar time cutoffs.
3. Strong generalization capabilities: G2GNN generalizes to graphs that out-of-distributien or up to 4 times larger than those other learning-basee methods trained on the same distribution the test set.
seen during training, while still significantly outperforming
4. Rigorous Evaluation: We enhance existing benchmark datasets commonly used in the ML for combinatorial optimization community by including strong traditional baselines and evaluating solvers at comparable runtimes. We additionally allow solvers 30-minute time limit, which is at least 24 times longer than our longest- uogges-ruuning model.
2 RELATED WORK
The broad intersection between machine learning (MI.) and combinatorial optimization (CO) has seen much work with different facets explored in various surveys (Bengio al., 2021 Kotary et al. 2021] Cappart et al., 2023). srate-of-the-ary learning-based primal heuristics specifically can be broadly categorized by their training supervision and solution construction methods. Supervised learning approaches use training data composed of problem instances and corresponding solutions derived from existing solvers (Khalil et al. 2016 Selsam et al. 2019; Nair et al., 20200] Sun and Yang 2023). However, these may face challenges such the unavaila unavailability labiiity of high-quality solvers for all problems and poor generalization capabilities across different problem instances (Yehuda et al. 2020). Despite these challenges, recent studies have shown that diffusion-basee training can enhance generalization in supervised learning (Sun and Yang (202))).
Unsupervised learning approaches have also been explored, differing primarily whether solutions are constructed autoregressively or not. Earlier non-autoregreesive models generate a 'soft' solution in single step, which is then decoded into final solution using methods ranging from simple greedy (Karalias and Loukas 2020) decoding to more sophisticated techniques (Min et al. (022). As Sanokowski et al. (2024) noted, these approaches can be classified as single-step diffusion methods. These models are notably faster and more scalable than their autoregressive counterparts, [Sanokowski jet al. (2023) suggest that non-autoregressive solution construction may fail to capture essential dependencies among problem variables and they refer to these types of methods as mean-field approximations.
The earlier single-step non-autoregressive methods outperformed by autoregressive construction governed by MDPs (Sanokowski et al. 2023 Zhang et al. 2023). However, these models are trained using reinforcement learning (RL) and face high computational needs and poor generalization (Sun and Yang (023). Additionally, autoregressive construction does not allow modification fixed decisions, unlike diffusion-basee based construction where all variables be altered at each step.
2

---

Published as a conference paper at ICLR 2025
The success of generative diffusion models (Sohl-Dickstein et al. 2015) made it appealing for CO. For diffusion-bassee CO approaches, noise is sequentially added to the optimal solution obtained from other solvers in the forward process, and the model learns to iteratively remove this noise in the reverse process. [Sun and Yang (023) models the CO problems as a discrete diffusion problem using Bernouilli and Categorical noise. For MIS, they outperform oon-eutoreeressivve models but have similar performance to autoregressive models, suffering from long diffusion schedules. Li al. 2023) follow the same training procedure as Sun and Yang (2023) but employ gradient-guided noising-denosing rounds during inference. This improves upon Sun and Yang (2023); however, long diffusion schedules and reliance on the gradients hinder effectiveness. [Sanokowski al.) (2024)
trains a diffusion model to sample from the Boltzmann distribution with the probability of sampling solution being positively correlated to its objective value. They derive an unsupervised loss function using a continuous Lagrangian relaxation, showing that longer generation schedules increase quality.
PRELIMINARIES
We consider the broad class of combinatorial optimization problems on graphs and instantiate G for three NP-hard problems on undirected unweighted graphs G = (V, E). As in many real-world scenarios, we consider distributional versions of these problems, where we are asked to train algorithm on a dataset of instances and then deploy the algorithm unseen instances.
Maximum Clique (MC): A clique in graph a subset of vertices where every two vertices are adjacent. The Maximum Clique problem involves finding the largest clique in G.
Maximum Independent Set (MIS): An independent set in a graph G is a subset of vertices, none of which are adjacent. The Maximum Independent Set problem aims to find the largest independent set.
Maximum Cut (MCut): For a graph = (V, E), the Maximum Cut problem seeks to partition the set of nodes V into two subsets S and V S, maximizing the number of edges between S and V S.
Solutions for these problems can be represented by binary decision for each node, Y {0, 1,11, indicating solution inclusion, Y; = if v; E otherwise 0. Additionally, the maximum clique and maximum independent set problems are closely related; clique S in graph corresponds to an independent set S in its complementary graph (Cormen et al. (2001)). We use this relationship for all approaches and solve MC problems by solving MIS on the corresponding complementary graph.
X"GNN FRAMEWORK
X'GNN, illustrated in Figure I is an iterative framework that explores the search space by simul- taneously generating pool of K- K-Coupled solutions and exploiting promising ones via stochastic refinement.
K K-Coupled solutions form group of K solutions that are built collectively, refer to each group as a K-Couple. We model the K-Couple using a multilayer graph, copying the original graph K times to represent the K solutions, and adding auxiliary edges between corresponding nodes in different layers. We model the solution values themselves as node features. We then iteratively feed the K- KoCulee into a graph neural network (GNN) which makes a prediction on each node corresponding to a new K K-Couple. We train the GNN's outputs at each iteration using a combination of an unsupervised optimization loss, a constraint satisfaction loss, and a diversity loss on the K K-Couple. Importantly, before feeding a K- KCCCoppl as input to the GNN, we randomly perturb the solution to help escape local optima. Furthermore, we randomly initialize the K- K-Couple.
Formally, given a problem represented by graph G = (V, E), we represent the GNN input of K solutions at iteration & using 'X E [0, 1] x with ' denoting the feature of node u E V for solution & E 1,...,K K in iteration t. We use 'Ý' to denote the K- K-Coupled solution generated at iteration t. That is, 'Ý (G, X). Similarly, we the notation 'Ý- to denote the probability of node u E V being in solution & E 1,..., . K generated at iteration f.
Solution Generation and Stochastie Iterative Refinement: We refer to the first iteration (t 1) of GNNNN as construction and the subsequent iterations (t 2 2) as refinement. During construction, randomly initialize node features X to 0.5 with probability p and 0 with probability p.
3

---

Published as a conference paper at ICLR 2025
Create Multilayer graph
Exploration: Coupled Solution Pool Generation
Original Graph G EV
GN
Gus (V", Fo Ee)) Multlayer Graph
1 Initial node features
1y Solutions after construction
Exploitation: Stochastic Refinement
GN No
Objective Loss
Constraint Loss Diversity Loss
--
X
Overall Loes
Figure 1: Illustration of GNNNN for a Minimum Independent Set instance. First, a multilayer graph created from K = 2 copies of the original graph, with cross edges to couple solutions. Copies of the original edges (E)) are drawn in blue, and cross edges (E')) are drawn in red. Node features correspond to the probability of being in the solution, representing soft solutions. Initially, when generating the coupled solutions. the features are random. These features are fed into a GNN to obtain K soft solutions. During stochastic refinement, the GNN iteratively takes solutions from the previous time step. randomly perturbs them, and generates new solutions. Stochastic refinement can be repeatedly applied inference and is done once during training. Finally, the training loss calculated for all generated solutions using the objective value, Lagrangian term, and diversity.
with being 0.95 in practice. Essentially, we initialize the K -Cuule with unbiased solutions while introducing diversity to break symmetries for nodes with identical degrees.
During refinement, randomly set the previous iteration's 's output 1- to 0 with probability & to generate new node features 'X.
The parameter ó offers natural way control exploration and exploitation. If from the previous iteration is used, maximizing exploration. Φ 0. the previously generated solutions are maintained, and the method will deterministically refine the K- K-Couple, maximizing exploitation. Thus, high values of Φ lead to exploration whereas low values lead to exploitation. We refer step of this approach Stochastic Refinement and the general application of multiple iterations as Stochastic Iterative Refinement.
information
Aligning the model's input and output enables repeated use the recurrent model. Recurrent models trained on short iterations can be deployed for longer iterations to solve more complex problems (Schwarzschild et al., 202Ip; however, overuse can result in 'overthinking" (Bansal et al., 2022). X"GNN mitigates this by not iterating over the hidden representations, but rather iterating stochasti- cally over the output space. The stochastic sampling process significantly impacts performance by facilitating exploration around the current solution, allowing exploitation, and escaping local optima. Moreover, helps generalization to bigger and -istof-distribution datasets.
Converting Soft Solutions to Hard Solutions: Since the GNN outputs soft solutions ý* we convert them to discrete feasible solutions S depending the problem. For MCut, we select node into S iff y* 0.5, yielding feasible solution due to the absence of constraints. For MIS and MC, we add node into S in order of decreasing probability ý* long S U {u) satisfies problem constraints.
K- -Coupled Solutions: To couple solutions, we construct a multilayer graph G = (V',E') from the original graph G (V, F.). GM contains K "layers" each containing copy of the original graph.
4

---

Published as a conference paper at ICLR 2025
Additional edges (cross edges) connect nodes in different layers corresponding the same node in G. We denote E as the edges corresponding to original edges E, and E as the cross edges, such that E" = Eo U E' We construct GM as follows: For each node U, E V, we create node of for all layers k = 1, ...., K. For each edge (vi, 0j) E E, we create an original edge between of and of for all h = 1, ...,, K, forming E-- We then add cross edges Egc, such that for each node E V all copies of have pairwise edge between them in Gas In practice, we select K = 2.
GG Neural Network Architecture: The GNN used by X to construct and refine solutions consists of 2L layers combining Graph Isomorphism Networks (GIN) (Xu et al. 2019) and Graph Attention Networks (GAT) Velickovic et al. 2018)) Brody et al. 2022 The layers alternate between GIN layers operating (V", (V) to work on individual solutions and GAT layers operating on (V', EC) to enable information sharing between solutions. This alternating design enables the simultaneous generation of K K-coupled solutions. Note that the same model parameters used for both construction and refinement.
Training and Loss Functions: We train G using unsupervised combinatorial optimization losses which take the form of Lagrangian relaxations of the original problem. We adopt nonlinear programming formulations for MCut, MIS, and MC problems from Sanokowski al. (0024). For MIS and MC, the objective is to include as many nodes in S as possible, penalizing constraint violation, whereas in MCut the objective is to include as many edges in the cut as possible. We additionally propose adding a loss function to promote diversity among the K K-coupled solutions. In the MIS and MC settings, we want solutions to contain different nodes, whereas we are interested in having different cut edges for MCut. We write the optimization problems, continuous relaxations, and Lagrangian terms for the constraints in Table !
Overall, GNN trains the GNN parameters 0 to jointly optimize objective quality (Co), constraint satisfaction (Lc), and solution diversity (Ca) over the training set G:
Σ Co (8 + (P*)) + +x2Ca(G,(8))
min Egeg
For MC and MIS, we impose node diversity:
La(G,))= K(K
1
Σ pki
ISK SK uEV k1
For MCut, we impose edge diversity:
Ca(G.))= K(K 1)
Σ Σ
1
1-
(2Ý%) 1)) 1) 1 1 1)(28 1)
1sh (u,D)E ki ki
Problem
Formulation
Objective
Constraint loss
max (
ΣVEV Yu
MC
Σ Y NEV
Σ (u.r)
s.t. Y.Y. = O, V(u,)) & E
max V
Evev Yu
MIS
Y.
Σ
s.t. Y.Y. 0, V(u, v) E E
NEV
(u.))E
(2Y,. 1)(2Y,
(2f,
1)22..
MCut
V IVI (M.
2
(M.))
Table 1: Mathematical formulation, objective loss Co, and constraint loss L. for our problems.
We train GGNN using a two-stage training procedure. In the first stage, the model learns to construct solutions, and in the second stage, the model learns to stochastically refine constructed solutions for one step. The proposed two-stage training procedure leads to better initial solutions and more stable solution refinement for X2GNN.
5

---

Published as a conference paper at ICLR 2025
Inference: Unlike during training, during inference use the stochastic refinement step multiple times leading to stochastic iterative refinement. Training the model on single stochastic refinement iteration is enough to teach the model to generally improve solutions. We show that using the stochastic iterative refinement longer leads to a significant increase in solution quality. Additionally, instead of generating just one K-coupled solution, we generate C. K-coupled solutions increase exploration. These K- -ccoupled solutions are independent and effectively run X XNGNN simultancously with different random seeds.
GNN offers time-quality trade-off's by selecting C, the number of K K-Coupled solutions, and T the number of iterations. By increasing C' and/or T. we can consider more solutions to improve solution quality by using more time. For each choice of C' and T. G generates C' x K solutions at the iterations to generate C x K T solutions in total. Hence,
first iteration that are then refined for the computational impact of C and 7 is very similar. A natural question is how to select C' and T for fixed computational budget. Under a fixed budget, increasing C promotes exploration by maintaining more solutions, whereas increasing T enhances exploitation by allowing more refinement iterations on existing solutions. This mechanism controls exploration and exploitation in our optimization framework, which is crucial for effectively navigating the search landscape of complex problems.
EXPERIMENTS
Datasets: Previous literature has identified that some problem instances for MIS and MC are relatively easy (Dai et al.] 2020]. To ensure rigorous evaluation, we use synthetically generated hard
instances, following previous work (Karalias and Loukas 2020, Zhang et al.] [023: [aankkossi
et al. 2024). Our datasets include RB graphs (Xu and Li 2000), revision to model B graphs (Gent et al. 2001; Smith and Dyer 1996). known to generate challenging instances for MC and MIS. Specifically, we use RB graphs with 200-300 no25s()B250) and 800- 200 nodes (RB1000) 1000). For MIS, we also evaluate on Rénéi (ER) graphs (Erdös and Rényi 1959) with 700-800 nodes and edge probability 0.15 (ER750), well as regular graphs where each node has either 3 (d=3) or 5 (d=5) neighbors. Following Schuetz et al. (2022). we generate 20 regular graphs for each degree d 3, 5 and each size [00 10 10 10", 10 for testing. To train learning-haa -based methods, we generate 4,000 additional graphs with n 103, enabling evaluation of both generalization and scalability, For MCut, we use Barabási- Albbert (BA) graphs (Barabási and Alberi 1999) with 250 nodes (BA250) and 1,000 nodes (BA1000). We train on 4,000 graphs and test on 500 graphs except for ER (128 test graphs) and regular graphs (20 test graphs for each size and d).
Baselines: We compare GºGNN against both Operations Research (OR) and Machine Learning (ML) techniques. We compare against Gurobi (Gurobi Optimization, LLC, (024) on all tasks as it is a general-purpose exact solver that is highly performant on many CO tasks due to years of development. For MIS, we compare against KAMIS (Lamm et al.) 2016), a highly specialized MIS solver, as well as learning-boc based approaches such as PPO (Ahn et al.) 2020), Gflow (Zhang et al. 2023), DIFFUSCO (Sun and Yang 2023). T2T al. 2023). and DifUUCO (Sanokowski et al. 2024. For MC, we benchmark against KAMIS used on the complement graph, greedy algorithms, mean-field annealing (MFA), and learning- based methods including ERDOS and its annealed version ANNEAL (Karalias and Loukas, 2020 Sun et al., (022). DiffUCO, and Gflow. MCut comparisons (SDP) based approximation algorithm (Goemans and Williamson 1995). Tabu Search (TS) (Nath and Kuhnie 20244). and tearning-basee methods RUN-CSP (Tönshoff al. 2020). ANYCSP (Tönshoff' et al. (023). ERDOS. ANNEAL, DifiUCO, and Gflow. When given, we use Fast, Quality, and 30min to denote that we set time limits around the twice the fastest version of X twice the slowest version of ' and 30 minutes respectively.
include weweeeiiiiie-roggammii
Evaluation Metrics:
We employ three metrics: the mean objective value (Size), the mean drop in quality relative to the best-known solution (Drop), and the mean runtime in seconds (Time). Overall, better methods find solutions with lower solution quality drop at smaller runtimes. Since all problems are maximization problems, larger size is better. For instance, a 10% drop means the method generates solutions with a mean objective value of 90, while the best method achieves 100. In all tables, learning-baa based methods are shaded. Bold entries denote the best learning- based method, and italics indicate the best method, learning traditional. Additionally, we denote the method type categorizing methods into operations research (OR), heuristic (H), supervised learning (SL), and unsupervised learning (UL.)

---

Published as a conference paper at ICLR 2025
Table 2:
Results for Max Clique on small and large RB graphs, presenting the mean clique size, drop in quality compared to the optimal, and runtime in seconds. Learning bearning-based methods are shaded, and the best learning-based result bolded. The best global result in italies. XºGNN generates solutions at least 14% to 23% better than all learning- based methods. G solves RB250 optimally, with a similar run time as Gurobi and KaMIS.
Method
Type
RB250
RB1000
Size
Drop
Time
Size
Drop
Time
KaMIS
0%
Gurobi (30min)
OR
19,074
0%
0.73
40.652
0%
287
Gurohi (Quality)
OR 19.068
0.03%
0.61
36.23
10.88%
Gurobi (Fast)
OR 14.62
23.35%
0.17
25.36
37 626
Groody
H 13.53
29.07%
0.03
26.71
34.30%
0.04
MFA
14.82
0.04
31.27%
Erdos
UL 12.02
36.98%
0.06
25.43
37.44%
Anneal
UT.
14,1
26.08%
0.06
27.46
32.45%
Gflow
UL
16.24
14.86%
0.06
31.42
22.71%
0.44
DITUCO
16.3
G (RB250X2X64)
UL
19.04
0.18%
0.09
39.83
2.02%
1.5
GNNN (RB250(8x64)
UL
19.072
0.01%
0.37
40.09
1.38%
PUNN (28650))32661)
19.074
1.19%
For generalization, we denote the training dataset with (RB250) or (BA250) in the model name. We denote variants of GNNNN that generate C 2-2-Cueeeed solutions and use T stochastic refinement steps with (2CxT) in the model name.
5.1 RESULTS ON MAXIMUM CLIQUE
Results for MC on small and large RB datasets shown in Table For MC, train G on RB250 and showcase generalization to larger instances. X*GNN generates solutions of at least 14% and 23% higher objective value than the second-best learning- based methods on RB250 and RB1000, respectively.
Compared to traditional algorithms, GNN solves every RB250 instance optimally, with a similar run time as Gurobi and KaMIS. On the larger dataset, on which X"GNN wasn't It trained, X"GNN generates solutions that are within 2% of optimality while almost being 50 and 190 times faster than KaMIS and Gurobi, respectively. Additionally, at similar runtime, X GNN has substantially better solution quality than Gurobi.
5.2 RESULTS ON MAXIMUM INDEPENDENT SET
Table presents results for Maximum Independent Set (MIS) small RB, large RB, and ER graphs. For all datasets except regular graphs, the metaheuristic KaMIS achieves the best solution quality. Again, X"GNN outperforms all learning-based methods by a large margin, especially for the largest RB 1000 dataset, where X X2GNN generates solutions that are 9% better than the second best. Even the model trained on RB250 dataset is able outperform the other lcarning-basee methods on both RB 1000 and ER750 datasets, showing that X 2NNN can successfully generalize to harder and different graph distributions.
Comparison with the traditional algorithms is more nuanced. On ER750. GNNN generates better solutions than KaMIS and Gurobi when they are given either 15 or 60 seconds. On RB 1000, R2NNN generates better solutions than Gurobi but slightly worse solutions than KaMIS at around 20 seconds.
Figure presents the solution quality relative to the theoretical lower bound and the running time for regular graphs of varying sizes. Given the large graph sizes, obtaining optimal solutions is intractable. Following Schuetz et al. (2022), we use analytical upper bounds for random d-regular graphs, with the best-known ratios 03 an/n 0.45537 and as/n 0.38443 for d = 3 and d 5. respectively (Duckworth and Zito 2009). However, these bounds may not be tight. For instances with n = 100 and d = 3, both X GNNNN and KaMIS find optimal solutions, verified by Gurobi. Notably, the analytical upper bound remains 2.6% above these solutions, indicating that actual performance may be better than suggested.
7

---

Published as a conference paper at ICLR 2025
Table Results for Max Independent Set on small and large RB graphs and ER graphs, presenting the mean independent set size, drop in quality compared to the virtual best (KaMIS), and runtime in seconds. GNN substantially outperforms learning-bas -asee approaches on all datasets. When generalizing from small RB250 instances, G2GNN outperforms learning-baset methods trained on larger and in-distribution problems. On ER instances, X*GNN outperforms traditional OR approaches given similar time limits.
Method
Type
RB250
RB1000
ER750
Size
Drop
Time L
Size
Drop L
Time
Size 1
Drop
Time J
KaMIS (30min)
OR 20.106
0%
3.92
43.218
0%
381
45.234
0%
382
Gurobi (30min)
OR 20.106
0%
0.31
42.96
0.60%
550
43.62
3.57%
1800
KaMIS (Quality)
OR
20.106
0%
3.92
42.98
0.55%
18
44.84
0.87%
61
Gurbhi (Quality)
OR
20. 106
0%
0.42
42.25
2.24%
22.27
43.5
3.83%
120
KaMIS (Fast)
OR 20.032
0.37%
1.16
42.66
1.29%
6.5
43,46
3.92%
Gurobi (Past)
OR 19.16
4.71%
0.1
38.81
10.20%
1.23
41:31
8.67%
3.62
PPO
UL 19.01
5.45%
0.15
32.32
25.22%
0.91
41.11
9.12%
2.11
GFlow
UT. 19.18
4.61%
0.05
37.48
13.28%
0.4
41.14
9.05%
1.03
DIFUSCO
SL
12.07%
35.82
17.12%
41.11
40.35
10.80%
15.46
12T
SL 18.35
8.73%
2.32
35.822
17.11%
26.55
41.37
8.54%
13,92
UL
4.31%
38.87
43.63
3.55%
X'GNN(16x8)
UL 19.51
2,96%
0.034
40.53
6.22%
0.3
42.05
7.04%
0.31
X GGN(644x8)
UT. 19.82
1.42%
0.
41.54
3.88%
1.18
43.06
4.81%
1.07
X GNN(25668)
UL 19.98
0.63%
42.
2.38%
4.66
43.82
3.13%
X GNN(256632)
UL
20.072
0.17%
42.48
1.71%
18.36
44.43
1.78%
15,26
X (NN(1024x32)
UL 20.098
0.04%
42.81
0.94%
74.4
44.91
0.72%
57.18
X GNNIRB25002266:3)
UL
20.072
0.17%
1.94
39.28
9.1%
9.43
44.15
2.40%
7.96
300
011000
HMMS
0.77
640
Number of modees.
Number rodes,
Figure 2: The left plot shows the relative solution quality compared to the theoretical upper bound for X²GNN, DiffUCO, and KaMIS (higher better). The right plot shows the average running time for each method (lower is better). Lines with squares and triangles show the results for regular graphs where each node has 3 and 5 neighbors, respectively. X*GNN outperforms DifTUCO on graph sizes and families in terms of solution quality while being faster on larger graphs. It also surpasses KaMIS in larger graphs with a better run time.
GºGNN surpasses Dif in both solution quality and computational efficiency larger graphs. DifTUCO fails to solve = 106 graphs within two hours, while X"GNN efficiently produces high- quality solutions in about 600 seconds. Although KaMIS slightly outperforms X"GNN smaller instances, X"GNN excels on larger graphs with lower computational time, scaling effectively to instances three orders of magnitude larger than those in training.
5.3 RESULTS ON MAXIMUM CUT
Results for Maximum Cut small and large BA datasets shown in Table X*GNN outperforms all state-of- tiite--f-the-ate art learning-basee methods on both datasets. However, ANYCSP and DiffUCO notably have only slightly the large dataset, G outperforms Gurobi with a time limit of 30 minutes per instance while only using 0.2 seconds. Similarly, X outperforms Tabu Search, finding better solutions faster.
performance than G both in terms of speed and quality. For
8

---

Published as a conference paper at ICLR 2025
Table 4: Results for Max Cut on small and large BA graphs. presenting the mean cut size, drop in quality to the virtual best, and runtime in seconds. GNN outperforms learning- based methods, slightly outperforming ANYCSP. Additionally, on BA1000, X2GNN outperforms Gurobi given 30 minutes by generating better solutions in 0.2s.
Method
Type
Size 1
Drop
Time 4
Size
Drop
Time 1
Gurobi (30min)
OR
235.32
09
759
2966.55 58
0.76%
1800
Gurobi (Quality)
731.99
0.45%
2931.02
1.95%
Gurobi (Fast)
OR
731.83
0.47%
0.16
2930.99
1.95%
0.66
SDP
OR
700.04
4.8%
4.2
Tahu Search
733.79
0.21%
2926.6
2. 2.10%
11.5
Greedy
688.31
6.39%
0.02
2761.06
7.64%
0.29
704.03
4.26%
5.20%
Erdos
UL 693.45
5.69%
0,07
2870.34
3.98%
Anneal
UL 696.73
5.25%
2863.23
4.22%
0.24
GFlow
UT. 704.3
4.22%
0.27
2864.61
4, 4.17%
1.95
CSP
726.96
2925.8
2.12%
ANYCSP
UT. 725.12
0.03%
2,5
2988.6
0.02%
7.37
DIFUCO
733.5
0.25%
2.77
2981.1
0,27%
X (GNN(1688)
UT. 734.21
0.15%
0.08
2985.2
0.14%
0.2
GNN(6448)
UL.
734.92
0.05%
0.15
2987.7
0.05%
0.48
X (NN(25688)
735.17
0.02%
2988.7
0.02%
X (GNN2256322
735.26
0.01%
0%
X GGN (BA250)2566x22
UL 735.26
0.01 %
4.1
2985.5
0.13%
These results indicate that on 3 CO problems, XºGNN outperforms neural baselines, is competitive with specialized metaheuristies like KaMIS, and improves over general solvers like Gurobi.
5.4 ABLATION
In this section, we analyze the impact of K-coupled solutions for different values of K. We also measure the impact of stochastic refinement, two-stage training, and encouraging diversity.
Table Effects of the parameter K K-coupled solutions, showing K gives the lowest drop.
Problem
K =1
K= =
K =
K
MIS MC MCut
4.015:
0.43%
3.81%
9.47%
0.14%
0.01%
0.21%
1.79%
0.030%
0.015%
0.021%
0.157
Table 5 demonstrates that K 2 is the optimal choice for each problem. Its impact is particularly significant for MIS, while more subtle for MC and MCut.
We evaluate the impact of ablating aspects of X 2 by comparing achieves a drop value of 0.43% on MIS. Using deterministic refinement instead of stochastic refine- ment significantly increases the drop value to 4.97%. Training the full framework in single stage increased the drop value to 1.44%. Similarly, ignoring the diversity loss raises the drop value to 1.81%. These findings highlight the cumulative benefits our proposed techniques. The combination of K = 2 coupled solutions, stochastic refinement, two-stage training, and diversity loss is crucial for the superior performance of X
standard version which
5.5 NEURAL SEARCH DYNAMICS
For fixed budget, GNN controllably balance exploration and exploitation by trading off the number solution couples generated at each iteration C, with the number iterations taken.
MC and MIS problems benefit from different exploration-exploitaiee feasible region structures: In MC, selecting node restricts subsequent additions to only its neighbors, causing the search space contract rapidly with each decision. Early choices have high impact, potentially eliminating optimal solutions if poor selections are made. Consequently, exploring diverse starting points (higher C) becomes crucial. In MIS, selecting node only eliminates its neighbors
trade-off's due to their distinct

---

Published as a conference paper at ICLR 2025
from consideration, typically leaving a substantial portion of nodes available. This more gradual search space reduction allows solutions to recover from suboptimal early choices through additional refinement iterations.
As shown in Figure S our experiments confirm these insights. Figure SggureBajennee Baddemonstrates that MC benefits from prioritizing exploration (higher C), with C=64 providing optimal performance. Conversely, Figure (3) shows that MIS performs better with emphasis on exploitation (higher T, lower C), with C=4 yielding the best results.
These findings highlight that while all combinatorial optimization problems require both strategies, their relative importance varies based on how solution construction progressively constrains the search space.
Search Dynamics Max Clique
Search Dynamics for Max Independent Set
% Drop in quality vs optimal
Drop in quality vs optimal
10
10t
C-2
10p
CH4
C-16
C-10
10-1
C-64
C-64
102
Total number of solutions C
Total number of solutions C+T
(a)
(b)
Figure Search dynamics on RB250: Each line corresponds to one setting of C. where higher values increase exploration. We present the drop in solution quality (lower is better) over various computational budgets. For MC, higher values C yield better performance, suggesting the search benefits from broader exploration of the solution space. Conversely, for MIS, lower values of C' lead to better solutions, indicating the search benefits from deeper exploitation of promising regions.
6 CONCLUSION
In this work, introduce Explore-and-Exploii GNN (X?GNN), novel unsupervised neural framework that addresses a key challenge in tearning-based combinatorial optimization (CO). Unlike most existing approaches that focus on constructing a limited number of solutions, X"GNN effectively explores the vast search space of NP-hard CO problems through two key mechanisms:
(i) Exploration: X"GNN generates multiple solutions simultaneously, and promotes solution diversity.
(ii) Exploitation: GNNN employs neural stochastic iterative refinement, using sampled partial solutions to guide the search toward promising regions and escape local optima.
Our experiments on three canonical NP-Hard CO problems - Maximum Clique (MC), Maximum Independent Set (MIS), and Maximum Cut (MCut) demonstrate that X*GNN significantly out- performs state-of-the-art learning-based approaches. Notably, for large MC problems, X"GNN consistently generates solutions within 1.2% of optimality, while other learning- based methods struggle to reach within 22% of optimal. Moreover, 22NNN exhibits exceptional generalization capabilities, outperforming existing methods even when trained on smaller or out-o--distributtin graphs. The iterative nature of X"GNN allows users to trade off runtime and solution quality, as the model can be applied indefinitely to refine solutions. This feature, combined with its strong performance and generalization performance, positions X*GNN as a competitive framework with promising directions for future research in learning- based heuristics for combinatorial optimization. By balancing exploration and exploitation, 'NNN offers more effective and adaptable approach to neural combinatorial optimization, addressing the limitations of existing methods and paving the way for robust solutions to complex CO problems across various domains.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This project is partially supported by Schmidt Sciences programs, an A12050 Senior Fellowship and two Eric and Wendy Schmidt AI in Science Postdoctoral Fellowships; the National Science Foundation (NSF); the National Institute Food and Agriculture (USDA/NIFA); the Air Force Office of Scientific Research (AFOSR). Additionally, Utku Umur Acikalin is supported by the Turkish Ministry of National Education.
REFERENCES
Agoston E Eiben and Cornelis A Schippers. On evolutionary exploration and exploitation. Funda- menta Informaticae. 35(1-4):35 1998.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2)400--21,, 2021.
James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. In International Joint Conference Artificial Intelligence, 2021.
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( (41130):1661, 2023.
Elias Boutros Khalil, Pierre Le Bodic, Le Song, George L. Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizoma, USA, pages 724-731, AAAI Press, 2016. doi: 10. 1116699AAAAL30110 609
URL httph:tt////....... /https:://oi.ooo http://otoooooooooo/
v301 10080
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT solver from single-bit supervision. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
hittps://openreet ew net forum HMC 1A5tm
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks. CoRR, abs/2012. 13349, 2020. URL http:s://aaxiii.....//
2os.2 13349
Zhiqing Sun and Yiming Yang. Difusco: Graph- diffusion solvers for combinatorial opti- mization. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 3706-3731. Curran Asso- ciates, Inc., 2023. URL 2023 2023/file/0batee 22207//1162230333322212111131113
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what we cannot teach. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10831-10841. PMLR, 13-18 Jul 2020. URL htttps://proceed:: v119/yehuca200 html
www.mlll...r......mm press/
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
Yimeng Min, Frederik Wenkel, Michael Perlmutter, and Guy Wolf. Can hybrid geometric scattering networks help solve the maximum clique problem? Advances in Neural Information Processing Systems, 35:22713-22724, 2022.
Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. arXiv preprint arXiv:2406.0166 2024.
11

---

Published as a conference paper at ICLR 2025
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Vari- ational annealing on graphs for combinatorial optimization. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural In- formation Processing Systems, volume 36, pages 63907-63930. Curran Associates, Inc., 2023. URL htttpss:/prroeeeednggggooo/ neur cctppp.cccppeeee wttp:r/ffiiaaaaaae///////// Paper www.eonnnneee..o.. pdf
File/ #ile/ccccccccdes2222222221111111 Con.aeaerreeatcaaaaaaoooo-eeeeee
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 11952-11990 Curran Asso- ciates, Inc., 2023. httphhttss:/ppoceeeeteet 2023
neur wttp:rppppppppppppppppppppp files/paprreeree
Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 2256-2263 JoLR.org, 2015. html
ngs. mlr r. wea.r.pess//ve wwt.pprrss////////ee www.:/3///hh1iichhee
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NewrlPS 2023, New Orleans, IA, USA, December 10 16, 2023, 2023.
Thomas Cormen, Charles E. Leiserson, Ronald L.. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press and McGraw-Hill Book Company, 2001. ISBN 0-262-03293-7.
Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages (6695-67066 2021. URL http:htttt:::ppceeeeeeeeeeeeeeee ings neur ps. CC/ htap://222..aaaaa322222222222662
-bsteeeffaaaae---aaaaaacco Abst .html
Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Extrapolation without overthinking. In Sanmi Koyejo. S. Mohamed, Agarwal, Danielle Belgrave, Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- De- cember 9, 2022, 2022. URL http: http//aaaassseaaa www..iipp.comm wwwphipp.cpppppppppppp haappper_fiees/ppeaeee wewlle//ppe//eee /
html
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representationss, ICLR 2019, New Orleans. LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL httlhtttp:///opeeeeet id=ryGs61A5km
net. forum?
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In The Tenth In- ternational Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.ne, 2022. URL htt.:ttts://ppeeeeeeee
net. for.mm wttp://teeoooommmm///m2mxxxxmmmm www.:nettttteeee
12

---

Published as a conference paper at ICLR 2025
Hanjun Dai, Xinshi Chen, Yu Li, Xin Gao, and Le Song. A framework for differentiable discovery of graph algorithms. In Learning Meets Combinatorial Algorithms at NeurlPS2020, 2020.
Ke Xu and Wei Li. Exact phase transitions random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12:93-103, 2000.
Ian P Gent, Ewan MacIntyre, Patrick Prosser, Barbara M Smith, and Toby Walsh. Random constraint satisfaction: Flaws and structure. Constraints, 6:345-372, 2001.
Barbara M Smith and Martin E Dyer. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 111-2)):15-111 1996.
Erdös and A Rényi On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-57) 1999.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https::///// www gurobi com
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pages 138-150 SIAM, 2016.
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. In International conference on machine learning, pages 134-144. PMLR, 2020.
Haoran Sun, Etash K Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint ar arXiv:2207.11542 2022.
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Ankur Nath and Alan Kuhnle. A benchmark for maximum cut: Towards standardization of the evaluation of learned heuristics for combinatorial optimization. arXiv preprint arXiv:2406.11897, 2024.
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maximum constraint satisfaction. Frontiers Artif. Intell., 3:580607, 2020. doi: 10.338/FRAA.2000.58666 URL
3389/ frai.rri....... 338. 2020. 580607
Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe. One model, any csp: Graph neural networks fast global search heuristics for constraint satisfaction. In Edith Elkind, editor, Proceedings of the Thirty-Second International Join Conference on Artificial Intelligence, IJCAI- 23, pages 4280-4288 International Joint Conferences Artificial Intelligence Organization, .0233/
2023. doi: 02224966/jccii222234777 /
476
Main Track.
William Duckworth and Michele Zito. Large independent sets in random regular graphs. Theoretical Computer Science, 5236655))53655444 2009.
DIMACS. The second dimacs implementation challenge: 1992-1993. ac.
Attps://iridia,
www.://MMMMM--eceereaeeaa.a Accessed: 2024-11-20.
Renee Mirka and David Williamson. An experimental evaluation of semidefinite programming and spectral algorithms for max cut. ACM Journal of Experimental Algorithmiic, 28:1-18. 2023.
13

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL DETAILS
A.1 NETWORK ARCHITECTURE
We use a GNN architecture where Graph Isomorphism Network (GIN) Xu et al. (2019)) and Graph Attention Network (GAT) (Velickovic et al. (2188); [Brody et al. (022)) layers used in interleaved manner. We use 72 GIN and GAT layers. The initial node features (node probabilities) transformed to higher dimension by a linear layer before they passed to the first GIN layer.
The GIN layers work on the original edges and GAT' layers work on the crossedges. GIN layers composed of two-layer MLPs with RELU activations after the MLP layers. We apply Layer Normalization after each MLP layer in GINs and after each GAT layer. We add skip connections to both GIN and GAT layers. Finally, the output of each GAT layer is concatenated and fed into a final two-layer MLP. This architecture is executed recurrently starting from the last hidden representation from MLP n times. The final output transformed into logits and the probability that each node belongs to S is computed via Softmax. For all problems, the architecture hidden representation size is 64.
A.2 EYPERPARAMETER
the hyperparameters on each dataset is given Table 6 nt, n represents the number of layers and number of recurrent steps. K and C means C' K Coupled solutions are generated during training. On all settings, we select K = and C = during training. K and C' values used during inference are shown right next to the model. \ and x2 are the weights of the constraint and diversity loss, respectively.
Dataset
Ir
bs
TL
K
C
Ø
A1
A
RB-250 MIS
50
0.001
64
2
2
4
0.5
0.75
RB-1000 MIS
50
0.001
64
4
4
64
2
4
0.5
1
0.75
ER-750 MIS
50
0.001
64
4
4
64
2
4
0.5
0.75
RB-250 MC
50
0.001
64
4
2
64
2
4
0.8
0.75
BA-250 MCut
50
0.001
64
4
2
64
2
4
0.8
0.75
BA-1000 MCut
50
0.001
64
4
4
64
2
4
0.8
0.75
Table 6: Hyperparameters used in training.
A.3 COMPUTATIONAL RESOURCES AND TIME MEASUREMENTS
All experiments are conducted on machine with 2 Intel Xeon 6348 processors with 28 cores, 1TB of memory, and 4 A100 80GB GPUs. All traditional heuristics are run using a single core and Gurobi run with 4 cores, allowing 40GB of memory for each instance.
We only use A100 during training or inference for all datasets. The training time for MIS is roughly hour and hours for RB250 and RB 1000 datasets, respectively. The training time for MCut is roughly I hour and 3 hours for BA250 and BA1000 datasets, respectively. The training time for MC roughly 2 hours for the RB250 dataset.
For baselines, we run each method in our machine and report the time we obtain our machine to have a fair comparison. However, we use the original size when available on the same dataset split.
B ADDITIONAL EXPERIMENTS
B. ADDITIONAL EXPERIMENTS FOR MAXIMUM CLIQUE
For MC, we consider a challenging dataset from DIMACS implementation challenges related Maxi- mum Clique (DIMACS). This dataset contains 37 challenging graphs. We the GNNN model trained on the RB- 1000 dataset as well as its fine- tuned version. We report the performance of X"GNN 256x32 with and without fine-tuning as well the best traditional heuristic KaMIS.
14

---

Published as a conference paper at ICLR 2025
Table Table shows the clique size and the running time for each instance for X and KaMIS, considering that G'N FT fine-tunes GNNNN these instances, and X is trained only RB instances. The clique sizes matching the best-known solutions are shown in bold.
Size
Runnig Time
Instance
n
m
Best known
KaMIS
G'NN FT
G'NNN
KaMIS
G'NNN FT
GNGNN
hmc1-20
brock200_4
200
13,089
17
16
16
16
5.45
3,7
3.67
brock400
400
59,786
24
24
24
9.17
4.35
brock400__
400
59.765
25
25
25
8.77
4.28
4.29
brock800
800
208 166
24
20
20
20
33,91
10.84
10.79
brock8000_4
20
C1000,9
1,000
450,079
68
66
66
64
19.06
6,68
6.59
C125.99
125
6,963
C2000.5
2,000
939,836
15
14
0
188 88
72.63
72.4
C2000,9
2,000
1,799,532
75
75
73
45.28
17.67
17.59
C250.9
250
27.984
44
44
44
5.15
3.65
C4000.5
4,000
4,000,268
16
D
596.31
367.1
369.75
C500.9
56
DSIC1000_5
1,000
499.652
15
15
12
12
70.18
20.1
19.96
DSICS00_5
500
125,248
13
26.61
7.24
1,3000_0..9_44
200
17,910
44
44
44
44
5.20
3.71
3.59
gem200_p0.9..
200
17,910
55
55
55
5,20
3.74
3.6
gen400 p0.9__5
400
71,820
53
55
55
5.35
3.71
3.58
gen400__pe p0.9 65
400
71,820
65
63
63
5.22
3.71
3.58
gen400_pp. p0.9_.5
75
75
hamming10.. 10-4
1,024
434,176
40
38
40
38
12.24
9.53
944
hamming8-4
256
20,864
16
16
16
5,76
3,55
kellerd
171
9,435
11
11
11
5.40
3.71
3.58
keller5
776
225,990
26
23
27
10.97
8.32
8.26
kellers
3,361
4,619,898
59
39
43
61.87
75.01
75.2
MANN_a27 a27
378
70,551
126
126
126
92
5.05
3.69
3.57
MANN_a8 a81
3,321
5,506,380
1100
1100
1097
664
5.06
4,25
4.14
p_hat1500-1
1,500
284,923
11
10
88.97
61.61
60.96
p. h_ba11500-2
1.500
568,960
65
65
62
85.44
39,96
40.47
P. hat
1,500
847,244
94
94
94
44.08
22.49
22.45
har300-1
300
10,933
18.69
5,27
5.19
hat3300-2
300
21,928
25
25
25
12.02
4,48
4.38
h0030033
P_hat700-1
700
60,999
11
9
2
42.16
15,36
15.27
P_hat700-2
700
121.728
44
44
44
25.06
11.49
11.42
P_ha1700-33
700
183,010
62
62
62
13.62
7.38
7.31
Table shows that X²GNN is able generalize and generate optimal or near-optimal solutions on many instances even though it is trained on RB RB0000 instances, set of much sparser instances. However, it does fail to generate good solutions on a few instances. With fine-tuning, solution quality improves quite lot both for these failing cases and also in general, leading to average gap of 6.68% from 17.41%. %. Even the most successful traditional heuristic KaMIS achieves an average gap of 3.87%. Considering this dataset is designed be challenging dataset, learning general rule based on RB 1000 instances that can solve many problems, and achieving a gap of 6.68% after fine-tuning noteworthy.
B.2 ADDITIONAL EXPERIMENTS FOR MAXIMUM INDEPENDENT SET
For MIS, we evaluate G performance on an additional dataset that comprises instances from Coding Theory applications, specifically error correction codes, with graph sizes ranging from 64 to 4,096 nodes. For this dataset, we utilize the X"GNN model trained on the RB 1000 dataset. We compare against KaMIS, the state-of- of the-the-ad art MIS solver.
On the Coding Theory dataset (Table 8 X "GGN finds the best-known solution in 20 of 32 instances, compared KaMIS's 28 instances. X "GGNN achieves an average gap of 3.37% from best-known solutions (versus 0.34% for KaMIS). Excluding less than half the best-known value, > average gap improves to 1. 1.74%. This performance is notable given domain-specifee tuning performed.
outlier instance where X²GNN finds solution
To demonstrate X²GNN's adaptability to weighted problems, we extend it to weighted maximum independent set problems with minimal modifications: adding weight embedding layer combined
15

---

Published as a conference paper at ICLR 2025
Table 8: The table shows the size of the independent sets found by G and KaMIS and the running time in seconds for each instance. The last row shows the average gap in percentages from the best-known solution. The instances where a method found the best-known solutions are shown in bold.
Graph
Best Known
X*GNN 256x32
KaMIS
X*GNN 256x32 Time
KaMIS Time
1dc.64
10
10
10
5.06
5.14
1dc.128
16
16
16
3.87
4.04
25c
30
30
30
4.37
4.50
1dc.512
52
52
52
6.33
6.49
Idc.1024
94
94
93
11.29
11.40
1dc.2048
172
172
172
24.25
24.40
let.64
18
18
18
3.81
1.31
lct.128
28
28
28
3.81
3.85
lct.256
50
50
50
3.82
3.90
let.512
100
98
100
4.68
4.74
let.1024
171
165
171
7.12
7.23
let.2048
316
300
316
13.95
14.02
Itc.8
4
4
4
3.71
0.48
ltc.16
8
8
8
3.76
0.81
Itc.32
12
12
12
3.76
0.30
Itc.64
20
20
20
3.79
1.10
Itc.128
38
38
38
3.75
1.15
Itc.256
64
63
63
3.78
3.88
Itc.512
110
109
110
4.39
4.48
1024
196
189
196
6.64
6.73
Itc.2048
352
332
352
12.91
13.00
Izc.
18
18
18
3.77
3.87
1zc.256
36
36
36
3.99
4,10
1zc.512
62
62
62
5,46
5.55
12c.1024
112
109
112
9.13
9.32
1zc.2048
198
181
195
18.78
18.89
Izc.4096
379
326
353
40.19
40.41
2dc.128
5
5
5
4.52
1.46
2dc.256
7
7
7
8.22
10.06
2dc.512
11
11
11
19.07
22.31
10c.1024
15
16
52.72
57.81
2dc.2048
24
11
24
152.61
162.73
Average Gap
3.37%
0.34%
with node representations via summation, and incorporating weights into the loss function calculation. Using the RB250 dataset with uniform random integer weights between 1 and 5, we compare against optimal solutions from Gurobi. Table 9 shows X²GNN maintains high solution quality with 0.8% optimality gap.
Table Results for Weighted Maximum Independent Set on small RB graphs, presenting the mean independent set size, drop in quality compared to the optimal, and run time in seconds.
Method
Type
RB250
Size f
Drop +
Time +
Gurobi
OR
82.94
0%
0.21
X²GNN(16X8)
UL
78.52
5.33%
0.03
(64x8)
UL
80.26
3.23%
0.09
GN2N(22668
UL
81.31
1.97%
0.35
X GNN(256x332)
UL
81.83
1.34%
1.25
X (02443333
UL
82.28
0.8%
4.92
16

---

Published as a conference paper at ICLR 2025
In ablation study, replaced the GAT layer with simple MLP for processing cross-edges. Table 10 shows this variant still outperforms other learning based approaches but underperforms compared to the GAT version, indicating GAT's superior capability in aggregating information across different solutions.
Table 10: The results for replacing GAT layers with simple MLP layer.
Method
Type
RB250
Size
Drop +
Time 4
KaMIS (30min)
OR
20.106
0%
3,92
Gurobi (30min)
OR
20.106
0%
0.31
KaMIS (Quality)
OR
20.106
0%
3.92
Gurobi (Quality)
OR
20.106
0%
0.42
KaMIS (Fast)
OR 20.032
0.37%
1.16
Gurobi (Fast)
OR
19.16
4.71%
0.1
PPO
UL 19.01
5.45%
0.15
GFlow
UL 19.18
4.61%
0.05
DIFUSCO
SL 17.68
12.07%
0.87
T2T
SL
18.35
8.73%
2.32
DiffUCO
UL
19.24
4.31%
0.42
(GGNN-GAT(16X3)
UL 19.51
2.96%
0.034
X2GNN-G-AT(64888
UL
19.82
1.42%
0.128
X=GNN-GAT(256X8)
UL
19.98
0.63%
0.5
X=GNN-GATT(56X322
UL
20.072
0.17%
1.94
(GGN-GGAT(1024433)
20.098
0.04%
7.11
X
UL 18.95
5.75%
0.027
X2 GNN-MMPP6443))
UL
19.41
3.46%
0,096
X GNNNMML2(25668
UL
19.698
2.03%
0.38
X GLPN2222)(56632
UL 19.886
1.09%
1.35
B.3 ADDITIONAL EXPERIMENTS FOR MCUT
For the Maximum Cut (MCut) problem, evaluate G nut-of-distribution performance on two additional benchmark sets. The first dataset, introduced in MMira and Williamson (2023). comprises diverse graphs from the SNAP Networks repository (referred to SNAP dataset). This dataset is particularly suitable for assessing generalization capabilities due to its heterogencous graph distributions. The second dataset, known Gset traditionally used to evaluate MCut algorithms.
well-established benchmark collection
To train GNN,, generate 4,000 Erdös-Rényi (ER) graphs with sizes uniformly sampled from between 200 and 500 and edge probabilities from [0.1, 0.75). We then evaluate the trained model on both SNAP and Gset datasets.
Table 11
presents results for the SNAP dataset, comparing 'NNN against ANYCSP (trained on the same dataset), Tabu Search (TS). Semidefinite Programming (SDP) relaxation, and BMZ heuristic from Mirka and Williamson (202)). XºGNN discovers the best solutions among all compared methods for all but two instances, demonstrating superior performance over both ANYCSP and traditional heuristics.
For the Gset evaluation, we use on all unweighted GSET instances, demonstrating that X*GNN can generalize larger instances. Table 12 shows the cut size achieved by the traditional heuristics BLS, DSDP, KHLWG and learning based heuristics X2GNN and ANYCSP for each instance. To aggregate the results, we first compute the virtual best solution by taking the maximum value found by any of the compared algorithms. Then, for each instance we compute the average gap from the best as 1 solution/best and take the mean to calculate the average gap from the virtual best solution.
17

---

Published as a conference paper at ICLR 2025
Table 11: Table shows the cut sizes for instance and method. The cut sizes matching the best are shown in bold.
Graph
X GNN (256x32)
ANYCSP
TS
BMZ
SDP
ENZYMES8
88
133
126
126
126
126
126
johnson 16-2-4
120
5460
3036
2941
3036
30336
3036
hamming6-2
64
1824
992
946
992
992
992
ia-infect-hyper
113
2196
1279
1208
1279
1278
1275
soc-dolphins
62
159
122
122
122
122
122
email-enron-only
143
623
427
427
427
426
422
dwt_209
209
976
557
557
557
557
551
ca-netscience
379
620
580
627
634
634
ia-nffect-dublin
410
2765
1771
1709
1758
1767
1750
road-chesapeake
39
170
126
126
126
126
125
Erdos991
492
1417
1036
1036
1012
1031
1019
dwt_503
503
3265
1938
1938
1937
1931
1934
p-hat700-1
700
60999
33413
31856
33426
33440
33450
email-univ 1133
5451
3775
3764
3657
3765
3736
The results indicate that X2GNN achieves average gap of 0.12% from the best solutions among the compared ones under the 64x256 setting, which has a maximum running time of seconds on the largest instance with 10 nodes. ANYCSP under the 64x256 setting has a similar running time and achieves an average gap of 0.69% from the best solution. When we increase the number of refinement iterations by order of magnitude, the average gaps achieved by X2GNN and ANYCSP 0. 0.12% and 0.56%, respectively. Despite having an order of magnitude longer runtime, ANYCSP achieves higher average gap than X2GNN at even short runtime. These results show that both methods scalable and can generate high-quality solutions to larger and different distributions than those seen during training; however, X2GNN performs better than ANYCSP.
Additionally, X2GNN generates solutions with a smaller gap on average than the second best traditional heuristic KHLWG, whereas ANYCSP consistently generates solutions with higher gap than KHLWG.
18

---

Published as a conference paper at ICLR 2025
Table 12: Results for Max Cut Gset dataset, presenting the cut size for each instance. The last row shows the average gap in percentages from the best solution.
Graph
BLS
DSDP
KHLWG
X2GNN 64x256
ANYCSP 64x256
X2GNN 64x2560
ANYCSP 64x2560
GI
11624
11624
11583
11582
11598
11616
G14
3064
2922
3061
3054
3021
3058
3035
GI5
3050
2938
3050
3043
301
3036
3024
GI6
3052
3052
3040
3011
3045
3024
G17
3047
3046
3037
3002
3039
3018
G22
13359
12960
13359
13339
13263
13347
13285
13344
13006
13342
13319
13247
13329
13309
G24
13377
12933
13337
13310
13273
13319
13276
G25
13340
13332
13311
13248
13327
13287
G26
13328
13328
13296
13236
13306
13272
03
11622
11620
11583
11581
11591
11614
G36
7678
7670
7646
7529
7654
7566
G37
7689
7682
7665
7546
7666
7593
G38
7687
7683
7649
7547
7658
7570
G4
11646
1 16466
11597
11612
11617
11633
6660
6622
6639
6651
G44
6650
66.39
6645
6622
6646
6631
G46
6649
66-49
6639
6622
6644
6637
G47
6657
6665
6651
6626
6654
6647
G48
6000
6000
6000
6000
6000
6000
6000
G49
6000
6000
6000
6000
6000
6000
6000
11583
11594
G50
5880
5880
5880
5872
$846
5880
5876
3847
G52
3851
3849
3835
3792
3840
3805
G53
3850
3848
3841
3796
3844
3812
G54
3852
3851
3842
3791
3841
3802
G55
10294
9960
10236
10241
10066
10283
10141
19248
G60
14176
13610
14057
14121
13855
14146
13952
26997
8017
26963
26863
G70
9541
9456
9458
9492
9189
9525
9290
GeoMean
7726.5
7703.5
7667.0
Mean Gap
0.01%
0.13%
0.12%
0.69%
0.11%
0.56%
19


Reviews:
[{"review_id": "kZnwtwjen6", "reviewer": "Reviewer_Kcjm", "summary": "The paper proposes an iterative neural approach to search for solutions to graph combinatorial optimization (CO) problems. The approach is based on two phases: the generation of a diverse pool of solutions and their iterative improvement. The training is unsupervised and relies on a composite loss that combines the continuous relaxation of the CO problem objective, a penalization of the constraint violation and a diversity-encouraging term. The approach is evaluated on three graph CO problems and shows a very good performance compared to learning and non-learning based methods as well as a strong generalization performance.", "questions": "* L258: the paper states that the training is done in two stages. Are they done sequentially or alternatively? The arrows in Figure 1 towards the \"loss block\" made it confusing to me.\n\n* In the Ablation section, when evaluating the impact of K, what was the value of C? In particular, it's important to evaluate the effect of K=1 with a large C, to demonstrate the value of the K-coupled solutions. \n\n* Remarks:\n  * L245, L252 it may be misleading to state that the diversity is \"imposed\" through a loss, \"encouraged\" would be more clear.\n  * It would be helpful to give an explanation of the corresponding equations L249 and L254 \n  * Since at training, T=1, the authors could get rid of the t index in the description to lighten the notations", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Novel unsupervised framework to generate solutions to graph CO problems \n* The framework components, in particular the architecture and the loss are generic and should apply to a variety of CO problems defined on unweighted graphs. \n* Original way to deal with several solutions for a given instance by constructing a \"K-coupled graph\" that allows to capture the whole collection of solutions to input to the refinement step.\n* Strong and consistent performance on the three problems and nice generalization to larger instances\n* The paper cites and compares to a number of relevant baselines in the experiments", "weaknesses": "* While the paper explains well how the hyperparameters (K, C, T, $\\phi$) control the exploration/exploitation trade-off, the paper does not provide clear guidelines on how to choose good values for these hyperparmeters, except a grid-search. \n    * In Sec 5.5, the paper claims L253 \"Different search strategies are needed for MC and MIS due to the different feasible regions. MC requires exploration to avoid local optima, and MIS requires exploitation to improve solutions.\" I don't understand this argument, can the authors elaborate on this? \n    * In general, for all CO problems and search methods, there is a risk of getting trapped in a local minima and a need for solution improvement. I can't see how one can decide beforehand what is more important for a given problem, especially since it may depend on the instances. \n\n* Comparing the run times between learning-based approaches which usually run on GPUs and OR solvers which run on CPUs is always delicate to interpret and gives a partial view of the efficiency of the methods. While there is no straightforward way to make the comparison more fair, it should at least be acknowledged.\n   * In addition, the paper does not provide information on the machines on which the experiments were done -- this is especially important to appreciate the claims on the run times.\n\n* The main paper contributions are to compute meaningful output probabilities on the nodes but then only a simple rule or a greedy method is applied to construct a feasible solution (See paragraph Converting Soft Solutions to Hard Solutions). \n   * Using a threshold of 0.5 seems arbitrary to chose whether or not a node is part of the solution. Did the author try other values? How one can choose this threshold for a new problem?\n   * Given the probabilities, more sophisticated search methods can be applied such as beam search, Monte Carlo tree search or a least stochastic sampling (similarly to what is done when the model outputs heatmaps for example in the cited DIFUSCO method). \n   * Evaluating the proposed approach in combination with a stronger search technique, like the above, would be interesting and strengthen the claims. \n   * The question being: is the proposed approach useful only when a simple rule is used to construct the solutions or is it also helpful when combined with more sophisticated search?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w2wugLDBhv", "reviewer": "Reviewer_m7s4", "summary": "This paper presents an explore-and-exploit Graph Neural Network (GNN) framework for combinatorial optimization (CO) problems. The key idea involves generating multiple solutions simultaneously to facilitate exploration while employing neural stochastic iterative refinement for exploitation. This approach effectively balances exploration and exploitation, leading to high-quality performance. Experiments conducted on three CO problems—namely, the maximum independent set, maximum clique, and maximum cut—demonstrate that the proposed algorithm outperforms learning-based algorithms in the literature.", "questions": "1. During the iterative refinement process, do the local optimal solutions occur at intermediate steps, or do they only manifest in the final iteration?\n2. How are the values ​​of C and T determined for each CO problem?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed framework utilizes Graph Neural Networks and unsupervised learning to effectively balance exploration and exploitation for combinatorial optimization problems.\n\n2. Empirical results demonstrate high-quality optimization performance and goode generalization capabilities compared to learning-based baselines.", "weaknesses": "1. The encoder uses multiple original graphs as input; however, the rationale for connecting identical vertices across these graphs with edges is unclear. Table 5 only presents comparison results for the MIS and MC problems, why are the results for MCut not included? The description of the Drop Value is unclear, it would be better to provide a more detailed comparison of the results. Additionally, the drop value for K=2 shows a significant difference only in the context of MIS.\n\n2. There is a lack of an ablation study on the design of the total loss function. The total loss function includes includes objective quality, constraint satisfaction, and solution diversity. It would be useful to analyze the results when the loss function includes only one of these components, such as solely objective quality, as well as the combination of objective quality and constraint satisfaction, and the combination of objective quality and solution diversity. This comparative analysis could provide insights into the impact of each loss component on the overall performance.\n\n3. The result comparisons for each CO problem contain too few types of benchmarks. MC and MIS are closely related problems, and the instances tested in the experiments should remain consistent. Additionally, it would be beneficial to include more results for RB graphs and ER graphs. For the Max Cut problem, providing more results for BA graphs would also be helpful. Furthermore, testing the proposed algorithm on DIMACS and COLOR02 instances would demonstrate its generalization capabilities.\n\n4. It would be beneficial to explicitly state the limitations of the proposed approach, for example, the scalability issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iEh08jW3lP", "reviewer": "Reviewer_sKQy", "summary": "In this paper, the authors propose a framework that combines exploration and exploitation for combinatorial optimization (CO). The proposed framework explores the search space by generating a pool of solutions and exploits the promising ones through refinement. The model is based on Graph Isomorphism and Graph Attention Network, it outputs soft solutions that are heuristicly converted to hard solutions. The framework is applied and tested on three graph CO problems: the Maximum Clique Problem, the Maximum Independent Set Problem, and the Maximum Cut Problem.", "questions": "1. Is it possible to apply this approach to other combinatorial optimization (CO) problems, such as routing or scheduling? Or to graphs with node/edge features (e.g., the Maximum Weighted Independent Set/Clique)?\n\n2. What is the motivation for using Graph Isomorphism Networks (GIN) and Graph Attention Networks (GAT) and constructing the multilayer graph in the way described? There is no theoretical or empirical discussion justifying this choice. The ablation study shows that using more than two coupled layers degrades performance, which is really surprising This may suggest that GAT struggles to propagate information effectively across more than two solutions and/or that the proposed simple multilayer graph, which connects only copies of the same node in G, is not powerful enough to represent relations between solutions. Did you try using a more sophisticated multilayer graph and/or a different method to aggregate the data between solutions?\n\n3. Following this, the multilayer graph for 2-coupled solutions (as used in the experiments) is very simple - it has 2N nodes and N edges (one edge per pair of corresponding original nodes). GAT is designed to aggregate information from many neighboring nodes, so using it on such a simple graph (in effect, it computes attention between just two nodes) seems odd and possibly unnecessary. Wouldn't a simple MLP achieve the same result?\n\n4. In the discussion of experiments, much emphasis is placed on comparing results based on running time, but no details are provided on how the experiments were conducted. Were the solvers and models run on the same hardware? Were they tested under the same conditions (e.g., serial or parallel execution)? Neural networks can often solve multiple instances in parallel batches on GPUs, which might not be the case for solvers executed on CPUs (which are inherently much slower than GPUs by design). Claims about running times are only comparable if all methods are tested under similar conditions; otherwise, the comparison could be confusing. E.g. claim No. 4 \"We additionally allow solvers a 30-minute time limit, which is at least 24 times longer than our longest-running model.\" could be misleading. By checking results, Gurobi is in most cases much faster than the proposed method (e.g. in Table 1 Gurobi vs. longest-running model for RB250 is 0.31s vs. 1.41s). \n\n5. All CO problems have simple greedy heuristics, such as choosing the node with the smallest degree for the MIS problem. Did you attempt to exploit this for the initialization of node features (e.g., assigning lower probabilities to high-degree nodes since they are less likely to be part of the solution)? This approach might provide a better initialization than random and could lead to faster learning.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The idea of using K-coupled solutions for exploration and Iterative Stochastic Refinement for exploitation looks original and promising.\n- The model shows excellent results; the proposed method outperforms state-of-the-art learning-based approaches not only on the training distribution but also in terms of generalization to larger problem sizes.", "weaknesses": "- Main concern: reproducibility seems impossible. There are no details about the implementation, only a brief description of the architecture  ('2L layers' of GIN and GAT), with no further details. There is no mention at all of the hyperparameters and the training process.\n- The proposed framework is tailored to a small subclass of CO problems. It can be applied to simple graphs, defined by their adjacency matrices, and to problems where solutions can be represented as binary decisions for each node. This makes the framework inapplicable to other classes of CO problems, such as routing or scheduling, as well as to any graph problems with node or edge features.\n- Although the paper claims that the method promotes solution diversity by generating multiple solutions simultaneously, in practice, the pool contains only two solutions. The method struggles when more diverse solutions are provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Asby5gkNv", "reviewer": "Reviewer_aRXC", "summary": "This paper proposes GNN-based framework to solve several classic combinatorial optimization problems. The proposed approach behaves like a population-based heuristic method. Since extensive efforts have been devoted to the development of machine learning methods for addressing combinatorial optimization, I'm concerned about whether it can outperform the state-of-the-art algorithms.", "questions": "See the weakness part.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The proposed network generates $K$-coupled solutions and behaves like a population-based heuristic method. This is kind of novel.", "weaknesses": "I have a few concerns below.\n\n- Line 245, the loss function includes constraint satisfaction and solution diversity. How to choose $\\lambda_1$ and $\\lambda_2$? Usually, the penalty method demonstrate very weak generalization capabilities. Hence, I personally think combining several terms in the loss function is not a good idea.\n\n- For MCut and MIS comparison, a state-of-the-art algorithm [1] should be considered as baseline. This algorithm [1] is quite scalable and able to provide high-quality solutions to MCut and MIS.\n\n- The proposed algorithm is not very scalable. For example, in Table 2 and 3, the computational time increases quickly with the problem size. MIS, MC and MCut are simple combinatorial optimization problems. Why not consider some large-sized instances (for example, Gset instances for MCut,  https://web.stanford.edu/~yyye/yyye/Gset)? How does the proposed algorithm perform?\n\n[1] Schuetz, M.J., Brubaker, J.K. and Katzgraber, H.G., 2022. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4), pp.367-377.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)