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

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 $1.53$ milliseconds (interquartile range $1.05$–$1.97$ milliseconds). AIRGraph gives learned partial assignments explicit, instance-specific guarantees, independently of how the predictor was trained.