GraphMaker: Can Diffusion Models Generate Large Attributed Graphs?
Authors: Mufei Li
Eleonora Kreacic
Vamsi K. Potluru
Pan Li
Venue: Accepted by TMLR ()

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

Published in Transactions on Machine Learning Research (10/2024)
GraphMaker: Can Diffusion Models Generate Large At- tributed Graphs?
Mufei Li
mafes edu
School of Electrical and Computer Engineering Georgia Institute of Technology
Elconora Kreačić
clenoom.braccceepppaayy...m com
J.P. Morgan AI Research
Vamsi K. Potluru
vamsi humsskk.pttam@@iinnnnne..ccm
J.P. Morgan Al Research
Pan Li
panli edu
School of Electrical and Computer Engineering Georgia Institute of Technology
Reviewed on OpenReview: https: // ottpr//veerrvvee....m net/ ffrmmm id= 0
Abstract
Large-scale graphs with node attributes are increasingly common in various real-world appli- cations. Creating synthetic, attribute-rich graphs that mirror real-world examples is crucial, especially for sharing graph data for analysis and developing learning models when origi- nal data is restricted to be shared. Traditional graph generation methods are limited in their capacity to handle these complex structures. Recent advances in diffusion models have shown potential in generating graph structures without attributes and smaller molecular graphs. However, these models face challenges in generating large attributed graphs due to the complex attribute-structure correlations and the large size of these graphs. This paper intuoes a novel diffusion model, GraphMaker, specifically designed for generating large attributed graphs. We explore various combinations of node attribute and graph structure generation processes, finding that an asynchronous approach more effectively captures the intricate attribuute-struccuuee correlations. We also address scalability issues through edge mini-batching generation. To demonstrate the practicality of our approach in graph data dissemination, we introduce a new evaluation pipeline. The evaluation demonstrates that synthetic graphs generated by GraphMaker can used to develop competitive graph ma- chine learning models for the tasks defined over the original graphs without actually accessing these graphs, while many leading graph generation methods fall short in this evaluation.
1 Introduction
Large-scale graphs with node attributes are widespread in various real-world contexts. For example, in social networks, nodes typically represent individuals, each characterized by demographic attributes (Golder et al. 2007). In financial networks, nodes may denote agents, with each node encompassing diverse account details (Allen & Babus 2009). The task of learning to generate synthetic graphs that emulate real-world graphs is crucial in graph machine learning (ML), with wide-ranging applications. A traditional use case is aiding network scientists in understanding the evolution of complex networks (Watts & Strogatz) 1998:
Barabási Albert] 1999; [Chung Lu 22002) Barrat al.) 2008 Leskovee ct al., 2010). Recently, vital application has emerged due to data socurity needs: using synthetic graphs to replace sensitive original
graphs, thus preserving data utility while protecting privacy (Jorgensen et. al. 2016 Eliás et al. 2020 This

---

Published in Transactions on Machine Learning Research (10/2024)
Original Data
Generative Model
(b) GraphMaker-Sym
Denoue Attributes and Structure Synchronously
deT
house
(x'")")) 1,
(x**0), - p r
(X") A p!n)
Graph
Denoise Adtiibutts
Denoise Structure
Developed Model
Generated Data
(x ym,,)
(00)
(X(1), Mm)), f
public
Node Attribures (N).
Node Label (P)
Creph Str Struut
Figure 1: (a) Data generation for public usage. (b) & (c): Generation process with two GraphMaker variants.
approach is especially beneficial in fields like social/finaccill network studies, where synthetic versions can be used for developing and benchmarking graph learning models, avoiding the need to access the original data. Most of such scenarios require generating large attributed graphs. Fig. (a) illustrates this procedure.
Traditional approaches primarily use statistical random graph models generate graphs (Erdös Rényi 1959 Holland al.] 1983 Barabási & Albert 2002). These models often contain very few parameters such triangle numbers, edge densities, and degree distributions, which often suffer from limited model capacity, AGM (Pfeiffer et al. 2014] extends these models for additionally generating node attributes, but it can only handle very few altribules due to the curse of dimensionality. Recent research on deep generative models of graphs has introduced more expressive data-driven methods. Most of those works solely focus on graph structure generation (Kipf & Welling, 2016 You et al. 20188) Bojchevski et al. 2018 Li et al.] 2018 Liao et al., 2019). Other works study molecular graph generation that involves attributes, but these graphs are often small-scale, and only consist of tens of nodes per graph and single categorical attribute per node (Jin
al.
2018 Liu al. 2018
You al. 2018a De Cao & Kipf 2018).
Diffusion models have achieved remarkable success in image generation (Ho et al. 2020 Rombach et al, 2022) by learning a model to denoise a noisy sample. They have been recently extended to graph structure and molecule gencration. Niu et al. (2020) corrupts real graphs by adding Gaussian noise to all entries of dense adjacency matrices. GDSS (Jo al. 2022) exlends the idea for molecule generation. DiGress (Vignac) et al.] 2023) addresses the discretization challenge due Gaussian noise. Specifically, DiGress employs D3PM Ausstn al.] 20211) to edit individual categorical node and edge typos. However, DiGross is still designed for small molecule generation. EDGE (Chen al.) 2023) and GRAPHARM (Kong al. 2023 propose autoregressive diffusion models for graph structure and molecule generation. Overall, all previous graph diffusion models are not designed to generate large attributed graphs and may suffer from various limitations for this purpose.
Developing diffusion models of large-attributed graphs challenging on several aspects. First, a large attributed graph presents substantially different patterns from molecular graphs, exhibiting complex cor- relations between high-dimensional node attributes and graph structure. Second, generating large graphs poses challenges to model scalability the number of possible edges exhibits quadratic growth in the mum- ber of nodes, let alonc the potential hundreds or thousands of attributes per node. Third, how to evaluate the quality of the generated graphs remains an open problem. Although deep models have the potential to capture more complicated data distribution and correlations, most previous studies just evaluate high-level statistics characterizing structural properties such as node dogree distributions, and clustering coefficients of the generated graphs, which can be already captured well by early-day statistical models (Pfeiffer et al. 2012 Seshadhri et al.] 2012 Therefore, finer-grained way to evaluate the generated large-attributed
2

---

Published in Transactions on Machine Learning Research (10/2024)
graphs is needed for understanding the strengths and limitations of deep generative models, in particular, if the generated synthetic graphs are to be further applied to develop and benchmark graph learning models.
Here we present GraphMaker, a diffusion model for generating large attributed graphs. First, we observe that denoising graph structure and node attributes simultaneonsly with a diffusion model (Fig. (b)) may yield poor performance in capturing the patterns of either component and their joint patterns for large attributed graphs, which is different from the existing observations for molecule generation (Jo et al. 2022). Instead, we propose generalized diffusion process that allows asynchronous corruption and denoising of the two components (Fig. | (c)), which shows better performance in learning the generative models for many real-world graphs. Second, for scalability challenges, we employ minibatch strategy for structure prediction to avoid enumerating all node pairs per gradient update during training, and design & new message- neural network (MPNN) to efficiently encode the data. Third, motivated by the end goal of generating synthetic graphs that preserve utility for developing graph learning models (Fig. [ (a)), we propose to utilize
ML models, including graph neural networks (GNNs) (Kipf Welling 2016 2017 Wu et al. 2019 Gasteiger let al. 2019), by training them on the generated graphs and subsequently evaluating their performance on the original graphs. When equipped with strong discriminative models, our evaluation protocol allows more fine-grained examination of attribute-struucture correlation, which is complementary to the evaluation based on high-level graph statistics. For the scenarios targeting the task of node classification, each node is additionally associated with a label. In this case, GraphMaker can perform conditional generation given node labels, which further improves the data utility for ML model development.
Extensive studies on real- world networks with up to more than 13K nodes, 490K edges, and 1K attributes demonstrate that GraphMaker overall significantly outperforms the baselines in producing graphs with re- alistic properties and high utility for graph ML model development. For evaluation on graph ML tasks, GraphMaker achieves the best performance for 80% of cases across all datasets. For property evaluation, GraphMaker achieves the best performance for 50% of cases, In addition, we demonstrate the capability of GraphMaker in generating diverse novel graphs.
2
GraphMaker
2.1
Preliminaries and problem formulation
Consider an undirected graph G = (V,EX)) with the node set V and the edge set E. Let N = [V] denote the number of nodes. Each node v E V is associated with F-dimensional categorical attributes X Note that we are to generate graphs without edge attributes to show a proof of concept, while the method can be exlended for the case with edge altribules. We aim to learn Pg with Pg based on one graph G sampled from it, which can be used generate synthetic graphs for further graph learning model development. In Section 2.6 we provide some reasoning on why the distribution may be possibly learned from one single observation. In the scenarios targeting node classification tasks, each node is additionally associated with label Y,, which require learning Pyxy from (G, Y) instead.
2.2 Forward diffusion process and reverse process
Our diffusion model extends D3PM (Austin et al. 2021 large attributed graphs. There are two phases. The forward diffusion process corrupts the raw data by progressively perturbing its node altributes or edges. Let X XxXXx be the one-hot encoding of the categorical node attributes, where for simplicity we assume all attributes to have Cx possible classes. By treating the absence of edge an edge type, we denote the one-hot encoding of all edges by A E NxNx2, Let ( be the real graph data (X, A).
We individually corrupt node attributes and edges of G(+-1) into G by first obtaining noisy distributions with transition matrices and then sampling from them. By composing the noise over multiple time steps, for G( = (x()) A (() at time step 1 E [T], we have g( q(x (x,)) = x.,, QK) for any o E [N], f E (P) AQ To ensure G(t) to be undirected, Q4 is only applied to the upper triangular
and (A)( part of A. The adjacency matrix of G(t), i.c., A is then constructed by symmetrizing the matrix after sampling. We consider general formulation of Qx, and ((1) that allows asynchronous corruption of node
3

---

Published in Transactions on Machine Learning Research (10/2024)
attributes and edges. Let Tx [tx..... , [T] be the time steps of corrupting node attributes, and TA (t).... TTa c [T]
be the time steps of corrupting edges. Then,
a (1 - (tx(t) (1-āxx(t) 1mx,
(1)
A Cralt) I+ (1 a7a(1)) 1m
(2)
where ()2(1)) Reslese if S 1
or otherwise (2) än = 1,, for Z E (X, We consider the popular
cosine schedule in this paper Nichol & Dhariwal 2021 where (1)(() = cos? (2(t//72lts for some small I+a
s, but the model works for other schedules as well. Is the identity matrix, 1 is a one-valued vector, mx, is the empirical marginal distribution of the f-th node attribute in the real graph, m,4 is the empirical marginal
distribution of the edge existence in the real graph, and denotes transpose.
During the reverse process, the second phase of the diffusion model, denoising network ds,t is trained to perform one-step denoising po (G((-))) t). Once trained, we can iteratively apply this denoising network to noisy graph sampled from the prior distribution II II mx, Iliss Ilaces mA for data gener- ation. While we consider Ñ = in this paper, the model is capable of generating graphs a different size. We model (GG .t) as a product of conditionally independent distributions over node attributes and edges.
Po Po(((t-)) =
II II
Pe X ((())))
(3)
II N
po po
Sohl-Dickstein et al. (015) and Song & Ermon 2019 show that we can train the denoising network to predict
G(U) instead of G 1) as long as g(G G G ypo (G 1) has a closed- fosed-form expression. This
holds for case. By the Bayes rule, have q q( ( G t, GXO) x (Q)) ) @ xx, (t-1))
(t-1) where
and @ is the elementwise product. Similarly, we have (LAl""""GG (())) x
2.3 Two instantiations
To model the complex correlations between node attributes and graph structure, we study two particular instantiations of GraphMaker, named GraphMakor-Sync and GraphMakor-Async, When categorical node label Y is present, as in the task of node classification, we can treat it as an extra node attribute. For simplicity, we do not distinguish from X for the rest of this sub-section unless stated explicitly.
GraphMakor-Syne (GMaker-S). GraphMaker employs forward diffusion process that simultanc- ously corrupts node attributes and edges for all time steps, which corresponds to setting Tx Ta [T]. The denoising network is trained to recover clean node attributes and edges from corrupted node attributes and edges. During generation, it first samples noisy attributes XT), and noisy edges (T") from the prior distri- butions. It then repeatedly invokes the denoising network d0 to predict G()) for computing the posterior distribution pe (G() t), and then samples ((--1), Fig. (b) provides an illustration.
GraphMaker- (GMaker-A). In practice, we find that GraphMaker--Syne cannot properly capture the correlations between high-dimensional node attributes, graph structure, and node label, shown in later Sections 3.2 and 3.3 Previous work has pointed out that failure to model edge dependency in graph structure generation yields poor generation quality in capturing patterns like triangle count |Chanpuriyal et al. 2021). We suspect that this problem stems from synchronous refinement of node altributes and graph structure, hence we propose to denoise node attributes and graph structure asynchronously instead. We consider a simple and practically effective configuration as proof of concept, which partitions [1, T] into two subintervals Ta [1, tm and Tx [tm + 1, The denoising network de, consists of two sub-networks. dox,t is an MLP trained to reconstruct node attributes (0) given (X(1), t). Φ0 is trained to reconstruct
4

---

Published in Transactions on Machine Learning Research (10/2024)
.t. During generation, it first samples noisy attributes X then repeatedly invokes Φ0x: t until the generation of node attributes is finished. Finally, it samples noisy edges A and invokes 69A. (A (6) x ,t) repeatedly to complete the edge generation. Fig. 1 (c) provides a visual illustration.
edges given (A,),x(0),
x()).)).
2.4 Conditional generation given node labels
An important learning lask for large attributed graphs is node classification, where each node associated with a label. To generate graph data with node labels, one naive way to simply generate node labels as extra node attributes. While this idea is straightforward, it may not perform the best at capturing the correlation between node label and other components, empirically demonstrated in Section 3.2 and 3.3 To further improve the generation quality for developing or benchmarking node classification models, we propose conditional graph generation. Conditional generative models have been proven valuable in many applications, such as gencrating images consistent with a target text description (Rombach et al.) (022) or material candidates that satisfy desired properties (Vignac et al. 2023 where controllable generation is often desirable.
Specifically, since the node label distribution Py can be estimated from the real node labels, we can simplify the problem by learning the conditional distribution Pgp: rather than Pøxy, which essentially requires learning a conditional generative model. This corresponds to sctting Y (c). During training, the denoising network is supplied with uncorrupted node labels. During generation, node labels are sampled and fixed at the begimning to guide the generation of the rest node attributes and graph structure. We notice that conditional generation gives a further boost in the accuracy for developing node classification models through the generated graphs.
Y(T) in figure (b) &
2.5 Scalable denoising network architecture
Large attributed graphs consist of more than thousands of nodes. This poses severe challenges to the scalability of the denoising network. We address the challenge with both the encoder and the decoder of the denoising network. The encoder computes representations of GO) and the decoder makes predictions of node attributes and edges with them.
Graph encoder. To enhance the scalability of the graph encoder, we propose a message passing neural network (MPNN) with complexity O(EE) instead of using a graph transformer (Dwivedi & Bresson 2021 with complexity O(N2), which was employed by previous graph diffusion generative models (Vignac et al. 2023). Empirically, we find that with a 16-GB GPU, we can use at most a single graph transformer layer, with four attention heads and hidden size of 16 per attention head, for a graph with approximately two thousand nodes and one thousand attributes. Furthermore, while in theory graph transformers surpass MPNNs in modcling long-range dependencies owing to non-local interactions, it is still debatable whether long-range dependencies are really needed for large-attributed graphs. In particular, graph transformers have not demonstrated superior performance on standard benchmarks for large attributed graphs like OGB (Hu ct al. 2020
Let (1) and (() respectively be the one-hot encoding of the edges and node altributes for the time step t. The encoder first uses multilayer perceptron (MLP) to transform x(t) and the time step into hidden representations (1.)) and h()) It then employs multiple MPNN layers to update attribute representa- tions. For any node E V. x((++1] = a awi() /ww/x((0 h(t) + +bQ + Eues(o ((l)) (1..)) ((l))) x-x), where
w! W w X and by are learnable matrices and vectors. (v) consists of v and the neighbors of v corresponding to (1) consists of a ReLU layer Jarrett et al. (2009), LayerNorm layer Ba el. al. (2016). and dropout layer Srivastava et al. (2014). The encoder computes the final node representations with
H x (1.0) x((.)) Ih.), which combines the representations from all MPNN layers as in JJK-Nets Xu
et al. 2018 We employ two separate encoders for node attribute prediction and edge prediction.
For conditional generation discussed in Section 2.4 we treat node labels in a way different from other node attributes. Specifically, we update node label representations separately Y( ab +
Emerio [oo[[]] ((()) y-x), where will) Wy and by are learnable. Note that here we do not cor-
5

---

Published in Transactions on Machine Learning Research (10/2024)
rupt node labels, there is no need to incorporate the time-step encoding h(t) The label representa- tions of layer 1, (Y (ee are used in computing x(( with x(( a (w
T h (1) + b +
EuENiO - x Y W and H with H x | |
[x] [No[[o]]
(9)
Decoder. The decoder performs node attribute prediction from H in the form of multi-label node classification. To predict edge existence between nodes u, V in an undirected graph. the decoder performs binary node pair classification. It first computes the elementwise product H C H and then applies an MLP to transform this product into the final score. Due to limited GPU memory, it is intractable to perform edge prediction for all N node pairs at once. During training, we randomly choose subset of the node pairs for a gradient update. For graph generation, we first compute the representations of all nodes and then perform edge prediction over minibatches of node pairs.
2.6 Can graph generative model be learned from single graph?
It remains to be answered why we can learn the graph distribution from only one sampled graph. Due to the permutation equivariance inherent in our MPNN architecture, the derived probability distribution is permutation invariant. In other words, altering the node ordering in a graph doesn't affect the model's likelihood of gencrating it. This suggests that our model is primarily focused on identifying common patterns across nodes instead of focusing on the unique details of individual nodes. In this case, single, expansive graph can offer abundant learning examples- each node centered subgraph acts as a distinct data point.
This raises an intriguing query - should a model for large graph generation capture individual node charac- teristics? We think the answer depends on the use cases. If the goal is to analyze population-level trends, individual node details will be distractions. Note that traditional graph generative models like ER (Erdös & Rényi 1959), and its degree-corrected counterpart (Seshadhri et al. 2012) only capture population-level statistics like degree distributions. For scenarios that involve sharing synthetic graphs with privacy consid- erations, omitting the node-specific details is advantageous. Conversely, if node-specific analysis is essential, our model might fall short. Overall, there's always a tradeoff between a model's capabilities, the data at hand, the desired detail level, and privacy considerations. We think of our work as a first step and will let future works dive deeper into this issue. In Section 3.5 we empirically study this point. Indeed, adopting a more expressive model with node positional encodings (Eliasof al., 2023) that may capture some individual node details does not consistently improve the quality of the generated graphs in our evaluation.
3 Experiments
In this section, we aim to answer the following questions with empirical studies. Q1) For the end goal of using synthetic graphs to develop and benchmark ML models, how does GraphMaker perform against the existing generative models in preserving data utility for ML? Q2) For the studies of network science, how does GraphMaker perform against, the existing generative models in capturing structural properties? Q3) For the potential application of privacy-preserving synthetic data sharing, generative models should avoid merely reproducing the original graph. To what extent do the generated synthetic graphs replicate the original graph? Q4) Does capturing individual-level node characteristics benefit capturing population-level patterns?
3.1 Datasets and baselines
We utilize three large attributed networks for evaluation. Cora is citation network depicting citation relationships among papers (Sen et al. 2008), with binary node attributes indicating the presence of keywords and node labels representing paper categories. Amazon Photo and Amazon Computer are product co- oo-purchase networks, where two products are connected if they are frequently purchased together (Shchur et al. 2018). The node attributes indicate the presence of words in product reviews and node labels represent product categorics. See Appendix A.1 for the dataset statistics. Notably, Amazon Computer (13K nodes, 490K edges) is order of magnitude larger than graphs adopted for evaluation by previous deep generative
Datasets:
6

---

Published in Transactions on Machine Learning Research (10/2024)
models of graph structures (Chen et al. 2023 Kong et al. 2023 and hence it is a challenging testbed for model scalability.
Baselines: To understand the strengths and weaknesses of the previous diffusion models in large attributed graph generation, we consider two ttaee-of-the-art diffusion models developed for graph generation, GDSS (Jo et al. 2022 and EDGE (Chen et al. (023). For non-diffusion deep learning (DL) methods, we adopt feature- based matrix factorization (FMF) (Chen et al.) 2012), graph auto-encoder (GAE), and variational graph auto-encoder (VGAE) (Kipf & Welling 2016). In addition, compare against the
Rényi (ER) model (Erdös & Rényi 1959), traditional statistical random graph model. None of the non-diffusion basclines inherently possesses the capability for node attribute generation. Therefore, we equip them with the empirical marginal distribution p(Y) II, ((X..)lYY)) for attribute and label generation. Node attributes and label generated this way yield competitive classification performance, as shown in Appendix A.3 For more details on baseline experiments, see Appendix A.2
3.2 Evaluation for ML utility (Q1)
To evaluate the utility of the generated graphs for developing ML. models, we introduce a novel evaluation protocol based on discriminative models. We train one model on the training set of the original graph (G, Y) and another model on the training set of generated graph (G, Y). We then evaluate the two models on the test set of the original graph to obtain two performance metries ACC(G]G) and ACC(GIG). If the ratio is close to one, then the generated graph is considered as having utility similar to the original graph for training the particular model. We properly Lune each model to ensure a fair comparison, see Appendix A..3 for more details.
ACC(G)))/ACC(GH))))
Node classification. Node classification models evaluate the correlations between unlabeled graphs and their corresponding node labels. Given our foeus on the scenario with single large graph, we approach the semi-supervised node classification problem. We randomly split a generated dataset so that the number of labeled nodes in each class and each subset is the same that in the original dataset. For discriminative models, we choose three representative GNNs - SGC (Wu et al. 2019), GCN (Kipf & Welling 2017 and APPNP (Gasteiger et al.] 2019). As they employ different orders for message passing and prediction this combination allows for examining data patterns more comprehensively. To scrutinize the retention of higher- order patterns, we employ two variants for each model, one with a single message passing layer denoted by 1-* and another with multiple message passing layers denoted by L-* In addition, we directly evaluate the correlations between node attributes and node label with MLP in appendix A.3
Link prediction. This task requires predicting missing edges in an incomplete graph, potentially utiliz- ing node attributes and node labels. To prevent label leakage from dataset splitting, we split the edges corresponding to the upper triangular adjacency matrix into different subsets and then add reverse edges after the split. We consider two types of discriminative models Common Neighbor (CN) (Liben-Nowell & Kleinberg 2003) and GAF (Kipf & Welling 2016]. CN is a traditional method that predicts edge existence if the number of common neighbors shared by two nodes exceeds a threshold. GAE is an MPNN- based model that integrates the information of graph structure, node attributes, and node labels. As before, we consider two variants for GAF. Following the practice of Kipl & Welling (2016), we adopt ROC-AUC as the evaluation metric.
Table presents the results. Unless otherwise mentioned, we report all results in this paper based on three different random seeds. For the performance of the discriminative models trained and evaluated on the original graph, see Appendix A.3 Out of 24 cases, GraphMaker variants perform better or no worse than the baselines for 20 of them (~ 83%).
Diffusion models that asynchronously denoise node attributes and graph structure (GraphMakerrAsymu (GMaker-A) and EDGE) outperform the synchronous ones (arrphMaker-SSnn (GMaker-S) and GDSS) by a large margin. This phenomenon is in contrast to the previous observation made for molecule generation by the GDSS paper (Jo et al., )022), reflecting the drastically different patterns between a large attributed graph and molccular graphs. EDGE proposcs a degree guidance mechanism, where the graph generation is conditioned on node degrees pre-determined from the empirical node degree distribution. While achieves competitive performance on Cora, it falls short on Amazon Photo, which might be due to degree constraints.
7

---

Published in Transactions on Machine Learning Research (10/2024)
Table 1: Evaluation with discriminative models. Best results are in bold. OOM stands for out of memory.
Cora
Model
Node Classification +
Link Prediction -1
1-SGO
L-SGC
L-GON
1-APPNP
L-APPNP
CN
1-GAE
L-GAE
ER
0.55 +: 0.08
0.65 1: 0.17
0.64 + 0.22
0.83 = 0.02
0.87 + 0.04
0.80 + 0.13
0.90 = 0.07
0.79 :: 0.05
FMF
1.06 +: 0.01
0.83
4: 0.12
0.79 +: 0.16
1.04 = 0.02
1.01 # 0.02
0.71 + 0.00
0.95 = 0.01
0.74 = 0.03
GAE
1.06 +: 0.01
0.85
+: 0.19
0.76 +: 0.17
1.04 + 0.02
1.01 + 0.02
0.71 + 0.00
0.96 = 0.01
0.75 + 0.07
VGAE
1.00 +: 0.01
0.70 1: 0.23
0.51 +: 0.16
1.04 +: 0.02
1.00 + 0.02
0.71 + 0.00
0.97 = 0.00
0.71 + 0.03
GDSS EDGE
0.28 +: 0.10
0.25 + 0.07
0.26 + 0.08
0.23 = 0.04
0.23 + 0.06
0,88 - 0.14
0,82 = 0.07
0.74 +: 0.05
0.92 + 0.03
1.01 + 0.01
1.00 + 0.02
0.96 + 0.02
1.00 + 0.02
1.00 + 0.00
0.97 + 0.00
0.97 + 0.01
GMaker-S
0.40 +: 0.06
0.41 +: 0.07
0,40 + 0.00
0.41 + 0.00
0,40 + 0.02
0.88 +: 0.14
0.92 = 0.06
0.83 +: 0.05
GMaker-A A
0.88 + 0.04
0.97 + 0.04
0.99 + 0.03
0.93 + 0.03
1.00 + 0.02
1.00 + 0.00
0.98
0.00
0.99 + 0.00
GMaker-S (oond.)
0.93 + 0.02
1.02 + 0.02
1.01 + 0.02
0.98
0.01
1.01 + 0.02
1.00
0.00
0.98
0.00
0.98 + 0.01
GMaker-A (vond.)
0.95 +: 0.02
1.00 + 0.02
1.00 + 0.03
0.96 + 0.03
1.01 +: 0.02
1.00 0.00
0.98 0.00
0.99 0.00
Amazon Photo
Model
Node Classification +1
Link Prediction -1
I-SGC
L-SGC
L-GCN
1-APPNP
L-APPNP
CN
1-GAE
L-GAE
ER
0.38 + 0.10
0.45 + 0.17
0,16 +: 0.12
0,79 = 0.04
0,80 + 0.04
0.85 1 0.22
0,95 = 0.00
0,63 1: 0.15
FMF
0.84 + 0.09
0.37 + 0.17
0,12 1 0.01
0.85 = 0.03
0.72 1 0.05
0.54 + 0.00
0.99 = 0.00
0,82 : 0.01
GAE
0,60 + 0.10
0,18 + 0.03
0.07 + 0.04
0.84 = 0.03
0.72 1 0.08
0,54 + 0.00
0.99 = 0.00
0.74 + 0.03
VGAE
0.89 + 0.11
0.42 +: 0.08
0.19 +: 0.09
0.78 + 0.02
0.81 + 0.00
0.54 + 0.00
0.99 = 0.00
0.79 + 0.02
CDSS
00M
OOM
00M
0OM
OOM
OOM
OOM
OOM
EDGE
0.78 :: 0.08
0.76 1: 0.09
0.76 +: 0.05
0.90 =: 0.02
0.92 =:2 0.02
1.00 :: 0.00
0.97 = 0.01
0.91 +: 0.03
CMaker-S
0.12 +: 0.03
0.19 1: 0.08
0.11 +: 0.05
0.18 + 0.06
0.21 +: 0.05
0.54 + 0.00
0.85 = 0.01
0.84 +: 0.00
CMaker-A
0.97 +: 0.06
0.98 + 0.06
0.93 + 0.03
0.93 : 0.01
0.92 + 0.02
1.00 + 0.00
1.00 = 0.00
0.98 + 0.01
GMaker-S (oond.)
1.00 + 0.06
1.00 + 0.06
0.89 + 0.01
0.89 + 0.01
0.89 + 0.02
0.99 + 0.00
0.98 + 0.00
0.98 + 0.00
GMaker-A (oond.)
1.12 -: 0.11
1.02 + 0.05
0.94 + 0.00
0.93 + 0.03
0.94 + 0.01
1.00 + 0.00
1.00 0.00
0.99 + 0.00
Amazon Computer
Model
Node Classification + 1
Link Prediction + +1
I-SGO
L-SGC
L-GON
1-APPNP
L-APPNP
CN
1-GAE
L-GAE
ER
0.28 1: 0.20
0.38 1: 0.11
0.16 0.10
0.76 : 0.15
0.87 1: 0.02
0.82 : 0.20
0.96 = 0.03
0.88 4: 0.03
FMF
0.20 0.06
0.08
0.11 0.03
0.91 : 0.03
0.71 1: 0.26
0.34 0.00
0.99 0.00
0.83 1: 0.02
GAE
0.43 0.13
0.29 0.04
0.35 0.19
0.92 = 0.02
0.79 1 0.03
0.34 0.00
0.98 = 0.00
0.87 1 0.07
VGAE
0.34 0.05
0.37 0.01
0.12 0.07
0.80 0.15
0.62 = 0.17
0.54 0.00
0.97 = 0.02
0.87 = 0.03
CDSS
0OM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
EDGE
00M
0OM
0OM
OOM
OOM
OOM
OOM
OOM
GMaker-S
0.32 +: 0.19
0.32 1: 0.11
0.07 1: 0.03
0.18 +: 0.04
0.09 + 0.05
1.00 + 0.00
0.84 = 0.01
0.77 : 0.08
CMaker-A
0.92 1: 0.07
0.86 1: 0.15
0.94 1: 0.01
0.95 : 0.01
0.97 1 0.02
1.00 + 0.00
0.96 = 0.00
0.98 :: 0.01
S (oond.)
0.76 + 0.04
0.87 + 0.04
0.92 + 0.00
0.89 + 0.02
0.92 + 0.01
0.85 + 0.01
0.97 + 0.01
0.98 + 0.03
GMaker-A (pond.)
1.00 +: 0.18
1.00 + 0.10
0.96 + 0.02
0.96 + 0.02
0.98 + 0.03
0.82 +: 0.01
0.97 = 0.00
1.01 + 0.00
Moreover, conditioning on degree distribution reduces the novelty of the generated graphs. In terms of scalability, GraphMaker the only diffusion model that does not encounter the out-of-memory (OOM) error on a 48-GB GPU. As GDSS denoises dense adjacency matrices, it has a complexity of O(N2) for representation computation even with an MPNN. Therefore, it has worse scalability than EDGE. Overall, the results also suggest the effectiveness of the proposed evaluation protocol in distinguishing and ranking diverse generative models.
For scenarios targeting the task of node classification, we can adopt conditional generation given node labels for better performance, as discussod in Section [2.4] Label-conditional GraphMaker variants, denoted by (cond.) in the table, perform better or no worse than the unconditional ones for about 90% cases. Among the GraphMaker variants, label-conditional GraphMaker-AAyne achieves the best performance for
8

---

Published in Transactions on Machine Learning Research (10/2024)
Table 2: Evaluation for benchmarking ML models. Best results are in bold. OOM stands for out of memory.
Cora
Amazon Photo
Amazon Computer
Model
Pearson f
Spearman
Pearson f
Spearman
Pearson
Spearman
ER
-0.87 0.03
-0.10 + 0.10
0.29 0.05
0.49 0.12
0.14 0.04
0.12 +: 0.05
FMF
0.03 0.07
-0.25 + 0.08
0.13 :: 0.03
0.37 0.00
0.43 0.06
0.66 + 0.08
GAE
0.04 = 0.06
0.25 = 0.08
0.30 1 0.07
0.39 = 0.03
0.27 0.05
0.41 + 0.03
VGAE
-0.02 0.04
-0.29 0.07
0.32 0.14
0.52 0.03
0.08 0.11
0.18 + 0.15
GDSS
-0.44 = 0.28
0.03 = 0.25
0OM
OOM
0OM
OOM
EDGE
0.97 = 0.02
0.97 = 0.02
0.63 + 0.03
0.61 = 0.02
00M
OOM
GMaker-S
-0.11 = 0.20
0,18 = 0.33
0.26 +: 0.55
0.31 = 0.47
-0.09 0.05
0.12 0.19 0.73 + 0.05
GMaker-A
0.97 = 0.01
0.93 = 0.04
0.99 + 0.00
0.79 0.07
0.97 + 0.01
GMaker-S (cond.)
0.96 =: 0.03
0.99 + 0.02
0.87 +: 0.05
0.90 0.02
0.94 0.01
0.90 + 0.05
GMsker-A (cond.)
0.98 = 0.01
0.95 4 0.05
0.90 0.06
0.87 0.07
0.98 + 0.02
0.75 + 0.12
18/24- 75% cases. Meanwhile, it is worth noting that label conditioning narrows the performance gap between GraphMaker-Syni and SaaphMakke-Asynss
Utility for Benchmarking ML Models on Node Classification. Another important scenario using generated graphs is benchmarking ML. models, where industry practitioners aim to select the most effective model architecture from multiple candidates based on their performance on publicly available synthetic graphs and then train a model from scratch on their proprietary real graph. This use case requires the the
generated graphs to yield reprodueible relative performance of the candidate model architectures original graph. Following Yoon et al. (2023), for each candidate model architecture, we train and evaluate one model on the original graph for ACC(G))) and another on a generated graph for ACC(G]G). We then report the Pearson/ /Spaarman correlation coefficients between them (Myers et al. 2010). We include all six model architectures for node classification in the set of candidate model architectures.
Table presents the experiment results. Out of 6 cases, unconditional GraphMaker-Async performs better no worse than all baselines for 5 of them. Overall, the results are consistent with the previous obser- vations in terms of the benefit of asynchronous generation and label conditioning. The only exception is TraphMake-AAymn in terms
that label-conditional Graph slightly outperforms label-conditional of Spearman correlation coefficient by a small margin of 0.02 on average. Spearman correlation coefficient examines the reproduction of relative model ranking differences, and is most useful when there exists a sub- stantial performance gap between each pair of candidate models. In practice, when multiple models perform sufficiently similar, the final decision on model selection can involve a tradeoff between cost and performance. In this case, exactly reproducing the relative model ranking differences may be less important than repro- ducing the relative model performance differences, in which case Pearson correlation coefficient is preferred instead. This applics to our case, as reflected by the raw ACC(G]G) values reported in Appendix A.3
3.3 Evaluation for structural properties (Q2)
To assess the quality of the generated graph structures, following You et al. (0188)) we report distance met- rics for node degree, clustering coefficient, and four-node orbit count distributions. We adopt 1-Wasserstein distance W1 (z, y), where x, are respectively a graph statistic distribution from the original graph and a generated graph, and a lower value is better. Besides distribution distance metrics, we directly compare a few scalar-valued statistics. Let MG) be non-nogative-vahne statistic, we report Eg-po [M
where & is a generated graph. A value closer to 1 is better. In addition to triangle count, we employ the following metric for measuring the correlations between graph structure and node label (Lim et al. 2021 where a larger value indicates a higher correlation.
Cx Σ M( = Cx -1 km
Ex. N(o) YYH I1, = =b]l W(()
max f0.
(4)
N
9

---

Published in Transactions on Machine Learning Research (10/2024)
Table 3: Evaluation for structural properties. Best results are bold. OOM stands for out memory.
Amazon Photo
Model
W1 4
G
M(C)/M( -1
Degree (x109)
Chuster (x10)
Orbit
# Triangle
k(A.Y) Y)
h(A?, Y)
ER
0.019 + 0.000
0.15 + 0.00
1.4+0.0
0.005 + 0.000
0.0013 0.0002
0.0024
0.0001
FMF
3.8 = 0.0
0.15 - 0.00
1.400
0.0032 + 0.0011
0.10 + 0.00
0
GAE
3.8 +: 0.0
0.15 + 0.00
1.4
0.0064 + 0.0011
0.062 + 0.000
0 0
VGAE
3.8 + 0.0
0.15 : 0.00
1.4
0.0040 +: 0.0023
0.12 1.12::000 0.00
0
GDSS
OOM
OOM
OOM
OOM
OOM
OOM
EDGE
0.0017 + 0.0001
0.1
0.060 + 0.021
0.34 + 0.04
0.38 + 0.02
0.41 + 0.03
GMaker-S
3.4 0.0
0.15 0.00
1.3++.0
0.010 0.001
0.0010
0.0000
0+ 0.93 0.03
GMaker-A
0.017 = 0.000
0.018 + 0.000
0.41 + 0.00
1.5
0.88 0.02
GMaker-S (cond.)
0.074 = 0.006
0.13 0.00
1.0
0.1 0.0
1.1
0.76 + 0.02
GMaker-A (oond.)
0.0069 1 0.0007
0.039 0.005
0.55 0.08
0.88 1 0.08
1.0
1.4 1 0.0
Amazon Computer
Model
W1 +
E G
MGGG/M(G)) -1
Degree (x10²)
Cluster (x10-1)
Orbit
# Triangle
i(A,Y Y)
i(A? Y)
ER
0.025 + 0.000
3,0 1 0.1
2.2 0.0
0.022 = 0.015
0.00095 +: 0.00000
0.0029 +: 0,0000
FMF
6.8 + 0.0
3.1 0.1
2.1
0.0036 0.0051
0.067 + 0.001
0++
GAF
7.5 0.0
3.2 0.0
2.1
0.0036
0.0051
0.034 0.000
0+0
VGAE
7.4 0.0
3.1
2.1 0.0
0.0036 = 0.0051
0.083 0.000
0
GDSS
00M
0OM
00M
OOM
OOM
OOM
EDGE
00M
00M
00M
00M
0OM
0OM
GMaker-S
0.050 + 0.000
3.0
0.0
0=
0.0056 + 0.0006
0.0099 + 0.0001
GMaker-A
0.030 + 0.000
0.0
0.86 + 0.00
1.9 - 0.2
0.84 + 0.01
0.79 0.09
GMaker-S (cond.)
0.26 0.03
2.7 0.1
1.5 0.1
0.072
0.005
1.2 0.0
0.54 0.01
GMaker-A (cond.)
0.21 + 0.00
2.0 + 0.3
1.2 + 0.0
0.46
0.08
1.3 + 0.0
1.2 + 0.0
where Cy is the number of node classes, and (Vv) consists of the neighboring nodes of v. We also report the metric for two-hop correlations, denoted by i(AA2, Y). The computation of clustering coefficients, orbit counts, and triangle count may be costly for the large generated graphs. So, in such cases, sample edge-induced subgraph with the same number of edges from all generated graphs.
Table 3 displays the evaluation results on Amazon Photo and Amazon Computer. See Appendix A.5 for the results on Cora. None of the models consistently outperforms the rest. In terms of the number of cases where they achieve the best performance, the best model is label-conditional GraphMaker-Asyyn with out of 18. The degroo-guidance mochanism adopted by EDGE is effective in capturing local structural patterns and leads to the best performance for degree Wi and orbit W, on Cora and Amazon Photo. Across the conditional and unconditional cases, GraphMaker-Asyyann outperforms GraphMaker-Syne in W1 metrics and triangle count for 21 /24 87.5% cases, demonstrating superior capability in capturing edge dependencies. In consistent with the evaluation using discriminative models, label conditioning yields better performance for 26/36 Re 72% cases.
Diversity. Based on evaluation with statistics and discriminative models, we also show that GraphMaker is capable of generating diverse and hence novel graphs in Appendix A.4
3.4 Evaluation for graph recovery (Q3)
To quantify the recovery of the original graph by the synthetic graphs, we evaluate their similarity. Precisely mcasuring the similarity between two graph structures requires solving the subgraph isomorphism problem, which known to be NP-complete (Cook) 1971). This challenge is further complicated by the presence of numerous node attributes. Therefore, propose local node-centered comparisons based the node
10

---

Published in Transactions on Machine Learning Research (10/2024)
Table 4: Evaluation for graph similarity on Cora.
The most similar results are bold.
Model
Attribute (x10 3)
1-hop (x10
2-hop (x ")
ER
16
1.8
9.2
FMF
160
1.2
7.7.1. 0.5
GAE
1.6 16:000 0.0
1.2
7.7.+...4 0.4
VGAE
1.6
1.2
7.8
GDSS
46.7
48.9
46.3 0.1
EDGE
0.0
134000
4.0
GMaker-S GMaker-A
15
1840.1
9.2
1.3+
1.5
6.4
GMaker-S (cond.)
1.0
1.5
6.8
GMaker-A (cond.)
0.9 0.0
1.2
3.7
Table 5: Ablation study for node-personalized label-conditional models on Cora. Better results are bold.
Wi 4
M(C)/MMG)))
+1
Model
PE
Degree
Cluster
Orbit
# Triangle
b(A,)
K(A?, Y)
GMaker-S
0.62
23
1.3
0.071
0.92
0.95
(cond.)
0.53
23
1.4
0.06
0.91
0.96
GMaker
1.5
(cond.)
Node Classification +1
Link Prediction
Model
PE
MLP
1-SGC
L-SGC
L-GCN
1-APPNP
LAPPNNP
CN
1-GAE
L-GAE
GMaker-S
1.00
0.93
1.01
1.01
0.99
1.01
1.00
0.98
0.98
(cond.)
1.02
0.89
0.99
0.99
0.95
1.00
1.00
0.97
0.98
GMaker-A
1.00
1.00
(coud.)
0.93
1.00
1.00
labels and attributes. Given node in the original graph, we define its most similar counterpart ((v) in a synthetic graph as follows:
(TV) arg min
XX Xollı,
(5)
where V, X, and Ý are the node set, node attributes, and node labels in synthetic graph, respectively. We then report the overall attribute discrepancy with:
1
Σ X.
Xa(w)lla
(6)
N
PEy
To account for structures, we extend the comparison to K K-hop neighbors (1) and (())(=
N E min (EM(
|X,, Kalli.
(x
Table presents the evaluation results on Cora. While label-conditional GraphMaker-Asyne generally pro- duces the most similar synthetic graphs, associated metrics remain at a similar order of magnitude compared to other approaches, suggesting that GraphMaker does not merely replicate the original graph.
3.5 Ablation study for node personalization (Q4)
We perform an ablation study see if capturing each node's personalized behavior helps improve the graph generation quality. We adopt state-of positional encoding (PE) method RFP (Eliasof al., 2023). It uses random node features after certain rounds of message passing operations as PFs, where
11

---

Published in Transactions on Machine Learning Research (10/2024)
the random initial features can be viewed as identity information to distinguish node from the others. In our experiments, for each noisy graph either during training generation, we compute PFs based on the current noisy graph structure and then use PEs as extra node attributes. This essentially assists the model in encoding more personalized behaviors of nodes. We cxamine the effects of such personalization on label-conditional GraphMaker for Cora. Table 5
presents the evaluation results for structural properties and ML. utility. For 22/29 R 76% cases, GraphMaker variants without PE perform better than or comparable GraphMaker variants with PE, which suggests that personalized node behaviors may not be really useful to learn graph generative model, at least in our downstream evaluation.
4 Further related works
We have reviewed the diffusion-based graph generative models in Section | Here, we review some other non- diffusion deep generative models and some recent improvement efforts synthetic graph data evaluation. We leave review on classical graph generalive models to Appendix A.6
Non-diffusion deep generative models of large graphs. GAE and VGAE (Kipf & Welling, 2016) extend AE and VAE (Kingma & Welling 2014 Rezende et al. 2014) respectively for reconstructing and generating the structure of a large attributed graph. NetGAN (Bojchevski et al. 2018) extends WGAN (Ar- jovsky et al. 2017| for graph structure generation by sequentially generating random walks. GraphRNN YYo et al.) 2018b) and Li et al. (2018) propose auto-regressive models that generate graph structures by sequen- tially adding individual nodes and edges. GRAN (Liao al. (219)) introduces more efficient auto-regressive model that generates graph structures by progressively adding subgraphs. CGT (Yoon et al. 2023) tackles simplified version of the large attributed graph generation problem that we consider. It clusters real node altributes during data pre-processing and generates node-centered ego-subgraphs (essentially trees) with a single categorical node label that indicates the attribute cluster.
Evaluation of generated graphs with discriminative models. GraphWorld (Palowitch al. 2022) is software for benchmarking discriminative models on synthetic altributed graphs, but it does nol compare synthetic graphs against a real graph in benchmarking, CGT (Yoon et al. 2023 uses generated subgraphs to benchmark GNNs. It evaluates one model for node classification on the original graph and another on generated subgraphs, and then measures the performance correlation/ hation///dsscceeccyyc/ of the models. Our work instead is the first effort to train models on a generated graph and then evaluate them on the original graph. Outside the graph domain, CAS employs discriminative models to evaluate the performance of conditional image generation (Ravuri & Vinyals. 2019).
5 Conclusion
We propose GraphMaker, a diffusion model capable of generating large attributed graphs, along with a novel evaluation protocol that assesses generation quality by training models on generated graphs and evaluating them on real ones. Overall, GraphMaker achieves better performance compared to basclines, for both existing metries and the newly proposed evaluation protocol. Potential future works include extending GraphMaker for larger graphs with 1M+ nodes, continuous-valin valued node attributes, node labels that indicate node anomalies for anomaly detection, etc.
Broader Impact Statement
The current manuscript primarily focuses on building a model for generating high-quality synthetic graphs. However, for saivacy-preservigg synthetic data sharing, there is likely a privacy-utility trade-off that warrants more thorough investigation in future work. Additionally, the misuse of GraphMaker and the generated synthetic graphs may lead to the spread of misinformation. Therefore, the release of synthetic graph should be accompanied by statement indicating its source.
12

---

Published in Transactions on Machine Learning Research (10/2024)
References
Franklin Allen and Ana Babus. Networks in Finance, chapter 21, pp. 367-382. Wharton School Publishing, 2009.
Martin Arjovsky, Soumith Chintala, and Lóon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference Machine Learning, pp. 214 223, 2017.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Newral Information Processing Systems, pp. 17981-179999 17993, 2021.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint arXiv:1607.04450 2016.
Albert-Lásza Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439): 509-512, 1999.
Albert-Táss1ó Barabási and Réka Albert. Statistical mechanics of complex networks. Rewiews of Modern Physics, 74(47):47-97, 2002.
Alain Barrat, Mare Barthélemy, and Alessandro Vespignani. Dynamical Processes on Compler Networks. Cambridge University Press, 2008.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. NetGAN: Generating graphs via random walks. In Proceedings of the 35th International Conference Machine Learning, pp. 610-619, 2018.
Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. On the power of edge independent graph models. In Advances in Newral Information Processing Systems, pp. 2021.
Tianqi Chen, Weinan Zhang, Qiuxia Lu, Kailong Chen, Zhao Zheng, and Yong Yu. Svdfeature: A toolkit for feature-based collaborative filtering. Journal of Machine Learning Research, 13(16))33619 3622, 2012.
Xiaohui Chen, 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.
Fan Chung and Linyuan Lu. The average distances in random graphs with given expected degree. Proceedings of the National Academy of Sciences of the United States of America, 99(25):15879 15882, 2002.
Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Araual ACM
Symposium on Theory of Compuling, pp. 151 151-158, 1971.
Nicola De Cao and Thomas Kipf. MolGAN: An implicit generative model for small molecular graphs. ICML workshop on Theoretical Foundations and Applications of Deep Generative Models, 2018.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Grophs: Methods and Applications, 2021.
Marek Eliás, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the 2020 ACM-SIAN Symposium on Discrete Algorithms (SODA), pp. 560-578, 2020.
Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In International Conference on Machine Learning, pp. 2023.
Paul Erdös and Alfréd Rényi. On random graphs Publicationes Mathematicne (Debrecen), 6:290-200 297, 1959.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Represeniations (ICLR), 2019.
Scott A. Golder, Dennis M. Wilkinson, and Bernardo A. Huberman. Rhythms of social interaction: Mes- saging within massive online network. In Communitiies and Technologies 2007, pp. 41 66, 2007.
Jonathan Ho, Ajay Jain, and Picter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, pp. 6840 6851, 2020.
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps.
Social Networks, 5(2):109- 137, 1983.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, pp. 22118 22133, 2020.
Kevin Jarrett, Koray Kavukeuoglu, Marc' Aurelio Ranzato, and Yann LeCun. What is the best multi-stage architecture for object recognition? pp. 2146 2153,113311000 2009.
In 2009 IEEE 12th International Conference on Compuler Vision,
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of the 35th International Conference on Machine Learning, pp. 2323 2332, 2018.
Jachyeong Jo, Seul Lee, and Sung Ju Hwang, Score-based generative modeling of graphs via the system of stochastic differential equations. In Proceedings of the 39th International Conference on Machine Learning, pp. 10362 10383, 2022.
Zach Jorgensen, Ting Yu, and Graham Cormode. Publishing attributed social graphs with formal privacy guarantees. In ACM SIGMOD International Conference Management of Dala (SIGMOD), pp. 107 122, 2016.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations (ICLR), 2014.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. NewrIPS Workshop on Bayesian Deep Learning, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Represenlations (ICLR), 2017.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang, Autoregres- sive diffusion model for graph generation. In Proceedings of the 40th International Conference on Machine Learning, pp. 17391 17408, 2023.
Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kro- necker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11(3))9985 1042, 2010.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXio preprint NXN::180300392) 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Aduances in Newral Information Processing Systems, 2019.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the Twelfth International Conference on Information and Knowledge Management, pp. 556 556-559, 2003.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Advances in Newral Information Processing Systems, pp. 20887 20902, 2021.
Qi Liu, Miltiadis Allamanis, Marc Brockschmidt, and Alexander L. Gaunt. Constrained graph variational autoencoders for molecule design. Advances in Newral Information Processing Systems, 2018.
J.L. Myers, A. Well, and R.F. Lorch. Research Design and Statistical Analysis. Routledge, 2010.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. Tn Proceedings of the 38th International Conference on Machine Learning, pp. 8162-8171, 2021.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modcling. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Stalislics, pp.
2020.
John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. In Proceedings of the 28th A ACM SIGKDD Conference on Knowledge Discovery and Dala Mining, pp.
2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjic Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advonces in Newral Information Processing Systems, pp. 8024 8035, 2019.
Joseph J. Pfeiffer, Timothy La Fond, Sebastian Moreno, and Jennifer Neville. Fast generation of large scale social networks while incorporating transitive closures. In 2012 International Conference on Privacy, Securily, Risk and Trust and 2012 International Confernece on Social Compuling, pp. 154 165, 2012.
Joseph J. Pfeiffer, Sebastian Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher. Attributed graph models: Modeling network structure with correlated attributes. In Proceedings of the 23rd interna- tional conference on World wide web, pp. 831-843 2014.
Suman Ravuri and Oriol Vinyals. Classification accuracy score for conditional generative models. In Advances in Neurol Information Processing Systems, 2019.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In Proceedings of the 31st International Conference on Machine Learning, pp. 1278-1286, 2014.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp- 10684-10695, 2022.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Ratt Collec- tive classification network data. AT Magazine, 29(3):33, 2008.
Comandur Seshadhri, Tamara G Kolda, and Ali Pinar. Community structure and scale-free collections of crdös-rényi graphs. Physical Review E, 856))0056109 2012.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. NeurIPS Workshop on Relational Representation Learning, 2018.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequllbbruu thermodynamics. In Proceedings of the 32nd International Conference Machine Learning, pp. 2256-22222 2265, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, 2019.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting, Journal of Machine Learning Research, 15(56):
1929 1958, 2014.
Clement Vignac, Igor Krawezuk, Antoine Sirandin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In International Conference on Learning Rep- resentations, 2023.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.0133 01311, 2019.
Duncan J. Walts and Sleven H. Strogatz. Collective dynamics of 'soall-world' networks. Nature, 393: 440-442, 1998.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 6861-6871, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th Interna- tional Conference on Machine Learning, pp. 1453-5462, 2018.
Minji Yoon, Yue Wu, John Palowitch, Bryan Perozzi, and Russ Salakhutdinov. Graph generative model for benchmarking graph neural networks. In Proceedings of the 40th International Conference on Machine Learning, pp. 40175-40198, 2023.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovee. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in Neurol Information Processing Systems, 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning, pp. 5708 5717, 2018b.
A Appendix
A.1 Dataset statistics
Table presents the detailed dataset statistics.
Table 6: Dataset statistics. For [8), we add reverse edges and then remove duplicate edges.
Dataset
|
[3]
# labels
# attributes
Cora
2, 708
10,556
7
1, 1,433
Amazon Photo
7, 7,6
238, 163
8
745
Amazon Computer
13, 752
491, 722
10
767
A.2 Details for baseline experiments
For a fair comparison, we augment the input of fcature-based MF, GAE, and VGAE to include node attributes and label. During generation, we first sample node attributes and node label, and then pass them along with empty graph with self-loops only for link prediction.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Table 7: Evaluation with MLP. Best results are in bold. Highest results are underlined.
Model
Cora
Amazon Photo
Amazon Computer
PYY) IL. P p P II. PIX,
0.57 = 0.02
0.20 = 0.08
0.16 = 0.07
1.10 + 0.04
0.97 + 0.04
0.97 + 0.02
GraphhMker-Sym (conditional)
1.00 + 0.04
0.97 + 0.01
0.90 + 0.01
GraphhMake-Asyyne (conditional)
1.03 + 0.04
1.05 + 0.01
1.00 + 0.05
Table 8: Performance of discriminative models trained and evaluated on the original graph.
Node Classification (ACC)
Link Prediction (AUC)
Dataset
MLP
1-SGC
L-SGC
L-GCN
1-APPNP
L-APPNP
CN
1-GAE
L-GAE
Cora
0.546
0.764
0.786
0.807
0.780
0.810
0.707
0.930
0.925
Amazon Photo
0.699
0.619
0.638
0.895
0.900
0.913
0.934
0.952
0.958
Amazon Computer
0.615
0.554
0.542
0.780
0.793
0.774
0.925
0.942
0.911
For EDGE, we adopt the hyperparameters it used for generating the structure of Cora. The original EDGE paper generates molecules by first sampling atom types and then generating a graph structure conditioned on the sampled atom types. We extend for generating a large attributed graph by first generating node attributes and label and then generating the graph structure conditioned on them. To generate attributes and label, we use the attribute generation component in the unconditional GraphMaker-Asyıc..
For GDSS, we adopt the hyperparameters provided in the open source codebase and the S4 integrator proposed in the original paper to simulate the system of reversc-time SDEs. As GDSS directly denoises the dense adjacency matrices, it needs to decide edge existence based on threshold to obtain the final graph structure. We choose a threshold so that the number of generated edges is the same as the number of edges in the original graph.
A.3 Additional details for evaluation with discriminative models
To evaluate the quality of the generated attributes, we train one MLP on the real training node attributes and label, and another ML.P on the generated training node attributes and label. We then evaluate the two models on the real test node attributes and label to obtain two performance metrics ACC(G)G) and ACC( If the ratio ACC(G/C)AACC(GR having a utility similar the original data for training the particular model.
is close to one, then the generated data considered as
For all evaluation conducted in this paper with discriminative models, we design hyperparameter space specific to each discriminative model, and implement a simple AutoML pipeline to exhaustively search through a hyperparameter space for the best trained model.
Table 7 presents the results for node classification with MLP. The conditional empirical distribution p( ( II, p(X..,/YY consistently outperforms the unconditional variant p II,
Table details the performance of the discriminative models trained and evaluated on the original graph.
A.4 Evaluation for diversity and novelty
To study the diversity of the graphs generated by GraphMaker, we generate 50 graphs with each conditional GraphMaker variant and make histogram plots of metrics based on them. For structure diversity, we report W, for node degree distribution. For node attribute and label diversity, we train an MLP on the original graph and report its accuracy on generated graphs. Figure D presents the histogram plots for Cora, which demonstrates that GraphMaker is capable of generating diverse and hence novel graphs.
17

---

Published in Transactions on Machine Learning Research (10/2024)
GraphMaker-Sync
GraphMaker-Async
10
10
Degree W1
5
5
0
0
0.6
0.8
1.25
1.50
1.75
15
15
10
10
MLP
Accuracy
5
5
0
0
0.550
0.575
0.575
0.600
Figure 2: Histogram plots metrics, which demonstrate the diversity of the generated graphs.
Table 9: Evaluation for structural properties. Best results are in bold.
Cora
Model
W1 1
Ed
MCC//MG)
Degree (x 10
Cluster (x10)
Orbit
#
Triangle
Ñ(A, Y)
M(A?, Y)
0.001 0.000
2.4
164
0.0066 0.0002
0.0068 0.0018
0.092 0.003
FMF
1.3 + 0.0
2.0
166
0.0063 0.0025
0.11 4: 0.00
0::0
GAE
1.3 + 0.0
2.0
1.6
0.0071 +: 0.0018
0.11 -: 0,00
0:0
VGAE
1.4 + 0.0
2.4
1.6
0.0060 0.0019
0.10 11000.00 0.00
0
GDSS
0.00089 + 0.00001
2.0
1.5 0.0
0.0076 + 0.0020
0.013 + 0.003
0.084 +: 0.006
EDGE
0.00058 0.00002
1.7
0.27 + 0.05
0.32 + 0.02
0.82 0.08
0.77 0.09
G
0.0011 + 0.0001
2.4
1.7 0.0
0.0037 + 0.0019
0.072 - 0.008
0.20 + 0.01
A
0.0016 + 0.0001
1.5
0.56 + 0.00
0.82 + 0.06
0.86 - 0.02
0.75
GMaker-S (cond.)
0.00061 0.00006
0.0
1.4
0.059 0.014
0.91 0.02
0.94 0.04
GMaker-A A (cond.)
0.0015 + 0.0002
0.90 + 0.09
0.77 + 0.18
1.5 + 0.1
1.1 +.0
1.2 1.2+0.0
A.5
Evaluation for structural properties on Cora
See Table g
A.6 Review on classic graph generative models
ER (Erdss & Rényi 1959) generates graph structures with a desired number of nodes and average node degree. SBM (Holland et al. 1983) produces graph structures with a categorical cluster label per node that moet target inter-cluster and intra-cluster odge densitics. BA (Barabási Albert 2002) generates graph
structures whose node degree distribution follows power law. Chung-Lu (Chung Lu 2002) generates graphs with node degree distribution that equals to pre-specified node degree distribution in expecta-
18

---

Published in Transactions on Machine Learning Research (10/2024)
Table 10: Hyperparameters for GraphMaker--Snn.
Hyperparameter
Cora
Amazon Photo
Amazon Computer
Node attribute prediction
Hidden size for time step representations
32
16
16
Hidden for node representations
512
512
512
Hidden size for node label representations Number of MPNN layers Learning rate Optimizer
64
64
64
2
2
2
0.001
0.001
0.001
AMSGrad
AMSGrad
AMSGrad
Link prediction
Ilidden size for time step representations
32
16
16
Hidden size for node representations
512
512
512
Hidden size for node label representations
64
64
64
Hidden size for edge representations
128
128
128
Number MPNN layers Learning rate
2
0.0003
0.0003
0.0003
Optimizer Batch size
AMSGrad
AMSGrad 524288
AMSGrad
16384
2097152
Others
Number of diffusion steps
3
3
Patience early stop
15
15
Maximal gradient norm for clipping
10
10
10
tion. Kronecker graph model [eskovee et al. Kronecker product.
2010) generates realistic graphs recursively by iterating the
A.7
Implementation details
We implement work based on PyTorch Paszke et al. 2019 and DGL (Wang et al. 2019
A.8
Hyperparameters
We perform carly stop when the evidence lower bound (ELBO) stops getting improved for pro-specified number of consecutive evaluations (palience). Table 10 lists the hyperparameters for GraphMaker-Syne..
Table 11
lists the hyperparameters for GraphMaker-Asyne.
19

---

Published in Transactions on Machine Learning Research (10/2024)
Table 11: Hyperparameters for GraphMakee-Async.
Hyperparameter
Cora
Amazon Photo
Amazon Computer
Node attribute prediction
Hidden size for time step representations
16
16
Hidden size for node representations
512
512
1024
Hidden size for node label representations Number linear layers Dropout
64
64
64
0.1
0
0
Number of diffusion steps Learning
6
7
0.001
0.001
0.001
Optimizer
AMSGrad
AMSGrad
AMSGrad
Link prediction
Hiddon for time stop representations
16
Hidden size for node representations
512
512
512
Hidden size for node label representations
64
64
64
Hidden size for edge representations
128
128
128
Number MPNN layers
2
2
Dropout
0.1
0
0
Number of diffusion steps
9
9
Learning rate
0.0003
0.0003
0.0003
Optimizer
MSGrad
AMSGrad
A AMSGrad
Batch size
16384
262144
2097152
Others
Patience for early stop
20
15
15
Maximal gradient norm for clipping
10
10
10
20


Reviews:
[{"review_id": "EYjbDzyKS1", "reviewer": "Reviewer_J2L9", "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:\n\n+++ scaling to 13k nodes on a non-autoregressive diffusion model is a great achievement\n\n+++ the ablation study of training on a single graph is very interesting to observe\n\n++ strong results in the studied metrics\n\n### Weaknesses:\n\n--- architecture and training not described in enough detail to reproduce (what is the decoding method involving MLP for the edges? what are the subsampling ratios during training? etc.)\n\n-- limited novelty: the method is basically DiGress with an MPNN and randomized subsets for edge predictions during training\n\n-- no clear definition of what \"large\" means, no evaluation on a \"small\" attributed graph (e.g. Guacamol) that would allow to compare the work directly to prior work or comparison to follow-ups to DiGress like SparseDiff which can scale to larger graphs\n\n-- maybe I missed it, but I could not find note of number of seeds used to evaluate, there are no error bars or other attempts to evaluate uncertainty in the evaluation", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 presents GraphMaker, a graph diffusion model following the D3PM framework, centered around a MPNN architecture producing node embeddings from which node attributes and edges are predicted, with training made sub-quadratic by predicting only random subsets of edges at a time. \n\nThe authors evaluate this framework on Cora, Amazon Computer and Amazon Photo, comparing against GDSS, EDGE, (V)GAE and non-deep learning Erdős-Rényi and feature-based matrix factorization, and in particular explores training a generative model on a single graph by using the synthetic distribution to train node classifiers. They report competitive performance on most datasets and tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical:\n\n0. Add _a lot_ more detail about training setup, evaluation setup, hyperparameters etc. to the appendix or main body to make the results reproducible\n\n1. Include at least one evaluation on e.g. Guacamol or another dataset that EDGE, DiGress etc. were evaluated on to contextualize both your edge implementation and how your network performs on these smaller tasks\n\n2. Perform statistical evaluation on the significance of the differences observed by training multiple seeds with different data subsets/graphs and performing a suitable statistical significance test (e.g. https://en.wikipedia.org/wiki/Welch%27s_t-test). If this is not computationally feasible, at least include analysis on how many would be required and report it (for future reproducibility studies) and come up with a proxy experiment to perform qualitatively\n\n### Nice to haves:\n\n1. Acknowledging that the diffusion model is basically DiGress with an MPNN and subsampling would be nice, but not critical\n\n2. The classification metric $ACC(G|\\hat{G})$ is highly reminiscent of https://proceedings.neurips.cc/paper/2019/hash/fcf55a303b71b84d326fb1d06e332a26-Abstract.html which should be mentioned in the related work\n\n3. NetGAN https://arxiv.org/abs/1803.00816 and many early graph generative models trained on only a single network, this should be discussed", "broader_impact_concerns": "I think the statement is suitable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KmWfnNjmKi", "reviewer": "Reviewer_pXm7", "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:\n- Proposed GraphMaker can generate edges, node attributes, and node labels more accurately than current approaches.\n- Increases scalability of diffusion models for graph generation by one order of magnitude.\n- Well thought out evaluation procedure, considering both prediction tasks on the real graph data and benchmarking using only synthetic graph data. Additionally, the authors also consider evaluation of graph structures.\n- Presentation and references have a good balance between recent papers on graph neural networks and more classical network science papers.\n\nWeaknesses:\n- Claims the possibility of protecting privacy by generating a synthetic graph, but the synthetic graph could be so close to the actual graph that it doesn't protect privacy at all. See the major issue I describe in Requested Changes.\n- Some minor presentation issues, which I mention in Requested Changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 the GraphMaker diffusion model for generating large attributed graphs. They explore both synchronous (denoising node attributes and edges at all iterations) and asynchronous (first denoise node attributes and then denoise edges) approaches for GraphMaker. The proposed approach scales to 10,000+ nodes, one order of magnitude higher than current diffusion models for graph generation. They perform a comprehensive evaluation that considers multiple different ways of measuring the quality of the generated graph and demonstrate the improvement that GraphMaker provides.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major issues:\n- There is no experiment showing how well the original graph can be recovered from the synthetic graph. I believe that this is an important experiment given the the synthetic graph is generated by starting with the real graph and corrupting it. A graph that is less corrupted should score highly on the current experiment metrics but also have a higher probability of leaking out the original graph itself. This should probably also be discussed in the broader impact statement.\n\nMinor issues:\n- Presentation in some of the tables is confusing, such as the scientific notation used in Tables 3 and 4, as well as some tables in the appendix. I have never seen quantities denoted using notations such as $7.0e^{-3}$, only $7.0 \\times 10^{-3}$ or the compact version 7.0e-3 without exponent. Ideally, the exponents could be taken out of the table entries itself by using a common exponent, described in the table heading. For example, # Triangle ($\\times 10^{-3}$). If the authors insist on using their current notation, then at least explain it in the table caption.\n- Last paragraph of introduction: insert missing word \"of\": 80% of cases and 50% of cases\n- Appendix A.1 is so short that I suggest moving it into the main paper in Section 2.2, where it is referenced. It is not overly complicated and would likely not distract the reader from the main points being discussed.", "broader_impact_concerns": "There is a short broader impact statement that is insufficient. It mentions \"protecting privacy\", but privacy protection is never evaluated at any point in this paper. This relates to the major issue I mention in Requested Changes regarding the possibility of leaking portions of the original graph data, which should also be mentioned in the statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "m80xNltzsM", "reviewer": "Reviewer_6cRc", "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\n\n1.\tGraphMaker adopts an asynchronous approach to generate node attributes and graph structures, which more effectively captures the complex correlations between attributes and structures. Compared to synchronous generation, asynchronous generation performs better at learning and simulating patterns in real-world large property graphs.\n2.\tGraphMaker adopts the strategy of edge mini-batch generation and designs a new information transfer neural network (MPNN) to encode data efficiently, thereby improving the model's ability to process large-scale graphs.\n3.\tThis paper proposes a novel evaluation protocol to evaluate the data utility of generated graphs by training machine learning models on the generated graphs and evaluating their performance on the original graphs. This method allows for a more efficient check of the quality of the generated graphs.\n\n## Weaknesses\n\n1.\tTable 1 shows that the graph generated by the model can be a good substitute for the original graph, so the two have similar effects in downstream tasks. Table 2 also shows that the generated graph correlates very well with the original graph. However, the performance in Table1 and Table2 can only show that the generated graph is very similar to the original graph, and does not clearly show that the generated graph can bring additional benefits to downstream tasks. For example, when the generated graph is used together with the original graph, the model's performance on downstream tasks cannot be compared to the performance of the original graph alone.\n2.\tThe data sets used in the experiment are relatively small. For example, the Cora dataset is a smaller graph dataset that was proposed in 2008. Experiments require a larger-scale Dataset to prove the effectiveness of the work. For example, the OGB dataset proposed in article \" Open Graph Benchmark: Datasets for Machine Learning on Graphs\" can be used to conduct larger-scale experiments to prove the model's effectiveness.", "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 proposes a novel graph generation model GraphMaker. Different from previous graph generation models, GraphMaker mainly focuses on the generation of large attribute graphs. This model is based on the diffusion model and asynchronous generation method to generate large attribute graphs, and introduces a new evaluation method to prove the effectiveness of the generated graphs. This provides ideas for future researchers to explore larger graph generation tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As pointed out in the weaknesses part, the authors should use more realistic and challenging datasets.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers' feedback is leaning towards accepting this submission. However, the reviewers requested that the proposed changes (such as the added experiments discussed during the rebuttal phase)  will be added to the paper for it to be accepted. 

Therefore, I ask the authors to add these to the final paper as a minor revision.
Decision: Accept (poster)