SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion
Authors: Junwei Su
shan Wu
Venue: ICML 2025 poster (2025)
Keywords: graph generation
scalable
size generalization
Primary area: deep_learning
TL;DR: This paper improves the score-based graph generative model via a structural prior.

Abstract: Graph diffusion generative models (GDGMs) have emerged as powerful tools for generating high-quality graphs. However, their broader adoption faces challenges in \emph{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; \emph{it also exemplifies the principle of modularization in generative modelling, offering a new avenue for exploring generative models by decomposing complex tasks into more manageable components.}

SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion
Junwei Su
Shan Wu?
Abstract
1. Introduction
Graph diffusion generative models (GDGMs) have emerged as powerful tools for generating high-quality graphs. However, their broader adop- tion faces challenges in scalability and size gen- eralization. GDGMs struggle to scale to large graphs due to their high memory requirements, they typically operate in the full graph space, requiring the entire graph to be stored in mem- ory during training and inference. This constraint limits their feasibility for large-scale real-world graphs. GDGMs also exhibit poor size general- ization, with limited ability to generate graphs of sizes different from those in the training data, re- stricting their adaptability across diverse applica- tions. To address these challenges, 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, signifi- cantly reducing memory complexity and enabling scalability large graphs. The block represen- tation also improves size generalization by cap- turing fundamental graph structures. Empirical results show that SBGD achieves significant mem- ory improvements (up to 6x) while maintaining comparable or even superior graph generation per- formance relative to state-of-the -f-the--rt methods. Fur- thermore, experiments demonstrate that SBGD better generalizes unseen graph sizes. The sig- nificance of SBGD extends beyond being scal- able and effective GDGM; it also exemplifies the principle of modularization in generative model- ing, offering a new avenue for exploring genera- tive models by decomposing complex tasks into more manageable components.
Graphs are 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 mroeein((Smmnnvve) & Komodakis, 2018; Li et al., 2018; Preuer et al., 2018) or molecules.
Given its significance, the graph generation problem has long history of research, with rule-based random graph models traditionally dominating the field (Barabási & Al- bert, 1999; Holland et al., 1983; Erdós et al., 1960; New- man et al., 2002). A prime example of such a model is the Stochastic Block Model (SBM) (Bollad et al., 1983), which is based on the observation that real-life graphs often con- sist 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 struc- ture reflects community 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 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; Vignae et al., 2022; Jo et al., 2022).
'School of Computing and Data Science, University of Hong Kong "School of Resources and Environmental Engineering, Hefei University of Technology. Correspondence to: Junwei Su <jun- >.
GDGMs belong the family of Liffusion-based generative models (also referred to the score-based generative mod- els), which model the data generation process through a diffusion mechanism operating within the data space. These models consist two key components: (1) a forward pro- cess that gradually degrades the data into simple known
weisu@Cconeet.hhie hk..he.etttkuk.......... Shan Wu
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Stochastic Block Graph Diffusion
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 re- sults, as these models are capable of capturing the complex distributions and structures characteristic of graphs.
ticularly exceling generating graphs larger than those seen in the training set. Our ablation study block graph size also reveals that smaller block representations initially improve performance, but excessively small blocks can de- grade generative quality. Moreover, experiments show that block graph size also impacts the model's 's size generalization ability. These findings suggest the existence of an optimal block size, with granularity depending on the data's proper- ties and the specific generative task. This insight opens up promising avenues for future research.
Overall, these results highlight the advantages of incorporat- ing structural prior through block representation, allowing SBGD to overcome key limitations of existing diffusion- based models. This approach provides a more flexible, seal- able, and efficient solution to graph generation. Furthermore. it exemplifies the principle of modularization in generative modeling, offering novel way to explore generative mod- els by decomposing complex tasks into more manageable components.
Challenges and Limitations. Despite their success, exist- ing 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 mod- els 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).
2. Background and Motivation
In this section, we present a brief introduction to diffusion- based generative models, graph diffusion generative models, and the role of block structure in graphs. We defer some of the technical details to the appendix due to page limitation.
2.1. Diffusion Generative Models.
DGMs (Song & Ermon, 2019; Song et al., 2020b; Song & Ermon, 2020; Sohl-Dickstein et al., 2015; Song et al., 2020a) belong to the large family of latent variable models. It models the data generation process as a transition pro- cess in the latent space and primarily comprises two main components: a noise model (forward process) and a denois- ing neural network (backward process). The noise model I gradually corrupts data point x to form sequence of increasingly noisy data points (xy). It adheres to a Markovian structure, formulated as:
1.1. Contribution and Significance
To address the challenges outlined, we propose the Stochas- tie Block Graph Diffusion (SBGD) model, which incorpo- rates 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, en- abling the generation of larger graphs with reduced memory overhead (see Table 1 for comparison of memory complex- ity between our method and existing GDGMs). Additionally, this block-based representation enhances the model's 's abil- ity to generalize across graphs of varying sizes, as smaller, fundamental building blocks can be recombined in different configurations to generate graphs at different scales.
T
xy.,)) = P(x])x) II P(x
In most cases, Gaussian noise is used for the forward pro- cess. This amounts to a Markov chain that gradually adds Gaussian noise to the data according to a variance schedule $ .r:
Empirical evaluations on both real-world and synthetic datasets show that SBGD achieves up to 6x improve- ment 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, par-
P(xx|xx-) :- N(x-; / 1 3,x;-1, BeI), PP Pxxx|(x) N(xi; 0;X0, (1 - a;))),
where a := 1 - Br and ā. := I 1 ag. Then, the goal of the backward process is to learn a (denoising) neural network so (0 is the learnable parameter) to reverse this noising process.
2

---

Stochastic Block Graph Diffusion
(a) Example graph with random layout.
(b) Example graph with block structure highlighted.
(c) Adjacency matrix of the example graph.
Figure 1. Visualization of an example graph in different layouts and its matrix representation. Fig. ((a) is visualization the example
graph with random layout. Fig. 1(b) visualization of the example graph with Kamada Kawai layout (Kamada et al., 1989) and the blocks are highlighted with different colours. Fig. 1(b) is a visualization of the adjacent matrix of the example graph where the dense area
the diagonal region of the matrix represent the blocks in the graph.
Graph Diffusion Generative Methods
SBGM (Niu et al., 2020)
SDE (Jn al., 2022)
DiGress (Vignac al., 2022)
SRGD (ours)
Memory Complexity
O(N
O(N² NF)
OIN + NF)
OCC O'C* + CFF
Computation Complexity
OTT
O NF))
O + NF))
O(T + RCF))
Table I. A summarized comparison of existing graph diffusion generative model. N is the number of vertices and F is the dimension of the feature. C' is the size of the block graph (which much smaller than N) and & is the numher of blocks from the graph (kC' is the size of the graph). T is the number of diffusion steps used in the generation process. It is evident from the table that our method offers better memory complexity while keeping the same computation complexity.
To generate new samples, a point is sampled from the prior (convergent) distribution P(xx) (typically standard Gaus- sian) and iteratively denoised by the neural network so until it recovers the original data distribution. This follows series of (reverse) state transitions.
graph generation by considering the entire graph at each step, encompassing both the structure and feature matrix.
2.2. Block Structure in Graphs.
In real-life graphs, a prominent feature is their block (com- munity structure) (Deshpande al., 2018; Holland et al., 1983), where vertices within the same block display dense connections and exhibit similar behavioural traits (i.c., sim- ilar feature distributions). This contrasts sharply with ver- tices from different blocks, which are sparsely connected, highlighting the distinct boundaries between these units. For example, in social networks, groups of friends form tightly connected communities. In citation networks, papers the same research domain cite each other frequently. In bio- logical networks, where certain proteins or genes interact heavily within specific functional modules. Block structures are cornerstone of graph analysis (Newman et al., 2002; Newman, 2006) and play a critical role in many graph learn- ing algorithms, such as DeepWalk (Perozzi et al., 2014) and ClusterGCN (Chiang et al., 2019). The block structure simplifies graph representation, highlighting modularity and reducing complexity by focusing inter- and intra-block interactions.
80
XT
XT
X0-
This is achieved by using sampling rules such as those spec- ified in DDPM/DDIM (Ho et al., 2020; Song et al., 2020a).
GDGMs represent important extension of DDMs to graph data and have demonstrated empirical success in graph gen- eration tasks. Due to the inherent complexity of graph data, which consists of both structural and feature information, existing GDGM extensions rely on matrix representations of the graph. They model the graph generation process using system of stochastic processes that capture the depen- dency between the structure and features. This is typically achieved by incorporating underlying models, such as graph neural networks, to model these interdependencies. The stochastic process used in GDGMs can either be stochas- tic differential equation (for continuous data spaces) (Jo et al., 2022) or a discrete Markov chain (for discrete data spaces) (Vignac al., 2022). Both approaches model the
3

---

