acceptodds
Under review as a conference paper at ICLR 2027

Certify Before You Commit: Test-Time Structural-Regret Certificates for Learning-Augmented Graph Optimization

Abstract

Machine learning can speed up hard graph optimization by fixing predicted variables or restricting search, but a single wrong commitment can exclude every high-quality solution. Prediction accuracy and confidence do not quantify this objective loss. We introduce augmented-instance regret (AIR), which measures the loss caused by enforcing a partial assignment, and AIRGraph, a model-agnostic framework that certifies such assignments at test time. AIRGraph computes a safe upper bound on AIR, combines it with a problem-specific repair credit, and accepts a proposal only when the credit exceeds the approximation-scaled bound. We prove that an independent fallback preserves the original approximation guarantee for arbitrary predictions. We instantiate AIRGraph for weighted Vertex Cover, weighted Maximum Independent Set, and signed MaxCut/Max-2Lin. Our local linear-programming Vertex Cover certificate is always at least as tight as the classical Nemhauser–Trotter certificate and transfers exactly to Maximum Independent Set; our MaxCut flow certificate is always at least as tight as a closed-form regional bound. Exact audits on small, exactly solved instances find no implementation violations. On 500 small Barab\'asi–Albert (BA-small) graphs, the tighter MaxCut certificate changes 541 gate decisions and improves 149 outputs relative to the closed-form certificate, with no degradation. On 480 large Barab\'asi–Albert (BA-large) graphs, evaluating the cheap MaxCut certificate for an existing proposal takes a median of milliseconds (interquartile range – milliseconds). AIRGraph gives learned partial assignments explicit, instance-specific guarantees, independently of how the predictor was trained.

Primary area:
optimization
Keywords:
learning-augmented algorithms, combinatorial optimization, graph optimization, test-time certification, structural regret

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_h9b2OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the objective loss incurred by enforcing learned partial assignments in graph optimization. It defines augmented-instance regret as the difference between the unrestricted and conditioned optima, and proposes AIRGraph, which combines an upper bound on this regret with a problem-specific repair credit.

The paper derives certificates for weighted Vertex Cover, their additive transfer to Maximum Independent Set, and regional commitments in signed MaxCut. For Vertex Cover, a persistent-face local LP strengthens an NT-based certificate. For MaxCut, a multicommodity-flow bound strengthens a closed-form regional bound. Experiments investigate certificate validity, gate decisions, computational overhead, and comparisons with confidence selection, size-based selection, and matched-time search.

Critical strengths

1.The paper targets a meaningful decision interface. Pricing the objective consequence of a realized commitment is more directly relevant to variable fixing than prediction confidence or label accuracy alone.

3.The problem-specific certificate constructions are substantive. The local-LP strengthening for Vertex Cover and the MaxCut flow bound are the strongest technical contributions. The supplied proofs give clear safety and dominance arguments.

3.The evaluation includes important negative controls. The paper explicitly reports that size-based selection explains the clean-condition selection gains and that prediction-seeded search obtains better objectives under matched budgets.

4.The scope of the MIS result is appropriately limited. The paper correctly distinguishes additive regret equivalence from a multiplicative approximation guarantee.

Critical weaknesses

W1. The generic framework is algebraically simple; novelty rests on the instantiations.

The certificate–repair theorems follow directly by substitution, sequential composition telescopes optimum differences, and best-of fallback safety is automatic once the fallback is retained. These observations are useful organizationally, but should not carry the main novelty claim.

W2. The demonstrated practical value is narrower than the framework’s breadth suggests.

Prediction-seeded search outperforms AIRGraph on both tested MaxCut predictors, while simple size rules reproduce or improve the clean-condition selection frontier. The evidence therefore supports a commitment-certification interface more strongly than an improved optimization procedure.

W3. The certified margins are weaker than readily available fallback bounds on the main benchmark.

The fallback’s feasible-value ratio exceeds the structural factor on all 480 BA-large graphs. This does not invalidate the commitment-specific guarantee, but makes its additional operational value unclear unless commitments must remain binding.

W4. The experiments do not directly evaluate the strongest binding-commitment use case.

Final polishing and fallback selection may alter committed labels. These operations preserve the objective guarantee but do not preserve the commitment itself. A setting with externally imposed commitments would better demonstrate the intended application.

