acceptodds
Under review as a conference paper at ICLR 2027

Augmented Lagrangian Optimization Neural Network for Minimum Vertex Cover

Abstract

Unsupervised neural solvers for minimum vertex cover (MVC) use continuous penalties to learn small feasible covers. We identify a geometric mismatch in the spherical MVC relaxation: rotating a selected vertex from a discrete cover decreases the objective at second order, while a squared edge penalty responds only at fourth order. Linear feedback acts at second order and can reverse this directional curvature. Guided by this distinction, we introduce ALON, an Augmented Lagrangian Optimization Neural Network combining gradient-based message passing, projected node feedback, and an edge-wise penalty. Node states reduce multiplier storage from edges to vertices. We quantify the information lost by this compression, bound edge violations as embeddings become discrete, and derive conditional feasibility and first-order residual bounds for projected updates. Across 19 datasets, the +AL configurations improve cover quality in 70 of 76 backbone–dataset pairs and tie three more. ALON attains the best printed neural mean on 16 of the 19 datasets, and amortized inference is about three orders of magnitude faster than a direct solve of the same relaxation on the WS split.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Unsupervised Learning, Graph Neural Networks, Minimum Vertex Cover, Augmented Lagrangian Methods

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_KzjuOpenReview ↗
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
  1. 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.

  2. 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
  1. When would ALON be a better choice than NuMVC or FastVC?
  2. Do measurements during training support the mechanism described in Theorem 4.1?
  3. Does the controlled feedback experiment show similar improvements on ER and hard RB graphs?
  4. How much total training memory does node-level feedback save?
5 comments

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?

  1. 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:

    Dataset (test graphs)MethodMean feasible cover size ↓Recorded mean time (ms/graph) ↓
    PROTEINS (112)ALON25.090.463
    PROTEINS (112)FastVC25.014.273
    PROTEINS (112)NuMVC24.981.992
    WS [50,100] (200)ALON45.600.717
    WS [50,100] (200)FastVC45.471.598
    WS [50,100] (200)NuMVC45.546.842

    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.

  2. 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].

  3. 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?

  1. Training diagnostics support relevance to the near-discrete regime. In a separate RB200 experiment, the embedding-gradient norm ϵ/n\epsilon/\sqrt n decreases from 13.778 to 0.103, edge residual ∥g∥1/m\|g\|_1/m from 0.279 to 0.000512, and polarization defect P/(2m)\mathcal 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).

  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:

    DatasetTraining graphs × seedsFeedback removed → retainedPositive increment / states
    WS1600 × 314.816 → 15.5284800/4800
    MUTAG150 × 31.889 → 2.681450/450
    ENZYMES480 × 35.037 → 5.7581440/1440

    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.

  3. 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/4D_i>w_i/4, where Di=∑j∈N(i)∖C(μi+μj)D_i=\sum_{j\in\mathcal N(i)\setminus C}(\mu_i+\mu_j). Selected-vertex fractions are averaged equally over graphs and then over three seeds:

    DatasetSelected vertices satisfying the thresholdEssential selected vertices satisfying the threshold
    WS67.8% ± 0.21 pp68.4%
    MUTAG83.4% ± 8.32 pp83.4%
    ENZYMES83.5% ± 1.04 pp83.5%

    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.

Part 2/2

Q2 (continued). Why does the benefit remain at zero-multiplier inference?

  1. 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 trainingFeasible cover size ↓Pre-repair feasibility ↑
    Neither pathway90.998 ± 0.08010.5%
    Loss only91.258 ± 0.14794.8%
    Features only91.828 ± 0.26028.2%
    Both pathways90.378 ± 0.10899.8%

    The benefit remains in the trained network parameters. Loss feedback adds ∑iμi∇θci(Vθ)\sum_i\mu_i\nabla_\theta c_i(V_\theta) 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?

  1. 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.01345.632 ± 0.1242/3
    WS [100,200] (200)90.895 ± 0.06690.430 ± 0.2003/3
    ER [50,100] (200)55.373 ± 0.40655.103 ± 0.4952/3
    ER [100,200] (200)137.477 ± 0.696137.410 ± 0.1712/3
    RB200 (100)152.203 ± 0.835154.630 ± 0.7811/3
  2. 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.

  3. 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?

  1. 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:

    DatasetNode feedback (MiB) ↓Edge feedback (MiB) ↓
    WS [100,200]106.06109.00
    ER [100,200]378.82416.76
    ER [400,500]2657.592996.74
    RB2003635.783690.32
  2. 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.

  3. Node feedback reduces multiplier storage from O(m)O(m) to O(n)O(n). Both variants retain the O(Lmd)O(Lmd) 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.

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

