Edge-based sequential graph generation with recurrent neural networks

Graph generation with Machine Learning is an open problem with applica tions in various research fields. In this work, we propose to cast the gen erative process of a graph into a sequential one, relying on a node ordering procedu re. We use this sequential process to design a novel generative model compo sed of two recurrent neural networks that learn to predict the edges of gr aphs: the first network generates one endpoint of each edge, while the second network generates the other endpoint conditioned on the state of the first. We test o ur approach extensively on five different datasets, comparing with two well-know n baselines coming from graph literature, and two recurrent approaches, on e of which holds state of the art performances. Evaluation is conducted consider ing quantitative and qualitative characteristics of the generated samples. Results show that our approach is able to yield novel, and unique graphs originating from very different distributions, while retaining structural properties very similar to t hose in the training sample. Under the proposed evaluation framework, our ap proach is able to reach performances comparable to the current state of t he art on the graph generation task. Keywords: graph generation; recurrent neural networks; auto-regress ive models; deep learning 1. Introduction Graphs are well-known data structures that allow to store and acc ess relational data efficiently. Their use to represent information is ubiquit ous, especially in domains such as Biology [1], Chemistry [2] and Natural Langu age Processing [3]. In all these fields, as well as many others, data do no t exist in isolation, but are connected among themselves by complex relations hips. Hence, graphs are usually preferred to "flat" vectorial data whenever t here is the need to encode both relational knowledge and numerical information in a c oncise and compact way. This trend has been increasing especially since the advent of Graph Neural Net works [4] and contextual Neural Networks for Graphs [5], which paved the r oad for modern graph-based Deep Learning [6] models. As of today, Graph Neu ral Networks are used with success for predictive tasks such as semi-supervise d classification [7], link prediction [8], and text classification [9]. Besides being able to predict outcomes using graphs, one open and le ss studied problem in Machine Learning is how to instruct learning models t o generate graphs from arbitrary distributions. This implies that to learn a graph distribution, one cannot aim to explore the entire graph space, exc ept for trivial instances. Moreover, graph distributions of interest usua lly cover only a tiny portion of this large space.