Research map / Learning theory and algorithms / Combinatorial and search optimization
Controlling Continuous Relaxation for Combinatorial Optimization
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 Continuous Relaxation Annealing (CRA), a rounding-free penalty annealing method for unsupervised GNN-based combinatorial optimization solvers (applied to PI-GNN), evaluated on MIS, MaxCut and diverse bipartite matching.
Problem
Unsupervised learning (UL)-based solvers for combinatorial optimization get trapped in local optima (e.g., trivial all-zero plateau on dense random regular graphs) and require artificial rounding of relaxed soft solutions back to discrete variables, which hurts robustness.
Approach
Adds a penalty term gamma*sum(1-(2p_i-1)^alpha) to the relaxed loss and anneals gamma from negative (smoothing the objective into a convex shape and escaping plateaus) to positive (forcing near-binary outputs), so the solution is effectively rounded during training without a post-hoc threshold.
Key results
- On MIS over RRG with d=20, CRA-PI-GNN (SAGE) reaches ApR 0.963 versus DGA 0.891 and PI-GNN (SAGE) 0.745 on 10,000-node graphs.
- On Gset MaxCut G14, CRA gets 0.994 ApR versus PI-GNN 0.988, RUN-CSP 0.960, and greedy 0.946.
- CRA-PI-GNN keeps non-trivial solutions on dense RRGs (d up to 80) where PI-GNN returns zero independent set (ApR 0.00).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add CRA to PI-GNN (SAGE) | PI-GNN (SAGE) · MIS 20-RRG, 10,000 nodes | ApR: 0.745\pm0.003 -> 0.963\pm0.001 | Helped |
| Add CRA to PI-GNN (SAGE) | PI-GNN (SAGE) · MIS 100-RRG, 10,000 nodes | ApR: 0.000\pm0.000 -> 0.924 \pm 0.001 | Helped |
| Add CRA to PI-GNN | PI-GNN · MaxCut Gset G14, G15, G22, G49, G50, G55, G70 | ApR | Helped |
| Use CRA-PI-GNN instead of PI-GNN | PI-GNN · MIS problems on d-RRG across degrees | independent set density | Helped |
| Use CRA-PI-GNN instead of PI-GNN | PI-GNN · MaxCut problems on d-RRG across degrees | cut ratio | Helped |
| Use CRA-PI-GNN instead of PI-GNN | PI-GNN · MIS learning across d=3, 5, 20, 100 | epochs to reach solution | Helped |
Surprising findings
- Vanilla PI-GNN collapses to the trivial all-zero plateau on MIS for degrees d>=20 and yields ApR 0.000 on 100-RRG, contrary to earlier claims that it only struggles on harder cases.
- Binary cross-entropy penalty is unusable for positive gamma because its gradient diverges at 0 and 1.
Limitations
- Hyperparameters (gamma(0), scheduling rate, curve rate alpha) were fixed with minimal tuning and may need problem-specific tuning.
- Runtime depends on GNN optimizer and annealing rate; on small ER instances CRA is slower than iSCO and less effective on small problems.
Experimental setup
Datasets: random regular graphs Erdos-Renyi graphs Gset Cora citation network (for DBM) SATLIB
Benchmarks: Gset MaxCut random regular graph MIS Erdos-Renyi MIS diverse bipartite matching (Matching-1, Matching-2) DIMES MIS benchmarks
Metrics: approximation ratio independent set density cut ratio runtime
Baselines: PI-GNN random greedy algorithm degree-based greedy algorithm RUN-CSP Goemans-Williamson SDP EGN Meta-EGN DIMES iSCO Gurobi KaMIS
Builds on: PI-GNN Erdős Goes Neural Meta-EGN penalty method
Closest papers by meaning
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · similarity 0.86)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.84)
- Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization (NeurIPS 2024 · similarity 0.83)
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances (ICLR 2024 · similarity 0.83)
- COExpander: Adaptive Solution Expansion for Combinatorial Optimization (ICML 2025 · similarity 0.83)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.83)
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.