Abstract Identifying molecules that exhibit some pre-specified properties is a difficult problem to solve. In the last few years, deep generative models have been used for molecule generation. Deep Graph Variational Autoencoders are among the most powerful machine learning tools with which it is possible to address this problem. However, existing methods struggle to capture the true data distribution and tend to be computationally expensive. In this work, we propose RGCVAE, an efficient and effective Graph Variational Autoencoder based on: (i) an encoding network exploiting a new powerful Relational Graph Isomorphism Network; (ii) a novel probabilistic decoding component. Compared to several State-of-the-Art VAE methods on two widely adopted datasets, RGCVAE shows State-of-the-Art molecule generation performance while being significantly faster to train. The Python code implementing RGCVAE is openly accessible for download at: https://github.com/drigoni/RGCVAE.