Research map / Learning theory and algorithms / Combinatorial and search optimization
ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems
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.
Relaxes Max-k-Cut to a probability-simplex continuous problem, optimizes it with a pre-trained-then-fine-tuned GNN, and recovers discrete solutions via random categorical sampling with an expected-objective-equality guarantee.
Problem
Max-k-Cut with arbitrary-sign edge weights is NP-hard; existing relaxations lack guarantees that relaxed and discrete objective values match, and exact/SDP/heuristic/L2O methods scale poorly to large graphs.
Approach
Relax the one-hot constraints to the Cartesian product of probability simplices, optimize the relaxed objective with a GNN parametrization using pre-train + per-instance fine-tune, and round by categorical sampling, which preserves the objective in expectation.
Key results
- On Gset Max-Cut G1-G21 ROS reaches comparable cut values to baselines in about 1.5-3 s versus ~180 s for ANYCSP and hundreds of seconds for GW/Genetic.
- On weighted perturbed G70-G81 (scale up to 20,000 nodes), ROS-vanilla and ROS solve in seconds, while MD is ~15x slower at N=10,000 and PI-GNN takes ~100x longer.
- On random 3-regular/5-regular N=10,000 Max-3-Cut, ROS-vanilla achieves 24413 vs ANYCSP 24930 and MD 23341 (ROS 24086), showing ROS is competitive but not uniformly best in cut value.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ROS instead of ANYCSP | Max-k-Cut on random regular graphs · Random regular graphs, k=2 and k=3, N=100 to 10,000 | cut value: 128.20_{\pm 2.82} vs 131.65_{\pm 3.35}; 24085.95_{\pm 21.88} vs 24929.80_{\pm 7.53} | Hurt |
| Use ROS instead of MD | Max-k-Cut on weighted Gset graphs · Weighted Gset, noise [0, 10], G70/G72/G77/G81, k=2 and k=3 | cut value: 45490.21 -> 46707.60; 78065.07 -> 82450.68 | Helped |
| Remove pre-training from ROS (ablation) | ROS · Random regular graphs | cut value: 128.20_{\pm 2.82} -> 132.80_{\pm 1.99}; 240.30_{\pm 2.59} -> 243.20_{\pm 1.80} | Helped |
| Add pre-training to ROS-vanilla (ablation) | ROS · Random regular graphs and Gset | computational time: approximately 1.5 times; around 40% | Helped |
| Remove pre-training from ROS (ablation) | ROS · Gset benchmark | cut value | No clear effect |
Surprising findings
- ROS-vanilla (no pre-training) gets slightly higher cut values than pre-trained ROS on many instances, with pre-training trading some quality for speed.
- ANYCSP, a strong unweighted baseline, returns very poor cut values on weighted Gset perturbations (even negative values for G72), indicating it cannot handle weighted instances.
Limitations
- The sampling guarantee is only in expectation; the method runs T=100 samples and keeps the best, with no quality guarantee for the best sample.
- The relaxed problem is non-convex and solved only locally by the GNN, so global optimality of the relaxation is not guaranteed.
- Some benchmark entries are N/A due to 30-minute timeouts for baselines, and comparisons on some tables are against a limited baseline set.
Experimental setup
Datasets: random regular graphs (training, N=100) Gset COLOR Bitcoin-OTC
Benchmarks: random regular graphs (N=100,1000,10000) Gset (weighted perturbations and unweighted) COLOR anna/david/huck Bitcoin-OTC
Metrics: cut value computational time
Baselines: GW BQP Genetic MD (mirror descent) PI-GNN ECO-DQN ANYCSP MOH LPI
Builds on: Goemans-Williamson SDP relaxation PI-GNN ANYCSP Lovász extension
Closest papers by meaning
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs (NeurIPS 2026 · similarity 0.88)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.88)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.88)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.88)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.88)
- Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.87)
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.