Library

Variational Annealing on Graphs for Combinatorial Optimization

Several recent unsupervised learning methods use probabilistic approaches to solve combinatorial optimization (CO) problems based on the assumption of statistically independent solution variables. We demonstrate that this assumption imposes performance limitations in particular on difficult problem instances. Our results corroborate that an autoregressive approach which captures statistical dependencies among solution variables yields superior performance on many popular CO problems. We introduce subgraph tokenization in which the configuration of a set of solution variables is represented by a single token. This tokenization technique alleviates the drawback of the long sequential sampling procedure which is inherent to autoregressive methods without sacrificing expressivity. Importantly, we theoretically motivate an annealed entropy regularization and show empirically that it is essential for efficient and stable learning.

cs.LGcs.AIcs.DMstat.MLComputer ScienceMathematics
Source

Paper

References (54)

01Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetsDinghuai Zhang, H. Dai, Esmeralda S. Whitammer et al.2023 · arXiv.org · 52 citations In Library
02Unsupervised Learning for Combinatorial Optimization Needs Meta-LearningHao Wang, Pan Li2023 · International Conference on Learning Representations · 28 citations In Library
03DIMES: A Differentiable Meta Solver for Combinatorial Optimization ProblemsRuizhong Qiu, Zhiqing Sun, Yiming Yang2022 · Neural Information Processing Systems · 171 citations In Library
04Neural Set Function Extensions: Learning with Discrete Functions in High DimensionsNikolaos Karalias, Joshua Robinson, Andreas Loukas et al.2022 · Neural Information Processing Systems · 16 citations In Library
05Annealed Training for Combinatorial Optimization on GraphsHaoran Sun, E. Guha, H. Dai2022 · arXiv.org · 27 citations In Library
06Supplementing recurrent neural networks with annealing to solve combinatorial optimization problemsShoummo Ahsan Khandoker, Jawaril Munshad Abedin, Mohamed Hibat-Allah2022 · Machine Learning: Science and Technology · 13 citations In Library
07Unsupervised Learning for Combinatorial Optimization with Principled Objective RelaxationHaoyu Wang, Nan Wu, Hang Yang et al.2022 · Neural Information Processing Systems · 52 citations In Library
08Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setM. C. Angelini, F. Ricci-Tersenghi2022 · Nature Machine Intelligence · 51 citations In Library
09Can Hybrid Geometric Scattering Networks Help Solve the Maximal Clique Problem?Yimeng Min, Frederik Wenkel, Michael Perlmutter et al.2022 · Neural Information Processing Systems · 34 citations In Library
10What's Wrong with Deep Learning in Tree Search for Combinatorial OptimizationMaximilian Böther, Otto Kißig, M. Taraz et al.2022 · International Conference on Learning Representations · 64 citations In Library
11Combinatorial optimization and reasoning with graph neural networksQuentin Cappart, Didier Chételat, Elias Boutros Khalil et al.2021 · International Joint Conference on Artificial Intelligence · 502 citations In Library
12Variational neural annealingMohamed Hibat-Allah, E. Inack, R. Wiersema et al.2021 · Nature Machine Intelligence · 111 citations In Library

Scroll for more · 38 remaining

Similar papers

Annealed Training for Combinatorial Optimization on GraphsHaoran Sun, Etash Kumar Guha, Hanjun Dai2022 · arXiv (Cornell University) In Library
Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on GraphsNikolaos Karalias, Andreas Loukas2020 · arXiv (Cornell University) · 175 citations In Library
Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and MoreFanchen Bu, Hyeonsoo Jo, Soo Yong Lee et al.2024 · International Conference on Machine Learning · 10 citations In Library
Learning Combinatorial Optimization Algorithms over GraphsElias Boutros Khalil, H. Dai, Yuyu Zhang et al.2017 · Neural Information Processing Systems · 1.7k citations In Library
Graph Learning for Combinatorial Optimization: A Survey of State-of-the-ArtYün Peng, Byron Choi, Jianliang Xu2020 · arXiv (Cornell University) · 5 citations In Library
Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization ProblemsShoummo Ahsan Khandoker, Jawaril Munshad Abedin, Mohamed Hibat-Allah2022 · arXiv (Cornell University) · 2 citations In Library
Graph Learning for Combinatorial Optimization: A Survey of State-of-the-ArtYün Peng, Byron Choi, Jianliang Xu2021 · Data Science and Engineering In Library
Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial OptimizationPablo Loyola, Kento Hasegawa, Andres Hoyos-Idobro et al.2025 · arXiv.org · 1 citation In Library
Supplementing recurrent neural networks with annealing to solve combinatorial optimization problemsShoummo Ahsan Khandoker, Jawaril Munshad Abedin, Mohamed Hibat-Allah2023 · Machine Learning Science and Technology In Library
Regularized Langevin Dynamics for Combinatorial OptimizationShengyu Feng, Yiming Yang2025 · International Conference on Machine Learning · 11 citations In Library

