  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.