This paper proposes ALON, a neural network solver for the Minimum Vertex Cover (MVC) problem. The method builds on a spherical Burer–Monteiro relaxation and introduces node-level projected feedback alongside edge-wise squared penalties. The core motivation is that, near a discrete feasible cover, rotating a selected vertex away from its discrete position leads to a second-order decrease in the objective, while the squared edge-constraint penalty only responds at fourth order. Therefore, simply increasing a fixed penalty coefficient cannot change this local geometric relationship. ALON uses node multipliers to approximate edge multipliers, reducing the storage requirement for feedback states from scaling with the number of edges to scaling with the number of vertices, while retaining edge-wise squared penalties to detect constraint violations.

The paper also presents an exact feedback identity along local rotation directions, a compression error bound relating node residuals to edge residuals, conditional feasibility and first-order residual bounds under projected feedback, and output certificates based on SDP dual relaxation. The experiments cover 19 datasets and four GNN backbones, including weighted MVC, out-of-distribution evaluation, comparisons between node-level and edge-level feedback, and runtime comparisons against directly solving the continuous relaxation.


Post rebuttal update:

The authors' rebuttal gives substantive response to previous questions. Q1 and Q4 are partly resolved, Q2 and Q3 are resolved. For Q1 and Q4: (i) The RB200 inversion, with a hypothesis and, if possible, a diagnostic; (ii) scope limited to the four synthetic families and TU-small, since the hard instances are where the method does not lead.

This reviewer is going to increase the score given the authors rebuttal responses.

Critical strengths

The paper provides a reasonably clear local geometric motivation, and the node-level feedback mechanism has a degree of novelty. The theoretical analysis and experimental evaluation also form a relatively complete technical narrative.

Through local rotation analysis, the paper explains the difference in curvature between linear feedback and squared penalties, while also discussing the potential information loss caused by aggregating edge residuals at the node level. These analyses offer useful insights into the role of constraint feedback in neural combinatorial optimization.

In addition, the authors discuss the limitations of their method fairly thoroughly, including the fact that the theoretical results do not guarantee convergence of network parameter training, that nonnegative node multipliers can only represent a restricted space of edge multipliers, and that classical local search methods still have advantages in runtime and solution quality.

Critical weaknesses

Although the experimental results generally support the effectiveness of introducing node-level feedback, the respective contributions of augmented feedback and the dedicated network design have not been fully disentangled. Meanwhile, the theoretical results mainly depend on given optimization trajectories and residual conditions, and their connection to the actual training process could be made clearer. The applicability of compressed node-level feedback also deserves further discussion.

  1. The contribution of augmented feedback itself needs to be further isolated One of the main contributions of the paper is improving neural MVC solvers through node-level augmented feedback. The Raw/+AL comparisons across four GNN backbones in Table 1 do show that introducing augmented feedback generally improves solution quality. This provides relatively broad experimental support for the effectiveness of the method.

However, for the specifically designed ALON architecture, its improvements over methods such as OptGNN may still be influenced by several factors simultaneously, including the construction of gradient features, normalization strategies, network update layers, and the augmented feedback mechanism. Therefore, the current results do not fully establish how much each design component contributes to the performance improvements.

Appendix A already provides a valuable WS matched ablation. With the same backbone, number of layers, embedding dimension, training budget, and decoding procedure, adding dual feedback reduces the average repaired cover size from 91.090 to 90.428, while the pre-repair infeasibility rate decreases from 89.5% to 0.83%. This experiment provides good evidence for the independent contribution of dual feedback in this setting, and it deserves more emphasis in the main text.

Nevertheless, this strictly controlled experiment is mainly conducted on the WS setting. Considering that different graph families may vary considerably in topology, constraint density, and optimization difficulty, this reviewer would like to know whether similar matched ablations also hold across other graph families.

For example, it would be useful to further compare variants that only modify the network architecture, only introduce dual feedback, and use the full ALON model, while keeping network capacity, training budget, and decoding procedures consistent. This could help clarify whether ALON's performance improvements mainly come from the augmented feedback mechanism or from the combined effects of multiple architectural designs.

The current experiments provide evidence for the feedback mechanism, especially the Raw/+AL comparisons across different backbones. However, for the dedicated ALON architecture, strictly controlled experiments across different graph families are still lacking. Therefore, there still is room to better distinguish the respective contributions of its architectural design and feedback mechanism.

  1. The connection between the theoretical analysis and the actual training process needs further clarification Theorems B.1/B.2 analyze a process in which projected feedback updates are performed based on the node residuals of the current output. In Algorithm 1, however, the training procedure iterates over multiple batches within an epoch, accumulates the residuals from the corresponding outputs into C_acc, and then performs a projected update when the feedback update is due.

The appendix already explains that residuals are cached on a per-graph basis and that the theoretical analysis can be applied according to the feedback update times of individual training graphs. Therefore, this reviewer does not consider this an obvious theoretical error. However, the current description still does not fully clarify the correspondence between the actual grouped update and the theoretical recurrence.

