  Searching for novel molecules with desired chemical properties is crucial in
drug discovery. Existing work focuses on developing neural models to generate
either molecular sequences or chemical graphs. However, it remains a big
challenge to find novel and diverse compounds satisfying several properties. In
this paper, we propose MARS, a method for multi-objective drug molecule
discovery. MARS is based on the idea of generating the chemical candidates by
iteratively editing fragments of molecular graphs. To search for high-quality
candidates, it employs Markov chain Monte Carlo sampling (MCMC) on molecules
with an annealing scheme and an adaptive proposal. To further improve sample
efficiency, MARS uses a graph neural network (GNN) to represent and select
candidate edits, where the GNN is trained on-the-fly with samples from MCMC.
Experiments show that MARS achieves state-of-the-art performance in various
multi-objective settings where molecular bio-activity, drug-likeness, and
synthesizability are considered. Remarkably, in the most challenging setting
where all four objectives are simultaneously optimized, our approach
outperforms previous methods significantly in comprehensive evaluations. The
code is available at https://github.com/yutxie/mars.
