Research map / Probabilistic and scientific modeling / Variational and generative sampling
Variational Annealing on Graphs for Combinatorial Optimization
Sebastian Sanokowski, Wilhelm Franz Berghammer, Sepp Hochreiter, Sebastian Lehner
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add annealed entropy regularization (T0 > 0 vs T0 = 0) (ablation) | VAG-CO · MVC RB-100 | relative error | Improved |
| Add subgraph tokenization (k=5) vs none (ablation) | VAG-CO · MVC RB-100 | relative error | Improved |
| Increase subgraph tokenization size k from 1 to 10 (ablation) | VAG-CO · MVC RB-100 | AR* | Improved |
| Use autoregressive VAG-CO instead of mean-field MFA-Anneal | VAG-CO · MIS ENZYMES | AR-hat: 0.968 -> 0.9863 | Improved |
| Use VAG-CO instead of MFA-Anneal | VAG-CO · MIS COLLAB | AR-hat: 0.917 -> 0.993 | Improved |
| Use VAG-CO instead of MFA-Anneal | VAG-CO · MaxCl ENZYMES | AR-hat: 0.806 -> 0.943 | Improved |
| Use VAG-CO instead of MFA: CE | VAG-CO · MIS ENZYMES | AR*: 0.9875 -> 0.9960 | Improved |
| Use VAG-CO instead of MFA-Anneal: CE | VAG-CO · MIS COLLAB | AR*: 0.9991 -> 0.9988 | No clear effect |
| Use VAG-CO instead of MFA: CE | VAG-CO · MVC COLLAB | AR*: 1.00021 -> 1.0017 | Hurt |
| Use VAG-CO instead of MFA-Anneal: CE | VAG-CO · MaxCl ENZYMES | AR*: 0.9921 -> 0.987 | Hurt |
| Use VAG-CO instead of Meta-EGN | VAG-CO · MVC TWITTER | AR*: 1.019 -> 1.0024 | Improved |
| Use VAG-CO instead of GFlowNet | VAG-CO · MaxCut BA 200-300 | average cut value: 704.30 -> 722.31 | Improved |
Closest papers by meaning
- Regularized Langevin Dynamics for Combinatorial Optimization (ICML 2025 · similarity 0.86)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.86)
- A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization (ICML 2024 · similarity 0.86)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.86)
- $\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization (NeurIPS 2025 · similarity 0.85)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.85)
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.
