- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes ALON, an unsupervised neural solver for minimum vertex cover. It adds multiplier feedback to a continuous relaxation and stores the multipliers at nodes rather than edges. The analysis explains a limitation of squared penalties near discrete covers. Experiments compare ALON with neural baselines, alternative feedback schemes, and classical solvers.
Critical strengths
-
The paper explains why a squared penalty can fail to prevent the model from moving away from a valid cover, and how added feedback can help.
-
A controlled experiment shows that the feedback improves cover size and reduces constraint violations. The paper also compares storing feedback at nodes with storing it at edges.
Critical weaknesses
The method does not perform better than strong classical solvers
The appendix shows that NuMVC and FastVC reach the same solution quality faster and find equal or smaller covers on 18 of 19 datasets. The large speedup reported in the paper is against directly solving the continuous relaxation, rather than these competitive algorithms.
It is unclear whether the theory explains the improvements in practice. The analysis studies embeddings near discrete covers, but the paper does not show that training operates in this regime.
The feedback is also removed at inference. Finally, storing fewer multipliers does not necessarily save much total memory, since edge-gradient computations remain the main cost.
Questions for authors
- When would ALON be a better choice than NuMVC or FastVC?
- Do measurements during training support the mechanism described in Theorem 4.1?
- Does the controlled feedback experiment show similar improvements on ER and hard RB graphs?
- How much total training memory does node-level feedback save?
5 comments
Part 2/2
Q2 (continued). Why does the benefit remain at zero-multiplier inference?
-
All four controlled variants use zero multipliers at inference. Architecture, parameter count, training budget, and decoding are matched. On all 200 WS test graphs and three training seeds:
Feedback during training Feasible cover size ↓ Pre-repair feasibility ↑ Neither pathway 90.998 ± 0.080 10.5% Loss only 91.258 ± 0.147 94.8% Features only 91.828 ± 0.260 28.2% Both pathways 90.378 ± 0.108 99.8% The benefit remains in the trained network parameters. Loss feedback adds to the parameter gradient. Feedback features change the layer inputs and subsequent parameter updates. Inference uses the resulting parameters with the temporary multipliers set to zero. Section 3.4 now explains this distinction.
Loss feedback alone substantially improves feasibility. Using both pathways improves feasibility by 89.3 percentage points and reduces mean cover size by 0.620 vertices relative to neither pathway, with smaller covers in all three paired seeds. Thus the joint training intervention improves the final predictions even after feedback is removed at inference. Appendix D.1, Table 13, reports this control.
Q3. Does the controlled feedback experiment show similar improvements on ER and hard RB graphs?
-
The ER means improve; the hard RB200 mean increases under the tested configuration. Within each setting, architecture, parameter count, training budget, and decoder are held fixed; both feedback pathways are enabled or disabled together. Every variant uses zero multipliers at inference. WS and ER use 200 epochs, and RB200 uses 1000, with three paired seeds:
Dataset (test graphs) Both off: cover size ↓ Both on: cover size ↓ Improving paired seeds WS [50,100] (200) 45.700 ± 0.013 45.632 ± 0.124 2/3 WS [100,200] (200) 90.895 ± 0.066 90.430 ± 0.200 3/3 ER [50,100] (200) 55.373 ± 0.406 55.103 ± 0.495 2/3 ER [100,200] (200) 137.477 ± 0.696 137.410 ± 0.171 2/3 RB200 (100) 152.203 ± 0.835 154.630 ± 0.781 1/3 -
The ER improvements are 0.270 and 0.067 vertices, respectively; RB200 increases by 2.427. In the accompanying WS [100,200] control, mean cover size decreases from 90.895 to 90.430, with improvement in all three paired seeds. These comparisons keep the architecture fixed and measure the effect of enabling feedback in each setting.
-
Appendix D.1, Table 14, reports all five settings, with a reference in Section 5.3. The separate four-pathway control in Table 13 shows that joint loss and feature feedback improves both quality and feasibility on WS. The cross-family table above establishes where the mean quality improvement holds under the tested configurations.
Q4. How much total training memory does node-level feedback save?
-
Paired measurements show approximately 1.48%–11.32% lower total peak training memory, including edge-gradient computations. The largest absolute saving is 339.15 MiB:
Dataset Node feedback (MiB) ↓ Edge feedback (MiB) ↓ WS [100,200] 106.06 109.00 ER [100,200] 378.82 416.76 ER [400,500] 2657.59 2996.74 RB200 3635.78 3690.32 -
Each pair uses the same full training split, batch order, architecture, FP32 precision, Adam optimizer, and full-dataset state cache. After five warm-up steps, memory is measured over all batches in two complete epochs. Appendix D.4, Table 18, reports the totals and this protocol.
-
Node feedback reduces multiplier storage from to . Both variants retain the edge-gradient intermediates, which are included in the measurements above. Section 5.3 now distinguishes the multiplier-state reduction from the measured saving in total training memory.
References
[1] Garmendia, A. I., Ceberio, J., and Mendiburu, A. (2024). Applicability of Neural Combinatorial Optimization: A Critical View. ACM Transactions on Evolutionary Learning and Optimization, 4(3), Article 15.
[2] Li, J., Chen, W., and Guo, M. (2025). Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization. arXiv:2511.19573.
[3] Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., and Song, L. (2017). Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS.
Thank you again for your helpful feedback. As the discussion period draws to a close, we would appreciate your thoughts on our additional time–quality comparisons, controlled feedback experiments, and total training-memory measurements. We have also clarified the settings in which ALON offers a useful trade-off. Could you let us know whether these responses address your main concerns, or whether any remaining issues affect your overall assessment? We would be happy to provide further clarification.
Part 1/2
Thank you for recognizing the penalty analysis and feedback control.
Q1. When would ALON be a better choice than NuMVC or FastVC?
For a trained model, the additional comparison shows a useful trade-off between return time and cover size. On PROTEINS and WS [50,100], ALON records shorter mean times, with small differences in mean feasible cover size:
In this additional protocol, classical search stops when it reaches that graph's ALON cover size or detects expiry of the requested 100 ms limit. Each solver uses three seeds per graph and three repetitions per seed. The table reports the recorded test-time means for this protocol.
These results support using ALON when a trained model is available and rapid return of a high-quality feasible cover is the priority. The mean cover differences are 0.08/0.11 vertices on PROTEINS and 0.13/0.06 on WS relative to FastVC/NuMVC, respectively. Learning a reusable solution policy for recurring graph problems is a motivation of neural combinatorial optimization [3]. Evaluation should consider quality, computation, and reuse together [1]; learning combined with graph structure is also studied in [2].
The original classical comparison and the additional target-stopping experiment use different protocols. The former reports equal or smaller classical covers on 18 of 19 datasets; the latter reports the trade-off above on two test sets. The large speedup in Section 5.3 and Appendix C.8 concerns direct solving of the continuous relaxation.
Q2. Do training measurements support the mechanism, including zero-multiplier inference?
Training diagnostics support relevance to the near-discrete regime. In a separate RB200 experiment, the embedding-gradient norm ϵ/n decreases from 13.778 to 0.103, edge residual ∥g∥1/m from 0.279 to 0.000512, and polarization defect P/(2m) from 0.193 to 0.00244. Each quantity is normalized per graph and averaged over training graphs and three seeds. The latter two decreases show outputs approaching discrete directions and edge feasibility (Appendix D.2).
Learned feedback increases directional curvature at actual training outputs. We hold each output fixed and remove or retain only its linear feedback term. Along a tangent direction that decreases the cover objective, the results are:
The increment is also positive at every evaluated state along two fixed random tangent directions. Appendix D.2, Table 15, reports all three directions. These measurements establish increased curvature along the tested directions at the network's continuous outputs.
The learned multipliers satisfy the explicit restoring threshold at many vertices. At feasible discrete reference covers, we retain the learned multipliers and test Di>wi/4, where Di=∑j∈N(i)∖C(μi+μj). Selected-vertex fractions are averaged equally over graphs and then over three seeds:
Here an essential selected vertex has an unselected neighbor in the reference cover; pp denotes percentage points. This evaluates the theorem's condition at reference covers, alongside the continuous-output measurements above.