Discovering Graph Generation Algorithms
This approach addresses graph generation for researchers by offering interpretability and potential for out-of-distribution generalization, though it is incremental as it builds on evolutionary search and graph neural networks.
The paper tackles the problem of generating graphs by discovering algorithms instead of using traditional probabilistic or deep generative models, achieving competitive performance and sometimes perfect generalization.
We provide a novel approach to construct generative models for graphs. Instead of using the traditional probabilistic models or deep generative models, we propose to instead find an algorithm that generates the data. We achieve this using evolutionary search and a powerful fitness function, implemented by a randomly initialized graph neural network. This brings certain advantages over current deep generative models, for instance, a higher potential for out-of-training-distribution generalization and direct interpretability, as the final graph generative process is expressed as a Python function. We show that this approach can be competitive with deep generative models and under some circumstances can even find the true graph generative process, and as such perfectly generalize.