  We approach the graph generation problem from a spectral perspective by first
generating the dominant parts of the graph Laplacian spectrum and then building
a graph matching these eigenvalues and eigenvectors. Spectral conditioning
allows for direct modeling of the global and local graph structure and helps to
overcome the expressivity and mode collapse issues of one-shot graph
generators. Our novel GAN, called SPECTRE, enables the one-shot generation of
much larger graphs than previously possible with one-shot models. SPECTRE
outperforms state-of-the-art deep autoregressive generators in terms of
modeling fidelity, while also avoiding expensive sequential generation and
dependence on node ordering. A case in point, in sizable synthetic and
real-world graphs SPECTRE achieves a 4-to-170 fold improvement over the best
competitor that does not overfit and is 23-to-30 times faster than
autoregressive generators.
