Enforcing convex constraints in Graph Neural Networks

Ahmed Rashwan (University of Bath) · Keith Briggs (BT) · Chris Budd (University of Bath) · Lisa Kreusser (University of Bath and Monumo)

best-approximation problemcomponent-averaged dykstraconstrained optimisationconvergence resultdynamic constraints end-to-end traininggpu-accelerated implementationgraph neural network linear programmingnon-convex quadratic programsoptimization techniquesradio transmit power optimizationsparse vector clippingsurrogate gradient

Many machine learning applications require outputs that satisfy complex, dynamic constraints. This task is particularly challenging in Graph Neural Network models due to the variable output sizes of graph-structured data. In this paper, we introduce ProjNet, a Graph Neural Network framework which satisfies input-dependant constraints. ProjNet combines a sparse vector clipping method with the Component-Averaged Dykstra (CAD) algorithm, an iterative scheme for solving the best-approximation problem. We establish a convergence result for CAD and develop a GPU-accelerated implementation capable of handling large-scale inputs efficiently. To enable end-to-end training, we introduce a surrogate gradient for CAD that is both computationally efficient and better suited for optimization than the exact gradient. We validate ProjNet on four classes of constrained optimisation problems: linear programming, two classes of non-convex quadratic programs, and radio transmit power optimization, demonstrating its effectiveness across diverse problem settings.