Peer review

Accept (poster)NeurIPS 2023 · via OpenReview
Reviewer rhwA4/10 · confidence 4/52023-07-03

Summary

This paper uses RL and Annealing to train a learned CO solver. They demonstrate that their algorithm empirically performs well over many problem types and dataset types.

Strengths

1. This paper uses several important baselines. 2. The breadth of the datasets chosen is good.

Weaknesses

1. You are missing a comma in the first sentence. 2. Use \citep to put parentheses around your citations 3. You misspell Reinforce in the table. 4. The experiments seem relatively limited in that comparison is only for two problem types. Moreover, the authors do not compare with Gurobi to get a range on how solvers that are not learned perform on these problems. Also, the time taken by each algorithm is not used to compare these algorithms. Indeed, these metrics are important to see to compare. 5. I do not understand the contribution of this paper. Indeed, it seems that this paper combines annealing from Sun et al. and RL for CO, which is also known. The subgraph solving seems to reflect many classical CO algorithms and is not new. The subgraph tokenization may be novel. In general, I'm a little confused about what the overall contribution of this paper is in the context of the literature. 6. Also, the improvement in the solving ratio seems very small, enough such that hyperparameter tuning your algorithm and not tuning the baselines can make this difference. I might also change the title of the paper. Currently, it closely resembles "Annealed Training for Combinatorial Optimization on Graphs" by Sun et. al.

Questions

1. During the RL process, how do you compute the reward of an intermediate graph where spins for certain nodes have not been assigned? Do you only compute the reward for nodes that have assigned spins? Overall, due to the limitations in the experiments, issues with experiments, and lack of contribution, I am voting to reject this paper. However, if the authors can run some further experiments comparing this paper with Gurobi and including the time taken by each algorithm, I believe this paper will be improved. I am flexible, so if the authors adequately address my concerns, I will increase my score accordingly.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

1 poor

Contribution

2 fair

Limitations

They have addressed the limitations.

Reviewer 59Wh6/10 · confidence 3/52023-07-05

Summary

The authors present Variational Annealing on Graphs for Combinatorial Optimization (VAG-CO), a novel method for tackling combinatorial optimization problems. This method presumably combines elements of variational inference, annealing, and graph theory to form an effective optimization approach. ===== After reading the rebuttal, the authors have convinced me to increase my score.

Strengths

Novel Methodology: The paper presents a new approach to solve combinatorial optimization problems, Variational Annealing on Graphs for Combinatorial Optimization (VAG-CO), which is innovative and adds value to the existing literature. Overcoming Limitations of Existing Methods: The authors identify the limitations of the widely used Mean-Field Approximation (MFA) and propose a way to overcome these, which demonstrates a deep understanding of the problem space. Improvement in Efficiency: The use of sub-graph tokenization and entropy regularization to improve the efficiency of the training and inference process could potentially revolutionize the way these types of problems are solved.

Weaknesses

1. The experiments are only completed on synthetic data. It will be more convincing if the proposed method can be applied and compared on some real data. 2. Maximum Independent Set (MIS) and Minimum Vertex Cover (MVC) are well-known problems in graph theory and are widely used as benchmark problems in combinatorial optimization. However, they only represent a subset of the vast array of combinatorial optimization problems. A more extensive evaluation of the proposed method would involve its application to a larger and more diverse set of problems. This would enable a more comprehensive understanding of its capabilities and limitations. If the authors want to claim the wide application of the proposed method, they may want to conduct experiments for Traveling Salesman Problem, Knapsack Problem, Vehicle Routing Problem etc.

