Efficient and Scalable Graph Generation through Iterative Local Expansion
Authors: Andreas Bergmeister
Karolis Martinkus
Nathanaël Perraudin
Roger Wattenhofer
Venue: ICLR 2024 poster (2024)
Keywords: Graph Generation
Denoising Diffusion
Spectral Graph Theory
Primary area: generative models
TL;DR: We introduce a novel method to build a graph by progressively expanding a single node to a target graph, adding nodes and edges in a localized manner through denoising diffusion, building first the global structure and then refining.

Abstract: In the realm of generative models for graphs, extensive research has been conducted. However, most existing methods struggle with large graphs due to the complexity of representing the entire joint distribution across all node pairs and capturing both global and local graph structures simultaneously.
To overcome these issues, we introduce a method that generates a graph by progressively expanding a single node to a target graph. In each step, nodes and edges are added in a localized manner through denoising diffusion, building first the global structure, and then refining the local details. The local generation avoids modeling the entire joint distribution over all node pairs, achieving substantial computational savings with subquadratic runtime relative to node count while maintaining high expressivity through multiscale generation.
Our experiments show that our model achieves state-of-the-art performance on well-established benchmark datasets while successfully scaling to graphs with at least 5000 nodes. Our method is also the first to successfully extrapolate to graphs outside of the training distribution, showcasing a much better generalization capability over existing methods.

Published as a conference paper at ICLR 2024
EFFICIENT AND SCALABLE GRAPH GENERATION THROUGH ITERATIVE LOCAL EXPANSION
Andreas Bergmeister* ETH Zürich
Karolis Martinkus Prescient Design
Nathanaël Perraudin' SDSC, ETH Zürich
Roger Wattenhofer DISCO, ETH Zürich
ABSTRACT
In the realm of generative models for graphs, extensive research has been con- ducted. However, most existing methods struggle with large graphs due to the complexity of representing the entire joint distribution across all node pairs and capturing both global and local graph structures simultaneously. To overcome these issues, introduce a method that generates graph by progressively ex- panding a single node to a target graph. In each step, nodes and edges are added a localized manner through denoising diffusion, building first the global struc- ture, and then refining the local details. The local generation avoids modeling the entire joint distribution over all node pairs, achieving substantial computa- tional savings with subquadratic runtime relative to node count while maintain- ing high expressivity through multiscale generation. Our experiments show that our model achieves state-of-the-arr performance on well-established benchmark datasets while successfully scaling to graphs with at least 5000 nodes. Our method is also the first to successfully extrapolate to graphs outside of the training distri- bution, showcasing a much better generalization capability over existing methods.
INTRODUCTION
Graphs are mathematical structures representing relational data. They comprise a set of nodes and set of edges, denoting pairwise relations between them. This abstraction is ubiquitous in modeling discrete data across domains like social networking (Fan et al. 2019). program synthesis (Nguyen jet al. 2012 Bieber et al., 2020). or even origami design (Geiger et al 2023). A crucial task the generation of new graphs that possess characteristics similar to those observed. For example, in drug discovery, this involves creating graphs that encode the structure of a desired type of protein (Ingra-
ham et al. 2022
Martinkus et al. 2023) molecule (Jin et al. 2018 Vignac et al. 2023b).
estimate parameters of known mod- els like Stochastic Block Model (SBM) (Holland et al. 1983) Frdos-Renyi et (1960) but often fail to capture the complexity of real-world data. Deep learning offers a promising alternative, with approaches falling into two categories depending on the factorization of the data-generating distribution. Autoregressive techniques build graphs incrementally, predicting edges for each new node (You et al., 20188) Liao et al.) 2020 Dai et al.] (2020). One-shot methods generate the entire graph at once using techniques such variational autoencoders (Simonovsky & <Komodakis] 2018).
Traditional graph generation methods AAlert & Barabási 2002
generative adversarial networks (Cao & Kipf, 2022, Martinkus et al. 2022). normalizing flows (Liu
al. 2019), score-based and denoising diffusion models (Niu al. 2020 Hacfeli et al. 2023
Despite the success of these methods in generating graphs comprising several hundred nodes, scaling beyond this range poses challenges. The computational cost of predicting edges between all node pairs scales at least quadratically with the number of nodes, which is inefficient for sparse graphs typical of real-world data. Sample fidelity is also issue, autoregressive methods struggle with node-penn wwtt---ptettnniinvaaaaea invariaat training due to the factorial increase in node orderings, and one-shot methods often fail to capture both global and local graph structure simultaneously. Also, in contrast to algorithmic approaches (Babiac et al.) 2023), neither have been shown to generalize to larger unseen graph sizes. Finally, the neural architectures employed either exhibit limited expressiveness,
"Conrespondence to: andreas www.beeeeeeeerrreeemmo itt.eeer..nee.e.e.cccc I Equal contribution.

---

Published as a conference paper at ICLR 2024
Coarsening
G
G2
G1
Go
Expansion Refinement
Figure Example of 4-level coarsening sequence. Colors indicate the node contraction sets y(P), Our generation process aims at reversing with expansions and refinements the T steps of this sequence from Gr to Go. The details of a single step are provided in Figure
although with linear complexity in the number of edges for message passing neural networks (Xu er al. 2019). are computationally expensive with quadratic even higher scaling factors for more expressive architectures (Dwivedi & Bresson 2021 Maron et al. 2020).
We present novel approach to graph generation through iterative local expansion. In each step, we expand some nodes into small subgraphs and use diffusion model to recover the appropriate local structure. The model is trained reverse graph coarsening process, depicted in Figure TT applied to the dataset graphs (Loukas) 2018 Loukas & Vandergheynst, 2018 Hermsdorti Gun- We argue that this inherently suitable for generating graphs, as it allows for the generation of an approximate global structure initially, followed by the addition of local details. This generative process effectively represents particular kind of network growth, which we find to be much more robust to changes in generated graph sizes than existing approaches. Moreover, our method enables modeling the distribution of edges with- out the need to represent the entire joint distribution over all node pairs, enhancing scalability for larger graphs. Our theoretical analysis shows that, under mild conditions, our method exhibits sub- quadratic sampling complexity relative the number of nodes for sparse graphs. We also introduce a more efficient local version of the Provably Powerful Graph Network (PPGN) (Maron et al. 2020), termed Local PPGN. This variant is especially well suited for our iterative local expansion approach, maintaining the high expressive power in the local subgraphs that we process while providing better computational efficiency. To demonstrate the effectiveness of our approach, ments with widely used benchmark datasets. First, in the standard graph distribution modeling task from Martinkus (2022); Vignac al. (2023a), our model achieves state-of-the-an performance score on the planar and tree datasets. Additionally,
derson 2019 Jin et al. 2020bb Kumar al.
conducted experi-
with the highest generated graphs most closely matching the test set's structural statisties for protein and point cloud datasets. Second, we evaluate our method's 's ability to generalize beyond the training distribu- tion, by generating graphs with an unseen number of nodes and verifying if they retain the defining characteristics of the training data. In this setting, our method is the only one capable of preserv- ing these characteristics across the considered datasets. Third, we show that for sparse graphs our model exhibits subquadratic sampling complexity relative to the number of nodes, and validate this empirically by generating planar graphs of increasing size. Our implementation is available"
Senedit-Unnquuness--Se
RELATED WORK
The seminal work by You al. (018)) pioneered graph generation using recurrent neural networks, creating the adjacency matrix sequentially. [iao et al. (2020) improved this approach by simultane- ously sampling edges for newly added nodes from a mixture of independent Bernoulli distributions with parameters obtained from message passing graph neural network. Kong et al. (2023) concep- tualized this method as the inverse of an absorbing state diffusion process (Austin et al. 202T and proposed reinforcement learning optimize node addition sequences.
Lately, diffusion models have come to dominate alternative approaches in terms of sample quality and diversity. Although initially only effective for graphs with tens of nodes (Niu et al., 2020). sub-
sequent improvements using discrete diffusion (Vignac et al. 2023a b) Haefeli et al. (2023). refining
the diffusion process with destination predicting diffusion mixture (Jo al. 2023). dropping
2

---

Published as a conference paper at ICLR 2024
Coarsening
Gr
Expansion and Refinement
8 G(G,
G =(GG)e))))
G = G(G PHs)
Figure 2: Single step schematic representation of the proposed methodology. The upper delin- cates two sequential coarsening steps, using color differentiation to denote the contraction sets Vir). Commencing from the right in the lower row, the expansion of G1+1 into G. C(Gr+1, v1+1) is shown, assuming known cluster size vector W1+1- Colors distinguish membership within expan- sion sets while dashed lines indicate edges to be removed as per the edge selection vector et. The resultant refined graph G G(Gi, ei) is shown in the central box, where node features correspond to the cluster size vector vy, used in expanding Gt into G (illustrated in the leftmost box).
permutation equivariance Yann et al. 2023) allowed for successful generation of graphs with a few hundred nodes. Nevertheless, scalability and computational complexity remain challenges for these models. As a countermeasure, Diamant et al. (2023) suggest limiting the maximal bandwidth of generated graphs. They leverage the observation that real-world graph nodes can often be ordered to confine non-zero adjacency matrix entries within narrow diagonal band (Cuthill & McKeel
1969).
Within this band, generation can be achieved using models such as GraphRNN (You et al. variational autoencoders (Grover et al. 2019), score-based generative models (Nuu et al. Alternatively, [Chnn et al. (2023b) introduce degree-guided diffusion, which begins with an RNN- generated degree sequence to condition the graph diffusion model. During each step, the model only considers edge connections between nodes predicted to require degree increases. This non- local process requires a simple, non-expressive, message passing graph neural network for efficient execution. However, it does offer an increase in empirical computational efficiency. Goyal et al.) (2020) propose a different approach by generating a canonical string representation of the graph using a long short-term memory network. Although the length of the string is linear in the number of graph edges, generating the strings for model training has worst-case factorial complexity, which limits the practicality of this approach for general large-scale graph generation tasks.
2018
2020
An orthogonal line of research leverages hierarchical constructions for more efficient graph gener- ation. Dai et al. (2020) improve the original RNN-based adjacency generation by You et al. (2018)
using binary tree-structured conditioning on rows and columns of the matrix, cutting the comp complexity
from (n²)) to O( + m) logn). with representing nodes and m edges. Shirzad et al. (002
suggest a two-stage process starting with tree-based cluster representation, followed by incremental subgraph construction. Another two-level approach to generation is proposed by Davies et al. (2023)
using DiGress (Vignac et al., 2023a) to create cluster graphs, followed by independent generation of cluster subgraphs and intra-cluster edges. In related vein, Karami (2023) present methodol-
ogy that extends to multiple levels of hierarchy, with autoregressive generation of cluster subgraphs.
Limnios al. (2023) propose another method enhance DiGress's scalability, which involves divide-and-conquer strategy for sampling subgraph coverings. Although the independence assump- tions of these hierarchical methods improve scalability, they may compromise sample accuracy, contrasting with our approach that avoids such assumptions. Both Davies et al. (2023) and Karami B
(203)) utilize the Louvain algorithm (Blondel et al., 2008) for pre-generating clusterings for train- ing, unlike our method, which employs random sampling of coarsening sequences during training. Additionally. Guo et al. 2223) introduce graph expansion layer for inclusion the generator of generative adversarial network or the decoder of variational autoencoder, with parameter training carried out through reinforcement learning. Hierarchical approaches have also been developed for molecular generation (Jin et al. 2018, 2020al Kuznetsov & Polykovskiy 202I), with the aim of improving efficiency and performance by integrating domain knowledge. However, these methods not optimized for general graph generation tasks.
3

---

