  Large-scale graphs with node attributes are increasingly common in various
real-world applications. Creating synthetic, attribute-rich graphs that mirror
real-world examples is crucial, especially for sharing graph data for analysis
and developing learning models when original data is restricted to be shared.
Traditional graph generation methods are limited in their capacity to handle
these complex structures. Recent advances in diffusion models have shown
potential in generating graph structures without attributes and smaller
molecular graphs. However, these models face challenges in generating large
attributed graphs due to the complex attribute-structure correlations and the
large size of these graphs. This paper introduces a novel diffusion model,
GraphMaker, specifically designed for generating large attributed graphs. We
explore various combinations of node attribute and graph structure generation
processes, finding that an asynchronous approach more effectively captures the
intricate attribute-structure correlations. We also address scalability issues
through edge mini-batching generation. To demonstrate the practicality of our
approach in graph data dissemination, we introduce a new evaluation pipeline.
The evaluation demonstrates that synthetic graphs generated by GraphMaker can
be used to develop competitive graph machine learning models for the tasks
defined over the original graphs without actually accessing these graphs, while
many leading graph generation methods fall short in this evaluation.
