Augmented Lagrangian Optimization Neural Network for Minimum Vertex Cover

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$[100,200]$ split.