To apply block decomposition, partition the nodes into I non-overlapping groups, V [Vi,..., Vel, where V, con- tains the nodes in the i-th partition (see the supplementary material for partition details). The subgraph induced by Stochastic Block Graph Diffusion
P(C
c
Decompose
Sample
QC coty
S6, Spp $
t 2
Figure 2. The overview of SBGD. (1) incoming graphs decomposed into block graphs where vertices share similar properties. (2) sample from the set of block graphs and conduct separate diffusion. The noise model is defined by the distribution P(.) (3) The denoising
network se, se. s learns to predict the clean graph, including the inter-connections, from c( and c! During inference, the predicted distribution is combined with Q(c(t-1) GG ( in order to sample discrete ((t-1) from this distributions.
3. Stochastic Block Graph Diffusion (SBGD)
partition, have set C of l block graphs
In this section, we introduce the SBGD model, designed to overcome the scalability and size generalization challenges of traditional GDGMs by incorporating block structure prin- ciples into the diffusion-based graph generation framework. SBGD performs the diffusion process within a compact block space instead of the full graph space, thereby reduc- ing memory complexity and enhancing size generalization. Fig. 2 is an overview of SBGD.
C = [c Cyl
- 9[V
= [IA,, (A Xx)).
where A, and X, are the adjacency matrix and feature trix of block graph C,, respectively. The complete adjacency matrix of G can be partitioned into h2 submatrices:
A
A
3.1. Block Graphs Representation
A
A
A
Ak
Let G = EV,E,X X) denote an undirected graph, where == (1.2....,NN) .N 3 is the set of N nodes, & C V x V represents the edges, and
NxF is the node attribute matrix, where each row X2 contains the feature vector for node Alternatively,
A : 0
A ik
A
A
represent G two-tuple G = (), where A is the N x N adjacency matrix, with Aji.j] = if there is an edge between nodes and j. and 0 otherwise. These representations are used interchangeably to accommodate different aspects of the generation process. For any matrix H, we denote its transpose as H' and its value at time step as (4).
A
A&1
0
Here, A consisting of all diagonal blocks of A and each diagonal block A; D&] [V:] adjacency matrix con- taining the links within C.. A is the matrix consisting of all off-diagonal blocks of A and Aij contains the links be- tween two partitions V; and V,, Then, the graph G can be represented by two tuples ((Ca), (Aij}) where {C.} is the set of block graphs and {Aa} is set of adjacency matrix among block graphs with the sparse connection.
V; is denoted as the block graph C, = G[V.]. Given this
3.2. Diffusson Frameworks
Forward process. Based on the block graph decomposi- tion, we further factorize the distribution of feature matrix

---

Stochastic Block Graph Diffusion
and adjacency for the forward process as:
block graphs C, C, from the block graph set and aims to predict the clean two-block graph U[C.) U induced by C., Cj. Then, we recover/model the sparse interaction be- tween these two block graphs with another neural sC Cý).
(((()))(1-)) = II
P(C c xE[R]
"
II (JER
(- PIA
(3.1)
This amounts to the following objective,
The complete distribution of the graph is decomposed into two components where the first component is the distribu- tion of the block graph and the second component is the distribution of the interactions among the block graphs. For the first component, we further decompose the block graph distribution into adjacency matrix and feature matrix, i.e,
L = Ec,., [IIsa(Ct, -A5-A151 12
The complete training objective given by,
C CA, + CA, + fx, + Lx, + LI.
Sampling and Implementation. Once the network S0.50, S& for the graph structure, features, and cross-block graph interactions are trained, we follow the standard pro- cedure for sampling from diffusion model. This involves first creating a set of block graphs using sΦ and so, and then recovering their interactions using Sø. For our implemen- tation, we use the commonly employed graph transformer architecture for all of these networks. Pseudo-code for train- ing and sampling is provided in Appendix B, along with additional technical details of the implementation.
( c((- = P (1) X
(t- IPAA
(8) A D)
Then, we adopt the existing approaches from (Jo et al., 2022; Vignac et al., 2022) to model the forward diffusion as system of stochastic process. We apply Gaussian noise to X and A in the forward process, i.e.,
P(A (4) A ) (9) - ()AA)) 1-1 II P(X x (1" - N(X (0) /(1 (1--111) xA "-) ,,11)
For the second component of Eq. 3.1, we note that the interactions Ai between the block graphs are sparse (see
3.3. Theoretical Discussion.
Fig. 4), and light-weight module should be sufficient to capture this information. In addition, the interconnection A, depends on the choice of block graphs. To capture such a dependency, we propose to model these interactions matrix with another neural network that takes in two (generated) block graphs C, Cj as input and generated the interaction among block graph C, and C2 output.
In this section, we present a theoretical discussion of our proposed method. Our analysis focus on the memory com- plexity and performance benefit of block representation, and the benefit of using analogue bit.
Memory Analysis. Existing denoising diffusion-based ap- proaches for graph generation operate directly on the com- plete graph space, which Ieads to a memory complexity of O(N2), where N is the number of vertices in the graph. This quadratic complexity arises because the diffusion pro- cess needs to track pairwise interactions correlations between every pair of vertices, making it highly memory- intensive for large-scale graphs. In contrast, our proposed SBGD approach reduces memory requirements by decom- posing the graph into smaller block graphs, each of size C. where C & N. As a result, the memory complexity is reduced (C2)), which can lead to significant memory savings, especially when dealing with very large graphs. A memory complexity comparison among existing methods is provided in Table 1.
Training Objective. The core idea of the denoising diffu- sion model is to use neural networks to model the reverse (denoising) process for facilitating generation. With the de- composition above, we need two separate denoising neural networks so and 5 (0 and sb are learnable parameter) to model the denoising processes for the graph structure and feature correspondingly. Instead of directly learning neu- ral net to model the transition from / to t --1 1, we adopt the idea from (Vignac et al., 2022; Chen et al., 2022) and learn (or the noise from c,²).
neural network to predict c This amounts to,
so (0) ((!) ()) A (0)) |].
Advantage for Distributed Training, This block-wise rep- resentation not only reduces the memory footprint but also provides several advantages in the context of distributed training. By partitioning the graph into smaller, subgraphs (blocks), the model can process each pair of block graphs separately or in parallel, allowing for more efficient dis- tributed computation. Each computational node or device in a distributed system can handle smaller subproblems, reduc- ing the memory load per node and mitigating bottlenecks associated with memory constraints.
LA.- = Er,c
Lx, = Ey,e
( x
(t) (1) ( ||]
where e is drawn from the standard Gaussian distribution. If the denoising neural network simply operates separately in the individual block graph, the sparse connection among the block graphs will be lost. Therefore, in capturing the interconnection, the denoising neural network takes in two
5

---

Stochastic Block Graph Diffusion
Therefore, the modularity of the block representation is par- ticularly beneficial for large-scale graph learning tasks. It improves scalability, the approach scales linearly with the number of blocks rather than quadratically with the number of vertices, making it feasible to handle graphs with millions or even billions of vertices. Moreover, the localized nature of block-wise operations preserves important structural in- formation within each block while enabling inter-block inter- actions to be modeled through additional aggregation steps, ensuring that the diffusion process still captures global graph properties without incurring prohibitive memory costs.
diffusion-based graph generation methods including Di- Gress (Vignac et al., 2022), GDSS (Jo et al., 2022), and EDP-GNN (Niu et al., 2020). In addition, we also con- sider several representative deep graph generation such as GraphRNN (You et al., 2018), SPECTRE (Martinkus et al., 2022), and EDGE (Chen et al., 2023).
Datasets. We consider five real and synthetic datasets with varying sizes and connectivity levels: Planar-graphs, Con- textual Stochastic Block (odel(cSBM) (Deshpande et al., 2018) 8), Proteins (Dobson & Doig, 2003), QM9 (Wu et al., 2018), OGBN-Arxiv, and
(Hu et al., 2021). Notably, OGBN-Products a large dataset for graph gener- ation tasks, and our method is the only approach capable of successfully training on
Benefit of Structural Prior. Block representation improves size generalization in graph generation by focusing on lo- cal, size-invariant structures like communities, which have consistent internal patterns (e.g., degree distributions, clus- tering coefficients) regardless of the overall graph size. By learning these modular, block-based components, the model can generalize well across different graph sizes, applying the same learned rules to both smaller and larger graphs. This approach reduces the learning complexity compared to full- full-graph methods, as shifts the focus to intra-community relationships (with complexity ((C)) and sparse inter- community connections, rather than handling the full graph (with complexity (N)3).
Evaluation. Our evaluation focuses on two main aspects: (I) the quality of the generated graphs, assessing how well the method captures the underlying graph distribution, and (2) the memory consumption required during graph gen- eration. For assessing the quality of generated graphs, we follow established graph generation studics and adopt both structure- based and neural-based metrics. In terms of structure-based metrics, we measure the Maximum Mean Discrepancy (MMD) (Gretton et al., 2012) between test and generated graphs across graph properties, including degrees, clustering coefficients, and orbit counts. For neural- based metrics, we use the Fréchet Inception Distance (FID) pro- posed by (Heusel et al., 2017) (with modified procedure in (Thompson et al., 2022)) to evaluate the alignment be- tween graph distributions in a learned embedding space. To ensure direct comparison of memory consumption, we use our method as reference point and report the memory consumption ratio as the baseline model's 's memory divided by our model's 'ss memory, highlighting the relative efficiency across approaches.
Moreover, block-based models avoid overfitting to specific global graph patterns that are unique to certain sizes. This modular approach allows the model to expand or contract based on the number of blocks, making adaptable to a wide range of graph scales. The combination of reduced learning complexity, modularity, and the ability to learn size- invariant patterns ensures better generalization and faster convergence across graphs of different sizes, enhancing scalability and performance.
4. Experiment
Testbed. Our experiments were conducted on a Dell Pow- erEdge C4140, The key specifications of this server, perti- nent our research, include: CPU: Intel Xeon Gold 6230 processors equipped with 20 cores and 40 threads, GPU: NVIDIA Tesla V100 SXM2 units equipped with 32GB of memory, Memory: An aggregate of 256GB RAM, dis- tributed across eight 32GB RDIMM modules, and Operat- ing System: Ubuntu 18.0 88.44TS
In this section, we present an experimental study of our proposed method. We defer some of the technical details of these experiments to the appendix. The goal of the ex- perimental study is to empirically validate and answer the following two main questions for our method.
Can SBGD achieve comparable/hetter performance in generating graphs while requiring less memory?
4.2. Experimental Results
2. Can SBGD extrapolate better in generating graphs of size that are not observed in training data?
Effectiveness. We evaluate the effectiveness of our ap- proach in both real-life and synthetic datasets. The results are presented in Table I. observe that SBGD can achieve significantly better memory consumption (up to 6 x more memory efficient) while maintaining comparable or bet- ter performance in generation in almost all metrics com- pared to existing baselines. In particular, under the given testbed, our method is the only one that can successfully
Overview. The empirical results answer the above questions affirmly, and thereby validate the effectiveness of SBGD.
4.1. General Setup
Baselines. In our experiments, we compare the perfor- mance of SBGD against several state tf- denoising-
6

---

Stochastic Block Graph Diffusion
Training Graph 100)
Generated Graph 1Sice
Generated Graph (Size
Ger Graph 2000
Generated Graph (Size
Figure 3. Visualization of graphs of different sizes generated from SBGD. The figure illustrates that SBGD able to maintain the overall characteristic of the ground-truth (training graph) nicely even if generating graph of varied size.
60
60
(Lower is Better)
(Lower Better)
Score (Lower is Belterr
FID Score
20
30
30
GraphäM-
GDSS
SPECTRE
DiGress
10
S9GDD
0
10
20
2
10
12
Graph Size
Number of Partitions
Graph Size
(a) Size Generalization of Different Methods
(b) Effect of Partition Partition (c) Partition Number and Size Generalization
Figure 4. Experiments on Size Generalization and Partition Number. Figure 4(a) illustrates the size generalization performance of different methods. Figure 4(b) shows the performance of method function of the number of partitions. Figure 4(c) demonstrates how the number of partitions impacts the size generalization of our method.
train and learn on the OGBN -rroduusssuts dataset. This vali- dates the effectiveness of our approach in addressing the main motivation for making the graph generation method scalable and efficient for large graphs. In addition, we ob- serve that recent diffusion-based methods such as DiGress consistently outperform other deep-learning based method such GraphRNN. This is consistent with the existing liter- ature and further indicates our improvement on the diffusion model is important for the graph generation.
affect the learning process. For this, we are interested in two questions: 1) how does the partition number affect the generation quality and 2) how does the partition number affect the size generalization ability of the method? For the first question, we evaluate the FID score (relative the training dataset) with respect different partition number. As illustrated in Fig, 4(b), there is an optimal point for the partition number. We hypothesize the reason behind this is that when the partition number is too large (block size being too small), the method would be unable to learn some important global structure. On the other hand, when the partition number is too small (block size being too large), the method would pick up noise from the undesired global structure. Next, we look at how partition number affects the size generalization Based on the previous observation, we would expect that a larger partition number (leading to a smaller block size) would extrapolate better for generating a smaller graph. On the other hand, lower partition number (leading to a larger block size) would extrapolate better for generating larger graph. The results in Fig. 4(c) indeed match our expectation.
Size Generalization. Next, we evaluate the size general- ization of our method compared existing baselines. For this, we use the eSBM model and focus on the FID metric to evaluate the distance between the generated distribution and the training distribution. As illustrated in Fig. 3 and 4(a), our method can maintain global structure characteristic and significantly excels in generating graphs with varied sizes. This indicates that our method is able to extrapolate better size generation with respect to complex/large graph generation, validating our previous theoretical discussion on the benefit of block-representtatio.
Partition Number. Next, we investigate how the partition number, the main hyperparameter of our framework, can
7

---

Stochastic Block Graph Diffusion
Table Performance Comparison of Graph Generation Methods. The symbol & indicates that a lower value is preferable, while t indicates that a higher value is better. The best and second- becond-best performances are highlighted in dark gray and light gray, respectively. "N.S." means the method does not support the dataset," "O.O.M." means "Out Memory," and "N.A." means the metric is not available for the dataset. "M.R." denotes the memory ratio, with the baseline reference being our method.
Datuset
Method
Deg. :
Clus.
Orbic :
Spec.
Wavelt 0.19% 1.0e-3
Avg.
V.UNT
FID 1
M.R.
GraphRNN
0.097 2.11-3
0.525 1.23p-3
0.650 3,25e-3
0.333 L,60-3
0
38.0 1.02
SPECTRE
0.002 + 1.87e-3
0252 e 1.5te-3
0.69 a 2.42-3
0,871 3-46-3
0.176 1.50e3
0.40
600 0.89
33.3 0.842
4.2
EDGE
0.204 4 1.12e
0.522 3.22e
0.589 a 2.17e
0.788
à 2.21ee
0.154
1 3.56e
0.45
60.6 1.731
46.7 4 2.768
5.3
Planar Graphs
EDP-GNN
0.68 8.760-4
0.639 + 1.01e-3
0.886 2.83-3
0 2.0le3
0.48
0
1,391
GDSS
0.85 1.45-33
7.71 0.275
1.770-3
0.773
0.98
1.80-3
0.33
87.5
33.34 1.721
DiGress
0.06 4 7.58ee
0.451 4 5,900 4
0.775
a 3.32e-
0,091
1 1.07e
0.33
2.998
29.0 4 3,011
5.7
SBGP
0.01 1.21ec4
5811e 0.216
0,446
0.768
4.218-3
0.095
2:33ee4
0.32
1.642
2.857
GraphRN'
1.00
1.78
0.388 3.11o
1.53p-3 0.538
0.758
2.46o-3
0:210
1.836-3
0.0
67.7 2.86
20.7 1.28
SPECTRE
0.087 5.87744
2:436-
0.499 a 2.31e
0.741
à 2.75e-
0,174 1/4e-3
0.37
70.3 3.72
17.6 a 0.92
4,0
EDGE
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
Contextual Stochastic Block Model
GDSS
EDP-GNN
0.82 1 3
N.S
0.298 a 8
N.S
0:448 9 7.21e-4
N.S.
0.538
N.S.
E 2.32
0.154 9:2le4
N.S.
0.31
66.9 5.12
N.S.
N.S.
22.1 a 0.88
5.5
N.S.
DiGress
0.83 2,08 3
0.302 7:25e-
0.457 6.39c
0,610
3.5%
0,165 8.63e
0.32
83.1 1.74
18.8 0.53
5.3
SBGD
0,257 5.776-4
0.537 1.255-3
D154
16.3
GrapRRNN
N.A.
NA
N.A.
N.A.
N.A.
N.A.
75.6
39.5 + 3.35
6.4
SPECTRE
N.A.
NA.
N.A.
N.A.
N.A.
N.A.
68.6 1.88
4 2.22
4.5
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
RDP-GINN
N.S.
NS.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
QM9
GDSS
N.A.
N.A
N.A.
N.A.
N.A.
N.A.
68.6
21.6 1,56
5.7
DiGiress
N.A.
N.A.
N.A.
N.A.
N.A.
N.A.
19.7 1.25
5,5
SBGD
N.A.
N.A.
N.A.
N.A.
N.A.
N.A.
91.2 1.8
20.0 4 1.02
1,0
GraphRNN
0.77 E 1.88e-
2316-3
0153 & L846-3
3.
0.35
N.A.
2.19
6.2
SPECTRE
0.095 2.31ee3
0.371 2.713 2
0,822 & 3.27633
1.9ee3
N.A.
25.0
BDGE
N.S.
NS.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
-GBNNAAri
GDSS
EDP-GNN
N.S.
1.92
0.165 1666-1
NS.
N.S.
2:27e-3
NS..
0.780
1.99-3
D172
N.S.
N.S.
N.S.
N.A.
N.S.
N.S.
DiGress
0.600 1 1.72e-
0,156 1.226-3
0,285 4 1.97e:
0.761 2.826-3
0177
1 KSee3
0.88
N.A.
33.7 4 1.21
5,3
SBGD
0.062 3,01e
0.148 1
0.21 4 1,008 3
0.739 & 3,486-3
0.133 1.74e
0.27
N.A.
21.4 1,25
1.0
GriphRNN
OOM
0OM
COM
SPECTRE
UOM
DUM
G0M
0UM
OUM
UOM
OUM
GOM
OUM
RDGE
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
OGBN products
EDP-GNN
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
N.S.
GDSS
GOM
OOM
OOM
COM
OOM
COM
0OM
GOM
OOM
DiGress
00M
DOM
OOM
0OM
OOM
0OM
0OM
OOM
OOM
SBGD
3.568-3
1.3263
22736-5
30883
N.A.
2,788-3
5. Related Works
on extending DDM into the graph domains. (Niu et al., 2020) is one of the pioneer works in graph generation that extends the diffusion model in the graph domain. (Niu et al., 2020) shows that a diffusion-
Graph Generation. Graph generation research has a rich history, underscored by the importance of the prob- lem, and is characterized by the use of various random graph models. Notable among these are the Erdos-Renyl (ER) model (Erdös et al., 1960), Barabasi-Albert mod- elt (Barabási & Albert, 1999), and the Stochastic-Blan -Bocck Model (SBM) (Holland et al., 1983) each contributing uniquely to our understanding of graph structures. The SBM, in particular, is pivotal because it builds on the obser- vation that real-life networks often consist of more funda- mental block or community structures. This is evident in the way real-life networks exhibit block structures (Su & Marbach, 2022; 2023; Abbe, 201 8), where vertices within a block show similar behaviours and have dense interconnec- tions, while inter-block connections remain sparse. Many graph algorithms have been developed based on this under- standing, leveraging the inherent block structure in networks. In our current work, we connect this traditional knowledge in graph analysis with the recent advancements in graph dif- fusion generative models. By applying the block structure prior, we aim to enhance the graph diffusion model's 's perfor- mance, particularly in scaling up to handle larger graphs
model combined with backbone is permutation invariant and capable of capturing the complex distribution of the graph structure of real-life graphs. (Jo et al., 2022) further extend the procedure to incorporate graph structure. In order to speed up the sampling efficiency, (Chen et al., 2023) pro- pose to use Bernoulli distribution as the diffusion process to model the generation and deletion of edges and to use an empty graph as the convergent point. However, their method suffers from two limitations: 1) their methods only model the generation of graph structure and are inapplicable to graphs with features (i.e., inapplicable to most of the interesting applications); and 2) they use a single point in space (empty graph) as the convergent distribution, which seriously limits the expressive power of the generation pro- cess (Xu et al., 2022). (Vignac et al., 2022) aims to tackle the discrete nature of graph structure data and extend the discrete diffusion (Hoogeboom et al., 2021; Austin et al., 2021) to the graph structure data with categorical features. Their method also requires accommodating the complete graph in training or sampling, but they are still suffering from the memory explosion problem.
Graph Diffusion Generative Model. Inspired by the suc- cess of DDM in other domains, there is increasing attention
Recent work also explores multi-modal distributions under-
8

---

Stochastic Block Graph Diffusion
lying graph structures enhance generation accuracy (Jo al., 2023). Moreover, an alternative line of research ap- proaches graph generation an autoregressive editing pro- cess graphs (Zhao et al., 2024), fundamentally distinct from the diffusion framework. An intriguing future research direction would be to investigate potential synergies be- tween these autoregressive and ilffusion-based generative paradigms.
References
Abbe, E. Community detection and stochastic block mod- els: recent developments. Journal of Machine Learning Research, 18(177):1-66 2018.
Aref, S. and Mostajabdaveh, M. Analyzing modularity max- imization in approximation, heuristic, and graph neural network algorithms for community detection. Journal of Computational Science, 78:102283, 2024.
6. Concluding Discussion
Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and Van
6.1. Conclusion
Den Berg, R. Structured denoising diffusion models in discrete state-spaces. Advances Neural Information Processing Systems, 34:17981 2021.
We present the SBGD model, which leverages a block graph representation to address key challenges faced by existing GDGMs. By utilizing a block-based structure, SBGD not only reduces memory complexity, improving scalability, but also enhances size generalization. Through extensive empir- ical evaluations, show that SBGD significantly improves memory efficiency and scalability, while demonstrating su- perior generalization across graphs of varying sizes. This makes SBGD a more flexible and efficient solution to the graph generation problem.
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439):509-511 1999.
Brockschmidt, M., Allamanis, M., Gaunt, A. L., and Polo- zov, O. Generative code modeling with graphs. arXiv 2018
preprint
Chen, T., Zhang, R., and Hinton, G. Analog bits: Gen- erating discrete data using diffusion models with self- conditioning. arXiv preprint arXiv:2208.04200 2022.
6.2. Future Work
Chen, X., He, J., Han, X., and Liu, L.-P. Efficient and degree- guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.044
Our experiments reveal a trade-off when increasing the num- ber of partitions in the block representation. We hypoth- esize that the key factor controlling this trade-off is the alignment between the resulting block size, the inherent granularity of the graph structure, and the granularity quired for the downstream task. Further investigation into this issue presents an exciting direction for future research. Specifically, developing metrics to quantitatively capture this phenomenon could provide valuable insights, allowing us to refine the block representation for improved perfor- mance across wide range of graph generation tasks.
2023.
Cherifi, H., Palla, G., Szymanski, K., and Lu, X. On community structure in complex networks: challenges and opportunities. Applied Network Science, 4(1):1-35, 2019.
Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.-J. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266, 2019.
Impact Statement
Chung. F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
This paper presents work whose goal is to advance the scal- ability of score-based graph generation method. There are many potential socictal consequences of our work, none which we feel must be specifically highlighted here
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Con- textual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
Dhariwal, P. and Nichol, A. Diffusson models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8794, 2021.
Acknowledgement
We would like to thank the anonymous reviewers and area chairs for their helpful comments. This work was supported in part by grants from the National Key Re- search and Development Program of China (Grant No. 2023YFC3707905), and the Natural Science Foundation of China (No. 42302326).
Dobson, P. D. and Doig, A. J. Distinguishing enzyme struc- tures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-733, 2003.
Erdös, P., Rényi, A., et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 571):17-60, 1960.

---

Stochastic Block Graph Diffusion
Fiedler, M. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298-335 305, 1973.
Lee, H., Hyung, E., and Hwang, S. Rapid neural architec- ture search by learning generate graphs from datasets. 2021.
arXiv preprint
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf. B., and Smola, kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773) 2012.
Li, Y., Zhang, L.., and Liu, Multi-ohjective de novo drug design with conditional graph generative model. Journal of cheminformatics, 10:1-24, 2018.
Grover, A., Zweig, A., and Ermon, S. Graphite: Iterative generative modeling of graphs. In International confer- ence on machine learning, pp. 2434 2434-2444. PMLR, 2019.
Martinkus, K., Loukas, A., Perraudin, N., and Wattenhofer, R. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In In- lernational Conference on Machine Learning, pp. 15159- 15179. PMLR, 2022.
Hamilton, W. I.., Ying. R., and Leskovec, J. Inductive representation learning on large graphs, 2018.
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. Gans trained by two time-scale update rule converge to local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Newman, Modularity and community structure in ner- works. Proceedings of the national academy of sciences, 103(23):8577-8882 2006.
Newman, M. E. and Girvan, M. Finding and evaluating community structure in networks. Physical review E, 69 (2):0261 13, 2004.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851, 2020.
Newman, M. E.. Watts, D. J., and Strogatz, S. H. Random graph models of social networks. Proceedings of the national academy of sciences, 1):256p 2572, 2002.
Holland, W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Hoogeboom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 1e:12444-12466 2021.
Nichol, A., Dhariwal, P., Ramesh, A., Shyam, P., Mishkin, P., McGrew, B., Sutskever, I., and Chen, M. Glide: Towards photorealistic image generation and editing with text-guided diffusion models. arXiv preprint arXiv:2112.10741, 2021.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, Open graph benchmark: Datasets for machine learning on graphs, 2021. URL https: /aaps://arxiin //arx/aaaavv..//aa/eaa org/ abs//b00 00687.
Niu, C., Song, Y., Song. J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via score-based generative modeling. International Conference on Ar- rificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020.
Jo, J., Lee, S., and Hwang, S. J. Score-based generative modeling of graphs via the system of stochastic differen- tial equations. International Conference on Machine Learning, pp. 10362-10383. PMLR, 2022.
Perozzi, B., AI-Rfou, R., and Skiena, S. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowl- edge discovery and data mining, pp. 701-710, 2014.
Jo, J., Kim, D., and Hwang, J. Graph generation with dif- fusion mixture. arXiv preprint arXivv2302.03396 2023.
Preuer, K., Renz, P., Unterthiner, T., Hochreiter, S., and Klambauer, G. Fréchet chemnet distance: a metric for generative models for molecules drug discovery. Jour- nal of chemical information and modeling, 58(9):7736 1741, 2018
Kamada, T., Kawai, S., et al. An algorithm for drawing general undirected graphs. Information processing letters, 31,1):7-15, 1989.
Karrer, B. and Newman, M. F. Stochastic blockmodels and community structure in networks. Physical review E, 83 (1):016107, 2011.
Rombach, R., Blattmann, A., Lorenz, D.,, Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF con- ference on computer vision and pattern recognition, pp. 10684-10695, 2022.
Karypis, G. and Kumar, V. Multilevelk-wan partitioning scheme for irregular graphs. Journal of Parallel and Distributed computing, 48(1 48(1):96-129, 1998.
Korte, B. H., Vygen, J., Korte, B., and Vygen, J. Combina- torial optimization, volume 1. Springer, 2011.
Simonovsky, M. and Komodakis, N. Graphvae: Towards generation small graphs using variational autoencoders.
10

---

Stochastic Block Graph Diffusion
In Artificial Neural Networks and Machine Learning- ICANN 2018: 27th International Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 1 27, pp.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 932):113-330 2018.
Springer, 2018.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International conference on machine learning, pp. 2256-2263 PMLR, 2015.
Xie, S., Kirillov, A., Girshick, R., and He, K. Exploring randomly wired neural networks for image recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1284-1293, 2019.
Song, J., Meng, C., and Ermon, S. Denoising diffusion im- plicit models. arXiv preprint arXiv:2010.02500 2020a.
Xu, Y., Liu, Z., Tegmark, M., and Jaakkola, T. Poisson flow generative models, 2022.
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang, D., Yu, J., Wang, H., Wang, W., Weng, C., Zou, Y., and Yu, D. Diffsound: Discrete diffusion model for text- to-sound generation. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2023.
Song, Y. and Ermon, S. Improved techniques for train- ing score- score-based generative models. Advances in neural information processing systems, 33:1 15:11233-12444 2020.
You, J., Ying, R., Ren, X., Hamilton, W., and Leskovec, J. Graphrnn: Generating realistic graphs with deep auto- regressive models. In International conference on ma- chine learning, pp. 5708-5717. PMLR, 2018.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Er- mon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011. 13456, 2020b.
Zhao, L.., Ding, X., and Akoglu, L. Pard: Permutation- invariant autoregressive diffusion for graph generation. arXiv preprint arXiv:2402.0366/ 2024.
Su, J. and Marbach, P. Structure of core-periphery commu- nities. In International Conference on Complex Networks and Their Applications, pp. 151-161. Springer, 2022.
Su, J. and Marbach, Structural properties of core- periphery communities. Advances in Complex Systems, pp. 2340004, 2023.
Thompson, R., Knyazev, B., Ghalebi, E., Kim, J., and Taylor, G. W. On evaluation metrics for graph generative models. arXiv preprint arXhv:201..08871 2022.
Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.1477 14734, 2022.
Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F,, Xie, X., and Guo, M. Graphgan: Graph representation learning with generative adversarial nets. In Proceed- ings of the AAAI conference artificial intelligence, volume 32, 2018.
Wang, M., Zheng, D., Ye, Z., Gan, Q., Li, M., Song, X., Zhou, J., Ma, C., Yu, L., Gai, Y., et al. Deep graph library: A graph-centric, highly- seghoy-perfommant package for graph neural networks. arXiv preprint arXiv: 190.001355 2019.
Wieder, O., Kohlbacher, S., Kuenemann, M., Garon, A., Ducrot, P., Seidel, T., and Langer, T. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12 2020.

---

Stochastic Block Graph Diffusion
A. Background
Denoising Diffusion Models (DDM). DDM models (Song & Ermon, 2019; Song et al., 2020b; Song & Ermon, 2020; Sohl-Dickstein et al., 2015: Song et al., 2020a) belong to the large family of latent variable models which use a latent space of the same dimension the data. It models the data generation process as a transition process in the latent space and primarily comprises two main components: noise model (forward process) and denoising neural network (backward process). The noise model y gradually corrupts data point to form sequence of increasingly noisy data points (21,,..,,7) (T)) It adheres to a Markovian structure, formulated as:
( ................................ (e......,TTI1))) = q(z II (x)
(A.1)
Then, we want to learn denoising network do that aims to reverse this process by predicting #;-1 from Tt. To synthesize new samples, a noisy point is sampled from the prior distribution p(ær) and then inverted through the iterative application of the denoising network. For diffusion model exhibit efficiency, it should satisfy three properties:
1. The distribution (<z)(==) should possess a closed-form equation, facilitating parallel training across varying time steps.
2. The posterior pe ( = f q(xx=1//4e x) do (z) must also be expressed in closed-form enabling the utilization of the neural network's 's target.
3. The limit distribution 9sx limr- (( (r) must remain independent of æ, making viable as a prior distribution for inference.
A scheme that satisfies all these properties is to Gaussian noise (Ho al., 2020) as the noise model and it has become the de-facto option for the forward process. This amounts to a Markov chain that gradually adds Gaussian noise to the data according to a variance schedule B.....,Br:
q 11-1) == N (m1s V1 11 3,1),,
((<)( = N (1aa; 0,70, (1 - a))
(A.2)
where o₁ := 1 Bg and Og2- == II as Instead of directly learning a neural net model the transition from de Tt-1, one can learn a neural net f(x t) to predict za (or e) from Te, and estimate x;-1 from H, and estimated Zg (or ē).
Graph Diffusion Generative Model Building upon the empirical success of DDM in other domains, there is increasing attention on extending DDM to tackle the graph generation problem (refer to the related work section for a more detailed discussion). Two notable extensions by (Niu et al., 2020) and (Jo et al., 2022) involve the utilization of matrix representations for graphs, which allows them to treat the graphs a similar manner as images. However, these approaches exhibit two key limitations: 1) they overlook the discrete nature of graph data, and 2) the dimensionality of the representation space scales O(22), where N denotes the number of vertices.
To tackle the discrete nature of graph structure data, recent work (Vignac et al., 2022) extends the discrete diffusion model from other domains (Hoogeboom et al., 2021; Austin et al., 2021) and models the graph representation using a state space model, treating the noising process as a Markov transition on the state transitions. However, this approach still suffers from the issue of memory explosion, as each state in the state space model continues to represent the complete graph.
Block Structure in Graphs. In real-life graphs, prominent feature is their block (community structure) (Deshpande et al., 2018; Holland et al., 1983), where vertices within the same block display dense connections and exhibit similar behavioural traits (i.e., similar feature distributions). This contrasts sharply with vertices from different blocks, which are sparsely connected, highlighting the distinct boundaries between these units. The concept of block structure is a cornerstone in graph analysis (Newman et al., 2002; Newman, 2006) and plays a crucial role in many graph learning algorithms such as DeepWalk (Perozzi et al., 2014) and ClusterGCN (Chiang et al., 2019). In this paper, we integrate the traditional principles of graph analysis with the graph diffusion generation model. By leveraging the block structure of the graph as the diffusion space, we aim to significantly reduce memory complexity in our approach.
A.1. Training Objective Derivation
In this appendix, we present a derivation for the Equations used in the problem formulation for completeness. A similar derivation can be found in (Jo et al., 2022).
12

---

Stochastic Block Graph Diffusion
The partial score functions can be estimated by training the time-dependent score-based models se(.) and (.))), that
s9 $9 t) Vx log P(G)), (G,,)) VA log PG:).
However, the objectives introduced in SGM for estimating the score function are not directly applicable here, since the partial score functions are defined as the gradient of each component, rather than the gradient of the data as in the conventional score function. This interdependence between the two diffusion processes tied by the partial scores adds another layer of difficulty.
To address this issue, an new objective for estimating the partial scores needed. Intuitively, the score-based models should be trained to minimize the distance to the corresponding ground-trute truth partial scores. The following new objectives generalize score matching (Song al., 2020b) to the estimation of partial scores for the given graph dataset, as follows:
min E, 0
Egg g. (000 - Vx log (()))
(A.3)
min E,
Eg. Es, Go (9.) V log P()))
(A.4)
where is uniformly sampled from [0, The expectations are taken over samples Go Pdata and G. P( where PG) denotes the transition distribution from O to induced by the forward diffusion process.
Unfortunately, the equations above are still not directly trainable since the ground-truth partial scores are not analytically accessible in general. This is why we need to underlying process to be an OU process, as we can leverage the known conditional density of OU process for training.
min E, 0
Eg, Es,so (0,, E,.0 V log PG
(A.5)
min R2 Rg,10 (00(),,)) V log P(G.)9))
(A.6)
Since the drift coefficient of the forward diffusion process is linear, the transition distribution P(Ge(Go) can be separated in terms of X, and A, as follows:
P(G. = XX,
(A.7)
Notably, can easily sample from the transition distributions of each component, P(X, X,) and IP(A,AA)), as they Gaussian distributions with mean and variance determined by the coefficients of the forward diffusion process. This leads to the following training objective:
min E. Eg, Eg ((., Vx log X ||2
(A.8)
min E, Rgg Eg (St, VA log (AA)
(A.9)
The expectations in the equation above can be efficiently computed using the Monte Carlo estimate with the samples (t, Go. G.). Note that estimating the partial scores is not equivalent to estimating Vx log P(X.) or VA log P(A,). the main objective of previous score-based generative models, since estimating the partial scores requires capturing the dependency between X, and A, determined by the joint probability through time.
1. DERIVATION OF TRAINING OBJECTIVE A.3
The original score matching objective can be written as follows:
Eg. [S,,, t) Vx log [1] Eg, [[|so (Gr, () [ 2Eg, (So, t), Vx log (P())) Ci,
13

---

Stochastic Block Graph Diffusion
where C1 is constant that does depend W. On the other hand, we have
Bg No [|se(Gr,)) t) Vx Por Bg [||se (Gt, t) Bo is (so t). Vx log P(g)(())))))) C2.
For the second term, from the derivation (Appendix A.1 from (Jo et al., 2022)), we know that it has the following equivalency:
Eg, (S 1), Vx log (P())) Eg, 19 ((so()r, (), Vx log (G)))))))
Since the constant C₁ and C2 does affect the optimization results, can conclude that the following two objectives equivalent with respect to 0
Eg, Es Go []s t) V log ( Bg, [( V log P()))
Similarly, computing the gradient with respect to A, we can show that the following two objectives are also equivalent with respect to Φ:
Es Eg, [91, - V log (() [ EG, [1 () V log (()))
Now, it remains to show that Vx log (o)) is equivalent to Vx log P Xo). Using the chain rule, we get that
Ô log IP (A,
0A,
Tr VA log Pog a(X))u
0.
0(x))
With this result, we have that,
Vx log Go) = Vx log + Vx log Vx log
Therefore, conclude that
V log P(G.)90) = Vx log (Xx,)
With a similar computation for A,, we can also show that A log (o) is equal to V lo)
B. Algorithm Summarization
SBGD decompose the graphs into finer structural structures (blocks) and operates latent graph space consisting the building block of the graph structure, allowing for the computation of various graph descriptors each diffusion step. The procedure of training and sampling from SBGD are summarized in Algorithm and Algorithm 2 respectively.
Implementation. SBGD decompose the graphs into finer structural structures (blocks) and operates latent graph space consisting of the building block of the graph structure, allowing for the computation of various graph descriptors at each diffusion step. The detailed and complete procedure of training and sampling of SBGD are provided in the supplementary material
C. Graph Partition Problem
The graph partition problem is a fundamental problem in graph theory and computer science. It involves dividing graph into multiple smaller subgraphs, or "partitions," that satisfy certain properties. This problem has wide-ranging applications, including parallel computing, clustering, network analysis, and community detection. The goal to achieve a division of the graph that satisfies specific constraints while optimizing one or more criteria, such as minimizing the number of edges between partitions or ensuring that each partition is balanced size.
14