Questions

How do the authors define hard problems in the paper? What are the criteria?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The experiments are not extensive.

Reviewer fy9s6/10 · confidence 3/52023-07-05

Summary

This paper explores the use of autoregressive deep generative models for solving combinatorial problems. Starting from an optimization problem, the authors reformulate it using a Boltzmann distribution on the solution set. This distribution can then be approximated with a parametric family, typically a neural network, following a variational approach (minimization of the free energy). While many previous works use the independent (or "mean field") approximation, it is suggested that building the solution iteratively is more expressive, and thus performs better. In this case, the autoregressive model used is a graph neural network, which gives a conditional probability for the current spin given past choices. To increase inference speed, two tricks are introduced: subgraph tokenization (making several decisions at once) and dynamic graph pruning (removing fixed vertices from the graph). Training is achieved using a temperature annealing scheme which favors gradual concentration around global optima. This annealing process enjoys an interpretation in terms of sample complexity and curriculum learning. Numerical experiments on the maximum independent set and the minimum vertex cover problem show the promise of this new method.

Strengths

### Originality This paper describes a new combination of known ideas, coherently motivated by the specific goal of solving hard optimization problems: - formulation of optimization in the language of statistical physics - variational approximation of the Boltzmann distribution - iterative construction of a solution - RL framework with partial rewards - temperature annealing As far as I can tell, the training tricks related to tokenization and pruning seem to be novel. ### Quality The proposed model makes theoretical sense, and rests on solid foundations of previous work. I particularly enjoyed the interpretation of annealing as curriculum learning: as the temperature gets lower, the learning gets harder. As for the numerical experiments, they appear to be thorough and include a wide variety of algorithms. The authors also took care to test on harder instances whenever nearly optimal solutions were too easy to reach. They do however exhibit a few inconsistencies, which I point out below. ### Clarity n.a. ### Significance This paper contributes to a wider discussion on the best variational ansatz for combinatorial optimization. Comparing mean field with autoregression is an important first step, and hopefully the field can evolve towards more generic structured representations. Subgraph tokenization is also an interesting idea, which deserves to be pushed further.

Weaknesses

### Originality ### Quality A questionable algorithmic choice is the arbitrary order in which nodes are processed. It isn't obvious why BFS ordering of the vertices makes more sense than other options. The same goes for subgraph tokenization: why take the $k$ next vertices in the BFS order, even though they might be very far apart from each other? As for the experiments, the realistic datasets of the first batch are seemingly too easy, since every method implemented by the authors (including the baseline DB-Greedy) shows near-perfect accuracy. The results of Table 2 are very surprising to me, as both EGN and MFA are mean field methods with conditional expectation decoding, yet they exhibit wildly different performances on the minimum AR. On the other hand, the average AR is only reported for new methods, not for the state of the art. I would welcome more detail from the authors on this point. In any case, the benefits of autoregression as opposed to independence are not definitively proven by this series of benchmarks. The synthetic datasets of the second batch are designed to be harder to solve, but the associated plots do not include other methods from the state of the art, which were analyzed on realistic datasets only. Again, clarification from the authors would be very welcome. ### Clarity The notations are sometimes a bit hard to follow. Several algorithms included in the benchmark suite are only mentioned earlier in the text. ### Significance Depending on the validity and fairness of the benchmarks, the results may be less significant than announced by the authors. I look forward to the rebuttal period to enlighten this aspect.

Questions

L121: Why BFS in particular? Is there a way to make the order itself parametric? L160: Is there a way to perform subgraph tokenization that does not scale exponentially with $k$? L198: Are there other insights from curriculum learning that we could draw inspiration from? I'm not at all familiar with this literature L215: What if our problem provides no natural way to define partial rewards? L312: Why change the evaluation metric from approximation ratio to relative error? Not sure I grasp the difference

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

The authors do not discuss many limitations of their work, although they mention the additional complexity. Societal impact is irrelevant here.