Published as a conference paper at ICLR 2024
3 METHOD
This section presents our proposed method for graph generation through iterative local graph cxpan- sion. A graph is tuple G (V,E), where V is set of n | vertices and & set of [8] undirected edges. Assuming an arbitrary indexing of the nodes from 1 to n, we use y(6) to denote the i-th node in V and e(kJ) = {v((), x(0) E & to denote the undirected edge connecting the nodes v(() and e()), Although the generated graphs are unattributed, the proposed method internally generates node and edge features denoted by v and e respectively. Their i-th component, denoted by v|1] and eli], corresponds to the feature of the i-th node or edge in the graph. W E R is a symmetric adjacency matrix with non-zero entries ji = W il assigning positive (unary for the dataset graphs) weight to edges e e(a-)) E Consequently, the combinatorial Laplacian matrix is defined as L = D W, where D is the diagonal degree matrix with Dli, Σド= W [i, j]. All graphs are assumed to be connected.
3.1 GRAPH EXPANSION
Starting from a singleton graph G2 = (fv}. 0), we construct a sequence of graphs with increasing size in an auto-regressive fashion as
G
expand
G refine G1-1+
with Go being the graph to be generated. In every step, expand each node in Gj into cluster of nodes, connecting nodes within the same cluster and between neighboring clusters, resulting in a graph G with Ri-1 nodes. Subsequently, we refine G into GL-1 by selectively eliminating certain edges present in GT-1- Figure illustrates this process. Let us now formalize the definitions of the expansion and refinement steps.
Definition (Graph Expansion) Given a graph G = EV with |V] = n nodes and a cluster size vector v E N" denoting the expansion size of each node, let G(G, v) (V, E) denote the expansion of It contains vlp) nodes, v(Pi) ..... ((Po(e)), for each node (()) E V in the initial graph. As such, the expanded node set is given by V ->==()))... -..))....uu)) where y(r) (1( 1 I S elp) I p < The edge set E includes all intracluster edges, felpupil | < p S n, 1 < <i<> < < vlp)], as well as the cluster interconnecting edges, (e/p.1eh etp-a) E E ) E V(r), wl E V(0)).
Definition 2 (Graph Refinement) Given graph G = (V,E) with m = | edges and an edge
selection vector e E {0, 1hth let G e) = (V,E) denote the refinement of G, with V = 1 and and only if elil 1.
& such that the i-th edge eli)
Probabilistic Model Starting from a given dataset
..... (G())...,GCo of ii.d. graph samples, we
aim to fit a distribution p(G') that matches the unknown true generative process as closely as possible. We model the marginal likelihood of graph G the sum of likelihoods over expansion sequences
p()
Σ p(w)
(EIIGG)
Here, (I) denotes the set of all possible expansion sequences (Gz = ([v), 0), GI-I. Go G') of a single node into the target graph G, with each G being a refined expansion of its prede- cessor, that is, Gi-1 = G(G vi) is the expansion of G, according to Definition with the cluster size vector vr and Gi-1 = G( is the refinement of G according to Definition 2 and the edge selection vector 61-1
Factorization We factorize the likelihood of a fixed expansion sequence w = (G,,, Go) into product of conditional likelihoods of single expansion and refinement steps, assuming a Markovian structure, as
m<)==p(Gn II P Gt) = II p(e Gz-1)p(0r Gt).
L=
4

---

Published as a conference paper at ICLR 2024
To avoid modeling two separate distributions p(e: Gi) and p(er Gi), rearrange terms as
p(=) p
GL) p(vL)
II p(u, G))p(e Gi) L1=-1
p(eo Go):
(1)
and model to be conditionally independent of Gi given Gt, i.. p(vi Gi, Gi) p(vi allowing us to write
Gi),
p(v Gi)p(e: Gi) p(v,, ei Gi).
We represent the expansion and refinement vectors as node and edge features of the expanded graph, respectively. This enables us model single joint distribution over these features for each refine- ment and consecutive expansion step.
3.2 LEARNING TO INVERT GRAPII COARSENING
We now describe how we construct expansion sequences w [I) for a given graph G and use them to train a model for conditional distributions p( [1: et Gi). For this, we introduce the notion of graph coarsening as the inverse operation of graph expansion. Intuitively, obtain a coarsening of graph by partitioning its nodes into nonoverlapping, connected sets and contracting the induced subgraph of each set into single node.
Definition 3 (Graph Coarsening) Let = EV,)) be arbitrary graph and P (V(), ..... Vinl be partitioning of the node set V, such that each partition Viv) P induces a connected subgraph in G. We construct a coarsening G(G,P) = (V,E) of G by representing each partition ViP) E P as a single node vfp) E V. We add an edge clp-a) E ε, between distinct nodes v(P) f (94 V in the coarsened graph if and only there exists an edge ed6.t E & between the corresponding disjoint clusters in the original graph, i.e. v16) E v(P) and vlu) E v(9).
An important property of this coarsening operation is that it can be inverted through an appro- priate expansion and subsequent refinement step, elaborated in Appendix A Based on this premise, it can be deduced through an inductive argument that for any given coarsening sequence (G Go. GI.... GL (fv). that transforms graph G into a single node, there exists corresponding expansion sequence E [I(G') with the same elements in reverse order, i.c. w = (G,, Go). Note that successive coarsening steps always result in a single-node graph, as long the original graph is connected, and every coarsening step contains at least one non-trivial contraction set, i.e. a set of nodes with more than one node.
We define the distribution p(T) over coarsening sequences symmetrically to p(w) in Equation D and use (G) to denote the set all possible coarsening sequences a graph G. With this, it holds that
pG)
Σ (E
p(w)
P(T)).
(EII(G)
Note that this inequality is strict, there exist expansion sequences that not the reverse of any coarsening sequence"] As we can easily generate samples from II()), this a suitable lower bound on the marginal likelihood of G that
aim maximize during training.
Contraction Families Without further restrictions on the allowed partitioning of the node set in Definition 3 for an arbitrary graph G there can potentially be exponentially many coarsenings of it, rendering the computation of the sum Eren(g) P(T)) intractable. Therefore, we further restrict the possible contraction sets in graph coarsening to belong to given contraction family F(G). We use (G) to denote the set of all possible coarsening sequences of G that only use contraction sets from F(G) in each step. [T=(G)) is subset of ITG),, and hence Equation 2 with TT(G) replaced by (G( still holds. Following Loukas (2018), we experiment with edge contraction F(G) = E and (b2) E ε} ( E V}.
neighborhood contraction F(G)
For example, the refinement step might split the graph into two connected components, which cannot, from Definition be coarsened back into single connected graph.
5

---

Published as a conference paper at ICLR 2024
Variational Interpretation a graph G, it holds that
Given a distribution q(á
G) over coarsening sequences IIy for
GG) N
Σ
p(T)
pl n [ G)
G)
(E)T==(G)
and one can derive the evidence lower bound on the log-likelihood under the given model as
log p(G) Z
E [T]q(=/()
logp(us |GL) +
Σ
log,(e Gi) log p(eu Go)
+ +H(g(T (T G)),
(3)
leading to variational interpretation of the model.
Spectral Guided Generation The above formulation is agnostic to the distribution q( G) over coarsening sequences (G), giving us the flexibility to choose distribution that facilitates the learning process and improves the generative performance of the model. While the uniform distri- bution over all possible coarsening sequences (G) gives the tightest bound in Equation 3 as the entropy term vanishes, arbitrary coarsening sequences could destroy important structural properties of the original graph G, making it difficult for the model to learn to invert them. Therefore, we propose distribution y that prioritizes coarsening sequences preserving the spectrum of the graph Laplacian, which is known to capture important structural properties of a graph. Note that the dis- tribution 9 does not need to be explicitly defined. Instead, for training the model, only need a sampling procedure from this distribution. In Appendix [ we propose sampling procedure for ee
coarsening sequences which is parametric in cost function. It iteratively evaluates the cost function
across all contraction sets and subsequently selects a most-miiniizing partition of the contraction sets in greedy and stochastic fashion. When instantiating the cost function with the Local Variation Cost proposed by Loukas (2018). we obtain Laplacian spectrum-preserrvng distribution over coarsening sequences. In Appendix C we summarize the work Loukas (018)) and show how our generic sampling procedure can be instantiated with the Local Variation Cost. In Section [.I] we empirically validate the effectiveness of this approach by comparing the generative performance of the model with and without spectrum- preeeurviggeeeeiingggg sampling. While numerous graph coarsening tech- niques exist (Loukas) 2018 Hermsdorff & Gunderson 2019; Jin et al., 2020b Kumar et al., [022] 2023), our chosen method stands out for two key reasons. It adheres our coarsening definition with an efficient local cost function guiding contraction set selection. Additionally, it's a multilevel scheme that maintains the original graph's 's Laplacian spectrum at each level, essential for our goals.
3.3 MODELING AND TRAINING
We now turn to the modeling of conditional distributions p(v), ex|Gi) within our marginal likelihood factorization for p(G). Let Po (v, (G,) denote the parameterized distribution, with O as the param- eters. We use the same model for all 1 < < L conditional distributions pa(u,, es Gi) well as Pe(eo Gu) and pe (o GL) Po(UL), with the parameters 0 being shared between all distri- butions. For the latter two distributions, we disregard the edge and node features, respectively, but maintain the same modeling approach for the other distributions. In the following, we describe the modeling of po(v,, e, Gi) for arbitrary but fixed level < L.
Modeling with Denoising Diffusion Models An effective method should be capable of represent- ing complex distributions and provide a stable, node permutation -nniutaatioonnvaiiantt invariant training loss. Denoising diffusion models meet these criteria. This method entails training denoising model to restore the original samples-in our setting, node and edge features tt and er-from their corrupted counter- parts. Inference proceeds iteratively, refining predictions from an initial noise state. Although this requires multiple model queries per graph expansion, it does not affect the algorithm's asymptotic complexity nor impose restrictive assumptions on the distribution, unlike simpler models such as mixtures of independent categorical distributions. We adopt the formulation proposed by [Song et al. 2021), ,, enhanced by contributions from Karras al. (0022. This method represents the forefront in image synthesis, and preliminary experiments indicate its superior performance for our application. For comprehensive description of the framework and its adaptation our context, Appendix E

---

Published as a conference paper at ICLR 2024
3.4 LOCAL PPGN
A key component of our proposed methodology is the specialized architecture designed to parame- terize the conditional distributions pe(v), e: Gi). equivalently, the denoising model. Our design incorporates a novel edge-wise message passing layer, termed Local PPGN. When designing this layer, drew inspiration from the PPGN model (Maron et al., 2020), which is provably more pressive than graph message passing networks at the expense of increased computational complexity (cubic in the number of nodes). Recognizing that our suggested methodology only locally alternates graphs at every expansion step and that these graphs possess a locally dense structure, as result of the expansion process (Definition []. we designed a layer that is locally expressive, resembles the PPGN layer on a dense (sub)graph, but retains efficiency on sparse graphs, with linear runtime relative to the number of edges. An elaborate explanation of this layer and its placement within existing graph neural network models can be found in Appendix F In-depth architectural details of the overall model are presented in Appendix F2
3.5 SPECTRAL CONDITIONING
Martinkus et al. (2022) found that using the principal Laplacian eigenvalues and eigenvectors of target graph as conditional information improves graph generative models. A salient aspect of our generative methodology is that it generates graph G₁ from its coarser version, GL+1. Given the preservation of the spectrum during coarsening, the Laplacian spectrum of G1 is approximated by that of GI+1. The availability of G(+1 during the generation of G2 allows computing its principal Laplacian spectrum and subsequently conditioning the generation of G₁ on it. Specifically, we ac- complish this by computing the smallest non-zero eigenvalues and their respective eigenvectors of the Laplacian matrix L1+1 of G1+1. We then employ SignNet (Lim et al. 2022) to obtain node embeddings for nodes in G1+1. which are then replicated across nodes in the same expansion set to initialize Gi's s embeddings. This shared embedding feature also aids the model in cluster identifica- tion. Our Local PPGN model, while inherently capturing global graph structures, can benefit from explicit conditioning on spectral information. We adjust the number of eigenvalues I as tunable hyperparameter; when k = 0, node embeddings are drawn from an isotropic normal distribution.
3.6 PERTURBED EXPANSION
As noted, the given Definitions and are sufficient to reverse a contraction step with an appro- priate expansion and subsequent refinement step. However, we have observed that introducing an additional source of randomness in the expansion is beneficial for the generative performance of the model, particularly in the context of datasets with limited samples where overfitting is concern. Therefore, we introduce the concept of perturbed expansion, where in addition to the edges in É, we add edges between nodes whose distance in G is bounded by an augmented radius independently with given probability. A formal definition and an illustrative explanation of this concept can be found in Appendix
3.7 DETERMINISTIC EXPANSION SIZE
Our graph expansion method iteratively samples a cluster size vector e incrementally enlarge the graph. The process halts when v is entirely composed of ones, indicating no further node expansion necessary. However, this stochastic approach may not reliably produce graphs of predetermined size. To remedy this, we propose a deterministic expansion strategy, primarily applicable in cases of edge contraction where the maximum expansion size is two. In this strategy, v is treated as binary. We set the target size for the expanded graph at each expansion step and, instead of sampling v, we select the required number of nodes with the highest probabilities for expansion to reach the predefined size. Additionally, we introduce the reduction fraction, calculated one minus the ratio of node counts between the original and expanded graphs, as an additional input to the model during training and inference. More details discussed in Appendix G
7

---

Published as a conference paper at ICLR 2024
Planar Graphs (Pless
64, Ray
Model
Deg.J
Clus. J
Orbic 1
Spec. 4
Wavelet
Ratio
Valid 1
Unique
Novel
V.U.N.
Training set
0.0002
0.0310
0,0005
0.0038
0.0012
1.0
100
100
GraphRNN Yon 2018
0,0049
0.2779
1.2543
0,3459
0.1034
100
100
GRAN Lindar 2163
0.0077
0.0426
0.009
0,9075
0.0019
2.0
97.5
85.0
2.5
0..0
SPECTRE mars 2022
0.0005
0.0755
0.0012
0.0112
0.0059
3.0
25.0
100
100
25.0
DiCiress Vignare
0,0007
0,0780
0.0079
0.0098
0,0031
5.1
77.5
100
100
77.5
EDGE (Tinn Mi.
0.0761
0.7737
0.0957
BwR (DUPOONNT (11-00 al. 2025
0.0231
0.2596
0.5473
0.0444
0.1314
251.9
0.0
100
100
0.0
BICG (Da gt 21/0
0,0007
0,0570
D.0367
0,0101
0,0052
16.0
62.5
85.0
42.5
5.0
GraphGen (ayyll 2010
0,3328
0.2106
0.4236
0.0430
0.0989
210.3
100
Ours (0nc-bbot)
0.0003
0.0345
0.0006
0.0101
0.0030
1.7
67.5
100
100
67.5
Ours
0.0005
0.0626
0.0017
0.0075
0.0013
2.1
95.0
100
100
95.0
Stochastic Block Model (Pres
187, Pag
104)
Model
Deg.J
Clus. 4
Spec 4
Wavelet
Ratio
Valid
Unique
Novel
Training scl
0.0008
0.0332
0.0255
0.0027
0.0007
1.0
100
100
GraphRNN You nl. 2018
0,0055
0,0584
0,0785
0,0065
0,0431
14.7
5.0
100
100
5.0
GRAN di 2060
0.0553
0,0054
25.0
100
100
SPECTRE Mar e al. 2022
0.0015
0.0521
0,0412
0.0056
0.0028
2.2
52.5
100
100
52.5
DiGrress Viriac dre 200233
0.0018
0.0485
0.0415
0.0045
0.0014
1.7
60.0
100
100
60.0
BIGE
0.0279
0.1113
D/0854
0,0251
100
BwR (EDJSUNNT Daaaal 61
2025
0.0478
0.0638
0.1139
0.0169
0.0894
38.6
7.5
100
100
7.5
Bi0G (Dai c 2070
0.0012
0.0634
0.0667
0,0059
0.0370
11.9
10.0
100
100
10.0
GraphCen
2020
0,0550
0.0623
0.1189
0.0182
0.1193
48.8
5.0
100
100
5.0
Ours (00c- sbot)
0.0071
75.0
100
Ours
0.0119
0.0517
0.0669
0.0067
0.0219
10.2
45.0
100
100
45.0
Tree Graphi (riaws
64, Wong = 66)
Model
Deg.4
Clus. J
L
Spoc.
Warelet
Ratio J
Valid
Unique
Novdl
Training set
0.0001
0.0000
0,0000
0.0075
0.0030
1.0
100
100
GRAN Lino etoeetall 2020
0.1884
0.0080
0.0199
0.2751
0.3274
607.0
0.0
100
100
0.0
DiGress Vinna
0.0002
0,0000
0,0113
90.0
100
100)
EIGE Cuenn
0.2678
0.0000
0.7357
0.2247
850.7
7.5
100)
BwR
(50)=UNNT M et al. 2023
0.0016
0.1239
0.0013
0,0480
0.0388
11.4
0.0
100
100
0.0
BiGG
Dai 20A
0,0014
0,0000
0.0000
0.0119
0,0058
5.2
100
87.5
50,0
75.0
GraphCenn GGoyal
2020
0.0000
0.0000
0.0153
0,0122
100
Ours (one-shot)
0.0004
0.0000
0.0000
0.0080
0.0085
2.1
82.5
100
100
82.5
Ours
0.0001
0.0000
0.0000
0.0117
0.0047
4.0
100
100
100
100
Table 1: Sample quality on synthetic graphs
Proteins (feas.
300,
256)
Point Cleud CPean
3057 Rag = 1332)
Model
Deg.1 |
Clus.
Orbit
Spec 1
Wavelet
Ratio
Deg.
Clus.
Otbit 1 Spes.
Wivelet
Rario
Trininng se1
0,0083
0.0058
0.0033
0.0005
0.0005
1.0
010000
0.1768
0.004)
0,0043
0.0024
1.0
GigkkRNN el
2018
0.004
0.1475
0.5851
0.0152
0.0530
91.3
G0M
00M
DOM
0OM
G0M
O0M
GRAN (Lagneau 2004
0,0499
0.1234
0.3458
0.0125
0.0341
$7.5
0.0201
0.430
0.2625
0.0011
0.0456
18.8
SPECT Kus Astrimnt XC X02
0,0555
0.0843
0.0267
0.0052
0.0118
19.0
00M
00M
DOM
00M
00M
00M
DiGress [Vino o0 201-3
0,0041
0.0489
0.1266
0.0018
0.0065
18.0
00M
00M
DOM
0OM
G0M
00M
EDGE Lee a 20/40
0,1863
0
0.6756
0,1075
0.2371
399.1
0.486]
0.3298
1.020
0,4066
0,310
143.4
BwR (LDF ONV Unsmzit et 2023
0,1262
0,4202
0.4939
0,0702
0.1199
245.4
0.4927
0.4690
1,7200
0,2912
0.3915
133.2
BXGG
Dii al A1.7
0,0700
0.1150
0.4696
0/0067
0.0222
57.5
0..994
0.6035
0.363
0.159
0.09%4
38.5
Gingliee anydrer
5020
0,0159
0.1677
0.3787
0.0181
0.3477
53.5
000
000
OCT
00T
00T
OUT
Ous (one-siot)
0,0155
0.0711
0.6396
0.0026
0.3886
13.3
0UM
0OM
0OM
0OM
GOM 0
OUM
Ous
0,0330
0.0309
0.0147
0.0013
0.0090
5.9
0.0139
0.5775
0.0780
0,0055
7,0
Table 2: Sample quality on real-world graphs. All models achieve perfect uniqueness and novelty. Several models fail on the point cloud dataset due to memory limitations (OOM), and GraphGen is unable to generate the canonical string representations within a reasonable timeframe (OOT).
EXPERIMENTS
Our experiments evaluate three main aspects of our model: (1) its ability to generate graphs with structural properties similar to the training data on common synthetic graph generation datasets (pla- nar, SBM, tree); (2) its ability to scale to much larger real-world graphs (proteins and point clouds); (3) extrapolation to outoof-distribution graph sizes. We rely on the standard metrics, datasets and evaluation procedures introduced by Martinkus et al. 2022 Details on this and the hyperparameters we used are covered in Appendix !
Simple Graph Generation. In Table the most critical metric is the percentage of valid, unique, and novel graphs (V.U.N) in the generated set. Validity for synthetic graphs indicates the adherence to the defined properties, e.g. planarity or acyclicity. Uniqueness and novelty metrics report the diversity of the output, serving as an indicator for non-overfitting Our method demonstrates strong performance, surpassing our baseline, which operates without iterative expansion, but directly gen- erates the full graph using the diffusion model (Ours (one-shot)). The exception is the SBM dataset, where the inherent randomness of the graphs and the absence structure aside from large clusters, likely affects the results. Nevertheless, our model still attains satisfactory V.U.N. score. The first.
8

---

Published as conference paper at ICLR 2024
Extrapolation
Extrapolation
neleton vold & uneue
0.8
0.8
0.4-
Fraetion
0.4
48
112
Groph Size
Graph Size
Planar interpolation
Tree Interpolation
1.0
1.0
Rodton vale 5 Uniuu
0.6
0.6
0.4
0.0
0.0
12
48
64
80
112
128
144
80
96
112
12n
144
Graph Size
Graph Sizw
GRAN
DiCrmss
BIG
(onewshat)
Figure 3: Extrapolation and interpolation to out-of diitrr--iittibutioon graph sizes. The shaded area repre- sents the training size range.
five columns of the table show the maximum mean discrepancy (MMD) between the generated and test graphs for the degree distribution, clustering coefficient, orbit counts, spectrum, and wavelet coefficients. We summarize these metrics by the average ratio between the generated and training MMDs. Although DiGress is the overall best performer with respect to this metric, our method achieves competitive results and is the best for planar graphs.
The benefits our approach become clearer with larger, complex real-world graphs. In Table 2 we show model performance protein graphs with up to 500 nodes and point cloud graphs with up to 5037 nodes (see Table 6). In both cases, our method outperforms competitors by a large margin in structural similarity to the test set. Note that several methods unable to scale 5037 nodes.
Appendix H offers a runtime comparison, affirming our method's subquadratic scaling when gener- ating sparse graphs of increasing size. This section also includes theoretical analysis of the model's complexity. Sample graphs generated by our model can be found in Appendix!!
Extrapolation and Interpolation. We assess our model's capability to generate graphs with node counts beyond the training distribution through extrapolation (creating larger graphs) and interpo- lation (varying sizes within observed ranges). We use a planar and a tree dataset, each compris- ing 128 training graphs with sizes uniformly sampled from [32, 64) for extrapolation and from [32, 64] U [128, 160) for interpolation. Our evaluation involves generating graphs with 48 to 144 nodes, producing 32 graphs per size for validation and 40 for testing. We report the validity and uniqueness rates of generated graphs.
de that our method is uniquely capable of reliably extrapolating and interpolating to nut-of-distribution graph sizes across both datasets. We note that GRAN, DiGress and Ours (one shot) fail, general. generate larger graphs in contrast to their performance on smaller versions of the datasets (see Table Therefore, our experiment does not fully determine whether these methods fail because they cannot interpolateeextrapolate or because they are unable to generate larger graphs.
CONCLUSION
In this work, we present the first graph generative method based on iterative local expansion, where generation is performed by single model that iteratively expands single node into the full graph. We made our method efficient (with sub-quadratic complexity) by introducing the Local PPGN layer that retains high expressiveness while performing only local computation. We performed tests on traditional graph generation benchmarks, where our method achieved state-of-the-art results. Furthermore, to the best of our knowledge, method is the only one able to generate graphs outside of the training distribution (with different numbers nodes) while retaining the main graph characteristics across different datasets.

---

Published as a conference paper at ICLR 2024
REFERENCES
Andrea Agostinelli, Timo Denk, Zalán Borsos, Jesse Engel, Mauro Verzetti, Antoine Caillon, Qingqing Huang, Aren Jansen, Adam Roberts, Marco Tagliasacchi, et al. Musiclm: Generating music from text. arXiv preprint arXiv:2301.11325 2023.
Réka Albert and Alsert-László Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74:47-97, 01 2002.
Brian D.O. Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):31-3326, 1982. ISSN 0304-4149,
Maximilian Augustin, Valentyn Boreiko, Francesco Croce, and Matthias Hein. Diffusion visual counterfactual explanations. Advances Neural Information Processing Systems, 35:364-377, 2022.
Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. CoRR, 2107.03006 2021.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization, 2016.
Mihai Babiac, Karolis Martinkus, and Roger Wattenhofer. Discovering graph generation algorithms.
arXiv preprini arXiv:2304. /2895, 2023.
David Bieber, Charles Sutton, H. Larochelle, and Daniel Tarlow. Learning execute programs with instruction pointer attention graph neural networks. ArXiv, 12621, 2020.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, P000(10);100008, oct 2008
Zalán Borsos, Raphačl Marinier, Damien Vincent, Eugene Kharitonov, Olivier Pietquin, Matt Shar- ifi, Dominik Roblek, Olivier Teboul, David Grangier. Marco Tagliasacchi, et al. Audiolm: a language modeling approach to audio generation. IEEE/ACM Transactions Audio, Speech, and Language Processing, 2023.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs, 2022.
Ting Chen, Ruixiang Zhang, and Geoffrey Hinton. Analog bits: Generating discrete data using diffusion models with seff-conditioning, 2023a.
Xiaohui Chen, Jiaxing He, Xuhong Han, and Liping Liu. Efficient and segree-guided graph gener- ation via discrete diffusion modeling. ArXiv, 2305.04111, 2023b.
E. Cuthill and J. McKee Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th National Conference, ACM '69, pp. 157-172, New York, NY, USA, 1969. Association for Computing Machinery. ISBN 978 9781450374934.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative mod- eling for sparse graphs. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th In- ternational Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2302-2312. PMLR, 13-18 Jul 2020.
Alex O. Davies, Nirav Ajmeri, and Telmo M. Silva Filho. Size matters: Large graph generation with higgs, 2023.
Nathaniel Diamant, Alex M. Tseng, Kangway V. Chuang, Tommaso Biancalani, and Gabriele Scalia. Improving graph generation by restricting graph bandwidth, 2023.
Paul Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymen without align- ments. Journal of molecular biology, 330:771-83, 08 2003.
10

---

Published as a conference paper at ICLR 2024
Chenpeng Du, Yiwei Guo, Feiyu Shen, Zhijun Liu, Zheng Liang, Xie Chen, Shuai Wang, Hui Zhang, and Kai Yu. Unicats: unified context-aware eet-to--peech framework with contextual vg-diffusion and vocoding. arXiv preprint arXhv:2306.075477 2023.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, 2021.
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. The World Wide Web Conference, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric, 2019.
Jeremia Geiger, Karolis Martinkus, Oliver Richter, and Roger Wattenhofer. Automating rigid origami design. In Proceedings of the Thirty-Second International Joint Conference on Artifi- cial Intelligence, IJCAI-23, pp. 5815-5823, 2023. Al and Arts.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: scalable approach to domain- agnostic labeled graph generation. In Proceedings of The Web Conference 2020. ACM, 2020.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs, 2019.
Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to-image synthesis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10696-10706, 2022.
Yinglong Guo, Dongmian Zou, and Gilad Lerman. An unpooling layer for graph generation, 2023.
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffu- sion models for graphs benefit from discrete state spaces, 2023.
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaäl Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 15, Pasadena, CA USA, 2008.
Gecia Bravo Hermsdorff and Lee M. Gunderson. A unifying framework for spectrum-pressevinng graph sparsification and coarsening. ArXiv, 1902.09702, 2019.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models, 2020.
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First
steps. Social Networks, 5(2):109-137) 1983, ISSN 0378-8733.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:1 34:12454-12465. 2021.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure
Leskovec. Strategies for pre-training graph neural networks, 2020.
John Ingraham, Max Baranov, 7ak Costello, Vincent Frappier, Ahmed Ismail, Shan Tie, Wujie Wang, Vincent Xue, Fritz Obermeyer, Andrew Beam, and Gevorg Grigoryan. Illuminating protein space with programmable generative model. bioRxiv, 2022.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autocncoder for molecular graph generation. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2323-2332 PMLR, 10-15 Jul 2018.
Wengong Jin, Regina Barzilay, and T. Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning, 2020a.

---

Published as a conference paper at ICLR 2024
Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Con- ference Artificial Intelligence and Statistics,, volume 108 of Proceedings of Machine Learning Research, pp. 4452-4462 PMLR, 26-28 Aug 2020b.
Jachyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with cestination-prediicit diffusion mixture. 2023.
Mahdi Karami. Higen: Hierarchical graph generative networks, 2023.
Tero Karras, Miik Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models, 2022.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation, 2023.
Manoj Kumar, Anurag Sharma, and Surinder Kumar. A unified framework for optimization-based graph coarsening. J. Much. Learn. Res., 24:118: 1t:11881-11::00 2022.
Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Surinder Kumar. Featured graph coarsening with similarity guarantees. In International Conference on Machine Learning, 2023.
Maksim Kuznetsov and Daniil Polykovskiy. Molgrow: A graph normalizing flow for hierarchical molecular generation, 2021.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L.. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks, 2020.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning, 2022.
Stratis Limnios, Praveen Selvaraj, Mihai Cucuringu, Carsten Maple, Gesine Reinert, and Andrew Elliott. Sagess: Sampling graph denoising diffusion model for scalable graph generation, 2023.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows, 2019.
Andreas Loukas. Graph reduction with spectral and cut guarantees. J. Mach. Learn. Res., 20: 116:1-116:42, 2018.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. ArXiv, 1802.07510, 2018
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks, 2020.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators, 2022.
Karolis Martinkus, Jan Ludwiczak, Kyunghyun Cho, Weishao Lian, Julien Eeffaacce-Vnaassee Isidro Hotzel, Arvind Rajpal, Y. Wu, Richard Bonneau, Vladimir Gligorijević, and Andreas Loukas. Abdiffuser: Full-atom generation of in-vitro functioning antibodies. ArXiv, 2308.05027. 2023.
Marion Neumann, Plinio Moreno, Laura Antanas, R. Garnett, and Kristian Kersting. Graph kemels for object category prediction in task-dependent robot grasping. In Mining and Learning with Graphs, 2013.
Anh Tuan Nguyen, Tung Thanh Nguyen, Hoan Anh Nguyen, Ahmed Tamrawi, Hung Viet Nguyen, Jafar M. Al-Kofahi, and Tien Nhut Nguyen. Graph-based -rieet-oriented, context-sensitive source code completion. 2012 34th International Conference on Software Engineering (ICSE), pp. 69-79, 2012.
12

---

Published as a conference paper at ICLR 2024
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. 2020.
Hamed Shirzad, Hossein Hajimirsadeghi, Amir H. Abdi, and Greg Mori. Td-gen: Graph generation with decomposition, 2022.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders, 2018.
Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics, 2015.
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations, 2021.
Zhicong Tang, Shuyang Gu, Jianmin Bao, Dong Chen, and Fang Wen. Improved vector quantized diffusion models. arXiv preprint Siki::2205..60000 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need, 2023.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation, 2023a.
Clément Vignac, Nagham Osman, Laura Toni, and Pascal Frossard. Midi: Mixed graph and 3d denoising diffusion for molecule generation. In ECML/PKDD, 2023b.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural Compu- tution, (3(7):1661-1674 2011.
Nisheeth K. Vishnoi. Lx b. Foundations and Trends@ in Theoretical Computer Science, 8(1-2): 1-141, 2013. ISSN 1551-305X.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful graph neural networks?, 2019.
Qi Yan, Zhengyang Liang, Yang Song, Renjie Liao, and Lele Wang. Swingnn: Rethinking permu- tation invariance in diffusion models for graph generation, 2023.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn Generating realistic graphs with deep ruto-regressive models, 2018.
13

---

Published as a conference paper at ICLR 2024
A INVERT COARSENING BY EXPANSION AND REFINEMENT
In this Appendix, we show that each coarsen graph (according to Definition can be inverted with specific expansion and refinement step.
Let G = (V.&) ) be an arbitrary graph and P connected subgraph that induces partitioning of its node set. Furthermore, let G. (Ve, &.) G(G,P) denote the coarsened graph according to Definition 3 In the following, we construct an expansion and refinement vector that recovers the original graph G from its coarsening Ge.
We start with the expansion by setting the vector NIPl to
pppl
1ioe for all V(v) P.
v) denote the expanded graph as per Definition 1 (or Definition 4 It is important to note that the node of G and G. possess the same cardinality. Thus, can establish a bijection ;o V + Ve between them, where the i-th node in the p-th partition of P is mapped to the corresponding node y(P.) E V. within the expanded graph. This construction leads to the edge of G. being superset of the one of the original graph G. To why, consider an arbitrary edge e(f5) E E. If both v(t) and n(6) belong the same partition y(v) P, they contracted common node v(P) in Ge. When expanding u(P) to set of |D(e)| nodes in Ge. by construction of the intercluster edge set in Definition (resp. Definition 4p. all |>(e) nodes are connected in Ge- On the other hand, if y(t) and (()) lie in different partitions V(v) and y(a), respectively, an edge in the original graph implies that the partitions representing the nodes v(P) E V. and v(9) V. are connected G.. Consequently, when expanding w/()) and vl9), all |)0) nodes associated with u()) are connected to all |>(()] nodes associated with n.(4) in Ge- Specifically, v(v(()) and ((P()) are connected in G.-
Let G. =
Therefore, for the refinement step, we define the vector e E &el as follows: given an arbitrary ordering the edges &,, let e(i,) &, denote the i-th edge in this ordering, we set
{
-( ()) E
eli]
(5)
otherwise.
As per Definition 2 the refined graph is then given by G, = G(Ges C(ā(G v), e), which is isomorphic to the original graph G.
14

---

Published as a conference paper at ICLR 2024
B PERTURBED GRAPH EXPANSION
The following definition formalizes the concept of randomized graph expansion, which is a gen- eralization of the deterministic expansion introduced in Definition I concept is provided in Figure
A visual representation of this
Definition 4 (Perturbed Graph Expansion) Given graph G = (V,E), cluster size vector v E N", a radius E N, and probability 0 S 1, the perturbed expansion G is constructed as in Definition ! and additionally for all distinct nodes v(n), v/9) E V whose distance in G is at most r, we add each edge e e(pi95) independently to & with probability p.
Perturbed Expansion
G
vi)
Figure 4: Depiction of perturbed expansion. The graph G₁ is expanded into G utilizing the cluster size vector aligned to the node features. Deterministic expansion components are represented by linear black edges, whereas curved red edges showcase supplemental edges implemented for radius of r = 2 and probability of p = 1. With < 1, a subset of these edges would be randomly excluded.
15

---

Published as a conference paper at ICLR 2024
C SPECTRUM-PRESSRRIIN COARSENING
The work Loukas 2018) presents a multi-level graph coarsening algorithm designed to reduce the size of graph while ensuring that the Laplacian spectrum the coarsened graph closely approxi- mates the spectrum of the original graph. Since the Laplacian spectrum captures crucial structural properties graph, this implies that fundamental structural properties of the original graph, such (normalized) cuts, preserved by the coarsening. The proposed reduction scheme aligns well with our framework, as it defines graph coarsening in a similar manner to Definition 3 and the selection of subgraphs for contraction involves computing cost for each contraction set.
Let us now summarize the key aspects of the proposed framework and illustrate how we adapt it to setting. We consider graph G (V,E) with nodes and Laplacian L. Let P (D(1) "i.......... D(*)} be partition of the node set V into non-overlapping, connected sets, and Ge (Ve, Er. = G(G, P) the coarsened graph according to Definition 3 with n, nodes.
Comparing the Laplacian matrices of G and G. requires us relate signals E RR" G' to signals Ie E RT on G.. For this we associate a projection matrix P E R and it's corresponding Moore-Penross pseudoinverse p+ E nxne with P, defined as
if O E viv)
{1
if v(() E V(n)
Plp, i]
pt [+[ppp)
otherwise
0 otherwise
For graph Laplacian L and this choice of P. Loukas Laplacian of the coarsened graph G. with weight matrix
2018) shows that Le LP
is the
Welp.g]
Σ
Wig
(6)
To measure the similarity between the Laplacians and Le. Loukas (2018) introduces the following fairly general notion of restricted spectral approximation.
Definition 5 (Restricted Spectral Approximation) Two matrices L E Raxn and Le p LP+ R are (V, ci-simiaar, with V being a k S ne S n-dimensional subspace of R", if there exists 0 such that
|| - P* P Se||=]] Vo E V,
where |0]| Vx Læ denotes L-induced semi-norm.
When V is chosen the span of the eigenvectors associated with the i smallest non-zero eigen- values of L, Uı = spannu,,.... un span then L and L, are (U,, e)-similar, Loukas) (018) shows that the smallest non-zero eigenvalues of L, are close to the ones of L, and the lifted cigenvectors PT u, are aligned with the original eigenvectors u.
C.1 LOCAL VARIATION COARSENING
Loukas (2018) further proposes a multi-level graph coarsening algorithm to construct a coarsening sequence Go, GI...., with each coarse graph G, possessing Laplacian L, with high spectral similarity to the original Laplacian L associated with G, according Definition 5 While the procedure the original work is quite general and allows for any choice V. let us commence by considering the case where V is chosen as the span of the k eigenvectors associated with the smallest non-zero eigenvalues of L. In this case, for each coarsening step, the algorithm first computes local variation cost for each contraction set and then contracts disjoint sets with small cost. The local variation cost of a contraction set C C V is defined as
mi A
Cv (G,C)
C
SPT denotes the transpose of the Moore-Penrose pseudoinverse of P.
16

---

Published as a conference paper at ICLR 2024
Here, I1 = =I- Pe Pe is the complementary projection matrix when contracting solely the nodes in C. Le is the Laplacian of G with modified weights We. given by
W [i 2 W
if u wl) EC
Weli,j]
if of Cl, & C otherwise.
A,- a matrix allowing us to evaluate the cost only on the selected Laplacian subspace Ug. is defined recursively as
A = ULA
= = B L,B:)
A
with B, = P.P:- ... A1 being first-level matrix Ao left-multipied by the projection matri- ces P. of all coarsening steps up to level
With this construction, holds that the Laplacian of the resulting coarsened graph G₁ is (Uk, c)- similar to the Laplacian of with S II' + o;) - 1, where o; bounds the error introduced by the i-th coarsening step as
I A1-1 of
CEP:
with P; being the node partitioning used the i-th coarsening step.
C.2 ADAPTING LOCAL VARIATION COARSENING TO OUR SETTING
A noteworthy distinction between setting and the one investigated by Loukas (2018) lies in the usage of unweighted graphs. Therefore, we assign a weight of 1 to each edge in the original graph G. For coarsening sequence G Gu, G1...., according to Equation 6 With this, all the quantities required to calculate the local variation cost are readily available and it be employed instantiate the cost function in Algorithm
then maintain sequence of weight matrices
An important point to mention is that while the method proposed by Loukas 2018 operates deter- ministically, our approach introduces element of randomness.
17