W5. The tighter certificates can be expensive, and numerical certification needs clarification.

The flow certificate takes approximately five seconds per small graph in its comparison study. A matched-time comparison would clarify whether tightening is preferable to additional completion or search. For LP-based certificates, ordinary floating-point solutions and finite audits are not by themselves formal numerical certificates.

Questions for authors

Q1. Can the authors evaluate a deployment setting where accepted commitments must remain binding throughout completion, polishing, and final selection?

Q2. What operational decision benefits from the structural bound when the independently computed fallback already gives a stronger ratio certificate?

Q3. How does flow-based certification compare with spending the same time on additional search or residual completions?**

Q4. For the local VC LP, does the implementation use a verified lower bound on the LP optimum? An approximate primal objective could underestimate regret and compromise safety.

Q5. Are there natural prediction shifts under which certification provides an advantage beyond commitment size, without confidence-preserving synthetic corruption?

2 comments
AuthorsOpenReview ↗

Response to Reviewer h9b2

Thank you for your constructive comments and suggestions. We added exact-arithmetic checks and three studies, marked in red.

Responses to Questions

Q1. Binding commitments (W4). Yes. We evaluated a binding pipeline on all 480 BA-large graphs (Sec. 5.3, lines 430–452; App. B.9, Table 13, lines 1392–1419).

  • Protocol: Accepted regional labels remain fixed through contracted completion, residual-only polishing, and final selection. The fallback is returned only if the gate rejects every proposal.
  • Results: All binding and feasibility checks pass. The gate certifies a positive-margin commitment on all 480 graphs, attaining mean objective 2923.648, or +61.965 above the fallback. Count-matched largest-size selection reaches 2924.419 (difference −0.771-0.771, 0.026%). Twelve binding outputs score below the unrestricted fallback, which cannot be returned after acceptance. Every accepted branch satisfies its pre-completion bound. Section 6 (lines 509–515) lists upstream binding decisions as future work.

Q2. Structural bound vs. fallback ratio (W3). The bound supports pre-completion acceptance of a binding restriction (Sec. 5.3, lines 423–455; App. B.5, lines 1221–1233). The fallback ratio v(Sfb)/WIv(S_{\mathrm{fb}})/W_I (mean 0.7130.713) exceeds the structural factor (median 0.6730.673) on all 480 BA-large graphs. If the fallback violates commitment TT, its value cannot certify a completion respecting TT. The AIR certificate and repair credit guarantee, before residual solving, that the specified repaired branch attains at least αOPT(I)+GI(T)\alpha OPT(I)+G_I(T). If the fallback satisfies TT, it is a valid restricted solution and its stronger feasible-value bound applies.

Q3. Flow vs. equal-budget completion or search (W5). We ran a paired budget study on 500 BA-small graphs (Sec. 5.2, lines 412–420; App. B.7, Table 9, lines 1305–1330).

  • Flow-gated completion scores 714.566 in 2.488 s mean accounted time; cheap-bound completion receives the same cap and scores 713.984, finishing in 1.644 s (flow gain +0.582, 95% CI [−0.622,1.810][-0.622,1.810]). Non-binding seeded search scores 725.225 in 2.487 s.
  • Operational takeaway: The cheap bound takes median 1.53 ms per existing proposal in a separate BA-large microbenchmark (App. B.3, lines 1174–1179). Section 6 (lines 523–525) proposes testing selective flow for proposals the cheap bound cannot certify.

Q4. Verified VC LP lower bound and numerical safety (W5). Yes. We verify a dual lower bound, without relying on a floating-point primal objective (Sec. 4.1, lines 289–294; App. B.2, lines 1101–1109).

  • VC dual witness: HiGHS proposes dual variables; we convert them to rationals, check every dual constraint exactly, and evaluate L^(T)\widehat L(T). Weak duality gives L^(T)≤Llocal(T)\widehat L(T)\le L_{\mathrm{local}}(T), so [w(F)−L^(T)]+[w(F)-\widehat L(T)]_+ conservatively upper-bounds AIR. A verified NT bound is available if verification fails. All 228 audited VC rows have verified local-dual and NT witnesses; none uses the NT fallback.
  • MaxCut flow witness (App. A.6, lines 918–926): Candidate paths become exact binary rationals; demands, loads, and overflows are checked exactly, and the AIR bound is rounded upward (repair credit downward). All 2,008 BA-small flow bounds in the paired run pass. These checks cover the verified finite-input calculations.

