acceptodds
Under review as a conference paper at ICLR 2027

Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update

Abstract

Graph neural networks (GNNs) can solve combinatorial optimization (CO) problems in an instance-wise unsupervised way: a fresh network is trained on one instance with a continuous relaxation of the QUBO objective as the loss, with no labels, no pre-training and no training distribution. This regime assumes nothing about the instance and yields a stand-alone heuristic, but it is also the hardest one for a network, and existing methods of this kind (PI-GNN, CRA) are beaten by simple classical heuristics. We show that one change to the training loop closes most of this gap. At every iteration, QRF-GNN feeds the network’s own previous prediction back as a detached dynamic node feature, so each node adapts its de- cision to the current states of its neighbours; the input evolves together with the weights, and training becomes a guided search over binary configurations. We complement the mechanism with a two-branch GraphSAGE block and compact static features. On Max-Cut, Graph Coloring and Maximum Independent Set, QRF-GNN outperforms prior instance-wise unsupervised GNNs by a wide mar- gin, matches or exceeds pre-trained neural solvers evaluated on their own training distributions, and approaches the best dedicated heuristics, on graphs with up to a million nodes. An analysis of the training dynamics shows that the recurrent fea- ture turns a run that freezes early in one configuration into a walk over near-binary configurations that ends in a discrete local optimum.

Primary area:
optimization
Keywords:
Combinatorial Optimization, GNNs, Quadratic Unconstrained Binary Optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_r82cOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1(−1)
Soundness
2(+1)
Read review
Paper summary

The authors propose QRF-GNN, an instance-wise unsupervised CO solver that feeds the previous prediction back as a detached node feature while updating the GNN weights against a relaxed QUBO objective. Combined with a two-branch GraphSAGE architecture, it improves on earlier instance-wise GNNs on Max-Cut, MIS and graph coloring. The paper also studies the resulting search dynamics and includes large sparse-graph experiments.

Critical strengths

Feeding the current prediction back into the network is easy to understand and gives meaningful improvements over PI-GNN and CRA in several settings. The recurrent-feature ablations across GraphSAGE, GCN and GATv2 help isolate its contribution on Max-Cut. The training-dynamics analysis also goes beyond reporting final objectives.

Critical weaknesses
  1. Some implementation details need clarification. Eq. (4) feeds back the previous logits, while Appendix B.1 says the reported variant concatenates logits and probabilities. The implemented relaxation is also unclear: using p⊤Qpp^\top Qp in Eq. (3) and directly relaxing the linear terms in Appendix A give different losses, since pi2≠pip_i^2\neq p_i before saturation. For MIS, the penalty schedule and thresholding alone do not establish that every reported set is feasible.

  2. Some performance claims do not match the tables. Section 5.2 says QRF-GNN is within 0.5% of RLSA on ER-[700–800], but Table 1b gives 42.8 vs 44.10, i.e. roughly a 2.95% relative shortfall. The same paragraph says it beats every amortised learning baseline, although DiffUCO, RLNN and X²GNN report 43.63, 43.34 and 44.91. These are material differences in how the results are positioned.

  3. Runtime and reporting protocols are not sufficiently aligned. The baseline sources are disclosed, which I appreciate, but converting published times to total test-set time does not make different hardware, implementations and restart budgets directly comparable. Table 1 lacks seed-level uncertainty and explicit QRF-GNN restart counts, although other tables do report std. The same-code comparison in Appendix C.3 is helpful, but only covers G14. Tables 2 and 6 also give different QRF-GNN results for the same Gset instances, e.g. 9559 vs 9548 on G70.

  4. The million-node experiment is useful, so scale itself is not missing. However, it uses fixed-degree sparse Max-Cut graphs. Appendix C.1 reports that the P-value drops from about 0.735 to 0.722 as size grows, while the best solution is found increasingly close to the iteration cap. Near-linear cost under a fixed cap therefore does not establish near-linear time to a comparable solution quality.

  5. Applicability beyond compact graph QUBOs remains open. Max-Cut, MIS and coloring provide useful coverage, but all have fairly direct graph-based formulations. The paper acknowledges the need for compact, well-scaled QUBOs, which is an important restriction. Capacity, assignment or scheduling constraints can introduce extra variables, stronger penalties and denser interactions. Avoiding pre-training does not by itself establish broad applicability. Can the framework handle a qualitatively different constrained problem, e.g. KP or JSSP, or a routing formulation such as TSP/CVRP? Even one additional experiment would help. Otherwise, please explain the expected variable/edge expansion, penalty selection and feasibility handling, and state the practical scope more concretely.

  6. Recent graph-CO work is under-covered. DiffUCO and X²GNN are already included, but relevant recent methods such as DIMES, Meta-EGN, VAG-CO, COExpander, M²GenCO, GenSCO, NExCO, etc., are missing from the comparison or discussion. Their training regimes differ from QRF-GNN, but that calls for careful positioning rather than leaving them out, especially where they share MIS or Max-Cut benchmarks. The distinction from solution-conditioned refinement and iterative search could also be clearer.