The authors could further clarify how residuals are accumulated in Algorithm 1, particularly whether C_acc is maintained independently for each graph and whether each graph contributes only one output during a feedback update cycle. If each graph contributes only one residual, then the actual update can be directly related to the recurrence in Theorems B.1/B.2. If multiple outputs are accumulated, this revierer would appreciate a clearer explanation of the aggregation and normalization procedures, as well as how the resulting update is mapped to the theoretical analysis. Since the appendix already partially explains the mechanism for maintaining graph-specific multiplier states, this reviewer thinks this is mainly an issue of implementation clarity and the correspondence between theory and practice.

In addition, Table 5 provides an expression for the feedback step size, but the paper does not sufficiently explain the specific values or schedule of a_t, or the precise definition of N_b. For example, does N_b refer to the number of batches in each epoch, or the number of effective accumulation steps within a feedback update cycle? How is the feedback step size normalized when the batch size changes? Given that the strength of dual feedback directly affects the optimization process, these details are important for understanding the method and reproducing the experiments.

This reviewer also has a question about the relationship between the theoretical analysis and the actual network updates. The paper's local geometric analysis uses Riemannian gradients on the spherical manifold, while Eq. (12) uses Euclidean gradients to construct directional features, followed by a learnable mapping and spherical normalization to update the node representations.

This reviewer understands that the authors do not claim Eq. (12) to be a strict Riemannian gradient descent step, and Appendix B.8 also discusses the relationship between parameter gradients and embedding stationarity. However, the local curvature analysis mainly describes the geometric properties of the continuous optimization objective, while the actual network updates are also influenced by learnable transformations. Therefore, the authors could further clarify to what extent these local geometric properties can explain the observed network training behavior, and whether there are corresponding experimental diagnostics supporting this connection.

  1. The applicability of node multiplier compression deserves further discussion ALON adopts a restricted node-multiplier parameterization. This design reduces the multiplier state from the edge level to the node level and makes it easier to integrate with GNN node representations. However, it is not equivalent to the unrestricted per-edge equality-constraint multipliers used in standard augmented Lagrangian methods.

The paper already acknowledges this limitation fairly clearly. Theorem 4.2 establishes a relationship between edge residuals and node residuals, and shows that the extent to which node residuals can control actual edge-constraint violations is related to the polarization defect. Proposition 9 also shows that, even on relatively simple graphs, nonnegative node multipliers may fail to stabilize certain discrete optimal covers. These theoretical analyses are strengths of the paper. However, the current experiments mainly compare node-level and edge-level feedback through the final cover quality, without sufficiently demonstrating how much these theoretical limitations affect the actual training process.

For example, reporting the evolution of node residuals, edge-wise constraint residuals, polarization defect, and multiplier magnitudes during training could provide more direct insights into the relationship between node residuals and actual edge residuals, as well as whether the model gradually moves toward regions with smaller polarization defects.

The paper has already compared node-level and edge-level feedback on WS and PROTEINS, and these results support the effectiveness of node compression in the tested settings. Is this advantage depends on particular graph structures or embedding distributions.

In particular, would residual cancellation and the limited expressive capacity of node multipliers become more significant on graph families with different cycle structures, edge densities, or constraint complexities? This could help explain why node-level feedback performs well in some settings and under what circumstances it may be less effective than full edge-level feedback.

Questions for authors

Regarding mechanism attribution: The WS matched ablation in Appendix A already provides valuable evidence for the independent contribution of dual feedback. Have the authors observed similar results on other graph families or at different graph scales? If the ALON network architecture, parameter count, and training budget are kept unchanged, does disabling only dual feedback lead to consistent performance changes?

Regarding grouped updates: How exactly is C_acc maintained and normalized for each graph in Algorithm 1? When multiple outputs are involved in a feedback update cycle, how does the actual update correspond to the recurrence analyzed in Theorems B.1/B.2? In addition, what are the precise definitions and schedules of a_t and N_b in Table 5?

Regarding the correspondence between theory and implementation: Eq. (12) uses Euclidean gradients to construct network features, while the theoretical analysis mainly relies on gradients and local curvature on the manifold. How do the authors interpret the connection between the two? To what extent can these theoretical results explain the actual learned update behavior?

Regarding the applicability of node compression: Have the polarization defect and node residuals in Theorem 4.2 been monitored during training? Have the authors observed significant residual cancellation across different graph families? Can these quantities help explain the performance differences between node-level and edge-level feedback in the experiments?

4 comments

Part 1/2

Thank you for your assessment. We address attribution and grouped updates here; Part 2 covers geometry, compression, and references.

