Graph Generation via Spectral Diffusion
Giorgia Minello Alessandro Bicciato Luca Rossi Andrea Torsello Luca Cosmo
In this paper, we present GRASP, a novel graph generative model based on 1)
the spectral decomposition of the graph Laplacian matrix and 2) a diffusion
process. Specifically, we propose to use a denoising model to sample
eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian
and adjacency matrix. Our permutation invariant model can also handle node
features by concatenating them to the eigenvectors of each node. Using the
Laplacian spectrum allows us to naturally capture the structural
characteristics of the graph and work directly in the node space while avoiding
the quadratic complexity bottleneck that limits the applicability of other
methods. This is achieved by truncating the spectrum, which as we show in our
experiments results in a faster yet accurate generative process. An extensive
set of experiments on both synthetic and real world graphs demonstrates the
strengths of our model against state-of-the-art alternatives.