Questions for authors

see weaknesses.

Reviewer_UohVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies learning-based heuristics for combinatorial optimization in an instance-wise unsupervised setting, where a randomly initialized network is trained on each instance using a relaxed Quadratic Unconstrained Binary Optimization (QUBO) objective as the loss function without requiring any labels or pretraining. The authors introduce QUBO-based GNN with Recurrent Feature (QRF-GNN), which changes the training procedure by using the previous iteration’s solution to derive input features for the next iteration, allowing the input to evolve alongside the network weights. They claim this formulation turns training into a guided search over binary variables. The authors initialize QRF-GNN with a two-branch GraphSAGE block with parallel mean and max aggregation scheme, and test QRF-GNN on Maximum Cut, Graph Coloring, and Maximum Independent Set problems. The experimental results show that QRF-GNN substantially outperforms prior instance-wise unsupervised GNNs and is competitive with pretrained learning-based heuristics evaluated on their own training distributions. The authors’ analysis of training dynamic reveals that recurrent features help with premature convergence and allow the network to explore near-binary solutions.

Critical strengths
  1. The idea behind the proposed method is clear and well-motivated.
  2. The evaluation spans multiple tasks and against quite a few methods, and demonstrates competitiveness of the proposed method.
  3. Section 6 is particularly an interesting read. It provides explanation for the advantage of the proposed method. The rounded solution ablation is interesting as it shows how going from discrete to continuous features help with leaving local optima.
Critical weaknesses

The recurrent feature (RF) mechanism is the key component of QRF-GNN, and it also involves a dropout step that controls how much of the solution is preserved. This ratio can have a large impact, setting it to 1 would be like disabling RF, while setting it to 0 would disable random perturbation without disabling RF. Currently, the contributions of the RF mechanism and dropout are entangled. My concern is that disabling dropout in the RF could have a similar impact to disabling RF. An experiment disabling only RF dropout would help separate individual contributions of recurrent features and dropout. Similarly, QRF-GNN’s sensitivity to this dropout ratio hyperparameter is not measured. Other dropout ratios such as 0.2 and 0.8 might lead to different training and learning dynamics and might impact the final performance. Its impact across problems is not clear. An experiment comparing dropout ratios of 0.0 (disabling), 0.2, 0.5 (current, control), and 0.8 values for each problem would help with this weakness.

The recurrent feature update mechanism is similar to AnyCSP’s recurrent states and X2GNN’s stochastic refinement mechanism. Both approaches rely on the previous iteration’s output to derive input features for the next iteration. In the former, node features are recurrently used, and in the latter, the predicted soft solution is randomly perturbed by setting some variables to 0 while keeping the rest as they are. The paper cites AnyCSP and X2GNN and compares against them on multiple benchmarks, but it does not discuss the similarities and differences between the mechanisms. A short comparison of the proposed mechanism to the related work would make the connection clearer.

More generally, the presented results could have been described more carefully to avoid overclaim. The abstract claims that the advantages of the method hold up “on graphs with up to a million nodes”. However, the main paper does not seem to support this claim at all and I found something related in the appendix but it seems to only provide results on QRF-GNN at this scale. It is unclear how the baselines perform at this scale and if the advantages still hold. The evaluation at that scale is also very thin: only on 20 random 5-regular graphs. The abstract should not include an important claim like this that is not supported by results.

In general, since the performance results reported in Table 1 are quite close, confidence interval would add strength to the author’s claim.

Questions for authors