Q5. Natural shift beyond commitment size (W2). We applied a frozen BA-small GNN4CO checkpoint to 500 WS-small graphs without changing labels or confidence (Sec. 5.5, lines 483–485; App. B.11, Table 16, lines 1493–1515).

  • The binding fixed-size rule (K=4K=4) falls below the fallback on 463 of 500 WS-small graphs, losing 24.622 points on average (95% CI [23.300,25.924][23.300,25.924]). AIRGraph rejects all proposals because every certified gain is negative and returns the fallback.
  • A BA-small-calibrated confidence threshold also rejects every WS-small proposal. This transfer shows protection beyond commitment size; it does not distinguish certification from calibrated confidence abstention.

Revisions addressing remaining weaknesses (W1–W2)

  • W1 (technical novelty): The generic gain and composition results in Section 3 now appear as Propositions 3.3 and 3.4 (lines 216–243). The revised Contributions paragraph (lines 112–131) and Section 4 opening (lines 247–253) emphasize the VC persistent-face local LP (Theorem 4.3) and MaxCut flow bound (Theorem 4.7) as the main technical constructions.
  • W2 (practical framing): Section 6 (lines 509–525) presents AIRGraph as a test-time commitment-certification interface and discusses selective flow refinement and external upstream-binding applications as next steps.

We hope these results and revisions fully clarify your questions and concerns.

Thanks for your active response. I will keep my score.

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

AIRGraph bounds the objective loss from partial variable commitments, combines this with repair credits, and retains a fallback approximation guarantee. It develops vertex-cover certificates, an additive transfer to independent set, and a MaxCut certificate hierarchy. Experiments examine bound tightness, acceptance decisions, solution quality and cost.

Critical strengths
  • The persistent-face VC LP and MaxCut flow construction give substantive, tighter certificates for individual commitments without assuming accurate predictions.
  • On 500 BA-small graphs, flow bounds change 541 proposal-acceptance decisions and improve 149 graph outputs relative to the cheap bound. Strong search baselines and size controls also expose the limits of certification’s empirical benefit.
Critical weaknesses
  • Evidence for a favorable computation–quality trade-off remains limited. On BA-large, commitment-size rules reproduce the clean selection frontier; prediction-seeded search achieves better mean final objectives on both Table 1 datasets under matched post-inference budgets (§§5.3–5.4). The flow results demonstrate useful decision changes, while a net advantage over the stronger search and selection controls remains unclear. This limits practical significance while preserving the certificate contribution.
Questions for authors

None essential to my current recommendation.

2 comments
AuthorsOpenReview ↗

Response to Reviewer Y4px

Thank you for your constructive review and insightful comments. To examine the computation–quality trade-off and practical significance you raised, we conducted three new controlled studies in the revision (marked in red): (1) an unmodified out-of-distribution (OOD) graph-family transfer study, (2) a strictly binding commitment evaluation, and (3) a matched-budget flow evaluation.

1. Evaluating practical value relative to size rules and heuristic search

Our results delineate the operational difference between unconstrained optimization and certified commitment:

  • Size rules on clean data and under distribution shift (Sec. 5.4, p. 9, lines 464–472; New Appendix B.11, Table 16, pp. 28–29, lines 1493–1515): On clean BA-large graphs, larger commitments leave smaller residuals and size rules perform well. When we apply a frozen BA-small GNN4CO model directly to 500 WS-small graphs (an unmodified graph-family shift) without synthetic corruption, the fixed-size rule (K=4K=4) falls below the fallback on 463 of 500 graphs, losing an average of 24.622 objective points (95% CI [23.300,25.924][23.300,25.924]; Sec. 5.5, p. 9, lines 483–485). AIRGraph computes negative certified gain for every proposal and rejects all of them, preventing degradation. A confidence threshold calibrated on BA-small also rejects all WS-small proposals. Thus this experiment shows protection beyond commitment size, while calibrated confidence abstention is effective under this shift too.
  • Strictly binding commitments (Sec. 5.3, pp. 8–9, lines 430–452; New Appendix B.9, Table 13, pp. 26–27, lines 1392–1419): When partial commitments represent hard upstream decisions or mandatory variable fixings that downstream solvers cannot alter, the tested unconstrained seeded search does not respect those restrictions. We evaluated a strictly binding pipeline on all 480 BA-large graphs where accepted regional labels remain fixed through residual completion, residual-only polishing, and final output. AIRGraph certifies a positive-margin proposal on all 480 graphs, achieving a mean objective of 2923.648 (+61.965 above the unrestricted fallback). Count-matched size selection reaches 2924.419, a difference of 0.771 (0.026%). AIRGraph also provides a formal, instance-specific bound for the accepted restriction before completion.

