Graphs are fundamental data structures which concisely capture the relationalstructure in many important real-world domains, such as knowledge graphs,physical and social interactions, language, and chemistry. Here we introduce apowerful new approach for learning generative models over graphs, which cancapture both their structure and attributes. Our approach uses graph neuralnetworks to express probabilistic dependencies among a graph's nodes and edges,and can, in principle, learn distributions over any arbitrary graph. In aseries of experiments our results show that once trained, our models cangenerate good quality samples of both synthetic graphs as well as realmolecular graphs, both unconditionally and conditioned on data. Compared tobaselines that do not use graph-structured representations, our models oftenperform far better. We also explore key challenges of learning generativemodels of graphs, such as how to handle symmetries and ordering of elementsduring the graph generation process, and offer possible solutions. Our work isthe first and most general approach for learning generative models overarbitrary graphs, and opens new directions for moving away from restrictions ofvector- and sequence-like knowledge representations, toward more expressive andflexible relational data structures.