---

Published as a conference paper at ICLR 2024
D COARSENING SEQUENCE SAMPLING
This section describes the methodology used to sample a coarsening sequence π E (G) for given graph G. Importantly this implicitly defines the coarsening sequence probability density function [( G).
Our approach for sampling a coarsening sequence E [I= from q( G) is presented in Algo- rithm At each coarsening step I, we assess the cost of all contraction sets F(Gr), where lower cost indicates a preference for contraction. This cost computation based on the current graph Gj and may incorporate information from previous coarsening steps. While there are no inherent restrictions on the cost function, it should be efficiently computable for practical purposes. Sub- sequently, we randomly sample reduction fraction. Then, employing greedy and randomized strategy, we select a cost-minimizing partition of F(Gr) that achieves the desired reduction fraction upon contracting the graph as per Definition This partitioning procedure is detailed in Algo- rithm 2 with Definition
The resulting contraction sets are used to construct the coarsened graph G in accordance
Note that our procedures are designed with a heuristic approach that allows alternative choices. Various components of the procedure remain parametric, such as the contraction family F, the cost function c, the range of reduction fractions [Pmin, (mma), and the randomization parameter X
Practical Considerations Depending on the structure of the graph, may not always be feasible to achieve a non-overlapping partitioning of the node set that satisfies the desired reduction fraction. Our empirical investigations indicate that such circumstances rarely arise in the examined datasets, provided that Pmax is not unreasonably large. In the event that such situation does occur, we choose to proceed with the partitioning achieved thus far. Furthermore, to mitigate an imbalance of numerous small graphs in the coarsening sequence, we deterministically set the reduction fraction P to Pmax when the current graph contains fewer than 16 nodes. should be noted that during sample coarsening sequence from the dataset graph but only consider the
the training phase, graph at a random level within the sequence. Consequently, in terms of practical implementation, Algorithm does not return the coarsening sequence x, but instead provides coarsened graph along with the node and edge features necessary for model training. To optimize computational efficiency, upon computation of the coarsening sequence, we cache its elements, select level at random, and return the corresponding graph and features, subsequently removing this element from the cache. Recomputation of the coarsening sequence for a specific graph necessitated only when the cache is exhausted.
Hyperparameters all the experiments conducted described in Section 4 we use the Local Variation Cost (presented in Appendix C with preserving eigenspace size of A = 8 as the cost function c. The range of reduction fractions set as [Pmiu- Pimax] = 10.1, 0.3). The randomization parameter X is assigned value of 0.3. Moreover, edge contractions are used for all graphs, i.e., F(G) = E, for a graph G = (V,E).
D.1 COST FUNCTION ABLATION STUDY
We assess the influence of the cost function e on the generative performance of our model. In this regard, we compare the Local Variation [7 with its specified parameters against a random cost function, where each contraction set is assigned a uniformly sampled random cost from the range [0, 1]. The randomization parameter À is set to 0 for the random cost function. Otherwise, the prescribed parameters are used for both cost functions. Following this comparison, we train our model on the planar, tree, and protein datasets described in Section 4 We report the average ratio between the generated and training set MMD values. For the synthetic datasets, we additionally report the fraction of valid, unique, and novel graphs among the generated graphs. The results of the experiments are shown in Table 3 A key observation from the results is that the Local Variation Cost demonstrates a slightly superior performance over the random cost function across all evaluated datasets. This suggests that while the model's performance, is not an indispensable factor and alternative cost functions could potentially be suitable.
coarsening contributes positively
18

---

Published as a conference paper at ICLR 2024
Algorithm 1 Random Coarsening Sequence Sampling: This algorithm demonstrates the pro- cess of Random Coarsening Sequence Sampling, detailing how a coarsening sequence sampled for a given graph. Starting with the initial graph, it iteratively computes the costs of all possible contraction sets, samples a reduction fraction, and uses a greedy randomized strategy to find cost- minimizing partition of the contraction sets. Then coarsening of the preceding graph is added to the coarsening sequence, according to Definition 3 and the process repeats until the graph is reduced single node.
Parameters: contraction family F, cost function c, reduction fraction range [pmin Pmax
Input: graph G
Output: coarsening sequence
G2) E (G)(G)
1: function RNDREDSEQ(G)
2: Go = (Vo, E0) +
3:
(Go)
4:
I+0
5:
while [V-1| do
6:
1 1+1 p Uniform( (pmin: Pmmxx)
7:
random reduction fraction
8:
f + c(., Go. (P1,.... Pt-1))
cost function depending on previous contractions i> reduction amount
9:
m + pp. 1--1l
10:
Pi + RADDREEEMMIMCOSTPATTTFGGGG...L
Vi - (of")) D( E Pt}
D new node
& - lef E--1 E1-1,
Hist
(
v/2) .011 1100
new edge set
G: - &i)
14:
end while
return (Go...., Gt)
Return coarsening sequence
16: end function
This algorithm represents Random- ized Greedy Min-Cost Partitioning, where the cheapest contraction set is selected iteratively from the candidate sets. The selected set, with probability 1 X, is discarded and the process contin- ues with the next cheapest set. Conversely, with probability x, the set is added to the partitioning removed from the remaining candidates. Termination occurs when the partitioning contains at least m sets or there are no remaining candidates.
Algorithm Randomized Greedy Min-Cost Partitioning:
and all intersecting
Parameters: randomization parameter À E [0, 1]
Input: candidate contraction sets C = ()(1) ..... V(n)), reduction amount
Output: partitioning P = (p()),...,,,()) S C. with v(.) n p(i) @ for i + and EvEr |V] IPI 2 m
function RADGRIEDYMIINCOSPPARTC,,,,
2: P+0
3: while EvEr VI |P] < and C + do
4: repeat
5:
V +- arg minvec f(V)
6:
C C- C {V*
7:
b b~ Bernoulli(A)
8:
until b 0 or C
9:
P - PU C E Vnv= = 0)
10:
11:
end while
12:
return P
13: end function
19

---

Published as a conference paper at ICLR 2024
Planar graphs
Tree graphs
Proteins
Cost
Ratio
V.U.N. t
Ratio +
V.U.N. f
Ratio +
Local Variation
2.1
95.0
4.0
100
5.9
Random
3.9
85.0
6.2
100
8.2
Table 3: Ablation study the cost function c.
20

---

Published as a conference paper at ICLR 2024
E DENOISING DIFFUSION
Denoising diffusion models represent a class of generative models initially proposed for image gen-
eration (Sohl-Dickstein al. 2015 Ho et al., 2020) and subsequently adapted for various data modalities, such as audio (Du et al. 2023 Borsos et al. 2023 Agostinelli et al. 2023 text (Austin
al.
2021 Hoogeboom et al. 2021). discretized images (Gu et al. 2022 Tang et al. 2022 Au-
gustin et al. 2022: Hoogeboom et al. 2021), and graphs (Vignac et al. 2023a Haefeli et al. 2023).
exhibiting exceptional performance across domains. These models founded on the fundamental concept of learning to invert an iterative stochastic data degradation process. Consequently, denois- ing diffusion models comprise two main components: (1) a predefined fixed forward process, also known as the noising process {2x [z:)/=o which progressively transforms samples drawn from the data generating distribution 2g = x ~ p(x)) into noisy samples 24 ~ p(x:). with the level of degradation noise increasing as progresses; and (2) trainable backward process, referred to as the denoising process, which aims to reverse the effects of the noising process. The construction of the forward process ensures that the limit distribution p(zr) is both known and simple, for example, a Gaus- sian, thereby allowing for easy sampling. During inference, pure noise samples are drawn from this distribution and subsequently transformed by the denoising process to obtain samples following the data-generating distribution p(z).
E.1 GENERATIVE MODELING WITH STOCHASTIC DIFFERENTIAL EQUATIONS
Song et al. 2022 introduce continuous-time formulation of the diffusion model, in which forward and wack processes are described by stochastic differential equations. In this summary. we outline the general framework along with specific instantiations of its components and improvements proposed by Karras et al.] (2022). The same framework setup is adopted in the work of Yan et al. 22033
The fundamental concept involves modeling a continuous-ting indexed diffusion process {a; To as the solution to an Itō stochastic differential equation of the form
dæ; = fæ t)dt + g(f)dw, where f. and g are the drift and diffusion coefficients, respectively, and is a standard Wiener process. Different choices of f and g lead to distinct diffusion processes with varying dynamics. We adopt the variance exploding setting, where f(x,, t) and g(t) do do((c) for a time-dependent de
noise scale (t). Consistent with Karras al. 2022 select (t) to be linear in t. This leads to the following forward process:
dæ. v 22dd..
When integrating from time 0 to I, the corresponding transition distribution is given by:
p(a, mn) N( mp, 12 T).
(10)
The stochastic trajectory of sample behaving according to g but with reversed time direction, can be described by a stochastic differential equation too (Anderson 1982
dx. = (x+, t) - g(t)²Va,, log (og)())))dt + (())d
(11)
With the prescribed instantiations of f and g. the backward process becomes
dæ; 2t æ, log p(x;) + 22dw..
(12)
Here, denotes Wiener process with reversed time direction, i.e., from T to O. We get generative model, by simulating this process from time 7 to 0, to transform a sample from the prior distribution p(ær)) into one that follows the data distribution p(æto).
Denoising Score Matching Simulating the backward process necessitates evaluating the gradient of the log-density Va, log p(x,( As this gradient is generally intractable, we train model to approximate it using denoising score matching. This training principle is based on the insight that zo) with respect to E; can be expressed as:
conditioned on F., the gradient of logp(zz
20 3t
V my p(x, xo))
(13)
(2
21

---

Published as a conference paper at ICLR 2024
of Vincent 2011) proof that for fixed the minimizer So. (xx)
E
So(wi)
30 Zt
(14)
p( p( (20)
t²
satisfies Sg- (a:) V ((4)) almost surely.
Instead of approximating the score directly, Karras et al. (2022) train a denoising model Da( (,, t)
to reconstruct 2o from Zy- The joint training objective for all is given by:
E 8
A(
E
E
[ 1) moll
(15)
Here, A: [0. T R2, is a time dependenn weighting function, and is sampled such that In()) [ Pata) (details in Table 4 The score can then be recovered from the optimal denoising model Dā as n,, log p(x,) D (z,, xtt/t²
Preconditioning Instead of representing Da directly neural network, Karras et al. (2022) pro- pose preconditioning a network F'g with time-dependent skip connection to improve the training dynamics. Furthermore, they aim to achieve uniformity in the variance of the input and output of the network by employing appropriate scaling:
Da(ær, ()
cakip (1)x, + Cout (()))((
Weighting functions are summarized in Table
Self-conditioning Sampling from the diffusion model is an iterative procedure, in which the de- noising model iteratively queried construct samples ze from æt, for t' < t. [Chen al. (2023a) propose to additionally condition Da on previous estimates ăæ for improved sample quality. We observed that this improves the generative performance the model and thus adopt this technique in our work. Consequently, we augment the denoising model with an additional input
Do (mr, á, t) Cskip() (t)aa + Coal (B) Fo (Can (f) (t) t).
During training, given a noisy sample It. we then set a = O with 50% probability, and a Do 0,t) t) otherwise. Note that in the latter case, gradients are propagated through & During sampling, we set a to a previous estimate.
Sampling Once the denoising model trained, we can compute the gradient of the log-density and simulate the backward process, starting from sample from the prior distribution p( ((r)) Stochastic sampling based on Heun's 2nd order method was proposed by Karras et al. (2022). The procedure, combined with self-conditioning, is summarized in Algorithm Notably, this algorithm is identical to the one presented in Yan et al. (2023).
Parametrizing Graph Expansion We use this framework to model the conditional distribution po 21-1) over the node and edge features required to refine and subsequently expand the graph G.. For this, continuous representations of the node and edge features are required. For our experiments, where both node and edge features binary, represent 0 values as -1 and 1 values as 1. Let (o and (e:)o denote the corresponding continuous representations of the node and edge features. We instantiate the diffusion framework jointly over these features. should be noted that as the diffusion process adds noise independently to each dimension, this is equivalent to organizing the node and edge features in single vector æ = [v.e] E [-1, 14 +ni that is then used in the diffusion framework.
We further instantiate the denoising model Da. specifically its preconditioned version, with graph neural network GNN, (such as our proposed Local PPGN model) that operates on the graph Gi. This can be expressed as:
Fo &, 1) = GNNo(((())e. (e:),), [6r, ēi), t, Gr).
Here, (vi) and (e:), denote noisy samples of the node and edge features, respectively, and a [6), é,] represents a previous estimate of the node and edge features that concatenated to the input of the GNN.
22

---

Published as a conference paper at ICLR 2024
Algorithm SDE Sampling: This describes the sampling procedure by simulating the backward process using given denoising model.
Parameters: number of steps N, time schedule {4:)/= noise addition schedule (1
Input: denoising model Dg
Output: sample æ [1l ei]
I: function ADESAM)L
2: I ~ N(0, of
b Sample from prior
3:
I ++0
4:
for = 1,...,,.. N do
5:
~ NO,, S muise I) i t t + %/t
6:
v 122 f7e
7:
Add noise
8:
â - Do @z, .t,
D Denoise
9:
d - (ē - 0)/
Compute gradient
10:
a - x + (t,+1 F)d
> Euler step from to f,+1
11:
if 41 > 0 then
12:
$ <- Do (r. & 1++1)
b Denoise Compute gradient Second order correction
13:
d' (x 2)) li+1
14:
H (t1+1 - t) (d d')
15:
end
end for
17: return x
end function
For given expansion G2 of a reduced graph with target node and edge encodings dy and et, during training, we sample time-step I, construct noisy sample æ; æo + | 6, with N (0, I), and optimize the model parameters by minimizing
loss between the prediction and the target ato [u,, ei]- Overall, training involves sampling coarsening sequence out of which random level / selected. Subsequently, noisy sample is constructed and the model is trained to denoise matching. It is known to be equivalent to reweighed variational bound (Ho et al. 2020). As such, our training procedure can be interpreted maximizing weighted lower bound of random terms in Equation 3 Algorithm 4 summarizes the loss computation for given node and edge features vy and e, and denoising model Da that is assumed to be instantiated with a graph neural network GNN, operating on underlying graph Gi-
it. The objective in 15 is referred to as denoising
T data = 0.5
7
min 0.002
max
Constants
P -12
Pad 1.2
meam
Simin 0.05
Simax 50
Spoise 1.003
Schum 40
Cin(t)
Crarl (1)
Weightings
oi ++"
Va +
Cskip (t)
aas
(teir()) -
a +12
Schedules
4 (amax
(amin"
Tmax ) 7 1 St: Sua
min
Samm
V2 1) N
N
Table 4: Summary of hyperparameters for the diffusion process.
23

---

Published as a conference paper at ICLR 2024
Algorithm Diffusion loss: This describes the loss computation for given node and edge features
V; and et.
Input: node and edge features it and et, denoising model De
Output: trained model parameters 0
function DIFFUSIONL
et, Dg)
2:
(vt)o < ENCODE( vn)
D. Encode node features
3: (ei)o <- ENCODE(e:)
Encode edge features Sample noise level
4:
In(() (P Paa)
5:
if 1, where b (ermoulli(055) then
6:
(e:); (ei)o + with N.
7:
(vi): - (v:) t with NN I)
8:
é, Do((())) (e))), 0, 0),t)
Get self-conditioning estimates
9:
clip gradients of and
else
11:
0, é + 0,0
end
13:
(ei) + (ei)o + c, with e ~ I)
(v:), (V))0 tt with ~ NO.
15:
D. Denoise
16:
return (w))l l -
17: end function
24

---

Published as a conference paper at ICLR 2024
F GRAPH NEURAL NETWORKS
A key element of our generative methodology is the neural architecture, employed to parameterize the denoising model. This architecture necessitates numerous desirable characteristics: it should be expressive enough to adequately model the complex joint distribution of node and edge features, maintain invariance to the permutation of nodes, and sustain a low computational expense. The importance of this final attribute is underscored by iterative expansion strategy, which frees us from the need to model a distribution over all conceivable O(n²) node pairings. As a result, our objective is to identify model that scales rate less than quadratic with respect to the total number of nodes.
Despite the rich literature on graph neural networks, addressing all these requirements simultane- ously presents a considerable challenge. Message passing GNNs, although linear in complexity with respect to the number of edges, are shown be no more expressive than the I-Weisfeiler-Lehman test (Xu et al. 2019). Additionally, handling fully connected graphs effectively is a hurdle for them that might impede the processing of locally dense expanded graphs (Definition D In contrast, higher-order GNNs, while being more expressive, come with elevated computational costs. Our investigation featured various architectures, including message passing GNNs, transformer-based model advocated by Vignac et al. (2023a), and PPGN (Maron et al. 2020). Our experimentation revealed that PPGN performed exceptionally well, although being computationally expensive.
F.1 PROVABLY POWERFUL GRAPH NETWORKS
Maron et al. 2020) introduce PPGN, a permutation-equiivriaate graph neural network architecture.
The PPGN possesses provable 3- WL expressivity, which is categorically stronger than message passing models and operates on dense graph representations.
Given a graph embedding H Ruxaxh with H[i.j] E being the h-dimensional embedding of the ordered edge (i,j). PPGN layer updates the graph embedding as follows: Two separate
multilayer perceptrons, termed MLP; and ML.P are applied along the third axis of H to compute two third-order tensors M,, M2 gnxaxx i.e., for i E [ra]:
M [ MLP (H (1)))
(16)
M2 [ = 2 (1))
(17)
Subsequently, an element-wise matrix multiplication yields M m This is computed with : M, [3:3;dd] Ma(:;;, d] for each d E [M] Equivalently, this operation can be expressed as:
M
M, (i. M2 Σ kE(n)
(18)
where i,j [n]] and @ denotes the element-wise multiplication. Lastly, the updated graph embed- ding, represented as H' is obtained using third multilayer perceptron, MLPs, by setting for each j E [m]:
H' [ = M M(.,))),
(19)
where
|| signifies the concatenation operation.
F.2 LOCAL PPGN
In devising our model, we recognized that the graphs of our interest are sparse, a common quality among many real-world graphs. Additionally, expanded graphs (Definition ( are locally dense with fully interconnected clusters but globally sparse. Hence, our objective is to construct a model that is expressively local but globally sparse. Our proposed Local PPGN which is comparable the PPGN architecture for fully connected graph and a message passing GNN for a graph devoid of triangles, appears to strike a favorable balance between expressivity and complexity.
The fundamental operation of our Local PPGN layer is an edge-wise message passing mechanism.
It assumes underlying directed graph d (V, E. where V is the set of nodes and E is the set
25

---

We begin our analysis of this layer by exploring the sets of messages subject Published as a conference paper at ICLR 2024
LocalPPGN Messages
Figure 5: Illustration of a directed graph with self-loops. In the following, we list the update formula for three representative edge embeddings:
(h')0,) =y (1.),,, (h h hO.2) @ (h0.2) (211)) (h0.3, (00.,, (h/) = =y (1.).) 6 ( (1.) h 213) + (1012) h (2.3)) @ (h(1.3) / h.)))) (h')(3.4) (113.14 Φ (3.4) h (4.1))
of directed edges. The emebeddings (i.) E R² associated with the edges (i.j) E E are updated as follows:
(h1)(1)) =y hiw)) UMMEN- (el0))
+
(hlitt), (hll)),
(20)
Here, the operator + represents a inttuutttiooninvaiiin and differentiable aggregation operation. The functions and y are arbitrary differentiable functions that can be instantiated, for instance, multi-layer perceptrons. ~V(((()) denotes the set of nodes with outgoing edges to o(1), and (v((0) denotes the set of nodes with incoming edges from 1.)
Aggregation Sets to aggregation. For any given node v(()) E V and its associated embedding h (f.1), the aggregation set includes the message ((((t,)) h (8.0)). For each neighboring node v(t), the set also contains the message (f.)), 16(.)). For a directed edge (i-)) E E. the aggregation set comprises of the mes- sage (t.(),) 1 (65)). Additionally, each triangle (w(6), o((t), x00) present in the graph contributes the message (i.(k.)) h (RJ)) to the aggregation set. Figure provides illustration of the message sets that undergo aggregation for a representative graph.
The complexity of this layer, from the above amalysis, scales linearly with the number of edges and triangles in the graph. For graph lacking triangles, the complexity therefore scales linearly with the number edges. Conversely, for fully connected graph, scales cubically with the number of nodes.
Complexity
Relation to PPGN With + instantiated as sum, d and y with multi-layer perceptrons as ((x, y) MLP (ar) & MLP2(y) and 7 y) ML.P; 3 (ær y), we recover the PPGN layer as delineated in Section Fl for a fully connected graph. To discern this, one may compare the scheme 20 with our message passing-liks formulation of the PPGN layer in Equation [8
When applied to general graph, one interpretation of our layer's effects is the application of the PPGN layer on each fully connected subgraph within the main graph. This was the initial impetus behind our design choice; we aimed to fuse the expressivity of PPGN with the efficiency of message passing GNNs. Given that our graph generation method only introduces local modifications each step, theorize that this level of local expressivity is sufficient.
26

---

Published as a conference paper at ICLR 2024
F.3 ARCHITECTURAL DETAILS
We instantiate our Local PPGN model with succession of the prescribed layers, each responsible for transforming dhidden- -daiddenddmensionnl -imensional embedding into another of matching dimensions. For every layer, set + as count. We set Φ(x, y) = MLP1 (x) @ MLP2(y), where both MLP1 and MLP₂ are multi-layer perceptrons, accepting inputs of dimension duidden and producing outputs of dimension dPPGN. We define (x,, y) = MLP3 3 (æ: y), where MLP3 is a multi-layer perceptron with an input dimension of dhidden + dpPGN and an output dimension of dhidden.
and normalize by division through the square root of the total message
MLP Architecture Within our model, all multi-layer perceptrons consist of two hidden layers. The first has daidden neurons, while the second matches the output dimension. Following each hidden layer, a layer normalization (Ba et al. 2016) and a ReLU activation function are applied.
Input Embeddings We unify the node, edge and global features (diffusion time step, reduction fraction, target graph size) into a common -ombb--ddmnioona space. Sinusoidal Positional Encod- ings (Vaswani al.) (023) are utilized for discrete target graph size embedding, whereas linear pro- jections are used for the remaining features. Global features are replicated for each node and edge in the same graph and are appended to the respective node edge features. The initial given node em- beddings, as outlined in Section 3.5 are also concatenated to the node embeddings. Similarly, given node embeddings corresponding
the edge's 's endpoints are joined with the edge embedding. Each embedding feature is subject to independent dropout with 0.1 probability before being projected to dnidden dimensions via linear layer.
Final output features for each node or edge are obtained by concatenating the initial em- bedding and all intermediate embeddings (i.e., outputs of every layer), applying dropout with 0.1 probability and projecting these features to the desired output dimension using a linear layer.
Output
SignNet Our methodology incorporates the SignNet model (Lim et al. 2022) for procuring node emheddings from a given graph using the principal spectrum of its Laplacian. Specifically, the smallest non-zero eigenvalues and the associated eigenvectors of the graph's Laplacian are utilized as input. Each eigenvector concatenated with its corresponding eigenvalue (where eigenvalues are duplicated along the node dimension) is projected into dsigaNet dimensions and subsequently fed into a Graph Isomorphism Network (GIN) (Xu et al. 2019) to generate an embedding. This opera- tion performed twice for each eigenvector once the original eigenvector and once with each dimension negated. The yielded embeddings are then averaged to obtain sign-invariant embedding. This procedure repeated for every individual eigenvector, after which all embeddings for each node are concatenated. This concatenated output is subsequently mapped to demb -im-enninnii output using a multi-layer perceptron.
The aforementioned GIN comprises sequence of message passing layers, where each layer applies a multi-layer perceptron to the summed node embeddings of all adjacent nodes. Analogously to the Local PPGN, all intermediate embeddings from these layers concatenated, subjected to dropout operation with a probability of 0.1, and projected to dsignNer. dimensions using a linear layer.
It should be noted that all MLPs within SignNer have hidden dimension of dsign which can diverge from dhidden- Apart from this, all other architectural details remain identical.
We have also designed version of the PPGN model for baseline one-shot model. Notably, only edge features need to be generated here, which eliminates the need for input node features. Additionally, there are initial node embeddings, and reduction fraction target graph size global features. However, outside these differences, we maintain a consistent architecture with our Local PPGN model.
PPGN
Implementation Details We implement the Local PPGN and SignNer models using the Py ToTch Geometric framework (Fey & Lenssen 2019), the use of sparse graph representations that facili- tate scalability to larger graphs. We utilize the standard batching strategy, which involves merging several graphs into unified disconnected graph, with batch index to identify the original graph
27

---

Published as a conference paper at ICLR 2024
associated with each node. In contrast, the PPGN model is implemented using dense PyTorch oper- ations and representations.
F.4 GRAPH NEURAL NETWORK ARCHITECTURE ABLATION STUDY
The objective of this study is demonstrate the superior performance of proposed Local PPGN model. over conventional node-wise message passing architecture that we refer to as GINE, For the purpose of defining this model, let's denote the embedding of node v(0) E V as h. E TR and the embedding of edge (i,j) E & for a graph G = (V,E) as h(T) E R The updates to these embeddings performed as follows:
h n()
ho (1)
Vnode
h (id))
h (id), h( h h(())
Vodge
In the above equations, (v((0) represents the set of nodes adjacent to v(() We define ((x e)
ReLU(x, e) and instantiate + as sum, Toods (x, y) MLP Mcd + y) and Yedge (z, y,
ML.P [x || z), where MT.Pnoule and MT.Pedge edge are multi-layer perceptrons. The node update operation modified version of the GIN layer (Xu et al.] (019)), as proposed by Hu et al. (220)) All other aspects of this model, including the MLP design, input embeddings, and output, are kept identical those in the Local PPGN model. The findings from this ablation study are summarized in Table 5 We observe that the Local PPGN model consistently outperforms the GINE model across all datasets under consideration. The performance improvement is particularly pronounced for planar graphs, underscoring the importance of local expressivity in our model for capturing the structural properties of such graphs.
Planar graphs
Tree graphs
Proteins
Model
Ratio +
V.U.N. f
Ratio +
V.U.N. t
Ratio +
Local PPGN GINE
2.1
95.0
4.0
100
5.9
4.0
57.5
12.2
97.5
7.2
Table 5: Ablation study of the graph neural network architecture.
28

---

Published as a conference paper at ICLR 2024
G END-TO-END TRAINING AND SAMPLING
We provide algorithmic details for the end-to-end training and sampling procedures Algorithm and Algorithm respectively. Both algorithms assume the deterministic expansion size setting, described in Section 3.7 In the scenario without deterministic expansion size, the only deviation conditioned on the reduction fraction. The corre-
during the training phase is that the model sponding sampling procedure in this setting is described in Algorithm 8 All mentioned algorithms rely on the node embedding computation procedure, described in Algorithm [
Algorithm 5 Node embedding computation: This describes the procedure for computing node embeddings for given graph. Embeddings are computed for the input graph and then replicated according to the cluster size vector.
Parameters: number of spectral features k
Input: graph G = &), spectral feature model SignNelg. cluster size vector v Output: node embeddings computed for all nodes in V and replicated according to
I: function EMBEDDINGS(G = (V, SignNetg. v)
2: if then
H (1) h(VD iid N(O. I)
3:
> Sample random embeddings
4: else
5:
if k < \ then
6:
(A...... )x), [1
us] + EIG(G)
Compute k spectral features
7:
else
8:
[1 AI....., À 11-1 [u
1 f- GG) Compute [V] - 1 spectral features b Pad with zeros
9:
Ayp!...... 2R) [upp)...... ..... Ux t [0..... 0). (O.....0)
10:
end
11:
H (2) 1 [vD] + SiguNel (P......, Aa), [u Ug). G)
12:
end
13:
G= (V(1) .... U p(0),8) G(G.v)
Expand as per Definition b Replicate embeddings
14:
set H s.t. for all [[V]]: for all ((m)) V(r), Hpd Hpp
return H
16:
end function
29

---

Published as a conference paper at ICLR 2024
Algorithm End-to-end training procedure: This describes the entire training procedure for our model.
Parameters: number of spectral features k for node embeddings
Input: dataset D {G(1) ..... G(M) denoising model GNNo, spectral feature model SignNet
Output: trained model parameters
1: function TRAIN(D, GNNN,, SignNeto)
2: while not converged do
3:
G Uniform(D)
Sample graph >> Sample coarsening sequence }> Sample level
4:
(Go..... GL) RNDREDSEE(()
5:
(~ Uniform( (.......
6:
ifl = L then
7:
G1+1 + G1
8:
V141 f-1 1
9:
e, 4 Ø
10:
else
11:
set D1+1 as in Eq. and e, as in Eq. 5 s.t. [[G(G(4,,441) Gr
12:
end if
13:
if = 0 then
14:
01
15:
else
set vi in Eq. 4 the node set of G(G, 0z) equals that of G
17:
end if
H. t EABEDDINGS(GHI, SignNet,. vt+1)
Compute node embeddings < 1 (m (m//m=1), with and nı-1 being the size of G: and Gi-1
19:
20:
Dg + GNNe(:, G1, Hi, no. no. p). where no is the size of Go
21:
take gradient descent step on VgDIFFUSIONLOSS// E1, Ds)
22:
end while
23: return
24:
end function
Algorithm 7 End-to-end sampling procedure with deterministic expansion size: This describes the sampling procedure with the deterministic expansion size setting, described in Section [37] Note that this assumes that the maximum cluster size is which is the case when using edges as the contraction set family for model training.
reduction fraction range [Pinin: Pinax] Input: target graph size N, denoising model GNNo, spectral feature model SignNet Output: sampled graph G (V,E) E) with [V] N
Parameters:
1: function SAMPLE(NN GNNo. SignNet,g
2: G= G=(VEE) < ((v).0) 0)
Start with singleton graph > Initial cluster size vector
3:
v+
v
[2]
4:
while [V] < N do
5:
H <- EMBEDDINGS (G, SignNet v)
Compute node embeddings
6:
< ]
7:
p~ Uniform([Pnin Pmax])
> random reduction fraction number of nodes add ensure not to exceed target size >> actual reduction fraction
8:
n4 s.t. n_ p(n + n4)1
9:
+ min(n+, N m))
- 1 (n/ (n)))
Dg = G H, p.
12:
Sample feature embeddings set v s.t. for [n]: viil = 2 if [n] (o)ol 2 (o)o[l) 2 n4 and vli]
(v)o, (e)o + SDESAMMLE((D))
13:
otherwise
14:
e f DiSCRETIZE((E)))
15:
G (V,,) + G(G,e)
D Refine as per Definition
16:
end while
17:
return G
end function
30

---

Published as a conference paper at ICLR 2024
Algorithm End-to-end sampling procedure: This describes the entire sampling procedure with- out the deterministic expansion size setting.
Input: target graph size N, denoising model GNNo, spectral feature model SignNet
Output: sampled graph G (V, E)
1: function SAMPLE( GNNo. SignNet
2:
G (V, - (1 0)
Start with singleton graph Initial node embedding
3:
H EMBEDDINGS( (G, Gignnntttg... 1)
4:
Da + GNNo(. G, H)
5:
(v)o, -DDESAMPLEDD))
6:
v + ((SCRETIZE((*))))
b Initial cluster size vector
7:
while [V] < do
8:
H < EMBEDDINGS(G, SignNet,: v)
Compute node embeddings
9:
Dg + GNNo(: G(G, v), H. N)
10:
(v)o, (e)o + SDESAMPLE(Da)
b Sample feature embeddings
11:
<- DISCRETIZE (1)))
12:
e DISCRETIZE (e)o)
13:
G = -V,,)) = -VG,)
Refine as per Definition
14:
end while
15:
return
end function
31

---

Published as a conference paper at ICLR 2024
H COMPLEXITY ANALYSIS
In the following, we analyze the asymptotic complexity of our proposed method for generating a graph G with n nodes and m edges. The method involves creating an expansion sequence (Gr- = (fv),0) 0), GL-I,..., Go G) that progressively expands a single node into the graph G.
Assuming there exists positive constant e >> 0 such that the number of nodes nu of G1 satisfies the inequality 14 2 11+ for all 0 I I < L iterates, we can deduce that the length of the expansion sequence does not exceed L [logi+e +c n²] E Ollogn) This assumption holds true in the context of deterministic expansion size setting, as delineated in Algorithm / In the case of Algorithm B although not guaranteed, it likely to hold as the model trained to invert coarsening sequences with a minimum reduction fraction of Pmin-
Two observations are made to bound the sizes of the iterates Gj in the sequence. Since expansion can only increase the number of nodes in the graph, no Gi has more than n. nodes. For the number of edges, similar statement cannot be made, as a refinement step can remove arbitrarily many edges. Theoretically, graph G; with >> 0 could encompass more than edges. Nevertheless, this scenario is improbable for a trained model provided sufficient training data and model capacity as graph coarsening, according to Definition [3] can only decrease the number of edges. Consequently, the coarse graphs used for model training do not contain more edges than the dataset graphs. For the purpose of this analysis, we assume that the number of edges in all G3 is asymptotically bounded by m..
Next, we bound the complexity of generating an iterate G: in the sequence. For I = L, this in- volves instantiating singleton graph and predicting the expansion vector fg, which can be done in constant time and using constant space. For all other instances where 0 S l L, given the graph G1+1 and the expansion vector Ut+1, the graph G2 and expansion vector Uy are derived by constructing the expansion G. = G(G++1, v141). This is followed by sampling ey and et and sub- sequently constructing Gi =G(G), et). J. Let Umax denote the maximum cluster size, which is 2 for the edge contraction set family. This allows us to establish an upper bound on the number of edges in the expansion G. The edge set of Gj comprises, at most, f4++1 P'ne (Vme- intracluster edges and a maximum of m4412²m cluster interconnecting edges. It is reasonable to assume that Umax is con- stant, as the distribution of expansion sizes can only encompass constant number of categories. Consequently, no expanded graph will asymptotically exceed m edges. Sampling es and et is done by querying the denoising model a constant number of times. The complexity for this depends on the underlying graph neural network architecture. For message passing models, this is linear in the number of nodes and edges in the graph. Our Local PPGN model also achieves this efficiency the graph contains at most O(m) many triangles. Finally, we bound the complexity of obtaining the node embeddings for Gj. The first step involves calculating the & main eigenvalues and eigen- vectors of the graph Laplacian of G1+1- By using the method suggested in Vishnoi (2013), this can be achieved with complexity of Ō(km411) where Ô hides polylogarithmic factors. Computing the node embeddings from this using SignNet is done in O(km++1 time and space. The replication of the embeddings for the expansion Gj is linear relative to the number of nodes in Gj. Given that we select ie as a constant, the aggregate complexity for computing the node embeddings equates to Ö(n + m).
2
In conclusion, under the stated assumptions, the complexity to generate graph G with n nodes and m edges is Ö + m), again hiding polylogarithmic factors.
Figure 6 provides an empirical comparison of our method's runtime efficiency in generating sparse planar graphs against other graph generation models. Our approach achieves subquadratic runtime with respect to the number of nodes, outperforming DiGress (Vignac et al. 2023a) and our baseline one-shot method. It operates a constant factor slower than BwR (EDP- GNN) (Diamant et al.) 2023) and BiGG (Dai et al. 2020) but exhibits similar asymptotic scaling. This is remarkable given that our method significantly exceeds these models in terms of sample fidelity, as shown in our experiments.
32

