Random Walk Diffusion for Efficient Large-Scale Graph Generation
Authors: Tobias Bernecker
Ghalia Rehawi
Francesco Paolo Casale
Janine Knauer-Arloth
Annalisa Marsico
Venue: Accepted by TMLR ()

Abstract: Graph generation addresses the problem of generating new graphs that have a data distribution similar to real-world graphs. While previous diffusion-based graph generation methods have shown promising results, they often struggle to scale to large graphs. In this work, we propose ARROW-Diff (AutoRegressive RandOm Walk Diffusion), a novel random walk-based diffusion approach for efficient large-scale graph generation. Our method encompasses two components in an iterative process of random walk sampling and graph pruning. We demonstrate that ARROW-Diff can scale to large graphs efficiently, surpassing other baseline methods in terms of both generation time and multiple graph statistics, reflecting the high quality of the generated graphs.

Published in Transactions on Machine Learning Research (03/2025)
Random Walk Diffusion for Efficient Large-Scale Graph Generation
Tobias Bernecker*
Computational Health Center, Helmholtz Mumich School of Computation, Information and Technology, Technical University of Munich
Ghalia Rchawi"
Computational Health Center, Helmholtz Munich Max Planck Institute of Psychiatry, Munich School of Life Sciences, Technical University of Munich
Francesco Paolo Casale
francescopaolo.cose casale cossdeeehhmmoobttmmmmndd.
Computational Health Center, Helmholtz Munich
Helmholtz Pioncer Campus, Helmholtz Munich. School of Computation, Information and Technology, Technicol University of Munich
Janine Enauer-Arloth
arlothh@psgch.mmp.
Max Planck Institute of Psychiatry, Munich Computational Health Center, Helmholtz Mumich
Annalisa Marsico
canalie..nariooiieenbttttmmmmm..
Computational Health Center, Helmholtz Munich
Reviewed on OpenReview: https: // optpr/vveerr.ve....mmmo net/ form?? id= dus--Spsshhddd/nnoooddddddd--02-
Abstract
Graph generation addresses the problem of generating new graphs that have data distribu- tion similar to real-world graphs. While previous diffusion-based graph generation methods have shown promising results, they often struggle to scale to large graphs. this work, we propose ARROW-Diff RAgrsRegressive RandOm Walk Diffusion), a novel random walk- based diffusion approach for efficient large-scale graph generation. Our method encompasses two components in iterative process of random walk sampling and graph pruning. We demonstrate that ARROW-Diff can scale to large graphs efficiently, surpassing other base- line methods in terms of both generation time and multiple graph statistics, reflecting the high quality of the generated graphs.
1 Introduction
Graph generation addresses the problem of generating graph structures with specific properties similar real-world ones, with applications ranging from modeling social interactions to constructing knowledge graphs, well designing new molecular structures. For example, an emerging task in drug discovery is to generate molecules with high drug-like properties. Traditional methods for graph generation focused
generating graphs with predefined characteristic (Frdös et. al. 1960 Barabási & Albert] 1999). Due to their hand-crafted nature, these methods fail to capture other graph properties, e.g., the graphs generated by Barabási & Albert (1999) are designed to capture the scale-free lopology but fail to capture communily structures of real-world graphs.
'Equal contribution.

---

Published in Transactions on Machine Learning Research (03/2025)
Recently, deep learning- Ceanning-based approaches have gained attention for overcoming the limitations of traditional graph generation methods by learning the complex topology of real-world graphs. These approaches typically involve an encoder that learns a dense representation of the graph, a sampler that generates samples from this representation, and a decoder which restores the sampled representation into a graph structure (Zhu et al. 2022). , Different decoding strategies have been proposed, including sequential decoders that generate the graph step-by-step (You et al.] 20188 Liao et al. 2019), and one-shot generators that can create the entire graph in single step (Kipf & Welling, 2016b Simonovsky & Komodakis 2018 Grover al. 2019).
While sequential decoders struggle to model long-toc dependencies and require node-ordering process, one-shot generators suffer from scalability issues and compromised quality due to the independent treatment of edges ( Chanpuriya et al. 2021), making these methods suboptimal for large-scale graph generation Guo
& Zhao 2022).
An even more recent body of work in graph generation are diffusion-based probabilistic models, inspired by non-equiibrrimm thermodynamics and first introducod by Dicl-Dicksteen et al. (2015). Bricfly, diffusion models consist. of two processes: A forward diffusion process which gradually corrupts input data until it reaches pure noise, and reverse diffusion process which learns the generative mechanism of the original input data using a neural network. biffusion-based methods for graph generation can be divided into two main categories. The first one includes methods that implement diffusion in the continuous space e.g., by adding Gaussian noise to the node features and graph adjacency matrix (Niu et al. 2020 Jo et al., 2022p. This form of diffusson however makes it difficult to capture the underlying structure of graphs since it destroys their sparsity pattern (Vignac et al.] 2023). The second category includes methods that are based on diffusion in the discrete space (Haefeli et al.. 2022; Vignac et al. 2023 Chen et al. 2023) by performing successive graph modifications e.g.; adding or deleting edges/nodess
edge/node features. Diffusion-based graph generation methods do not sulfer from long-term memory dependency which makes them advantageous over autoregressive (sequential) methods. However, many approaches found in the literature are only designed for small graphs (Niu et al.) 2020 Jo et al., 2022 Vignac et al.] 2023). One of the recent diffusion-based graph generation approaches is EDGE (Chen et al. 2023), which uses a combination of a discrete diffusion model and a Graph Neural Network (GNN). EDGE scales to large graphs (up to ~4k nodes and ~38k edges), however, the number of required diffusion steps and hence graph generation time increases linearly with the number of edges in the graph.
To address the existing gaps in this field, we introduce ARROW-Diff (AutoRegressive RandOm Walk Dif- fusion), a novel iterative procedure designed for efficient, high-quality, and large-scale graph generation. To the best of our knowledge, ARROW-Diff is the first method to perform (discrete) diffusion on the level of random walks within a graph. Our method overcomes many limitations of existing graph generation ap- proaches, including scalability issues, the independent treatment of edges, the need for post-processing, and the high computational complexity resulting from operations performed directly on the adjacency matrix. ARROW-Diff integrates two components: (1) A discrete diffusion model based the order-agnostic au- toregressive diffussio framework (OA-ARDM) (Hoogeboom et al. 2022) applied on random walks sampled from a rcal-world input graph, and (2) a GNN trained to predict the validity of the proposed edges in the generated random walks from component. (1). The random walk-based diffusion in component. (1) enables ARROW-Diff to capture the complex and sparse structure of graphs (Perozzi et al. 2014 Grover & Leskoved 2016 Bojchevski et al., 2018), avoid any dense computation, and scale to large graphs, since the required number of dillusion steps is only equal to the random walk length. Moreover, due to the autoregressive na- ture of the implemented diffusion framework (OA-ARDM), ARROW-Diff overcomes the edge-independencee limitation of methods like VGAE (Kipf & Welling, 2016b) and NetGAN (Bojchevski et al. 20188). On the other hand, the GNN in component (2) enables ARROW-Dif to select highly probable edges based on the topological structure learned from the original graph. It also helps to overcome the need for post-processing as in NetGAN (Bojchevski et al., 2018). ARROW-Diff builds the final graph by integrating the two com- ponents in an iterative process. This process is further guided by node degrees inspired by EDGE (Chen) et al., 2023) to generate graphs with a similar degree distribution to the original graph. Using this iterative approach, show that ARROW-Dif demonstrates superior or comparable performance to other baselines multiple graph statistics. Furthermore, ARROW-Dit is able to efficiently generate large graphs (in this
work, up to 20k nodes and ~60k edges), such as the citation networks from McCallum et al. (0000 Sen
2

---

Published in Transactions on Machine Learning Research (03/2025)
et al. 2008); Pan et al. 2016). with significantly reduced (down to almost 50%) generation time compared
to other baselines.
2 Related Work
In the following, we provide an overview of the different classes of graph generation models and identify their strengths, as well as their limitations.
One-Shot Graph Generation Models These methods include graph generation approaches based on
the Variational Autocncoder (VAE) (Kingma & Welling 2013) model, like VGAE (Kipf & Welling 2016b), GraphVAE (Simonovsky & Komodakis, 2018) and Graphite (Grover et al., 2019). which embed a graph G into continuous latent representation 2 using encoder defined by a variational posterior (s(2]G), and generative decoder p=(G))) These models are trained by minimizing the upper bound on the negative log- ligllikel [= log pe GG xx] + (=])( [[]]]] (Kingma & Welling 2013). However, due to their run time complexity of ((N)), VAF-based graph generation approaches are unable to scale to large graphs.
Sequential Graph Generation Models One of the most scalable non-diffusion and sequential graph generation methods is NetGAN (Bojchevski et al., 2018). which is based on the concept of Generative Adversarial Networks (GANs) [Goodfellow et al.) 2014]. Specifically, it uses Long Short-Term Memory (LSTM) (Hochreiter & Schmidhuber 1997) network to generate random walks. After training, the generated random walks are used to construct a score matrix from which the edges of the generated graph are sampled. The aforementioned approach generates edges in an independent manner, sacrificing the quality of the generated graphs and limiting their ability to reproduce some statistics of the original graphs such as triangle counts and clustering cocfficient (Chanpuriya et al. 2021). In contrast, ARROW- Diff overcomes this problem by directly using the edges generated by an autoregressive diffusion process on the level of random walks. Other edge-depeudeent sequential approaches include GraphRNN (You et al., 2018). GRAN (Liao et al, 2019), and BiGG (Dai et al. 2020). These methods iteratively generate the entrics of a graph adjacency matrix one entry or one block of entries at a time. To overcome the long-term boutlneck issue of Recurrent Neural Networks (RNNs), Liao et al. (2019) propose to use a GNN architecture instead of an RNN, which utilizes the already generated graph structure to generate the next block, allowing it to model complex dependencies between each generation step. To satisfy the permutation invariance property of graphs, these methods require node ordering scheme. Moreover, GRAN and GraphRNN are only able to scale to graphs of up to 5k nodes.
Discrete Diffusion-Based Graph Generation Models To exploit the sparsity property of graphs, discrete diffusion-based graph generation models focus on diffusion in the discrete space, i.e., on the level
of the adjacency matrix (Haefeli al., 2022 Vignac et al. 2023). Although these approaches generate high-quality graphs (Niu et al.) 2020: Jo et al.
2022) and overcome the limitation of autoregressive models, they are restricted to small graph generation, like chemical molecules, because they perform predictions for
every pair of nodes. Recently, KKng et al. 2023) developed GraphARM, an autoregressive graph generation approach based on diffusion in the node space. GraphARM demonstrates faster sampling time, since the number of diffusion steps required equals the number of nodes. Our method, however, requires only a number of diffusion steps equal to the random walk length, making it far more scalable than GraphARM. Aside from the method proposed in this work, the only diffusion-based approach able to scale to large graphs is EDGE (Chen et al., (002).. The forward diffusson process of EDGE is defined by successive edge removal until an empty graph is obtained. In the reverse diffusion process, only fraction of edges are predicted between active nodes for which the degree changes during the forward diffusion process. This method generates graphs with a similar degree distribution to the original graph and has decreased run time of OT (M, K2)), where M is the number of edges in a graph and K is the nunber of active nodes. In this work, we introduce a random walk- based discrete diffusion approach to efficiently generate random walks as a first step for graph generation. The random walk- diffusion process implemented through the OA-ARDM (Hoogeboom et al., (202)) framework enables more efficient sampling than in other discrete diffusion models, with significantly reduced number of diffusion steps equal only to the random walk length.
3

