SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion
Junwei Su, Shan Wu · 2025
Read SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion by Junwei Su, Shan Wu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14352.txt.
Introduction
Junwei Su and Shan Wu propose a new way to build graphs with computers in a 2025 paper. Graph models that grow networks step by step can create useful fake data. Yet they need huge amounts of memory for large graphs. They also fail to make graphs of sizes they never saw in training.
Their method, called SBGD, first splits a graph into blocks based on common real world patterns. The model then works in that smaller block space instead of the full graph. Tests show memory use fell by up to six times. Quality stayed as good as or better than older methods. The block form also let the model make graphs of new sizes more reliably.
Catalog record
| CREATOR | Junwei Su, Shan Wu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-14352
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion Junwei Su, Shan Wu Abstract Graph diffusion generative models (GDGMs) have emerged as powerful tools for generating high-quality graphs. However, their broader adoption faces challenges in scalability and size generalization . GDGMs struggle to scale to large graphs due to their high memory requirements, as they typically operate in the full graph space, requiring the entire graph to be stored in memory during training and inference. This constraint limits their feasibility for large-scale real-world graphs. GDGMs also exhibit poor size generalization, with limited ability to generate graphs of sizes different from those in the training data, restricting their adaptability across diverse applications. To address these challenges, we propose the stochastic block graph diffusion (SBGD) model, which refines graph representations into a block graph space. This space incorporates structural priors based on real-world graph patterns, significantly reducing memory complexity and enabling scalability to large graphs. The block representation also improves size generalization by capturing fundamental graph structures. Empirical results show that SBGD achieves significant memory improvements (up to 6 × \times ) while maintaining comparable or even superior graph generation performance relative to state-of-the-art methods. Furthermore, experiments demonstrate that SBGD better generalizes to unseen graph sizes. The significance of SBGD extends beyond being a scalable and effective GDGM; it also exemplifies the principle of modularization in generative modeling, offering a new avenue for exploring generative models by decomposing complex tasks into more manageable components. 1 Introduction Graphs are a fundamental mathematical construct used to represent relational data, consisting of nodes and edges that depict pairwise relationships. This concept is widely applied across various fields, such as social networks ( Grover et al. 2019 ; Wang et al. 2018 ) , program synthesis ( Brockschmidt et al. 2018 ) , and neural architecture search ( Xie et al. 2019 ; Lee et al. 2021 ) . A key challenge in this domain is the generation of new graphs that mirror the properties of the observed ones. For example, in drug discovery, this involves creating graphs that represent the structural composition of specific proteins ( Simonovsky & Komodakis 2018 ; Li et al. 2018 ; Preuer et al. 2018 ) or molecules. Given its significance, the graph generation problem has a long history of research, with rule-based random graph models traditionally dominating the field ( Barabási & Albert 1999 ; Holland et al. 1983 ; Erdős et al. 1960 ; Newman et al. 2002 ) . A prime example of such a model is the Stochastic Block Model (SBM) ( Holland et al. 1983 ) , which is based on the observation that real-life graphs often consist of densely connected blocks of vertices exhibiting similar behaviors ( Abbe 2018 ; Newman et al. 2002 ; Newman & Girvan 2004 ; Newman 2006 ; Karrer & Newman 2011 ; Cherifi et al. 2019 ; Su & Marbach 2022 ) . This block structure reflects community-like patterns where nodes within the same block are more likely to connect, while inter-block connections are sparser. However, these rule-based models face significant limitations: they fail to capture the complex and nuanced distribution of graph-structured data observed in real-world problems ( Niu et al. 2020 ) . As a result, the focus has shifted towards deep learning-based methods that can model more intricate graph properties. Among these, graph diffusion generative models (GDGMs) have emerged as a promising solution, showing impressive performance in graph generation ( Niu et al. 2020 ; Vignac et al. 2022 ; Jo et al. 2022 ) . GDGMs belong to the family of diffusion-based generative models (also referred to as the score-based generative models), which model the data generation process through a diffusion mechanism operating within the data space. These models consist of two key components: (1) a forward process that gradually degrades the data into a simple known distribution, such as standard Gaussian, and (2) a neural network that reverses this process to reconstruct the original data (see Sec. 2 for more details). Diffusion models are known for their ability to generate high-quality samples and have been successfully applied in domains like image and audio synthesis ( Dhariwal & Nichol 2021 ; Rombach et al. 2022 ; Nichol et al. 2021 ; Yang et al. 2023 ) . Extending this framework to graph data has produced promising results, as these models are capable of capturing the complex distributions and structures characteristic of graphs. Challenges and Limitations. Despite their success, existing GDGMs face two primary challenges: scalability and size generalization. First, scalability remains a significant hurdle due to the high memory demands of GDGMs. These models currently model the diffusion generative process at the graph level, requiring the entire graph — including its structure and features — to be stored in memory during the process. As the graph size increases, memory usage scales quadratically with the number of nodes, making these models impractical for large-scale graphs, such as those found in social networks or molecular simulations, where graphs can contain millions of nodes and edges ( Hamilton et al. 2018 ) . Second, GDGMs face difficulties with size generalization. They are typically trained on graphs of a fixed size and often fail to generate graphs that differ significantly in size from those encountered during training. This limitation restricts their applicability in scenarios where graph sizes can vary widely, such as in molecular structures ( Wieder et al. 2020 ) . 1.1 Contribution and Significance To address the challenges outlined, we propose the Stochastic Block Graph Diffusion (SBGD) model, which incorporates a structural prior based on the block-based organization commonly observed in real-world graphs (see Figure 4 for an illustration). By leveraging this block structure, SBGD captures community-like patterns and represents the graph in a block space. Performing the diffusion process within this block space significantly reduces memory usage, enabling the generation of larger graphs with reduced memory overhead (see Table 1 for a comparison of memory complexity between our method and existing GDGMs). Additionally, this block-based representation enhances the model’s ability to generalize across graphs of varying sizes, as smaller, fundamental building blocks can be recombined in different configurations to generate graphs at different scales. Empirical evaluations on both real-world and synthetic datasets show that SBGD achieves up to a 6 \times improvement in memory efficiency, while maintaining comparable or superior generative performance relative to state-of-the-art GDGMs. This makes SBGD highly scalable for large graphs. Furthermore, experiments on size generalization demonstrate that SBGD exhibit better size generation, particularly exceling at generating graphs larger than those seen in the training set. Our ablation study on block graph size also reveals that smaller block representations initially improve performance, but excessively small blocks can degrade generative quality. Moreover, experiments show that block graph size also impacts the model’s size generalization ability. These findings suggest the existence of an optimal block size, with granularity depending on the data’s properties and the specific generative task. This insight opens up promising avenues for future research. Overall, these results highlight the advantages of incorporating a structural prior through block representation, allowing SBGD to overcome key limitations of existing diffusion-based models. This approach provides a more flexible, scalable, and efficient solution to graph