---

Published as a conference paper at ICLR 2024
1400
(one-shot)
1000
800
Sampling
600
200
0-
1000
1250
1500
1750
Graph Size
Figure 6: Sampling Efficiency Comparison: The plot illustrates the time required to generate single planar graph as function of node count. Mean and standard deviation are calculated over 10 runs. Models with complexity tied to sparsity structure were trained to overfit single graph, and timing was recorded for generating that graph. Models failing to replicate the target structure, such as those producing disconnected graphs, have been excluded for faimesss. Experiments were conducted using a single NVIDIA GeForce RTX A6000 GPU. The reported values encompass all graph sizes that do not surpass the GPU's memory capacity of 40GB.
33

---

Published as a conference paper at ICLR 2024
1 EXPERIMENTAL DETAILS
1.1 DATASETS
We utilize the following synthetic and real-world datasets for our experimental evaluation:
Planar graphs: This dataset from Martinkus al. (022) comprises 200 planar graphs
with 64 nodes. These graphs are generated by applying Delaunay triangulation on a set of points placed uniformly random in the unit square.
SBM (Stochastic Block Model) graphs: We obtain this dataset from Martinkus et al. (2022), consisting of 200 graphs with 2 to communities. Each community contains 20 40 nodes, and the probability of an edge between nodes is 0.3 if they belong the same community and 0.05 otherwise.
Tree graphs: We generate 200 random trees, using NetworkX (Hagberg et al. 2008). each containing 64 nodes.
Dobson & Doig (003)) provide dataset of protein graph representations. In this dataset, each node corresponds to an amino acid and an edge exists between two nodes if the distance between their respective amino acids is less than 6 angstroms.
Protein graphs:
Point cloud graphs: We adopt the point cloud dataset used in Liao et al. (202)) which consists of 41 point clouds representing household objects (Neumann et al, 2013). As substantial portion of the graphs are not connected, only keep the largest connected component each graph.
For consistency, we employ the train/test split method proposed by Martinkus et (2022) Specifi- cally, we allocate 20% of the graphs for testing purposes and then partition the remaining data into 80% for training and 20% for validation. When available we use the exact split by Martinkus et al. 2022).
The dataset statistics are presented in Table 6
Dataset
Max. nodes
Avg. nodes
Max. edges
Avg. edges
Train
Val.
Test
Planar
64
64
181
177
128
32
40
SBM
187
104
1129
500
128
32
40
Tree
64
63
128
32
40
Protein
500
258
1575
646
587
147
184
Point cloud
5037
1332
10886
2971
26
7
8
Table 6: Dataset statistics.
I.2 EVALUATION METRICS
We the same evaluation metrics Martinkus et al. (2022) compare the performance of model with other graph generative models. We report the maximum mean discrepancy (MMD) between the generated and the test graphs for the following graph properties: degree distribution, clustering coefficient, orbit counts, spectrum, and wavelet coefficients. As reference, we compute these metrics for the training set and report the mean ratio across all of these metrics as a com- prehensive indicator of statistical similarity. It is important to note that for the point cloud dataset, given its k-nearest neighbor structure, the degree MMD identically zero; consequently, it is not incorporated into the mean ratio computation. Analogously, for the tree dataset, both the clustering coefficient and orbit counts are excluded from the ratio computation for the same reasons.
Another set of important metries uniqueness and novelty. These metrics quantify the proportion of generated graphs that are not isomorphic to each other (uniqueness) or to any of the training graphs (novelty).
As proposed by Martinkus et al. (2022) for synthetic datasets, we also report the validity score which verifies whether the generated planar graphs retain their planarity, whether the SBM graphs have high likelihood of being generated under the original SBM parameters, and whether the tree graphs lack cycles.
34

