- 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
-
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 in Eq. (3) and directly relaxing the linear terms in Appendix A give different losses, since before saturation. For MIS, the penalty schedule and thresholding alone do not establish that every reported set is feasible.
-
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.
-
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.
-
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.
-
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.
-
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.