2. Computational cost of the flow certificate and two-tier proposal

To test whether the 541 decision upgrades from the flow certificate justify its runtime under a budget cap, we ran a paired computation study on the 500 BA-small graphs (Sec. 5.2, p. 8, lines 409–420; New Appendix B.7, Table 9, p. 25, lines 1305–1330):

  • Flow vs. equal-budget alternatives (Sec. 5.2, p. 8, lines 412–420; Table 9, p. 25, lines 1317–1329): The separate certificate-frontier study records mean flow certification time of 2.438 s per graph. In the paired study, all 2,008 flow bounds use exact rational path witnesses. Under a matched per-instance cap (2.488 s mean flow accounted time), flow-gated completion has an observed mean advantage over cheap-bound residual completion (which finishes early in 1.644 s) of +0.582 (95% CI [−0.622,1.810][-0.622,1.810]). Non-binding seeded search scores +10.659 above flow in 2.487 s. The paired interval includes zero.
  • Two-tier operating envelope (Sec. 6, p. 10, lines 523–525): These findings motivate a further test:
    1. Cheap certificate as the fast default (Appendix B.3, p. 22, lines 1174–1179): In a separate BA-large microbenchmark, evaluating the cheap bound for an already materialized proposal takes a median of 1.53 ms. The gate selects a positive-margin proposal on all 480 BA-large graphs (p. 8, lines 423–428) and rejects all proposals in the BA-to-WS shift (p. 9, lines 483–485).
    2. Selective flow refinement (Sec. 5.2, p. 8, lines 409–411; Sec. 6, p. 10, lines 523–525): Flow upgrades 541 gate decisions and improves 149 outputs without degradation in the certificate-frontier study. Section 6 proposes invoking flow only for proposals the cheap bound cannot certify and evaluating the full adaptive pipeline under paired budgets.

We hope these results and revisions fully clarify your questions and concerns.

Reviewer_Y4pxOpenReview ↗

Thanks for response

I thank the author for the response. I will keep my positive score.

Reviewer_syPdOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposed a framework for deciding whether an optimizer can safely enforce decisions predicted by a machine learning algorithm. The authors evaluate their proposed framework on three problems, weighted vertex cover, maximum independent set and single max-cut/max-2lin, and demonstrate the improvement in optimization performance.

Critical strengths

None

Critical weaknesses

Overall, I found the writing of this paper required substantial improvement to the point that it is hard to understand and identify the contribution of this paper. In particular, the authors define so many theorems in section 3 and 4, which makes it difficult to tell which theorem is the main contribution of this paper. Most of the theorems in section 3 seem trivial, for instance Theorem 3.3 and Theorem 3.4, which follow directly from the inequality in equation (2-5).

For me, it seems like the main contribution of the paper is in section 4. Unfortunately, section 4 is extremely difficult to follow as the author did not clearly define the problems, weighted vertex cover, maximum independent set and single max-cut/max-2lin, used in the section. The authors simply assume readers already familiar with those problems and just roll out theorems in rapid succession. A lot of notations in section 4 are also not properly defined, for example N(B)N(B) in section 4.1 and ⊕\oplus is section 4.3, making the section even harder to follow.

I believe there is novelty in this paper; however, the writing of this paper needs significant improvement in order to meet the standard for ICLR.

Questions for authors

None

2 comments
AuthorsOpenReview ↗

Response to Reviewer syPd