---

Published as a conference paper at ICLR 2024
1.3 HYPERPARAMETERS AND TRAINING SETUP
We train our model using the Adam optimizer (Kingma & Ba 2017) and an initial learning rate of 10-4. A comprehensive summary of the additional hyperparameters employed for model, as well as the baselines against which we compare, can be found in Table We train all models until there is no further performance improvement on the validation set, with an upper limit of four days. For model selection, we choose the epoch exhibiting the best validation metric, which constituted the fraction of valid, unique, and novel graphs in the case of synthetic datasets, and the mean ratio for real-world datasets.
Experiment
Hyperparamtter
Prowein
Point Cloud
Exmpelation
Interpolation
cubedding (slustee?
PPCN embodding (dopoN)
128
128
128
Iopu: embedding size (dam))
32
32
32
32
32
Number layers
10
10
10
10
10
10
10
Ours
Number of denuising steps
Batch size
256
32
236
16
256
32
256
16
236
256
32
256
32
FMA coefficient
0.99
0.999
0.99
0.9999
0.999
0.99
0.99
Number spectral features
2
2
SignNet embedding Ned)
128
125
SignNee
layens
cusbedding
embbedking (depaa))
Input embedding size (dusi))
32
32
Ours (ono-4hox)
Number layers
Nomber of denoising stops
256
256
256
255
256
256
Ratch size
16
16
EMA coefiicient
0.999
0.99
0,999
0,9999
0.999
0.999
Hidden
128
256
128
128
Emihelding
128
GRAN
layers
Batch mixtures
Number layers
10
10
DiGress Vigune et al.
30236
Number of diffission steps
1000
1000
1800
1000
1800
1000
Batch size
64
12
64
2
64
12
EDGE Chen al. 202330
Number of diffision steps
Batch size
128
16
256
32
16
256
8
256
2
Hidieen size
128
128
128
128
128
BoR (EDP-GNN) Diamant al.
2023
Number diffasion steps Ratch
200
200
Ordering
DRS
DFS
Ascummlated gradients
Banch size
32 32
32
32
GraphCeen Goyal atal 2020
Banch size
32
32
32
32
Table 7: Training hyperparameters for the models used in the experiments. A dash (-) signifies that we did not perform the experiment for the associated dataset, either due to memory restrictions because the results sourced from Martinkus al. (2022). All unspecified hyperparameters default to their standard values. For all additional models, the results are adapted from Martinkus al. 2022).
35

