# Simulated annealing for optimization of graphs and sequences

arXiv: https://arxiv.org/abs/2110.01384 · HTML: https://mlsanity.com/paper/2110.01384/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 69 references that are in the map.
- First posted on arXiv 1 Oct 2021.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Get To The Point: Summarization with Pointer-Generator Networks](https://mlsanity.com/paper/1704.04368/) (2017)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [Generating Sentences from a Continuous Space](https://mlsanity.com/paper/1511.06349/) (2015)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Grammar Variational Autoencoder](https://mlsanity.com/paper/1703.01925/) (2017)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [Optimization of Molecules via Deep Reinforcement Learning](https://mlsanity.com/paper/1810.08678/) (2018)
- [MoFlow: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/2006.10137/) (2020)
- [On Using Monolingual Corpora in Neural Machine Translation](https://mlsanity.com/paper/1503.03535/) (2015)
- [Sequence-to-Sequence Learning as Beam-Search Optimization](https://mlsanity.com/paper/1606.02960/) (2016)
- [Lagging Inference Networks and Posterior Collapse in Variational Autoencoders](https://mlsanity.com/paper/1901.05534/) (2019)
- [Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features](https://mlsanity.com/paper/1703.02507/) (2017)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [A Sensitivity Analysis of (and Practitioners' Guide to) Convolutional Neural Networks for Sentence Classification](https://mlsanity.com/paper/1510.03820/) (2015)
- [Generating Sentences by Editing Prototypes](https://mlsanity.com/paper/1709.08878/) (2017)
- [A Continuously Growing Dataset of Sentential Paraphrases](https://mlsanity.com/paper/1708.00391/) (2017)
- [EditNTS: An Neural Programmer-Interpreter Model for Sentence Simplification through Explicit Editing](https://mlsanity.com/paper/1906.08104/) (2019)
- [Paraphrase Generation with Deep Reinforcement Learning](https://mlsanity.com/paper/1711.00279/) (2017)
- [A Deep Generative Framework for Paraphrase Generation](https://mlsanity.com/paper/1709.05074/) (2017)
- [Neural Paraphrase Generation with Stacked Residual LSTM Networks](https://mlsanity.com/paper/1610.03098/) (2016)
- [Unsupervised Paraphrasing by Simulated Annealing](https://mlsanity.com/paper/1909.03588/) (2019)
- [Unsupervised Text Generation by Learning from Search](https://mlsanity.com/paper/2007.08557/) (2020)
- [Iterative Edit-Based Unsupervised Sentence Simplification](https://mlsanity.com/paper/2006.09639/) (2020)
- [Decomposable Neural Paraphrase Generation](https://mlsanity.com/paper/1906.09741/) (2019)
- [Discrete Optimization for Unsupervised Sentence Summarization with Word-Level Extraction](https://mlsanity.com/paper/2005.01791/) (2020)
- [A task in a suit and a tie: paraphrase generation with semantic augmentation](https://mlsanity.com/paper/1811.00119/) (2018)

## Built on by (most cited first, 5 of 5)

- [Learning Non-Autoregressive Models from Search for Unsupervised Sentence Summarization](https://mlsanity.com/paper/2205.14521/) (2022)
- [Let it Calm: Exploratory Annealed Decoding for Verifiable Reinforcement Learning](https://mlsanity.com/paper/2510.05251/) (2025)
- [Target-Guided Bayesian Flow Networks for Quantitatively Constrained CAD Generation](https://mlsanity.com/paper/2510.25163/) (2025)
- [Search and Learning for Unsupervised Text Generation](https://mlsanity.com/paper/2309.09497/) (2023)
- [Enhancing Quantum Memory Lifetime with Measurement-Free Local Error Correction and Reinforcement Learning](https://mlsanity.com/paper/2408.09524/) (2024)

## Abstract (arXiv)

Optimization of discrete structures aims at generating a new structure with the better property given an existing one, which is a fundamental problem in machine learning. Different from the continuous optimization, the realistic applications of discrete optimization (e.g., text generation) are very challenging due to the complex and long-range constraints, including both syntax and semantics, in discrete structures. In this work, we present SAGS, a novel Simulated Annealing framework for Graph and Sequence optimization. The key idea is to integrate powerful neural networks into metaheuristics (e.g., simulated annealing, SA) to restrict the search space in discrete optimization. We start by defining a sophisticated objective function, involving the property of interest and pre-defined constraints (e.g., grammar validity). SAGS searches from the discrete space towards this objective by performing a sequence of local edits, where deep generative neural networks propose the editing content and thus can control the quality of editing. We evaluate SAGS on paraphrase generation and molecule generation for sequence optimization and graph optimization, respectively. Extensive results show that our approach achieves state-of-the-art performance compared with existing paraphrase generation methods in terms of both automatic and human evaluations. Further, SAGS also significantly outperforms all the previous methods in molecule generation.