Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
Authors: Yikai Wu
Haoyu Zhao
Sanjeev Arora
Venue: Accepted by TMLR ()

Abstract: AI methods, such as generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on Maximum Independent Set (MIS). Strikingly, even on in-distribution random graphs, leading AI-inspired methods are consistently outperformed by state-of-art classical solver KaMIS running on a single CPU, and some AI-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic. Even with post-processing techniques like local search, AI-inspired methods still perform worse than CPU-based solvers. To better understand the source of these failures, we introduce a novel analysis, serialization, which reveals that non-backtracking AI-inspired methods, e.g. LTFT (which is based on GFlowNets), end up reasoning similarly to the simplest degree-based greedy, and thus worse than KaMIS. More generally, our findings suggest a need for a rethinking of current approaches in AI for CO, advocating for more rigorous benchmarking and the principled integration of classical heuristics. Additionally, we also find that CPU-based algorithm KaMIS have strong performance on sparse random graphs, which appears to show that the shattering threshold conjecture for large independent sets proposed by Coja-Oghlan & Efthymiou (2015) is either false or does not apply for real-life sizes (such as $10^6$ nodes).

Published in Transactions on Machine Learning Research (04/2026)
Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
Yikai Wu'
yikai, www.:um@@spppinntonncoom
Deportment of Computer Science & Princeton Longuage and Intelligence (PLJ) Princeton University
Haoyu Zhao'
haogu@@cs.prnnceeon.com edu
Department of Computer Science & Princeton Language and Intelligence (PLI)
Princeton University
Sanjeev Arora
wroro@cs.princelln edu
Department of Computer Science & Princeton Language and Intelligence (PLI)
Princeton University
Reviewed on OpenReview: /t opw.r/veee..eee...mm
forum? ksGoCT52M6
Abstract
AI methods, such as generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on Mazimum Independent Set (MIS). Strikingly, even on in-distribution random graphs, leading Al-inspired methods are consistently outperformed by state-of-art classical solver KaMIS running on a single CPU, and some Al-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic. Even with post-processing techniques like local search, Al-inspired methods still perform worse than CPU-based solvers. To better understand the source of these failures, we introduce a novel analysis, serialization, which reveals that non-backtracking Al-inspired methods, e.g. LTFT (which based on GFlowNett)). end up reasoning similarly to the simplest basede-bbsed greedy, and thus worse than KaMIS. More generally, our findings suggest need for rethinking of current approaches in Al for CO, advocating for more rigorous benchmarking and the principled integration of classical heuristies. Additionally, we also find that CPU-based algorithm KaMIS have strong performance sparse random graphs, which appears to show that the shattering threshold conjecture for large independent sets proposed by Coja-Oghlan & Efthymiou (2015) does not apply for real-life sizes (such as 106 nodes).
1 Introduction
Combinatorial optimization (CO) lies at the core of numorous scientific and engineering studies, encompassing applications in network design, resource allocation, healthcare, and supply chain (Du & Pardalos 1998 Hoffman 2000 Zhong Tang 2021). Combinatorial optimization usually involves selecting an optimal solution from discrete but often exponentially large set of candidates. Many are NP-hard (meaning that if P p NP then there is polynomial-tima algorithm for solving them in the general cases (Papadimitrion & Steiglitz 1998 This makes it challenging to design algorithms with provable guarantees, but in practice solvers can find reasonable quality solutions (c.g., Gurobi (Gurobi Optimization, LLC 2024
Recent advances in artificial intelligence (AI) and GPU computing have motivated use of Al-inspired approaches, e.g., Graph Neural Networs (GNNs) and reinforcement learning, to learn problem-specifi stratogics for Na-hard optimization problems such as MIS [Li ct al. 2018 Ahn et al. 2020 and TSP (Kool
"Equal contribution. Correspondence Yikai Wu yikai wudcs. wwwnceton.nneeeeee

---

Published in Transactions on Machine Learning Research (04/2026)
2018 Zhang et al. 2021 AI models can also be trained to predict search directions or refine heuristic rules [Li et al. 2018 d O Costa et al. 2020). These algorithms utilize advanced GPUs and often require
et al.
shorter inference compared to CPU-based algorithms. Additionally, Al-inspired methods avoid the need to design houristics for specific problems, allowing gencralization to new instances and problems (Bengio et al.
2021b
Cappart et al., 2023
Despite the claimed benefits of Al-inspired methods, a few years ago Angelini & Ricei-Tersenghi (2023)
showed that one specific GNN-based MIS algorithm (Schuetz et al. 2022 failed to surpass greedy algorithms.
While their work focused specifically evaluating that particular solver, it raised critical questions about the baseline performance of AI-based methods. Böther et al.] (2022) showed that AI-inspired approaches fail to provide superior search directions compared to traditional heuristics in tree search algorithms for MIS. Gamarnik (2023) suggests that GNN has theoretical limits which may become obstacles for GNN- MIS algorithms.
However, in recent years many new Al-inspired CO algorithms, utilizing a variely of techniques, such diffusion models (Sun & Yang, 2023 Sanokowski et al., 2024), GPU-accelerated sampling (Sun et al. 2023 and direct optimization (Alkhouri et al.
2025) have been developed and claimed to significant improve over the previous ones. Furthermore, GFlowNets Bengio et al. (2011a), which have been proposed as general-purpor purpose tools for tasks like scientific discovery and reinforcement learning Bengio et al. (2023), has also been used to solve CO problems (Zhang et al. 2023). Since combinatorial optimization an arena where humans have hand-designed algorithms for many decades, the following question is of great scientific interest:
Do Al-inspired algorilloms perform beller than classical heurislics for combinatorial optimization?
1.1 Our contributions
We explore the question in the context of Maximum Independent Set (MIS) problem: given a graph, aiming to find the largest subset of nodes with no edges present between any node pair. The simplicity of the problem attracted design of many heuristics to tackle the problem (Andrade et al. 2012 Lamm et al. 2015)
In recent works, MIS also a main target in efforts that design Al-inspired approaches such as non-conver
optimization (Schuetz al. 2022 Alkhouri et al. 2025 reinforcement learning (Ahn al., 2020:
Zhang
et al.
2023 and diffusion models (unn & Yang 2023 Sanokowski et al. 2024
For classical heuristics, we test degree-based greedy (Deg-Greedy, pick node with smallest degree at each step), and the state-of-the-ar MIS solver KaMIS (Lamm et al.) 2017 Dahlum et al. 2016). For Al-inspired algorithms, we test the newest algorithms from each "category" according to the techniques they use, including sampling algorithm isco (Sun et al. 2023), non-convex optimization algorithm PCQO (Alkhouri et al. 2025), reinnfrreement-leaniing related algorithms LwD (Ahn el al. 2020) and LTFT (Zhang el al. 2023) based on GFlowNets (Bengio al. (2211a) and diffusion models DIFUSCO (Sun & Yang 2023) and
DiffUCO (Sanokowski et al. 2024).
Testing on different graph types with different sizes and densities leads to the following empirical finding (Section 3
Finding 1: Current Al-inspired algorithms for MIS still don't outperform the best heuristic KaMIS, which runs on a single thrend in a CPU, while A AT-inspired methods often require signifieunt computational resources.
Finding 2: As the graph becomes larger or denser, KaMIS exhibits a notable superiority to Al-inspired algorithms.
Finding 3: The simplest degree-based greedy algorithm (Deg-Greedy) serves as very strong baseline. Some Al-inspired algorithms perform similarly to or worse than Deg-Greedy, especially for larger and denser graphs.
Section 4 presents ablation studies to understand why some Al-inspired methods fail to improve over the simplest
method. We introduce a new mode of analysis, serialization, that transforms the solution of any algorithm into a sequential list of choices leading the final independent set. We compare sequential order with the produced by Deg-Greedy (Sections 4.1 and 4.2 We find that the reinforcement.
2

---

Published in Transactions on Machine Learning Research (04/2026)
learning related algorithm LTFT, based on GFlowNets, behaves similarly to Deg-Greedy. We also found several qualitative characteristies that appear to distinguish algorithms that perform significantly better than Deg-Greedy from those that perform similarly or even worse than Deg-Greedy. We also explore whether Al- inspired method can improve their solution quality via a post-processing step using local search (Section 4.3 but find that they still fail to outperform KaMIS after some improvements. In Section 4.4] we discuss an additional result that may be of interest for MIS experts: on random graphs, KaMIS has level of performance
MIS showing that the shattering threshold conjecture for large independent sets proposed by Coja-Oghlan & Efthymiou 2015 does not apply for real-life sizes (such as 10t nodes).
Details on the code, external codebases, and data generation procedures are provided in Appendix D Our implementation is publicly available at httpps///ggbabb..o////aaa///////
2
Benchmarking Classical and Al-inspired Methods for Maximum Independent Set
We focus the experiment setup for benchmarking different algorithms for Maximum Independent Set problems (MIS).
2.1 Maximum Independent Set (MIS) problem
Given an undirected graph g(V,E) where V is the set of nodes and & is the set of edges, an independent set is a subset of vertices I S V such that no two nodes in I are adjacent, i.c., (u.z) & & for all u, E I. The goal in MIS is to find the largest possible independent set, I
2.2 MIS algorithms
We classify the algorithms we test as: (1) classical heuristics, which includes Deg-Greedy and KaMIS (OnlineMIS (Dahlum et al. 2016) and ReduMIS (Lamm et al. 2017)); (2) GPU-accelerated non-learning algorithms, which includes iSCD (Sun al.
2023) and PCQO (Alkhouri et al.) 2022 ; and (3) learning- based
algorithms, which includes LæD (Ahn al. 2020). LIFT (Zhang
2023). DIFUSCD (Sun & Yang 2023 We provide brief introductions of them below, please refer to
and DiffUCO (Sanokowski et al. 2024).
Appendices 3.4 to B.6 for details.
Deg-Greedy (Degree- based greedy) Simplest heuristic: always picks node with the smallest degree in the current graph, add to the current independent set, and delete that node and all of its neighbors from the graph. Most papers on Al-inspired methods do not compare with this baseline.
OnlineMIS and ReduMIS are two variants of the MIS solver KaMIS, mainly consists of three alternating steps: greody, local scarch, and graph roductions. OnlineMIS (Dahlum al. 2016) only applics simple reduction after local search, while ReduMIS Lamm et al. (2017) applies many graph reduction techniques.
isCO [Sun et al. 2023 is a GPU-acceleratedd sampling- based method, incorporating gradient- discrete MCMC and simulated annealing. The MCMC is designed based on the Metropolis-Haste algorithm, which if given enough time (exponential), can get the optimal solution.
PCQO (Alkhouri al. 2025 dircctly optimizes the quadratic loss function of the MIS using gradient descent. It sensitive to optimization hyperparameters, so hyperparameter search is required for achieving good results. Extensive hyperparameter search may give better results than in our experiments.
LwD (Ahn et al. 2020) is reinforcement learning based algorithm which models the problem as Markov Decision Process (MDP) and requires a dataset (without solutions) to train the policy. In each step, several nodes are added to the independent set and are never deleted. We call it a non-backkracking algorithm. Böther al. (2022) also benchmarked this algorithm. Ahn et al.] (2020) reported that outperforms KaMIS on very large but very sparse random graphs, which we do not include our benchmark, while Böther et al. 2022 found that their performance are similar on these graphs.
3

---

Published in Transactions on Machine Learning Research (04/2026)
LTFT Zhang et al. 2023 is also non-backtraeking MDP-based algorithm similar to LMD, but it only selects one node at time, which is decided by GelowNets (Bengio et al. 2021a). Thus, it has a very similar procedure to Deg-Greedy. The algorithm requires a dataset (without solutions) to train the neural network.
DIFUSCO (Sun & Yang 2023 is an end-to-end one-shot MIS solver using diffusion models and requires a supervised training dataset with solutions.
DiffUCO (Sanokowski et al. 2024) also uses diffussin model but with unsupervised learning and annealing techniques. It requires training dataset without solutions.
Non-backtracking vs one-shot Among algorithms that build up the set step by step, Deg- Beg-Greedy, LTFT and LwD are non-backirackinng meaning once a node added to the set it is never dropped from it. OnlineMIS and ReduMIS are backtracking algorithms, since as part local search they might decide that a previously picked should be dropped from the set allow further additions. AT-inspired methos PCQD, DIFUSCO, and DiffUCO are one-shot algorithms, since they work like end-to-end MIS solvers and directly return the full set.
2.3 Graph types
Erdös-Renyí (ER) graphs (Erdös & Rényi 1959 are random graphs where edges are connected uniformly at random (with a given probability or a fixed number of edges). We vary 2 parameters for ER graphs nd number of nodes n and average degree d, by fixing the number of edges at 2. Previous benchmark Böther
et al. 2022) and algorithms (Ahn et al.) 2020 Sun & Yang 2023 Zhang et al. 2023 Alkhouri et al. 2025
used it as test graphs for MIS, though without varying parameters as did.
Marabási-Albert (BA) graphs Allert & Barabási 2002 are random graphs generated by probabilistic growth process, mimicking real-world networks such as Internet, citation networks, and social networks (Albert)
& BBarabasi 2002 Radicchi et al. 2011). For BA graphs, we vary 2 parameters: number of nodes and parameter m (not number of edges). The average degree of BA graphs can be approximated as 2m.
2000); a. random constraint satisfaction problem (CSP) model. RB graphs are considered difficult instances for MIS due their structured randomness and high solution hardness. We use two dalasets from Zhang al. (2023) (also used in Sanokowski et al.
RB graphs RB graphs are derived from Model RB (Xu & Li
2024 RB-small (200-3 (200-300 nodes) and RB-large (800 (800-1200 nodes), to benchmark bearinng-assed solvers.
Real-world graphs We pick REDDIT-MULTI-SK and COLLAB (anaaddag & Vishwanathan 2015 from TUDataset website (Morris et al. 2020 since they have enough graphs for training and graph sizes not too small. REDDIT-MULTI-SK has 508.52 52 average nodes and 594.87 average edges. They are mostly very sparse graphs. COLLAB has 74.49 average nodes and 2457.78 average edges. They are mostly small but dense graphs.
2.4
More experiment details and computational resources
For synthetic graphs, we test 8 instances for each parameter (n, d) or (n, m); for real-world datasets, we test 100 graphs. Learning-basee methods are trained on 4000 graphs generated with the same parameter setting (for random graphs) or drawn from the same real-world dataset. Unless otherwise specified, default. hyperparameters are used (details in Appendix B
Our benchmark evaluates solution quality under fixed resource budgets. The computational limits for each method are summarized in Table [ including hardware, time budget, memory allocation, and the largest graph sizes successfully handled. CPU-based methods (Deg-Greed) OnlineMIS, ReduMIS) run on a single CPU thread with a 24-hour limit and up to 64GB RAM; in practice, ReduMIS often terminates much earlier on smaller graphs but can scale to n ze 10 GaU-based and learning based methods are evaluated using A100 GPUs with a 96-hour limit (including training), and their scalability constrained by GPU memory and training completion within this budget (see Appendices B.4 B.6 We use best-of-20 sampling for all learning-based based algorithms and for Deg- Gredd..
4

---

Published in Transactions on Machine Learning Research (04/2026)
Table Summary of computational resource limits used in the benchmark. We report the hardware configuration, time limits, memory allocations, and the largest graph size successfully trained or evaluated under the specified resource constraints. Memory refers to RAM for CPU-based methods and GPU memory for GPU-based methods. The values represent the resource limits allocated in benchmark setup, not the actual runtime peak memory consumption required by the algorithms. Among the evaluated methods, only DiffUCO supports multi-GPU training.
Methods
Hardware
Time Limit
Memory
Graph Successfully Trained or Evaluated
Deg-Greedy, OneineMIS,
1 CPU thread
24 hrs
64GB
> 106
ReduMIS
1SCD
1x A100
96 hrs
80GB
< 10000
(fails dense
graphs)
PCQD
1x A100
96 hrs
80GB
I 10000
LwD, LTFT, DIFUSCO
1x A100
96 hrs (train-
80GB
S 3000
ing)
DiffUCD
A 100 GPUs
96 hrs. (train-
320GB
S 1000
ing)
3 Performance Gap: Classical Methods Outperform Al-inspired Methods
In this section, we present our main experiment results. The performance of different algorithms on Erdös- Renyí (ER) graphs, Barabási-Albert (BA) graphs, RB graphs, and real-world graphs are shown in Tables 2 to respectively.
Al-inspired algorithms don't outperform ReduMIS. Our first main finding that, current Al-inspired algorithms do not outperform the best classical heuristics ReduMIS in terms of performance. As shown in Tables 2 5. ReduMIS consistently achieves superior results compared to all other methods, with the exception of iSCO sometimes perform similarly.
Although learning-based algorithms are claimed to be more efficient, they require significant training time and GPU memory, which is over our resource constraint for graphs with more than 3000 nodes, while ReduMIS can handle graphs with up to x 106 nodes (See Table 9 Although iSCO performs close to ReduMIS, it requires significant GPU memory and we are unable to get results for dense graphs with 10000 nodes. Its performance also bocome worse than ReduMIS for larger graphs.
We also note that LæD performs the best among learning-based algorithms, despite it being the oldest. learning- based algorithm we tested. In summary, experiment results show that current Al-inspired algorithms still don't outperform the best classical heuristics for the MIS problem.
The performance gap between ReduMIS and Al-based methods widens with larger and denser graphs. While ReduMIS consistently outperforms Al-based methods in most cases, the performance gap is small on small or sparse graphs. On ER graphs when 100, 300 and average degree d = 10, LwD has results within 1% gap from ReduMIS. However, as the graph becomes larger or denser, the performance gap between ReduMIS and Al-based algorithms eularges. On ER graphs, when n = 1000, there is a clear performance gap between AI-based algorithms and ReduMIS, with the only exception of the sampling based 1sco. When d 10, DiffUCO and LwD still reaches 98% of ReduMIS's performance. For denser graphs(d = 100), DiffUCO and LwD only reaches 96% of ReduMIS's performance. This gap widens further for n = 3000, where Al-based algorithms perform significantly worse than ReduMIS and sometimes fail to outperform simple heuristic Deg-Greedy. Classical solvers have difficulty handling graphs with million edges, but learning-based implementations struggle to scale up to that size.
Deg- nng-Greedy serves as strong baseline. Another key finding that the simplest degree-based greedy (Deg-Greedy) serves as remarkably strong baseline. As shown in Table 2 leveraging neural networks for
5

---

Published in Transactions on Machine Learning Research (04/2026)
Table 2: Performance different algorithms on Erdös Rényi (ER) graphs. We report the average independent size among 8 graphs generated by the graph parameters n, d. < denotes the algorithm fails to return solution within 96 hours, or the graph cannot be fitted into the GPU resources: a single 80GB A100 GPU for 1sC0, LTFT and DIFUSCO, and four 80GB A100 GPUs for DiffUcO. Best-of-20 sampling for Deg-Greedy and all bearinggbbssed algorithms. The numbers within +1% of the best in each row are highlighted. x denotes training terminated without reaching the target steps and test using the latest checkpoint. i denote testing with out-of-disrribttion trained models. Details in Appendix
CPU-based
GPU-acc
Learning- based
geg-Greedy
OnlineMIS
ReduMIS
iSCD
PCQO
LwD
LIFT
DIFUSCO
DiffUCD
10
29.25
30.50
30.50
30.62
30.63
30.38
28.62
30.25
30.02
30
13.63
14.00
14.75
14.50
14.50
14.38
13.12
13.88
13.92
10
77.50
93.88
94.38
94.75
94.63
94.25
88.62
93.50
91.84
44.50
47.88
47.88
47.62
47.63
46.88
43.25
43.88
45.04
100
16.13
18.00
18.38
18.00
18.00
17.00
16.25
16.62
16.93
10
303.25
314.75
316.13
315.62
310.00
311.25
297.00
303.88
311.67
30
151.00
158.88
163.75
163.50
158.63
158.38
150.00
143.75
152.55
1000
100
60.63
64.75
66.63
66.50
60.13
63.88
60.88
55.38
63.551
300
22.25
25.00
25.75
24.62
23.25
19.12
22.62
20.88
18.36f
10
9U7.13
947.25
954.25
950.88
923.25
934.12
888.25
902.00
935.28
451.88
480.88
493.13
491.62
464.25
473.25
449.00
413.38
459.571
3000
100
183.63
194.38
201.50
200.38
185.63
190.75*
184.00
171.38
194.071
73.50
77.63
80.75
78.88
69.22 25
73.88
1000
23.38
26.00
26.25
23.00
23.62
10
2909.88
3161.88
3173.62
3149.92
2569.75
30
1498.00
1607.50
1639.88
1625.47
1331.63
613.75
650.00
670.88
543.13
10000
300
249.00
258.38
272.25
218.63
1000
87.13
91.50
94.25
77.50
3000
29.63
33.00
33.25
26.63
node selection, LTFT often perform comparably to Deg-Greedy, particularly on larger or denser graphs. For example on ER graphs when n = 1000 or 3000, LTFT gives performance within 2% of Deg-Greedy (Table Additionally, DIFUSCO and PCQO fail to outperform beg-Greedy on larger or denser graphs, such as n = 1000 with d 2 100 and n 3000 for DIFUSCO,
3000 with 300and 10000 for PCQO.
Similar trends on other types of graphs We also tested on Barabási- (BA) graphs (Table 3), RB graphs (Table 4. and real-world graphs (Table 5). For BA graphs and RB graphs, ReduMIS also outperform all other methods across various setting. For real-world graphs, most methods including ReduMIS perform close to the best, likely because these dalasets are either small or sparse and thus easy for MIS problem. On BA and RB graphs, we also observe that the performance gap between ReduMIS and Al-inspired methods increase as the graphs become larger and denser.
Deg-Greedy is also strong baseline for all these graph lypes. Notably, for large RB graphs, learning-based methods perform worse than Deg-Greedy. Since RB graphs are considered difficult cases for MIS (Zhang et al. 2023), these results may suggest learning-basee methods even weaker for graph types with higher intrinsic hardness' than ER graphs.
Performance on Rorl-World Graphs On real-world graphs, we observe roughly equivalent performance across most methods, including the simplest degree-based greedy heuristic Deg-Gr -eg-Greedy. This suggests that available datasets suitable for training are algorithmically 'easy," making it difficult to differentiate between sophisticated solvers and simple heuristics. Consoquently, the primary disadvantage of AI-basod methods here is computational efficiency: while Deg-Greedy achieves optimal or near-optimal results on single CPU thread, AT methods require significant GPU resources and orders of magnitude longer time for training

---

Published in Transactions on Machine Learning Research (04/2026)
while Table 3: Performance of different algorithms on Barabási Albert (BA) graphs. Table
changing ER graphs to BA graphs with graph parameter n, m. We report the average independent set size among graphs generated by the graph parameters n, m. The numbers within =0.5% of the best in each row are highlighted. See caption of Table for other details and definitions of and f.
Heuristies
GPU-acc
Learning-based
m
Reg-Greedy
OneineMIS
ReduMIS
iSCO
PCQO
LTFT
DIFUSCO
DiffUCO
5
39.50
39.50
39.50
39.50
39.50
39.50
38.12
39.38
39.25
100
15
21.00
21.63
21.63
21.62
21.63
21.62
20.62
21.25
21.25
5
121.88
123.13
123.13
123.12
123.00
123.12
115.62
122.88
123.00
300
15
69.38
71.38
71.38
71.38
71.25
70.75
64.75
69.50
69.25
50
38.00
49.88
50.00
50.00
50.00
50.00
41.75
50.00
50.00
5
412.63
417.13
417.13
417.12
415.75
416.00
385.75
417.12
416.00
15
232.75
245.00
246.38
246.25
242.00
243.12 12
224.25
236.38
240.75
1000
50
107.50
115.75
116.88
116.75
113.50
113.00*
106.38
105,25
56.381
150
81.50
150.00
150.00
150.00
150.00
150.00*
82.25
135.001
5
1236.63
1257.00
1257.13
1255.62
1243.00 00
1248.12
1177.25
1254.38
1252.63f
15
709.50
749.63
754.50
752.00
722.25
727.75*
661.88
726.38
737.381
3000
50
335.38
362.63
369.75
368.25
357.13 13
336.88*
323.88
142.25
150
147.25
160.25
165.75
164.00
152.75
144.75
500
141.00
500.00
500.00
491.00
223.88
5
4128.75
4206.00
4205.35 38
4190.47
3640.75
15
2377.88
2525.00
2534.00
2517.07 0.7
1946.38
50
1122. 13
1228.88
1251.13
1241.98
938.38
10000
150
511.25
555.75
580.13
573.37
433.88
500
192.50
209.13
217.50
150.63
1500
67.25
1500.00
1500.00
Table 4: (Comparison of the performance of different algorithms on RB graphs) Table 2 on RB graphs (Xu & Li 2000) Datasets are from Zhang et al. 2023).
The numbers within +1% of the best are
highlighted.
Heuristics OnLineMIS
GPU-ace
Learning- based DIFUSCO
Dataset
of nodes
Deg-Greedy
ReduKIS
1SC0
PCQO
LuD
LTFT
DiffUCO
RB-small
200-300 800-1200
19.11
20.11
20.14
20.05
20.08
16.44
18.63
18.23
19.26
RB-large
39.16
42.66
42.95
41.53
39.62
32.55
38.32
36.22
38.91
Table 5: (Comparison of the performance of different algorithms real-world graphs) Table 2 real-world datasets. In general, graphs in REDDIT-MULTI-IK are very sparse, while COLLAB are dense but small. The nunbers within +1% of the best are highlighted.
Henristics OnlineNIS
GPU-acc
Learning-
Dataset
Beg-Greedy
ReduMIS
1SC0
PCQO
LwD
LTFT
DIFUSCO
D1 ffUCO
REDDIT-MULTI-SK COLLAB
350.73
350.73
350.66
350.73
344.47
350.73
343.35
350.72
350.69
8.68
8.70
8.70
8.70
8.57
8.69
8.70
8.75
8.70
and inference. Given the scarcity of harder real-world datasets that are suitable for training (sufficient. quantity/sinn we followed the community standard of using random graph (ER and BA) for our main evaluation.
4 Deconstructing the Performance Gap: Algorithmic Analysis
Our results show that the state-of-the-art Al-inspired algorithms for MIS still do not outperform the best heuristic ReduMIS. The surprising finding was that they also often do not purporform the simplest. classical

---

Published in Transactions on Machine Learning Research (04/2026)
Percentage
20.0
40.0
60.6
80.0
ER graphs
BA graphs
10
73.72
67.63
50.77
35.94
30
95 40
89.62
93.74
52.82
63.32
36.81
38 11.11
17.30
d
86.89
95.21
95.62
ER
87.56
68 87
14.81
300
150
1000
93.75
500
91.38
100
300
1000
3000
100
300
1000
3000
Figure 1: Percentage of rounds when LTFT selects the node with smallest possible degree, i.e., behaves similarly to degree-basee based greedy. On ER graphs when the graph is dense (closer to the bottom left corner), the percentage of rounds LTFT selects the node with smallest possible degree higher, i.e., behaves more similarly degree- based greedy. On BA graphs, the percentage choose the smallest possible node is generally lower, but denser BA graphs LTFT also behaves more like pegrec-bascee greedy.
heuristic, Deg-Greedy, especially large and dense graphs. In this section, we delve deeper into this comparison (Sections 4.1g and 4.2) Furthermore, we explore the impact of augmenting various algorithms with a local search as a post hoc step to enhance solution quality (Section 4.3
4.1 Comparison between Deg-Greedy and LIFT
Deg-Gre eog-Greedy sequentially picks nodes for the independent set. At cach step, it picks the node with the smallest. degree in the residual graph (where the nodes in the independent set and their neighbors are removed), It does not reverse any decisions (ie once picked, the node stays in the independent set.). As in Section 2.2 we call it non-backtracking algorithm. LIFT is also non-backtracking algorithm and it often perform similarly to beg-Greedy in Tables 2 and 3 It uses a trained policy network GFlowNets (Bengio et al. 2021a) to pick a node for the independent set at each step. Thus, we can naturally compare LTFT with Deg-Greedy by investigating how close this trained policy compares to the naive policy in Deg-Greedy.
The results are shown Figure D Overall, we observe that LTFT frequently selects nodes with very small degrees. On ER graphs where the average degree is least 30, LTFT picks the node with the smallest degree over 85% of rounds except for sparse graphs (d 10 and (n, d) (3000, 30)). On BA graphs, while the percentage is lower, it still exceeds 75% on large and sufficiently dense graphs. Moreover, in cases where LTFT selects the smallest degree nodes less frequently, its performance is worse than Dog-Greedy.
To conclude, our results suggest that despite using neural net to learn the policy, LTFT is closely aligned with Deg-Greedy: prioritizing nodes with small degrees at each step. The high consistency between the node selection strategies of LTFT and Deg-Greedy can explain their similar performance.
4.2 Serialization: allows comparing to Deg-Greedy
In the previous part, we demonstrate that LTFT employs a heuristic similar to Deg heg-Greedy, selecting the node with the smallest degree in the remaining graph in each round. However, other algorithms, such as ReduMIS, PCQO, and DIFUSCO, which does not select one node at a step without backtracking, cannot be analyzed based on the sequence of nodes picked. Thus, we introduce a method called degree-based solution serialization to analyze their behavior and compare them with Deg-Greedy.
Given a graph G(V,E) and an independent set solution I (which is an independent set), process proceeds follows: (1) Repeatedly remove the node in Z with the smallest degree. (2) A After removing node from I,
8

---

Published in Transactions on Machine Learning Research (04/2026)
ER (n=1000,. d=30)
(n=1000, m=15)
100
3798-99 90
97
85
78
1st
96.85
70
74
83
90
90
1/3
Percertage
1/3
Parcentage
60
56
63
2rd 1/3
67
45
40
20
Deg Gready
Ontimellds
fadiutts
8C0
PC30
LWO
UTT
DIPUSCO
Dog Grendy
Ontimeltt
acD
LaD
OTT
airucoo
Figure 2: The percentage to choose the smallest possible degree node on different part of the (degree-based) serialization. We find that the best algs (0nl ineMIS, ReduMIS, isCO) and the best performing learning-basee based algorithm LwD share similar characteristic pattern, that they have high consistency with degrce-basod groedy on second and third part of the scrialization, while on the first part there low consistency. On the other hand, PCQO and DIFUSCO has low consistency with degree-based greedy in general.
also remove it and its neighbors in G. (3) Continue this process until all nodes I are removed. The order in which nodes are removed forms the serialization of the solution. This procedure is detailed in Algorithm [
To evaluate the algorithms, we compute the percentage of rounds in which the smallest degree node is sclected during serialization, similar to our comparison between LTFT and Deg-Greedy. Due to random lie-breaking in Algorithm ! we repeat the process 100 times and select the serialization with the highest number of rounds selecting the smallest degree node. Although Deg-Greedy theoretically achieves 100% smallest-degree selections in its best serialization, random tie- breaking prevents us from perfectly recovering this with 100 repetitions. Instead of reporting the overall percentage, we divide the serialization into three equal parts and report the percentages for each part.
The results, shown in Figure compare the percentage of smallest-degree node selections across different algorithms. Due to space constraints, we present results only for ER and BA graphs under selected parameters; additional results are available in Appendix C.2
Algorithms that often perform the best, namely OnlineMIS, ReduMIS, and iSCO, exhibit a consistent pattern after scrialization. In the first one-third of the serialization, these algorithms deviate significantly from selecting the dmeglest-degree nodes. However, in the middle and final thirds, the percentage of smallest-degree node selections increases substantially. This suggests that while degree-based greedy heuristies may appear shortsighted initially, they are highly effective in the later stages of solution construction. Interestingly, LwD, which performs the best among learning- baseengg-bssed based methods tested in our sctting, also shares this pattern.
As for PCQO and DIFUSCO, they show consistently low percentages of smallest-degree node selections throughout. the serialization, particularly on ER graphs.
Through serialization, we observe distinct differences in node selection patterns among algorithms. Our findings suggest that Al-based methods might fail to utilize (PCQO and DIFUSCO) or emphasize too much (LTFT) simple yet highly effective hcuristics, such greedily selecting the smallest-degree node, which may partly explain their performance limitations.
In Appendix C.3 we perform a pseudo-natural serialization for LwD. LwD is also a non-backtracking algorithm like LTFT, but it does not have a "natural scrialization' like LTFT (Section 4.1) because it chooses several nodes in step. The pseudo-natural serializalion performs serialization in each step of LwD. The results Figure 0 align with our "counterfactual" serialization results here.
4.3 Incorporating local search to improve solution
In the previous sections, we show that solutions generated by Al-based algorithms generally differ from those produced by degree-based greedy methods, which may explain their inferior performance on MIS
9

---

Published in Transactions on Machine Learning Research (04/2026)
problems. A natural idea is to enhance these solutions with simple heuristics, such local search. Local search post-processing has also been used for AT-algorithms in previous works (Ahn et al. 2020 Böther et al. 2022
We applied the 2-improvement local search (Andrade et al. 2012) (details in B.7 which is used in KaMIS, as post-processing step to all algorithms (except OnlineMIS and ReduMIS since they already has local search), and the resulting performance improvements are presented in Table G
Table 6: Incorporating local search as post-processing procedure on selected ER graphs. We add 2-improvement local search for the algorithm tested. We report the performance after the local search and the improvement from local search in (). Full results for ER and BA graphs in Table 10
Heuristics
GPU-acc
Learning-basct LTFT
(n, d)
Deg-Greedy
OnlineMIS
ReduMIS
19C0
POQO
LvD
DIFUSCO
1000,30
152.75 (1.75)
158.88
163.75
163.50 (0)
159.13 (0.5)
158.62 (0.24)
151.38 (1.38)
150.62 (6.87)
1000,100
60.75 (0.13)
64.75
66.63
66,50 (0)
60.88 (0.75)
64.12 (0.24)
61.88 (1.00)
57.88 (2.50)
3000,30
456. 12 (4.24)
480.88
493.13
491.62 (0)
469.75 (5.5)
474.00 (0.75)
454.38 (5.38)
442.75 (29.37)
As shown in Table G algorithms like PCQO and DIFUSCO benefit significantly more from the local search post-processing compared to others, such as Deg-Greedy and LwD. This observation aligns with our earlier findings: Tf the solution after serialization exhibits a high percentage of smallest-degree node selections in the later stages, there is relatively little room for improvement through local scarch. Conversely, the solution after serialization shows a low percentage of smallest-degree node selections, there is greater potential for improvement via local search.
In addition, although all algorithms except iSCO have improvements after local search, they still perform worse than ReduMIS in most cases.
In summary, our analysis highlights a promising direction for designing machine learning- based combinatorial optimization algorithms. Rather than relying solely on end-to-end methods like PCQO or DIFUSCO, incorporating classical heuristics, such as greedily selecting the smallest-degree node, into the overall algorithm may yield better results. One potential approach could involve using machine learning algorithms to identify small subset of nodes, followed by a degree-based greedy method to complete the solution.
4.4 Perspective for theoreticians: Empirical performance vs asymptotic conjecture
For theoretical analysis for MIS on ER graphs and regular graphs, see Coja- Oghlan & Efthymiou (2015) Wormald et al. (1999): Barbier et al. (2013); Gamarnik & Sudan (2014). In ER graphs with n nodes and average degree d, the MIS has size 2n for asymptotically large n and d, and simplest random greody achieves half-optimal at alnd (Grimmett & McDiarmid 1975). Yet, there is no known polynomial time d algorithm which can achieve MIS size (1+c)=ine for any constant and it is conjectured that polynomial-time algorithms cannot do better than (1 + o(1)) ind (Coja-Oghlan & Efthymiou 2015). Thus it natural measure the goodness of an algorithm by the ratio of the MIS size obtained to nind comparison across different n and d's.
d This ratio can faciliate
Surprisingly for Figure 3 plots this ratio for several algorithms. (Plots for all algorithms in Appendix C.5 ReduMIS and OnlineMIS this ratio is consistently larger than 1.2 and often larger than 1.3 even for fairly large n, d. One possible reasoning for our finding is that the graphs we able to evaluate empirically are very far from the asymptotic regime where the conjecture might be applicable (i.c., if it is truc). We note that the proofs for Theorem 2 in the original paper had to assume d > exp(20) and thus n > exp(40), much larger than any practical sizes of graphs. Our findings suggest that indeed the conjecture itself may not hold for graphs one may encounter in real life. Of course this does not disprove the conjecture per se since it concerns asymptotically large n and d, but our results could encourage further analysis and potential collaboration between researchers theoretical and empirical aspects of MIS on random graphs.
10

---

Published in Transactions on Machine Learning Research (04/2026)
ReduMIS
OnlineMIS
Deg-Greeth
10
10
1.4
30
30
30
Ratio Values
100
100
100
1.3
300
300
300
1.2
1e3
1e3
1e3
3e3
3e3
3e3
1.1
100
300
les
Figure 3: Heatmap for ratios of MTS size to aind on ER graphs. We find that the ratio for ReduMIS and KaMIS consistently larger than 1.2, suggesting that ReduMIS and KaMIS might surpass the conjectured upper bound (Coja-Oghlan Efthymiou 2015
d
5 Related Works
Classical and heuristic methods for MIS
Classical methods for MIS range from simple greedy algorithms
to advanced solvers like KaMIS which involves a number heuristics. There are various existing heuristics
for MIS, such reduction techniques (Butenko al. 2002 Xiao & Nagamochi 2013 Akiba & Iwata
2016), local search (Andrade al. 2012), and evolutionary algorithms (Back & Khuri 1994 Borisovsky
& Zavolovskaya 2003 Lamm et al. 2015). KaMIS (Lamm et al. 2017 Dahlum et al. 2016)
developed
based on these heuristics. In addition, MIS can be formulated into binary integer programming problem
Nemhauser & Trotter Jr. 1975), which can be solved by the state-of-art integer programming solver Gurobi
Gurobi Optimization, LLC (2044)
Machine learning for combinatorial optimization In recent years, various MI.based algorithms have been developed for the MIS problem and most of them are based on graph neural networks (GNNs). Some of them using supervised learning (Li et al.) 2018 Sun & Yangl 2023 Li et al. 2024) and requires labelling
training data using classical solvers. Alternatively, those based on reinforcement learning (Khalil al.) 2017
Ahn al. 2020
Qiu et al.
2022 Sanokowski al. 2023) and other unsupervised learning objectives (Karalias
& Loukas 2020
Sun et al.)
2022: Zhang et. al.) 2023 Sanokowski et al. 2024h do not require labeled training
data. Zhang et al. (0023
LTFT
uses GFlowNets [Bengio et al. 2021a) which is related to reinforcement
learning. Notably, Ahn et al. (2020): : Sanokowski et al. [2023 Zhang et al. (2023) model MIS problem as a
Markov Decision Process (MDP) and generate the solution step-by by-step (autoregressively) While Sanokowski
et al. 2023) fixes the order node updates, Ahh et al. (2020) (L=D) and Zhang et al. (2023) (LTFT) choose
which node to update at each step so that they have a "natural" or "pseudo-natural" serialization and most
suitable for our analysis in Scction 4.1 and Appendix C.3 In addition, Sun Yang (0023) (DIFUSCO) and
Sanokowski al. (2024) (DiffUCO) both utilizes diffusion model.
Most of the algorithms above also work on other types of graph CO problems, such Maximum Cut, Maximum Vetex Cover, and Minimum Dominating Set. Some (Khalil et al. 2017 Qîu et al. 2022 Sun &
Yang 2023 also work for the Travelling Salesman Problem (TSP).
Other GPU-based solvers for CO Recently, some non-learning GPU-based solvers for CO problems have been developed. Sun et al. (2023) developed a GPU-accelerated sampling based method which works on MIS, Max Cut, and TSP. [Schuctz et al. [2022); Ichikawa (002)) uses GNNs conduct non-convex optimization
for MIS without machine learning. Alkhouri eL al. 2025
uses direct. quadratic optimization without GNNs.
Benchmarks for MIS Böther et al. (022 provides a benchmark for several MIS algorithms including Gurobi (Gurobi Optimization, LLC 2024], KaMIS (ReduMIS) (Lamm et al. 2017). Intel- Thee-Treeeearh (Li et al.) 2018), DGL--Tresccare recent Al-inspired method, though only focuses its comparsion for learning based tree search algorithms. It suggests that LuD is better than learning-hased tree search algorithms. This aligns with results where LuD
and LwD Ahn et al. (2020). It is the only MIS benchmark we know about including
11

---

Published in Transactions on Machine Learning Research (04/2026)
performs the best among saarinng-based algorithms. This benchmark covers various types of random graphs and several real-world datasets, so it. is a good reference benchmark for comparison over different types of graphs. Though unlike our benchmark, it does not provide comparison across various size and density for random graphs. Our benchmark fills this gap and provides a more detailed comparison. We also include many newer AT-inspired algorithms, and greedy algorithms which leads to detailed analysis like serialization.
Angelini & Ricci-Tersenghi (2023) showed that one specific GNN-based MIS algorithm (Schuetz et al. 2022 failed to surpass Deg- Greddy on regular graphs. Although their title ("Modern graph neural networks do worse...) appears to suggest broad conclusion about GNN-based methods, their empirical evaluation limited to that specific algorithm. The algorithm papers also report experiments comparing with previous algorithrss but those comparisons usually only focus on a few datasets and a few selected baselines.
6 Conclusion and Takeaways
Given the great interest in designing "general purpose AI reasoners", it interesting to check how well recent Al-based methods have fared in combinatorial optimization, a field with a long history of ingenious hand-designed algorithms. Our careful empirical comparisons on the MIS problem showed that none of the new AL-inspired methods outperform ReduMIS, the best CPU-based MIS solver. Strikingly, this underperformance holds even on in-distribution random graphs, a setting arguably ideal for machine learning-based approaches. As the graphs get. larger or denser, the superiority of ReduMIS becomes more evident, whereas several Al-inspired algorithms degrade to performing no better than the simple degree- based greedy heuristic -eeg-rredyy)
A key contribution of this work is the introduction of serialization, novel analysis technique to deconstruct and compare the decision-making processes of different algorithms. This analysis revealed that some Al- inspired methods, such as the GFlowNet-basee LTFT, end up reasoning very similarly to the simple Greedry heuristic, which helps explain their performance limitations. More importantly, serialization uncovered a distinct pattern shared by high-performing algorithms like OnlineMIS, ReduMIS, isCo, and LwD: they deviate from simple greedy choices in the initial stages but align with them in the later stages of constructing a solution. This suggests serialization is a powerful tool for discovering the intrinsic characteristies of high-quality solutions, which can provide overlooked insights for the principled design of future algorithms.
Serialization-baseed analysis also shows the importance of algorithmic strategies in understanding this performance gap. One-shot methods like DIFUSCO and PCQO handicap themselves by foregoing the benefits of local search, whereas non- non-backtracking methods like Deg- Geg-Greedy and LTFT handicap themselves by never delcting vertices from the independent set being built. In contrast, KaMIS performs a full local search, allowing algorithm, L=D,
it to iteratively add and delete vertices. Interestingly, the best-performing learning-basee operates in a middle ground by selecting several nodes at time, which may allow a closer approximation to local scarch. And while post-processing with local scarch improves the solutions of most AT-inspired methods, they still fail to match the performance of ReduMIS.
While prior work has questioned whether Al-inspired methods consistently outperform strong classical baselines, our evaluation of more recent approaches suggests that these challenges persist at practically relevant scales. Similar patterns have been observed in the Traveling Salesperson Problem (TSP), where neural methods often struggle to surpass specialized classical solvers under careful benchmarking (Joshi et al. 2022: Xia et al. 2024).. Notably, both MIS and TSP are among the most extensively studied problems in Al-based combinatorial optimization, yet in both cases claimed advantages of Al-based methods weaken under more extensive and carefully designed evaluation. This suggests that rigorous and comprehensive benchmarking is essential across combinatorial optimization problems when assessing Al-based approaches.
Moreover, while our study focuses on MIS, the lesson of principled integration of classical heuristics may crcionsspprticclarrpp closely related graph problems such as Maximum Clique, Vertex
extend to other Cover, and Graph Coloring, which share similar structural and scalability challenges.
We thus propose that. future work should prioritize the following directions:
12

---

Published in Transactions on Machine Learning Research (04/2026)
Rigorous and Comprehensive Benchmarking: Future work must establish more realistic benchmarks that evaluate algorithms on a wider range of instance sizes and densities. They are necessary for meaningful comparisons and provide important guidance for future developments. The ovaluations should also report crucial computational costs, such as GPU memory usage, to ensure lair comparisons against efficient CPU-based solvers that are often more scalable in practice.
Deeper Understanding of Learning Limitations: A concerted effort is needed to understand theoretical barriers like Gamarnik (2023) for GNN- methods. Meanwhile, expanding on empirical tools like serialization to pinpoint specific failure modes is also important for guiding the development of new algorithms.
Principled Integration of Classical Heuristics: Researchers should move beyond treating classical solvers as black-box basclines and instcad analyze, learn from, and integrate their most effective components. promising direction to design hybrid models that use AI to guide classical heuristics for instance, by using learned model to identífy a subset of nodes and select suitable heuristics (such reduction, local search, or degree-based greedy) to apply. Previous work by Garmendia et al. (2023) demonstrates the potential of such neural improvement heuristics, and we advocate for further exploration in this direction.
Acknowledgments
YW, HZ, and SA acknowledge funding from DARPA. The authors would like to thank Alvaro Velasquez, Ismail Alkhouri, Kaifeng Lyu, Sadhika Malladi, and Pravesh Kothari for helpful discussions.
References
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent sets. In International conference on machine learning, pp. 134-144. PMLR, 2020.
Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/fp algorithms in practice: A case study of vertex cover. Theoretical Computer Science, 609:211 225, 2016.
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, and Alvaro Velasquez. Differentiable quadratic optimization for the maximum independent set problem. In International Conference on Machine Learning, pp. 1102 1127. PMLR, 2025.
Ismail R Alkhouri, George K Atia, and Alvaro Velasquez. A differentiable approach combinatorial optimization using dataless neural networks. arXiv preprint ar arXiv:2203.0822) 2022.
Saced Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference on Learning Represenlations, 2019.
Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18:525-541 547, 2012.
Maria Chiara Angelini and Federico Ricci- Terriniersenhh. Modern graph neural networks do worse than classical greedy algorithms solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29 31, 2023.
Thomas Back and Sami Khuri. An evolutionary heuristic for the maximum independent set problem. In Proceedings of the first IEEE conference on evolutionary computation. IEEE World Congress on Computational Intelligence, pp. 531 535. IEEE, 1994.
Schirin Bacr, Jupiter Bakakeu, Richard Meyes, and Tobias Meisen. Multi-agent reinforeement learning for job shop scheduling flexible manufacturing systems. In 2019 Second International Conference on Artificial Intelligence for Industries (AT4T), pp. 22-25. IEFE, 2019.
13

---

Published in Transactions on Machine Learning Research (04/2026)
Nikhil Bansal. Approximating independent sets in sparse graphs. In Proceedings of the twenty-sizth annual ACM-STAM symposium on Discrele algorithms,, pp. 1-8. SIAM, 2014.
Jean Barbier, Florent Krzakala, Lenka Zdeborová, and Pan Zhang. The hard-core model on random graphs revisited. In Journal of Physics: Conference Series, volume 473, pp. 012021. IOP Publishing, 2013.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advonces in Neural Information Processing Systems, 34:27381-27300 2021a.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021b.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet. foundations. The Journal of Machine Learning Research, 24(1):10006-10000 2023.
Béla Bollobés and Béla Bollobás. Random graphs. Springer, 1998.
Ravi Boppana and Magnús M Halldórsson. Approximating maximum independent sets by excluding subgraphs.
BIT Numerical Mathematics, 32(2):180-196, 1992.
Pavel A Borisovsky and Marina S Zavolovskaya. Experimental comparison of two evolutionary algorithms for the independent set problem. In Workshops on Applications of Evolutionary Computation, pp. 154-164. Springer, 2003.
Nicolas Bourgeois, Bruno Escoffier, Vangelis T Paschos, and Johan MM van Rooij. Fast algorithms for max independent set. Algorithaiica, 62:382 415, 2012.
Sergiy Butenko, Panos Pardalos, Ivan Sergienko, Vladimir Shylo, and Petro Stetsyuk. Finding maximum independent sets in graphs arising from coding theory. In Proceedings of the 2002 ACM symposium Applied computing, pp. 542 546, 2002.
Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Scidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2022.
Quentin Cappart,, Didier Chételat, Elias 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 61, 2023.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial oplimization. Advances in neural information processing systems, 32, 2019.
Amin Coja-Oghlan and Charilaos Efthymiou. On independent sets in random graphs. Random Structures & Algorithms,, 4733):436-4900 2015.
Paulo R d Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian conference on mochine learning, pp. 465-480. PMLR, 2020.
Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Accelerating local search for the maximum independent set problem. In Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petershurg, Russia, June 5-8, 2016, Proceedings 15, pp. 118-133. Springer, 2016.
Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combinatorial actions: An application vehicle routing. Advonces Neural Information Processing Systems, 33:609-620, 2020.
14

---

Published in Transactions on Machine Learning Research (04/2026)
Jian Ding, Allan Sly, and Nike Sun. Maximum independent sets random regular graphs. Acto Methematica, 217(():263-34)) -400, 2016.
Dingzhu Du and Panos M Pardalos. Handbook of combinatorial optimization, volume 4. Springer Science & Business Media, 1998.
P. Erdös and A. Rényi. On random graphs i. Publicationes Mathematicae Debrecen, 6:290, 1959.
David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 1111411),,, 2021.
David Gamarnik. Barriers for the performance of graph neural networks (gnn) in discrete random structures. Proceedings of the National Academy of Sciences, 120(46):e314409222) 2023.
David Gamarník and Madhu Sudan. Limits of local algorithms over sparse random graphs. In Proceedings of the 5th conference on Innovations in theoretical computer science, pp. 369 376, 2014.
Andoni I Garmendia, Josu Ceberio, and Alexander Mendiburu. Neural improvement heuristics for graph combinatorial optimization problems. IEEE Transactions on Newral Networks and Learning Systems, 2023.
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.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Grathwohl, Dale Schuurmans, and Hanjun Dai. Dises: a benchmark for discrete sampling. Advances in Neural Information Processing Systems, 36, 2024.
Geoffrey R. Grimmett and Colin JH McDiarmid. On colouring random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 77, pp. 313-324. Cambridge University Press, 1975.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www.uurott com
Fran Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. S1AM Journal on Computing, 31(5):1608 1623, 2002.
Karla L Hoffman. Combinatorial optimization: Current successes and directions for the future. Journal of computational and applied mathematics, 124(1-2):341 360, 2000.
Yuma Ichikawa. Controlling contimuous relaxation for combinatorial optimization. arXiv:2209.1699 2023.
arXiv preprint
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousscau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constrainls, 27(1):70 98, 2022.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for com- binatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659 6672, 2020.
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.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08/ 008.00803.877, 2018.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-laarning with graph networks learn generalizable branching heuristic for sat solver? Advances in Neural Information Processing Systems, 03:9608-9621, 2020.
Sebastian Lamm, Peter Sanders, and Christian Schulz. Graph partitioning for independent sets. In
International Symposium Experimental Algorithmss, pp. 68 81. Springer, 2015.
15

---

Published in Transactions on Machine Learning Research (04/2026)
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato Werneck. Finding near-optimal independent sets at scale. Journal of Heuristics, 23(4), 2017.
Gilbert Laporte. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2):231 2477 1992.
Ted G Lewis. Network science: Theory and applications. John Wiley & Sons, 2011.
Kaiwen Li, Tao Zhang, Rui Wang, Yuheng Wang, Yi Han, and Ling Wang. Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE transactions on cybernetics, 52(12): 13142-13111 2021.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong srructur-hhrdneess-ee
bascline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4414-4425, 2023.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neurol Information Processing Systems, 36, 2024.
Zhaoyu Li and Xujic Si. Nsnet: A general neural probabilistic framework for satisfiability problems. Advances in Neural Information Processing Systems, 35:25573 25585, 2022.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advonces in newral information processing systems, 31, 2018.
Chun-Cheng Lin, Der-Jiunn Deng, Yen-Ling Chih, and Hsin-Ting Chiu. Smart manufacturing scheduling with edge computing using multiclass deep q network. IEEE Transactions on Industrial Informatics, 15(7): 4276-4284, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. Tn JCML 2020 Workshop Gruph Representation Learning and Beyond (GRL+ 2020), 2020. URL www.graphheeaningg.. io
George Nemhauser and Leslie E Trotter Jr. Vertex packings: structural properties and algorithms. Mathematical Programming, 8(1):232-25 228882222282222 1975.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531-25548 2022.
Filippo Radicchi, Santo Fortunato, and Alessandro Vespignani. Citation networks. Models of science dynamics: Encounters between complexity theory and information sciences, pp. 257, 2011.
Mustazee Rahman and Bálint Virág. Local algorithms for independent sets are half-optimal. Annals of Probabilily, 45(3), 2017.
Pedro Sanchez, Xiao Liu, Alison Q O'Neil, and Sotirios Tsaftaris. Diffusion models for causal discovery via topological ordering. arXio preprint arXiv:2210.0 22000220000 2022.
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Variational annealing on graphs for combinatorial optimization. Advances in Neural Information Processing Systems, 36:63907 63930, 2023.
Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervisod neural combinatorial optimization. In Corly-first International Conference Machine Learning, 2024.
16

---

Published in Transactions on Machine Learning Research (04/2026)
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physies- inspired graph neural networks. Nature Machine Intelligence, (6))3777777 2022.
Haoran Sun, Etash Kumar Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022.
Haoran Sun, Katayoon Goshvadi, Azade Nova, Dalc Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning, pp. 32859 32874. PMLR, 2023.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial oplimization. Advances in Neural Information Processing Systems, 36:3706-33 37311, 2023.
Nicholas C Wormald. Analysis of greedy algorithms on graphs with bounded degrees. Discrete Mathematics, 273(1-3):235 230,, 2003.
Nicholas Wormald et al. The differential equation method for random graph processes and greedy algorithms. Lectures on approzimation and randomized algorithms, (3(155):0943 05073, 1999.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rothinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems. In International Conference on Machine Learning, pp. 54178-54190. PMLR, 2024.
Mingyu Xiao and Hiroshi Nagamochi. Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theoreticol Computer Science, 469:92 100992-104, 2013.
Ke Xu and Wei Li. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12:93-103, 2000.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2013.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: neural-enhanced ant systems for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: Learning to generale sat formulas. Advances in neural information processing syslems, 32, 2019.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in neural information processing systems, 33: 1621-1632, 2020.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36:11952 11969, 2023.
Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. IEFF Transactions Neural Networks and Learning Systems, 34(4): 2119 2132, 2021.
Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Combining reinforcement learning with lin-kernighan-helseee helsgau algorithm for the traveling salesman problem. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 12445-12452, 2021.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018.
Liwei Zhong and Guochun Tang. Preface: Combinatorial optimization drives the future of health care.
Journal of Combinatorial Optimization, 42:675-677 676, 2021.
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In International Conference on Learning Representations, 2020.
17

---

Published in Transactions on Machine Learning Research (04/2026)
Appendices
More Related Works
18
B
Detailed Experiment Setup
19
B.1
Algorithm Pseudo-code for segree-based scrialization
19
B.2
Datascts
19
B.3
Hardware configurations
21
B.
Classical (Ps--baee algorithms
21
B.5
GPU-acoelerated non-learning algorithms
22
B.6
Learning- based algorithms
22
Local search
C
More Experiment Results
24
Larger graphs
25
C.2 Serialization
25
C.3 Comparison between Greddy and LwD
28
Local search
28
More results on the ratio
31
D Code and Data Release
31
D.1
Data generation
32
D.2
Greedy algorithms
32
03 Analysis codes
32
D.4
External solver codebases
33
A
More Related Works
More on theoretical results for MIS For random ER graphs with number of nodes and average degree d, the upper bound of MIS size is 2nlad for asymptotically large n and d. (Coja-Oghlan & Efthymiou, 2015). Grimmett & McDiarmid 1975) proves that the simplest Ran-Greedy can achieve half-optimal at annd on random ER graphs Despite that, there is no known existing polynomial algorithm which can reach MIS a for any constant e for asymptotically large n and d. @Coja-Oghlan Efthymiou, 2015 Oghlan & Efthymiou (2015) also suggests that the reason likely independent sets of size larger than
size (1+ e) d
(1+ and forms an intricately ragged landscape, where local algorithms will stuck. Gamarnik & Sudan (2014): Rahman & Virág (2017) proves that for local algorithms (which is defined to only use information from constant neighborhood of node to decide whether the node is in the independent set) are at most half optimal for independent set on random d-regular graphs. Gamarnik & Sudan (2014) suggests this is due to & property of the MIS problem, which they denote as the Overlap Gap Property (OGP) (Gamarnik: 2021). Gamarnik (2023) suggests that graph neural networks (GNNs) are also a type of local algorithms and thus being limited by OGP. While most AT-inspired MIS algorithms use GNN, the proof only applics algorithms use GNNs as the only component find solutions like (Schuetz al. 22022). so may not apply directly to more complicated algorithms like those tested in paper. Yet, it may still suggests reason
18

---

Published in Transactions on Machine Learning Research (04/2026)
why GNN-based algorithms (including most Al-inspired algorithms) cannot outperform classical heuristics like KaMIS.
In addition, Barbier et al. (2013) provides conjectured tighter upper bound than Inlnd for d-regular graphs d' using the hard-core model in physics. Ding et al. (2016) proves a similar tighter upper bound for d-regular graphs. Wormald (2003) gives average-case performance for Deg-Greedy on d-regular graphs.
More on classical heuristics Over the past few decades, significant progress has been made in tackling NP-hard combinatorial optimization (CO) problems by developing approximation algorithms and heuristic methods. Approximation algorithms provide provable guarantees on solution quality and have led to groundbreaking results for classical problems, such as the Maximum Independent Set (MIS), Traveling Salesperson Problem (TSP), and Maximum Cut (Boppana & Halldórsson 1992 Laporte 1992 Goemans & Williamson 1995).
As we mentioned Section 5 there are various existing heuristics for MIS. For exmaple, reduction techniques reduce the graph into smaller instances. [Akiba & Iwata (2016) and Xiao & Nagamochi (2013) have shown variety of reduction techniques which work well for MIS problem. Butenko al. (2002) ; Bourgeois et al.
(2012) uses reduction techniques to develop efficient exact algorithms for MIS. Local search improves existing independent set by removing small number of nodes and insert other eligible nodes. Andrade et al. (2012) gives an efficient local search algorithm for MIS and has been used as a subprocess for several MIS solvers. Evolutionary algorithms combine several existing solutions into a new solution. Examples include
Back & Khuri (1994); [Borisossyy & Zavolovskaya (2003): Lamm et al. (2015). KaMIS (Lamm et al. 2017
Dahlum al.) 2016: was developed based on many of these techniques above.
In addition, the MIS problem can also be relaxed into semi-definite programming (SDP), which leads to several approximation algorithms (Halperin
2002 Bansal 2014
More on AI methods for combinatorial optimization In addition to Section we note that Sun
et al.
(022); Sanokowski et al. (2023) 2024) use annealing techniques. [unn & Yang (2023 was developed
based on Qiu et al. (2022), and Sanokowski et al. (2024) was based on Sanokowski et al. (202)). Sanokowski
ct al.
2024) can also be considered as an extension of Karalias & Loukas 2020))
Besides MIS, Maximum Cut, and TSP, people also considered to use AI-Inspired methods for other com- binatorial optimization problems, including Vehicle Routing Problems (including TSP) (Kool et al. 2018
Chen & Tian
2019 Delarue et al.
2020:
Li et al. 2021 Zheng et al. 2021 Ye et al. 2024 Job Scheduling
Problems LLn et al. 2019
Baer et al.
2019
Zhang et al. 2020 Ye et al. 2024] Boolean Satisfiability
(SAT) Amizadeh et al.
2019
You et al.
2019
Kurin et al. 2020
& Si 2022
Li et al. 2023 and Casual
Discovery (Zheng et. al.
2018
Zhu et al.
2020
Sanchez et al. 2022
B Detailed Experiment Setup
B.1
Algorithm coudo-code for Begree-based serialization
Please refer to Algorithm I for the pseudo-code for degree-based serialization, mentioned in Section 4.2
B.2 Datasets
For synthetic graphs, we test 8 graphs for each parameter (n, d) (n,m), We test on 100 graphs for real-world datasets. For learning- based algorithms,, use 4000 training graphs generated using the same parameter (in case of random graphs) or drawn 4000 graphs from the same real-world dataset.
Erdös-Renyí (ER) graph ER graphs (Erdös & Rényi 1959 are random graphs where edges are connected uniformly at random (with a fixed probability or number of edges). We vary parameters for ER graphs, number of nodes n and average degree d, by fixing number of edges at ad ER graphs are fundamental objects in network sciences (Lewis] (2011) and random graph theory (Bollobás & Bollobás, 1998). There are also theoretical analysis and conjecture upper bound for MTS on ERR graphs (Coja-Oghlan & Efthymiou 2015
19

---

Published in Transactions on Machine Learning Research (04/2026)
Algorithm 1 Degree-based solution serialization
Require: The graph G(V,E), the independent set I 1: // Maintain the copy
2: 9 + --GI'++ I
3: Initialize empty ordered list
4: C=1
while I' + Φ do pick v E I' with smallest degree in g", break ties randomly
LU
Delete {u} U Neighbors(t) from g", delete from I'
end while
10: return Ordered list. L
Previous works (öthhr et al. 2022 Ahn et al. 2020 Sun & Yang 2023 Zhang et al. 2023 Alkhouri et al. 2025) used it as test graphs for MIS, though without varying parameters as we did.
ER graphs have 2 parameters: the number of nodes n and the average degree d. For graphs with given (n.d) d) We generate them by choosing M nd edges uniformly at random between n nodes. This is the Renyí's G(n, M) model.
There is also G(n, p) model for ER graphs, which is also used widely. They behave similarly for many graph properties to G(n, M) models when M = (2)p and we expect the emipirical results for MIS problems will also be very similar.
For the main experiments, we use ER graphs with n {100, 300, 1000, 3000, 10000), (10,30, 100, 300, 1000, 3000} 3000,
n as shown in Table 3 We also test on larger graphs with (30000, 1 10 x 10 10 3 x 109} shown in Table 9 Due to computational and time limits, we could only obtain results from classical CPU-based algorithms for these large graph, and only sparse graphs for very large n 2 1 x 105.
with
Barabási-Albent (BA) graph Barabási-Albert (BA) graphs (Albert & Barabási 2002 are random graphs generated by a probabilistic growth process, whereby new nodes preferentially attach to existing nodes with higher degrees, mimicking real-world networks such Internet, citation networks, and social networks (Albert & Barabási 2002 Radicchi al. (011). For BA graphs, we vary parameters: number of nodes and parameter (not number of edges). The average degree of BA graphs can be approximated 2m.
BA graphs also have 2 parameters: the number of nodes n and the generation parameter m, with > m. For a given (n, m), the generation process initializes with m nodes, and then add node at cach step. When adding a new node, m neighbors of the new node are sampled from the existing nodes, with the probability of the current degree of the nodes. The average degree of BA graph with given (n,m) can be computed d = 2m
m
2 2m.
For the main experiments, similar to ER graphs, we also use n = {100, 300, 1000, 3000, 10000}. Since the average degree 2m, we use m = (5, 15, 50, 150, 500, 1500) with 2m n.
RB graphs RB graphs are derived from Model RB (Xu & Li 2000 a random constraint satisfaction problem (CSP) model. RB graphs are considered difficult instances for MIS due to their structured randomness and high solution hardness.
We use two datasets from Zhang et al. (2023) (also used in Sanokowski et al. (2024)), RB- RB-small (200 300 nodes) and RB-large (800-1200 nodes), to benchmark lcarning- based solvers.
Real-world graphs We pick REDDIT-MULTI-S and COLLAB Yannadaag & Vishwanathan 2015 from TUDataset website (Morris al. 2020 since they have enough graphs for training and graph sizes not too small. REDDIT-MUL.TIS has 508.52 52 average nodes and 594.87 average edges. They mostly very sparse
20

---

Published in Transactions on Machine Learning Research (04/2026)
graphs. COLLAB has 74.49 average nodes and 2457.78 average edges. They are mostly small but dense graphs.
Since we need at least 4100 graphs to train and test our algorithms and the graphs should not be too small, it is difficult to find such datasets. Fortunately, Morris et al. (2020) provides a website www. www.graphleet.. www.gaaeaaaaanng.... which includes many graph datasets prepared by them or collected from other works. Although most of the datasets are still too small or having too small graphs, we are able to find 2 datasets: REDDITT-MULI-55 and COLLA, both from Yanardag & Vishwanathan (2015). REDDIT-MULTI-SK has 4999 graphs with average nodes 508.52 and average edges 594.87, so the graphs are generally very sparse. COLLA has 5000 graphs with average nodes 74.49 and 2457.78, so they are denser but smaller graphs.
We were not able to find real-world datasets with enough size of more larger and denser graphs, which are generally more difficult for MIS algorithms. The dataset DIMACS used Böther et al. (2022) contains such graphs but they only have graphs which is not enough for training.
B.3 Hardware configurations
The CPU we use is either Intel Xeon Processor E5-2680 v4 @ 2.40GHz or Intel Xeon Silver 4214 Processor @ 2.20GHz. The GPU we use is Nvidia Tesla A100 80GB when we refer to time limit or time cost. For small graphs when the GPU memory limit and time limit is not reached, we also use Nvidia RTX A6000 48GB and Nvidia RTX 20801i 11GB.
B.4 Classical CPU-based algorithms
Ran-Greedy and Deg-Greedy Deg-Greedy (Degree-based Greedy) is follows: Starting from empty set. Select node with the lowest degree of the graph (if there exists several nodes of the lowest degree, pick one uniformly at random) and add it to the set. Then remove the node and all its neighbors from the graph.
Ran-Greedy (Random Greedy) is as follows: Starting from an empty set. Select a node from the graph uniformly at random and add into the set. Then remove the node and all its neighbors from the graph. The only difference between it and Deg- gog-Greedy is that the choice of node completely random.
They are both non-backtracking algorithms.
We did not include results of Ran-Greedy in the main paper because ils performance is siguificantly lower than all other algorithms. It can be considered as baseline and has theoretical significance, since it has provable guarantce for random graphs (Grimmett & McDiarmid 1975).
In order to match the best-of-20 sampling we used for the learning- based-agoorrrtmmss, we also ran Deg-Greedy for 20 times and report the best results in the main experiments (n < 10000).
We wrote the script in Python and ran it single CPU thread for each graph with time limit of 24hrs, but it actually run less than 1hr smaller graphs like n S 3000. We gave 32GB memory for graphs with n < 10000 and 64GB memory for larger graphs. Since there are much more efficient implementations like C++, the efficiency of the greedy algorithms is not very relevant.
KaMIS (OnlineMIS and ReduMIS) KaMIS (Karlsruhe Maximum Independent Sets) Laam et al. 2017) htttps://karlsruhemiss github. . 1o/) is the state-of-art heuristic solver for MIS and has been used as a baseline in many previous works. It provides 2 algorithms for the MIS problem: ReduMIS (Lamm et al. 2017 and OnlineMIS [Dhllum et al.) 2016).
We can provide a time-limit for both algorithm. OnlineMIS will use up the time given while ReduMIS will end on its own when it finds appropriate. In general, ReduMIS provides better results when given enough time, where OnlineMIS is faster to reach a solution of reasonable quality for large and dense graphs
We ran both algorithm on single CPU thread for each graph with a time limit of 24hrs, because our benchmark focus on performance instead of efficiency. For relatively small graphs (n S 3000), ReduMIS often require less than 1hr and at most. 1.25hrs, and OnlineMIS can also provide answer with the same quality
21

---

Published in Transactions on Machine Learning Research (04/2026)
when giving 1hr time limit. We gave 32GB memory for graphs with 10000 and 64GB memory for larger graphs.
B.5
GPU-accelerated non-learning algorithms
isC0 isC0 (improved Sampling for Combinatorial Optimization) Sun et al. 2023 is a GPU-acoelerated sampling-base based method. It does not require learning. According to (Sun et al. 2023). the main benefit is that it can process large batch of graphs in parallel thus improve efficiency. While processing small number of graphs like in our case (8 test graphs), it still requires significant time, often longer than ReduMIS.
We use the code from the codebase of DISCS GGoshvadi et al. 2024), which is a follow-up paper for iSCO, as isCo did not provide the codebase. We use 80GB A100 GPU to run iSCO with all lest. graphs logether. The time limit 96hrs, and the actual time it requires shorter. It fail run graphs of size (n 3000, 1000), (n 10000, d = 100), and larger because they require larger than 80GB memory. The code does not support multi-GPU.
PCQO PCQO (Parallelized Clique-Informed Quadratic Optimization) AAlkhouri et al. 2025 is GPU- accelerated gradient- based optimization algorithm, which directly optimize on the quadratic loss function of the MTS problem. The loss function for a graph GV,(, E)) and solution vector æ is
f(x) = Σ E.p + VVV
Σ By - >' Σ
By (a,))EE
(1)
(u,v)E
where E' is the edge set of the complement graph G'. y and 7 are hyperparameters and there are many other hyperparametens including learning rate, momentum, etc.
This algorithm is sensitive to hyperparameters and the default hyperparameters lead to bad solution quality for most of our dataset. Therefore, unlike in other algorithms where we use the default setting, we perform a hyperparamettr lumining. We also did not find a good set of hyperparameters for all ER graphs or all BA graphs, so we do grid search of hyperparameters for each dataset (i.e. for each (n, d) pair in ER graphs and each (n, m) pair in BA graphs).
We use the hyperparamter search range suggested by the authors (Alkhouri al. 2025): J. We use learning rate (0.0001,0.00000, 0.00001, 0.000001), momentum 0.9, y {200, 500, 1000, 2000, 5000), 7 1, batch size 256, number of steps 27000, steps per batch 450. We then report the results obtained from the best set of hyperparameter. However, for n 2 30000, the grid search within this domain does not provide solution with reasonable size (worse than Ran-Greedy), so we do not report results for larger graphs. Despite that, there may exist. a better set of hyperparanters which could make this algorithm perform well on larger graphs. Automatic hyperparameter search could significantly improve the usability of this algorithm.
We use 80GB A100 GPU for all test graphs together with a time limit of 96hrs. It able run all experiments from 10000, and often requires shorter time compared to isCo and KAMIS.
B.6 Learning-basee algorithms
We use 4000 training graphs for each datasets to train our models. Without otherwise noted, all the training are in-distribution, with respect to single set of parameters (i.e. (n, d) for ER graphs, m)) for BA graphs) for synthetic graphs.
LWD LwD (Learning what to Defer) (Ahn et al. 2020 is reinforcement learning based algorithm which requires training data to learn the policy. It models the MIS problem Markov Decision Process (MDP), where in each step it selects some (possibly 0, 1, or multiple) nodes to add into the independent set. It is a non-backtracking am as the added nodes are never taken out. Böther et al. (2022) also included this algorithm in their benchmark.
We use the code from Böther al. (022) since provides better functionality than the original codebase. We use the default setting provided by Böther et al. (0222) in their MTS Benchmark codebase (https:
22

---

Published in Transactions on Machine Learning Research (04/2026)
but change the number of samples to 20 (defanlt is 10) for test sampling, in order to match the best-of-20 sampling in our benchmark.
We use 80GB A100 GPU to train for each datasets and test with the same GPU. The training time limit is set to 96hrs. The default number of training steps (number of updates to the policy) 20000. Since LwD stores checkpoints throughout the process, we still report the test results based on the newest checkpoints for unfinished experiments if we have the checkpoints which reports meaningful results (better than half of the results reported by Deg-Greedy). Those results are indicated by in the tables. The number of steps taken by those datasets with unfinished experiments is in Table
Table 7: Number of Steps at termination for unfinished LuD experiments
Type of Graphs
Parameters
Number of Steps at termination
(1000, 300)
1500
ER (n, d)
(3000, 100)
7200
(1000,50)
18600
(1000, 150)
9600
BA (n, m)
(3000, 15)
9300
(3000, 50)
600
LTFT LTFT (Let the Flows Tell) Zhang et al. 2023) similar to LwD, also model the MIS problem as a MDP and non-backtracking. The difference is that only choose 1 node at each step, making it more similar to Deg-Greedy. The node chosen at each step is chosen by GFlowNet (Bengio et al. 2021a). which is trained by in-distribution training data.
We use the default setting provide by Zhang et al. 2023 for training with 20 epochs. By default setting, it has best-of-20 sampling and report the best solution found.
We use 80GB A100 GPU train for each datasets and lest with the same GPU. The training time limit is set to 96hrs. It completes training for all graphs with n S 3000, but larger graphs require larger GPU memory. The code does not support multi-GPU.
DIFUSCO DIFUSCO (Diffusion Solvers for Combinatorial Optimization) (Sun & Yang 2023 trains diffusson model using supervised learning to produce solution for the MIS. The diffusion model provides an entire solution so it is a one-shot algorithm.
The training data is 4000 graphs for each dataset (1 set parameter for synthetic graphs). All training is in-distribution. The training data is labelled by ReduMIS with time limit of 1hr. For graphs used for training (n < 3000), ReduMIS gives the same performance compared to time limit of 24hrs.
We use the default setting in (Sun & Yang 2023) except that we use 50 diffusion steps throughout training and lesting, and 20 samples for testing to be aligned with best-of-20 sampling in other methods. We train the model for 50 epochs (default) for each dataset.
We use 80GB A100 GPU train for each datasets and test with the same GPU. The training time limit is set to 96hrs. The code does not support multi-GPU, We report results where the training can be completed.
Although Sun & Yang (2023) suggested that DIFUSCO has some generalization ability. We found the performance degrade significantly for out-of-distribution trained models (specifically trained smaller graphs with the same average degree but test on larger graphs), we did not report the results of larger graphs where the in-distribution training cannot finish.
DiffUCO DiffUCO (Diffusion for Unsupervised Combinatorial Optimization) (Sanokowski al., 2024] is also diffusion model based algorithm but unlike DIFUSCO it uses unsupervised learning. The diffusion model
23

---

Published in Transactions on Machine Learning Research (04/2026)
is trained to sample the solution of low energy state. It also provides entire solution and is also one-shot algorithm.
We use the default setting in Sanokowski et al. 2024) for RB-llare MIS task (in their Appendix C.5). During testing, we use conditional expectation with 20 samples to align with best-of-20 sampling in other algorithms. The code supports multi-GPU. We use 80GB A100 GPU to train for each datasets with time limit 96hrs.
The training time significantly longer than other learning- based algorithms for the same dataset and it can only complete training up to ER graphs with (n 1000, d 100) and BA graph with (n 1000, d = 50). According to Sanokowski et al. (2024) it has reasonable generalization ability, and we also found that the performance drop is relatively small if we test larger graphs using models trained with smaller graphs with similar average degree. Therefore, we also report lest results using out-of-distribution trained model. The parameters of those datasets and the datasets used to train corresponding models are reported in Table S Those results are labelled using f in tables.
Table 8: Paramcters of Test and Training Graphs for out-of-distribution testing in DiffUCO
Type of Graphs
Parameters of Test. Graphs
Parameters of Training Graphs
(1000, 300)
(1000, 100)
(3000, 10)
(1000, 10)
ER (n,d)
(3000, 30)
(3000, 30)
(3000, 100)
(1000, 100)
(1000, 150)
(1000, 50)
(3000, 5)
(1000,
BA (n, m)
(3000, 15)
(1000, 15)
(3000, 50)
(1000, 50)
B.7
Local search
Local search is method to improve given independent set. It can be used a post-processing technique, be used as sub-procedures in more complicated algorithms like KaMIS. Andrade et al. (2012) provides efficient local search algorithm. Part of it is to find 2-improvement, which is the part used as sub-procedure in KaMIS (Lamm et al. 2017 Dahlum et al. 2016).
The local search algorithm for 2-improvment for a given independent set / is as follows. This algorithm process every vertex æ E / in turn. First, it temporarily removes æ from I, creating a new set S. We call a vertex free vertex of S if there no edge between and any vertex in S. If S has less than two free vertices, stop: there is no 2-improvement involving x. Otherwise, for each neighbor v of x that is free vertex for S, insert into S and check if the new set (S') has free vertex w. If it does, inserting leads to 2-improvement; if it does not, remove from S' (thus restoring S) and process the next neighbor of w. If no improvement is found, reinsert into S to turn it back to I. Every vertex is scanned O(1) times in this algorithm so it can find a 2-improvement (if there exists) in (mm) time according to Andrade et al. (2012).
We implemented this algorithm in Python and use it as a post-processing for the solutions produced by the algorithm we test.
C More Experiment Results
In this section, we show more experiment results. Appendix C.1 shows more experiment results on much larger graphs, where the Al-inspired methods cannot handle. Appendix C.2 show the serialization results on more graphs. Appendix C.3 show more detailed results between LwD and Deg-Greedy, which applics bigree-based serialization as subprocodure. Appendix C.4 shows the full results when adding local search processocss procedure.
24

---

Published in Transactions on Machine Learning Research (04/2026)
C.1 Larger graphs
Table reports results for large ER graphs not reported in Table 2 Within our computation limits
described in Appendix B we can only obtain results for classical heuristic algorithms (Ran-Greedy, Deg-Greedy, OnlineMIS, ReduMIS).
Table 9: (Comparison of the performance of different algorithms on larger Erdös Seelss-Réniii (ER) graphs) Contimuation of Table on ER graphs with number of nodes larger than 100,000 for classical heuristic algorithms. Other algorithms out of our computational limits for these large graphs.
Heuristics
71
d
Ran-Greedy
Deg-Greedy
OnlineMIS
ReduMIS
10
7170.50
8951.75
9486.00
9505.38
30
3429.38
4464.12
4832.88
4914.88
100
1386.00
1817.25
1963.12
2012.62
30000
300
570.50
738.00
794.75
815.50
1000
205.63
260.75
279.88
287.50
3000
106.00
106.12
10
23990.00
29856.38
31613.38
31650.62
30
11444.38
14870.12
16128.88
16287.50
100
4615.25
6064.50
6564.00
6702.38
300
1886.62
2470.75
2661.50
2714.75
100000
1000
83.50
941.38
959.75
10
71954.38
89487.12
94622.88
94799.75
30
34318.88
44653.38
48234.38
48713.00
100
13850.12
18190.38
19676.50
20061.38
300000
300
5688.00
7987.50
8141.25
1000
2831.38
3000
802.00
10
239749.12
312462.62
315630.88
30
114397.00
158625.22 29
161622.75
1000000
100
46161.12
64915.00
66539.75
300
26458.75
1000
6890.00
9473.00
10
719348.75
904613.12
942475.57
3000000
30
343479.38
459671.29
179938.75
C.2
Serialization
Figures and shows the percentage to choose the smallest possible degree node different part of the scrialization across various algorithms for all ER graphs and all BA graphs with nodes S 3000, respectively. The serialization process is discussed in Section 4.2 Missing bars are algorithms which we do not get results
due to computational limit, same as in Tables andd
These results reinforced our obscrvations Scction 4.2 First, the percentage for Deg-Greedy and LTFT are generally high. Deg-Greede reaches 100% for all parts some graphs, which the theoretically achievable percentage since Deg-Greedy actually picks the lowest degree node in the remaining graph and this sequence
25

---

Published in Transactions on Machine Learning Research (04/2026)
ER (n= 100,
d-10)
ER (n=100, d-30)
76
100gz
33
36
50
37
26
100
07
Percettog
19 1/
2nd 1/3
2nd
Day Suready
LaR
DInISCO
Dep Sieedd
Delivetee
Lad
UTT
DRUSCO
(0=300, d=10)
(n=300,
100
02
92
100
1020moc
00
Percentge
Dasy Direnty
PC20
OFT
DRUISOO
Sreedi
800
UTF
DIIRCO
ER (n= 300, d=100)
ER (n=1000, d=
10000000
100
07
31
03
50
Perchtnge
23
30
50
30
15
Dig timmess
BECO
RCD0
DRUSCO
Delisett
Recsatti
RC00
180
DPF
DRUSCO
1n-0000,000 d-30)
(n-1000, d-100)
100
80
80
Percettng
40
A7
N
Strentp
Greedd
Onlinelil
Pentultyy
DT7
DIUACOO
ER (n=1000, d=300)
ER (n=3000, d=10)
10000.00
102
10b
200
300
Rertetaye
23
66
50
45
33
23
Deg Simends
850
DRURCO
Belatts
Le0
gmT
DRTRSCO
(n=3000, d=30)
ER (n=3000 d=100)
25
60
53
55
15
25
31
Deliaett
Drusco
Dep Sme-timedd
Delisttts
Redssee
Le0
UFF
DRUSCO
(n-3000, d-300)
(n-3000, d-1000)
100
102101000
100
95
100
10200000
100.00
Peccnttnge
73
Day Ctrendy
Redales
DRURCO
Gready
Redultes
800
A000
DROSCO
Figure 4: The percentage to choose the smallest possible degree node on different part of the serialization for all ER graphs reinforces our observations in Section 4.2 In addition, we also observe that algorithms similar to Deg-Greedy BeggGreedy and LTFT) and good- pord-performing algorithms (OnlineMIS, ReduMIS, iSCD, and LwD) have clearly different characteristies across various (n, d), described in Appendix C.2
26

---

Published in Transactions on Machine Learning Research (04/2026)
BA In=100, m=5)
BA (n= (n=100, m=
Pescetoge
50
1st
2nd
3rd
Deg Strmensy
Raskate
RED
DRURCO
Dep Greeds
Ressatrs
Le0
Ort
DRUSCO
(n=300, m=
(n= 300, m=15)
100
1000007 10
1000999
100
54
Pelortoge
Dogg limness
Delisets
PCDO
LoG
Dirasco
Dep tireess
UTT
DRUSCO
BA (n=
m=50)
BA (n=1000,
m= 5)
10300000
102300
100000
100020
10C.0
AO0800
300,00
04
Perceitnge
50
Dhig Ctreedp
DRUICOO
Onlinetto
Beriaad
RC0
D27
DRUSSO
BA (n= 1000,
m=15)
(n=1000 m=
35
27
15
35
Festerngge
33
35
Remoles
R5D
DEURCO
Degy Gtrendly
Oriments
LaO
DFT
DRUNCO
(n=1000,
m=150)
(n=3000, m=
100
1000000
10000
10000
100000
100000
1030
1000e
Pecortoge
24
37.
50
85
g
Dog Strneds
Delmatts
RCG
PCDO
DRUSCO
Grewdd
RC00
Lag
DIrUSOO
BA (n- 3000, m=15)
BA (000,00, m=50)
100
10
67
37 38
Someed
Delivetts
Rediado
Dinico
Dep Dep-timedd
Dnliwedes
un
DWosco
(n=3000,
(n=3000, m=500)
100
100
10200000
100300
10090
79
Percerage
Day Gimeaa
Redarts
umy
DRUcCO
Day Greddy
Reckatt
DRosco
Figure 5: The percentage to choose the smallest possible degree node on different part of the serialization for all BA graphs It reinforces our observations in Section 4.2 In addition, we also observe that algorithms similar to Deg-Greedy (Deg-Greedy and LTFT) and good-performing algorithms (OnLineMIS, ReduMIS, 1SCO, and LwD) have clearly different characteristies across various (n, m), described in
Appendix C.2
27

---

Published in Transactions on Machine Learning Research (04/2026)
will give a serialization with percentage 100% for all parts. In those cases, LTFT also have percentage close to 100% for all 3 parts.
Second, for those algorithms with good performance, namely OnlineMIS, ReduMIS, isCO, and LwD, the bar plot shows similar characteristics. The percentage for the 1st third is generally low, while the 2nd third is high, and the 3rd third is higher and close to 100%. This characteristies are observed in most settings accross various parameters (n, (n, m) for both ER and BA graphs. The exception is only very sparse BA graphs.
Moreover, newly from these plots across various parameters, also observe that given same n, Beg-Greedy and LTFT tend to have lower percentage for sparse graphs (smaller d or m) and higher percentage for denser graphs (larger d or m) across all 3 parts. On the other hand, OnlineMIS, ReduMIS, isCO, and LwD tend to have the percenlage of 1st 1/3 decreases, while the percentage of the 2nd and 3rd 1/3 increases, when the density of graph increases (d or m increases for same n). This shows another qualitative difference between the algorithms similar to Deg-Greedy (Deg-Greedy and LTFT) and the good-performing algorithms (OnlineMIS, ReduMIS, iscO, and LæD).
We also note that BA graphs (n = 300, m 50), (n 1000, 150), and (n 3000, 500) are outliers. Most algorithms have percentage close to 100% for all parts. This is because these graphs are rather different from other BA graphs They have an easily found large MIS, which is the m nodes initially in the graph at the start of the BA generation process. (Albert & Barabási 2002). From Table 3 we can see many algorithms can find these MIS and report MIS size of m for these graphs. This suggests that for this special type of BA graphs, our serialization analysis can observe different characteristics from other BA graphs.
C.3 Comparison between Deg Deg-Greedy and LwD
LwD, similar to LTFT, is also a non-backtracking MDP based algorithm which picks nodes sequentially, The main difference is that instead of picking node at a step like Veg-Greedy and LTFT, it picks some nodes at step, which can be 0 or or multiple nodes. In that case, it does not have a natural serialization like LTFT (discussed in Section 4.1p. However, since it still have steps and we still know some nodes are chosen before others, we perform a serialization within each step. We call this pseudo-natura serialization.
The procedure of our pseudo-natural serialization is as follows. Consider a step t of LwD, let the independent set before the step be I---- Similar to Amgorithm| | we build a residual graph G' which removes the nodes in I-- and their neighbors from G. Then, LwD chose a set of nodes S, to add to the independent set. We then perform the scrialization for the set St (replace I' by S in Algorithm [ and get a ordered list Lt La the ordered list for step. We then concatenate all the ordered lists L,'s 's for all the steps in order to get full ordered list L. For this serialization, we do not repeat it as in Algorithm I
Similar to Scction average percentage of the nodes being the smallest degree node in the residual graph. In addition to that, similar to Section 4.2 we divide the ordered list L. into 3 equal parts to compute the average percentage of the nodes being the smallest degree node seperately.
we plot a heatmap Figure 0 across various parameters for ER and BA graphs on the
The heatmaps for overall percentages suggest that LwD is not very similar to Deg reg-Greedy like LTFT. From the heatmaps for different 1/3 parts, we can the percentage increases from the 1st 1/3 to the 3rd 1/3 for all the datasets (different parameters of the synthetic graphs). This aligns with our "counterfactual" serialization results for LwD in Section 4.2 where we also observe the percentage increases clearly from 1st 1/3 to 3rd 1/3. This shows that our serialization method in Section 4.2 can reflect the pattern correctly.
The percentages here in the heatmap is smaller than the percentages for "counterfactual" serialization in the bar graphs in Section 4.2 This likely due to the fact that in the "counterfactual" serialization we repeat the serialization process for 100 times and report the highest percentages we get, while here we only do scrialization once for each step.
C.4 Local search
Table 10 shows the full results after incorporating 2-improvement local search from the ARW local search algorithm (Andrade et al. 2012: as processnn step, which is discussed in Section 4.3.
28

---

Published in Transactions on Machine Learning Research (04/2026)
Graphs 1st 1/3
Graphs 2nd 1/3
ER Graphs 1/3
Graphs Overall
10
10
10
30
43.10
22.49
8.37
3.95
8
71.46
41.82
30.88
20.93
30
94.00
72.57
57.43
56.43
30
69.46
45.60
32.22
27.10
80
100
95.53
9.94
5.22
100
90.02
32 86
22.15
100
97.23
62.52
49.48
100
94.25
35.09
25.61
300
84.93
300
88.41
300
96.48
300
89.93
60
Percentage
300
1000
3000
100
300
1000
3000
100
300
1000
3000
300
1000
3000
n
n
n
BA Graphs 1st 1/3
BA Graphs
2nd
1/3
BA Graphs 3rd
1/3
BA Graphs Overall
38.04
34.36
33.77
33.20
44.95
56.92
68.95
65.92
73.50
84.95
89.54
79.71
52.15
58.74
64.08
59.61
15
28.85
20.68
15.93
3.28
45.82
41.27
42.29
24.69
81.03
71.79
73,88
17.00
51.78
46.5/
44.03
34.99
m
10.54
78.30
9.47
50
53.63
8
73.41
34.28
22.65
150
98.22
150
98.22
150
98.47
150
98.31
100
300
1000
3000
100
300
1000
3000
100
300
1000
3000
100
300
1000
3000
Figure 6: Percentage of the smallest possible degree node in the pscudo-natural scrialization of LwD, i.e., behaves similarly to degree-based greedy, for the 3 equal parts of the serialization, and the overal average From the overall heatmaps, we can see LwD is not very similar to Deg-Greedy like LTFT. From the heatmaps for different 1/3 parts, we can see the percentage increases from the 1st 1/3 to the 3rd 1/3 for all the datasets (different parameters of the synthetic graphs). This aligns with our "counterfactual" results for LwD in Section 4.2 where also observe the percentage increases clearly from 1st. 1/3 to 3rd 1/3.
29

---

Published in Transactions on Machine Learning Research (04/2026)
Table 10: Adding local search as a post-processing procedure. This the full graph for local search
described in Section 4.3
Heuristies
GPU-aec
Learning-hased LTFT
param
Deg-Greedy
OnlineMIS
ReduMIS
19C0
PCQO
LxD
DIFUSCO
ER Graphs
100,10
29.50 (0.25)
30.50
30.50
30.62 (0)
30.63 (0)
30.38 (0)
29.00 (0.38)
30.25 (0)
100,30
13.62 (0)
14.00
14.75
14.50 (0)
14.50 (0)
14.38 (0)
13.25 (0.13)
13.88 (0)
300,10
92.12 (0.50)
93.88
94.38
94.75 (0)
94.63 (0)
94.25 (0)
90.12 (1.50)
93.50 (0)
300,30
11.75 (0.25)
47.88
17.88
47.62 (0)
17.63 (0)
46.88 (0)
41.00 (0.75)
44.62 (0.74)
300
16.12 (0)
18.00
18.38
18.00 (0)
18.00 (0)
17.12 (0.12)
16:25 (0)
16.88 (0.26)
1000,10
305.38 (2.13)
314.75
316.13
315.62 (0)
310.75 (0.75)
311.25 (0)
300.00 (3.00)
306.38 (2.50)
1000,30
152.75 (1.75)
158.88
163.75
163.50 (0)
159.13 (0.50)
158.62 (0.24)
151.38 (1.38)
150.62 (6.87)
100
60.75 (0.13)
64.75
66.63
66.50 (0)
60.88 (0.75)
64.12 (0.24)
61.88 (1.00)
57.88 (2.50)
1000,300
22. (0)
25.00
25.75
24.62 (0)
23.25 (0)
20.75 (1.63)
22.62 (0)
21.62 (0.74)
3000,10
913.62 (6.50)
947.25
954.25
950.88 (0)
927.38 (4.13)
935.38 (1.26)
900.62 (12.37)
918.00 (16)
3000,30
456.12 (4.24)
480.88
493.13
491.62 (0)
469.75 (5.50)
(0.75)
454.38 (5.38)
442.75 (29.37)
3000,100
185.62 (2)
194.38
201.50
200.38 (0)
189.75 (4.12)
191.50 (0.75)
185.62 (1.62)
182.25 (10.87)
3000,300
74.00 (0.50)
77.63
80.75
78.88 (0)
70.88 (1.63)
74.38 (0.50)
1000
23.38
26.00
23.00 (0)
(0)
BA Graphs
100.5
39.25 (0)
39.50
39.50
39.50 (0)
39.50 (0)
39.50 (0)
38.50 (0.38)
39.38 (0)
100,15
21.00 (0)
21.63
21.63
21.62 (0)
21.63 (0)
21.62 (0)
20.62 (0)
21.25 (0)
300.5
122.38 (0.26)
123.13
123.13
123.12 12 (0)
123.00 (0)
123.12 (0)
118.62 (3.00)
123.00 (0.12)
300,15
70.00 (0.75)
71.38
71.38
71.38 (0)
71.25 (0)
70.75 (0)
66.62 (1.87)
70.00 (0.50)
300,50
39.25 (1.75)
49.88
50.00
50.00 (0)
50.00 (0)
50.00 (0)
43.62 (1.87)
50.00 (0)
1000,5
413.38 (2)
417.13
417.18
417.12 (0)
415.88 (0.13)
416.00 (0)
400.25 (14.50)
417.12 (0)
1000,15
234.88 (1.63)
245.00
246.38
246:25 (0)
242.12 (0.12)
243.12 (0)
230.50 (6.25)
237 (1.50)
1000.50
108.35 (1.00)
115.75
116.88
116.75 (0)
114.00 (0.50)
113.12 (0.12)
106.75 (0.37)
108.75 (3.50)
1000,150
90.88 (7.63)
150.00
150.00
150.00 (0)
150.00 (0)
150.00 (0)
87.62 (5.37)
3000,5
1241.50 (1.75)
1257.00
1257.13
1255.62 (0)
1245.38 (2.38)
1248.50 (0.38)
1213.12 (35.87)
1254.75 (0.37)
3000,15
714.62 (7.50)
749.63
754.50
752.00 (0)
729.38 (7.13)
730.50 (2.75)
693.00 00.00000 (31.12)
731.75 (5.37)
3000,50
333 00 (3.62)
362.63
369.75
368. 258.2510 (0)
359.25 (2.13)
341.00 (4.12)
334.00 (10.12)
3000,150
142 88 (2.38)
160.25
165.75
164.00 (0)
153.38 (2.63)
146.50 (1.75)
3000,500
172.12 19.12)
300.00
500.00
491.00 (0)
229.62 (5.74)
30

---

Published in Transactions on Machine Learning Research (04/2026)
C.5 More results the ratio
In addition what we show in Section 4.4 Figure 7 shows the ratio of MIS size to alnd for ER graphs with number of nodes and average degree d across more algorithms. We 1sC0 has consitently high ratios more than 1.2. Ran Ran-Greedy stays around 1.0 for all (n, d). Other algorithms, including Deg-Greedy, all have higher ratios for spanser graphs, but lower ratios (close to 1) for denser graphs.
d that ReduMIS, Onl InlinMMIS, and
ReduMIS
OnlineMIS
Deg-Greedy
10
10
10
30
30
30
100
100
100
300
300
300
1e3
1e3
1e3
3e3
3e3
3e3
100
3e5
n
Ran-Greedy
iSCO
DIFUSCO
1.4
10
10
10
30
1.2
Ratio Values
100
300
100
1.0
1e3
3e3
300
100
300
1e3
1e4
100
300
1e3
0.8
n
DiffUCO
LTFT
PCQO
10
10
10
30
100
30
100
300
1e3
100
300
3e3
100
300
le3
100
300
1e3
3e3
100
300
1e3
3e3
1e4
Figure 7: Heatmap for ratios of MIS size to nln(d)/d on ER graphs with number of nodes n and average degree d. We can see that ReduMIS, Onl OnlineMIS, and isCo has consitently high ratios more than 1.2. Ban-Greedy stays around 1.0 for all (n, d). Other algorithms, including Deg-Greedy, all have higher ratios for sparser graphs, but lower ratios (close 1) for denser graphs.
Code and Data Release
We are committed to releasing the resources needed to reproduce our experiments. Our analysis code and random graph generation code is available at /https://github. http://ggtttuu.commiia wwikaiiww/MIS-uuaaa
This repository a lightweight rescarch-code release designed to support the full experimental pipeline of the paper rather than standalone software package. includes data generation, baseline solvers (greedy algorithms), analysis scripts, local search post-processing, and evaluation pipelines for learned methods. All
31

---

Published in Transactions on Machine Learning Research (04/2026)
components operate shared graph and solution formats (NetworkX gpickle graphs and 0/1 solution vectors stored either plain text or rresutt files) and are designed to be composed into unified workflow.
D.1 Data generation
The synthetic datasets this work consist of large random graphs, including Erdös Renyf (ER) graphs and Barabási Albert (BA) graphs. Because many instances are extremely large, we do not release all generated graphs. Instead, provide the exact generation code and parameters needed to reproduce them.
The data/ folder extends the MTS benchmark framework (https://github. com/MaxiBoether So-bbenchmrrk--frawwwrr.. Our code is designed to replace the corresponding files in the upstream data__eneration module while reusing the framework's infrastructure (sampling interface, dataset writing, and optional labeling). The script random_graphe py implements both samplers and dataset generation.
Supported graph familics inchude Erdös-Renyi, m), Barabési-Albbrt, Holme-Kim, Watts Sartss-trrogazz and hyperbolic random graphs, well fixed-size variants such as GND, Regular, BA BA_n_ n_m, HK [_____PP __m_P, and WS j$_n_k_p. Graphs are serialized ggickll files and can optionally include node weights and labels.
For RB graphs, we use the generation code from the LTFT repository (nttps://github. cttph/bab..cm//maaarrrs/ll/ - Cttp///////teeeeeaaaaaaaaaaaaaa following prior work.
We also evaluate on real-world datasets REDDIT-MULTI-5K and COLLAB from the TUDataset collection Morris al. (2020) https://chrrmrrs..ge ittpmb/.o///aatss//////
D.2 Greedy algorithms
The repository includes implementations of the baseline solvers used in the paper, namely degree-based greedy (Deg-Greedy) and random greedy (Ran-Greedy). These implementations operate directly on the shared data format (- gpickle graphs and 0/1 solution vectors) and are integrated with the overall pipeline.
Both Deg-Greedy and Ran-Greedy support repeated randomized runs with best-of-k selection, matching the experimental protocol described in the paper. The local search implementation corresponds to the post-processing procedure used in Section 4.3 taking initial solution and itcratively improving it while maintaining feasibility.
D.3 Analysis codes
We release the analysis code used to aggregate raw solver oulputs and regenerate the results reported
Section 4
LIFT comparison (1tft/). The 1tft/ folder contains the evaluation entry point used for LTFT-based methods (see Section 4.1 The main script, evaluate. py, runs inference on MIS test graphs, performs and saves the best solution for each graph as a result file. It also records degree-ranking diagnostics in rankings. out and stats. out. This script depends on the upstream implementation at sttt:://gghhuu.ccm//aaaaaaaaa//p
repeated stochastic rollouts
Other algorithm comparison (serialization/). The serialization/ folder contains the analysis scripts used for our serialization-style comparison legree-based greedy (see Section 4.2). All scripts operate gpickle graphs and solution vectors (plain text .result), validate independence, and simulate the randomized greedy-removal process. They report rank-1, top five percent, and top ten percent. agreement statistics. Scripts include compare peeearregreedy.ppe py, compare_ Becearr_greey__eeeeegee greedy_folders.p
py, and compare
Local scarch analysis (local_search/). The local seeal_search/// folder contains scripts used for analyzing the effect of local search (see Section 4.3), including evaluation of improvements over initial solutions and integration with the same solution format used across the pipeline.
32

---

Published in Transactions on Machine Learning Research (04/2026)
D.4 External solver codebases
In addition to our own implementations, we use external solvers from prior work:
KaMIS (OnlineMIS / ReduMIS) Dahlum et al. (2016): Lamm et al.
(0177 :
https: https://gitte //ggttubb
LwD Ahn et al. 2020 official repo https://githut
we use the patched MISBenchmark version Böther et al. 2002 htttgs//jthub..co///rBBBBeeer1
mis-benchmark fraaeaorkkkfaaaakokk
LTFT Zhang al.
2023
DIFUSCO Sun & Yang
2023
DiffUCO Sanokowski et al.
2024
httg:r//gthhuo.oom///////////1/
PCQO Alkhouri et al.
(2025): : http:///tttaaacccc//ecemmmmmeett
iSC0 Sun et al.
(023
Reproducibility statement. The released repository includes data generation, baseline solvers (greedy algorithms), local search post-processing, analysis scripts, and evaluation pipclines, together with links external solver implementations. These components sufficient to reproduce the datasets, baseline results, and analysis presented in the paper. Documentation provided in the repository to guide reproduction of the main experiments.
33


Reviews:
[{"review_id": "DahZnVcvdY", "reviewer": "Reviewer_FE6x", "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": "", "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 present paper provides a large-scale, systematic benchmark showing that state-of-the-art AI-inspired methods for Maximum Independent Set (MIS) consistently underperform classical CPU-based solvers, especially KaMIS, even on in-distribution random graphs. In particular, they show that performance gaps widen with graph size and density, and that several AI methods fail to beat even the simplest degree-based greedy heuristic.\n\nIn order to analyze the performance, they introduce serialization, a new analysis tool that converts any MIS solution into a sequential decision process, enabling fine-grained comparison across algorithms. This analysis shows that some learning-based methods effectively replicate degree-based greedy behavior, explaining their limited gains.\n\nOn another angle, they present empirical evidence against the practical relevance of the shattering-threshold conjecture for MIS.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper's claims are mainly empirical, and the experiments are systematic: strong benchmarks, large and diverse datasets, and a wide range of methods are compared.", "audience_yn": "Yes", "audience_explanation": "This would interest most researchers working on the intersection between machine learning and combinatorial optimization.", "requested_changes": "Small typo: In legend for Table 5, Incoperating->Incorporating", "broader_impact_concerns": "Not applicable.", "additional_comments": "As you already noticed, AI-based methods perform especially well in real-world datasets. You mention this is because the datasets are easier. This is an important practical point: if the performance in real-world tasks is similar, what is the disadvantage of AI-based methods? Running time, computational resources? Are there no harder real-world datasets to compare? This point requires further discussion.\n\nRegarding references and discussion, it seems like the paper extends the analysis of [1] to more datasets and deep learning-based algorithms. I reckon the paper is cited, but given its importance for this study, further discussion regarding its limitations is needed.\nFurthermore, one of the conclusions of the paper is the need for \"Principled Integration of Classical Heuristics\" into deep learning frameworks. Maybe some discussion of current literature on the topic (such as [2]) could be helpful.\n\n\n[1]- Angelini, M. C., & Ricci-Tersenghi, F. (2023). 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.\n\n[2]- Garmendia, A. I., Ceberio, J., & Mendiburu, A. (2023). Neural improvement heuristics for graph combinatorial optimization problems. IEEE Transactions on Neural Networks and Learning Systems.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8pusyAC7kW", "reviewer": "Reviewer_e7Pk", "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": "", "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": "AI-inspired approaches for combinatorial optimization are often consistently outperformed by state-of-the-art classical solvers. The authors investigate the reasons behind this gap, proposing a novel analysis framework of analysis called serialization. Their analysis shows that non-backtracking AI-inspired methods effectively perform reasoning similar to simple degree-based greedy heuristics, which explains their inferior performance compared to advanced solvers such as KaMIS..", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper seems sound, the scope is clear and the evidence appears convincing", "audience_yn": "Yes", "audience_explanation": "The paper can be interesting for the TMLR audience as it introduces informative results whose methods may influence future lines of research outside the scope of the paper itself", "requested_changes": "The TMLR guidelines suggest to be cautios about overstatements about the results of the paper, it appears to me that, although the paper has many merits, it seems to me too speculative to assert that KaMIS’s performance “contradicts” or challenges the Coja-Oghlan Efthymiou conjecture, can the authors explain more thoriughly this claim?\n\nThe authors note that PCQO is sensitive to hyperparameters and that better tuning might improve results. This should be discussed more critically: if AI methods require extensive tuning to match classical heuristics, that is itself a limitation, can be this due to the fact  that methods are under-optimized relative to KaMIS?\n\nSerialization is intuitive I wonder if a more deepened theoretical analysis is possible.", "broader_impact_concerns": "No broader immpact concern", "additional_comments": "This paper makes a clear and well-supported contribution. The results are informative and the insights might influence future research lines.", "extra_scores": {}, "extra_text": {}}, {"review_id": "EEOhy1YBMi", "reviewer": "Reviewer_3pmo", "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": "", "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 compares a bunch of AI algorithms for combinatorial optimization against traditional heuristics on the MIS (maximum independent set) problem, finding that AI algorithms do not seem to do much better than simple heuristics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes, as far as I can tell the key experiments were done correctly and the results support the claims. That being said, it would be highly beneficial to the community if the authors released all their evaluation code and raw data along with the paper.\n\n~~The reason I answered \"no\" is just because I am concerned that the author's claim needs to be qualified with a statement about bias in the evaluation graphs (see \"requested changes\" below). If this is done I can change my answer to \"yes\".~~\n\n**Update**: after discussion with the reviewers I am no longer concerned about graph bias, I've changed my answer to \"yes\".", "audience_yn": "Yes", "audience_explanation": "Yes, ML for graph algorithms is an important topic which receives continued interest from the ML community.", "requested_changes": "Please clearly explain the limitations of your conclusions due to the choice of graphs. Although the paper touches on some of the theory behind ER random graphs, it really should explain the biases of these graph types:\n\n- ER random graphs are highly connected, and with high probability have O(ln d) MIS (a rather small number). Furthermore, due to the law of large numbers there is a concentration in the degree of nodes, so from the perspective of a MIS solver the graph \"looks\" like a couple of low-degree nodes and a bunch of nodes with similar degree. Choosing the low degree nodes already gets close to the optimum.\n- BA random graphs have \"hubs\" which are _not_ part of the MIS solution (because they are too highly-connected). Choosing non-hub node (which also have low degree) is a great strategy.\n- The \"real\" graphs see roughly the same performance of most algorithms. I suspect their structure is closer to BA since many real-world networks have this kind of structure\n\nIn short, I think the set of evaluation graphs is biased towards graphs where greedy heuristics are rather effective. This isn't necessarily a bad thing if you care about performance on real-world graphs (maybe greedy heuristics tend to work very well on real world graphs), but since the paper's main claim is about the _performance of AI algorithms_ I think at a minimum this bias should be stated transparently. Ideally the authors could do an additional experiment on systematically \"harder\" graphs and see if their conclusion still holds.\n\nI don't have a particular suggestion in mind for \"harder\" graphs, but some ideas for inspiration:\n\n- Random geometric graphs / unit disk graphs (high degree of clustering)\n- Stochastic block models / community graphs (tests whether heuristics are thrown off by community structures)\n- Hard benchmark sets for maximum clique problems\n- Random regular graphs (or graphs with a much more concentrated distribution of node degrees)\n\n\nMy second requested change is about §4.4. As far as I understand the results from Coja-Oghlan & Efthymiou which the authors claim to challenge are _asymptotic_, so experiments with small n and d don't contradict the theory. Maybe instead say something like \"empirically, modest size graphs are very far from the asymptotic regime.\" The current phrasing seems to overclaim the significance of the finding.", "broader_impact_concerns": "No concerns", "additional_comments": "Note that I am not really an expert in combinatorial optimization / graph theory so many of my suggestions were things I learned while doing research for this review. I have a very superficial understanding of theory in this area.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)