Could the authors explain the impact of dropout ratio at the recurrent feature mechanism? Is QRF-GNN sensitive to the dropout ratio? Do you use 0.5 for all three problems?

Could you please describe the differences between the proposed recurrent feature update mechanism and the AnyCSP’s recurrent states mechanism and X2GNN’s stochastic refinement mechanism?

Could the authors clarify which problem is used for Figure 5? Also the P-value is defined later but used to describe Figure 5.

Reviewer_SP6COpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors propose QRF-GNN, a framework for instance-wise unsupervised QUBO optimization to solve graph-based combinatorial optimization problems. The approach is instance-wise, i.e., a fresh Graph Neural Network is trained from scratch on each problem instance. The main contribution is the introduction of a recurrent-feature mechanism, in which, for each node, the output of the previous optimization iteration is fed as a dynamic input feature for that node (with stop-gradient to avoid backpropagation through iterations). This feedback is meant to augment static node features and help the model avoid early convergence and escape local optima. The authors also propose and leverage a two-branch layer architecture inspired by the Inception module. However, while this appears novel in the context of instance-wise QUBO-based approaches, recurrent and dynamical features are already established in the broader GNN literature (see, e.g., [1,2,3] below). The authors evaluate the approach against classical, heuristic and learning-based solvers on three NP-hard problems (i.e., Max-Cut, Graph Coloring, and Maximum Independent Set), with mixed results.

[1]: Jiaxuan You, Tianyu Du, and Jure Leskovec. 2022. ROLAND: Graph Learning Framework for Dynamic Graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '22). Association for Computing Machinery, New York, NY, USA, 2358–2366. https://doi.org/10.1145/3534678.3539300 [2]: Chengxi Zang and Fei Wang. 2020. Neural Dynamics on Complex Networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '20). Association for Computing Machinery, New York, NY, USA, 892–902. https://doi.org/10.1145/3394486.3403132 [3]: Rossi E, Chamberlain B, Frasca F, Eynard D, Monti F, Bronstein M. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637. 2020 Jun 18.

Critical strengths

None. Although the intuition behind the introduction of dynamic node features is simple and intuitive, I do not consider it a critical strength supporting acceptance because the advancement is incremental and the empirical evaluation on three NP-hard problems shows mixed performance, including against other learning-based approaches in some settings. Moreover, parts of the experimental setting remain unclear, and some of the claims are only partially supported by data as detailed below.

Critical weaknesses

My main concerns relate to the mixed results achieved and the interpretations and analysis of the impact of the recurrent features.

I must be honest: while the paper is generally easy to read, Section 6 and the SI are utterly compressed with information and conclusions that are not clearly rooted in the data, and some appear stronger than the available data allow. Also, some terms are introduced but only later formalized in the SI, like “near-binary” that, while intuitive, is operationally defined in terms of saturation only there. This makes the paper harder to follow and the conclusions harder to verify.