Q1. Feedback attribution across graph families

  1. The additional comparisons isolate feedback within a fixed ALON architecture. 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.01345.632 ± 0.1242/3
    WS [100,200] (200)90.895 ± 0.06690.430 ± 0.2003/3
    ER [50,100] (200)55.373 ± 0.40655.103 ± 0.4952/3
    ER [100,200] (200)137.477 ± 0.696137.410 ± 0.1712/3
    RB200 (100)152.203 ± 0.835154.630 ± 0.7811/3
  2. Mean cover size improves in all four WS/ER settings and increases by 2.427 on RB200. These fixed-architecture pairs isolate feedback; the original Raw/+AL comparisons across four backbones provide broader evidence.

  3. Section 5.3 points to Appendix D.1, Table 14. These are separate runs from Appendix A and the four-pathway control (Table 13), where joint feedback improves WS quality and feasibility.

Q2. How are cached residuals and step sizes mapped to the theoretical recurrence?

  1. In T1, each graph contributes one residual to its own cache entry per epoch. Let IqI_q be graph qq's disjoint global node-index range. At the start of each epoch the cache is cleared and multipliers are retained. The batch forward pass produces V^q,t\widehat V_{q,t}. Before Adam updates the parameters, we store its signed residual:

    +\operatorname{stopgrad}\bigl(c_q(\widehat V_{q,t})\bigr).$$ Each graph is visited once, so its cache equals that residual at the T1 feedback update. Different graphs occupy disjoint entries. Algorithm 1 and its preceding explanation now specify this indexing and update order.
  2. NbN_b is the number of training batches per epoch; its role is step scaling. With the mathematical multiplier convention, the update is

    \qquad\eta_t=\frac{a_t}{2N_b},\qquad\mu_q^0=0.$$ Preserving the nominal feedback step when batch count changes requires preserving $a_t/N_b$. The common scalar schedule, indexed by feedback updates, is
a_t= \begin{cases} a_0, & t=0,\\ \min(2a_{t-1},a_{\max}), & t>0 \text{ and } s_t>\frac{1}{2}s_{t-1},\\ a_{t-1}, & \text{otherwise}. \end{cases}$$ Here $a_0$ is the initial scalar and $a_{\max}$ is its cap. The scalar is selected before the multiplier update. Only $s_t$ uses absolute values; cached residuals retain their signs. Table 5 and its accompanying paragraph now define $N_b$ and the schedule, using $\mu_{\mathrm{stored}}=2\mu$. 3. **The T1 rule directly matches the per-graph recurrence in Theorems B.1/B.2.** Outputs in different batches can come from different parameter states because the analysis admits arbitrary primal outputs. For the multiple-output case raised in the review, let a graph accumulate outputs $V^{k\ell}$ with positive weights $\eta_{k\ell}$ while holding $\mu^k$ fixed: $$\mu^{k+1}=\left[\mu^k+\sum_{\ell\in\mathcal I_k}\eta_{k\ell}c(V^{k\ell})\right]_+.$$ Assume $\mu^0=0$, $V^{k\ell}\in\mathcal M$, and positive loss coefficients $\beta_{k\ell}$. Define $S=\sum_{k<K,\ell}\eta_{k\ell}>0$, $\epsilon_{k\ell}=\|grad_{\mathcal M}F_{\beta_{k\ell},\mu^k}(V^{k\ell})\|_F$, and $R_{k\ell}=\|g(V^{k\ell})\|_1+\epsilon_{k\ell}$. Then $$\min_{k,\ell}R_{k\ell} \le\frac{\sum_{k,\ell}\eta_{k\ell}R_{k\ell}}{S} \le\sqrt{\frac{\sum_{k,\ell}\eta_{k\ell}\epsilon_{k\ell}^2}{S}} +\frac{\|\mu^K\|_1}{2S} +\frac{\sum_{k,\ell}\eta_{k\ell}\mathcal P(V^{k\ell})}{S}.$$ All sums range over $k<K$ and $\ell\in\mathcal I_k$. To obtain the bound, sum the componentwise projection inequality over update blocks and apply $\|g(V)\|_1\le\tfrac12\mathbf1^\top c(V)+\mathcal P(V)$; weighted Cauchy–Schwarz bounds the gradient contribution. This explicitly retains each accumulated output and its weight. The single-output case recovers the T1 recurrence.

Part 2/2

Q3. Euclidean features and manifold geometry

  1. Tangent projection connects the gradient features to the analyzed objective. On the unit sphere,

    gradviF=(I−vivi⊤)∇viF.grad_{v_i}F=(I-v_iv_i^\top)\nabla_{v_i}F.

    Equation (12) uses ambient gradients as features, applies learned transformations, and normalizes the output. The local analysis describes the objective supplying those features; the learned mapping determines the network update. Section 3.4 now states this connection.

  2. We measure stationarity in the output space directly. Appendix B.8 relates parameter stationarity to embedding stationarity under a positive minimum sensitivity of the network Jacobian on the relevant tangent directions. Direct measurement gives the output residual without inferring it from a small parameter gradient. On RB200, ϵ/n\epsilon/\sqrt n falls from 13.778 to 0.103, together with decreases in edge residual and polarization. On WS, retaining feedback increases the mean tested curvature from 14.816 to 15.528, with positive increments at all 4800 evaluated states (Appendix D.2).

  3. Geometry motivates the design; output diagnostics and fixed-architecture controls test its effect. Related Burer–Monteiro [1] and inexact augmented Lagrangian [2] guarantees specify geometric and primal accuracy conditions.