---

Stochastic Block Graph Diffusion
Algorithm 1 SBGD Training Algorithm
Require: A set of block graphs and their interaction C [C;], A = (Aig}
1: Sample two block graphs C, Cj from
2: Extract the corresponding interactions Aij
3: Sample t Uniform( 1,, T)
4: Sample noise ((.
5: Corrupt data:
6: A (0)
(7(t)- A (0)
+ V1 (t)
7: A (f) 77(1] A [0] V (8)
A
X V7(t) X (0) VI 1111111 7t)
8:
X Vi(t)- X (0) + -1->(tt)-e
9:
10: Extract structural and spectral features from the block graph:
(1) (1) {AA)), x ,4), ((A) x("),) (
11: Predict and compute the weighted reconstruction loss:
A (A
X (0)
(0) 1)
A se (A)
X (0)
22
.t)
X (A
(0)
X
X (0) sw (A X 10 (t)
AG So ( A X Xj)
ΣA CA (0) )
+ +x (X (())) + C(Aig, Aig)
Algorithm SBGD sampling algorithm.
1: Sample ni, m2 from the training data distribution
Sample A. (T) AT
(T) from P PAmra (n1), A (122)
3: Sample X (!7) (!T) from Fx(n1), Px(22)
4: for
T' do
5:
2
(t)
2
(t)
f(A (X)
X
t), (AA) (x(9),)
(1)
A, so(A (0)
X
(0)
.t)
A = so(A)
(
,2,2,
X. (A (1,
X, s (A
(1) .z,.))
A (1-1) 1) A. (1
X (1-1) X
DDIM DDPM(A, A,, & A x0x00
6: end for
7: A S A, A,. X,
15

---

Stochastic Block Graph Diffusion
C.1. Formal Definition of the Graph Partition Problem
Formally, the graph partition problem can be defined follows: Given graph G EV, where V is the of vertices (nodes) and E is the set of edges (connections between nodes), the objective is to partition V into & disjoint subsets V1, V2,... V2 such that:
V= w=NUKU...UN V = 0 for all i i
Each partition Vú represents a subgraph of G, and the partitions are subject to various optimization criteria. A common objective is to minimize the cut size, which is the number of edges connecting vertices in different partitions. The cut size defined as:
Cut(V,, V2...., V&a)
Σ EEV, V2) ISKGSS
where EV, Vÿ) is the set of edges between partitions Vi and Vg, and [V,,, V2)l is the number of such edges. This is typically referred to as the min-cut problem, where the objective is to minimize the number of edges between partitions while ensuring the constraints on the partitioning of the vertices are satisfied.
Beyond the cut size, additional constraints may be imposed on the partitioning, such balancing the size of each partition (ensuring that the number of vertices in each partition is roughly equal), optimizing more complex objective such as minimizing the conductance or maximizing modularity in network analysis.
C.2. Approaches to Solving the Graph Partition Problem
The graph partition problem, particularly the min-cut problem, is NP-hard, meaning that efficient algorithm guarantees an optimal solution in polynomial time for all instances. Consequently, various heuristic and approximation methods are employed to tackle the problem. Key approaches include:
Spectral Partitioning: This approach uses the eigenvalues and eigenvectors of the graph's Laplacian matrix to determine the best way to partition the graph. By computing the Fiedler vector (the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix), the graph can be split into two parts such that the cut size minimized. This approach is widely used in clustering and graph partitioning, particularly for large graphs (Chung, 1997; Fiedler, 1973).
Optimization-Batte Methods: These methods formulate the graph partitioning problem as mathematical opti- mization problem and solve it using techniques such as linear programming, semidefinite programming, or integer programming. While these methods can provide exact solutions, they often suffer from high computational complexity, especially for large graphs (Korte et al., 2011).
Community Detection Algorithms: In the context of networks and social graphs, community detection algorithms aim to partition the graph in such way that the number of edges within each partition is maximized while the number of edges between partitions is minimized. Methods like the Louvain algorithm and Infomap have become popular for detecting communities in large-scale networks (Aref & Mostajabdaveh, 2024).
In this paper, we focus on incorporating structural priors into the score-based graph generative model. For the partitioning algorithm, we adopt the commonly used METIS algorithm (Karypis & Kumar, 1998) from the DGL library (Wang et al., 2019). Further exploration of partition algorithm selection and its impact on the performance of SGBD presents an exciting direction for future research.
We select the METIS partitioning algorithm primarily due to our core modeling assumption, which posits dense and homogeneous intra-block (diagonal) structures coupled with sparse inter-block (off-diagonal) connections. METIS excels in partitioning graphs into balanced, cohesive clusters while simultaneously minimizing edge cuts. This characteristic aligns closely with our scenario, making METIS a particularly suitable choice for capturing and leveraging the inherent block-wiss wise structure of the graphs under investigation.
16

---

Stochastic Block Graph Diffusion
D. Experiment Details
D.I. General Setup
Baselines. In our experiments, we compare the performance of SBGD against several state-of-the-art Senoising-diffusionn based graph generation methods including DiGress (Vignae et al., 2022), GDSS (Jo al., 2022), and EDP-GNN (Niu et al., 2020). In addition, we also consider several representative deep graph generation such as GraphRNN (You al., 2018), SPECTRE (Martinkus et al., 2022), and EDGE (Chen al., 2023). The summarized description of each baseline are follows.
GraphRNN: A pioneering autoregressive model for graph generation that sequentially generates graphs by adding nodes and edges in breadth-first-search order, effectively capturing the structure of small- medium-sized graphs.
SPECTRE: A graph generation framework leveraging spectral decomposition to generate realistic graph structures, focusing on preserving spectral properties like eigenvalues and eigenvectors for structural fidelity.
EDGE: An efficient graph generation method that employs generate graph edge-by-edge, enabling scalability.
EDP-GNN: pioneering biffusion-based graph generation model for generating graph structure.
DiGress: A state-of-the-art denoising diffusion-basse framework based Markov state model.
GDSS: graph generation method utilizing score-based generative modeling with stochastic differential equations (SDEs) to model the gradient field of the graph distribution.
Datasets. We consider five real and synthetic datasets with varying sizes and connectivity levels: Planar-graphs, Contextual Stochastic Block Model(cSBM) (Deshpande et al., 2018), Proteins (Dobson & Doig. 2003), QM9 (Wu et al., 2018), OGBN-Arxiv, and OGBN-Produch (Hu et al., 2021). Notably, OGBN-Products relatively large dataset for graph generation tasks, and our method is the only approach capable of successfully training on it. The summarized descriptions of each datasets follow.
Planar-graphs: A synthetic dataset consisting of planar graphs, where nodes and edges are arranged such that they can be embedded in the plane without edge crossings. This dataset is used to evaluate models on generating graphs with specific structural constraints.
cSBM is extension of the classic Stochastic Block Model (SBM), designed to incorporate node features context into the synthetic.
cSBM:
Proteins: A real-world dataset consisting protein structures represented as graphs, where nodes correspond to amino acids and edges represent spatial or functional interactions.
QM9: A dataset of small molecules represented as graphs, where nodes represent atoms and edges represent bonds.
OGBN-Arxiv: A large citation network dataset where nodes represent papers and edges denote citation relationships. Node features derived from paper abstracts.
OGBN-Products: large-scale product co-purchasing network where nodes represent products and edges signify co-purchase relationships.
D.2. Model Description and Configuration
For our implementation, we follow the approach outlined in (Vignac et al., 2022) and utilize Graph Transformer as the score network. Graph Transformers class of models that adapt the transformer architecture, originally designed for sequential data, to process graph-structured data. These models are particularly well-suited for tasks such as node classification, link prediction, and graph generation. One of the main advantages of Graph Transformers over traditional Graph Neural Networks (GNNs) is their ability to model long-range dependencies in graph data. By leveraging the attention mechanism, Graph Transformers can capture relationships between distant nodes, without requiring explicit graph convolutions, thus offering more flexible and scalable approach to graph representation learning.
17

---

Stochastic Block Graph Diffusion
D.3. Hyperparameter Tuning and Training
For training our network, adopt the widely-used Adam optimizer, tuning only the learning rate the primary hyperpa- rameter. To determine the optimal values for other hyperparameters in our model, we perform simple grid search over the following ranges:
Number of layers: [2, 4]
Hidden dimension: [8, 16, 32, 64, 128, 256]
Learning rate: [0.1, 0.05, 0.01, 0.005, 0.001]
Diffusion Length T: [50,100,200]
Sampling Steps: (000,200,500,1000
For the variance schedule, we follow the one in (Jo et al., 2022).
D.4. Evaluation Metric
Our evaluation focuses on two main aspects: (1) the quality of the generated graphs, assessing how well the method captures the underlying graph distribution, and (2) the memory consumption required during graph generation. To assess the quality of the generated graphs, we follow established graph generation studies and adopt both stuuctrr-bbssd and neural-based metrics. These metrics allow evaluate the generated graphs from different perspectives, ensuring a comprehensive comparison across methods.
1.4.1. STRUCTURE-BASED METRICS
Structure-based metrics evaluate how well the generated graphs match the statistical properties of real-world graphs. These metrics are critical for understanding whether the generated graphs preserve important structural characteristics like node connectivity and community structure, which are crucial for tasks like graph analysis and network modeling.
Maximum Mean Discrepancy (MMD): MMD is kernel-based metric that quantifies the difference between the distribution of graph properties in the generated graph and the real graph. Specifically, MMD measures how well the generated graph approximates the distribution of properties like node degrees, clustering coefficients, and orbit counts. The degree distribution reflects how nodes are connected within the graph, the clustering coefficient measures the tendency of nodes to form local clusters, and orbit counts capture the higher-order relationships between nodes (such as triangles and motifs), By comparing these properties between the generated and real graphs, MMD provides a robust measure of structural fidelity, where a lower MMD indicates better alignment between the graphs (Gretton et al., 2012).
D.4.2. NEURAL- HEURAL-BASED METRICS
Neural-based metrics evaluate the quality of generated graphs in the context of learned representations. These metrics useful for assessing whether the generator has captured not only low-level structural properties but also more abstract features that are harder to quantify with traditional metrics. This allows us to measure the generative model's performance in more holistic manner.
Fréchet Inception Distance (FID): FID is a widely used metric in generative models, originally proposed for image generation, that compares the distribution of features extracted from learned embedding space between the real and generated graphs. Specifically, we use FID assess the alignment between graph distributions in the embedding space produced by a pre-trained neural network. The key advantage of FID is that it compares high-level feature representations, providing insights into whether the generative model produces graphs that are not only structurally similar but also preserve the higher-level semantic relationships. A lower FID score indicates that the generated graphs are more similar to the real graphs in the learned embedding space (Heusel et al., 2017). This is particularly important when we are dealing with complex graph data that may contain non-trin non-trivial patterns or higher-order structures that are not easily captured by traditional structural metries.
18

---

Stochastic Block Graph Diffusion
D.4.3. MEMORY CONSUMPTION METRICS
In addition evaluating the quality of the generated graphs, we also focus on the memory efficiency the graph generation process. Memory consumption is crucial factor, especially for large-scale graph generation tasks, excessive memory usage can hinder the scalability of the model.
To ensure a direct comparison of memory efficiency between different methods, we define the memory consumption ratio as the ratio of the baseline model's memory consumption to our model's memory consumption. This metric highlights the relative efficiency of our approach in terms of memory usage during graph generation. A lower ratio indicates that our method requires less memory, making it more scalable and efficient, particularly when generating large graphs. By using our method reference point, provide a clear comparison of how different approaches perform in terms of memory consumption, which is essential for practical applications that require handling large-scale graphs.
Memory Consumption Ratio:
19


Reviews:
[{"review_id": "FKXHZDkfgW", "reviewer": "Reviewer_8djj", "summary": "This paper proposes a block graph representation on top of the diffusion model framework for graph generation. It claims to resolve the scalability and size generalization problems of existing models and comes with experiments on various benchmark datasets. The paper is generally well-written and easy to follow.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your detailed comments and thoughtful questions! They significantly help us improve the clarity and rigor of our manuscript. We appreciate the opportunity to address your concerns and questions below:\n\n## Details on Graph Sizes in Datasets\n\nWe apologize for omitting this information from the manuscript. The graph sizes used are publicly available, given the datasets utilized:\n\n1. **Planar:** Graphs with 64 nodes.\n2. **cSBM:** A synthetic graph dataset where graph size is configurable. For the main experiments (Table 2), we set the graph size to 180.\n3. **QM9:** Graphs with sizes up to 9 nodes.\n4. **OGBN-Arxiv:** Graphs up to 169,343 nodes.\n5. **OGBN-Products:** Graphs up to 2,449,029 nodes, significantly larger than other datasets, which explains the \"Out of Memory (OOM)\" issues faced by most methods.\n\nWe will include this explicitly in the revised manuscript.\n\n## Clarification on FID Metric for Graph Evaluation\n\nWe acknowledge your valid concern regarding the adaptation of FID (Frechet Inception Distance) from image to graph data. Following established practices in the literature ([1]), we adapted FID for graphs by utilizing a Graph Isomorphism Network (GIN) with random initialization as the embedding model. The embeddings were then used to compute FID scores following the standard procedure. We will clearly describe this approach in the updated manuscript.\n\nRegarding FCD and NSPDK, these metrics are specifically designed for molecular graphs, whereas our datasets primarily involve general graph structures. Thus, FID was chosen as a more universally applicable evaluation metric.\n\n## Experimental Setup of Figure 4(a)\n\nFor Figure 4(a), we used models trained on the cSBM dataset (graph size of 180) from Table 2, subsequently generating graphs of varying sizes. Please note the x-axis values represent graph size multiplied by 100. Figure 4 (a) shows that our method has the best size generalization performance among the tested methods.\n\nWe apologize for any confusion and will clearly state this in the revised manuscript.\n\n## Memory Usage and Computational Efficiency\n\nWe appreciate your suggestion regarding memory usage. Alongside the theoretical analysis, we reported relative memory usage ratios from the experiments in Table 2's last column. We acknowledge discrepancies between theoretical predictions and practical performance, which stem from specific implementation details and hyperparameter selections. The revision will provide additional details, explicitly discussing runtime and implementation-dependent factors.\n\n## Advantage for Distributed Training\n\nDue to technical constraints, we could not empirically verify advantages in distributed training scenarios. Therefore, we presented this as a theoretical discussion point rather than a main claim. This perspective will be clearly stated in the revised manuscript.\n\n## Distinction from PARD\n\nThank you for bringing PARD to our attention. While conceptually similar due to the principle on block structure, PARD represents a distinct class of graph generative models. It employs iterative component-based graph generation, aligning more closely with autoregressive models such as GraphRNN and EDGE. As such, PARD still require the entire graph in memory during generation, as noted in the original PARD paper ([2]). Our work specifically explores score-based diffusion generative models, thus positioning itself orthogonally to PARD.\n\nWe appreciate the recommendation and will cite and discuss PARD clearly in the related work section of our revised manuscript.\n\nWe greatly appreciate your insightful feedback and believe our revisions fully address your questions and concerns.\n\n[1] \"On Evaluation Metrics for Graph Generative Models.\" *International Conference on Learning Representations (ICLR)*.\n\n[2] \"PARD: Permutation-invariant Autoregressive Diffusion for Graph Generation,\" arXiv preprint arXiv:2402.03687, 2024.", "claims_and_evidence": "1. This paper claims to address the \"scalability\" concern of current graph generative models. To support this claim, it would be helpful to fully validate the approach with empirical experimental results. Could the authors compare the graph sizes in their benchmark datasets? For example, QM9 is relatively small in terms of average graph size (#nodes), while on the OGBN-products dataset, only the proposed method appears to train successfully without encountering an OOM error. Could the authors provide more details?\n\n2. The paper claims to improve \"size generalization\" capability, demonstrated by the quantitative results in Fig. 4(a), where FID is used. However, since FID was originally proposed for image generation, it would be helpful if the authors could clarify what type of pre-trained models were used to compute FID in the context of graph evaluation. Providing these details would ensure a fair and rigorous comparison.\nAlso, what are the experimental settings for Fig. 4(a)?", "methods_and_evaluation_criteria": "1. As mentioned above, some benchmark datasets may be too small to effectively validate the proposed method's ability to address the scalability issue. Please provide a clear comparison of their sizes.\n\n2. Please explain the details of how FID is used for graph data.\n\n3. Given that FCD and NSPDK (e.g., in [1,2]) are commonly used metrics for molecular generation tasks, could the authors clarify why these were not considered in the evaluation?\n\n[1] Yan Q, Liang Z, Song Y, Liao R, Wang L. Swingnn: Rethinking permutation invariance in diffusion models for graph generation. arXiv preprint arXiv:2307.01646. 2023 Jul 4.\n\n[2] Jo J, Lee S, Hwang SJ. Score-based generative modeling of graphs via the system of stochastic differential equations. InInternational conference on machine learning 2022 Jun 28 (pp. 10362-10383). PMLR.", "theoretical_claims": "The authors make several claims in Section 3.3: Theoretical Discussion, and below are my concerns.\n\n1. First, it would be valuable to report the actual memory usage during both training and inference. On the same hardware, how does the model’s running speed compare to the baselines? While the big-O analysis in Table 1 is informative, there may be a gap between theoretical complexity analysis and practical deep neural network deployment. Additional details on real-world computational efficiency would strengthen the discussion.\n\n2. The paper claims to have advantages in terms of \"Distributed Training.\" However, I do not see any real experiments supporting the claim that \"each computational node or device in a distributed system can handle smaller subproblems.\" While this may be conceptually true, the claim is fundamentally about practical implementation and must be validated by experiments to be considered valid.", "experimental_designs_or_analyses": "Already explained in the above comments.", "relation_to_broader_scientific_literature": "I don’t have any critical comments.", "essential_references_not_discussed": "More recent papers on graph diffusion models should be included as baselines for quantitative performance comparisons and technical discussions.\n\n[1] Yan Q, Liang Z, Song Y, Liao R, Wang L. Swingnn: Rethinking permutation invariance in diffusion models for graph generation. arXiv preprint arXiv:2307.01646. 2023 Jul 4.\n\n[2] Laabid N, Rissanen S, Heinonen M, Solin A, Garg V. Equivariant Denoisers Cannot Copy Graphs: Align Your Graph Diffusion Models. InThe Thirteenth International Conference on Learning Representations.\n\n[3] Zhao L, Ding X, Akoglu L. Pard: Permutation-invariant autoregressive diffusion for graph generation. arXiv preprint arXiv:2402.03687. 2024 Feb 6.", "other_strengths_and_weaknesses": "How is this paper different from previous work? Conceptually, it appears quite similar due to the decomposition process.\n\n[1] Zhao L, Ding X, Akoglu L. Pard: Permutation-invariant autoregressive diffusion for graph generation. arXiv preprint arXiv:2402.03687. 2024 Feb 6.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Already explained in the above comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "Z99dDW8DAV", "reviewer": "Reviewer_KH7S", "summary": "The manuscript introduces SBGD, a graph diffusion generative model based on a block representation inductive bias and aiming for lower memory complexity in the large-graph limit. SBGD first partitions the graph's nodes into $k$ non-overlapping groups using some pre-determined non-learned algorithm (here METIS). These groups partition the adjacency matrix into blocks of edges within the same group (diagonal blocks) or between two different groups (off-diagonal blocks). The Markovian forward process is decomposed into three independent \"noising\" conditional distribution: noising the node features $X_{i}^{(t)}$ group $i$'s nodes, noising the $i$-th diagonal block $A_{i}^{(t)}$ or noising the off-diagonal block $A_{ij}^{(t)}$ between group $i$ and group $j$. The noising and learned network score functions for the features and diagonal blocks are very Digress-like, and something lighter (not 100% clear to me at this time) is done for the off-diagonal blocks. The (sampling) backward process for each group is independent (though node features and diagonal blocks are jointly generated), and off-diagonal blocks are generated in view of the two groups they connect (again, details not 100% clear). Empirical results appear good. The theoretical scaling complexity is improved, and the manuscript's algorithm can run on OGBN-products while other approaches OOM on the same (frugal-ish) hardware.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your knowledgeable comments and insightful feedback. We greatly appreciate the time and effort you’ve invested in evaluating our work. Below, we address your concerns and questions. Please note that the responses may not follow the exact order of your original remarks, but we have ensured all points are addressed thoroughly.\n\n## Algorithms for Training and Sampling\n\nWe sincerely apologize for the confusion caused by the outdated pseudocode and associated inaccuracies in the description of our sampling procedure. Below, we clarify both the training and sampling processes, and we will revise the pseudocode accordingly in the updated manuscript.\n\n- **Training Process:** Our training approach follows a strategy similar to ClusterGCN [1]. At each iteration, we randomly sample two diagonal blocks and perform score learning using the diffusion model. The interaction between these two blocks (i.e., the off-diagonal component) is not subjected to the diffusion process but is instead inferred using a lightweight interaction network in a one-shot manner. As discussed in the paper, the motivation for this design is rooted in the fact that off-diagonal interactions tend to be sparse and easier to learn directly.\n- **Sampling Process:** Once the score networks and interaction networks are trained, graph generation are very flexible. First, one can generate the $k$ diagonal blocks using any preferred sampling method (e.g., DDPM, DDIM, or other variants). Then, the off-diagonal connections between each pair of blocks are generated using the interaction network.\n\nWe regret the confusion and will ensure the corrected pseudocode and explanations are clearly reflected in the revision.\n\n## Experimental Setup for Figures 3 and 4\n\nThank you for pointing this out. Both Figures 3 and 4 use graphs generated from the cSBM model; however, the training graph sizes differ slightly: In Figure 3, training graphs have a size of 100. In Figure 4, training graphs have a size of 180, which matches the size used in our main experiments (e.g., Table 2).\n\nAdditionally, the x-axis labels in Figure 4 should be interpreted as scaled by 100. We apologize for the oversight and will clarify this in the revised version of the manuscript.\n\n## Limitations of the Model and Potential Extensions\n\nThank you for your insightful critique regarding the model’s blind spots.\n\nWe fully acknowledge that our approach—emphasizing assortative, block-wise dense structures—may not effectively capture certain types of graphs, particularly disassortative networks or structures like star graphs. These represent important limitations of the current modeling framework.\n\nThat said, our structural prior is not arbitrary—it reflects common empirical patterns observed in many real-world networks, where assortativity and local structural cohesion are prevalent. In such domains, our assumptions are well-aligned with the underlying data distribution, contributing to the strong empirical results.\n\nWe find your proposed variation—autoregressive generation of both diagonal and off-diagonal blocks, with conditioning on previously generated content using GNNs—particularly compelling and interesting! This approach could capture richer inter-block dependencies and remain scalable controlled memory use. This is an exciting direction for future research, and we are grateful for your thoughtful suggestion.\n\n## Ablation on the Partition Algorithm\n\nOur choice of the METIS partitioning algorithm is motivated by our core modeling assumption: dense and homogeneous intra-block (diagonal) structure, with sparse inter-block (off-diagonal) connections. METIS is well-known for effectively partitioning graphs into balanced clusters while minimizing edge cuts—making it a natural fit for our setting.\n\nIn early experiments, we did explore random partitioning, but found that it yielded significantly worse performance, likely due to poorly aligned block structures and noisier diffusion learning. We will try to include a more systematic study on this in the revision.\n\nOnce again, we sincerely thank you for your constructive feedback. Your comments have helped us identify critical areas for clarification and potential extension, and have significantly improved the clarity, correctness, and quality of our manuscript.", "claims_and_evidence": "(Claim numbering is my own.)\n\n### Claim 1\n\n> Empirical results show that SBGD achieves significant memory improvements (up to 6×)\n\nThe core idea of breaking down a large graph into block structures to improve memory efficiency makes a lot of sense, and this claim is supported both theoretically (Section 3.3 and Table 1) and experimentally (last column of Table 2).\n\n### Claim 2\n\n> while maintaining comparable or even superior graph generation performance relative to state-of-the-art methods.\n\nThe results presented in Table 2 support this claim that the method offers competitive performances despite the memory savings. I have reservations as to how performances on this type of benchmark would translate to concrete use-case scenario, but this is an issue pervading the whole generative graph modeling subfield: I don't think that I can fault the manuscript for this.\n\n### Claim 3\n\n> experiments on size generalization demonstrate that SBGD exhibit better size generation, particularly exceling at generating graphs larger than those seen in the training set\n\nI fail to find the experimental setting details for the results shown in Figures 3 and 4(a). Figure 3 is not convincing to me: the training graph (leftmost) in Figure 3 has block-like structure quite aligned with the manuscript's main new modeling assumption, and if similar graphs are used in Figure 4(a), then the manuscript's claim is greatly weakened, and should minimally be amended to clarify this reliance on very specific graph structures.\n\n### Claim 4\n\n> that smaller block representations initially improve performance, but excessively small blocks can degrade generative quality\n\nThe claim makes sense and is supported by Figures 4(b-c), although it is not clear what dataset/protocol was used to produce these figures. The suggestion of \"an optimal block size, with granularity depending on the data’s properties\" could have (but wasn't) easily probed by plotting Figures 4 (b-c) for different datasets.\n\n### Claim 5\n\n> it exemplifies the principle of modularization in generative modeling, offering a novel way to explore generative models by decomposing complex tasks into more manageable components\n\nIt does. Writing this review spurred many ideas as to how to \"fix\" this work's weakest points, ideas made \"obvious\" now that this corner of the design space has been made visible to me. This manuscript has faults, but its core idea is both valid and important.", "methods_and_evaluation_criteria": "As mentioned above, there appear to be no details (neither in the main paper nor appendices) as to the experimental setting surrounding Figures 3 and 4.\n\nAlso as mentioned above, to the best of my understanding, the evaluation criteria are limited but standard for the subfield.\n\nI believe that the presentation of SBGD lacks important details necessary for reproducibility, notably on the front of the off diagonal blocks. In particular, lines 8 and 10 of Algorithm 2 (Appendix B) are incomplete (and/or incompatible). Is $\\widehat{A}_{12}$ obtained in one shot, or by DDIM/DDPM? This needs to be clear!\n\nMoreover, my understanding is that lines 6 and 7 of the same Algorithm 2 should both involve two separate calls to the score functions (like is done for the features on line 5), and that what is currently displayed on those lines implies a coupling between the diagonal blocks that is not mentioned elsewhere in the manuscript. Also, compared to Algorithm 1, the explicit dependencies in features are gone.\n\nThis appendix appears to aim for conciseness, at the cost of clarity/correctness, but there is no space limit for appendices. Please be clear!", "theoretical_claims": "I looked at all equations in the main text, but did not check any proofs in details. I gave some more attention to the algorithms, and found them wanting.", "experimental_designs_or_analyses": "I already mentioned issues surrounding Figures 3 and 4.\n\nI am not anymore following this subfield in enough details to properly assess the details surrounding Table 2.", "relation_to_broader_scientific_literature": "I've been out of date with the subfield for the last 2 years. The paper that I know should be cited, are cited. What is surprising is the absence of papers that I don't know: except for Aref & Mostajabdaveh (2024) cited in appendix, it looks like I didn't miss much in the last two years... That, or there are missing references!", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "There are typos, inconsistencies and/or lack of clarity at critical points in the manuscript. I have already mentioned Algorithm 2's deficiencies elsewhere. Figure 2 uses $\\mathbb{P}$ to represent the forward (noising) process, and $\\mathbb{Q}$ for the backward (denoising) one, but the unnumbered equations in Section 2.1 use the opposite. The caption of Figure 2 does not go in enough details to help me understand the model (and it has another typo in the expression for $\\mathbb{Q}$).\n\nFurther ablation studies are lacking, notably comparing random partitioning vs METIS. I don't currently understand the details as to how the off-diagonal blocks are obtained, but when I'll do I'll probably wonder what happens if this network is given as much capacity as the diagonal one (or the converse).", "other_comments_or_suggestions": "The manuscript favours an \"assortative\" view, where the off-diagonal blocks are sparser than the diagonal ones. But disassortative networks exist, and some generalization of this model could address them.\n\nMore generally, I suggest that the authors ponder what are the \"blind spots\" of this modeling approach, and discuss them, the cases where they may be more/less relevant, and potential workarounds. For example, suppose a training dataset where all graphs have a single node that is connected to most other nodes, whereas all other nodes' degree have an hard cap that is much lower than the block size. In the present algorithm, each diagonal block is generated independently, so there is no way to guarantee that exactly one such block will contain exactly one high-degree node. This is an example of a \"blind spot\", some structure that this model cannot capture. Other examples includes anything that involves at least 3 diagonal blocks or 2 non-diagonal ones.\n\nHere is a variation that I think could eschew many of these limitations. We can view the problem as the autoregressive generation of blocks (diagonal or not) one-by-one, where generating each block demands to perform DDIM or DDPM. In this view, this paper chooses to generate all diagonal blocks first, then generate the off-diagonal ones conditional on the two diagonal blocks they each connect. However, other orders are possible, and the conditioning could *a priori* depend on all previously generated blocks using, e.g., GNNs. If the graphs are sparse, there is a regime where these GNNs can be kept in check while preserving the $C^2$ memory complexity.", "questions_for_authors": "My score of 2 indicates that, in it's current state, I would reject this manuscript, but I do see a possible path forward for me to recommend acceptance. This path depends on the answers to the following questions.\n\n### Question 1\n\nDo you disagree with, or wish to make any clarification about, any assessment I made in this review? If yes, could you please clarify your perspective?\n\n### Question 2\n\nIs an actual forward (noising) process involved for the off-diagonal adjacency matrices? Is the inference done in one-shot?\n\n### Question 3\n\nCan you clarify/fix Algorithm 2? Please be explicit, using $i$ and $j$ instead of $1$ and $2$ to clearly indicate how to proceed when there are more than two blocks. In other words, I should be able to read the \"Computation Complexity\" of Figure 1 from the loop structure. Please pay special attention to function signatures: if $s_\\theta$ accepts 4 arguments and returns one output in Algorithm 1, it should accept 4 arguments and return one output in Algorithm 2.\n\nYou *may* do the same for Algorithm 1, especially if you notice some consistency/correctness issues while fixing Algorithm 2.\n\n### Question 4\n\nCan you provide all experimental details surrounding Figures 3 and 4? Please see my comments on Claims 3 and 4 above for details.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c96f7hobFO", "reviewer": "Reviewer_mdPb", "summary": "This paper introduces the SBGD model to address the scalability and size generalization challenges of Graph Diffusion Generative Models (GDGMs). Traditional GDGMs struggle with high memory requirements and poor generalization to graph sizes not seen during training. SBGD mitigates these issues by refining graph representations into a block graph space, leveraging structural priors to reduce memory complexity and enhance generalization. Empirical evaluations demonstrate that SBGD achieves memory savings while maintaining the graph generation performance of state-of-the-art methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, thank you for the insightful comments and helpful suggestions. These greatly help us improve upon the current paper, and we appreciate the opportunity for addressing your questions and concerns here.\n\n## Clarification of Graph Size\n\nWe intended the term \"graph size\" to specifically refer to the number of nodes. The confusion may stem from the visualizations in Figure 3, where denser layouts naturally arise as the node count increases (given a fixed edge-to-node ratio), making the graphs appear more connected. We will revise the manuscript to make this definition explicit and improve the accompanying figure captions for clarity.\n\n## Determination of the Number of Partitions\n\nThe number of partitions is treated as a tunable hyperparameter. As shown in Figure 4(b), our empirical analysis suggests that the optimal number of partitions depends on both the dataset and task. Extremely fine or coarse partitions tend to degrade performance due to underfitting or oversmoothing, respectively. We will explicitly state this in the revised manuscript and offer guidance on selecting this hyperparameter based on validation performance.\n\n## Comparison with Other Partitioning Techniques\n\nOur use of the METIS partitioning algorithm is motivated by the core modeling assumption that intra-block (diagonal) structures are dense and relatively homogeneous, while inter-block (off-diagonal) interactions are sparse. METIS is well-suited for this setting, as it efficiently divides graphs into balanced clusters while minimizing edge cuts.\n\nWe did experiment with random partitioning during early development, but observed significantly worse performance—likely due to incoherent block structures and noisier learning dynamics. We will aim to include a more systematic study of this comparison in the revised version.\n\n## Details on Theoretical Derivation\n\nThank you for pointing this out. We agree that providing more detailed derivation steps will enhance the clarity and completeness of the theoretical section. We will expand this part in the revision to include step-by-step derivations and clarify underlying assumptions.\n\n## Comparison with DruM (ICML 2024)\n\nWe appreciate the pointer to DruM—an interesting and related work. While both papers share a modular principle, the core assumptions and objectives differ:\n\n- DruM assumes that the graph distribution is multi-modal, and it decomposes the generative process into learning distinct modes to facilitate inference.\n- In contrast, our approach focuses on structural decomposition for memory efficiency, leveraging graph partitioning to operate on block-level representations. Our method does not rely on mixture modeling of distributions and avoids storing the full graph at once.\n\nWe will cite DruM in the revised manuscript and include a more thorough discussion in the related work section to highlight the differences and complementarity.\n\n## Discussion on Broader Impacts\n\nThank you for noting the omission of an impact statement. We will include one in the revised manuscript. Our method is designed for memory-efficient graph generation, which could lower the barrier for training generative models in resource-constrained environments, such as laboratory settings or edge devices. We do not foresee any immediate or specific negative societal impacts, but will include a balanced impact statement in line with standard publication policies.\n\n## Clarification on Distributed Training and Information Loss\n\nWe appreciate this question. In our training procedure, the fundamental unit is a **block pair**, which consists of two block graphs and their mutual interactions. In addition to training score networks for each block, we train a lightweight interaction network to model the off-diagonal connections.\n\nThis design enables distributed training, where block pairs can be allocated across multiple devices without the need for inter-device communication, since each block pair is self-contained. We will clarify this in the revised manuscript to highlight the scalability benefits of our approach.\n\nOnce again, we sincerely thank the reviewer for the thoughtful and constructive feedback. We hope our response has satisfactorily addressed your questions and concerns.", "claims_and_evidence": "The proposed SBGD method claims improved computational efficiency and generalizability. While the authors provide complexity comparisons in Table 1 and memory ratios in Table 2, an empirical analysis of training time would strengthen their efficiency claims. Regarding generalizability, the term \"graph size\" is somewhat ambiguous. In Figure 3, it appears to refer to the density of the edges. Please clarify the definition of \"graph size.\"", "methods_and_evaluation_criteria": "The method is straightforward yet appears effective. The decomposition of large graphs into blocks facilitates sparse graph construction. The efficiency and effectiveness of the proposed model are closely tied to how the graph is partitioned. The authors address this in Figure 4 with empirical results. How do the authors determine the number of partitions? Is it treated as a hyperparameter, or is it based on another metric?\n\nIn Appendix C2, the authors use METIS partitioning, which results in balanced graph blocks with approximately equal node counts. This might not be the case for real graphs, while we might find unbalanced blocks. Did the authors compare this method with other partitioning techniques?", "theoretical_claims": "The authors provide a theoretical discussion on model complexity. It would be beneficial to include more details on how these results are derived.", "experimental_designs_or_analyses": "The experiments are well-designed and effectively support the claims of efficiency and generalizability. One thing to note is that the authors missed one state-of-the-art baseline DruM[1]. Please add that into comparison if possible.\n\n[1] Graph Generation with Diffusion Mixture, ICML 2024", "relation_to_broader_scientific_literature": "Graph generation is a significant issue with applications across various domains. Diffusion-based graph generative models struggle with large graphs, and the proposed SBGD addresses this through block-wise modeling. While this contribution is noteworthy, a more in-depth discussion of its potential positive and negative impacts would be beneficial.", "essential_references_not_discussed": "See Experimental Designs Or Analyses for DruM[1].\n\n[1] Graph Generation with Diffusion Mixture, ICML 2024", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "The authors mention distributed training for block-wise modeling in their theoretical discussion, which is somewhat unconvincing. Node-wise samplers are well-implemented in both DGL and PYG and support distributed training. Additionally, treating blocks as batches may lead to information loss if edges between blocks are ignored. Can the authors elaborate on this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents SBGD, a diffusion-based graph generative model leveraging stochastic block structures to address key challenges in scalability and size generalization. The reviewers broadly appreciate the paper’s core idea of decomposing graphs into block representations to reduce memory overhead, enabling training on large-scale graphs. Empirical results support claims of competitive performance with improved efficiency.

Following the rebuttal, all reviewers either maintained or increased their scores, indicating that key concerns were satisfactorily addressed.
Decision: Accept (poster)