---

Published in Transactions on Machine Learning Research (03/2025)
Additionally, GNN component validates edges from the sampled random walks, enabling us to refine the generated graph and produce graphs of high quality.
3 Method
In this section, we introduce ARROW-DifT, an iterative procedure for efficient large-scale graph generation. We designed ARROW-Diff a way to overcome the critical limitations of previous graph generation ap- proaches and to enable it to scale to large graphs efficienlly, without sacrificing the graph generation quality, Tigure[provies provides an overview of ARROW-DifF which leverages two models that are trained independently of each other training set of edges from the original graph: (1) A random walk-based diffusson model based the OA-ARDM (Hoogeboom et al. 2022 framework trained to generate random walks from the original graph. This involves first sampling of random walks and then masking nodes in the forward diffusion process, with the model predicting the original nodes in the reverse diffusion process. (2) A GNN trained to capture the topology of the original graph. Our proposed method, ARROW-Diff, incorporates these two components in an iterative process which (1) the diffusion model generates random walks, proposing potential edges, and (2) the GNN evaluates and filters the edges proposed by the OA-ARDM based on learned topological features. This process is further guided by changes in the node degrees generate the final graph. In the following, we provide background information the OA-ARDM and its adaptation for random walk-basod diffusion, followed by detailed description of ARROW-DifT.
Initial Graph G ((I,... 6).09
Sample Start Nodes and Repeat
Start Nodes (1, ..,, 6)
Dittusion Model
Sampled Edges
Generated Random Walks
Edge Proposals
Edge Probabilities
Generated Graph
After Last Iteration
GNN
Figure 1: Overview of ARROW-Diff graph generation (inference) using a trained OA-ARDM (Hogeeboo ct al. 2022 and a trained GNN. Iterativcly, and starting from an empty graph, a diffusson model samples random walks from a set start nodes. Then, a GNN classifies the proposed edges and filters out invalid ones. This procedure is repeated L times using a different set of sampled start nodes guided by the change of node degrees with respect to the original graph.
Background: Order Agnostic Autoregressive Diffusion Models Recent works show that diffusion models are applicable to discrete data (Scks-Dickstein et al. 2015 Hoogeboom et al. 2021 Austin et al. 2021 Hoogeboom al. p022p. The diffusion process of these models based on the Categorical distribution over input features of a data point, instead of the Gaussian distribution. Initially, discrete diffusion models used uniform noise to corrupt the input in the forward diffusion process (Sohl-Dickstein et al. 2015 Hoogeboom

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm Optimizing Random Walk OA-ARDMs
1: Input: A random walk a E VD, the number of nodes N = [V], and a network f.
2: Output: ELBO L.
3: Sample ~ U(1,...:D)
Sample ((DD)
Compule m < (o < <1)
Compute i 4- m ② x + (1 m) o ((N + 1)-111 1b)
7: I + (1 m) o log ((x)
8: Li + D- slm(l)
9: t D.
ct al., 2021): Later, Austin et al. 2021 extended this process and introduced a general framework for discrete dillusion (D3PM) based on Markov transition matrices [Q:]k q(ar, = j|=;,1 = i) for categorical random variables Tt-1,4; E {1. 2, ................................ K}. One possible realization of the D3PM framework is the so-called absorbing state diffusion (Austin ct al. 2021 that uses transition matricos with an additional absorbing state to stochastically mask entries of dala points in each forward diffusion step. Recently, Hoogeboom el al. (2022)
introduced the concept of OA-ARDMs combining order-agnostic autoregressive models (Uria et al. 2014) and
absorbing state diffusion. Unlike standard autoregressive models, order-agnostic autoregressive models are able to capture dependencies in the input regardless of their temporal order. Let x be D-dimensional data point. An order-agnostic autoregressive model can generate æ a random order that follows a permutation Sp, where SD denotes the set of possible permutations of (1. D}. Specifically, their log- lieliiil can be written as
logp(x) 2 E. Eg- E log [logp(Foco)
(1)
where Fo((t) = (1) < (1.... D}} represents all elements of x for which (1) is less than (Hooge- boom et al. 2022). In the following, we explain the proposed random walk-based autoregressive diffusion in more detail.
Random Walk Diffusion Consider graph G EV, with N = [ nodes. We aim to learn the (unknown) generalive process p(G) of G. Inspired by Walp (Perozzi et al. 2014p, node2vec (Grover & Leskovee 2016), and by the random walk-based graph generation approach introduced by BBocchvski et al. (0118), we suggest to sample random walks from a trained diffuusion model and use the edges comprising the walks as proposals for generating a new graph. To achieve this, we train an OA-ARDM (Hoogeboom et al. 2022) by viewing each node a random walk as a word a sentence, and follow the proposed training procedure of Hoogeboom et al. (2022) for OA-ARDMs on sequence data (Algorithm D For a random walk w E yD of length D, we start by sampling time step L i~ UI,...., D) and random ordering of the nodes in the walk, a Z((D)), both from a uniform distribution. For each time step of the diffusion process, BERT-like (Devlin et al.) 2018) training is performed, in which D - t + nodes (words) are masked and then predicted by a neural network. Specifically, the OA-ARDM is trained by maximizing the following likeliioddood component at each time step t (Hoggeboom et al. 2022
E ((SD) L = D -+1
1
Σ
logp(r4/2a1e0))
(2)
kEO(21)
In the case of diffusion on random walks, masking of nodes equivalent to setting them to an absorbing state represented by additional class N (Hoogeboom et al. 2022). Thus, as suggested by Hoogeboom et al. (2022), the inputs to the network are (1) the masked random walk i @ x + (1 m) a, where = a < f is a Boolcan mask, a (N + 1) 1p and 1p is D-dimensional vector of ones, and (2) the sampled lime step I. During the training of the OA-ARDM, the random walks are sampled from the original graph.
ARROW-Diff Graph Generation Our proposed graph generation method, ARROW-Diff, is outlined in Al Algorithm 2 ARROW-Diff generates graphs similar to a single, given original graph G (V, F) through
5

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 2 ARROW-Diff Graph Generation
Input: A trained OA-ARDM, trained GNN. The node set V, features X and degrees de of an original graph G with the same node ordering as for training the OA-ARDM. The number of steps L to generate the graph.
2: Output: A generated graph G = (V, (V,F). F).
3: Start with an empty graph G = (V, E), where É = 0
4: Set the initial start nodes Vatart to all nodes in the graph: Vstart V do Sample one random walk for each start node Vstart using the OA-ARDM: R Compute edge proposals from R:
for 1= 1
pproposals == {m,, n2y) R|n,, n2 E Vi
Run the GNN on G (V, U Eproposale: X) to obtain probabilities for all edges in É U Eproposals Sample valid edges Evalid from É Epropeeals according to the edge probabilities
9:
Edge update: É t Evalid
10:
11:
if < then
Compute the node degrees dø of & based on E
12:
13:
Compute d == max(0, -
14:
Compute probability for each node n E V: p(n) max
de
15:
Sample start nodes Vstart from V according to p(n) using Bernoulli distribution
16:
end if
17:
end for
an iterative procedure iterations: It starts with an empty graph G = EV, 0), which contains the same set nodes V as the original graph but no edges. To add edges to G. ARROW-Dif initially samples one random walk for every node in V and considers all edges these random walks as edge proposals Éproposals for & (lines 6 and 7 in Algorithm 2 Next, and similar to the work of Liao et al. (219)), we sample valid edges from the proposed ones Eproposals using a Bernoulli distribution based on the binary edge classification probabilities. These probabilitics are calculated by taking the sigmoid of the dot-product of node embeddings (for node-pairs inside Ê U Fiproposals) predicted by the GNN component 8). This GNN model is trained on perturbed version of training set of edges from the original graph G to perform edge classification. Specifically, the training set of edges is corrupted by deleting edges and inserting invalid (fake) edges. Inspired by the degree- degree-guided graph generation process of Chen et al. (2023). we now sample nodes from V using a Bernoulli distribution by considering each node n E V according to a success probability p(n) = max(d]' where d = max(0, de - dg), are the positive differences of node degrees
G (V, f U P X) (line
du
dg and dø from and &. This set of sampled nodes is then used as start nodes for sampling the random walks in the next ileration. Hence, we modily the sampling procedure of (Hogeeboo al. (2022), which originally starts from sequence with only masked tokens, by manually setting the first node of random walk to specific node n E V, i.c.
if 1, mask if k: (2....,D)
n
(3)
Additionally, we use restricted set of permutations Sh = for e Spla(1) = 1}, in which the order of the first. element does change after applying the permutation. To sample the remaining parts 22.D of the random walk æ, we follow the sampling procedure of Hoogeboom et al. (0022) by starting time step t 2 and using o ~ U(())). ARROW-Diff can generate directed and undirected graphs. To generate undirected graphs, we suggest adding all reverse edges {(n,, na)l,,;)) n3) E Epropomals) to the edge proposals Eproposus (line 7), and to sample edges from à U Eproposals in a way to obtain undirected edges in Aralid (line 9).

---

Published in Transactions on Machine Learning Research (03/2025)
4 Experiments and Results
In our experiments, we compare ARROW-Diff to six bascline methods for graph generation that can scale to large graphs. These methods cover the different graph generation techniques which are explained in Section | and Section 2 To evaluate the performance of all methods, we use five different real-world citation graph datasets, each containing a single undirected graph and all considered large graphs with varying numbers of modes/odges We also evaluate the performance of ARROW-Dif in generating more structured and non- scale-free graphs. To this end, we create synthetic Stochastic Block Model (SBM) (Holland et. al., 1983) graph with 360 nodes and 3,824 edges. The results the SBM graph are shown in Appendix Section
4.1
Experimental Setup
Datascts To evaluate ARROW-Diff, we use five citation graph datasets: Cora-ML (McCallum et al. 2000
Cora (McCallum et al. 2000), CiteSeer (Giles et al. 1998), DBLP (Pan al. 2016), , and PubMed (Sen al.
2008 For Cora-ML and Cora, we use the pre-processed versions from Bojehevski & Günnemann (0018)
Each of the five datascts contains one single, undirected, large-scale citation graph. Motivated by Bojchevski et al. (2018), we only take the largest connected component (LCC) of Cora-ML, Cora, CiteSeer, and DBLP, which contain multiple connected components. Table T provides an overview of different characteristies for each graph/LCC. Similar to Bojchevski et al. (2018), we split the edges of each graph into training, validation, and test parts, and use only the training odges to train the bascline methods, as well as the OA-ARDM and GNN for ARROW-DifT.
Table 1: Dataset statistics of single, large-scale graph datasets used in this paper: Number of nodes, number of undirected edges, number of node features, and average node degree. star (*) indicates that the stat are reported for the LCC of the respective dataset.
# Node Features
Avg. Degree
Dataset
# Nodes
Edges
CT.
2,810
7,981
2,879
5.7
Cora"
18,800
62,685
8,710
6.7
CiteSeer*
1,681
2,902
602
3.5
DBLP"
16,191
51,913
1,639
6.4
PubMed
19,717
44,324
500
4.5
ARROW-Diff Training In the following, we provide details about the training of the OA-ARDM (Hooge-
boom et al. 2022) and the GNN used ARROW-DifT, which are trained independently. We train the OA-ARDM for random walk diffusion following the work of Hoogeboom et al.] (2022), which is explained Section 3 Specifically, we use a U-Net (Ronneberger et al.) 2015) architecture similar to Ho et al. (2020) with one ResNet block and two levels for the down- and up-sampling processes. Similar to Bojehevski et al.)
(2018) we set the random walk length, which equals the number of diffusion steps, to D = 16 and sample batches of random walks from the training split comprising edges from the original graph. Each node in the random walks, as well as each diffusion time step, is then represented using 64-dinenssinnal learnable embeddings and passed as imput to the U-Net. For the GNN component, we train a two-layer GCN (Kipf & Welling 2016a) to predict the validity of edges based on perturbed versions of the training split of the input graph. Specifically, the GCN is trained by minimizing the binary cross-entropy loss between predicted edge probabilities and the ground truth labels which indicate whether edge in the perturbed graph is valid invalid. The predicted probabilities are computed by taking the sigmoid of the dot-product between pairs of node embeddings. We ensure that the GCN model is well-tuned through: (1) The use of a perturbed version of the original graph for the training of the GCN, and (2) the use of a validation split and early stopping on the validation loss to ensure adequate training. As input to the GCN, we use either the original node fcatures (ARROW-Dit with node fcatures) or positional encodings (Vaswani et al., (017) (ARROW- Diff without node features). The positional encodings are 64-dimensional for Cora-ML and CiteSeer, and 128-dimensional for Cora, DBLP, and PubMed. The GCN uses node embeddings of sizes 100 and 10 in the
7

---

Published in Transactions on Machine Learning Research (03/2025)
hidden and output layer, respectively. The full list of hyper-parammeters for training the OA-ARDMs and the GNN models can be found in our code httpiioyy...roog/ttt.....///rerr
Baseline Methods To compare against ARROW- Diff, we use six different graph generation baseline meth-
ods, which are suitable for large graph generation and can be trained on single-graph datasets: VGAE (Kipf
& Welling 2016b), Graphite (Grover et al. 2019), NetGAN Bojchevski et al. (001)), GraphRNN (You et al. 2018), BiGG (Dai et al.) 2020), and EDGE (Chen et al. 2023 Hence, previously mentioned methods like DiGress (Vignac et al. 2023) and GDSS (Jo et al. 2022). which are suitable for small graph generation, are excluded from our experiments. GraphRNN can scale to graphs with up to 5k nodes (You al. 2018). so we only run it on the Iwo smaller datasets Cora-ML (McCallun et al. 2000) and CiteSeer (Giles al. 1998)
since it is still affordable to train it graphs of such sizes. The recent autoregressive diffusion-based graph generation method GraphARM (Kong et al. 2023) is also excluded due to the absence of a code repository, However, as demonstrated in the complexity analysis in Section 5 ARROW-Dif outperforms GraphARM in terms of runtime. To train the baseline methods, we use the recommended hyper-parameterss from their papers and code. The training et al. 2018) for early stopping on the validation edges from the data split. Some models for EDGE were not showing convergence even after 4 days of training. Hence, for evaluation, we considered the models epochs 2600 (CiteSeer), 5550 (Cora-MI.), 250 (Cora), 450 (DBLP), and 250 (PubMed). Additionally, to fit into GPU memory, decreased the batch size from to 2 to train on the Cora, DBLP, and PubMed datasets. We also decreased the embedding dimension parameter for BiGG from 256 to 128 for PubMed and to 64 for Cora and DBLP, to fit into memory of single GPU. Some of the aforementioned baselines do not incorporate node features in their training, honce, for a fair comparison, we report the performance of ARROW-Dif both with and without the use of original node features. In our case, node features are used for training and inference of the GNN model.
NetGAN is performed using their proposed VAL-criterion (Bojchevski
Evaluation of Generated Graphs We use six different graph metrics evaluate the performance of the trained models. Additionally, we report the edge overlap (EO) between the generated graphs and the original graph/LCC. Specifically, generate 10 graphs per dataset and compute the mean and standard deviation of the metrics to obtain more accurate estimate of the performance and assess robustness.
Average Clustering Coeffictent
Global Clustering Coefficient
0.12
E,000
Degree Assrrativlty
0.34
-018
0.006
19
0.12
0.00
0.10
60044
-021
15
15
Power aa Expenent
Number of "Triangle
1200
Maximum Node Degree
130
2,20
120
1000
2.13
2011
600
Original Graph
Mean
Standard Deviation
Figure 2: The change in different graph evaluation metrics with respect to L. The dotted line reports the value corresponding to the ground truth graph, in this case CiteSeer. For each metric, the mean and standard deviation were computed across generated graphs using [1, iterations for ARROW-Dif.

---

Published in Transactions on Machine Learning Research (03/2025)
4.2 Hyper-parameter Tuning
In the following, we investigate the influence ARROW-Diff generates graph within several iterations L.
of the choice of L, on the performance of ARROW-Diff. In Figure 2 we show how the different graph evaluation metrics change with respect to L on the CiteSeer (Giles et al. 1998) dataset. The increase trend on the average clustering coefficient, number of triangles, and maximum node degree can be explained by the increase in the total number of edges of the generated graph with respect to L (see Figure 3). With increasing L, more edges are addod, which in turn increase the maximum degrees of some nodes as well as the number of triangles. This also explains why e-g. the global clustering coellicient remains mostly constant, since the number of closed and open triangles rise simultancously. We choose I, 10 to generate graphs with ARROW-Diff across all datasets, since this value shows the closest results to the ground truth graph both in terms of number of triangles and power-law exponent. In Figure 3 the strong drop in the number of edges for I. E [1,5] is due to the fact that ARROW-Diff samples one random walk for every node in the graph at L = 1, which results in a high number of edge proposals. With increasing L, these edges will either be selected or dropped from the final generated graph based on the sampling on the probabilities computed by the GNN model.
Original Graph
6300
Mean
Standard Deviation
6000
5000
5000
500
5300
5000
1900
15
20
1.
Figure 3: The mean and standard deviation of the number of edges of 10 graphs generated by ARROW-Dif. using the original node features, are reported for L E [1.. The dotted line represents the number of edges of the original CiteSeer graph.
4.3 Results and Efficiency
In Table 2 we present the results for all baselines and for ARROW-Diff trained both with and without node features on the five datasets (Table 1. The results are reported as the mean across 10 generated graphs. To evaluate the stability of all methods, we also report the standard deviation of all metrics across the 10 generated graphs in Table The results presented in Table 2 indicate that ARROW-Dif achieves notable improvement. across many metrics, surpassing nearly all baselines in terms of triangle counts and power- law exponent (see generated node-degree distribution in Figure 7(a) We observe that EDGE performs the best in terms of maximum node degree across all datasets. This is due to its ability to steer the graph generation process towards a deggree distribution similar to that of the original graph. We would like to highlight that the number of edges in the graphs generated by VGAE (Kipf & Welling, (0166) and Graphite (Grover et al., 2019) was extremely high. Thus, we consider only edges for which the predicted probability P(A; 1|, 2,) a( 2,) > 0.95 for nodes i,j V. Even with this constraint, the graphs generated by VGAE had over 50M edges the Cora, DBLP, and PubMed datasets, which led to exhaustive metric computation. Therefore, we have omitted the results for these datasots from Table 2 The scalability of ARROW-DilT is demonstrated in the substantial decrease in graph generation time (down lo more than 50% compared to all baselines). This remains true even when generating very large graphs such as Cora, DBLP, and PubMed (column "Time' Table 2). In the presented results, the graph generation time of VGAE and Graphite is almost zero because operating on tensors of sizes up to 3, 000 x 000 entries is not challenging for modern computers. The scalability of ARROW-Diff is further reflected in the training speed.
9

---

Published in Transactions on Machine Learning Research (03/2025)
Table 2: Graph generation results of NetGAN [Bojchevski et al., 2018 VGAE
Kipf & Welling 2016b)
Graphite (Grover et al. 2019), EDGE (Chen et al. 2023), GraphRNN (You et al. 2018), BIGG (Dai et al. 2020,, and ARROW-Diff with and without node features on the single, large-scale graph datasets from Table | The performance is given in terms of the mean of six graph statistics across generated graphs The odge overlap represents the mean overlap with the edges of the original graph. The last column reports the graph generation time for all methods, which, for ARROW- is the time for executing Algorithm
Dataset Methods degree
Max.
Assort- ativity
Triangle Count
Power law exp.
Avg. cl. coeff.
Global cl. coeff.
Edge
Time
Overlap
[s]
Cora-ML
246
-0.077
5,247
1.77
0.278
0.004
NetGAN
181
-0.025
384
I.67
0.011
0.001
3.2%
6.2
VGAE
948
-0.043
70 M
1.66
0.383
0.002
22.2%
0.0
Graphite
115
-0.188
11,532
1.57
0.201
0.009
0.3%
0.1
EDGE
202
-0.051
1,410
1.76
0.064
0.002
1.3%
5.5
GraphRNN
38
-0,078
98
2.05
0.015
0.042
0.2%
2.0
BIGG
65
0.030
280
1.98
0.026
0.008
1.0%
47.2
ARROW-Dif
373
-0.112
5,912
1.81
0.191
0.001
57.3%
1.8
ARROW-Diff
439
-0.117
5,821
1.82
0.182
0.001
55.2%
1.7
(w/o features)
Cora
297
-0049
48,279
1.69
0.267
0.007
NetGAN
135
0.010
206
I.61
0.001
0.000
0.1%
35.0
Graphite
879
-0.213
M
1.31
0.338
0.001
0.3%
0.9
EDGE
248
0.078
11,196
1.65
0.021
0.002
0.2%
85.8
BIGG
222
-0.086
2,479
1.50
0.007
0.000
0.6%
820.4
ARROW-DE
536
-0.077
89,895
1.70
0.122
0.002
40.8%
13.7
ARROW-DE Diff
579
-0.080
77,075
1.68
0.105
0.001
42.3%
13.4
(w/o features)
CiteSeer
85
-0.165
771
2.23
0.153
0.007
NetGAN
42
-0.009
23
2.03
0.004
0.00T
0.7%
4.5
VGAE
558
-0.036
15
0.383
0.003
22.1%
Graphite
58
-0.198
2,383
1.70
0.157
0.016
0.3%
0.1
EDGE
82
-0.128
205
2.08
0.054
0.003
1.1%
4.2
GraphRNN
31
-0.243
2.88
0.011
0.007
0.2%
5.7
BIGG
76
-0.198
284
2.44
0.096
0.005
3.2%
29.6
ARROW-DiA
114
-0.192
795
2.24
0.109
0.004
57.8%
1.6
ARROW-Dif
148
-0.178
996
2.15
0.125
0.003
63.0%
2.0
(w/o features)
DBLP
339
-0.018
36,645
1.76
0.145
0.004
NetGAN
215
0.053
1,535
1.62
0.002
0.000
0.9%
29.8
Graphite
734
-0.207
2 M
1.32
0.331
0.002
0.3%
0.8
EDGE
258
0.146
13,423
1.70
0.018
0.002
0.4%
62.0
BIGG
71
0.183
795
1.60
0.004
0.001
1.4%
754.3
ARROW-Dif
478
-0.098
49,865
1.78
0.069
0.001
34.2%
11.2
ARROW-
675
-0.063
63,017
1.67
0.079
0.001
34.9%
(w/o features)
PubMed
171
-0.044
12,520
2.18
0.060
0.004
NetGAN
150
-0.021
184
1.90
0.001
0.000
0.1%
39.7
Graphite
918
-0.209
4 M
1.31
0.341
0.001
0.3%
1.3
EDGE
131
0.027
2,738
2.03
0.005
0.001
0.2%
92.7
BIGG
54
-0.183
2.74
0.000
0.000
0.0%
265.7
ARROW-Diff
478
-0.082
44,120
1.90
0.039
0.001
42.7%
14.4
ARROW-DiF
474
-0.126
41,379
1.85
0.034
0.001
41.2%
12.8
(w/o features)
10

---

Published in Transactions on Machine Learning Research (03/2025)
Due to the small number of diffusion steps needed to train the random walk-basse OA-ARDM (Hoogeboom et al. 2022), ARROW-Diff converges within 30 minutes on all datasets. In contrast, EDGE requires bet weew 2-4 days on each dataset.
4.4 Visualization of Generated Graphs
In Figure we visualize the training split of the Cora-ML and CiteSeer graphs as well one generated graph from NetGAN, Graphite, EDGE, BiGG, and ARROW-DiF (using node features). We observe that ARROW- Diff is able to capture the basic structure of the ground truth graph and seems to generate significantly fewer edges than most of the baseline methods.
Training Graph
NetGAN
Graphite
EDGE
BIGG
ARROW-Di
CiteSeer Coravi
Figure 4: Visualization the training graphs and generated graphs for Cora-ML and CiteSeer from Net- GAN, Graphite, EDGE, BIGG, and ARROW-Diff using the trained models from Table P We obscrve that ARROW-Diff is able capture the basic structure of the original graph.
5 Complexity Analysis
ARROW-DiLT can be used for fast generation of large graphs. In the following, we analyze the runtime complexity of ARROW-Diff, i.e., the complexity for executing Algorithm 2 Let N denote the number of nodes and [E] the number of odges in graph, D the random walk length which in this case is equal to the number of diffusion steps, and L the number graph generation steps (iterations) ARROW-DifT In each iteration 1 [1, I.), ARROW-Diff first samples one random walk of length for each start node n E Vstart (line 6) to compute edge proposals. This step has time complexity of O(ND) because Vataet S V, and Vstart V in the first step. Next, ARROW-Dif uses GCN (Kipf & Welling, 2016a), compute the probabilities for each edge in the so far generated graph including the set of newly proposed edges (line 8), which requires a maximum of O(LE)) operations. The computation of the new start nodes for the next iteration requires a maximum of O(EE) operations with a complexity of O(EE) for computing the node degrees of & (line 12), and O(N) to compute the probabilities (line 14) and sample the new start nodes (line 15). Overall, for L generation steps, ARROW-Diff has runtime of O(L(ND + [F])). This a great reduction in complexity compared to most existing diffusion-based graph generation approaches which have runtime complexity of O(TN2) and are therefore not suitable for large-scale graph generation. The runtime of ARROW-Di also outperforms that of EDGE (Chen et al. 2023). which is the only diffusion- method in the literature that performs large graph generation at the magnitude we show here. We also show that ARROW- has a belter runtime complexity compared to the recent autoregressive diffusion-based method Graph (Kong O(N2), using overall N(N 1)/2 operations to predict
et al. 2023), which has a runtime complexity the connecting edges of each node all previously denoised nodes across all sampling steps. In Table 3 we compare the runtime complexity of the graph generation process for ARROW-DE -iff against that of each baseline method.
11

---

Published in Transactions on Machine Learning Research (03/2025)
Table 3: Runtime complexity O(-) for all baseline models and ARROW-Dift. For all methods, N is the number of nodes and M is the number of edges an input graph. For NetGAN, D the random walk length, R is the number of sampled random walks, and K is the average degree of the nodes. For VGAE and Graphite, F is the size of the latent vector. For EDGE, K is the number of active nodes.
Method
Diffusion-based
Generation Type
Runtime
NetGAN
No
Sequential
O(RD+N NK) O(EN2) O(EN2)
VGAE
No
One-shot
Graphite
No
One-shot
GraphRNN
No
Sequential
O(N2)
EDGE
Yes
Sequential
O max K²)) O(N2)
GraphARM
Yes
Sequential
BiGG
No
Sequential
O((N M) log(N)) O(LIND+ + M))
ARROW-Diff
Yes
Sequential
6 Limitations
While ARROW-Dif demonstrates promising results for large-scale graph generation, several limitations must be considered. First, the runtime complexity for inference of the GNN component (O(EE)) with increasing graph size might present a bottleneck, limiting the efficiency and scalability of ARROW-DiH to very large graphs. Another limitation of ARROW-Diff is that it generates graphs with the same number of nodes as the original graph, due to the OA-ARDM framework (Hoogeboom et al. 2022 Addressing these limitations in future work could provide more comprehensive evaluation of ARROW-Dif''s performance and scalability across graphs with various sparsity and configurations.
Potential future work could focus on adaptation of ARROW-Dif for learning on multiple graphs which would enable the evaluation of ARROW-Diff on wider range of graph structures. Future experiments should also incorporate more comprehensive hyper hyper-parameter tuning for the reported baselines. Relying on default ppprrpparamtter for cach mothod may potentially undermine their performance. Finally, investigating the effect the random walk length on the results could provide valuable insights into ARROW-Dif'ss sensitivity to this parameter.
7 Conclusion
In this paper, we present ARROW-DifL, novel approach for large-scale graph generation based random walk diffusion. ARROW-Dif generates graphs by integrating two components into an iterative procedure: (1) An order agnostic autoregressive diffusion model on the level of random walks that learns the generative process of random walks of an input graph, and (2) GNN component that learns to filter out unlikely edges from the generated graph. Due to the random walk-based diffusion, ARROW- Diff efficiently scales to large graphs, significantly reducing the generation time compared to baselines. In our experiments, we show how ARROW-Diff generates graphs of high quality, reflected in the high performance many graph statistics.
Acknowledgements
Tobias Bernecker and Ghalia Rehawi are supported by the Helmholtz Association under the joint research school "Munich School for Data Science MUDS". Francesco Paolo Casale was funded by the Free State of Bavaria's Hightech Agenda through the Institute of AI for Hcalth (AIH). Janine Knauer-Arloth's contribu- tions were supported by the Brain & Behavior Research Foundation (NARSAD Young Investigator Grant, #28063). Annalisa Marsico acknowledges support by the BMBF Cluster4Future program CNATM.
12

---

Published in Transactions on Machine Learning Research (03/2025)
References
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Strue- tured denoising diffusion models in discrete state-spaces. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
https://openreviier wett/forun/id--T-XXPPC..
Albert-Lásv1ó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439): 509-512, 1999.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised in- ductive learning via. ranking. In International Conference on Learning Representations, 2018. URL
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann, NetGAN: Generating graphs via random walks. In Jennifer Dy and Andreas Krause (ods.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 610-619. PMLR, 10-15 Jul 2018. URL htttps://proceeddingg/ mlr http://innnnni....seeeeeeeeeeeee prress//80/oocchevssss 1ttpsskiiiahhhtt. .html
Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. On the power of edge independent graph models. Advances in Neural Information Processing Systems, 34: 94418-24429 2021.
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degroe-guided graph generation via discrete diffusion modeling. arXiv preprint arXw:2335.04111, 2023.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International conference on machine learning, pp. 2302-2312. PMLR, 2020.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800, 2018.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5 (1):17 60, 1960.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, DL '98, pp. 89-98, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919653, doi: 10.1145/2766552766688 URL https://doi.org/ 1141//7676155/777755. 276685
lan Goodfellow, Jean Bouget-Abadic Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Gencrative adversarial nets. Advances in neural information processing systems, 27, 2014.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD internalional conference on Knowledge discovery and dala mining, pp. 855 864, 2016.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modcling of graphs. In International conference on machine learning, pp. 2434 2444. PMLR, 2019.
Xiaojie Guo and Liang Zhao. A systematic survey deep generative models for graph generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):5370-5330, 2022.
Kilian Konstantin Hacfeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. ar preprint arXio:2210.015.4 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in newral 2020.
information processing systems,
Sepp Hochreiter and Jürgen Schmidluber. Long short-term memory. Neural computation, 98)) 1997.
13

---

Published in Transactions on Machine Learning Research (03/2025)
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps.
Social Nebworks, ((2))109-137,, 1983. ISSN 0378-8733 doi: http:///oooooo/////0000000/44440
URL www.sciencedirect. http://www.........o.c..o..////n
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. In A. Beygelzimer, Y. Dauphin, P. Liang, and
J. Wortman Vaughan (eds.), Advonces in Neural Information Processing Systems, 2021. URL https:
Emiel Hoogeboom, Alexey A. Gritsenko, Jasmijn Bastings, Ben Poolc, Rianne van den Berg, and Tim Salimans. Autoregrossivee diffusion models. In International Conference on Learning Representations, 2022. URL htttps://openrevierr htt.://moooommmiii.11133311////1
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference Machine Learning, pp. 10362 10383. PMLR, 2022.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arv preprint or Xrv::33122611, 2013.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609. 02907, 2016a.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. arXiv preprint arXi::1611.07300 2016b.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang. Autoregres- sive diffusion model for graph generation. In International conference on machine learning, pp. 17391 17408. PMLR, 2023.
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. Advances in neural information processing systems, 32, 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construc- tion of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Libui Chen, Yang Liu, and Shan- tanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXie preprint arXiv: 707.05005, 2017.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via scoro-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020.
Shirui Pan, Jia WU, Xingquan Zhu, Chengqi Zhang, and Yang Wang. Tri-party deep network representation. Network, 11(9):12, 2016.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. Tn Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Suman Ravuri and Oriol Vinyals. Classification accuracy score for conditional generative models. Advances in neural information processing systems, 32, 2019.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical image computing and computer-assisted InterventionMIICCA. 2015: 18th inter- national conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pp. 234-241. Springer, 2015.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collec- tive classification in network data. AT magazine, 29(3):93 93, 2008.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning-CCANN ICANN 2018: 27th International Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Port I 27, pp. 412 422.. Springer, 2018.
Jascha Sohl- Sohl-Dickstein, Eric Weiss, Niru Mahcswaranathan, and Surya Ganguli. Deep unsupervised learn- ing using nonequilibrium thermodynamies. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Re- search, pp. 2256 2265, Lille, France, 07 09 Jul 2015. PMLR. URL http:://proceedngs.nt.. wtw..eeeedddnnn..........ss...s. press/ -37/sohl-dicksteree
html
Benigno Uria, lain Murray, and Hugo Larochelle. deep and tractable density estimator. In Erie P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Reseorch, pp. 467 475, Bejing, China, 22 24 Jun 2014. PMLR. URL https:://proceedingg mlr. www.press/vvv. http://////rrra....1m html
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Newral Information Processing Systems, files/paper/
volume 30. Curran Associates, Inc., 2017. httpstts::: .dff
Clement Vignac, Igor Krawczuk, Antoine Sirandin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference
Learning Representations, 2023. URL https:/ mett:forummAddUUAD---UU-u-
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-rogressive models. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5708 -717- PMLR, 10-15 Jul 2018. URL http:ttt////prceeddagg mlr. /ttppp/eeeee.eaaaa..eeeeee////// Ptress/v80/you183 html
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. In Learning on Graphs Conference, pp. 47-1. PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (03/2025)
A Standard Deviations of the Results in Table 2
Table Standard deviation for each metric shown Table
Dataset Methods
Max. degree
Assort- ativity
Triangle Count
Power law exp.
Avg. cl. coeff.
Global cl. coeff.
Edge Overlap
Time
[s]
Cora-ML
246
-0.077
5,247
1.77
0.278
0.004
NetGAN
11
0.004
19
0.00
0.001
0.000
0.2%
1.0
VGAE
24
0.003
2 M
0.11
0.001
0.000
0.6%
0.0
Graphite
14
0.015
1,411
0.02
0.007
0.001
0.1%
0.0
EDGE
1
0.010
125
0.00
0.003
0.000
0.1%
3.7
GraphRNN
20
0.085
38.558
0,210
0.004
0.048
0.09%
1.47
BICG
45
0.029
65
0.02
0.004
0.003
0.1%
1.8
ARROW-Diff
9
0.002
320
0.02
0.007
0.000
1.5%
0.0
ARROW-DiR
13
0.004
326
0.01
0.006
0.000
1.5%
0.0
(w/o features)
Cora
297
-0.049
48,279
1.69
0.267
0.007
NetGAN
13
0.003
13
0.00
0.000
0.000
0.0%
0.9
Graphite
79
0.005
116,224
0.00
0.004
0.000
0.0%
0.0
EDGE
3
0.016
1,111
0.00
0.001
0.000
0.0%
0.8
BiGG
73
0.028
1,042
0.05
0.001
0.000
0.1%
127.9
ARROW-Dif
15
0.003
2,040
0.00
0.002
0.000
0.7%
0.7
ARROW-Dit
35
0.002
4,714
0.01
0.003
0.000
1.3%
1.3
(w/o features)
CiteSeer
85
-0.165
771
2.23
0.153
0.007
NetGAN
8
0.019
6
0.01
0.002
0.000
0.2%
0.2
VGAE
16
0.004
337,244
0.11
0.001
0.000
0.8%
0.1
Graphite
6
0.022
419
0.02
0.010
0.001
0.1%
0.0
EDGE
0
0.011
27
0.01
0.007
0.000
0.2%
3.3
GraphRNN
8
0.054
5.76
0.367
0.003
0.004
0.07%
0.6
BIGG
0
0.000
0.00
0.001
0.000
0.1%
ARROW-Diff
0.007 5
69
0.03
0.008
0.000
1.4%
0.0
ARROW-Diff
0.008 8
0.02
0.008
0.000
1.1%
0.2
(w/o features)
DBLP
339
-0.018
36,645
1.76
0.145
0.004
NetGAN
10
0.005
69
0.00
0.000
0.000
0.00
0.0%
Graphite
74
0.004
69,026
0.00
0.003
0.000
0.0%
0.0
EDGE
2
0.033
1,675
0.00
0.002
0.000
0.1%
-.0
1TT
0.5
11.7
BIGG
12
0.022
57
0.01
0.000
0.000
ARROW-DiFF
26
0.002
2,202
0.01
0.002
0.000
0.8%
0.7
ARROW-DE
27
0.003
2,797
0.01
0.002
0.000
0.6%
0.0
(w/o features)
PubMed
171
0.044
12,520
2.18
0.060
0.004
NetGAN
14
0.004
9
0.00
0.000
0.000
0.0%
1.8
Graphite
70
0.005
244,816
0.00
0.004
0.000
0.0%
0.0
EDGE
4
0.038
741
0.00
0.001
0.000
0.0%
0.5
BIGG
7
0.010
0.16
0.000
0.000
0.0%
32.5
ARROW-DiF
11
0.003
1,454
0.00
0.001
0.000
0.8%
1.1
ARROW-DifF
15
0.004
2,427
0.01
0.001
0.000
1.0%
0.0
(w/o features)
16

---

Published in Transactions on Machine Learning Research (03/2025)
B Evaluation of the Quality of the Generated Graphs
In the following analysis, we validate the capability of ARROW-Diff in learning the topological structure of the original graph and in generating new graphs that have similar data distribution the original graph. To this end, generated 100 graphs for each of CiteSeer, DBLP, and PubMed graphs. We used the graph embedding technique Graph2Vec (Narayanan et al. 2017) to map the generated graphs into embeddings of size 256. A principal component analysis (PCA) of the embeddings (Figure 5 revealed clear separation between the different generated graphs of the different datasets highlighting the ability of ARROW-Diff in gencrating graphs with similar structural properties for the same dataset. The results also depicted that the embeddings of the generated graphs are close in the embedding space to their original counterparts, indicating that ARROW-Dif produces graphs that closely mimic the structural properties of the input graphs and underscoring the fidelity of the generated graphs. A logistic regression-based based classifier trained the generated graphs and tested the real graphs reported Classification Accuracy Score (CAS) (Ravuri & Vinyals 2019) of 0.67.
PC2
-1-
GiteSeer
DBLP
PubMed
-2 Real Graphs
Gonerated Graphs
PC1 (8%)
Figure 5: Principal component analysis (PCA) of the Graph2Vee embeddings of the original CiteSeer, DBLP, and PubMed graphs and 100 generated graphs for each of the datasets, showing clear separation between the generated graphs of the different datasets, and proximity of the generated graphs to their real graph counterparts.
C Supplementary Experiments and Results
C.1 Stochastic Block Model Dataset
In the following experiment, we evaluate the ability of ARROW-Dif to generate graphs with a different structure to those shown in Section 4 Specifically, we create a synthetic datasct containing a Stochastic Block Model (SBM) (Holland et al., 1983) graph that does not show a preferential attachment property law degree distribution). The constructed SBM graph includes three communities with 60, 100, and 200 nodes, and a total of 3,824 edges. Similar our main experiments (Section 4 we split the edges into training, validation, and test edges, and use the same training split across all experiments.
C.2 Parameters for ARROW-Diff Training and Graph Generation
Due to the smaller size of the SBM graph, we set the random walk length and run ARROW-Dif for L 5 iterations only. We also set the dimensionality of positional encodings (used by the GNN component) of the nodes to 64.
17

---

Published in Transactions on Machine Learning Research (03/2025)
Table 5: edges.
The results of ARROW-Dif and six baseline models on the SBM dataset with 360 nodes and 3,824
Dataset Methods
Max. degree
Assort- ativity
Triangle Count
Avg. cl. coeff.
Global cl. coeff.
Edge Overlap
Time [s]
SBM
36
-0.016
3,623
0.134
0.019
NeIGAN
16
-0.013
2,393
0.080
0.010
9.2%
1.5
VGAE
122
-0.012
146,304
0.383
0.013
22.1%
0.0
Graphite
11
-0.134
23
0,048
0.082
0.3%
0.1
EDGE
0.017
1,581
0.072
0,012
5.7%
GraphRNN
14
-0.061
57
0.025
0.038
1.7%
0.2
BiGG
33
-0.029
2,201
0.113
0.019
65.9%
13.9
ARROW-
48
0.026
2,969
0.157
0.020
40.5%
0.5
Diff (w/o features)
C.3 Results
Table presents the results as the mean across 10 generated graphs. For evaluation, we omit the power- law exponent metric,
is exclusively applicable scale-free graphs. The results demonstrate that ARROW-Diff achieves the best performance on the triangle count metric, consistent with the results on the citation graphs (Table 2 It also shows competitive performance compared to other basclines the rest of the metrics, performing second best two metrics while siguificantly reducing graph generation time. In Figure 0 we provide a visualization of the training split of the synthetic SBM graph as well as the generated graphs, showcasing the ability of ARROW-Diff in capturing the three communtty structures the SBM graph.
Training Graph
NetCAN
Graphite
EDGE
BiGG
ARROW Diff
Figure 6: Visualization of the SBM training graph well generated graphs from NetGAN, Graphite, EDGE, BiGG, and ARROW-DRR Diff. We that ARROW-DD W-fffffi is able to capture the community structures of the original graph.
18

---

Published in Transactions on Machine Learning Research (03/2025)
D
Node Degree Distribution of Generated Graphs
Original Graph
Original Graph
Generated Graph
Generated Graph
10
10
Counts
Counts
10a
10"
10a
10a
10a
Node Degree
Node Degree
(a) CiteSeer dataset.
(b) SBM dataset.
Figure 7: Node degree distributions of the real CiteSeer and SBM graphs and one generated graph of ARROW-Diff for each of the two datasets. The original node features are used by ARROW-Dif for the CiteSeer dataset.
19


Reviews:
[{"review_id": "m6hPeqth39", "reviewer": "Reviewer_TkfS", "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. The paper reports strong results, in particular in edge overlap and metrics like assortativity, while benefiting form improved scaling via relatively short random walks chopping the graph up efficiently into parallélisable chunks\n    \n2. The idea is clever, it inherits the BA like preferential attachment pattern from netgan/ node2vec but but can do multi-step candidate selection as well as correction via the EDGE inspired guidance GNN\n    \n\nWeaknesses:\n\n- mainly in the evaluation/presentation:\n    \n    - the authors use the paper hyperparameters, but some some of these papers are years old. I myself have made this mistake of accidentally sandbagging papers. For a fair comparison, one would need to estimate total numbers of flops and parameters and spend equal resources tuning. This is going beyond what is common in ML and computationally expensive, however I think *acknowledging this* not only in the end of the paper, but also in the experimental setup is important.\n   - in particular, the authors match the random walk length method to the dataset characteristics, which is a level of tuning not all the baselines performed\n    - While I think the authors are in the clear, I would recommend using a form of bootstrap (chopping generated and original graphs into equally sized random overlapping communities computing metrics on these, then aggregating) to construct confidence intervals and perform p-tests for statistically significant results (Efron has a nice book introducing bias corrected bootstrapping methods). Alternatively one could use https://arxiv.org/abs/1905.10887 with the generated graphs as training set to evaluate on the real graph\n        \n    - Multiple random seeds should also ideally be taken for _training_, or acknowledgement of such shortcoming should be made\n        \n    - There should be a standardizd callibration procedure for the edge probability selection\n        \n    - there are some important strong baselines omitted:\n        \n        - [https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-213](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-213) an autoregressive model which can scale to > 100k nodes\n            \n        - [https://openreview.net/forum?id=2XkTz7gdpc](https://openreview.net/forum?id=2XkTz7gdpc) on a high level “EDGE, but spectrally guided”\n            \n        - [https://arxiv.org/abs/2311.02142](https://arxiv.org/abs/2311.02142) “Digress, but learning degree guidance”\n            \n    - there is also a nice chance to discuss whether the permutation-augmentation technique of OA-ARDMs will work for graphs, [https://arxiv.org/abs/2307.01646v4](https://arxiv.org/abs/2307.01646v4) is a work that argues yes, and [https://arxiv.org/abs/2110.02096](https://arxiv.org/abs/2110.02096) showed that *any* algorithm with a permutation invariant *loss* can work, however, this will only hold if one can actually *train* sufficiently. on the given tasks, I think this is a given, but worth discussion\n        \n    - while the baselines are inadvertently sandbagged (again, not a diss, I’ve done this myself by accident), the datasets are inadvertently cherry picked: they all exhibit BA style preferential attachment properties, which is playing to this algorithms strength. I’d like to see at least synthetic baselines on more structured graphs, maybe pointclouds/ grids, etc. again, not a grounds for reject IFF it is acknowledged as a limit of the evaluation", "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 presents ARROW-Diff, a graph generative model targeting in particular large graphs, constructed by combining OA-ARDMs (order agnostic autoregressive diffusion models, a variant trained with training time order-agnostic masking to train without reliance on order) with the random walk graph generation pioneered by netgan and node2vec, as well as the concept of active nodes and degree guidance pioneered by EDGE, using a GNN to commit to edges identified in the random walk as candidates..\n\nThe paper is evaluated against NetGAN, Graphite,EDGE on large citation graph datasets, as well as against VGAE and GraphRNN on the smallest 2., showing strong results", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical:\n- acknowledge or rebut the limitations I pointed out, add the missing related works or justify their omission\n- mention the baselines, if computationally feasible, compare against them\n- ensure that the results are statistically meaningful (be it via boostraps, CAS or both)\n- add at least one real world adversarial dataset (not exhibition preferential attachment), or even better, synthetic benchmarks to test corners of the network \n\nBonus/would strengthen:\n- all the computationally expensive extra work I pointed out.", "broader_impact_concerns": "Aside from the impending climate catastrophy which we all contribute to blasting GPUs, I think the authors are in the clear.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fZqkeDszcK", "reviewer": "Reviewer_iqjV", "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\nThe paper presents a significant advancement in the field of graph generation by introducing a scalable method that leverages random walks for diffusion processes. This approach is innovative as it reduces computational complexity and overcomes limitations related to edge independence and scalability found in existing methods. The methodology is well-articulated, with clear descriptions of both components—random walk-based diffusion and GNN validation. The use of OA-ARDM for random walk sampling is particularly noteworthy as it allows for efficient scaling by limiting diffusion steps to the length of the random walk rather than the size of the entire graph. The experiments conducted demonstrate that ARROW-Diff outperforms other methods in terms of both speed and quality of generated graphs. The results are compelling, showing significant reductions in generation time while maintaining or improving graph statistics such as degree distribution.\n\nOverall, this paper makes a substantial contribution to graph generation research by introducing a novel method that effectively balances efficiency and quality. It is recommended for acceptance after minor revisions to enhance clarity and address any potential limitations in broader applications.\n\nWeaknesses:\n\nScalability Concerns: Although ARROW-Diff is designed to handle large graphs, its performance may still be limited by the complexity of the Graph Neural Network (GNN) component. As the size of the graph increases, the computational cost associated with training and inference using GNNs can become significant, potentially offsetting the efficiency gains from the random walk-based diffusion model.\n\nGraph Quality Variability: The quality of the generated graphs, particularly in terms of preserving complex topological features like community structures or clustering coefficients, may vary. The method's reliance on random walks might not fully capture intricate dependencies present in certain types of graphs, leading to discrepancies between generated and original graph statistics.\n\nEdge Validity Prediction: The GNN component's ability to predict edge validity accurately is crucial for ensuring high-quality graph generation. However, if the GNN model is not well-tuned or if the training data is not representative of the target graph's structure, this can lead to errors in edge prediction, affecting the overall quality of the generated graph.\n\nDependency on Node Degree Guidance: The iterative process guided by node degrees could potentially introduce biases in graph generation. If the degree distribution of the input graph is not well-represented or if there are anomalies, it might lead to inaccurate reproduction of graph properties in the generated output.\n\nLimited Generalizability: The method's effectiveness across different types of graphs (e.g., social networks vs. molecular structures) might be limited. The specific design choices, such as random walk length and diffusion steps, may need significant adjustments to cater to diverse graph structures and sizes.", "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  introduces ARROW-Diff (AutoRegressive RandOm Walk Diffusion), a novel approach for generating large-scale graphs efficiently. The method addresses the limitations of previous diffusion-based graph generation techniques, which often struggle with scalability and quality when applied to large graphs. ARROW-Diff employs a two-component system:\n\n1. Random Walk-Based Diffusion Model: This component uses an order-agnostic autoregressive diffusion framework (OA-ARDM) to sample random walks from an input graph. The random walk-based diffusion captures the complex and sparse structure of graphs, allowing ARROW-Diff to scale efficiently.\n\n2. Graph Neural Network: This component predicts the validity of edges in the generated random walks, refining the graph generation process and ensuring high-quality outputs.\n\nARROW-Diff iteratively integrates these components, guided by node degrees, to produce graphs with similar degree distributions to the original graph. The method demonstrates superior performance in terms of generation time and graph quality compared to existing baseline methods, efficiently handling graphs with up to 20,000 nodes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some sections could benefit from additional clarity, particularly in explaining complex concepts like OA-ARDM and its integration with GNNs for readers unfamiliar with these models.\n\nWhile the paper addresses many challenges in large-scale graph generation, it would be beneficial to discuss potential limitations of ARROW-Diff, such as its applicability to different types of graphs or potential issues with very sparse or dense graphs. Suggestions for future work could include exploring enhancements in the GNN component or adapting the method for dynamic graph scenarios.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UzsTazhoI2", "reviewer": "Reviewer_xGqN", "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": "Strength:\nThe work proposes a novel method for graph generation, combining a diffusion model and a GNN.\nThe proposed model, ARROWDiff, outperforms previous graph generation methods in terms of fidelity to original graph characteristics.\n\nWeakness:\nNevertheless, the experimental results show that, even within 30 iteration, the generated graph do not approach the original graphs interms of several characteristics, especially globale clustering coefficient, while they deviate significantly in terms of maximum degree.", "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 ARROWDiff a methods that learns to generate large graphs of a similar structure as a sample original graph.\nARROWDiff uses a learned diffusion model to generate random walks from the original graph based on previous work by Hoogeboom et al. (2022), first sampling random walks and then masking nodes in forward diffusion to predict nodes in reverse diffusion. It also uses a GNN to capture the topology of the original graph and thereby assess the validity of edges proposed by the diffusion model.\nThe components work together in an iterative process to generate the final graph.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The proposed method works reasonably well, in comparison to alternative graph generation models.\nHowever, the comparison seems to be unfair, since the proposed method draws heavily from the graph embedding literature, yet it is not assesed in comparison to that literature. Graph embedding methods like DeepWalk, node2vec, VERSE, and NetSMF, can be used directly for reconstructing an embedded graph, which amounts in practice to a graph generation process in disguise. Such a usage of a graph embedding, which is practices in the embedding literature, comes very close to what is proposed in this work. Therefore, the study should assess the proposed method vs. graph embedding methods employed for generating new graphs similar to the embedded graph.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a generative model for large graphs. Reviewers appreciated the proposed approach and the paper is well-written. I believe the paper meets TMLR's acceptance criteria and thus recommend acceptance.
Decision: Accept (poster)