Q4. What do residual cancellation and node-versus-edge controls show about compression?

  1. The residual diagnostics quantify the information lost through aggregation. Let G=∥g∥1G=\|g\|_1, N=∥c∥1/2N=\|c\|_1/2, and P\mathcal P be the polarization defect. Theorem 4.2 gives G−N≤PG-N\le\mathcal P; the cancellation rate is (G−N)/G(G-N)/G for G>0G>0. Full-feedback, final-epoch measurements over three seeds are:

    Dataset (training graphs × seeds)Cancellation rate, mean ± SDG/mG/m(G−N)/m(G-N)/mP/(2m)\mathcal P/(2m)
    WS [50,100] (1600 × 3)26.9% ± 2.52 pp0.087560.023720.61646
    WS [100,200] (1600 × 3)24.4% ± 6.82 pp0.091550.022160.64276
    WS [400,500] (1600 × 3)30.3% ± 5.94 pp0.087230.026260.64248
    ER [50,100] (1600 × 3)28.7% ± 2.58 pp0.090490.025510.57597
    PROTEINS (890 × 3)38.2% ± 2.01 pp0.064230.024030.47787

    Rates and their standard deviations are reported across seeds; pp denotes percentage points. Column headings show the different normalizations. Appendix D.3, Table 17, reports the absolute diagnostics; the rate column is supplied here to make the relative aggregation loss explicit. For evolution during training, the separate RB200 diagnostic in Appendix D.2 records normalized polarization decreasing from 0.193 to 0.00244 and edge residual from 0.279 to 0.000512.

  2. The three-way quality control compares node feedback with both nonnegative and unrestricted edge feedback. The full WS/PROTEINS test sets use 200 training epochs and three seeds. Architecture, budget, decoder, and scalar adaptation rule are matched within each comparison:

    DatasetNode feedback ↓Nonnegative edge feedback ↓Unrestricted edge feedback ↓
    WS [100,200]90.430 ± 0.20091.662 ± 0.21191.525 ± 0.104
    PROTEINS25.134 ± 0.08825.137 ± 0.04925.164 ± 0.027

    Node feedback gives the smaller mean cover on WS; the three PROTEINS means are closely spaced. These comparisons are reported in Appendix D.3, Table 16.

  3. The design combines compact feedback with direct edge-constraint control. The multiplier state uses O(n)O(n) entries, and the retained edge-wise penalty acts on constraints whose signed residuals can cancel in the node aggregate. The measured cancellation rates quantify this cost, while the separate quality control shows that compact feedback remains effective in the tested WS/PROTEINS settings. For applicability across graph structures, Theorem 4.2 gives a residual-based criterion: polarization controls how much edge violation can be hidden by aggregation. Proposition 9 separately characterizes the restricted stabilizing capacity of nonnegative node multipliers. Together, these results explain why ALON combines node feedback with edge-wise penalties.

References

[1] Boumal, N., Voroninski, V., and Bandeira, A. S. (2020). Deterministic Guarantees for Burer–Monteiro Factorizations of Smooth Semidefinite Programs. Communications on Pure and Applied Mathematics, 73(3), 581–608.

[2] Şahin, M. F., Eftekhari, A., Alacaoglu, A., Latorre, F., and Cevher, V. (2019). An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints. NeurIPS.

Thanks for the response. I have read the authors' rebuttal responses and will take that into consideration.

Thank you for taking the time to review our responses and reconsider your assessment.

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

This paper studies the Minimum Vertex Cover (MVC) problem and proposes ALON, a neural network solving framework based on augmented Lagrangian optimization. The method builds on SDP relaxation and the Burer–Monteiro factorization to transform the discrete combinatorial optimization problem into a continuous constrained optimization problem on the spherical manifold. To address the local geometric defects of traditional quadratic penalty functions near discrete feasible solutions, the authors introduce linear dual feedback and incorporate the objective gradient, penalty gradient, and dual gradient into the message passing process of a GNN. In addition, the authors reparameterize edge-level Lagrange multipliers as node-level multipliers to reduce the storage overhead of dual states while retaining the edge-level quadratic penalty term. Theoretically, the paper analyzes the local curvature difference between the quadratic penalty function and the linear dual feedback, derives an upper bound on the constraint information loss caused by node-multiplier compression, and provides conditional feasibility and KKT residual bounds under projected dual updates, as well as an optimality certificate based on SDP duality. Experimentally, the authors validate ALON’s solution quality, cross-distribution generalization ability, and computational efficiency on 19 datasets. The results show that the augmented mechanism improves 70 out of 76 backbone–dataset comparisons, that ALON achieves the best neural network solving results on 16 datasets, and that it significantly reduces inference cost relative to directly solving the continuous relaxation.