The presented analysis – performed on 7 Gset network instances – suggest but not fully establish that the recurrent features induce trajectories that constitute the claimed guided search (“per-instance training [turned] into a guided search over binary configurations”).

  • “the visited bitstrings keep near-best cut quality at Hamming distances of several hundred [over 800] from the current best” is actually supported by the experiments, but “the recurrent feature turns training from a local descent that stops early into a persistent walk through high-quality solutions” is stretched: after zooming a lot into Fig 4a and the first column of subfigures of Fig 7, what I can tell is that the training reaches better solutions very early (first epochs already) and that the trajectories exhibit larger fluctuations. Have the authors tried to replace the recurrent features with random values of the same dimension or constant ones (e.g., zeros or ones)? Furthermore, the plot of the two shared principal components shows greater variability along those two directions, not over all directions, and is fairly hard to interpret. The Hamming distance, on the other hand, is only reported with respect to the best solution and tells little about the pairwise distance of the intermediate ones.
  • Lines 415-417: “The […] Figure 7 shows the gain in two regimes, broad exploration or early lock-on to a high-quality basin”: doesn’t the early lock-on regime contradict the claimed broad guided exploration and the claimed avoidance of premature convergence to local optima? From the abstract “turns a run that freezes early in one configuration into a walk…”
  • “how local optima are left”:
    • “the logit margin is an accumulator”: accumulator of what exactly? A local combinatorial state of the nodes? What’s the evidence supporting this sentence?
    • “Its logits carry not only the current assignment of each node but also how strongly the node holds it”: to my understanding, the larger the logit margin from the binary decision threshold, the “stronger” the node holds its assignment. “Nodes that are about to flip lose most of their margin in the preceding iterations” but isn’t it expected, considering that the farther the logit is from the binary threshold, the “stronger” its assignment, and that nodes’ logits evolve through iterative gradient-based optimization? Could part of this behaviour simply be the effect of the learning rate and of the optimizer, rather than evidence supporting an “accumulation” mechanism?
    • “and its flips are indistinguishable from noise.” What’s the noise model used here?
    • Figure 3b doesn’t show a “without rec” curve but instead QRF with graded and discrete feedback, PI-GNN (the flat curve at 0.98) and the population mean. It is unclear to me if PI-GNN is supposed to correspond to the “without rec” variant. Moreover, the event counts are dramatically different (79k, 400, and 150k respectively)
    • The detailed analysis of the margin dynamics is performed only on two Max-Cut instances (G14 and G22, although only G14 is shown) but the resulting interpretation is generalized as a behaviour of the approach, which is not supported by data
  • “The resulting moves are coordinated rather than random” and, later in the SI “With logit feedback, 20% of the iterations contain a multi-node move whose gain exceeds the best single flip available from the previous state, and the flipped nodes are 1.3×more connected to each other than random node sets of the same size (0.8×for the non-recurrent variant, whose rounded output changes at every iteration).” How many multi-node moves are observed, how is “a multi-node move” defined and how many nodes are affected? How many random combinations are sampled, and according to which null model? Isn’t it expected that a node’s embedding influences those of its neighbours through message passing? Also, do the authors compare this 20% fraction to the one obtained with the “without rec” variant? How many iterations in the non-recurrent variant contain a multi-node flip? Is this difference (recurrent vs non recurrent variants) statistically significant?
  • The authors claim that “static node features […] can cause the model to become biased […] and face ambiguity issues”. Yet, properly chosen static node features – together with message passing performing local aggregation – can greatly enhance the solution quality
  • In this regard, PageRank is the only topological feature considered and ablated (along with the embedding and the random ones, lines 1369-1372) as a static node feature. However, this feature strongly correlates to degree in undirected unweighted networks. Why this choice? Have the authors considered other topological features?

Evaluation settings and mixed results: On the Max-Cut task, QRF-GNN outperforms the other instance-wise algorithms and is faster than the pre-trained unsupervised ones (excluding the ones providing lower quality solutions), but trails behind two H and OR methods in Table 1A on small instances. On large instances, it provides better solutions than all reported H or OR methods while being faster than all but one (EO) and returning slightly worse sizes than the other ULs. Moreover, on the representative Gset subset (Table 2), the best QRF-GNN run produces suboptimal results in most rows, with two ties and an improvement over the reported heuristics. Regarding the second task, Maximum Independent Set, I really appreciate that the authors report the results in the main paper and do not relegate them to the SI. However, I must note that heuristic solvers often provide larger set sizes and way faster runtimes on smaller ER instances (e.g., RLSA scores 44.10 in 20s), while QRF-GNN outperforms all other reported approaches except KaMIS (but QRF is way faster) on larger instances. I also do not understand how the authors ensure the feasibility of the binarized solutions in MIS.

Graph coloring results (Supplementary Tables 11 and 12) only compare against a single dedicated heuristic (which achieves the same solution quality except for instances “Qween11-11” and “Qween13-13” in the k = \chi setting).

Questions for authors
  • A dropout probability of 50% is applied to the output of the first parallel block ht+1,1h^{t+1,1}. Why? How much does the introduced noise affect the search? Could it partially explain the exploration? I cannot find any ablation of this parameter
  • Can the authors provide more a more systematic analysis of the search space to support their claims? Does the proposed mechanism hold on other instances and tasks? I’m not asking for a visual analysis such as the one shown in Figures 3 and 7, but rather a statistical comparison between the two variants (with and without recurrent features) across the three tasks and datasets
  • Why isn’t the experimental protocol uniform (lines 355-358), particularly regarding the number of seeds and best-of-N?
  • Could the authors compare against other solvers for graph colouring?
  • How is the feasibility of the final MIS solutions checked?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.