In recent years, deep learning researchers have been increasingly interested in developing architectures able to operate on data abstracted as graphs, i.e., Graph Neural Networks (GNNs). At the same time, there has been a surge in the number of commercial AI systems deployed for real-world applications. At their core, the majority of these systems are based on black-box deep learning models, such as GNNs, greatly limiting their accountability and trustworthiness. The idea underpinning this paper is to exploit the representational power of graph variational autoencoders to learn an embedding space where a “convolution” between local structures and latent vectors can take place. The key intuition is that this embedding space can then be used to decode the learned latent vectors into more interpretable latent structures. Our experiments validate the performance of our model against widely used alternatives on standard graph benchmarks, while also showing the ability to probe the model decisions by visualising the learned structural patterns.