Thank you for your constructive review. Based on your comments, we have rewritten the Introduction, Section 3, and Section 4 to define the three optimization problems and key notation before use, separate straightforward algebraic rules from our core technical theorems, and make the main contributions clear. All revisions are marked in red in the updated manuscript.

1. Clarifying the role of Section 3 and streamlining the general results

We agree that the general substitution and composition properties in Section 3 are algebraically straightforward and should not obscure the main theorems in Section 4.

  • Clear division of labor: We revised the Introduction (p. 3, lines 112–135) and the opening of Section 3 (p. 4, lines 173–179) to explicitly state that Section 3 provides the general test-time decision rule, whereas Section 4 contains our core technical contributions on constructing problem-specific loss certificates.
  • Propositions: The generic gain and sequential composition results now appear as Propositions 3.3 and 3.4 (p. 5, lines 216–243; proofs in Appendices A.1–A.2).
  • Intuitive explanation of repair credit: Before Equations (2)–(5) (p. 4, lines 202–215), we added a plain-language explanation of where the repair credit KI(T)K_I(T) comes from: when a commitment fixes part of a graph, we account for the fixed part's objective value exactly and apply the ρ\rho- or α\alpha-approximation algorithm only to the remaining residual graph. This avoids paying the worst-case approximation penalty on the already-fixed region, generating a guaranteed objective saving KI(T)K_I(T) that can offset bounded commitment loss.

2. Self-contained problem definitions and explicit notation in Section 4

To make Section 4 self-contained and easy to follow, each subsection now defines the optimization problem, the committed decisions, and its notation before introducing certificates:

  • Weighted Vertex Cover (Sec. 4.1, pp. 5–6, lines 256–299): We formally define minimum-weight Vertex Cover, the commitment T=(A,B)T=(A,B), and the open neighborhood N(B)={v∈V∖B:∃u∈B,uv∈E}N(B)=\{v\in V\setminus B:\exists u\in B,uv\in E\}. We also write out the standard VC LP objective and constraints explicitly. Before presenting the formulas, we explain the intuition: classical Nemhauser–Trotter (NT) persistency gives a baseline loss bound using only integral LP coordinates, whereas our persistent-face local LP (Theorem 4.3) tightens this bound by accounting for weight an optimal cover must already pay on vertices touched by the commitment.
  • Weighted Maximum Independent Set (Sec. 4.2, p. 6, lines 306–323): We define the maximum-weight independent set problem, explain its exact complement relation with Vertex Cover (OPTMIS(G)=WV−τ(G)OPT_{\text{MIS}}(G)=W_V-\tau(G)), and state clearly that the transferred certificate is additive (Theorem 4.5), meaning the multiplicative guarantee in Proposition 3.3 is not invoked for MIS.
  • Signed MaxCut / Max-2Lin (Sec. 4.3, p. 7, lines 324–357): We formally define the binary labeling objective, define ⊕\oplus as addition modulo two (XOR), and define edge-set weights w(E′)w(E'), regional relative-label commitments, and the internal cut δW(S)\delta_W(S). Before Theorem 4.7, we explain the intuition: the closed-form cheap bound charges every violated internal edge and half the boundary weight as potential loss, whereas our multicommodity flow certificate routes demand through satisfied internal edges, using their capacity to offset potential loss and produce a tighter bound.

3. Highlighting main technical contributions and improving global readability

  • Explicit contribution hierarchy: In the Contributions paragraph of the Introduction (p. 3, lines 112–131) and the opening of Section 4 (p. 5, lines 247–253), we now highlight our two main technical constructions, namely the persistent-face local LP for Vertex Cover (Theorem 4.3) and the flow relaxation for Signed MaxCut (Theorem 4.7), along with the exact additive transfer to MIS (Theorem 4.5).
  • End-to-end readability: We refined the motivating example in Section 1 (p. 1, lines 47–54), clarified the workflow in Figure 1 (p. 2), structured Section 5.2 to separate correctness audits from decision upgrades and runtimes (p. 8, lines 399–420), and distinguished multiplicative vs. additive guarantees in Table 2 (p. 18, lines 964–966).

We hope these results and revisions fully clarify your questions and concerns.

Thank you for the rebuttal and the revisions. I will take it into consideration for my final assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.