---

Published as a conference paper at ICLR 2024
J
SAMPLES
(a) Dataset graphs.
(b) Samples generated by our model.
Figure Uncurated set of planar graph samples.
(a) Dataset graphs.
(b) Samples generated by our model.
Figure 8: Uncurated set of tree graph samples.
36

---

Published as a conference paper at ICLR 2024
(a) Dataset graphs.
(b) Samples generated by our model.
Figure 9: Uncurated of SBM graph samples.
(a) Dataset graphs.
(b) Samples generated by model.
Figure 10: Uncurated set of protein graph samples.
37

---

Published as a conference paper at ICLR 2024
pao
(a) Dataset graphs.
(b) Samples generated by our model.
Figure 11: Uncurated set of point cloud graph samples.
(a) Planar graphs generated by our model.
(b) Tree graphs generated by our model.
Figure 12: Uncurated set of graph samples with 48 to 144 nodes from the extrapolation experiment, surpassing the maximum number of 64 nodes seen during training.
38

---

Published as a conference paper at ICLR 2024
ددددددد
Figure 13:
Illustrative example of spectrum preserving coarsening: The first column of each row presents a graph from our datasets. The subsequent columns depict progressive coarsening steps applied to these graphs. Each coarsening step is executed with consistent reduction fraction of 0.3. The objective of these steps is to maintain spectral characteristics of the original graph throughout the coarsening process, thereby preserving essential structural information.
39