Reviewer ojQm8/10 · confidence 4/52023-07-14

Summary

This submission proposes a novel unsupervised framework for solving graph combinatorial optimization problems. The proposed method is coined as VAG-CO, which autoregressively generates solutions to CO problems via annealing / reinforcement learning. Corresponding theoretical analysis is provided and numerical demonstration on various datasets are conduct.

Strengths

- This paper is well written, and the technique is solid. - The proposed autoregressive generation is appropriate for solving graph CO problems whose solutions are a set over the nodes, which could be represented with a binary vector. - The authors use RL to optimize and carefully design an MDP to achieve that. - An open sourced implementation is also provided. - Solid technical analysis is provided. - Various experiments on both simulated and realistic benchmark and on both MIS and MVC tasks.

Weaknesses

This submission is great. A few issues are listed as follows. - It seems the method is also applicable for other CO problems such as Minimum Dominate Set. Would it possible for the authors to elaborate about at least the possibility? - It would be also good to evaluate under some subset of the MIS benchmark (https://github.com/maxiboether/mis-benchmark-framework).

Questions

See above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

See above.

Reviewer rhwA2023-08-10

Request for Further Clarification

I want to state I appreciate the detailed rebuttal. I have a few follow-up questions. ### Gurobi On real datasets such as Collab and Twitter, if you give Gurobi the same amount of time as VAG-CO to run, which is the stronger method in terms of approximation ratio? I understand you used Gurobi to calculate the approximation ratio, but which is the faster method on real datasets? I believe this is an important point for me. ### Questions about the experiments What do you mean when you say you can't provide the runtimes of Karalias et al. 2022 since they didn't provide the results? Are you not rerunning their algorithm on your setup? What about the method from Sun et al. 2022? I believe this is MFA-Anneal CE in your paper. Do you rerun their implementation or rely on the numbers from their paper? ### Code for the experiments May I ask why there was no code provided with this submission? I would have liked to check this code for an empirical paper such as this. ### Questions on Experiments Namely, of the four points you mentioned, the problem of MFA relying on the assumption that the parameters are statistically independent is known, so I do not believe point 1 contributes to this paper. Moreover, point 4 was discussed already in Sun et al. 2022. However, I agree that (ii) subgraph tokenization seems to be the central contribution of this paper that no other paper has done. Is there anything else I am missing?

Reviewer fy9s2023-08-11

The code is indeed provided: https://github.com/VAG-CO/VAG-CO

Authorsrebuttal2023-08-11

Further Clarification

We thank the reviewer for the prompt reaction. We are happy to read that the novelty and importance of Subgraph Tokenization is now acknowledged by the reviewer. We also point out that the reviewer is not correct in suggesting that we do not provide code. Our git repository is linked in a footnote on page one. **“On real datasets such as Collab and Twitter, if you give Gurobi the same amount of time as VAG-CO to run, which is the stronger method in terms of approximation ratio? ... which is the faster method on real datasets?”** In our experiments on MVC, MIS, Max-Cut, and Max-Clique Tab. 2,3,4,5 and Fig. 1 in the rebuttal file we report the Gurobi performance for 2-4 different Gurobi runtime limits which were chosen such that at least one runtime limit is comparable to the corresponding runtimes of VAG-CO. In the experiments on real-world graphs (Tab. 2,3,4) Gurobi is often able to solve the problems optimally within runtimes that are shorter than those for learned methods. Thus for these comparably easy CO problem instances Gurobi is the best performing method. Results on the hard synthetic datasets in Fig. 1 left and middle in the rebuttal file show again that Gurobi is superior for the easier synthetic problems, i.e. in Fig. 1 left the $AR^*$ is better for Gurobi at low $d$ and in Fig. 1 middle $AR^*$ is better for Gurobi at high $p$. For the particularly hard problems (high $d$, low $p$) VAG-CO outperforms or matches the results of Gurobi for comparable time budgets. **“What do you mean when you say you can't provide the runtimes of Karalias et al. 2022 since they didn't provide the results? Are you not rerunning their algorithm on your setup?”** As we state in the captions of Tab. 2 - 5 “(r)” indicates that these results are taken from the corresponding references - this does also hold for the corresponding runtimes. That means indeed that we did not run the methods from Karalias et al. [2022] ourselves but that we only report these results. We want to point out here that re-running all competing methods ourselves is computationally infeasible for us. **“What about the method from Sun et al. 2022? I believe this is MFA-Anneal CE in your paper.”** No, this is not “MFA-Anneal CE” in our paper. In contrast to Sun et al. [2022] our “MFA-Anneal CE” is trained via REINFORCE as stated in L273: “We also report results of our own implementation of an MFA-based method that is trained with REINFORCE.”. **“Do you rerun their implementation or rely on the numbers from their paper?”** As pointed out above “MFA-Anneal CE” is not the method of Sun et al. [2022]. We ran all experiments that are not indicated as “reported” by “(r)” by ourselves. This includes “MFA-Anneal CE”. The reviewer criticizes the four contributions of this paper that we listed in the response to the reviewer’s initial review. **“Namely, of the four points you mentioned, the problem of MFA relying on the assumption that the parameters are statistically independent is known, so I do not believe point 1 contributes to this paper.”** Our first point reads: “identification of a central limitation related to mean-field methods in numerous recent works”. The reviewer correctly states that the mean-field approximation (MFA) relies on the assumption that the parameters are statistically independent. In fact, that is the defining property of MFA. But this is not the point of our first contribution. Our contribution is that we point out that many recent methods in the field of neural CO rely on MFA and are limited by this assumption. We show empirically that by using a more expressive approach that does not rely on MFA we can obtain superior performance in particular on CO problem instances that are hard. In case the author is aware of any prior work that made this point we would be very interested in the corresponding references. **“Moreover, point 4 was discussed already in Sun et al. 2022.”** Our fourth point reads: “a motivation for annealing from statistical learning theory”. This point refers to Remark 1 in L194 in which we make a formal statement about the sample complexity of approximating Boltzmann distributions. We consider this theoretical insight as one of our contributions. We are not aware of any formal learning theoretical statement in Sun et al. [2022]. Based on our Remark 1 we argue that annealing can be regarded “as a principled curriculum learning approach”. The connection between annealing and curriculum was conjectured without learning theoretical arguments in Sun et al. [2022]. For this reason we will cite Sun et al. [2022] as follows in L201: “A connection between annealing and curriculum learning was put forward less formally already in Sun et al. [2022].” Karalias et al. [2022], “Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions”, arXiv:2208.04055 Sun et al. [2022], “Annealed Training for Combinatorial Optimization on Graphs”, arXiv:2207.11542

Reviewer rhwA2023-08-11

A few clarifications

I wanted to confirm a few things: 1. Gurobi beats VAG-CO on all datasets besides challenging RB problems, correct? 2. Do you have experiments for Karialas et al.'s work on RB problems? I believe you sampled these problems yourself. I have run their methods before. I disagree it is computationally infeasible. I see this work mainly as an empirical paper, so I am trying to understand better where and what this algorithm beats. It consistently beat the greedy baselines, MFA-anneal, and Karalias on real datasets (but not by much). On complex problems, it beats them slightly more but not that much better, having an AR difference of around .005 with the second-best method, and Karalias isn't used there, which is essential. It does not beat Gurobi at all on anything besides on hard problem case, as you mentioned. Therefore, I struggle to see how this, as an empirical paper, should be accepted if the improvement is marginal on most problem types (including the RB model) and it doesn't beat Gurobi, which is a classic benchline to beat in this literature. You also don't use Karalias as a baseline on RB model problems, the problem set where this paper has the most edge. I believe Karialias et al. or Sun et al. to be important baselines here due to their performance on RB problems. Have I misunderstood anything here? I hate to be harsh or discouraging to the authors, and I hope that my feedback is constructive.

Authorsrebuttal2023-08-16

**“1. Gurobi beats VAG-CO on all datasets besides challenging RB problems, correct?”** The reviewer’s question is based on an interpretation of our results that is not valid for the following reason: the extent of the parallelization of the solution search in both methods is arbitrary and thus not comparable (Gurobi : 24 CPU cores, 26 threads; VAG-CO: 1 GPU , 8 threads). Our paper’s contribution is not to decide whether Gurobi or VAG-CO is the better algorithm. We agree that this question is interesting but it is not what our experiments were designed for. Our experiments are designed for the comparison to the state of the art in neural CO. The vast majority of recent neural CO works like e.g. Karalias et al. [2020, 2022] and Sun et al. [2022] use Gurobi to obtain ground-truth and some of them report the corresponding runtimes but they do not interpret their results as a comparison between the general quality of their methods and Gurobi. Further examples are Wang et al. [2023] and Böther et al. [2022] where the authors do occasionally compare to Gurobi in some experiments. However, they do NOT interpret this as an insight on which algorithm is better in general. Similarly, we refrain from drawing such conclusions in our case which is analogous. We hope that the reviewer will base the review on our actual contributions and not on a problematic re-interpretation of our results. **“2. Do you have experiments for Karialas et al.'s work on RB problems?” & “… and Karalias isn't used there, which is essential.” & “You also don't use Karalias as a baseline on RB model problems … Karialias et al. or Sun et al. to be important baselines … ”** We hope the reviewer appreciates the extension of our results that was prompted by the initial review. After we delivered these results which confirm the strong performance of VAG-CO the reviewer now demands further new experiments. Since we are fully committed to convincing the reviewer we ran experiments on RB for Karalias et al. [2020] (EGN) and Sun et al. [2022] (EGN-Anneal). The results show that the former method performs similar to our MFA and the latter is similar to DB-Greedy (Fig. 1, middle). Importantly, both are clearly outperformed by VAG-CO. | p | 0.25 | 0.333 | 0.417 | 0.5 | 0.583 | 0.667 | 0.75 | 0.833 | 0.917 | 1.0 | |------------------|--------|--------|--------|--------|--------|--------|--------|--------|--------|-------| | EGN - AR* | 1.0167 | 1.0171 | 1.0166 | 1.0122 | 1.0115 | 1.0133 | 1.0116 | 1.0105 | 1.0066 | 1.000 | | EGN-Anneal - AR* | 1.0147 | 1.0146 | 1.0123 | 1.0108 | 1.0088 | 1.0095 | 1.0083 | 1.0073 | 1.0042 | 1.000 | | VAG-CO - AR* | 1.0110 | 1.0102 | 1.01 | 1.0077 | 1.0056 | 1.0063 | 1.0051 | 1.0044 | 1.0015 | 1.000 | **“It consistently beat … but not by much. … , it beats them slightly more but not that much better, having an AR difference of around .005 with the second-best method”** Using absolute differences between relative metrics is mis-leading. Even the worst possible MVC assignment on RB-200 would only result in an $AR^*$ optimality gap of .114. Likewise, an improvement of .005 in $AR^*$ represents a reduction of the optimality gap by 32% with respect to the second best method (DB-Greedy/EGN-Anneal). This is by no means a minor improvement. **“It does not beat Gurobi at all on anything besides on hard problem case, as you mentioned.”** We commented on the reviewer’s mis-conception in this point in the answer to “1. Gurobi beats…”. **"Therefore, I struggle to see how this, as an empirical paper, should be accepted if the improvement is marginal on most problem types (including the RB model) and it doesn't beat Gurobi, which is a classic benchline to beat in this literature.”** We discuss the reviewer’s mis-conception in judging the performance gap of VAG-CO in our answer to the statement “It consistently…”. Concerning the problems with the question of whether we “beat” Gurobi, please refer to our answer to “1. Gurobi beats…”. This answer will also clarify that claims of superiority or inferiority of neural CO methods with respect to Gurobi are NOT common in neural CO. Therefore, even IF our results would support the claim that VAG-CO was worse than Gurobi, it would be mis-guided to criticize our work for that. None of the relevant previous works made general claims on their method being a superior algorithm to Gurobi and this question is not directly related to any contribution of our work. Karalias et al. [2020], “Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs”, arXiv:2006.10643 Karalias et al. [2022], “Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions”, arXiv:2208.04055 Sun et al. [2022], “Annealed Training for Combinatorial Optimization on Graphs”, arXiv:2207.11542 Böther et al. [2022], “What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization”, arXiv:2201.10494

Reviewer rhwA2023-08-17

Updated Score

Dear Authors, Thank you for your update. Your results on the RB model over Sun's and Karalias's methods are good to have. While it is my opinion that the empirical benefit is not strong and the variance could have accounted for the minute increases in most cases, the consistent increase over several domains is strong. In my experience, the differences (even given you saying it is 32% of an increase) can be accounted for in the standard deviation of the results. I also have issues with the presentation. I have improved my score to borderline reject and I believe that is fair given my grievances. Thank you.

Authorsrebuttal2023-08-21

**“the empirical benefit is not strong and the variance could have accounted for the minute increases in most cases”** The standard errors over 3 seeds are reported in Tables 2,3, and 4 in the rebuttal file for the real-world datasets. For the $AR^*$ results we utilize the Conditional Expectation (CE) procedure for sampling the learned models for mean-field methods. VAG-CO clearly outperforms these methods just by sampling without requiring any further non-learned algorithmic component like CE. In particular, VAG-CO is significantly the single best method on three data sets. On additional four datasets it is among the best performing methods with one or two other methods. VAG-CO is significantly outperformed on only one dataset. On two datasets more than three methods achieve an $AR^*$ of 1.0 and VAG-CO is always among them. This is a remarkable advancement for this field since it shows that using a sufficiently expressive ansatz mitigates the need for hard-coded heuristics like CE. This aspect is substantiated by the $\hat{AR}$ results which allow us to assess directly the quality of the learned distribution over the solution space. Here VAG-CO is compared to the two strongest mean-field methods (MFA and MFA-Anneal) without CE. VAG-CO is significantly the single best method on eight datasets and is outperformed only once. On one dataset we observed no significant difference between the studied methods. Overall, VAG-CO is clearly the best performing method in these real-world dataset benchmarks from the recent literature. **“the differences (even given you saying it is 32% of an increase) can be accounted for in the standard deviation of the results”** In the following we report the standard errors for the RB results with respect to the solution generation procedure. For all methods we repeated the procedure to obtain $AR^*$ 12-times. For VAG-CO we repeatedly sampled new solutions and for the EGN-based methods we introduce randomness by utilizing random node-features as done in Karalias et al. [2020] and Wang et al. [2023]. The following table reports the average $AR^*$ for the 12 sample generation procedures along with the corresponding standard errors. The large performance advantage (lower is better) of the VAG-CO model is highly significant, in particular, for hard tasks (low $p$). In accordance with the real-world benchmarks, these computationally extensive experiments on hard synthetic CO problems clearly underline that VAG-CO represents an improvement with respect to the state of the art in neural CO. | $p$ | 0.25 | 0.333 | 0.417 | 0.5 | 0.583 | 0.667 | 0.75 | 0.833 | 0.917 | 1.0 | |------------------|---------------------|---------------------|---------------------|---------------------|---------------------|---------------------|---------------------|---------------------|---------------------|----------------| | EGN - $AR^*$ | 1.01771 $\pm$ 0.00010 | 1.01693 $\pm$ 0.00007 | 1.01657 $\pm$ 0.00011 | 1.01278 $\pm$ 0.00010 | 1.01187 $\pm$ 0.00010 | 1.01267 $\pm$ 0.00007 | 1.01216 $\pm$ 0.00009 | 1.01088 $\pm$ 0.00011 | 1.00713 $\pm$ 0.00007 | 1.0000 $\pm$ 0.0 | | EGN-Anneal - $AR^*$ | 1.01480 $\pm$ 0.00006 | 1.01415 $\pm$ 0.00005 | 1.01241 $\pm$ 0.00008 | 1.01028 $\pm$ 0.00010 | 1.00892 $\pm$ 0.00005 | 1.00966 $\pm$ 0.00010 | 1.00858 $\pm$ 0.00005 | 1.00715 $\pm$ 0.00007 | 1.00411 $\pm$ 0.00007 | 1.0000 $\pm$ 0.0 | | VAG-CO - $AR^*$ | 1.01134 $\pm$ 0.00007 | 1.01037 $\pm$ 0.00006 | 1.00941 $\pm$ 0.00007 | 1.00736 $\pm$ 0.00006 | 1.00534 $\pm$ 0.00011 | 1.00551 $\pm$ 0.00009 | 1.00509 $\pm$ 0.00005 | 1.00438 $\pm$ 0.00009 | 1.00152 $\pm$ 0.00005 | 1.0000 $\pm$ 0.0 | **“I also have issues with the presentation.”** As we have demonstrated multiple times above, we are absolutely willing to adapt our work according to the reviewer’s critique. In this case, however, the critique is too vague. Finally, we thank the reviewer for the continuous engagement. We are happy that the reviewer acknowledges that: "the consistent increase over several domains is strong". We hope that our response above eliminates the reviewer’s remaining doubt on the significance of our experimental results in the context of the literature. We stress that besides these strong experimental results, our work encompasses the introduction and demonstration of the graph generation technique Subgraph Tokenization, a statistical learning-theory perspective on variational annealing, and the identification of a limitation inherent to the application of the mean-field ansatz in the recent neural CO literature. Karalias et al. [2020], “Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs”, arXiv:2006.10643 Wang et al. [2023], “Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning”, arXiv:2301.0311

Reviewer fy9s2023-08-11

Thank you for your answer, which alleviates many of my concerns. In particular, I now understand the numerical experiments a bit better. A few minor details: - The comparison between EGN and your MFA might deserve a remark. - Among the slightly confusing notations: $\omega$ as a probability distribution, $\nu_i$ for the graph nodes (instead of just $i$) - On each result plot, please specify whether lower is higher or worse, since it now changes > BFS will typically order the nodes such that the next spins are likely to be directly connected to already generated spins and will typically have several generated spins in their neighborhood. This might be true at first, but as you expand the BFS, the radius gets larger and there is no guarantee that the $i+1$-th node visited comes from the same parent as the $i$-th one. In fact, it might be located in a very different part of the graph. Plus the whole procedure is very dependent on the choice of source. I agree that DFS seems worse but are there other algorithms one might consider?

Authorsrebuttal2023-08-18

Answer to Comment

We thank the reviewer for his prompt response and his follow up suggestions. ### Regarding the minor details: **"The comparison between EGN and your MFA might deserve a remark."** \ We will add a remark to the updated version of our manuscript. **"Among the slightly confusing notations: $\omega$ as a probability distribution, $\nu_i$ for the graph nodes (instead of just $i$ )"** \ We agree that using $\omega$ as a probability distribution may be confusing. Therefore, we will use $q$ instead and clarify in the text that it denotes a probability distribution. Also, we will use $i$ instead of $ \nu_i$ for the graph nodes. **"On each result plot, please specify whether lower is higher or worse, since it now changes"** \ We will specify in each figure whether lower or higher is better. ### Regarding the BFS question: We agree with the reviewer that in BFS, when the radius gets large, the next $k$ spins will very likely not be close to each other. However, we do not see why this should be a problem. It would,indeed, be interesting to investigate this in dedicated experiments. **"I agree that DFS seems worse but are there other algorithms one might consider?"**\ If one wants to have the property that the next $k$ spins have to be close to each other and that already generated spins are also close to these spins, we think the following algorithm could be considered: **Step 1:** select the first of $k$ nodes according to BFS.\ **Step 2:** search and select the $k-1$ unassigned nodes that are the closest (in terms of hop distance) to the first selected node (e.g. with a neighborhood search)\ **Step 3:** generate the spin values selected in Step 1. and Step 2. with Subgraph Tokenization\ **Step 4:** repeat Step 1. until all nodes have assigned spin values

Reviewer fy9s2023-08-11

Congratulations to the authors for the breadth of their numerical experiments, which are more than satisfactory. Indeed, the method as a whole may not be groundbreaking, but the authors are honest about it, and several key components appear quite novel. Besides, the outstanding performance on benchmark datasets deserves recognition. I'm thus raising my review score to 6.

Reviewer ojQm2023-08-18

Thank you for the feedback. I will keep my previous score.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC