SparseDiff: Sparse Discrete Diffusion for Scalable Graph Generation
Authors: Yiming QIN
Clement Vignac
Pascal Frossard
Venue: Accepted by TMLR ()

Abstract: Graph generative models encounter significant scaling challenges due to the need to predict the presence or type of edges for every node pair, resulting in quadratic complexity. While some models attempt to support large graph generation, they often impose restrictive assumptions, such as enforcing cluster or hierarchical structures, which can limit generalizability and result in unstable generation quality across various graph types. To address this, we introduce SparseDiff, a novel diffusion framework that leverages the inherent sparsity in large graphs - a highly relaxed assumption that enables efficient sparse modeling without sacrificing generation quality for different datasets. SparseDiff reduces the complexity of the three core components in graph diffusion models. It first introduces a noising trajectory that preserves sparsity with more memory-efficient computation. During training, SparseDiff uses a denoising network based on convolutional attention layers over a sparse edge subsets combining edge-based graph attention and query edge-based random attention mechanisms, maintaining expressiveness with reduced memory usage. Finally, for inference, at each denoising step, SparseDiff generates edge subsets iteratively, progressively reconstructing the adjacency structure. SparseDiff achieves state-of-the-art results on both small and large datasets, showing its robustness across varying graph sizes and its scalability. Additionally, it ensures faster convergence for large graphs, achieving a fourfold speedup on the large-scale Ego dataset compared to dense models. SparseDiff's efficiency, combined with its effective control over space complexity, positions it as a powerful solution for scaling applications involving large graphs.