Reviews:
[{"review_id": "gknJUDyMQt", "reviewer": "Reviewer_sNQQ", "summary": "In this study, the authors introduce a graph generative model that iteratively expands and refine a coarse graph into a larger graph. This model learns to invert a graph coarsening process by training a denoising diffusion model. To overcome the complexity problem of the available GNN models, a local GNN model based on the PPGN model is developed that concentrates on the local sub-graph expansion.", "questions": "1) It seems that the model is using two iterative processes: an outer process to expand a graph ($G_l -> G_{l-1}$) and an inner process that uses a denoising diffusion model at each $ l $? . It would be helpful to provide a clear explanation of these processes, especially in the context of using the one-shot method.\n\n2) Should the likelihood of a graph G presented before eq (1) be marginalized as:\n$P(G) = \\sum P(G|\\omega)p(\\omega)$? \n\nAlso, it seems more suitable to rather define it as marginalized over the coarsening sequences\n$P(G) = \\sum P(G|\\pi)p(\\pi)$\nAlso, in the first equation in variational interpretation, it is defined as marginalization over the a contraction family not all possible contraction sequences so it might be corrected by the upper bound:\n$P(G) \\ge \\sum_{\\pi in \\Pi_{F}} P(G|\\pi)p(\\pi)$\n\n3) Why do we need a multilevel coarsening scheme that ensures preservation of the Laplacian spectrum? Is this particular property a key to the model, or could other coarsening methods also be utilized which preserve global structures by explicitly preserving approximate Laplacian spectrum?\n\n4) In the footnote of page 5, an example is given for the expansion sequences that are not the reverse of any coarsening sequence. Are there other cases, or can the refinement step be restricted to ensure the refined graph remains connected?\n\n5) It would be valuable to elaborate on why this  added source of randomness in the expansion is beneficial to the model's performance.\n\n\n6) What was the range of $L$ in each dataset and what family of contractions did you use? Did you limit $L$? In the case $L=1$, is this method (one-shot) equivalent to one of the already available non-multiscale diffusion models in the literature such as Yan et al. (2023)?\n\n7) How the denoising process is focused on the local subgraphs details, did you only add noise to a subset of the edges at each diffusion step?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) Multi-scale graph generation from a coarse graph to fine details, adopted in this work, is important to learn the complex graphs which can also capture global structure and local details of the graphs. It is used as a key part to design efficient and scalable graph generative models. \n\n2) It designed an efficient local version of the PPGN model for parameterizing the local expansion and refinement model.", "weaknesses": "1) While the paper introduces a hierarchical and multiscale graph generation approach, it fails to acknowledge and compare it to previous methods [1, 2, 6] with similar objectives. For instance, HiGen [2] employs a hierarchical generation scheme, iteratively un-coarsing graphs and generating subgraphs in a coarse-to-fine manner with state-of-the-art quality. A hierarchical normalizing flow model for molecular graphs is also ignored [1], where new molecular graphs are generated by inverting edge contraction coarsening and duplicating node attributes after each expansion.\n\t\t\t\t\n2) The method maintains a  constant  number of eigenvalues $k$ (principal Laplacian spectrum) in the expansion process, which means that a fixed global structure of rank $k$ is used while the graph size is growing. On the other hand, since a local PPGN focuses on the local dense subgraph, therefore such *spectrum preserving local expansion* method may not capture some details that lie in the gap between the principal Laplacian spectrum (fixed global structure of the graph) and the local subgraphs. This can limit the model expressivity for larger graphs where this gap is larger.\n\n3) It lacks a comprehensive complexity analysis, despite claiming sub-quadratic complexity. It is essential to compare the sampling times to recent scalable graph generation models. Furthermore, there is no visualization of the generated graphs, which is crucial for assessing the quality of the model's output.\n\n4) The paper falls short in evaluating the generation quality by not comparing it to recent methods such as HiGen [2], GraphARM [3], and EDGE [4]. In particular, the performance on the Tree dataset is only compared against two benchmarks. It is also recommended to include the evaluation of the proposed model using random GNNs based on [5] as an alternative evaluation method to provide a more comprehensive assessment.\n \n5) The paper's presentation requires improvement to enhance its readability. \n\n-  a) Notations can be confusing, with some instances of the same notation used for different terms. For instance, distinguishing the expansion vector $\\mathbf{v}$ from nodes using different notation and handling variations in symbols such as $\\mathit{\\Pi}$ and $\\Pi$ would be beneficial. Additionally, the dual use of $\\theta$ for representing both the distribution over coarsening sequences and model parameters in section 3.3 may lead to confusion. \n\n- b) Contraction family and contraction function are both denoted by $\\mathcal{F}(G)$ while the family need not be a function of input graphs. \n\n- c) The paper should be improved for self-containment and clarity. For example, “we found that the formulation proposed by Song et al. (2021), supplemented with enhancements from Karras et al. (2022), yielded the most promising results, similarly to the approach used in Yan et al. (2023)” is very vague and one need to read the appendix. Also, a significant portion of the crucial model components is pushed to the appendix. \n\n- d) The paper employs the term \"autoregressive\" to describe the model, which might cause confusion. In section 2, it's mentioned that \"one-shot generative models have generally outperformed autoregressive ones.\" To avoid confusion, it's advisable to use more accurate terminology, such as \"recursive\" or \"iterative,\" to distinguish the model's nature.\n\n- e) The factorization mentioned at the bottom of page 4, based on the chain rule, should explicitly note the assumption of a Markov property in the expansion sequence, i.e., $P(G_{l-1} | G_l, G_{l+1}, …, G_{L} ) = P(G_{l-1} | G_l)$. This additional clarification will help readers better understand the underlying assumptions.\n\n[1] Maksim Kuznetsov and Daniil Polykovskiy. Molgrow: A graph normalizing flow for hierarchical molecular generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8226–8234, 2021.\n\n[2] M. Karami, “HiGen: Hierarchical Graph Generative Networks”, arXiv preprint arxiv:2305.19337 \n\n[3] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation, 2023.\n\n[4] Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.04111, 2023.\n\n[5] Rylee Thompson, Boris Knyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W Taylor. On evaluation metrics for graph generative models. arXiv preprint arXiv:2201.09871, 2022.\n\n[6] Hamed Shirzad, Hossein Hajimirsadeghi, Amir H Abdi, and Greg Mori. Td-gen: Graph generation using tree decomposition. In International Conference on Artificial Intelligence and Statistics, pp. 5518–5537. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "cqTdJUua4Y", "reviewer": "Reviewer_mLXw", "summary": "The paper describes a generative method for graphs. The generative procedure is cast in terms of reversing a graph hierarchical coarsening algorithm that groups nodes of the original graph in a hierarchical way to approximately preserve the spectra of the graph.\nThe authors propose to model the un-coarsening as a sequence of expansion - in which each node is expanded to a clique of a sampled number of nodes - and refinement steps. This later is tasked to remove edges from the expanded graph.\nBoth expansion and refinement are modeled in a Bayesian framework, where the joint distribution of the number of expansion nodes (for the next step) and edges to keep are conditioned on the previous graph in the hierarchical un-coarsening process.\nSampling from this distribution is performed through a denoising diffusion algorithm.", "questions": "There are a few things that are not clear in the method description:\n- at the end of page 4 it is mentioned that you have to model a probability distribution over node and edge features. Why features? aren’t v and e the number of nodes distribution and edge selection vector?\n- In the probabilistic model description, isn’t a graph G unequivocally defined by an expansion sequence? That is, given an expansion sequence, shouldn’t be the probability of a graph G either 1 or 0?\n- I would include some high-level details on how you model p(v_t,e_t | G_t) as a diffusion process. For instance, how are v and e modeled? Is e an adjacency matrix? Do you need to solve an inverse diffusion process for each expansion step?\n- Related to the previous point, if you need to sample through the denoising diffusion process, how does this impact the sampling time?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper provides a rigorous formulation (even if not always easily accessible) of graph generation in terms of graph uncoarsening in a probabilistic framework. The experimental section shows that the proposed method achieves results comparable (or better) to state-of-the-art graph generative models in standard datasets and shows that the method is able to deal with datasets with graphs of thousands of nodes.", "weaknesses": "The main limitation of the problem is that it is not easy to follow. It somehow lacks a level of abstraction that allows the reader to understand the individual parts of the method in an “intuitive” way before going into the details. You really need to carefully read and understand each bit of the 3.1 and 3.2 to understand where the method is headed.\n\nThe second weakness is the description and discussion of the local spectral preservation. Being the main focus of the title, I was expecting this to be one of the most important contributions of the paper. Unfortunately, it is briefly described in one paragraph in the main paper, and a small ablation experiment on this component is only provided in the appendix. \nIn general, I think that an ablation study on the most important design (e.g.  Spectral Conditioning) choices performed by the authors is missing and does not allow one to understand their impact.\n\nI also missed the presence of a brief paragraph positioning the paper with respect of the SOTA and highlighting its contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "dFHwVGGBOa", "reviewer": "Reviewer_HbqV", "summary": "This paper proposes a novel graph generation method via sequentially expansion. To achieve this, the authors sequentially coarse a graph via graph partition to obtain a sequence of intermediate graphs towards a single-node graph. The graph generation is basically reversing this process, starting from a single node graph and gradually do expansion and refinement towards the original full graph. What's more, each step of the graph refinement for reverting graph coarsen is modeled with denoising diffuison model, while all steps share the same parameters of denoising diffusion model. To establish and concretize this graph coarsen & graph expansion idea, the authors also study and optimize the orderings of coarsen and expansion (spectrum preserving graph coarsen), the underlying diffusion model used (SDE with pre-conditioning and self-conditioning), and also the network architecture (local PPGN to utilize sparsity while retain certain expressivity). The authors demonstrate the improved performance on several (small) plain-graph datasets, and two datasets with larger graphs.", "questions": "1. The definition of edge contraction and neighborhood contraction sets are unclear. How does each element inside the set translate to an order of coarsening? \n2. Can you explain how do you achieved batching of graphs when considering randomness of graph coarsening? And how do you batch different steps of graph expansion together? I'm concerning whether this leads to increased computation burden comparing with one-shot generation. \n3. When you use eigenvectors, why use SignNet? It is sign invariant representation, should be bad for edge prediction task. It should only be good for graph-level tasks. \n4. Can you provide more discussion over the choice of ordering of graph coarsen and graph expansion? From equation 1-3 they seem to play an important role. From your experimental result, how sensitive is the the ordering for generation quality? \n5. Can you provide result on molecular datasets? At least a relative small one QM9 should be considered.\n6. For one-shot generation, you have set the number of inference steps to be 1000, while for you each intermediate step needs 256 inference steps. Can you provide the total inference steps you used? Are this significantly larger than 1000? In the meantime, a fair comparison should use relatively same number of steps.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The designed method is novel. Graph generation via reverting graph coarsen is a promising and interesting approach.\n2. The development and concretization of the proposed idea is comprehensive. The authors discuss three additional design space around the idea: the graph coarsening ordering, the underlying diffusion model that utilizes newest improvement from literature, the local PPGN architecture to tradeoff expressivity with computational cost. \n3. The presentation in general is easy to follow, with minor problems that I will point out later. \n4. The authors designed an experiment of testing extrapolation and interpolation shows the great strength of sequentially expansion over one-shot generation, which is interesting and shows that the designed method is promising. \n5. The authors provide detailed configuration of hyperparameters, good for reader to check. \n6. I found that the spectrum preserving coarsen and spectrum guided generation are a good design, this constraints all intermediate graphs during the graph expansion process to be inside a family of graphs that having similar spectrum information. This probably leads to the improved extrapolation and interpolation result.", "weaknesses": "1. While being comprehensive that touches many design spaces, I personally found that it's a bit harder to know where the improvement of performance comes from. It would be great if the author can provide more detailed ablation study to guide the audience the importance of each design choice. \n2. For designed method depends on random orderings of graph coarsen and the reverse ordering of graph expansion. One shortcoming is that the designed method can be sensitive to orderings. The second shortcoming is that the method may needs a longer training period to converge comparing with one-shot generation, and I wish the author to discuss this. \n3. To follow up the previous shortcoming, I have noticed that the author only test the designed method over datasets with really limited number of graphs. I concern whether the training time increased due to the sequential coarsen and randomness of coarsen ordering can be too large for a dataset with large number of graphs. For example, typical molecule datasets can have millions of graphs inside. If the designed method has too much improved training cost, then it is not applicable to these real-world cases. Hence, I strongly suggest the author introduce additional datasets instead of just these small datasets. (small = limited number of graphs in the dataset) \n4. Decomposition of joint distribution, cannot be sum over all conditional likelihood. Instead should sum over P(G|order) x P(order). Similar issue inside equation 2, equation 3. These parts need a revision. \n5. The equation after eq.1 combines two independent distributions together, which uses less information to predict v_l, and can lead to error. This is because that edges being refined can be very important for identifying which node is expected to expand. \n6. The equation above (3) is essentially importance sampling, which needs the condition that support of distribution is covered all possible ordering (prob >0 for all orderings).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "pZoCk53mY6", "reviewer": "Reviewer_38QF", "summary": "This paper proposes a graph-generative model based on (1) iteratively expanding the coarse graph and (2) spectral conditioning. The authors demonstrate performance improvement over several baselines (GraphRNN GRAN, GDSS, Digress) on planar, SBM, tree, protein, and point cloud graphs.", "questions": "- I do not understand why the authors argue the V.U.N. metric is the most important metric. Could the authors elaborate on this point?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a new method for scalable graph generation, which is an important problem. The idea is sound and the empirical results are solid.", "weaknesses": "### Comparison to existing scalable graph generative model (BiGG, GraphGen)\n\nThe authors do not compare their results with significant baselines for graph generation. Since the proposed method is designed for scalable graph generation, scalable baselines should be prioritized over others. \n\n\n[Dai et al., 2020] Scalable Deep Generative Modeling for Sparse Graphs\n\n[Goyal et al., 2022] GraphGen: A Scalable Approach to Domain-agnostic Labeled\n\n[Diamant et al., 2023] Improving Graph Generation by Restricting Graph Bandwidth\n\n### Novelty compared to coarsening-based graph generation. \nThere exists a work based on generating graphs in a coarse-graining manner. The authors should compare with such a work. \n\n[Guo et al., 2022] An Unpooling Layer for Graph Generation\n\n### Lack of graph visualization and additional metrics for extrapolation\nThe authors do not visualize the generated graph, which is quite important for verifying the validity of the proposed method, e.g., well-generated graphs are usually connected and indistinguishable from training data from the human eyes. \n\n\nFurthermore, the authors only check a fraction of valid and unique ratios for interpolation and extrapolation tasks. I suggest reporting additional MMD-based metrics. \n\n### Lack of real-world experiments \n\nAll the datasets considered in the experiments are (perhaps arguably) synthetic. For the completeness of the experiment, the authors could consider real-world experiments like molecule generation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)