Critical strengths

(1)The most valuable contribution of the paper lies in revealing the local geometric defects of traditional quadratic penalty functions in the spherical MVC relaxation. Theorem 4.1 rigorously proves that near a discrete feasible solution, the decrease of the objective function is second-order, whereas the squared penalty term produces only a fourth-order response; therefore, no finite penalty parameter can eliminate the corresponding local negative-curvature directions. The authors further prove that linear dual feedback can provide a second-order restoring force and give an explicit multiplier threshold. This analysis provides a concrete and convincing mathematical basis for introducing the augmented Lagrangian mechanism, rather than merely an empirical algorithmic improvement. (2)The authors use node-level multipliers to reduce the storage complexity of dual states while retaining per-edge quadratic penalty terms to compensate for the information loss caused by residual aggregation. Theorem 4.2 provides a quantitative upper bound on the relationship between node-aggregated residuals and true edge constraint violations, and a counterexample reveals the limitations of this compression method. The experiments cover multiple graph distributions and GNN architectures; the augmented mechanism improves 70 out of 76 comparisons, and matching ablation experiments further support the effectiveness of dual feedback. These results jointly enhance the credibility of the proposed method.

Critical weaknesses

(1)Although Theorem 4.1 proves that linear dual feedback can improve the local curvature in specific directions, the paper does not verify whether the multipliers learned during training satisfy the corresponding curvature conditions, nor does it show a direct link between this curvature improvement and the final solution quality. In particular, ALON sets all dual multipliers to zero during inference, so the dual gradient feedback that plays a central role in the theoretical analysis does not actually participate in computation at inference time. The authors argue that the dual information during training has been absorbed into the network parameters, but direct mechanism validation and corresponding ablation experiments are lacking. In addition, Theorems B.1 and B.2 mainly provide conditional feasibility and KKT residual bounds that depend on the output trajectory, but they do not prove that the actual network parameter updates can satisfy the conditions required for the residuals to approach zero. Therefore, the existing theory cannot directly guarantee the training convergence of ALON, nor can it explain the quality of the final discrete solution. The authors are suggested to further report metrics such as curvature, constraint violation, polarization defect, and gradient residuals in the embedding space, so as to establish a closer connection between the theoretical analysis and the experimental results. (2)ALON largely inherits the SDP/BM relaxation and the optimization-gradient-based message passing architecture of OptGNN, and its main algorithmic improvement is the introduction of classical augmented Lagrangian feedback and node-level multiplier reparameterization. Therefore, the independent novelty of this paper as a new neural optimization algorithm remains somewhat limited. The experiments also mainly focus on ordinary MVC and weighted MVC, which is not yet sufficient to demonstrate the applicability of this mechanism to a broader range of combinatorial optimization problems. Although ALON achieves significant amortized speedup compared with directly solving the continuous relaxation, this comparison does not fully demonstrate its practical competitiveness. According to the paper’s own comparison with classical algorithms, NuMVC and FastVC can achieve solution quality no worse than ALON with comparable or even lower runtime on the current test scales, and on some larger-scale and difficult graph instances the performance gap remains significant. Therefore, the authors need to further clarify the applicable scenarios of this method relative to mature combinatorial optimization algorithms, as well as the value of the augmented Lagrangian mechanism in broader neural optimization tasks.

Questions for authors

(1)Theorem 4.1 gives explicit conditions under which linear dual feedback improves the local curvature. Can the authors analyze, on representative test instances, the curvature changes induced by the multipliers during training—for example, by reporting the corresponding restoring thresholds or local Hessian eigenvalues—and explain whether these changes are correlated with the final vertex cover quality? This would help determine whether the mechanism revealed by the theory truly explains the experimental performance improvement. (2)The paper sets all node multipliers to zero during inference, so the dual gradient features are also zero. Can the authors further explain how the dual feedback during training is absorbed into the network parameters? In particular, it would be desirable to see ablation experiments that separately remove the dual term in the augmented Lagrangian loss and the dual gradient features in the GNN message passing, so as to clarify their independent contributions to the performance improvement. (3)The residual bound in Theorem B.2 depends on the gradient error in the embedding space, multiplier growth, and polarization defect, but the paper does not prove that actual neural network training can make these quantities satisfy the required convergence conditions. Can the authors provide corresponding training trajectories or numerical results to show how these theoretical quantities evolve during actual training, and whether the derived residual bound has practical explanatory power? (4)Considering that NuMVC and FastVC exhibit strong time–quality advantages in the existing experiments, in what scenarios do the authors believe ALON has a clear advantage? In addition, the method has so far been validated mainly on MVC and its weighted version. Is there evidence that the proposed node-level augmented Lagrangian mechanism can be effectively generalized to other combinatorial optimization problems with different constraint structures? These results would directly affect the evaluation of the breadth and practical significance of this paper’s contributions.

