- 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
Thanks for your active response. I will keep my score.
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).
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)/WI (mean 0.713) exceeds the structural factor (median 0.673) on all 480 BA-large graphs. If the fallback violates commitment T, its value cannot certify a completion respecting T. The AIR certificate and repair credit guarantee, before residual solving, that the specified repaired branch attains at least αOPT(I)+GI(T). If the fallback satisfies T, 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).
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).
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).
Revisions addressing remaining weaknesses (W1–W2)
We hope these results and revisions fully clarify your questions and concerns.