Research map / Optimization / Optimizers
Enforcing convex constraints in Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces ProjNet, a GNN that enforces input-dependent linear constraints via a GPU-accelerated Component-Averaged Dykstra projection plus sparse vector clipping layers, with a surrogate gradient for the projection.
Problem
Enforcing input-dependent convex (linear) constraints on GNN outputs with strict feasibility, at scale and with batched sparse graphs, where existing vector clipping and optimisation layers are costly or do not scale.
Approach
Combines a GPU-implemented Component-Averaged Dykstra (CAD) projection, whose limit is proven to be a specific weighted projection, with sparse vector clipping that scales per independent constraint group, and trains through a cheap surrogate Jacobian (identity minus outer product of the normalized projection residual) instead of the exact projection gradient.
Key results
- ProjNet with c_h=0 reaches 0.9973 of optimal objective on linear programs versus 1.0000 for the LP solver baseline, with runtime advantage over Gurobi and PDLP at large scale.
- On transmit power optimisation, ProjNet (c_h=0) achieves 3.01 average objective vs 2.79 for fractional programming and 2.15 for trust-constr.
- CAD projection can solve projection problems up to two orders of magnitude faster than Gurobi when tolerance is relaxed and the initial point is near the feasible set.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add CAD projection instead of using an interior feasible point (ablation) | ProjNet · Linear programming | optimality ratio: 0.2954 -> 0.9973 | Helped |
| Add CAD projection instead of using an interior feasible point (ablation) | ProjNet · Quadratic (ER) | objective value: 1.93 -> 6.83 | Helped |
| Add CAD projection instead of using an interior feasible point (ablation) | ProjNet · Quadratic (BA) | objective value: 1.91 -> 7.73 | Helped |
| Add CAD projection instead of using an interior feasible point (ablation) | ProjNet · Transmit power | objective value: 1.79 -> 3.01 | Helped |
| Add sparse vector clipping (ablation) | ProjNet with c_h = 0 · Quadratic (ER) | objective value: 6.76 -> 6.83 | No clear effect |
| Add sparse vector clipping (ablation) | ProjNet with c_h = 0 · Quadratic (BA) | objective value: 7.72 -> 7.73 | No clear effect |
| Add sparse vector clipping (ablation) | ProjNet with c_h = 0 · Transmit power | objective value: 2.92 -> 3.01 | No clear effect |
| Set c_h from 0 to 1 (ablation) | ProjNet · Linear programming | optimality ratio: 0.9973 -> 0.9632 | Hurt |
| Set c_h from 0 to 1 (ablation) | ProjNet · Transmit power | objective value: 3.01 -> 1.79 | Hurt |
| Set c_h from 0 to 0.01 (ablation) | ProjNet · Quadratic (BA) | objective value: 7.73 -> 7.86 | No clear effect |
Surprising findings
- On quadratic programs, trust-constr and the classical solver baselines slightly outperform ProjNet in objective value, while ProjNet is competitive.
- Removing the CAD component (replacing with an LP-derived interior point) causes large drops on the linear programming task (0.2954 vs 0.9973).
Limitations
- Theory and method focus on linear constraints; extension to general convex constraints is conjectured rather than shown.
- Speed advantage diminishes when tolerance is tight or initial point is far from the feasible set; penalty c_h trades off speed and accuracy.
- Poor scaling and infeasibility of constraint sets are left to future work; test problems are well-scaled and feasible by construction.
Experimental setup
Datasets: randomly generated linear programs randomly generated non-convex quadratic programs (Erdos-Renyi and Barabasi-Albert graphs) randomly generated transmit power problems (geometric graphs)
Benchmarks: linear programming non-convex quadratic programming (ER and BA graphs) transmit power optimisation
Metrics: ratio of achieved to optimal objective average objective value runtime
Baselines: Gurobi PDLP PDLP-GPU (cuOpt) trust-constr Difference of convex programming Fractional programming Random hit-and-run sampling No SVC ablation No CAD ablation
Builds on: Dykstra's projection algorithm Simultaneous Dykstra vector clipping Graph Attention Network
Closest papers by meaning
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
- Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth (ICML 2021 · similarity 0.85)
- Graph Neural Networks Inspired by Classical Iterative Algorithms (ICML 2021 · similarity 0.85)
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs (NeurIPS 2026 · similarity 0.85)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · similarity 0.85)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.