5 comments

Part 1/2

Thank you for recognizing the geometric analysis and compression bound.

Cover sizes are means ± sample SD across three training seeds, averaging test graphs within each seed. Covers are measured after decoding and repair; pre-repair feasibility is reported separately.

Q1. Do learned multipliers produce the predicted geometry and improve quality?

  1. Feedback increases directional curvature at training outputs. Holding each output fixed, we remove or retain only its linear feedback term. Along a tangent direction decreasing the cover objective:
DatasetTraining graphs × seedsFeedback removed → retainedPositive increment / states
WS1600 × 314.816 → 15.5284800/4800
MUTAG150 × 31.889 → 2.681450/450
ENZYMES480 × 35.037 → 5.7581440/1440

Increments are also positive at every evaluated state along two fixed random tangent directions (Appendix D.2, Table 15). These are directional curvature measurements at continuous outputs.

  1. Learned multipliers meet the restoring threshold at many vertices. At feasible discrete reference covers, we test Di>wi/4D_i>w_i/4, with Di=∑j∈N(i)∖C(μi+μj)D_i=\sum_{j\in\mathcal N(i)\setminus C}(\mu_i+\mu_j), retaining the learned multipliers:
DatasetSelected vertices satisfying the thresholdEssential selected vertices satisfying the threshold
WS67.8% ± 0.21 pp68.4%
MUTAG83.4% ± 8.32 pp83.4%
ENZYMES83.5% ± 1.04 pp83.5%

Fractions are averaged equally over graphs, then three seeds; pp denotes percentage points. An essential selected vertex has an unselected neighbor. This tests the theorem's condition at reference covers.

  1. Training approaches the near-discrete regime. In a separate RB200 run, ϵ/n\epsilon/\sqrt n decreases from 13.778 to 0.103, edge residual ∥g∥1/m\|g\|_1/m from 0.279 to 0.000512, and polarization defect P/(2m)\mathcal P/(2m) from 0.193 to 0.00244. Quantities are normalized per graph and averaged over training graphs and three seeds (Appendix D.2).

  2. A controlled training intervention tests prediction quality. Joint feedback reduces mean feasible cover size from 90.998 to 90.378, improving all three paired seeds with zero multipliers at inference (Q2). Together, these tests support feedback's geometric action and its effect on predictions; they do not measure a per-instance curvature–quality correlation.

Q2. What remains at zero-multiplier inference, and what does each pathway contribute?

  1. Feedback changes the learned parameters. Loss feedback adds ∑iμi∇θci(Vθ)\sum_i\mu_i\nabla_\theta c_i(V_\theta) to the parameter gradient; feedback features change layer inputs and parameter updates. Inference uses the resulting parameters with multipliers set to zero (Section 3.4).

  2. All four variants use zero multipliers at inference. Architecture, parameter count, training budget, and decoding are matched; results cover all 200 WS test graphs and three seeds:

Feedback during trainingFeasible cover size ↓Pre-repair feasibility ↑
Neither pathway90.998 ± 0.08010.5%
Loss only91.258 ± 0.14794.8%
Features only91.828 ± 0.26028.2%
Both pathways90.378 ± 0.10899.8%
  1. Loss feedback alone substantially improves feasibility. Joint feedback improves feasibility by 89.3 percentage points and reduces cover size by 0.620 vertices, with smaller covers in all three paired seeds. This directly demonstrates a prediction benefit after feedback is removed (Appendix D.1, Table 13).

Part 2/2

Q3. How do the training quantities and the B.2 bound behave?

  1. First → final epoch diagnostics, averaged over each full training set, then three seeds:
DatasetResidual: first → finalB.2 bound: first → final
WS72.41 → 16.36267.22 → 415.22
MUTAG16.55 → 1.2037.65 → 11.72
RB2001507.79 → 7.693335.74 → 41.60
DatasetGradient termMultiplier termPolarization term
WS5.233 → 0.97358.735 → 9.736203.252 → 404.506
MUTAG4.004 → 0.59512.536 → 0.19321.111 → 10.927
RB200176.096 → 6.3161331.698 → 0.9431827.951 → 34.338
  1. MUTAG/RB200 residuals and all bound terms decrease. On WS, gradient and multiplier terms fall, but polarization increases the bound. The decomposition reveals behavior hidden by a falling residual.

  2. The bound separates stationarity, multiplier growth, and polarization. Let ST=∑t<TηtS_T=\sum_{t<T}\eta_t, ϵt=∥gradMFβt,μt(Vt)∥F\epsilon_t=\|grad_{\mathcal M}F_{\beta_t,\mu^t}(V^t)\|_F, and Rt=∥g(Vt)∥1+ϵtR_t=\|g(V^t)\|_1+\epsilon_t. Under the projected recurrence,

