SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators
This addresses graph generation for applications requiring efficient and high-fidelity modeling, offering a novel approach that is not incremental.
The paper tackles the problem of graph generation by proposing SPECTRE, a one-shot generator that uses spectral conditioning to model graph Laplacian spectra, overcoming expressivity and mode collapse issues. It achieves a 4-to-170 fold improvement in modeling fidelity over competitors and is 23-to-30 times faster than autoregressive generators.
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.