Research map / Learning theory and algorithms / Combinatorial and search optimization
Are Graph Neural Networks Optimal Approximation Algorithms?
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.
Proposes OptGNN, a message-passing GNN obtained by unrolling gradient descent on a penalized vector-form SDP for Max-CSPs, claimed to match UGC-optimal approximation, and evaluates it unsupervised on Max-Cut, Min-Vertex-Cover and Max-3-SAT.
Problem
Designing neural architectures for combinatorial optimization that are both efficient and capable of capturing algorithms with optimal worst-case approximation guarantees (UGC-optimal SDP-based algorithms for Max-CSPs).
Approach
Show that gradient descent on a quadratically penalized vector-form SDP for Max-CSPs is a message-passing algorithm on the constraint graph; parameterize its update with learnable matrices per layer to obtain OptGNN, trained unsupervised on the penalized Lagrangian and rounded with random hyperplanes.
Key results
- On Max-Cut across eight datasets, OptGNN clearly outperforms greedy and is competitive with Gurobi limited to 0.1s (e.g., ER 16387.46 vs 16476.72 for Gurobi 0.1s).
- On random Max-3-SAT (N=100, r=4.00), OptGNN leaves 4.46 unsatisfied clauses versus 5.46 for ErdosGNN and 6.85 for autograd SDP, but does not beat WalkSAT (0.14 with 100 restarts) or survey propagation (3.32).
- On GSET Max-Cut, OptGNN outperforms the SDP and greedy baselines but does not outperform ANYCSP, which the authors note is the neural state of the art.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OptGNN instead of Greedy | Maximum Cut · BA, ER, HK, WC, ENZYMES, COLLAB, REDDIT-M-12K, REDDIT-M-5K | average cut size: 2197.99 vs 1255.22 (BA); 16387.46 vs 8622.34 (ER) | Helped |
| Use OptGNN instead of Gurobi 0.1s | Maximum Cut · BA, ER, HK, WC, ENZYMES, COLLAB, REDDIT-M-12K, REDDIT-M-5K | average cut size: 2197.99 vs 2208.11 (BA); 568.00 vs 567.71 (REDDIT-M-12K) | Mixed |
| Use OptGNN instead of ErdősGNN | Max-3-SAT · N=100; clause ratios 4.00, 4.15, 4.30 | unsatisfied clauses | Helped |
| Use OptGNN instead of Autograd SDP | Max-3-SAT · N=100; clause ratios 4.00, 4.15, 4.30 | unsatisfied clauses: 4.46$^{\pm \text{1.68}}$ vs 6.85$^{\pm \text{2.33}}$ (r=4.00) | Helped |
| Use OptGNN instead of the low-rank SDP solver | Max-3-SAT · N=100; clause ratios 4.00, 4.15, 4.30 | unsatisfied clauses: 4.46$^{\pm \text{1.68}}$ vs 12.38$^{\pm \text{1.06}}$ (r=4.00) | Helped |
| Use OptGNN instead of WalkSAT (100 restarts) | Max-3-SAT · N=100; clause ratios 4.00, 4.15, 4.30 | unsatisfied clauses: 4.46$^{\pm \text{1.68}}$ vs 0.14$^{\pm\text{0.36}}$ (r=4.00) | Hurt |
| Use OptGNN instead of Survey Propagation | Max-3-SAT · N=100; clause ratios 4.00, 4.15, 4.30 | unsatisfied clauses: 4.46$^{\pm \text{1.68}}$ vs 3.32$^{\pm\text{0.81}}$ (r=4.00) | Hurt |
Surprising findings
- OptGNN does not beat WalkSAT or Survey Propagation on random Max-3-SAT, despite the theoretical optimality claim.
- OptGNN does not outperform ANYCSP on GSET, the best neural baseline in the comparison.
Limitations
- The optimality guarantee is worst-case and requires embedding dimension on the order of the instance size, while practical runs use small fixed dimensions where the low-rank SDP is NP-hard.
- Empirically, OptGNN does not beat strong local search or the best neural baseline (ANYCSP) on several benchmarks.
- The PAC-learnability bound is a perturbation analysis that the authors acknowledge does not fully explain the empirical success of backpropagation.
Experimental setup
Datasets: Erdos-Renyi random graphs BA HK WC ENZYMES COLLAB REDDIT-M-12K REDDIT-M-5K GSET forced RB instances (RB200, RB500) random 3-SAT
Benchmarks: Max-Cut on BA/ER/HK/WC/ENZYMES/COLLAB/REDDIT graphs GSET Min-Vertex-Cover on forced RB instances random Max-3-SAT with N=100
Metrics: cut size approximation ratio unsatisfied clauses runtime
Baselines: Greedy Gurobi WalkSAT Survey Propagation ErdosGNN Autograd SDP Low-Rank SDP ANYCSP Goemans-Williamson
Builds on: Goemans-Williamson SDP relaxation Unique Games Conjecture optimal SDP for Max-CSP ANYCSP Erdos Goes Neural
Closest papers by meaning
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.89)
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy (NeurIPS 2024 · similarity 0.89)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.89)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.88)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.88)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.88)
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.