min⁡t<TRt≤∑t<TηtRtST≤∑t<Tηtϵt2ST+∥μT∥12ST+∑t<TηtP(Vt)ST.\min_{t<T}R_t\le\frac{\sum_{t<T}\eta_tR_t}{S_T}\le\sqrt{\frac{\sum_{t<T}\eta_t\epsilon_t^2}{S_T}}+\frac{\|\mu^T\|_1}{2S_T}+\frac{\sum_{t<T}\eta_t\mathcal P(V^t)}{S_T}.

The bound admits arbitrary primal outputs; convergence requires all three terms to vanish as STS_T grows (Appendix B.7). These are finite-training diagnostics. Related analysis specifies primal accuracy and geometric conditions [6].

Q4. When is ALON useful, and does feedback transfer to other constraints?

  1. A trained ALON model offers a return-time/quality trade-off. The additional target-stopping comparison gives:
Dataset (test graphs)MethodCover size ↓Time (ms/graph) ↓
PROTEINS (112)ALON25.090.463
PROTEINS (112)FastVC25.014.273
PROTEINS (112)NuMVC24.981.992
WS [50,100] (200)ALON45.600.717
WS [50,100] (200)FastVC45.471.598
WS [50,100] (200)NuMVC45.546.842

Classical search stops at the graph's ALON cover size or detected expiry of the requested 100 ms limit: three seeds per graph, three repeats per seed. Times are recorded test-time means.

  1. With a trained model, ALON returns high-quality covers rapidly: size differences from FastVC/NuMVC are 0.08/0.11 on PROTEINS and 0.13/0.06 on WS. Reusable policies [3], quality/computation trade-offs [1], and graph structure [2] motivate this setting. Under the original protocol, classical solvers find equal or smaller covers on 18/19 datasets. The large speedup in Section 5.3/Appendix C.8 is against direct continuous relaxation solving.

  2. Bipartite matching tests transfer to node-capacity inequalities. For cv(p)=∑e∋vpe−1≤0c_v(p)=\sum_{e\ni v}p_e-1\le0, each node has a projected multiplier; feedback enters the loss and gradient features, with zero multipliers at inference. The experiment uses eight nodes per side, 512/64/128 training/validation/test graphs, and three seeds:

Feedback during trainingRaw feasibility ↑Feasible matching weight ↑
Neither pathway19.8%5.310 ± 0.007
Loss only20.3%5.332 ± 0.012
Features only70.1%5.335 ± 0.005
Both pathways77.6%5.336 ± 0.007
  1. Joint feedback raises raw feasibility by 57.8 percentage points and feasible weight by 0.026 (Appendix D.5, Table 19). This tests feedback transfer to node-indexed capacity constraints, alongside primal-dual learning [4] and deep augmented Lagrangian methods [5]; it does not test edge-to-node compression.

References

[1] Garmendia et al. (2024). Applicability of Neural Combinatorial Optimization: A Critical View. ACM TELO.

[2] Li et al. (2025). Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization. arXiv:2511.19573.

[3] Dai et al. (2017). Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS.

[4] Park, S., and Van Hentenryck, P. (2023). Self-Supervised Primal-Dual Learning for Constrained Optimization. AAAI.

[5] Kotary, J., and Fioretto, F. (2024). Learning Constrained Optimization with Deep Augmented Lagrangian Methods. arXiv:2403.03454.

[6] Şahin et al. (2019). An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints. NeurIPS.

Thank you again for your careful review. As the discussion period draws to a close, we would appreciate your thoughts on whether the additional curvature and residual diagnostics, together with the controlled feedback ablations under zero-multiplier inference, address your main concerns about the connection between our analysis and the learned solver. If any concerns remain that affect your overall assessment, we would be grateful for the opportunity to clarify them.

Comments on the paper

1 comment

We thank all reviewers for their thoughtful feedback. Our responses address the main concerns through the following clarifications and additional evidence:

  • Novelty and theoretical relevance: We clarified the contributions beyond prior methods and added curvature, stationarity, and residual diagnostics to connect the analysis with training behavior.
  • Feedback effectiveness: We added controlled ablations separating the loss and feature pathways, including zero-multiplier inference and comparisons across graph families.
  • Compression and implementation: We quantified aggregation loss and total training-memory savings, compared node- and edge-level feedback, and clarified the correspondence between the implemented updates and theoretical recurrence.
  • Practical value and broader applicability: We added time–quality comparisons with classical solvers and a bipartite-matching experiment.

These additions clarify the method’s mechanism, empirical benefits, and scope. We welcome further questions and would be happy to discuss any remaining points.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.