Published in Transactions on Machine Learning Research (07/2025)
SifrseDiff: Sparse Discrete Diffusion for Scalable Graph Generation
Yiming Qin Ecole Polgtechnique Fédérale de Lausanne (EPFL)
giming-qiin qin @epft..ch
Clément Vignac
signac@@isooorppiillaab..cm
Ecole Polgtechnique Pédérale de Lausanne (EPFL)
Pascal Frossard
pescol.frossardd@epf...
Ecole Polytechnique Fédérale de Lausanne (EPFL)
Reviewed on OpenReview: https: // opw.reviee.....ee..em net/ forum? id= kuJ3kppn
Abstract
Graph generative models encounter significant scaling challenges due the need to pre- dict the presence type of edges for every node pair, resulting in quadratic complexity. While some models attempt support large graph gencration, they often impose restrictive assumptions, such as enforcing cluster hierarchical structures, which can limit generaliz- ability and result in unstable generation quality across various graph types. To address this, we introduce SparseDiff, a novel diffusion framework that leverages the inherent sparsity in large graphs a highly relaxed assumption that enables efficient sparse modeling with- out sacrificing generation quality for different datasets. SparseDiff reduces the complexity of the three core components in graph diffusion models. It first introduces a noising tra- jectory that preserves sparsity with more memory-efficient computation. During training, SparseDill uses a denoising network based convolutional allention layers over sparse edge subsets combining edge-based graph attention and query edge-based random attention mechanisms, maintaining expressiveness with reduced memory usage. Finally, for inference, at each denoising step, SparseDiff generates edge subsets iteratively, progressively recon- structing the adjacency structure. SparseDiff achieves state-of-the-art results on both small and large datasets, showing its robustness across varying graph sizes and its scalability. Additionally, it ensures faster convergence for large graphs, achieving fourfold speedup the large-scale Ego dataset compared to dense models. SparseDiff's efficiency, combined with its effective control over space complexity, positions it powerful solution for scaling applications involving large graphs.
1 Introduction
Graph generation plays a pivotal role in various fields, such molecular chemistry (Vignac al. 2023b neural architecture search (Asthana et al. 2024) and social network analysis (Schweimer et al. 2022 for its ability to model complex relationships and create realistic structured data. Over the past docades, random graph models have played a foundational role in graph generalion (Erdös et al. 1960 Barabási 2013
However, their limitations in capturing complex dependencies in real-world data have shifted research toward machine learning based graph generative models. Traditional frameworks like generative adversarial networks (De Cao & Kipf 2018) and variational autoencoders (Simonovsky & Komodakis 2018) have primarily focused
small graphs. Recently, denoising diffusion models (Jo et al. 2022 Niu al. 2020); especially those
employing discrete modeling to better capture graph structure (Vignac et al. 2023a. have emerged, setting
"ooees available hattps://githan wwtp:/mmm//pparseaiiiiii

---

Published in Transactions on Machine Learning Research (07 (07/2025)
1. Efficient noise model
2. Sparse denoising network
3. Iterative inference
Gn
True labels
E
Query edges g
Sparse noise
Cross-entropy
Ey
G (8. 88. Fd)
Predicted distribution
E
Figure 1: SparsoDiff employs three key components for efficiency: (1) a noise model that constructs a sparse noisy graph G with high probability, preserving sparsity and enabling more efficient computation, (2) a denoising network trained over all nodes and a sparse subset of query edges with controllable size, Eg. and (3) iterative inference step that, at each time step t, progressively fills the adjacency matrix using sparse inputs given by Eyy, for E {1.
new benchmarks in graph generation tasks and improving scalability by gencrating graphs with up 200 nodes. Nonetheless, scaling to larger graphs remains challenging, restricting application in fields such protein generation (Yim et al. 2023), histopathology (Madeira et al. 2023). transportation (Rong et al.
2023) or anomaly detection in financial systems (Li et al. 2023).
Motivated by these limitations and recognizing that most real-world graphs are inherently sparse - for instance, cells in digital pathology connect only with immediate neighbors (Madeira et al. 2023), and con- nections in social networks are sparse (McCallum al., (2000) we propose SparseDiff. SparseDiff is a discrete diffusion framework that leverages graph sparsity without additional assumptions, Our technical contributions are fourfold. (1) We observe the universal sparsity of real-world graphs, adopting sparse triplet graph representation (E,X, X, Y) in place of dense formats, which scales more efficiently for graphs with different sizes (see Appendix E.2 This enables the realization of the remaining contributions of SparseDiff, representing the three core components of diffusion models (detailed in Section 2.1 as illustrated in Figure ! (2) The efficient noise model (Section 3.1 introduces a sparse noising process that preserves the sparsily of graphs along the forward diffusion trajectory with more space-efficient computation. (3) The sparse denoising neural network (Section 3.2) uses convolutional attention layers adapted to our sparse graph reprosentation. Its complexity scales with the number of non-zero entries of its sparse attention map, which covers existing edges and tunable number of random node pairs, enabling training large graphs under controllable space complexity without compromising performance. The model is trained on random query edges at each step, analogous to mini-batches in SGD, allowing optimization under constrained computation resources. (4) The iterative inference procedure (Section 3.3) modifies the standard sampling strategy to align with the sparse attention used during training. At each diffusion step, it incrementally reconstructs the dense adjacency matrix by adding odge subsets defined by query edges, maintaining structural consistency and improving efficiency generation time.
Our experiments demonstrate that SparseDiff consistently achieves state-of-the-ate performance both small graphs, including those with complex priors like molccular graphs, and large graph datascts. Notably, SparseDiff handles much larger graphs (up to 2485 nodes), while the performance of DiGress degrades on graphs with over 200 nodes. Specifically, SparseDiff outperforms both dense models like SPECTRE (Martinkus et al.) 2022) and DiGress (Vignac al. 20223), as well as other scalable models like EDGE (Chen) et al. 2023) and HGGT (Jang et al. 2023).. SparseDiff also converges four times faster than dense diffusion models large graphs, such social networks. These results empirically demonstrate the effectiveness of
2

---

Published in Transactions on Machine Learning Research (07/2025)
our sparse modeling approach and confirm its robustness through consistently high performance across diverse range of datasets.
In summary, SparseDiff is able to match the performance of dense diffusion models without restrictive assumptions, pioneering the use of sparse representations in graph diffusion, and distinguishing it from hierarchical and autoregressive methods. SparseDiff implemented within the discrete diffusion framework, specifically following the setup of Vignac et al. (2023a). Its noise model is particularly well-suited for scenarios where non-existent edges dominate, such as marginal trajectories in SparseDiff absorbing trajectories that converge to empty graphs. Additionally, the sparse attention mechanism and iterative sampling are broadly applicable to both diffusion or flow-based generative models, as they focus soicly on sparsifying the attention map and the corresponding adjaceney matrix. As a remark, while Sparse can potentially improve diffusson and flow models with sparse noisy graphs, it provides no benefit for continuous models that do not preserve sparsity, as they must be modeled using a dense adjacency matrix.
2 Related Work
2.1 Denoising Diffusion Models for Graphs
Diffusion models have gained increasing popularity due to their impressive performance across various gen- erative tasks in fields such as computer vision (Dhariwal & Nichol 2021: Ho et al. 2022), protein generation (Bakk al. 2021 Ingraham et al. 2022), and audio synthesis (Kong et al. 2020). These models are char- acterized by three core components. The first is Markovian noise model, which progressively corrupts data point to a noisy sample 2f over iterative steps from 1 to T, until it conforms to simple pre- defined prior distribution at step T. The second component is denoising network, parametrized by 0 which is trained to restore the corrupted data back to its less noisy state. Typically, this network aims to predict the original data x given the noisy sample 2'. The third component is the reverse process for data generation, where a fully noisy data point 2" is first sampled from a prior distribution. The denoising network then operates at cach time step E [T...., 1] to predict the less noisy distribution according to po(="~1|=') = J, q(="~1/24, (1)(x=)²), from which a new data point. z'-1 is sampled. While this integral is generally difficult to evaluate, two prominent frameworks, Gaussian diffusion (Ho et al. 2020 and discrete diffusion (Austin et al.] 2021), facilitate its efficient computation.
Initial graph diffusion models employed Gaussian noise directly on adjacency matrices NNu et al. 2020 Jo
et al. 2022). These models use graph attention network to regress the added noise e, where e = x' I, effectively regressing the noise up to an affine transformation, akin to regressing the discrete clean graph. To preserve the inherent discreteness of graphical data, subsequent models (Vignac al. 2023a Hacfeli et al., 2022) have leveraged discrete diffusion, reformulating graph generation as series of classification tasks, and achieving top-tier results. However, these models require predictions for all pairs of nodes, which implies a quadratic space complexity and thus restricts their scalability. We further provide a detailed discussion of discrete graph diffusion models in Appendix E.2
2.2 Scalable Graph Generation
Efforts to enhance the scalability of graph generative models mainly follow two paradigms: hierarchical re- finement and subgraph aggregation. The hierarchical refinement approach initially generates a low- resolutinn graph, which undergoes successive refinements for enhanced detail YYang et al. 2021 Karami 2023 For instance, the HGGT model (Jang et al.) 2023) employs hierarchical K²-tree representation. For molecule
generation, fragment- baased models (Jiin et al. 2018 2020 Maziarz et al. 2022 adeptly assemble compounds
using pre-defined molecular fragments. Recently, Bergmeister et al. 2023) proposes a hierarchical diffusion model based on spectrum-presrriigg local expansion algorithms, enabling the generation of non-attributed large graphs. On the other side, the subgraph aggregation approach divides larger graphs into smaller subgraphs, which are subsequently combined. For instance, SnapButton (Yang et al.] (202I) enhances au- toregressive models (Liu et al.] 2018 Liao et al. [209 Mercado et al., [2021] by merging subgraphs, and SaGess {Limnios et al.) (2023) trains a dense diffusion model to generate subgraphs sampled from a large graph that are then merged.
3

---

Published in Transactions on Machine Learning Research (07 (07/)025)
Additionally, some approaches predict all node pairs in an auto-regressive manner. Kong et al. (2023) integrated diffusion with autoregressive models, suggesting learning the node ordering, which is theoreti- cally as difficult as isomorphism testing. Alternatively, EDGE (Chen et al.) (023) uses absorbing states to create sparse diffusion by first gencrating a node degree distribution d' and gradually constructing the adjacency matrix A based on node degree changes during inference. While this factorization is universally applicable, the conditional distribution po( (A d may occasionally lead to degree distributions that are not feasible for undirected graphs during sampling, introducing slight misalignment between training and gen- eration. EDGE's performance also falls behind SparseDiff both small and large graphs. Besides, while latent diffusion is commonly used for scalability in vision tasks, applying it to graphs is more challenging due to permutation equivariance, where the decoded graph can appear in any permutation, necessitating graph matching. Current latent graph diffusion models either use predefined orderings (Evdaimon el al., 2024), or perform diffusion on node features followed by link prediction (Yang et al, 2024), with the latter underperforming SparsoDiff or other dense models (sce App. E.1 for details).
Overall, scalable generation models often introduce dependencies on node orderings, incorporate assumptions about data distributions, leverage specific graph properties, while latent graph diffusion faces challenges for graph matching. In contrast, the SparsoDiff model described in the next section aims at making no assumption besides graph sparsity, offering more general and streamlined framework for graph generation, while preserving competitive performance across a wide range of graphs with different sizes.
3 SparseDiff: Sparse Discrete Diffusion for Graph Generation
We now introduce SparseDiff, a Sparse Denoising Diffusion Model that matches the performance of dense models while significantly enhancing the scalability of graph diffusion to graphs with over 2, 000 nodes, significant improvement over previous dense models limited to around 200 nodes.
Unlike previous graph diffusion models, SifrseDiff builds on a sparse representation of graphs A graph G, consisting of n nodes and m edges, is represented as a triplet X,, X, Y). Here, E E N2xm indicates the edge list with the indices of endpoints. Node and edge attributes are considered to be discrete and are encoded in a one-hot format as E [0,1] and Y E (0, jmxb, where a and b are the number of classes, respectively. In particular, non-existing edges are considered an additional edge type, while edges in E are referred to ezrsting edges. This sparse representation is widely supported by standard graph processing packages such Pytorch Geometric (Fey & Lenssen 2019).
This work focuses solely on undirected graphs with discrete attributes, although continuous labels can be integrated, in a similar way to Viinac et al. (202bb). All considered graphs are free of self-loops. Figure [ provides an overview of SparseDiff framework. Further details on the training and sampling processes are provided Algorithms | and 2 respectively. In the following parts, we specifically focus on three critical components of the diffusion model as detailed in Section 2.1] the noise model, the denoising network, and the sampling algorithm. Appendix A summarizes the notation used throughout the paper, and Appendíx A.I further provides a detailed breakdown of the space efficiency for each component.
3.1
Efficient Noise Model
To improve memory efficiency, SparseDiff employs a dedicated noise model that maintains a similar sparsity level of the noisy graph Gt thronghout the noising trajectory under theoretical guarantee, as detailed in Section 3.1.1 This model also reduces the space complexity for computing noisy graph distribution as detailed in Section 3.1.2
3.1.1 Sparse Trajectory
Given that Gaussian noise applied to the adjacency mairix during diffusion typically results in dense noisy graphs, where all edge entries in the adjacency matrix acquire continuous values (Niu et al. 2020 Jo et al., 2022) we opt for discrete diffusion framework. In this framework, we sample a graph structure from the noisy distribution, allowing us to focus only on existing edges within the noisy graph, thereby reducing the number of edges necessary for computation. Tn the discrete graph diffusion model, the noisy trajectory
4

---

Published in Transactions on Machine Learning Research (07 2205))
each step is defined by ((=")=")=((XX)) YQy), where Q' represents the Markov transition matrix for that step 4, which transforms G into noisier distribution until reaching G²,, which follows predefined prior distribution that is easy to sample. Different types of Markov transition matrices are employed to corrupt the graphs into various prior distributions, inchuding uniform distributions, a special absorbing state (Austin el al. 2021), or marginal distributions (Vignac el. al. 2023a).
In this work, we employ the marginal transition model, which favors transitions towards the dominant class in the marginal distribution of the data. This strategy is particularly effective for preserving graph sparsity by naturally biasing toward non-existing edges, which is the dominant edge class for large graphs. Formally, considering the marginal distribution vectors px for node types and PE for edge types, and denoting their transposes by p', the noise level at each step is regulated by 8 with a' = 11- - -3. Formally, the marginal transition matrices are defined as follows:
=
-y=a'I+ 1spy
Here, 1, and 1, are column vectors of ones with dimensions equal to the number of classes a for nodes and for edges. These matrices incorporate a first term, the identity matrix I, to preserve the distribution from G²-1, and a second term to introduce noise aligned with the marginal distributions, namely px and Pg-
By employing continuous multiplication, we can derive the distribution at step directly from the initial clean graph using (G' (XQ'x )Q facilitating immediate transition to the noisy state without the need for iterative step-by-step calculations. For instance, the cumulative transition matrix Q' for nodes X is as follows: Q'x Q 2x Qx ā'I + (1 - a²) La)'x where Œ' = =aaa² a'. The parameter a² starls very close to 1 at at and approaches 0 al a², reflecting a gradual increase in noise influence over the diffusion process.
We note that this choice of marginal noise model does not guarantee that the noisy graph is always sparse. However, it is the case with high probability, stated by the following lemma, which is an application of Desolneux et al. (0088) (detailed in Appendix A.2
Lemma 3.1. (Probability Bound for Sparsity in Noisy Graphs) Consider an undirected graph with n nodes, m edges, and no self-loops. If the edge rutio given by m/ (() is denoted as and the edge ratio in the noisy groph sampled from the morginal transition noise model is given by re, then for n sufficiently large and r < 4' for any r < k < 1, we have:
k: <llog & + +1 log log(P(r, k]) -0())
(7)
k k 1-r
(1)
This lemma demonstrates that, in large and sparse graphs, the probability of the edge ratio Tn in the noisy graph exceeding threshold & (where k >> r) declines exponentially with graph size. For instance, in graphs with a low edge ratio and setting the edge threshold at k = 2r, the probability that the noisy graph exceeds k edges is approximately die = where 61 and 02 are constants. This probability decreases substantially as the graph size n grows.
3.1.2 Sparse Computation
The second requirement for the noise model is to reduce the space complexity for computing the noisy distribution. Standard discrete diffusion models represent all edges using Y E Roxaxb with transition probabilities computed as Y YQ' E gx resulting in O(n²) space complexity. To address this, we soparate existing edges from non-cxisting ones, as the latter primarily contribute quadratic complexity in sparse graphs. We define the set of indices of non-existing edges as Ene E (2x(())-m), where E E N2xm represents the set of indices of existing edges. Together, E and E,e form a partition of all node pairs.
Specifically, we compute YO E Rd for existing edges with space complexity O(m), we then sample new edge labels dircctly from this distribution, while removing edges transitioning to non-cxisting states to maintain sparsity in G For non-existing edges Exe, which typically drive quadratic complexity, we introduce a novel three-step approach to sample efficiently without dense adjacency matrices.
5

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
A
(0.2)
(0.3)
(0.1)
(0.2)
(0.3)
A B
C
D
1. flatten
B
C
(1.3)
2.
sample
B
C 00.
D
E
F
(0.
3)
4. convert back
D
3. insert
A
B
C
D
existing edges
new edges
Figure 2: Efficient sampling of new edge positions among non-existing positions is achieved using only the edge list, avoiding the quadratic space complexity of an adjacency matrix. The process involves: (1) Conceptually flattening the pair representations into a linear array, (2) Sampling uniformly positions from non-occupied positions from Ene: selecting A (1st) and (3rd), (3) Inserting offsets of and 2 the positions of and C to account for the count of existing edges before the selected positions, resulting in positions A (1st) and E (5th), and (4) Converting these positions back to index pairs (0, 1) and (1,3).
1. Sampling new edge count: Let m, (o) - m, denote the number of non-existing edges in G The number of new edges is sampled as ~ Bm,,, 4:), where q = 1 ["[0, represents the probability of a non-existing edge transitioning to an existing one.
Sampling positions: The new edge positions are selected uniformly at random from Ene-
Sampling edge attributes: The attribute of each new edge is drawn from the Multinomial distri- bution Multinomial 1 b)), representing the transition probabilities over existing edge types.
In this approach, Step employs Binomial distribution B(,,, 9t) to efficiently disregard edges that remain non-existent, focusing computation solely on newly emerging edges to reduce overhead. Step 2, sampling new edge positions, presents additional challenges, as it requires efficiently sampling a certain number of edges from batch of graphs with varying sizes. Moreover, the sampling must only occur from non-occupied positions, and we must only rely on the edge list rather than the adjacency matrix to avoid high space complexity. As illustrated in Figure we propose an algorithm to efficiently handle this sparse sampling. The method begins by conceptually flattening all vacant positions. Simple random sampling is then performed these positions using randint to select 2 elements from 4. Crucially, after sampling, the indices have to be adjusted by adding offsets to account for existing edges through a specially designed algorithm, before remapping them back to index pairs. Finally, as the noisy distribution for non-existing edges is uniform, i.e., (0, b), Step 3 samples directly from a fixed distribution, avoiding redundant matrix multiplications required in prior models.
3.2 Efficient Denoising Neural Network
The traditional model for graph diffusion typically outputs the probabilities for all edges and nodes, which aligns closely with attention layers. These layers explicitly encode edge features with computational complexity of O(n?de), where I is the number of layers and de represents the edge feature dimension. contrast, message-pasee paasagggg methods only account for existing edges, significantly reducing the complexity O(Imde), where m is the number of existing edges.
However, discussed in Appendix D.5.1 relying solely cessage-passingg and link prediction using node features tends to perform worse on both small and large datasets. This may be due to the inability to capture long-term and complex interactions between distant nodes, resulting in degraded performance in practice. To address this, we propose bridging the gap between a fully connected atlention layer and message-passing with a random attention mechanism. Specifically, we first integrate a convolutional transformer layer (Shi ct al. (2200) that restricts attention to existing edges. Additionally, we incorporate random attention by sampling query edges randomly from all possible node pairs. By expectation, the model learns the full attention map between nodes, enabling it to capture more complex interactions.

---

Published in Transactions on Machine Learning Research (07 (225))
noisy edge list E'
query edge list Eg
message-passing edge list E
Figure 3: The sparse attention map used in the sparse denoising network is based on the gressage-passinge edge list Em This edge list consists of noisy edges for graph attention E (shown in blue) and uniformly sampled query edges for random attention Eg (shown in red).
3.2.1 Edge Prediction Module using Sparse Attention
As previously discussed, relying solely on message- passsnng layers for edge prediction yields limited results. To enhance performance, we propose random attention mechanism through a randomly selected subset of node pairs, referred to as query edges. As shown in Figure 3 the input to the denoising network, referred to as message-passing edges, is denoted by their indices and categories (Em; Ym). This includes two edge sets: (1) noisy edges (E", Y"), representing existing edges in the noisy graph G³, and (2) query edges (Eg Yg), which are randomly selected for attention and loss computation. Formally, the model takes the following edges as input:
Em = E
= Y
(2)
Noisy edges indexed by E' preserve the topological information of the noisy graph, while query edges indexed by Eg are uniformly sampled from all node pairs, covering both existing and non-existing edges. This sampling strategy enables the model to predict arbitrary edge lypes while ensuring unbiased loss estimator relative to dense diffusion models.
Additionally, the query edges in Eg facilitate random attention and serve implicit shortcuts in the message- passing network, enabling graph rewiring. As noted in studies such as (Alon & Yahav, 2020; Topping el al. 2021 Di Giovanni et al. 2023), this mechanism enhances information propagation and helps mitigate over- squashing issucs by introducing additional rewiring edges denoted by E, Eg E..
To control the number of query edges, we define the sparsity parameter X as X Byl. Given that query edges may overlap with noisy edges and that the number of noisy edges my approximates the number of edges m in the clean graph (according to Lemma 3.1 the total number of message- meessage-pssing edges satisfies पे ensures that the computational complexity of SparseDiff
|mml= < E + E, I m + [An?1. Setting A = m remains approximately O(EE,,) = (m), aligning with the number of edges in the clean graph G. In our experiments, is selected to balance computational efficiency and effective batch size, as detailed in Appendix
C.2 This flexibility enables robust performance across different settings, demonstrated in Table 5
3.2.2 Model Training
Our sparse denoising network adopts a graph transformer architecture featuring normalization, food-forward, and attention layers (Veličković et al. (017). incorporates a sparse attention mechanism for handling sparse data (Shi et al. 2020), and integrates advanced features such PNA pooling layers (Corso al. 2020 and FiLM layers (Perez et al. 2018), which are designed to enhance predictive accuracy and effectively manage computational complexity. A detailed discussion of the model architecture is provided in Appendix B
Training of the network Φo parameterized by 0 involves predicting query edges Eg, and the loss minimized using the crossyyntropy (CE) loss between the predicted distribution GG = (Px, Px) and the clean graph G. As detailed in Alg. I the loss function is computed as follows:
Σ CE(X, P. 1Si5n
Σ (KJ)E,,
CF(Y,), PT),

---

P Set query edges Construct messago- paasggg-ppainnggggg edges and its attributes Y,, Construct the message-passing graph D Predict the distribution of nodes and query edges Sample labels Published in Transactions on Machine Learning Research (07 (07/2025)
Algorithm Sparse training step with the sparsity parameter (Section 3.1 & 3.2
1: Given the clean graph -= (E, x r Sample the noisy graph G (E', X Y"); Sample query edges Bg of size [An2]
Em + E. U Eg Y f- + UY,;
Construct peessage-passingg edges Construct the message-passing graph > Predict the distribution of nodes and query edges
Gm - Em, X Ym);
6: (px, (Px,P) @ Ey):
7: optimizer. step (E px) + CE(P, P());
> Loss calculation
Algorithm 2 Tterative inference at step with the sparsity parameter (Section 3.3
1: Initialize an empty graph G with unlabeled nodes X and no edges;
2: Randomly divide all node pairs into = [ equal-sized chunks [Co."". Ck-1k;
3: for in range(K) K)) do
Eg Csi
Em E Egi
6: Gm f (Em: X mm);
7: (PX, pK)= = dh (m, Eg);
X Multinomial( pxx Y, Multinomial(PP.)
9:
X + 8:
Assign node new labels > Add existing edges
10: y
8, Ng = 0 + E E, Y = =0]
Here, the constant weights nodes and edges in the loss calculation. It is rescaled by dividing by À to maintain consistent edge-to-node weight ratio across different À values. Conceptually, training SpfrseDiff is analogous to using stochastic gradient descent instead of standard gradient descent. Query edges act as random mini-batches, so SparseDiff's updates remain aligned with those of dense diffusion models.
3.3 Iterative Inference
SparseDiff also remains memory-effiiintt during the inference stage, as visualized in Part (3) of Figure 1 We start by sampling the number of nodes n of the generated graph from the node distribution of the training set, which remains constant during the reverse process. Next, we sample a random graph from the prior distribution GT I[ Cate(px) x IIgiessn Cate(py), where px and py represent the marginal probabilities of node and edge classes, respectively. The categorical distribution Cate(p) is used for both nodes and edges. The sparse denoising network Φe is then recursively applicd to predict the clean graph from the noisy one. The demoising processes of SparseDiff are further visualized in Figure 7
Directly predicting the entire graph at each diffusion step t is impractical due to quadratic memory re- quirements. Morcover, using dense graphs during inference could lead to a distribution shift compared the training stage, due to changes in the number of edges used for message-passing To mitigate this, we implement iterative procedure progressively cover all node pairs in Gt-1, 1 As detailed in Algorithm 2 and in Part (3) of Figure [ we divide all node pairs randomly into K x cqually-sized sets, representing the query edges for each prediction S During each iteration k, the noisy graph G remains identical, and a message-passing edge list Em is constructed using noisy edges and query edges from the 1tth set denoted by E.. SparseDiff then predicts the distributions for these query edges, samples labels, and integrates edges classified as existing into Gt-1.
When x(n-1) is not divisible by K, we adjust by slightly overlapping the last with the previous one.
2
8

---

Published in Transactions on Machine Learning Research (07/2025)
(a)
(b)
(c)
(d)
Figure Samples from SifrseDiff trained on large graphs (a) Ego training set (50 to 399 nodes); (b) Generated Ego graphs; (c) Protein training set (100 500 nodes); (d) Generated Protein graphs.
This iterative approach allows SparseDiff maintain favorable memory complexity, albeit at the cost of increased sampling time due to iterations at each diffusion step. However, unlike many scalable models, SparseDiff does not impose additional assumptions about data distribution, such as clustering distribution. Despite the increased sampling time, the generation time for SparseDiff remains efficient due to its ability to utilize larger batch sizes and to accelerate model computations using sparse inputs, as reported in Table 15 of Appendix D.4
degree
Finally, drawing inspiration from D3PM (Austin et al. 2021 and DDIM (Song et al., 2020), we propose a method to accelerate inference by reducing the inference steps by a factor In particular, at each step t, the model predicts (G"""I G) x (Qt) o GQ instead of "(""=1I'', G)) (QY) o GQ The results for acceleration are reported in Table 7
4 Experiments
We evaluate SparsoDiff on diverse graph datasets against a broad range of basclines, including GraphRNN (You al. 2018), GRAN (Liao et al.] 2019), GraphNVP (Madhawa al, 2019). SPEC-
TRE
Martinkus al. 2022 GDSS (Jo et al. 2022), DiGress (Vignac et al. 2023a), DruM (Jo et al.
2023
and scalable models such BiGG (Dai et al. 2020), GraphARM (Kong al. 2023 EDGE (Chen
ct al.
2023), HiGen (Karam 2023), and HGGT (Jang et al. 2023 We refer to the method from Bergmeister
eet al.
2023 as GraphLE We report results as originally published to ensure fair and consistent comparison.
DiGress (Vignac et al. 2023a), as the primary baseline, is reproduced using SparseDiff's settings due to missing checkpoints. Training and architectural hyperparameters are detailed App. D.6
SparseDiff metrics are reported mean + standard deviation, derived from five samples, mitigating variance of inference. We bold the best-performing method for each metric. The results underscore SparseDiff's significant competitive advantage on datasets containing larger graphs, such Planar and SBM (Martinkus let al. p022b. Protein (Dobson & Doig 2003), Ego and CORA (Sen et al. 2008). and Facebook (Mcauley & Leskovec 2014) alongside its state-of-the-art performance on datasets with small molecules, including QM9 (Wu et al.J 2018)) and MOSES (Polykovskiy et al. 2020). Notably, SparseDiff the only model that demonstrraes competitive performance across both large and small graphs, handling both attributed and unattributed graphs effectively.
4.1 Large Graph Generation
Dataset We evaluate SparseDiff on diverse graph datascts to demonstrate its scalability and versatility, First, we (est its ability to generale edge-crossing-fre. planar graphs with 64 nodes. Next, we assess its capacity to generate graphs with 2 to communities using Stochastic Block Model (SBM) graphs, scaling up 200 nodes the largest size seen in models like DiGress. We also evaluate Ego and Protein datasets, with graphs up to 500 nodes, representing citation relationships and amino acid interactions within 6 Angstroms. The largest edge ratio for these datasets is 8.8% confirming their sparsity. Detailed dataset. statistics are in

---

Published in Transactions on Machine Learning Research (07/2025)
Table 1: Sample quality on large graphs. The mean ratios to the reference of the Degree, Cluster, Orbit, and Spectre MMD metrics are reported to enable comprehensive comparison.
Class
Model
Degrce(10 44
Cluster (10-F) -10 Orbit (10-3))
Spectre (10-3)
Ratio 4
RBF (10-2)4
Protein
Reference
0.3
0.7
0.3
0.5
1.0
1.4
Dense
GRAN
5.1
17
DiGress
5.910.1
10:1..
5.1-1.8
2.9.0.5
1442.3
7.1115
Sparse
DruM
1.9
6.6
3.5
3.0
8.4
BiGG
2.6
HiGen
1.2
4.4
2.3
2.5
5.7
GraphL.E
3.0
3.1
0.5
1.3
4.7
SparseDiff
1.5+0.3
3.4+0.3
0.5
1.4+0.2
3.6+1.1
3.8+0.7
Ego
Reference
0.2
0.7
0.7
10
1.0
0.9
Dense
DiGress
8.9
5.4+0.4
3.0+0.3
1943.2
1943.1
3.4+:0.8
Sparse
EDGE
58
18
5.2
107
6.6
HiGen
47
0.3
3.9
81
4.5
SpfrseDiff 3.7=0.4
3.2+:..1
2.0+0.4
5.6
7.9+:0.9
2.6+
Table 2: Sample quality on synthetic graphs. The mcan ratios to the reference of the Degree, Cluster and Orbit MMD metrics are reported to enable a comprehensive comparison.
Dataset
Stochastic block model
Planar Orbit
Model
Degreel
Cluster
Orbit
Ratio
V.U.N.f
Degree
Cluster
Ratio +
V.U.N.1
Reference
0.9
3.3
2.6
1.0
100%
0.2
3.1
0.1
1.0
100%
GRAN
5.8
7.9
3.6
25%
0.7
4.3
0.1
0%
GG-GAN
5.9
2.8
25%
123
528
0%
SPECTRE
1.6
53%
0.5
7.9
0.1
2.0
25%
DruM
0.7
4.9
4.5
3.6
85%
0.5
3.5
0.1
1.5
90%
HiGen
5.5
5.8
7.9
3.6
GraphLE
12
5,2
6.7
5.8
45%
0.5
6.3
0.2
2.2
95%
DiGress
1.7+00.1
5.0+t0.1
3.6=0.4
1.6=0.1
74%++4
0.8+-0.0
4.1+0033
0.5=0.0
1.2=0.4
76%=1
SparseDiff'
1.6.1.99
5.0.10.1
4.5.1..9
1.7.1..5
75%.110
0.3.10.0
3.210.3
0.110.1
1.2.0.4
85%_19
Appendix C.2
To further highlight our model's scalability, we include the Facebook dataset, which contains
1,045 nodes, in Table II and the CORA dataset, which contains 2,485 nodes, in Table 12 respectively.
Metrics For evaluation, we use maximum mean discrepancy (MMD) metrics, standard in graph generation lasks. We report the validity of SBM graphs as the fraction passing a stochastic block model test, and for Planar graphs, the fraction that are planar and connected. For larger datasets, we also use the Radial Basis Function (RBF) MMD metric assess fidelity and diversity using a randomly parametrized GNN (Thompson al. 2022 Since MMD metrics often yield small values that are difficult compare directly, report Degree, Cluster, Orbit, Spectre and RBF MMD metrics in units of 10 10-2 10-2, 10 and 2 respectively. The theoretical optimal metrics, computed with MMD(train, test)?, are used the reference and represented by a light gray line. Detailed results with higher precision are available in Appendix C.3 for facilitating comparison. For the Facebook and the CORA dataset, the evaluation follows the setup of SaGess Limmios et al. 2023 and EDGE (Chen et al. 2023 for better comparison.
Results Tables 1 and show that SparsoDiff tops the aggregated averago-ratio motrics, trailing DiGress by just 0.1 on SBM. SpfrseDiff matches DiGress's best score within variance, suggesting can hit that mark with optimal seed. Dense models such DiGress (Vignac al., 2023a) excel on SBM and Planar graphs but falter on larger Ego and Protein datasets because of quadratic memory, failing outright for graphs over 1,000 nodes. SpfrseDiff, by tuning the sparsity parameter X, allows larger batches under the same resources, converges faster, and handles graphs well past. this threshold. On mid-sized SBM and Planar graphs it matches dense and sparse baselines (Table 2 it stays competitive on large Ego and Protein graphs (Table and lcads on the 1,000- and 2,000-node benchmarks (Tables 11
12
10

---

Published in Transactions on Machine Learning Research (07/2025)
Table 3: Molecule generation on QM9 with implicit hydrogens.
Dense Models
Sparse Models
Model
Valid (%iJ
Unique (%))
Conn. (%)
FCD )
Model
Valid (%)
Uuique (%)
Conn. (%) FCD L
SPECTRE
87.3
$5.7
GraphARM
90.3
1.22
GraphNVP
83.1
99.2
EDGE
99.1
100
0.46
GDSS
95.7
98.5
2.9
HGGT
99.2
95.7
0.40
DiGress
99.3
0..9=0.2
99.4:0.2
0.15:1001
SparseDifl
99.2-0.1
96.410.1
99.8:0.1
0.12:10.00
Table 4: Drug-sized molecular generation on the MOSES dataset.
Model
Valid (%) t
Unique (%)
Novel (%)
Filters (%) f
FCD
SNN (%)
Seaf (%)
Frag (%) f
GraphINVENT
96.4
99.8
95.0
1.22
53.9
12.7
98.6
DiGress
85.7
100.0
95.0
97.1
1.19
52.2
14.8
99.6
SparsoDiff'
84.7.0.2
100.0_0.00
95.1
97.0.10.2
1.28.1.01
52.2.1.00
15.5
99.810.0
4.2 Molecule Generation
Dataset and metrics Given that our method behaves like dense models in the limit case where X 1, it is expected to align with their performance on small graph datasets. We evaluate our approach using the QM9 and MOSES molecular datasets, anticipating its performance comparable to that of dense models. The QM9 dataset (Wu et al. 2018) features molecules with up to 9 heavy atoms, while the MOSES benchmark PPolkovskiy et al.) 2020), derived from ZINC Clean Leads, includes drug-sized molecules with extensive assessment tools. In QM9, we add formal charges as discrete node features during diffusion, similar Vignac et al. (2023b), and apply the same to DiGress for consistency. We assess molecular performance the proportion of connected graphs, validity of the largest connected component verified by RDKit, and uniqueness of over 10,000 molecules. Additionally, use the Frechet ChemNet Distance (FCD) (Preuer
et al. 2018 to measure molecular similarity, excluding 0.96% of invalid molecules for FCD analysis.
Results Table 3 demonstrates that SparseDiff consistently outperforms other scalable methods on the FCD metric, highlighting its effectiveness for small, structured graphs even without siguificant sparsity advantages. Additionally, SparseDiff achieves results comparable to the state-of-the-art dense model, DiGress, across other metrics on the QM9 dataset. Furthermore, Table shows that on the drug-sized molecular dataset MOSES, SpfrseDiff maintains similar performance to DiGress, further validating its effectiveness.
4.3 Efficiency Analysis
Figure 5: Occupied GPU under differ- ent sparsity parameter X.
Unconditional generation on QM9 under different sparsily parameters X.
Table 5:
25000
A Valid
Uniquet
Connected
FCD4
GRU Usage (MB)
20000
DiGress Baseline (--)
100%
99.2110.1
96.410..1
99.8110.1
0.12:10.00
15000
QM9
50%
99.11:0.1
96.8:0.2
99.611..1
0.11:0001
25%
99.2+0..1
96.5+00.2
99.6+0..1
0.12+0.01
5000
10%
99.14:0.1
96.9+0.2
99.6++0.0
0.11+:0.00
0.0
1.0
Sparsity Parameter
Impact of the sparsity parameter The sparsity parameter À plays a crucial role in SparseDiff, but its impact on performance is minimal. On the QM9 dataset, where À == 1.0 (dense diffusion) is computationally feasible, we vary À from 1.0 to 0.1 (high sparsity) and report results in Table 5 SparseDiff demonstrates consistent performance across this range, with connectivity, validity, uniqueness, and Frechet ChemNet Distance (FCD) metrics showing minimal variation. For instance, the validity metric remains between 99.1% and 99.2%, while uniqueness ranges from 96.4% to 96.9%. We note that models trained with X = 0.1 and X = 0.25 required twice many training epochs due to fewer edges being processed per epoch. Despite
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
this, all models exhibit consistent performance across different À values after convergence, which highlights the robustness and stability of SparseDiff in generating high-quality molecular graphs.
In Figure 5 we present the approximate linear relationship between the sparsity parameter À and the actual space complexity on the QM9 and SBM datasets, demonstrating effective control over space complexity through our proposed method. For example, on the SBM dataset, training with X = 0.25 reduces memory usage to only 31.8% of that required by DiGress. At == 1.0, where sparsity is maximal, our method further outperforms DiGress by avoiding the overhead associated with dense models, which enforce uniform size of (Rmary 7maz) for batched computations, where Raax represents the largest node count within the batch. Conversely, on the QM9 datasct, where graph sizes are more uniform, our method incurs a slightly higher space complexity at À = 1.0 due to the indexing operations inherent to wressag--psssnng mechanisms and the sparse graph representations.
Table 6: Convergence comparison graph diffusion models after 24 hours of training.
Figure 6: Convergence comparison between Di- Gress and SparseDiff.
Model
Deg.
Clust.I
Orbit
Ratio
RBF
0.06
SparseDiff DiGress
EDP-GNN
DiGress
4.0
22
36
3.4
9.9
59
5.6
RBF MMD
0.04
EDGE
46
18
4.5
87
3.6
GraphLE
58
23
4.2
110
SparseDiff
4.7
3.6
7.8
0.00
Training Time (h)
Training efficiency We compare SparseDiff's performance on the Ego dataset against. other difffusion models, including dense models like EDP-GNN and DiGress, and sparse models such EDGE and GraphLE. Table shows that after 24 hours of training on a V100-32G machine, SparseDiff outperforms all metrics except for minor increase in Orbit MMD compared to DiGress. The comparison of graph diffusion models' sampling speeds is further presented in Table 15 in Appendix D.4 Figure + shows that SparseDiff has a significantly faster convergence speed compared to DiGress, achieving satisfactory results within two days. Notably, a SparseDiff model trained for 12 hours demonstrates an RBF MMD comparable to a DiGress model trained for 48 hours.
Table 7: Inference acceleration results.
Inference efficiency We test the Ego and Planar datasets with different numbers of inference steps (1000, 500, and 200) after training with T = 000 steps. The results, presented in Table 7 sur- prisingly demonstrate that even with 5-fold in- crease in generation speed (down to 200 steps), our model keeps performing, and consistently outper- forms most other dense and scalable models, high- lighting its potential for more efficient generation.
Dataset
Steps
Deg.
Clust.,
Orbit
Ratio
RBFI
1000
3.6
3.1
1.5
8.2
2.0
Ego
500
2.3
2.9
2.0
6.2
2.1
200
3.7
3.1
1.6
8.4
2.3
Dataset
Steps
Deg.
Clust.
Orbit
Ratio
V.U.N
1000
0.3
3.2
0.1
1.2
85%
Planar
500
0.3
3.4
0.2
1.5
80%
200
0.5
3.7
0.4
2.6
69%
5 Conclusion
In this work, we introducod SparseDiff, a scalable discrete denoising diffusion model for graph generation. SparseDiff offers precise control over computational resources by predicting only subset of edges at each step. Experimental results highlight its superior and robust performance across graphs of varying sizes, making it applicable to tasks such as generating large molecules and community graphs. Additionally, the query edge design, sparse transformer architecture, and iterative sampling procedure of Sparse can be extended to other iterative graph generation models. Furthermore, the efficient sampling algorithm for non- existing edges is applicable for graph rewiring in other domains. While SparseDiff meets the demands of most scenarios, its scalability and ability generate graphs with out-of-distribution node counts could be further enhanced by incorporating a structured hierarchical approach, which is expected for future work.
12

---

Published in Transactions on Machine Learning Research (07 (025)
References
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arxiv preprint arx:::0006. 05205, 2020.
Rohan Asthana, Joschua Conrad, Youssef Dawoud, Maurits Ortmanns, and Vasileios Belagiannis. Multi- conditioned graph diffusion for neural architecture search. Transactions on Machine Leorning Research, 2024. ISSN 2835-8856. URL https::/openreviier http:///ww......ooomoo/////o//a/
Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured de- noising diffusion models in discrete state-spaces. In Advonces in Neural Information Processing Systems, volume 34, 2021.
Minkyung Back, Frank DiMaio, Ivan Anishchenko, Justas Dauparas, Sergey Ovchinnikov, Gyu Rie Lee, Jue Wang, Qian Cong, Lisa N Kinch, R. Dustin Schaeffer, et al. Accurate prediction protein structures and interactions using a track-track neural network. Science, 373(6557):871 876, 2021.
Albert-LászIó Barabési. Network science. Philosophical Transactions of the Royal Sociely A: Mathemalical, Physical and Engineering Sciences, 371(1987), 2013.
Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Efficient and seal- able graph generation through iterative local expansion. arXio preprint arXiv:2312.11529 2023.
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint 2xXiv:2305.44111 2023.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in newral information processing systems, volume 33, 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 2020.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modcling for sparse graphs. In International Conference Machine Learning. PMLR, 2020.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. In TCML Workshop on Theoretical Foundations and Applications of Deep Generative Models, 2018.
Agnés Desolneux, Lionel Moisan, and Jean-Michel Morel. Estimating the binomial tail. From Gestalt Theory Image Analysis: A Probabilistic Approuch, pp. 47 63, 2008
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. In Advances in Newral Information Processing Systems, 2021.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M. Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In Proceedings of the 40th International Conference on Machine Learning. 2023.
Paul D. Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without align- ments. Journal of molecular biology, 2003.
Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 1960.
lakovos Evdaimon, Giannis Nikolentzos, Michail Chatzianastasis, Hadi Abdine, and Michalis Vazirgian- nis. Neural graph generator: Feature-conditionned graph generation using latent diffusion models. arXiv preprint Xii::2403301533 2024.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint ar Xiv:::190s 02428, 2019.
13

---

Published in Transactions on Machine Learning Research (07/2025)
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. ar preprint arXi::2200.01 01..044, 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2020.
Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, et al. Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv:2210. 00.00003, 2022.
John Ingraham, Max Baranov, Zak Costello, Vincent Frappier, Ahmed Ismail, Shan Tie, Wujie Wang, Vincent Xue, Fritz Obermeyer, Andrew Beam, et al. Illuminating protein space with programmable generative model. bioRriv, 2022.
Yunhui Jang, Dongwoo Kim, and Sungsoo Ahn. Hierarchical graph generation with k2-trees. arXic preprint arXiv:2305.1912 2023.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molccular graph generation. In International conference on machine learning. PMLR, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning. PMLR, 2020.
Jachycong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. Xixi preprinl arXiv:2202.095: 02514, 2022.
Jaehyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with destination- diffusion mixture. Xixio preprint arXi::230..0356 2023.
Mahdi Karami. Higen: Hicrarchical graph generative networks. arXiv preprint arXiu:2305.19337 2023.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. Autoregres- sive diffusion model for graph generation, 2023. URL http:///pppppoooeeeeeeeeooo/oooo
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint XXi:2209.00760 2020.
Xujia Li, Yuan Li, Xueying Mo, Hebing Xiao, Yanyan Shen, and Lei Chen. Diga: Guided diffusion model for graph recovery in anti-moncy laundering. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In NewrIPS, 2019.
Stratis Limnios, Praveen Selvaraj, Mihai Cucuringu, Carsten Maple, Gesine Reinert, and Andrew El- liott. Sagess: Sampling graph denoising diffusion model for scalable graph generation. arXiv preprint arXiv:2306.1688 2023.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, 31, 2018.
Manuel Madeira, Dorina Thanou, and Pascal Frossard. Tertiary lymphoid structures generation through basph diffuusion. In International Conference on Medical Image Computing and Computer- Assisted Intervention, pp. 37-53. Springer, 2023.
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnyp: An invertible flow model for generating molecular graphs. arXio preprint arxi:: 1600, 2019.
14

---

Published in Transactions on Machine Learning Research (07/2025)
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. ar preprinl arXiv:220,006613, 2022.
Krzysztof Maziarz, Henry Richard Jackson-Flux, Pashmina Cameron, Finton Sirockin, Nadine Schncider, Nikolaus Stiefl, Marwin Segler, and Mare Brockschmidt. Learning to extend molecular scaffolds with structural motifs. In International Conference on Learning Representations (ICLR), 2022.
Julian Mcauley and Jure Leskovec. Discovering social cireles ego networks. ACM Transactions on Knowl- edge Discovery from Data (TKDD), 8(1):1 28, 2014.
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
Rocío Mercado, Tobias Rastemo, Edvard Lindclöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology, 2021.
Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling, In International Conference on Artificial Intelligence and Slatistics. PMLR, 2020.
Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville. Film: Visual reasoning with a general conditioning layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-Tangeling, Sergey Golovanov, Oklai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, et al. Molec- ular sets (moses): a benchmarking platform for molecular generation models. In Frontiers in pharmacology, Frontiers Media SA, 2020.
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Gunter Klambauer. Fréchet chemnet distance: a metric for generative models for molecules in drug discovery. Journal of chemical information and modeling, (896)1773-1171, 2018.
Can Rong, Jingtao Ding, Zhicheng Liu, and Yong Li. City-wide origin-destination matrix generation via graph denoising diffusion. arXiv preprint arXiv:2306. 04873, 2023.
Christoph Schweimer, Christine Gfrerer, Florian Lugstein, David Pape, Jan A. Velimsky, Robert Elsässer, and Bernhard C. Geiger. Generating simple directed social network graphs for information spreading. In Proceedings of the ACM Web Conference 2022, ACM, 2022. URL BtLhhtp::// /tcttp:/dx..oo dww.//xxxxxiiioooo/ooo////oooo 1115/344114/ 3512194
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Col- lective classification in network data. In The Al Magazine, 2008.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for scmi-supervised classification. arXiv preprint arXiv:2009. (5:::000000300,, 2020.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International conference on artificial newral networks. Springer, 2018.
Jiaming Song, Chenlin Meng, and Stefano Ermon. arXiv:2010.02250 025000 2020.
Denoising diffusion implicit models. arXin preprint
Rylce Thompson, Boris Knyazev, Elahe Ghalebi, Jungtack Kim, and Graham W Taylor. On evaluation metrics for graph generative models. arXiv preprint arXi:2200.009811, 2022.
15

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. ar preprinl arXiv:2111.14522, 2021.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXi::1710.1000 2017.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Represenlations, 2023a.
Clément Vignac, Nagham Osman, Laura Toni, and Pascal Frossard. Midi: Mixed graph and 3d denoising diffusion for molecule generation. In ECML/PKDD, 2023b.
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. In Chem. Sci. The Royal Society of Chemistry, 2018.
Ling Yang, Zhilin Huang, Zhilong Zhang, Zhongyi Liu, Shenda Hong, Wentao Zhang, Wenming Yang, Bin Cui, and Luxia Zhang, Graphusion: Latent diffusson for graph generation. IEEE Transactions Knowledge and Data Engineering, 2024.
Shuai Yang, Xipeng Shen, and Seung- Hwan Lim. Revisit the scalability of deep auto-regressive models for graph generation. In 2021 International Joint Conference Newral Networks (IJCNN), 2021.
Jason Yim, Brian L Trippe, Valentin De Bortoli, Emile Mathien, Arnaud Doucet, Regina Barzilay, and Tommi Jaakkola. Se (3) diffusion model with application to protein backbone generation. arXiv preprint arXiv:2302.0m 02277, 2023.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep rugo-regressive models. In International conference on machine learning. PMLR, 2018.
16

---

Published in Transactions on Machine Learning Research (07 (025)
A Theoretical Analysis
The notations used throughout the paper are summarized in Tab.
Notation
Explanation
G (E,X,Y)
Graph as (edge list, node attributes, edge attributes)
n
Number of nodes
m
Number of edges
E N2x
Edge list (pairs node indices)
Ene N2x
List of non-existing node-pait One-hot node attribute matrix
X (0.1) nxa
Ye [0.1]mxx mxh b
One-hot existing-edge attribute matrix # classes for nodes (a) and edges (b)
G
Noisy graph at diffusion step &
(G'")""1)
Markov transition probability from G to G Transition matrices for node/edge classes at a' = 8 noise scheduling scalars I a², cumulative noise schedule Cumulative transition matrices
Qxx Q'
a'
Q'x: Q
Px. PE
Marginal class probabilitics (nodes/odges)
my (2) my
# non-existing edges in G
Q (0,
Probability for non-edge becoming an actual edge at step t Query edge set Sparsity param. (|Egl/n²)
Ey
A
C
k-th chunk of node-pair queries
Em = E. U Eg
Messagc-passing edge list for denoising Sparse denoising network & with parameters 0 Predicted node and query-edge distributions
d9
DG (Px, ;N)
X, Y,
Sampled labels via Multinomial(PX), Multinomial(P,)
Table 8: Main notations used SparseDiff.
A.1 Space Complexity Analysis
In this section, we provide a comprehensive breakdown of the space complexity of SparseDiff for each com- ponent, supporting our claim that SparseDiff achieves higher efficiency.
We consider batch of graphs where each graph contains n; nodes and m. edges. Let bs denote the batch size. To analyze worst-case complexity, define:
7max
max Maxx
max mi.
(4)
O5tchs
0stibs
A.1.1 Efficient Noise Model
Our method explicitly exploits redundancy in the previous computation of YQ B2 Specifically, for edges sharing the same type (e.g., non-existing), the resulting noisy probabilities are identical. We leverage this property eliminate repeated computations and substantially improve efficiency.
Existing edges For existing edges, computing the noisy distribution involves matrix multiplication with cost of O22mb + 12), Multinomial sampling from this distribution requires further (mb)). Therefore, the total complexity is O(3mb + B2).
Non-existing edges For non-existing edges, the sparse computation consists of three main steps. Based the Py implementation, the space complexity of each step is follows:
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
1. Sampling edge count: O(1).
Sampling positions: O(2n² + m).
Sampling edge attributes: (bm,), where the number edge types.
The breakdown of space complexity for sampling positions is:
Steps and 2: A multinomial distribution is used to sample m, positions from the O(n² - m)) non-existing edge candidates in Ene. This results in space complexity O(n² - m, + m²). Assuming my 2 m and my s m, this simplifies to O(n²).
Step 3: Offsets are appended to the candidate edge list using a single pass over the sampled edges. This step has space complexity O(n² - m2). The space complexity to take into account existing edges is (m.)) This results in space complexity O(n²).
Step 4: Final operation to convert these positions back to index pairs selection involves element-wise operations over mh ~ m elements. These operations have (()) memory overhead.
In total, the space complexity for handling non-existing edges is O(2n² + bm + + 1). Steps and 2 are detached from the backward computation graph and involve trivial operations that are typically well- supported by cxisting frameworks.
Summary By aggregating all edges and adopting the same computation for existing edges as SparseDiff, DiGress has a total space complexity of (3n2b++b)) In contrast, SparseDiff requires O 4mb+ Given that is lypically large and that is negligeble compared to n², we compare the highest-order terms. Specifically, DiGress has leading complexity O(3"b), while SparseDiff has O(2n²).
Assuming m is negligible relative to n and taking b = 2 as a concrete example, the leading space complexity of DiGress becomes ((nnb) = ( In contrast, our optimized implementation eliminates redundant computations across edge types and achieves a total space complexity of O(2")). This results in a 3x roduction in memory usage. As increases when we consider more edge types other than edge existance, the gap widens further, making our approach increasingly advantageous in such settings.
A.1.2 Efficient Denoising Neural Network
As described Section 3.2 the space complexity the denoising neural network for each graph is determined by the number of edges used its message paeeeppsssngggg process:
Em.il S m. + [xR²]
where À is the tunable sparsity parameter controlling the number of sampled query edges. For a batch, the total number of edges being considered is dominated by bs| Em,,axl, where |Em,max| = Mmmax + [n
Em.il= = Σ m, + [m S bs(mmax + A 1) = bss Ems]Emm
(6)
Osicbs
Traditional full-attention mechanisms considers all node pairs which incurs as complexity linear to Obss n² ?: whereas SparseDiff scales only with a complexity upper-bounded by O (Mmax + ))?
In practice, for network with attention layers and edge activation dimension de, the total space complexity for batch of size bs is actually upper-bouned by:
O(bs L de Emm.)
(7)
Since de is typically large (c.g., 64 or 128) and L often exceeds five layers, this component becomes the primary memory bottleneck inside the network. Tn sparse graphs, the number of edges m, is typically much
18

---

Published in Transactions on Machine Learning Research (07 (025))
smaller than nf, making xx the dominant term in [mml As result, the space complexity grows ((xm in practice, leading to near-linear scaling of memory usage with X. This is further supported by the observation in Figure 5 that the memory usage scales approximately linearly with X, as this component dominates the GPU usage.
A.1.3 Iterative Inference
SparseDiff employs an iterative inference process that aligns with its training procedure, to maintain spansity in wessage-passing edges. This contrasts with previous models that rely on dense attention maps constructed from all node pairs. The complexity thus remains upper-bounded by Obss L de max)
A.1.4 Summary
We provide a sunmary of the highest-order complexity for the three components SparseDiff:
Efficient Noise Model: SparseDiff reduces noise application complexity to O(2n²) instead of O33m?), 2 2 by avoiding redundant computations and leveraging sparsity in non-existing edge processing.
Efficient Denoising Neural Network: SparseDifl's denoising work operates over sparse al- tention map, scaling as OAn²²), unlike dense baselines (e.g., DiGress), which process a full attention map with On complexity.
Iterative Inference:
Inference reuses sparsely sampled edges from training, keeping its space complexity similarly scaling with O(A²)).
Among them, the denoising network is the primary memory bottleneck during training. In contrast to dense baselines such as DiGress, which scale as O(n²) with large constant d, L with L the number of layers and de as the dimension of edge activations, typically set to 64 or 128, SparseDiff constrains memory usage by operating on sparse set of sampled edges scaling with O(An²). This is further supported by Fig.5 in the revised manuscript, which shows that GPU memory usage scales approximately linearly with X.
A.2 Proof of Lemma 3.1
The lemma for a noisy graph with guarantced sparsity comes directly from the proposition regarding the tail behavior of a binomial distribution (Desolneux el. al. 2008) as follows:
Proposition A.1. (Tail behavior of binomial distribution)
Let X,, i 1,..d be independent Bernoulli random variables with parameter < < and let S = El=1 Xt. Consider constant p <, r or real function p < r(1) 1. Then according the Hoeffding inequality, B(I,k,)) = P.S 2 k] satisfies:
logPis 2 rl] 2 rlog- r (1 p)log 1 1-r
(8)
1-p
For sparse graphs, the edge ratio r is clearly smaller than 1. Consider then Bernoulli random variables with the parameter and a noised edge ratio r < l 1 with / = nnn - 1)/2 (i.e. number of all node pairs in an undirected graph without self-loops) draws, and note the sampled 'existing' edge number Sn(n-1)/2 as mi.
we have:
m,
nnn 1)
h + (1 - r) log [k: log
1
log(Pir: n(n 1
2 k)) <
(9)
2
r
19

---

Published in Transactions on Machine Learning Research (07 (07/2025)
B Model Architecture
Our sparse denoising network adopts the graph transformer architecture Veličkovié et al. (017)) featuring normalization, feed-forward, and attention layers. To handle sparse data, it incorporates the sparse attention mechanism (Sh et al. 2020) based on weighted message- message-passing layers and integrates enhancements from Vignac et al. 2023a), such as PNA pooling layers (Corso et al. 2020) and FiLM layers (Perez et al. 2018
Precisely, we introduce the FiLM layer and the PNA layer inside the model architecture to enhance its performance. Precisely, the FiLM layer used to combine features at different scales, such as node and edge features. Specifically, given two features M1 and M2, and trainable parameters W1 and W2, the FiLM layer As illustration, within the convo-
output is calculated as F M22 M1 W1+(MM 3 lutional layer, the graph feature M2 is integrated with edge features M1 to enhance predictions. While PNA layer is used as specialized pooling layer to obtain information from different dimensions of a specific feature. Given the feature X and trainable parameter W, (NA(X)= cat(max (),, (i)) mean (X) ), std(()) W. For example, node features X are forwarded to a PNA layer for extracting global information across different scales, which is subsequently added to the graph feature to enhance its representation.
Finally, we enrich the wessage-passiing graph with additional encodings, such as the graph Laplacian and cycle counts, to enhance structural and positional information (detailed in Appendix B.Ijj.iixBB........ These encodings can only be computed effectively when the noisy graphs are sparse, which is another significant advantage of discrete diffusion models using marginal transitions. It is worth noting that not all these encodings can be computed in sub-quadratic time. However, in practice, this does not pose an issue as they are not used for propaaatto,,,,,,, which arises as the primary complexity bottleneck curing training. For instance, for the large Protein dataset, computing these encodings is five times faster than the forward pass itself. Nevertheless, on very large graphs, these expensive encodings should not be computed.
B.1 Additional Encodings
During training, we augment model expressiveness with additional encodings. To make things clear, we divide them into encodings for edges, nodes, and for graphs.
Encoding for graphs We first incorporate graph eigenvalues, known for their critical structural insights, and cycle counts, addressing message-passine passing neural networks" inability to detect cycles (Chen et al. 2020) The first requires n² operations for matrix decomposition, the socond requires n² for matrix multiplication, but both are optional in our model and do not significantly limit scalability even with graphs up to size 500. In addition to the previously mentioned structural encodings, we integrate the degree distribution to enhance the positional information within the graph input, which particularly advantageous for graphs with central nodes or multiple communities. Furthermore, for graphs featuring attributed nodes and edges, the inclusion of node type and edge type distributions also provides valuable benefits.
Encoding for nodes At the node level, we use graph eigenvectors, which are fundamental in graph theory, offering valuable insights into centrality, connectivity, and diverse graph properties.
Encoding for edges To aid in edge label prediction, we introduce auxiliary structural encodings related to edges. These include the shortest distance between nodes and the Adamic-Adar index. The former enhances node interactions, while the latter focuses on local neighborhood information. Due to computational constraints, we consider information within a 10-hop radius, categorizing it as local positional information.
Molecular information In molecular datasets, we augment node features by incorporating edge valency and atom weights. Additionally, formal charge information included as an additional node label for diffusion and denoising during training, as formal charges have been experimentally validated as valuable information (Vignac al. 2023b
20

---

Published in Transactions on Machine Learning Research (07/202) 2025)
1000
800
600
400
200
Figure 7: Visualization of iterative generation for Planar and SBM graphs.
C Experimental setup
In our experimental setup, we utilize a single V100-32G GPU machine, which is particularly prone to scalability issues, to demonstrate that our method allows users with limited GPU resources to effectively train on larger graphs. Detailed specifications regarding workers, memory allocation, execution time, and optimizers are meticulously indicated in the configuration details provided in our code.
As for dataset splits, adhere to the framework established by DiGress. Specifically, for the QM9 dataset, implement a split comprising 100k molecules for training, 20k for validation, and 13k for evaluating likelihood on the test set. For the Planar, SBM, and Protein datasets, employing a seed of 1234, we randomly assign 20% of the graphs to testing, while 80% the remaining graphs are utilized for training, and 20% for validation. For the Ego dataset, to ensure consistency with previous methods and a fair comparison, we maintain a split of 80% for training and 20% for testing, with 20% of the training set additionally used for validation purposes. All configuration details are comprehensively documented in the code provided.
C.1 MMD metrics
In research, carefully select specific metrics tailored to each dataset, with primary focus four widely recognized Maximum Mean Discrepancy (MMD) metrics. These metrics the total variation (TV) distance, as detailed in Martinkus et al. (2022). They encompass node degree (Deg), clustering coefficient (Clus), orbit count (Orb), and graph spectra (Spec). The first three local metrics compare the degree distributions, clustering coefficient. distributions, and the occurrence of all 4-node orbits within graphs between the generated and training samples. Additionally, the comparison graph spectra realized by computing the eigenvalues of the normalized graph Laplacian, providing complementary insights into the global properties of the graphs.
C.2 Statistics of the datasets
Table 9: Statistics for the datasets employed in our experiments.
Name
Graph number
Node range
Edge range
Edge Ratio (%)
X (%)
QM9
133,885
[2.9]
[2, 28
[20, 56
100
(M)(H) MOSES
133,885
[3, 29
[4, 56
[7.7, 44
50
1,936,962
[8, 27
[14, 62
[8.0, 22
50
Planar
200
[64, 64]
[346, 362
[8.4, 8.8
50
SBM
200
(44, 187]
[258, 2258
[6.0, 17
25
Ego
757
[50, 399
112, 2124
[1.2,
Protein
918
[100, 500]
[372, 3150
[8.9, 6.7
10
21

---

Published in Transactions on Machine Learning Research (07 (07/2025)
To provide comprchensive overview of the various scales found in 'existing" graph datasets, present here key statistics for them. These statistics encompass the number of graphs, the range of node numbers, the range of edge numbers, the edge ratio for 'existing' edges, and the sparsity parameter À used for training, icc the proportion of "existing" edges among node pairs. In our considcration, we focus on undirected graphs. Therefore, when counting edges belween nodes and j, we include the edge both directions.
C.3
Raw results
Table 10: Raw results the SBM, Planar, Protein, and Ego datasets.
Model
Deg. (o-3)4
Clust. (o-2)4
Orbit (e-2)
Spec. (e-3)}
FID4
RBF MMD (c-2)4
SBM
Training set
0.85
3.32
2.55
2.74
1.37
3.23
SparseDiff 1.57:10.91
5.04
4.51
6.68
4.55:12.01
4.98.10.06
Planar
Training set SparseDiff Protein
0.19
3.10
0.05
3.82
1.57
8.89
0.32
3.25
0.09:10.08
6.99
2.94
9.84
Training set SparseDiff 1.45:10.30
0.32
0.68
0.32
0.49
1.36
1.37
3.35
0.53
1.35:10.16
5.97
3.77
Ego Training set SparseDiff 3.70+0.44
0.16
0.71
0.69
0.98
0.07
0.86
3.18+:.10
1.98:+0.22
5.63+0.80
4.84+1.56
2.60#0.31
To comparison with other methods, Table 10 provides the raw numbers (not presented as ratios) for the SBM, Planar, Ego, and Protein datasets. Note that this table contains the FID metrics from Thompson et al. (2022), which we did not include in the main text. The reason is that we found this metric to be very brittle, with some evaluations giving a very large value that would dominate the mean results. Besides, we have identified a discrepancy in the Spectre metrics reported in the study by Martinkus et al. (2022) when computed under non-parallel computation. We thus provide the updated values for reference and use the updated value for ratio calculation in Table 2 and Table
Additional experiments
D.1 Training with larger graphs
However, using the same graph for both training and evaluation poscs potential risks, as high performance metrics could merely reflect overfitting to the training graph. Therefore, report results only the two relevant datasets in the appendix.
Table 11:
Large graph generation the Facebook dataset. Triangles and squares abbreviated 'tri' and 'squ' in the table, while PLE represents power law exp.
Model Num Nodes
Num Edges
Num Triangles
Num Squares
Max Deg
Clust
Assort
PLE
CPL
Ref
1045
27,755
446.846
34.098.662
1044
0.57579
-0.25443
1.28698
1.94911
SAGESS Uni
1043
27,758
429,428
35,261,545
999
0.52098
-0.01007
1.29003
2.00500
SAGESS RW
1009
27,764
490,844
43,006,252
1001
0.56138
0.02266
1.29398
1.96014
SAGESS Ego
1005
27,761
515,928
45,421,130
295
0.43074
0.34074
1 1.29381
2.65926
NetGAN
1045
27,755
262,574
15,635,626
849
0.39773
-0.01821
1 1.27429
2.13730
CELL
1045
27,755
250,968
14,855,676
474
0.30854
0.12788
1.27490
2.38650
DCSBM
1041
27,092
339,448
26,714,948
733
0.37549
0.07125
1.28845
2.33021
SaGess
1043
27,758
429,428
35,261,540 .545
999
0.52098
-0.01007
1.29003
2.00800
SparseDiff
1045
27,763
446,819
34.095,518
1044
0.43310
-0.02536
1.28687
1.94921
22

---

Published in Transactions on Machine Learning Research (07 (075))25)
We first train the large graph with 1045 nodes from the Facebook dataset, following the SaGess [immios et al. 2023) setting. SparseDiff was evaluated using SaGess metrics as reference. In the provided table, we present SaGess-RW demonstrating the best results among the three proposed SaGess models. Notably, SaGess generates small graphs and concatenates them to meet the required number of edges, while SparsoDiff generales a single large graph based on the specified node count. This explains SparseDiff's advantage the 'num nodes' metric and SaGess's advantage the 'num edges' metric. Furthermore, SparseDiff closely aligns with real data statistics, except for the clustering coefficient, showcasing not only its scalability up to 1000 nodes but also its strong performance such single-graph datasets.
Table 12: Large graph generation on the CORA dataset.
Model
FO
PLE
NTC
CC
CPL
AC
Ref
100
1.885
0.090
6.311
-0.071
OPB
10.9
1.852
0.097
0.008
4.476
-0.037
HDOP
0.9
1.849
0.113
0.009
4.770
-0.030
CELL
10.3
1.774
0.009
0.002
5.799
-0.018
CO
9.7
1.776
0.009
0.002
5.653
0.010
TSVD
6.7
1.858
0.349
0.082
4.908
-0.006
VGAE
1.5
1.717
0.120
0.220
4.934
0.002
GRNN
0.4
1.822
0.043
0.011
6.146
0.043
EDGE
1.1
1.755
0.446
0.034
4.995
-0.046
SparseDiff (pos)
0.3
1.896
1.434
0.075
4.747
-0.043
We evaluate our model the CORA dataset (McCallum et al. 2000), as used in EDGE (Chen et al, 2023). The CORA graph consists of 2,485 nodes. Our model is trained with positional encoding for fair comparison of the edge overlap ratio (EO), with the sparsity parameter set to 0.05. The performance results, after just one day of training, are presented in the table below. As shown, SparseDiff outperforms EDGE in out of metrics and remains competitive in the AC metric, further validating the scalability of our method.
D.2 QM9 with explicit hydrogens
Table 13:
Unconditional generation QM9 with explicit hydrogens. On small graphs such as QM9, sparse models are not beneficial, but SparseDiff still achieves very good performance.
Model
Connected Valid
Uniquet
Atom stablet
Mol stablet
DiGress
95.4
97.6
98.1
79.8
DiGress charges
98.6
97.7
96.9
99.8
97.0
SparseDiff(ours)
98.3+.08
97.9-t13
97.4+.10
We additionally report the results for QM9 with explicit hydrogens in Table 13 Having explicit hydrogens makes the problem more complex bocause the resulting graphs are larger. We observe that SparsoDiff achieves better validity than DiGress and has comparable results on other metrics when both are utilizing charges.
23

---

Published in Transactions on Machine Learning Research (07 (07/2025)
D.3 MOSES benchmark evaluation
Table 14: Mean and standard deviation across 5 samplings on the MOSES benchmark. SparseDiff has a similar performance to DiGress, despite shorter training time.
Model
Connected f
Valid (%) t
Unique (%) t
Novel (%) f
Filters (%) t
GraphINVENT
96.4
99.8
95.0
DiGress
85.7
100.0
95.0
97.1
SparseDiff
94.8.1.1
84.7:1.2
100.0
95.1
97.0
Model
FCD +
SNN (%) f
Scaf (%)
Frag (%) f
IntDiv (%) t
GraphINVENT
1.22
53.9
12.7
98.6
85.7
DiGress
1.19
52.2
14.8
99.6
85.3
SifrseDiff
1.28
52.2.:.0
15.511.3
99.8
85.41.0
Model
IntDiv2 (%) f
logP (c (c=²) 4
SA(c 3)
QED (c ()
Weight (%) +
GraphINVENT
85.1
0.67
4.5
0.25
16.1
DiGress
3.4
3.6
2.91
1.42
SifrseDiff
84.8
3.0
5.41.2
1.21
5.58
MOSES is an extensive molecular dataset with larger molecular graphs than QM9, offering much more com- prehensive of metrics. While autoregressive models such GraphINVENT are recognized for achieving higher validity on this dataset, both SparseDiff and DiGress exhibit advantages across most other metrics. Notably, SparseDiff closely aligns with the results achieved by DiGress, affirming the robustness of our method on complex datasets.
D.4 Sampling Speed Comparison
Table 15: Sampling speed for generating Ego graphs.
Model
EDP-GNN
DiGress
EDGE
GraphLE
SparseDiff
SparseDiff (200 steps)
Time (min)
5
32
2
20
28
5
The speed of generating 8 Ego graphs is demonstrated in Table 15 is coistrained to 2 due to its substantial memory requirements. An additional column labeled "SparseDiff (200 steps)" represents the sampling time after reducing the inference steps from 1,000 to 200 through acceleration stratogies. The table illustrates that SparsoDiff maintains comparable speed dense models without significant compromise space efficiency and be significantly accelerated during sampling.
Notably, for GraphLE, the batch size
D.5 Ablations
This part presents 2 ablation experiments that motivate approach. SparseDiff builds upon experimen- tal observation and hypothesis. Firstly, experiments demonstrate that relying solely node features for link prediction yiclds unsatisfactory results. This obscrvation encouraged us to design the mossago-passing graph to directly
graph that contains all edges to be predicted (i.e. query edges) as the message-passinnn obtain their edge features. Secondly, we hypothesized that preserving the same distribution of edge types as observed in dense graphs for loss calculation advantagcous for training. This hypothesis necessitates the sampling of query edges within each graph in batch of graphs with varying sizes, thereby introducing increased complexity to the algorithm design process.
24

---

Published in Transactions on Machine Learning Research (07 (075)
D.5.1 Link Prediction
Table 16: Influence of including edges features for edge prediction.
Model
Deg |
Clus |
Orby
Speck
FID
RBF MMD4
Link Pred
0.0043
0.0721
0.0275
0.0344
1.51e6
0.0315
SparseDiff
0.0019
0.0537=000
0.0299
0.0050#.00
16.1=12.9
0.0483
Table 17: Influence of including edges features for edge prediction the QM9 dataset.
Model
Valid
Uniquet
Connected
FCD4
Link Pred 98.12
96.25
99.58
0.310
SifrseDiff
99.23+0.06
96.37=1013
99.76+10.06
0.117:10.004
In Table 16 the model that does not explicitly incorporate edge features for edge prediction underperforms across all metrics, except for RBF MMD and orbit. Similarly, in Table 17 the link prodiction-based method fails to achieve comparable validity, even though QM9 is widely recognized as easy dataset to learn. Both experiments highlight a subtle yet challenging gap between wessage-passing and transformer-basel architectures for graph generation, as the latter provides richer topological interactions. While, in our case, this ablation proves detrimental, developing a more robust link prediction module could simplify the task to link prediction and significantly reduce space complexity.
D.5.2 Query edges with proper distribution
Table 18: Influence of edge loss distribution on EGO dataset.
Loss based on
Deg
Clus +
Orb
SpecI
FID4
RBF MMDJ
Comp graph
0.0021
0.0566
0.0270
0.0100
28.2
0.0396
Query graph
0.0019
0.0537+.00
0.0299
0.0050#.00
16.1
0.04834.01
In order to emphasize the importance of preserving the edge distribution when computing losses, we conduct model trained using all message-passingg edges as opposed
an experiment where we assess the performance solely using query edges. The former results in an increased emphasis on 'existing" edges during training compared to SparseDiff. Similarly, use the Ego dataset for initial experiments. Table shows that using edges of the message- passsegaannggggea graph Gm results in worse performance on most of the metries, which indicates the importance of keeping balanced edge distribution for loss calculation.
D.6 Hyperparameters
Training sctup The model is trained using a diffusion-basse framework consisting of 1,000 denoising steps. To balance the objectives associated with node and edge predictions, fixed loss coelficients of 5 and 2 are applied to edge and node terms, respectively. The learning rate is set to constant value of 0.0002 across all datasets. All experiments are conducted on a single V100 GPU with 32GB memory. The only introduced hyperparameter is the sparsity controller X, which is selected based on graph size according to Tab.
Model architecture For large graph datasets, the model comprises 8 sparse convolutional allention layers, following the same setup as the dense attention version proposed by Vignac et al. (2023a). It employs a multi- head attention mechanism with heads to jointly process 256-dimensional node features, 64-dimensional edge features, and 128-dimensional graph-level features. Hidden dimensions for the MLP layers before and after the transformer block are set to 256 for nodes, 64 for edges, and 128 for graphs. For molecular
25

---

Published in Transactions on Machine Learning Research (07/2025)
and synthetic datasets, adopt the same architectural configuration DiGress Vignac et al. 2023a to
maintain consistency across experimental settings.
Additional hyperparameters are further available in the shared codebase.
E
Comparison to Baseline Methods
E.1 Scalable Methods
EDGE EDGE (Chen et al., 2023) uses absorbing states construct sparse diffusion by first generating a node degree distribution d and then building the adjacency matrix A based on node degree changes during inference. While this factorization is broadly applicable, the conditional distribution po Po(Ald" degree sequences that are invalid for undirected graphs, creating a mismatch between training and sampling. EDGE also underperforms compared to SparseDiff on both small and large graphs. In contrast, SparseDiff only assumes the sparsity of graphs, ensuring alignment between training and generation.
yield
DruM DruM (Jo et al. 2023) predicts a destination graph and mixes several diffusion processes condi- tioned on that structure, introducing strong topological priors that guide denoising and improve convergence. However, DruM operates within a continuous diffusion framework. SparseDiff, by contrast, relies entirely on discrete diffusion, which better aligns with the inherently discrete nature of graph data.
Daa et al., 2020) generates graphs autoregressively by hierarchically decomposing the node- pair space into a binary tree, achieving O(n++ no sampling complexity. This structure enforces fixed generation order. SparseDiff avoids such inductive constraints, reconstructing edge subsets in single shot without any imposed ordering, resulting in a simpler and more flexible framework. Furthermore, BiGG is limited to unattributed graphs, whereas SparseDiff naturally supports diverse edge types and node features.
BiGG BiGG
HiGen HiGen (Krami 2023 adopts coarso-to-fine generation scheme, first producing community sub- graphs and then predicting inter-community edges. This hierarchical design assumes modular graph struc- ture. SparseDiff makes no such assumptions, treating all edges uniformly through sparse diffusion.
HGGT HGGT (Jang et al. 2023 encodes the adjacency matrix as a K token sequence and processes it with a Transformer using tree- based positional encodings. This strategy embeds structural priors using predefined hicrarchical data structure (the K2-tree) into the generation process. In contrast, SparsoDiff directly applies sparse diffusion over raw edge lists, avoiding dependence on any hierarchical encoding.
SaGess SaGess (Limnios al. 2023) is discrete denoising diffusion model for graph generation that scales to large networks through generalized divide-and-conquer strategy. It trains base diffusion model (DiGress) a collection of smaller subgraphs that collectively cover the original input graph. These sub- graphs are generated independently and subsequently assembled to form complete synthetic network. In contrast to SifrseDiff, which performs diffusion and precise denoising over the entire graph, SaGess achieves scalability by generating graph partitions independantly and merging them into a single graph.
GraphLE GraphLE [Bergmeister et al. 2023 grows the graph through local expansion, starting from a seed node and incrementally adding nodes and edges via multiple diffusion passes. While it avoids full pairwise modeling, this approach is practice esourco-intensing and requires denoising for cach expansion. SparseDiff instead performss the diffusion in a single process.
E.2 Discrete Graph Diffusion
While several models have emerged using discrete diffusion on graphs (Vignac et al. 2023a: Haefeli et al. 2022),
DiGress remains the most performant and is widely regarded as the benchmark.
Specifically, DiGress extends the discrete diffusion framework D3PM (Austin al. 2021] graph data by modeling both nodes and edges categorical variables encoded in one-hot format. In contrast rast. to SparseDiff,
26

---

Published in Transactions on Machine Learning Research (07 (07/2025)
which represents graphs using sparse triplets (E,X,Y) DiGress encodes graph G (X, E) with n nodes using a dense node feature tensor of shape (n x a) and an edge tensor of shape (n x b), where the edge tensor includes an additional category for absent edges.
To process batches of graphs with variable sizes, DiGress zero- zero-pada pads each graph to the dimensions (bs, Rmax: a) for nodes and (bs, Rmmax; Amax; b) for edges, where bs the batch size and 7max the maximum number of nodes among all graphs in the batch. This padding strategy introduces substantial memory overhead and fails to scale for variable-sized graphs, motivating our use of sparse representation to climinate this limitation.
Noise Model At each forward step t, DiGress applies categorical noise via transition matrices Q'x Q' where [Q' = P(x' = j x== = -). [Q = P(e' = e' = i), defining
GG' G² = ( Q' Ex QE), g('' |G) O' EQE).
with Q' -II'.m Q", as detailed in Section 3.1.1
DiGress defines the forward process using =I Q' and deviates from the uniform prior (Austin et al. 2021) by aligning the final state with the empirical marginal distribution of node and edge categories. This results in belter-initialized noisy graph, which leads to consistently improved performance.
In SparseDiff, we prove that the noisy graphs sampled along such trajectory have the same level of sparsity with the clean graph with high probability and also climinate redundant computations present in dense diffusion schemes.
Denoising Network The denoising network of DiGress permutation--qquiariaai full-attention graph transformer augmented with PNA (Corso el al. 2020) and FiLM (Perez et al. 2018) layers. Since attends over all n² pairs, captures long-range interactions but scales quadratically memory.
In SparseDiff, we propose messago-passing based denoising network which adapts better to sparse rep- resentation, governed by sparse attention map that incorporates all existing edges along with a controllable number of random connections. This enables training on large graphs with no degradation in generation quality.
Under an independence assumption across node and edge entries, DiGress optimizes the cross-entropy loss
C= Σ CE(E,,)) + A Σ CE(eg,P.)),
1==1
where xx n are the model's predicted category probabilities.
In SparseDiff, we perform the loss computation only on query edges randomly sampled from all node pairs, functionning random batches of the edges considered in DiGress. To ensure stability across different sparsily levels, we also reweight the edge loss based on the sparsity parameter X.
Inference DiGress frames graph generation as a discrete diffusion process over nodes and edges indepen- dently, following the D3PM formalism. At each step t, the model observes a noisy graph G, = (X',Y') and samples G.-1- For each scalar variable (i.e., a single node or edge) with one-hot state x², D3PM defines the exact postcrior conditioned on the unknown clean label I as:
q(x--1 |0( g(x" x²11) q(x--1 100)
q(x x0)
which, in matrix form, becomes:
q(a-11 (aat-110",0 100 Cat (at-1, p=
x' 2 2 ~ f Q
where Q' is the one-step transition matrix, Q'=IT' Q and "00 denotes element-wise multiplication.
27

---

Published in Transactions on Machine Learning Research (07 (025)
DiGress begins its generation by sampling the number of nodes from the training graph size distribution. Then, at each diffusion step I, it replaces the intractable posterior weights g(0g G+) and g( G+)) with predictions from denoising network, Po(x;, Gt) and po(el) G.). These then used to compute the reverse transition:
(((x-116. Σ 2(x ax (a",x") f0 Gt).
Nodes and edges are evaluated independently, and each categorical variable sampled accordingly. Iterating this process from = to produces the final generated graph.
In SiftseDiff, we modify this sampling process to align with the sparse attention mechanism used during training, ensuring both structural consistency and computational efficiency at inference time.
Summary In summary, DiGress explicitly addresses the discrete and permutatiion-equuivriaatt nature of graph data, outperforming existing one-shot generation methods in molecular graph synthesis. However, its reliance dense matrix representations limits scalability to graphs.
F Visualization
Training graphs.
Ofl
HN
(b) Generated graphs.
Figure 8: Visualization for QM9 dataset with implicit hydrogens.
28

---

Published in Transactions on Machine Learning Research (07 (07/2025)
(a) Training graphs.
(b) Generated graphs.
Figure 10: Visualization for MOSES dataset.
29

---

Published in Transactions on Machine Learning Research (07/200) /025)
(a) Training graphs.
(b) Generated graphs.
Figure 11: Visualization for Planar dataset.
30

---

Published in Transactions on Machine Learning Research (07/202) /025)
(a) Training graphs.
(b) Generated graphs.
Figure 12: Visualization for SBM dataset.
31

---

Published in Transactions on Machine Learning Research (07/202) 2025)
(a) Training graphs.
(b) Generated graphs.
Figure 13: Visualization for Ego dataset.
32

---

Published in Transactions on Machine Learning Research (07/202) /025)
(a) Training graphs.
(b) Generated graphs.
Figure 14: Visualization for Protein dataset.
33


Reviews:
[{"review_id": "3VCdUi1cz6", "reviewer": "Reviewer_x8GY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:** The idea of leveraging graph sparsity for diffusion-based generation seems interesting and practical. The paper also builds on existing work and is well-motivated.\n\n**Weaknesses:** I believe that the presentation of ideas needs to be improved. Especially:\n\n1. The technical contributions that are unique to this work are unclear. In particular, it is not straightforward to easily understand the contributions based on the current organization of content.\n\n2. The technical detail that requires further clarification and is contrary to the claims is the usage of $E_{ne}$ to sample edges in Section 3.1.2. Essentially, one can think of an adjacency matrix as a combination of $E$ + $E_{ne}$ which requires $O(n^2)$ space complexity. The authors state that they do not materialize such a matrix and rely on the sparsity of the graph (i.e, assume that the set of edges $E$ is small enough) for their computations. This is a bit confusing since I do not understand how \"Step 2: Sampling positions\" is possible without materializing $E_{ne}$.  This whole section was confusing to me.\n\n3. The authors have not presented any details about the hyper-parameters used for training. Also, the details about the number of layers, hidden dimensions, etc used for the GNN architecture are missing in Appendix B. Furthermore, the details about how the baseline numbers were measured is also missing.\n\nI am willing to reconsider my opinion about \"Claims and Evidence\" if the authors can address the above comments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a graph diffusion-based approach by leveraging the sparsity of large graphs and building on top of the DIGRESS framework [1]. \n\nNOTE: Overall, I feel that the reader should be extremely familiar with the diffusion on graphs literature to understand the implementation details and rigor of the paper. It would be great if the authors can address the feedback below and make their work more accessible.\n\n[1] Vignac, Clement, et al. \"Digress: Discrete denoising diffusion for graph generation.\" arXiv preprint arXiv:2209.14734 (2022).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. For each of the methods considered as a baseline in this work, can the authors briefly add some information about the technical details of the algorithms? In particular, where does SparseDiff differ from these previous works so that the readers can clearly understand the pain points that this paper addresses?\n\n2. It would be great to have a notations section in the paper to clearly explain what each symbol means in the paper. For example, I find it difficult to interpret Eq 3 even though it is a CE loss calculation. What computation steps are required to obtain $\\hat{P}^G_q$ ? I observed that step 6 in algorithm 1 can result in this value but what exactly in $\\phi_{\\theta}$ in step 6 ?\n\n3. Can the authors clarify how their sparse computation and the iterative inference process are related in terms of memory savings?\n\n4. Can the authors provide a breakdown of the memory savings from the three phases of the denoising process? Where exactly is the memory saving coming from?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fa7Rec8wJV", "reviewer": "Reviewer_vE9L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is generally well-written and well-structured. I found it understandable, and the figures are appropriate and clarify some key points, for example, Figures 2 and 3. I appreciated the thoroughness of the experimental evaluation.\n2. Some interesting key points are addressed in this work. One such example is the unfeasibility of applying dense models to larger graphs, but still having the need to model all node interactions, which is done in this work in a sparse way through random attention. Another instance is being able to tune the sparsification of the model, starting from a reference dense model. This work clearly takes inspiration from DiGress [1], for which SparseDiff can be seen as its sparse version. This reasoning could be extended to other dense models.\n3. Results show that sparsification does not hinder the expressivity of a dense model, but sometimes even elevates it. Additionally, better memory management helps in applying the model to much larger graphs.\n\nWeaknesses:\n1. Although the model seems novel as a whole, upon a deeper inspection, it is actually using the DiGress [1] diffusion and denoising processes. The change is in the representation used, which only materializes edges with a label and implicitly samples non-existing edges. Technically, the two models's diffusion processes should align perfectly, and the same is true for the denoising process, depending on the parameter $\\lambda$. Although this is not a weakness in itself, I would have appreciated this parallel being highlighted, and possibly having some guidelines for applying the same recipe to other dense models, if the authors find it possible.\n2. As explained in the previous point, intuitively, SparseDiff approximates DiGress, although with a different architecture. For this reason, I find it odd that SparseDiff can outperform the latter. One reason I can find is the change in architecture, and the fact that the inductive bias on sparsity is beneficial. I would like the authors to elaborate on this point.\n3. It seems there are a few bold statements regarding the line of hierarchical models. One such instance is \"While these approaches are designed specifically for large graphs, they rely on additional assumptions such as cluster structures or dependencies on node degrees which can hinder their generalizability.\"  Although it is true that these models exploit some properties of graphs, the motivation the authors provide is weak. Experimentally, I did not see this drop in generalization, and intuitively, these models softly follow these directions. For example, in EDGE [2] it is true that not all node degree sequences are feasible, but degrees are given as a conditioning feature to the model, not enforced through hard constraints.\n4. I would have appreciated a quantitative analysis of different memory consumptions, which should highlight the sparsification technique's impact, other than generation quality and training time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose SparseDiff, a novel graph diffusion model focusing on exploiting the sparsity of graph-structured data. One issue of dense graph generative models is having to deal with adjacency matrices, which scale quadratically with the number of nodes. The diffusion and denoising processes of SparseDiff operate instead on the edge list, whose size depends on the sparsity of graphs. As is done in DiGress [1], the diffusion process randomly flips the labels of nodes and edges, but differently from it, only existing edges are modeled explicitly. Non-existing edges go through 3 stages of sampling: the number of new edges,  their position, and their label. To keep the graph sparse during diffusion, the authors opt for the marginal transition process and accurately analyze the evolution of the number of edges. During training, the denoising model is trained to classify the correct existing edges but also addresses currently non-existing edges through random attention. At inference, all node pairs must be considered. The authors propose to do so by partitioning the square adjacency matrix into equally sized sets of edges, and iteratively sampling their new label for the next step using the above-mentioned denoising model. SparseDiff is evaluated on many small, medium, and large datasets against several baselines, from dense models to hierarchical and sparse models. Results show promising results in the direction of sparse conversion of dense models, such as SparseDiff.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As discussed in the weaknesses, critical changes comprise:\n- a deeper comparison between DiGress and SparseDiff, with a stronger motivation for the better results achieved.\n- mentioned bold statements being revisited, or better motivated.\n\nChanges that would likely enhance the value of the paper:\n- describing, if possible, a recipe for applying the same sparsification to other dense models\n- having an evaluation of the memory consumption of the model against others\n\nPossible typos on page 3, section 2.1: notation is inconsistent for $x$ (clean data) and $z_t$ (corrupted data). For example $x_t$ should be $z^t$, and $\\epsilon=z^t-x$.\n\n\n[1] Vignac, Clement, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. \"DiGress: Discrete Denoising diffusion for graph generation.\" In _The Eleventh International Conference on Learning Representations_ (2023).\n\n[2] Chen, Xiaohui, Jiaxing He, Xu Han, and Li-Ping Liu. \"Efficient and degree-guided graph generation via discrete diffusion modeling.\" In _Proceedings of the 40th International Conference on Machine Learning_, pp. 4585-4610. 2023.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YzCIVaGSoM", "reviewer": "Reviewer_tUWL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The motivation is clear. It holds great significance that leveraging the sparsity in large graphs to enable efficient sparse modelling without\nsacrificing generation quality.\n2. The method is clear and easy to follow. Fig.1 gives a very good illustration of the whole method.\n3. The proposed method has been tested on diverse graph datasets to demonstrate its scalability and versatility.\n\nWeaknesses:\n1. While the author shows the time efficiency in the experiments, the analysis of space complexity is missing.\n2. Besides description, a more formal definition or symbolized equation should be given, especially in Sec.3.1.2 and Sec.3.2.1.\n3. Lack of Thorough Theoretical Analysis. It is essential to provide a more rigorous theoretical foundation to support the claim of improved efficiency.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed SparseDiff, a novel diffusion framework that leverages graph sparsity to efficiently scale graph generative models by reducing complexity in noising, training, and inference, achieving state-of-the-art performance, robust scalability, and faster convergence on large-scale datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It would be more convincing to add some analysis of space complexity.\n- More formal definitions or symbolized equations should be given when introducing the details of the method.\n- Additional experiments should be put into the main pages to better show the proposed method's effectiveness.\n- More theoretical analysis should be added.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)