A Simple and Scalable Representation for Graph Generation
Authors: Yunhui Jang
Seul Lee
Sungsoo Ahn
Venue: ICLR 2024 poster (2024)
Keywords: Graph generative models
graph neural networks
graph representation
Primary area: generative models
TL;DR: We propose a simple and scalable edge list-based graph representation, gap encoded edge list (GEEL).

Abstract: Recently, there has been a surge of interest in employing neural networks for graph generation, a fundamental statistical learning problem with critical applications like molecule design and community analysis. However, most approaches encounter significant limitations when generating large-scale graphs. This is due to their requirement to output the full adjacency matrices whose size grows quadratically with the number of nodes. In response to this challenge, we introduce a new, simple, and scalable graph representation named gap encoded edge list (GEEL) that has a small representation size that aligns with the number of edges. In addition, GEEL significantly reduces the vocabulary size by incorporating the gap encoding and bandwidth restriction schemes. GEEL can be autoregressively generated with the incorporation of node positional encoding, and we further extend GEEL to deal with attributed graphs by designing a new grammar. Our findings reveal that the adoption of this compact representation not only enhances scalability but also bolsters performance by simplifying the graph generation process. We conduct a comprehensive evaluation across ten non-attributed and two molecular graph generation tasks, demonstrating the effectiveness of GEEL.

Published as a conference paper at ICLR 2024
A SIMPLE AND SCALABLE REPRESENTATION FOR GRAPH GENERATION
Yunhui Jang', Seul Lee?, Sungsoo Ahn'
Pohhng University of Science and Technology
2 Korra Advanced Institute of Science and Technology (uni5510, sungsco.. ahn) @postech.cco ac.kr. kr, seul.lee@kaist.ad
ABSTRACT
Recently, there has been a surge of interest in employing neural networks for graph generation, fundamental statistical learning problem with critical applications like molecule design and community analysis. However, most approaches encounter significant limitations when generating large-scale graphs. This is due their requirement to output the full adjacency matrices whose size grows quadratically with the number of nodes. In response this challenge, and scalable graph representation named gap encoded edge list (GEEL) that has a small representation size that aligns with the number of edges. addition, GEEL significantly reduces the vocabulary size by incorporating the gap encoding and bandwidth restriction schemes. GEEL can be autoregressively generated with the incorporation of node positional encoding, and we further extend GEEL to deal with attributed graphs by designing a new grammar. Our findings reveal that the adoption of this compact representation not only enhances scalability but also bolsters performance by simplifying the graph generation process. We conduct comprehensive evaluation across ten non-attributed and two molecular graph generation tasks, demonstrating the effectiveness of GEEL.
introduce new, simple,
INTRODUCTION
Learning the distribution over graphs a challenging problem across various domains, including social network analysis (Grover et al., 2019) and molecular design (Li al., 2018; Maziarka et al., 2020). Recently, neural networks gained much attention in addressing this challenge by leveraging the advancements in deep generative models, e.g., diffusion models (Ho et al., 2020), to show promising results. These works are further categorized based on the graph representations they employ.
However, the majority of the graph generative models do not scale large graphs, since they generate the adjacency matrix-based graph representations (Simonovsky & Komodakis, 2018; Madhawa al., 2019; Liu al., 2021; Maziarka al., 2020). In particular, for large graphs with N nodes, the adjacency matrix is hard to handle since they consist of N2 binary elements. For example, employing a Transformer-basee computational complexity. Researchers have considered tree-based (Segler et al., 2018 8) or motif- based representations (Jin et al., 2018; 2020) to mitigate this issue, but these representations constrain the graphs being generated, e.g., molecules or graphs with motifs extracted from training data.
autoregressive model for all the binary elements requires O(N4)
Intriguingly, few works (Goyal et al., 2020; Bacciu Podda, 2021) have considered generating the edge list representations as a potential solution for large-scale graph generation. In particular, the list contains M edges that are fewer than N2 elements in the adjacency matrix, distinctive difference especially for sparse graphs. However, such edge list-based graph generative models instead suffer from the vast vocabulary size 22 for the possible edges. Consequently, they face the challenge of learning dependencies over larger output space and may overfit to a specific edge edge combination appearing only in a few samples. Indeed, the edge list-based representations empirically perform worse than simple adjacency matrix based models (You et al., 2018), e.g., see Table 1.
In this paper, we propose a simple, scalable, yet effective graph representation for graph generation, coined Gap Encoded Edge List (GEEL). On one hand, grounded in edge lists, GEEL enjoys

---

Published as a conference paper at ICLR 2024
Intra-edge S B
GRAN BIGG
GDSS DiGeess
Inter-edge gap S
Generation time (s)
10.0
Graph
1.0
0.1
Edge list
(1, 2)
(1, 3)
(3, 4)
(3, 5)
Enzymes
Planar (b) Short inference time.
Grid
Reduction rate (%)
100
Repr. (
(p)
GEEL
(1, 1) (0, 2)
(2, 1)
(0, 2)
M
Enzymes (c) Rep. and vocab. size reduction.
Planar Grid
Overview.
Figure 1: Overview and advantages of gap encoded edge list (GEEL).
compact representation size that aligns with the number of edges. On the other hand, GEEL improves the edge list representations by significantly reducing the vocabulary size with gap encodings that replace the node indices with the difference between nodes, i.e., gap, described in Figure la. We also promote bandwidth restriction (Diamant et al., 2023) which further reduces the vocabulary size. Next, we augment the GEEL generation with node positional encoding. Finally, introduce new grammar for the extension of GEEL to attributed graphs.
The advantages of our GEEL are primarily twofold: scalability and efficacy. First, regarding scalability, the reduced representation and the vocabulary sizes mitigate the computational and memory complexity, especially for sparse graphs, as described Figure 1b. Second, concerning the efficacy, GEEL narrows down the search space to B via intra- and inter-edge gap encodings, where the size of each gap is bounded by graph bandwidth B (Chinn et al., 1982). We reduce this parameter via the bandwidth restriction scheme (Diamant et al., 2023). This prevents the model from learning dependencies among a vast vocabulary of size 2 This improvement is more pronounced when compared with the existing edge list representations, described in Figure 1c.
We present an autoregressive graph generative model to generate the proposed GEEL with node positional encoding. In detail, we observe that simple LSTM (Hochreiter & Schmidhuber, 1997) combined with the proposed GEEL exhibits (M) complexity. Furthermore, combined with the node positional encoding that indicates the current node index, our GEEL achieved superior performance across ten general graph benchmarks while maintaining simplicity and scalability.
We further extend GEEL attributed graphs by designing new grammar and enforcing filter out invalid choices during generation. Specifically, our grammar specifies the position of node- and edge-types to be augmented in the GEEL representation. This approach led competitive performance for two molecule generation benchmarks.
In summary, our key contributions are follows:
We newly introduce GEEL, simple and scalable graph representation that has compact representation size of M based on edge lists while reducing the large vocabulary size N2 of the edge lists B² by applying gap encodings. We additionally reduce the graph bandwidth B by the C-M ordering following Diamant et al. (2023).
We propose autoregressively generate GEEL by incorporating node positional encoding and combining with an L.STM O(M) complexity.
We extend GEEL to deal with attributed graphs by designing a new grammar that takes the node- and edge-types into account.
We validate the efficacy and scalability the proposed GEEL and the resulting generative framework by showing the state-of-the-art performance twelve graph benchmarks.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Adjacency matrix-based graph representation. The adjaceney matrix is the most prevalent graph representation, capturing straightforward pairwise relationships between nodes (Simonovsky & Komodakis, 2018; Jo et al., 2022; Vignac et al., 2022: You et al., 2018; Niu et al., 2020; Shi et al., 2020; Luo et al., 2021). For instance, You et al. (2018) proposed autoregressive generative models, Luo et al. (2021); Shi et al. (2020) presented normalizing flow models, and Jo et al. (2022) applied score-based models for graph generation. However, these methods suffer from the large representation size associated with generating the full adjacency matrix, which is impractical for large-scale graphs.
To solve this problem, several works have introduced scalable graph generative models (Liao et al., 2019; Dai et al., 2020; Diamant et al., 2023). Specifically, Liao et al. (2019) proposed a block- wise generation which enabled efffciency-quality trade-off. Dai et al. (2020) proposed to avoid consideration of every entry in the adjacency matrix, leveraging on the sparsity of graphs. Finally, Diamant et al. (2023) proposed to constrain the bandwidth via C-M ordering for any graph generative models, bypassing the out-of- ofbbwwwidhhhh elements, which results in NB representation size.
Tree-based graph representation. Researchers have developed tree-based representations by employing tree search algorithms (Segler et al., 2018; Ahn et al., 2022). Specifically, Segler et al. (2018) employed SMILES, a sequential representation for molecules, constructed from the DFS traversal of molecular graphs with omitted cycles. Complementing this, Ahn et al. (2022) designed new representation that exploits the inherent tree-like structure of molecules.
Motif-based graph representation. Researchers have investigated motif-based representations (Jin et al., 2018; 2020; Guo et al., 2022), aiming to capture meaningful subgraphs with lower computational costs. In detail, Jin et al. (2018; 2020) focused extracting common fragments from datasets. Since these techniques rely on domain- -omain-specific knowledge, Guo et al. (2022) introduced a domain- aggnosicc methodology learn motif-based vocabulary by running reinforcement learning. However, it is still restricted to generating graphs with seen motifs that are included in the training set.
Edge list-based graph representation. A few works have presented edge list-based representa- tions (Goyal et al., 2020; Bacciu & Podda, 2021). Employing an edge list as graph representation reduces the representation size to M, which is smaller than that of the adjacency matrix, N22 How- ever, these methods suffer from the large vocabulary size N resulting in a large search space and subsequently degrading the generation quality. They also face difficulties in capturing long-ter dependencies due to their reliance on depth-first search (DFS) traversal for edge construction. Specif- ically, DFS traversal fails to closely place edges connected to the same node so the model must span a broader range of steps to account for edges connected to the same node.
METHOD
In this section, introduce our new graph representation, termed gap encoded edge list (GEEL), and autoregressive generation process with GEEL. GEEL has a small representation size M by employing edge lists. In addition, GEEL enjoys reduced vocabulary size with gap encodings and bandwidth restriction, narrowing down the search space and resulting in high-quality graph generation.
3.1 GAP ENCODED EDGE LIST REPRESENTATION (GEEL)
First, we present our GEEL representation, which leverages the small representation size of edge lists and the reduced vocabulary size with gap encoding and bandwidth restriction. Consider graph with N nodes, M edges, and graph bandwidth B (Chinn et al., 1982). The associated edge list has a representation size of M which is smaller compared to the size of the adjacency matrix 2 However, it has a large vocabulary size of 2 consisting of tuples of node indices. To address this, we reduce the vocabulary size into B² by replacing the node indices in the original edge list with gap encodings as illustrated in Figure la. We encode two types of gaps: (1) the intra-edge gap between the source and the target nodes and (2) the inter-edge gap between source nodes in a pair of consecutive edges.
To this end, consider a connected undirected graph G = (V,E) with N nodes and M edges. We define the ordering as invertible mapping - {1, (1,-.-g N} from vertex into its rank for
3

---

Published as a conference paper at ICLR 2024
particular order of nodes. Then define the edge list TEL sequence of pairs of integers:
TEL (1), (52, t2),.... (SM,
where 8m, fm E (1....,, N) are the m-th source and target node indices that satisfy (I (sm), ), ( (tm]) edge list is sorted with respect to the ordering, i.c., if m < L, then 8m 8y or = St, tm < tr. For example, (1, (1, 3), (2, 3), (3, 5) is sorted edge list while (1, 2), (2, 3), (3, 5), (1, is not.
respectively. Without loss of generality, we assume that 8m tm and the
Consequently, we define our GEEL TGEEL as sequence of gap encoding pairs as follows:
TGEEL (a1, b1), (az, ( (aM: bMs),
where am and bn are the inter- and intra-edge gap encodings, respectively. To be specific, the inter-edge gap encoding indicates the difference between consecutive source indices as follows:
am mm Sm-1+
m L, ....,, M, 50 0.
Furthermore, the intra-edge gap encoding bm indicates the difference between the associated source and target node indices follows:
hm
Im 8ms
m7 1,..., M.
Then one can recover the original edge list TEL from GEEL TGEEL as follows:
Im = bm + Σ
Sm
t=1
Note that the gap encodings are always positive and GEEL can generalized to directed graphs by allowing negative intra-edge gap encodings.
Reduction of the vocabulary size. In training generative model for edge lists and GEEL, the
Graph
Adjacency matelx
(1.2).
vocabulary size of (8m; (m) and (am: bm.) deter- mines the complexity of the model. Here, show that the vocabulary size of our GEEL is B² for the graph bandwidth B, which is smaller than the vocabulary size N2 of the original edge list representation. Many real-world graphs, such as molecules and community graphs, ex- hibit low bandwidths shown in Appendix C and by Diamant et al. (2023).
a:
(2.3).
(2,4),
d:
(3.5).
e:
(4.5).
f:6
(4.6).
(5.6).
Bandwidth
max bm
The vocabulary size of our GEEL representation is bounded by max, hand, the maximum intra-edge gap encoding coincides with the definition of the graph bandwidth, i.e., the maximum difference between a pair of adjacent nodes, denoted as max, bm = B as described in Figure 2. On the other hand, we can obtain the following upper bound for the inter-edge encoding:
Figure 2: Bandwidth of an adjacency matrix.
maxm bm- On one
max mww.aaaxa.. 88m 8m-1) S max
max lp
8m-11 < max max (Le 82) S B, Ecm
where the first inequality is based on deriving 8m S max4<m te from the graph connectivity con- straint: each source node index must appear as target node index in prior for the graph to be connected, i.e., 8., for some < m. Consequently. the vocabulary size of our GEEL representation is bopeerbounded by max,,
maxx bn < B
Given that the vocabulary size GEEL is bounded by B², small bandwidth benefits graph generation by reducing the computational cost and the search space. We follow Diamant et al. (2023) to restrict the bandwidth via the Cuthill-McKee (C-M) node ordering (Cuthill McKee, 1969). We also provide an ablation study with various node orderings in Section 4.3.
3.2 AUTOREGRESSIV GENERATION OF GEEL AND NODE POSITIONAL ENCODING
Autoregressive generation. We first describe our method for the autoregressive generation of GEEL. To this end, we propose to maximize the evidence lower bound of the log-likelihood with respect
4

---

Published as a conference paper at ICLR 2024
C
Graph G
Node-type
Edge-type
3
[C,N.C.C]
;
Edge-tuple dummyy edge
(1, 1)
(1. 1)
(0, 2)
(1. 0) (1. (1
Attributed GEEL
C
(1. 1)
(1, 1)
(0, 2)
(1,
(1. 0)
Figure 3: An example of attributed GEEL. The colored parts of the attributed GEEL denote the node features (i.e., C and N) and edge features (i.e., single bond -). The shaded parts denote the self-loops added to the original GEEL, where self-loops are added to the nodes that are not connected to the nodes with larger node indices (i.e., nodes with indices 3 and 4).
the latent ordering. To be specific, following prior works autoregressive graph generative models (You al., 2018; Liao et al., 2019; Dai et al., 2020), we maximize the following lower bound:
log P(G) 2 (((r) [
where C' is a constant and (T((") is variational posterior of the ordering given the graph G. Under this framework, our choice of choosing the C-M ordering for each graph corresponds to a choice of the variational distribution ((T[G). Fixing particular ordering for each graph yields the maximum log-likelihood objective for log pl G, π) log ((TOBEL)
We generate GEEL using autoregressive model formulated as follows:
M
P(TCEEL) = p(a1, by) II m==
p(am, 1 (ar) (b.))
Notably, we treat each tuple (am bm) ) as one token and generate a token at each step. Similar to text generative models, also introduce the begin-of-sequence (BOS) and the end-of-sequence (EOS) tokens to indicate the start and end of the sequence generation process, respectively (Collins, 2003).
Finally, noteworthy that we train long short-term memory (LSTM) model (Hochreiter Schmidhuber, 1997) to minimize the proposed objective. Adopting LSTM as our backbone ensures an (MM complexity for our generative model, due the linear complexity of the LSTM. The model architecture can be freely changed to other architectures as demonstrated in Section 4.3.
Source node positional encoding, While the gap encoding allows a significant reduction in vocabu- lary size, it also complicates the inherent semantics since each source node index is represented by the cumulative summation over the intra-edge gap encodings. Instead of burdening the generative model to learn the cumulative summation, we directly supplement the token embeddings with the node positional encoding of the source node index, i.c., Ex= ag at the (m + 1)-th step as:
((am, bm)) Peuple (am,, Dyn)) ΦrE
Σ 8=1
where ó is the final embedding, Stuple is the token embedding, and érE is the positional encoding.
3.3 GEEL FOR ATTRIBUTED GRAPHS
In this section, we elaborate on the extension of GEEL to attributed graphs. To this end, we augment the GEEL representation with node- and edge-types. Our attributed GEEL follows specific grammar that filters out invalid choices tokens.
Grammar of attributed GEEL. For the generation of attributed graphs with node- and adge-types, we not only generate the edge-tuples (ax, by) as Section 3.1 but also generate node- and edge-types according to the following rules. We provide illustrative example of attribute GEEL in Figure 3.
5

---

Published as a conference paper at ICLR 2024
Before describing edge-tuples starting with new source node, add the paired node-type.
After adding edge-tuple, add the paired edge-type.
One can observe that our rules are intuitive: for each source node, we first describe the node-type and then generate the associated edge-tuple and types. For nodes that are not associated with any edge-tuple as source node, we add "dummy" edge-tuple with the node as its source. As result, our representation size for attributed graphs is at most. 2.M and the vocabulary size is 2 |X|+ F] where X denotes the number of node features and F denotes the number of edge features.
Autoregressive generation with grammar constraints. To enforce the attribute grammar, we introduce an algorithm to filter out invalid choices of tokens.
The first token is always the node-type token.
The node-type tokens are always followed by edge-tuple tokens.
The edge-tuple tokens are always followed by edge-type tokens.
The edge-type tokens are always followed by node-type tokens or edge-tuple tokens.
These rules prevent the generation process from generating invalid GEEL such the list that consists of only node-types or the list that has an edge-tuph aige-tupl without a following edge-type token. This procedure is done by computing the probability only over valid choices.
EXPERIMENT
4.1 GENERAL GRAPH GENERATION
Evaluation protocol. We adopt maximum mean discrepancy (MMI) evaluation metric to compare three graph property distributions between test graphs and the same number of generated graphs: degree, clustering coefficient, and 4-node-orbit counts. Results that are either superior to or comparable with the MMD of training graphs are highlighted in bold in Table 1. The comparability of MMD values is determined by examining whether the MMD falls within range of one standard deviation. Notably, our work stands out as a baseline for graph generative models, given its comprehensive evaluation across ten diverse graph datasets and its state-of-the-ar performance. Further details regarding our experimental setup are in Appendix A.
We validate the general graph generation performance of our GEEL on eight general graph datasets with varying sizes. Four small-sized graphs are: (1) Planar, 200 planar graphs, (2) Lobster, 100 Lobster graphs (Senger, 1997), (3) Enzymes (Schomburg et al., 2004), 587 protein tertiary structure graphs, and (4) SBM, 200 stochastic block model graphs. Four large-sized graphs are: (5) Ego, 757 large Citeseer network dataset (Sen et al., 2008), (6) Grid, 100 2D grid graphs, (7) Proteins, 918 protein graphs, and (8) 3D point cloud, 41 3D point cloud graphs of household objects. Additional results on two smaller datasets (Ego-small and Community-small are provided Appendix E.
We compare GEEL with seventeen deep graph generative models. They can be categorized into two according to the type of representation they use. On one hand, fifteen adjacency matrix- based methods are: Graph VAE (Simonovsky & Komodakis, 2018), GraphRNN (You al., 2018), GNF Liu et al. (2019), GRAN (Liao et al., 2019), EDP-GNN (Niu et al., 2020), GraphAF (Shi et al., 2020), GraphDF (Luo al., 2021), SPECTRE (Martinkus et al., 2022). BiGG (Dai et al., 2020), GDSS (Jo et al., 2022), DiGress (Vignac et al., 2022). GDSM (Luo et al., 2022), GraphARM (Kong et al., 2023), BwR (Diamant al., 2023), and SwinGNN (Yan al., 2023). On the other hand, two edge bastd methods are GraphGen (Goyal et al., 2020) and GraphGen-Redux (Bacciu & Podda, 2021). Note that one graph compression-ban method HGGT (Jang al., 2024) also included. We provide detailed implementation description in Appendix B.
Generation quality. We provide experimental results in Table 1. We observe that the proposed GEEL consistently shows superior or competitive results across all the datasets. This verifies the ability of our model to effectively capture the topological information of both large and small graphs. The visualization of generated samples can be found in Appendix D. It is worth noting that the generation performance on small graphs has reached saturation point, yielding results that are either superior comparable to training graphs.

---

Published as a conference paper at ICLR 2024
Table I: General graph generation performance. The baseline results are from prior works (Jo et al., 2022; Kong et al., 2023; Martinkus et al., 2022; Dai et al., 2020; Diamant et al., 2023) or obtained by running the open-source codes. Note that OOM indicates Oft-Orf-emory and N.A. indicates that the generated samples are all invalid. For each metric, the numbers that are superior or comparable to the MMD of the training graphs are highlighted in bold. The comparability is determined by whether the MMD falls within one standard deviation.
Planar
Lobster
Enzymes
SBM
[V] = 64
[V]
S
100
[V] S 125
31
[V] & 187
Method
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Training
0.001
0.002
0.000
0.005
0.000
0.007
0.006
0.018
0.007
0.016
0.002
0.047
GraphVAE
1.369
0.629
0.191
GraphRNN
0.005
0.278
1.254
0.000
0.000
0.000
0.017
0.062
0.046
0.006
0.058
0.079
GRAN
0.001
0.043
0.001
0.038
0.000
0.001
0.023
0,031
0.169
0.011
0.055
0.054
EDP-GNN
0.023
0.268
0.082
GraphGen
1.762
1.423
1.640
0.548
0.040
0.247
0.146
0.079
0.054
1.230
1.752
0.597
GraphGien-Re Redux
1.105
1.809
0.517
1.189
1.859
0.885
0.456
0.035
0.251
GraphAF
1.669
1.283
0.266
GraphDF
1.503
1.283
0,266
BiGG
0.002
0.004
0.000
0.000
0.000
0.000
0.010
0.018
0.011
0.029
0.003
0.036
GDSS
0.250
0.393
0.587
0.117
0.002
0.149
0.026
0.061
0.009
0.496
0.456
0.717
DiGress
0,000
0.002
0.008
0.021
0.000
0.004
0.011
0.039
0.010
0.006
0.051
0.058
GDSM
0.013
0.088
0.010
GraphARM
0.029
0.054
0.015
BwR
0.609
0.542
0.097
0.316
0.000
0.247
0.021
0.095
0.025
N.A.
HGGT
0.000
0.001
0.000
0.003
0.000
0.015
0.005
0.017
0.000
0.017
0.014
0.076
GEEL (ours)
0.001
0.010
0.001
0.002
0.000
0.001
0.005
0.018
0.006
0.025
0.003
0.026
(a) Small graphs (V max S 187)
Ego
Grid
Proteins
3D point cloud
50 S IV
S 399
100 < [V] g 400
13 S
[V S 1575
8 $
[V] < 5037
Method
Deg.
Clus.
Orh.
Deg.
Clus.
Orb.
Deg.
Clus,
Orb.
Deg.
Clus.
Orb.
Training
0.010
0.003
0.016
0.000
0.000
0,000
0.002
0.003
0.002
0.004
0.090
0.015
GraphVAE
1661
0.000
0.919
OOM
GraphRNN
0.117
0.615
0.043
0.011
0.000
0.021
0.011
0.140
0.880
OOM
GRAN
0.026
0.342
0.254
0.001
0.004
0.002
0.002
0.049
0.130
0.018
0.510
0.210
IDP-GNN
0.455
0.238
0.328
GraphGen
0.578
1.199
0.776
1,550
0.017
0.860
1.392
1.743
0,866
00M
GraphGen-Redah Redux
1.088
0.702
0.155
SPECTRE
0.013
0.047
0.029
BiGG
0.010
0.017
0.012
0.000
0.000
0.001
0.001
0.026
0.023
0.003
0.210
0.007
GDSS
0.393
0.873
0.209
0.111
0.005
0.070
0.703
1,444
0,410
OOM
DiGress
0.063
0.031
0.024
0.016
0.000
0.004
00M
0OM
GDSM
0.002
0.000
0.000
BwR
N.A.
0.385
1.187
0.083
0.092
0.229
0.489
1.820
1.295
0.869
SwinGIN
0.000
0.000
0.000
0.002
0.016
0.003
HGGT
N.A.
0.000
0.000
0.000
0.098
0.708
0.619
00M
GEEL (ours)
0.053
0.017
0.016
0.000
0.000
0.000
0.003
0.005
0.003
0.002
0.081
0.020
(b) Large graphs (399
< V max < 5037)
Scalability analysis. Next, we empirically validate the time complexity of our model. We first verify if the actual inference time aligns well with the theoretical O(M) curve. To this end, we generated Grid graphs with varying numbers of nodes: [10, 100, 200, 500, 1k, 2k, 5k, 10k). The results shown in Figure 4 indicate an alignment between the actual inference time and the ideal curve.
Then we conduct further experiments to compare the inference time of our model with that of other baselines. Note that we used the same computational resource for all models and other experimental details are in Appendix B. The results presented in Table 2 represent the time required to generate a single sample. Notably, our model shows shorter inference time owing to the compactness of our representation, GEEL, even compared to other scalable graph generative models (Liao et al., 2019; Dai et al., 2020). This evidence underscores the scalability advantages of our GEEL.
7

---

Published as a conference paper at ICLR 2024
Generation time (sec)
10a
Table 2: Inference time (sec) to generate graph.
C
10¹
G
Method
Type
Enzymes
Planar
Grid
10a
GRAN
Auto. Reg.
0.24
0.66
1.39
BiGG
Auto. Reg.
2.70
0.61
3.58
10-
GDSS
Diffusion
15.21
15.25
30.89
10
10
10'
10a
DiGress
Diffusion
8,82
12.09
32.29
Number of nodes
Figure 4: Infer: time on various graph sizes.
GEEL (ours)
Auto.
Reg.
0.12
0.25
1.11
Table 4: Molecular graph generation performance of the QM9 and ZINC datasets. The baseline results are from prior works (Jo et al., 2022; Ahn et al., 2022). The best results of coolecule-speciinn generative models and domain-agnonne generative models are both highlighted in bold.
QM9
ZINC250K
Method
Val. (%)
NSPDK (4)
FCD
Scaf. (1)
SNN
Frag. (t)
Val. (%) (1)
NSPDK (4)
FCD
Scaf.
SNN
Frag. (1)
(t)
(t)
Molecule specific generative models
CharRNN
99.57
0.0003
0J087
0.9313
0.5162
0.9887
96.95
0.0003
0.474
0.4024
0.3965
0.9988
CG-VAE
100,0
1.852
0.6628
0.3940
0,9484
100,0
11.335
0.2411
0.2656
0.8118
MoFlow
91.36
0.0169
4.467
0.1447
0.3152
0.6991
63.11
0.0455
20.931
0.0133
0.2352
0.7508
STGG
100.0
0.585
0.9416
0.9998
0.9984
100,0
0,278
0.7192
0,4664
0,9932
Domain-agnostic graph generative models
EDP-GNN
0.0046
0.3270
0.5265
0.8313
0.0485
GraphAF
74.43
0.0207
5.625
0.3046
0.4040
0.8319
68..7
0,0442
16.023
0.0672
0.2422
0.5348
GraphDF
0.0636
0.0978
0.4370
0.1770
0.2049
GDSS
95.72
0.0033
2,900
0.6983
0.3951
0.9224
97.01
0,0195
14.656
0,0467
0.2789
0.8138
DiGress
0.5263
0.0023
0.0021
DruM
99.69
0.0002
0.108
0.9449
0.5272
0.9867
98.65
0.0015
2.257
0.5299
0.3650
0.9777
GraphARM
1.220
88.23
0.0550
GEEL (ours)
100.0
0.0002
0.089
0,9386
0.5161
0.9891
99.31
0.0068
0.401
0.5565
0,4473
0.992
In addition, we provide the reduced represen- tation and vocabulary sizes in Table 3. Note that the vocabulary size of the original edge list and the representation size of the adjacency ma- trix are both N We can observe that GEEL is efficient in both sizes.
Table 3: Vocabulary and representation sizes. The vocabulary size is B2 and the representation size is M where B is bandwidth, N is the number of nodes, and M is the number of edges.
Dataset
Vocab, size
Rep. size
N22
Planar
676
181
4096
4.2 MOLECULAR GRAPH GENERATION
Lobster
2401
Enzymes
361
149
1.6255
SBM
12321
1129
34969
Experimental setup. We use two molecular datasets: QM9 (Ramakrishnan et al., 2014) and ZINC250K (Irwin et al., 2012). Following the previous work (Jo al., 2022), we evaluate 10,000 generated molecules using six metrics: (a) the ratio of valid molecules without correc-
Ego
58081
1071
>> 10"
Grid
361
684
467856
Proteins
62500
1575
> 10"
3D point cloud
111556
10886
> 107
tion ( (Val.), (b) neighborhood subgraph pairwise distance kernel (NSPDK), (c) Frechet ChemNet Distance (FCD) (Preuer et al., 2018), (d) scaffold similarity (Scaf.), (e) similarity to the nearest neighbor (SNN), and (f) fragment similarity (Frag.). We use the same split with Jo et al. (2022) for a fair comparison. Note that in contrast to other general graph generation methods, our approach uniquely facilitates the direct representation of ions by employing them as node type. We provide details in Appendix A.
Baselines. We compare GEEL with seven general deep graph generative models: EDP-GNN (Niu et al., 2020), GraphAF (Shi et al., 2020), GraphDF (Luo et al., 2021), GDSS (Jo et al., 2022), DiGress (Vignac et al., 2022), DruM (Jo al., 2023), and GraphARM (Kong et al., 2023). In addition, for further comparison, we also compare GEEL with four molecule-speciffe generative models: CharRNN (Segler et al., 2018), CG-VAB (Jin et al., 2020), MoFlow (Zang & Wang, 2020), and STGG (Ahn et al., 2022). We provide a detailed implementation description in Appendix B.
Results. The experimental results reported in Table 4. We observe that GEEL shows superior results to domain- aggostic graph generative models and competitive results with molecule-specinn generative models. In particular, for the QM9 dataset, observe that GEEL shows superior
8

---

Published as a conference paper at ICLR 2024
Table 5: Average MMD results for different model architectures.
Table 6: Average MMD for different representations. We adopted LSTM as model architecture and OOM de-
notes out-of-memory emror.
Backhone
Planar
Enzymes
Grid
LSTM 0.002
0.009
0.000
Representation
Repr.
Vocab.
Com--small
Grid
Point
Transformer
0.003
0.008
0.000
Flattened adj.
N²
2
0.029
0OM
OOM
Edge list
M
N²
0.010
0.000
00M
Edge list + intra gap
M
NB
0.013
0.000
O0M
GEEL (ours)
M
B².
0.016
0.000
0.044
results on FCD and Scaffold scores even compared to the molecule-specific models. We also provide visualization of generated molecules Appendix
4.3 ABLATION STUDIES
Different model architectures. Here, discuss the results of generating GEEL with Transformers (Vaswani et al., 2017). We evaluate four datasets: Planar, Lobster, Enzymes, and Grid, employing three MMD metrics for assessment. As presented in Table 5, LSTM shows competitive results to Transformers. Notably, LSTM achieves this performance with significantly reduced computa- tional cost, having linear complexity of O(n), in contrast the quadratic complexity O(n²) of Transformers, where n represents the sequence length.
Different representations. We discuss the results of gen- erating graphs with various representations here. We com- pare our GEEL with three alternative representations: flat- tened adjacency matrix, the edge list, and the edge list with intra-edge gap. The edge list the edge list with
12
C-M (8=19)
Training loss
10
BF5 (8-33)
8-
Random (8-347)
DFS (B-360)
traditional edge encoding (without any gap encoding) and
the last one is an edge list wherein the target node of each
edge is substituted by its intra-edge gap. Note that the edge lists are sorted in the same way we sort the edge list, explained in Section 3.1. The comparative results are in Table 6. We can observe that GEEL effectively reduces the vocabulary size compared other representations. This enables the generation of large-scale graphs, such as 3D point clouds, without memory constraints.
1000
2000
Epochs
Figure 5: Training curve with various node orderings.
Different node orderings. We here assess the effect of node ordering on graph generation. We compare our C- M ordering to BFS, DFS, and random ordering using the Grid dataset. As illustrated in Figure 5, the C-M order- ing outperforms others with faster convergence of training loss. Notably, the BFS also shows competitive loss con- vergence with C-M as it mitigates the burden long-term dependency. Specifically, both C-M and BFS orderings position edges related to the same node more closely than other baselines. These results highlight the effectiveness of C-M ordering on bandwidth reduction and generating high-quality graphs. Note that the MMD performance with any ordering eventually converges to the same levels of MMD as explained in Appendix H.
10
Orbit MMD
10-3
GRAN
BIGG
10-
GEEL
10K
# of nodes
Figure 6: Orbit MMD with various graph sizes.
Quality with various graph sizes. We also evaluate the generated graph quality with respect the graph size. Following prior work (Dai et al., 2020), we conduct experiments on grid data with (0.5k, 1k, 5k, 10k) nodes and reported orbit MMD. The results are in Figure 6 and we can see GEEL preserves high quality on large-scale graphs with up to 10k nodes.
5 CONCLUSION
In this work, we introduce GEEL, an edge list-based graph representation that is both simple and scalable. By combining GEEL with an LSTM, our graph generative model achieves O(M) complexity, showing significant enhancement in generation quality and scalability over prior graph generative models.

---

Published as a conference paper at ICLR 2024
Reproducibility All experimental code related to this paper is available at https:: / thub. Detailed insights regarding the experiments, encompassing dataset and model specifies, are available in Section 4. For intricate details like hyperparameter search, consult Appendix A. In addition, the reproduced dataset for each baseline is in Appendix B.
Acknowledgements This work partly tions Technology Planning & Evaluation (ITPP) grant funded by the Korea government (MSIT) (No. IITP-2019-0-01900 Artificial Intelligence Graduate School Program (POSTECH)), the Na- tional Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 0022IICIC111336) and Basic Science Research Program through the National Research Founda- tion of Korea (NRF) funded by the Ministry of Education 0022RIA6AI.N 1...AA003000 A0305525544))))
supported by Institute of Information & communica-
REFERENCES
Sungsoo Ahn, Binghong Chen, Tianzhe Wang, and Le Song. Spanning tree-based graph generation for molecules. In International Conference on Learning Representations, 2022. URL. https: //openreview. net/ o
3, 8, 14, 21, 25
Davide Bacciu and Marco Podda. Graphgen-redux: A fast and lightweight recurrent model for labeled graph generation. In 2021 International Joint Conference on Neural Networks (IJCNN),
pp. 1-8. IEEE, 2021. 1, 6
Phyllis Z Chinn, Jarmila Chvátalová, Alexander K Dewdney, and Norman E Gibbs. The bandwidth problem for graphs and matrices- survey. Journal of Graph Theory, 6(3):223-254, 1982. 2,
Michael Collins. Head-driven statistical models for natural language parsing. Computational linguistics, 2944)6589-637, 2003.
Elizabeth Cuthill and James McKee. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th national conference, pp. 157-172, 1969. 4
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International conference on machine learning, pp. 2302-2312. PMLR, 2020. 3, 5, 6, 9, 13, 14
Nathaniel Lee Diamant, Alex Tseng, Kangway V Chuang, Tommaso Biancalani, and Gabriele Scalia. Improving graph generation by restricting graph bandwidth. In International Conference on Machine Learning, pp. 7939-7959. PMLR, 2023. 2, 3, 4, 6, 7, 14, 26
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: a scalable approach to domain- agnostic labeled graph generation. In Proceedings of The Web Conference 2020, pp. 2020. 1, 3, 6, 14
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pp. 2434-2444. PMLR, 2019.
Minghao Guo, Veronika Thost, Beichen Li, Payel Das, Jie Chen, and Wojeiech Matusik. Data- efficient graph grammar learning for molecular generation. arXiv preprint 1xXiv:2203308031 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6855 2020.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997. 2, 5, 14
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool discover chemistry for biology. Journal of chemical information and modeling, 52(7):
1757-1768, 2012. 8
Yunhui Jang, Dongwoo Kim, and Sungsoo Ahn. Graph generation with Sk^2S-trees. In The Twelfth International Conference on Learning Representations, 2024, URL https: / //ppnreevee... net/ forum? net/forum?i A 6
10

---

Published as a conference paper at ICLR 2024
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-23322 PMLR, 2018. 1,
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International conference on machine learning, pp. 4839-4848, PMLR, 2020. 1, 3, 8,
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, pp. 10362-10383. PMLR, 2022. 3, 6, 7, 8, 13, 14, 21
Jachyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with destination-driven diffusion mixture. arXiv preprint arXiv:2302.03590 2023. 8, 14, 25
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang Autoregressive diffusion model for graph generation, 2023. URL httpa://openxevieew
net/forung 1d=:dd-44440 (0..-=98882xxx5555 6, 7, 8, 14
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 0rXiv:/803.03324, 2018.
Renjie Liao, Yujia Li, Yang Song. Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019. 3, 6, 7, 14
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. Advances in Neural Information Processing Systems, 32, 2019. 6, 14
Meng Liu, Kegiang Yan, Bora Oztekin, and Shuiwang Ji. Graphebm: Molecular graph generation with energy-based models. arXiv preprint arXiv:2102.005546 2021.
Tianze Luo. Zhanfeng Mo, and Sinno Jialin Pan. Fast graph generative model via spectral diffusion. arXiv preprint ar 2r2.v:2211... 08892, 2022. 14
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. In International Conference on Machine Learning, pp. 7192-7203. PMLR, 2021. 3, 6, 8, 14
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invertible flow model for generating molecular graphs. arXiv preprint arXiv: /905. 1600, 2019.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spec- tral conditioning helps overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning, pp. 15159-15179, PMLR, 2022. 6, 7, 14. 24
Lukasz Maziarka, Agnieszka Pocha, Jan Kaczmarczyk, Krzysztof Rataj, Tomasz Danel, and Michal Warchot. Mol-cyclegan: a generative model for molecular optimization. Journal of Cheminformat ics, 12(1):1-18, 2020. 1
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permu- tation invariant graph generation via score- based generative modeling. In International Conference on Artificial Intelligence and Statistics, pp. 4484 PMLR, 2020. 3, 6, 8, 14
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019. 14
Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-Lengeling, Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, et al. Molecular sets (moses): benchmarking platform for molecular generation models. Frontiers in pharmacology, 11 11:566644, 2020. 21

---

Published as a conference paper at ICLR 2024
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Gunter Klambauer. Fréchet chemnet distance: metric for generative models for molecules drug discovery. Journal of chemical information and modeling, 58(9): 177177166111,, 2018.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014. 8
Ida Schomburg, Antje Chang. Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 32(supp
2004. 6
Marwin HS Segler, Thierry Kogej, Christian Tyrchan, and Mark P Waller. Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS central science, 4(1): 120-131, 2018. 1, 8, 14
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):33-93, 2008. 6, 21
Elizabeth Senger. Polyominoes: Puzzles, patterns, problems, and packings. The Mathematics Teacher, 90(1):72, 1997.
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang. and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. arXiv preprint arX1v:2001.09382, 2020. 3, 6, 8, 14
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Coaring-ICANM) 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 27, pp. 412-422. Springer, 2018. 1, 3, 6, 14
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. 9
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint 2XX1:2209.14734 2022. 3, 6, 8, 13, 14, 24
Qi Yan, Zhengyang Liang, Yang Song, Renjie Liao, and Lele Wang. Swingnn: Rethinking permutation invariance in diffusion models for graph generation. arXiv preprint arXiv:2307.01646, 2023.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating
realistic graphs with deep auto-regressive models. In International conference machine learning, pp. 5708-5717. PMLR, 2018. 3, 5, 6, 13, 14
Chengxi Zang and Fei Wang. Moflow: an invertible flow model for generating molecular graphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 617-626, 2020. 8, 14
12

---

Published as a conference paper at ICLR 2024
A
EXPERIMENTAL DETAILS
In this section, we provide the details of the experiments.
A.1
GENERAL GRAPH GENERATION
Table 7: Hyperparameters of GEEL in general graph generation.
Planar
Lobster
Enzymes
SBM
Ego
Grid
Protenns
3D point cloud
Learning rate
0.001
0.0001
0.0005
0.0001
0.0001
0.001
0.0001
0.0012
Batch size
128
64
128
8
4
Table 8: Default hyperparameters of GEEL.
Input dropout rate
Dim. of token embedding
Num. of layers
0.1
512
3
We used the same split with GDSS (Jo et al., 2022) for Enzymes and Grid datasets, with DiGress (Vignac et al., 2022) for Planar and SBM datasets, with BiGG (Dai et al., 2020) for Lobster, Proteins, and 3D point cloud datasets, and with GraphRNN (You et al., 2018) for ego dataset. We perform the hyperparameter search to choose the best learning rate in (0.0001, 0.0005, 0.001, and 0.0012). We select the model with the best MMD with the lowest average of three graph statistics: degree, clustering coefficient, and 4-orbit count. In addition,
report the means of 5 different runs. It is notable that GEEL samples a C-M ordering for a graph at each training step (instead of fixing a unique ordering per graph). We found this to improve novelty without any decrease in performance and changing the hyper-parameters. We provide the best learning rates in Table 7 and other default hyperparameters that we have not tuned in Table 8.
A.2 MOLECULAR GRAPH GENERATION
We used the same split with GDSS (Jo et al., 2022) for fair evaluation. Following general graph generation, we perform the hyperparameter search to choose the best learning rate (0.0001, 0.001) and select the model with the best FCD score. The best learning rates 0.001 for both QM9 and ZINC datasets and other default hyperparameters are in Table 8 which the same as the general graph generation.
For ion tokenization, we used 13 node tokens for QM9: [C-]. [CH-], (C], (F), [N+], [N-], [NH+],
[NH2+], [NH3+), [NH], [N], [O-], [O]. In addition, used 29 tokens for ZINC: [Br), [CH-], [CH2-], [CH], [C], [CI], [F]. []]. [N+], [N-], [NH+], [NH-], [NH2+], [NH3+], [NH], [N], [O+], [O-], [OH+], [O], [P+], [PH+], [PH2], [PH], [P), [S+], [S-], [SH+], [S].
13

---

Published as a conference paper at ICLR 2024
B IMPLEMENTATION DETAILS
B.1 COMPUTING RESOURCES
We used Pytorch (Paszke et al., 2019) to implement GEEL and trained the LSTM (Hochreiter & Schmidhuber, 1997) models on GeForce RTX 3090 GPU. Note that we used A100-40GB for the 3D point cloud dataset. addition, due the CUDA compatibility issue of BiGG (Dai et al., 2020), we used GeForce GTX 1080 Ti GPU and 40 CPU cores for all models for inference time evaluation in Figure and Table 2.
B.2 DETAILS FOR BASELINE IMPLEMENTATION
Table 9: Reproduced dataset for each baseline.
Planar
Lobster
Enzymes
SBM
Ego
Grid
Proteins
3D point cloud
GRAN
GraphGen
/
BiGG
GDSS
DiGress
BwR
General graph generation. The baseline results from prior works are as follows. We reproduced GRAN (Liao et al., 2019), GraphGen (Goyal et al., 2020), DiGress ( (Vignac al., 2022), GDSS (Jo et al., 2022), BiGG (Dai et al., 2020), and BwR (Diamant et al., 2023) for the datasets that are not reported in the original paper using their open-source codes. The reproduced datasets are explained in Table 9. Note that BwR results are based on the GraphRNN variant, which shows the best results through three provided baselines. The other results for GraphVAE (Simonovsky & Komodakis, 2018), GNF (Liu et al., 2019), EDP-GNN (Niu et al., 2020), GraphAF (Shi et al., 2020), GraphDF (Luo al., 2021), and GDSS (Jo al., 2022) obtained from GDSS, while the results for GRAN (Liao et al., 2019), GraphRNN (You et al., 2018), 8), and BiGG (Dai et al.. 2020) are from BiGG and SPECTRE (Martinkus et al., 2022). Finally, the remaining results for SPECTRE and GDSM (Luo et al., 2022) are derived from their respective paper. We used original hyperparameters when the original work provided them.
Molecular graph generation. The baseline results from prior works are as follows. The results for five domain-ape aagnosicc graph generative models: EDP-GNN (Niu et al., 2020), GraphAF (Shi et al., 2020), GraphDF (Luo et al., 2021), GDSS (Jo et al., 2022), DruM (Jo et al., 2023) are from DruM, and the GraphARM (Kong et al., 2023) result is extracted from the corresponding paper. Moreover, reproduced DiGress (Vignac et al., 2022) using their open-source codes.
In addition, for molccule generative models, the result of MoFlow (Zang & Wang, 2020) is from DruM, the results of CG-VAE (Jin et al., 2020) and STGG (Ahn et al., 2022) is from STGG. Furthermore, we reproduced CharRNN (Segler et al., 2018).
B.3 DETAILS FOR INFERENCE TIME ANALYSIS
We conducted the inference time analysis using the same GeForce GTX 1080 Ti GPU for all models. The batch size is 10 and the inference time to generate single graph is computed by dividing the total inference time by the batch size.
B.4 DETAILS FOR THE IMPLEMENTATION
We adapted node ordering code from (Diamant et al., 2023), evaluation scheme from (Jo et al., 2022; Martinkus et al., 2022), and NSPDK computation from (Goyal et al., 2020).
14

---

Published as a conference paper at ICLR 2024
C
GRAPH STATISTICS OF DATASETS
C.1 GENERAL GRAPHS
Table 10: Statstics of general datasets.
Dataset
# of graphs
# of nodes
Max. B
Max. # of edges
Planar
200
[V| 64
26
Lobster
100
10 [
100
49
99
Enzymes
587
10 V
125
19
149
SBM
200
31 < V
187
111
1129
Ego
757
50.5/ V 399
241
1071
Grid
100
100 [V]
400
19
Protcins
918
13 < < 1575
125
1575
3D point cloud
41
8 V < 5037
167
10886
Table 11: Standard deviation of MMD in training dataset.
Planar
Lobster
Enzymes
SBM
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
0.000
0.001
0.000
0.003
0.000
0.006
0.001
0.003
0.002
0.008
0.002
0.017
(a) Small graphs (V max S 187)
Ego
Grid
Proteins
3D point cloud
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
0.005
0.001
0.004
0.000
0.000
0.000
0.001
0.002
0.001
0.04
0.062
0.017
(b) Large graphs (399 [V max S 5037)
The statistics of general graphs are summarized Table 10. It is notable that the bandwidths are relatively low compared to the number of nodes for real-world graphs, which enables the reduction of the vocabulary size of GEEL. In addition, we provide the standard deviations of MMD of training graphs that used as a criterion verify comparability in Table 11.
C.2 MOLECULAR GRAPHS
Table 12: Statstics of molecular datasets: QM9 and ZINC250K.
Dataset
of graphs
# of nodes
Max. B
Mux. # of edges
# of node types
of edge types
QM9
133,885
1
<
V V
9
5
13
13
4
ZINC250K
249,455
S
38
10
45
29
The statistics of molecular graphs are summarized in Table 12. Note that the # of node types indicate the number of ionized node type tokens as explained in Appendix A.
15

---

Published as a conference paper at ICLR 2024
D GENERATED SAMPLES
D.1 GENERAL GRAPH GENERATION
Planar
(a) Train
(b) GDSS
(c) GraphGen
eith mads
mode
(d) BiGG
(c) DiGress
(f) GEEL (ours)
Figure 7: Visualization of the graphs from the Planar dataset and the generated graphs.
Lobster
B-C6 9-18
Fare
a Train
(b) GraphGen
(c) GDSS
Bell Bell
0-25 5025
(d) DiGress
(c) GEEL (ours)
Figure 8: Visualization of the graphs from the Lobster dataset and the generated graphs.
16

---

Published as a conference paper at ICLR 2024
Enzymes
FOB BI1
(a) Train
(b) GRAN
(c) GraphGen
PALa
E-iL I-K
(d) BiGG
(e) DiGress
(c) GEEL (ours)
Figure 9: Visualization of the graphs from the Enzymes dataset and the generated graphs.
SBM
eX208 wol
BUTER PORE
CHLL wode
BUSE BOST
(a) Train
(b) GDSS
(c) GraphGen
BUIDE BOM
(d) BiGG
(c) GEEL (ours)
Figure 10: Visualization of the graphs from the SBM dataset and the generated graphs.
17

---

Published as a conference paper at ICLR 2024
Ego
POTE HITTS
(a) Train
(b) GRAN
(c) GraphGen
WITH
(d) BiGG
(c) GDSS
(c) GEEL (ours)
Figure 11: Visualization of the graphs from the Ego dataset and the generated graphs.
Grid
will
and
E-ILL IIS
6-46 9-36
8-18 1-18
(a) Train
(b) GDSS
(c) GraphGen
EXTTE
(d) DiGress
(c) GEEL (ours)
Figure 12: Visualization of the graphs from the Grid dataset and the generated graphs.
18

---

Published as a conference paper at ICLR 2024
Proteins
EIOM FAST
(a) Train
(b) GraphGen
parS 2013
GHEM POER
(c) GDSS
(d) GEEL (ours)
Figure 13: Visualization of the graphs from the Proteins dataset and the generated graphs.
We present visualizations of graphs from the training dataset and generated samples from GRAN, GraphGen, BiGG, GDSS, DiGress, and GEEL in Figure 7, Figure 8, Figure 9, Figure 10, Figure 11, Figure 12, and Figure 13. Note that only provide the visualization that have reproduced, which detailed in Appendix B. We additionally give the number of nodes and edges of each graph, where denotes the number of nodes and denotes the number of edges.
19

---

Published as a conference paper at ICLR 2024
D.2 MOLECULAR GRAPH GENEREATION
Figure 14: Visualization of the molecules generated from the QM9 dataset.
x Jroo 34 SIa
gooo
trao
504
Anuvo
aax
PUPES Dgo got olnoo
pudo you
$
aopu Bhn wyo outa sould
Figure 15: Visualization of the molecules generated from the ZINC250K dataset. We provide visualizations of generated molecules using GEEL in Figure 14 and Figure 15.
20

---

Published as a conference paper at ICLR 2024
E
ADDITIONAL EXPERIMENTAL RESULTS
E
GENERAL GRAPH GENERATION
Table 13: General graph generation on small graphs (V max S 20)
Ego-small
Community-sman
4 S
[V] s
18
12 < [V]
20
Method
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Training
0.025
0.035
0.012
0.020
0.044
0.003
GrE
0.130
0.170
0.050
0.350
0.980
0.540
GraphRNN
0.090
0.220
0.003
0.080
0.120
0.040
GRAN
0.009
0.038
0.009
0.005
0.142
0.090
GNF
0.030
0.100
0.001
0.200
0.200
0.110
EDP-GNN
0.052
0.093
0.007
0.053
0.144
0.026
GraphGen
0.085
0.102
0.425
0.075
0.065
0.014
GraphAF
0.030
0.110
0.001
0.180
0.200
0.020
GraphDF
0,040
0.130
0.010
0.060
0.120
0.030
BiGG
0.013
0.030
0.005
0.004
0.005
0.000
GDSS
0.021
0.024
0.007
0.045
0.086
0.007
DiGress
0.021
0.026
0.024
0.012
0.025
0.002
GDSM
0.011
0.015
0.001
GraphARM
0.019
0.017
0.010
0.034
0.082
0.004
SwinGNN
0.000
0.021
0.004
0.003
0.051
0.004
GEEL (ours)
0.020
0.035
0.012
0.020
0.022
0.006
We provide general graph generation results for smaller graph datasets: Ego-small and Community- small. The Ego-small dataset consists of 300 small ego graphs from larger Citeseer network (Sen et al., 2008) and Community-small dataset consists of 100 randomly generated community graphs. We used the same split with GDSS (Jo et al., 2022) and the results are reported in Table 13.
E.2 MOLECULAR GRAPH GENERATION
We provide molecular graph generation results for MOSES benchmark (Polykovskiy et al., 2020) in Table 14.
Table 14: Molecular graph generation performance of MOSES dataset. The baseline results are from prior works (Polykovskiy al., 2020; Ahn et al., 2022). The best results are highlighted in bold and the second best are underlined.
MOSES
Method
Validity (8) f NSPDK
FCD J
Scaf. +
SNN
Frag. f
Molecule generative models
CharRNN JT-VAE STGG
97.48
0.0732
0.9242
0.6015
0.9998
100.00
0.3954
0.8964
0.5477
0.9965
100.00
0.0680
0.9416
0.6359
0.9998
Domain-agnostic graph generative models
DiGress GEEL (Ours)
100.00
0.0005
0.6788
0.8653
0,5488
0.9988
99.99
0.0001
0.1603
0.8622
0.6310
0.9996
21

---

Published as a conference paper at ICLR 2024
F ADDITIONAL METRICS
F.1 GENERAL GRAPH GENERATION
We provide three additional metries: validity, uniqueness, and novelty scores for general graph generation in Table 15. GEEL achieves from 30% to 90% novelty, which is better than autoregressive models like GRAN and BiGG, but lower than the ceffusion-baseer graph generative models. This is partially due to the inherent trade-off between novelty and the capability of generative models to learn the data distribution faithfully. OOM indicates out-of-memory and N.A. for BwR indicates that the generated samples are all invalid.
22

---

Published as a conference paper at ICLR 2024
F.2 MOLECULAR GRAPH GENERATION
We also provide the uniqueness and novelty scores for QM9 and ZINC in Table 16. We can observe that our GEEL shows competitive novelty and uniqueness compared to the baselines. Notably, the models make a tradeoff between the quality (e.g., NSPDK and FCD) and novelty of the generated graph since the graph generative models that faithfully learn the distribution put high likelihood on the training dataset. In particular, the tradcoff is more significant in QM9 due to the large dataset size (134k) compared the relatively small search space (molecular graphs with only up to nine heavy atoms).
23

---

Published as a conference paper at ICLR 2024
Table 15: The results of general graph generation include validity, uniqueness, and novelty. The baseline results are from prior works (Martinkus et al., 2022; Vignac al., 2022) or obtained by running the open-source codes.
Planar
Lobster
[V]
10 [V] S 100
Method
Deg. (4)
Clu. (1)
Orh. (.)
Val. (1)
Uniq. (t)
Nov. (f)
Deg. (4)
Clu. (L)
Orb. (L)
Val. (f)
Uniq. (1)
Nov. (1)
GruphRNN
0.278
100.0
GRAN
0.001
0.043
0.001
97.5
85.0
2.5
0.038
0.000
0,001
SPECTRE
0.001
0.079
0.001
25.0
100.0
100.0
BiGG
100.0
0.0
GDSS
0.250
0.393
0.587
0.0
100.0
100.0
0.117
0.002
0.149
18.2
100.0
100.0
DiGress
0.000
0.002
0.008
85.0
100.0
100.0
0.021
0.000
0.004
54.5
100.0
100.0
BwR GraphRNN
0.609
0,542
0.097
52.5
95.0
100.0
0.316
0.000
0.247
100.0
63.6
100.0
Gruphite
3.4
100.0
100.0
0.076
0.0
BwR EDP-GNN
1.127
1.032
0.066
0.0
100.0
100.0
0.257
0.062
0.166
0.0
100.0
100.0
GEEL (ours)
0.001
0,010
0.001
82.5
97.5
27.5
0.002
0.000
0.001
72.7
100
72.7
GREL
0.006
92.5
92.5
15.0
0.001
0.006
1000
81.8
Eazymes
SBM
10 S [V] 125
[V] 187
Method
Deg. (4)
Clu. (4)
Orb. (L)
Uniq. (f)
Nov. (f)
Deg. (.)
Clu. (4)
Orb. (4)
Uniq. (1)
Nov. (1)
GraphRNN
0.017
0.062
0.046
0.006
0.058
0,079
100.0
100.0
GRAN
0.023
0.031
0.169
100.0
94,9
0.011
0.055
0.054
100.0
100.0
SPECTRE
0.002
0.052
100.0
BiGG
0.010
0,018
0.011
78.8
4.2
110229
0.003
0.036
92.5
10.0
GDSS
0.026
0.061
0.009
0.496
0.456
0.717
100.0
100.0
DiGress
0.011
0.010
100.0
0,006
0,051
0,058
100.0
100.0
BwR GriphRNN
0.021
0.095
0.025
97.5
100.0
N.A.
N.A.
N.A.
N.A.
N.A.
BwR Graphite
0.213
0,270
0.056
100.0
100.0
1,305
1.341
1,056
100.0
100.0
BwR EDP-GNN
0.253
0.118
0.168
100.0
100.0
0.657
1.679
0.275
100.0
100.0
GEEL (ours)
0.005
0.018
0.006
100.0
94.9
0.025
0.003
0.026
95.0
42.5
GEEL + No PE
0.005
0.014
0.002
100.0
93.2
0.013
0.002
0.028
100.0
35.0
Ego
Proteins
50 S [V] S 399
13 S [V] S 1575
Method
Deg. (L)
Clu. (U)
Orb. (L)
Uniq. (t)
Nov. (t)
Deg. (-)
Clu. (4)
Orb. (1)
Unig. (1)
Nov. (1)
GraphRNN
0.117
0.615
0.043
0.011
0.140
0.880
100.0
100.0
GRAN
0.026
0.342
0.254
0.002
0.049
0.130
100.0
100.0
SPECTRE
0.013
0.047
0.029
100.0
100.0
BiGG
0.010
0.017
0.012
89.5
57.2
0.001
0.026
0.023
GDSS
0.393
0.873
0.209
100.0
100.0
0.703
1.444
0.410
99.5
100.0
DiCiress
0.063
0.1311
0.024
100.0
100.0
0OM
00M
OOM
OOM
00M
BwR GraphRNN
N.A.
N.A.
N.A.
N.A.
N.A.
0.092
0.229
0.489
BwR Gruphite
0.229
0.123
0.054
100.0
100.0
0.239
0.245
0.492
BwR EDP-GNN
OOM
OOM
0OM
OOM
0OM
0.184
0,208
0.738
GEEL (ours)
0.053
0.017
0.016
89.4
62.8
0.003
0.005
0.003
93.7
88.9
3d point cloud
8 < [V] < 5037
Method
Deg. (L)
Clu. (L)
Orb. (L)
Uniq. (1)
Nov. (t)
GrL
00M
0OM
0OM
OOM
OOM
GraphRNN
OOM
00M
0OM
OOM
0OM
GRAN
0.018
0.510
0.210
BiGG
0.003
0.007
GDSS
0OM
0OM
OOM
OOM
OOM
DiGress
OOM
OOM
OOM
OOM
OOM
BwR GraphRNN
1,820
1.295
0.869
100.0
100.0
BwR Gruphite
OOM
OOM
0OM
BwR EDP-GNN
OOM
OOM
OOM
0OM
0OM
GEEL (ours)
0.002
0.081
0.020
100.0
80.0
24

---

Published as a conference paper at ICLR 2024
Table 16: Molecular graph generation performance of the QM9 and ZINC datasets including novelty and uniqueness. The baseline results from prior works (Jo al., 2023; Ahn et al., 2022). The best results of molecule generative models and domain-agnostic generative models are both highlighted in bold.
QM9
Method
Validity (%)
NSPDK
FCD (J)
Seaf. (t)
SNN (t)
(1)
Unique. (f)
Novelty (1)
Molecule-ppccficc generative models
CharRNN
0.9313
0.9887
CG-VAE
100.0
1.852
0.6628
0.3940
0.9484
MoFlow
91.36
0.0169
4.467
1444
0.3152
0.6991
98.65
94.72
STGG
100.0
0.585
0.9416
0.9998
0,9984
96.76
72.73
Domain-agnostic graph generative models
EDP-GNN
47.52
0.0046
2,680
0.3270
0.3265
0.8313
99.25
86.58
GraphAF
74.43
0.0207
5.625
0.3046
0.4040
0.8319
88,
86.59
GraphDF
93.88
0.06366
10.928
0.0978
0.2948
0.4370
98.58
98.54
GDSS
95.72
0,0033
2.900
0.6983
0.3951
0.9224
98.46
86.27
DiGress
98.19
0.0003
0.095
0.9353
0.5263
0.0023
96.67
25.58
DruM
99.69
0.0002
0.108
0.9449
0.5272
0.9867
96.90
24.15
GraphARM
GEEL (ours)
100.0
0.0002
0,089
0.9386
0.5161
0,9891
96.08
22.30
ZINC
Method
Validity (8)
NSPDK (L)
(1)
(t)
SNN (t)
Fra. (t)
Unique. (%) (t)
Novelty (58) (t)
Molecule specific generative models
CharRNN
0,474
0.4024
CG-VAE
100.0
11.335
0.2411
0.2656
0.8118
MoFlow
0.1447
100.00
STGG
63.11
0.0455
20.931
0.0133
0.2352
0,7508
99.99
99.89
agnostic graph generative
EDP EDP.GNN GNN
63.11
0.0485
16.737
0.0000
0.0815
0.0000
99.79
100.00
GraphAF
0.0672
GraphDF
90.61
0.1770
33.546
0.0300
0.1722
0.2049
99.63
100.00
GDSS
0.0195
14.656
0.0467
0.2789
0.81
99.64
100.00
DiGress
94.99
0.0021
3.482
0.4163
0.3457
0.9679
99.97
99,99 99.99
DruM
98.65
0.0015
2.257
0.5299
0.3650
0.9777
99.97
99.98
GraphARM
58.23
0.0550
16.260
GEEL (ours)
99.31
0.0068
0.401
0.5565
0.4473
0.992
99.97
99.89
25

---

Published as a conference paper at ICLR 2024
G DISCUSSION
G.1 LIMITATION
In this section, we discuss the limitations of our GEEL. The limitation of GEEL is two-fold: (1) unable to generate graphs with unseen tokens and (2) dependency on the bandwidth. Since GEEL based on the vocabulary with gap-encoded edge tokens, the model cannot generate the graphs with unseen tokens, i.e., the graphs with larger bandwidth than the training graphs. Nonetheless, we believe the generalization capability of our GEEL is strong enough in practice. In all the experiments, verified that vocabulary obtained from the training dataset entirely captures the vocabulary required for generating graphs in the test dataset.
Another limitation is the dependency square of the bandwidth. It is true that the vocabulary size of GEEL is highly dependent on the bandwidth. However, most of the worldw large-scale graphs have small bandwidths as described in Table 12 so B being as large as N is rare in practice. Additionally, for larger graphs with B = N, one could consider (a) decomposing the graph into subgraphs with small bandwidth and (b) separately generating the subgraphs using GEEL. This would be an interesting future avenue of research.
the bandwidth, i.c., the vocabulary size of GEEL is the
G.2 COMPARISON TO BwR
Here, we compare our GEEL to BwR (Diamant et al., 2023). Our work proposes a new edge list representation with the vocabulary size of B with gap encoding. Although we promote reducing the bandwidth B using the C-M ordering, as proposed by BwR, our key idea, the gap encoding edge list is orthogonal to BwR. Our analysis of 3 vocabulary size simply follows the definition of graph bandwidth. Morcover, one could also choose any bandwidth minimization algorithm (c.g., BFS ordering used in GraphRNN) reduce the vocabulary size B²
In detail, we compare our GEEL to three variants BwR. First, BWR+GraphRNN iteratively adds node to the graph by adding the neighbors independently at once using multivariate Bernoulli distribution. This ignores the dependencies between adjacent edges, which our GEEL captures via the edge-wise updates. Next, BwR+Graphite the whole graph in a one-shot manner. This also does not consider the edge dependencies during generation, while our GEEL does. Finally, BwR+EDP-GIN the continuous relaxation of the adjacency matrix. It requires the generative model to learn the complicated reverse diffusion process, which results in underfitting of the model. This issue is especially significant since the BwR+EDP-GNN uses a small number of 200 diffusion steps.
VAE-based generative model that generates
is a diffusion- based model that generates
26

---

Published as a conference paper at ICLR 2024
H ADDITIONAL RESULTS FOR ABLATION STUDY
Deg.
Clus.
Orb.
BFS
0.000
0.000
0.000
DFS
0.000
0.000
0.000
Random
0,000
0.000
0.000
C-M
0.000
0.000
0.000
Table 17: MMD on different node orderings
We provide the MMD performance of the ablation study on different orderings of Section 4.3 in Table 17. We can observe that the generation with any ordering eventually converges to the same levels of MMD.
27


Reviews:
[{"review_id": "eNFkdlEnkI", "reviewer": "Reviewer_EmZF", "summary": "Authors introduce a new parametrization for sequential generation of graphs. The parametrization is based on edge-lists with the main trick being encoding not the node IDs but difference between them. The use of C-M ordering is promoted and shown to be better than the usual DFS or BFS orderings used in the previous autoregressive models. Overall the proposed architecture is shown to be much faster than existing approaches and offer better or competitive results in graph generation quality.", "questions": "I would really like to see the uniqueness and novelty for all the models in the datasets that were tested. Validity as introduced in SPECTRE is also an interesting measure to have, that's maybe more easy to interpret than the MMDs, where it is available.\n\nI'll raise my score if this is addressed. I just don't think we can accept the paper without this information.\n\n### After Rebuttal\nI thank the authors for all the additional experiments and adjustments, esp. w.r.t. BwR.\nWhile the novelty and uniqueness of generated graphs is mediocre and performance is not really better than the newest one-shot models (e.g. SwinGNN), the proposed change is neat and does improve upon autoregressive baselines. Thus I raise my score.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed representation is very interesting and efficient. It also meshes well with the C-M ordering. \nThe choices are extensively ablated and shown to be better than alternatives. The experimental performance overall seems strong and experimental scalability is good. \nThe paper is well written and easy to follow.", "weaknesses": "My main concern with the paper are the evaluation metrics reported for the graph generation. First, only local MMD scores are reported (e.g. no Spectral MMD as used in GRAN or SPECTRE), but mainly that the novelty and uniqueness of the generated examples is not reported. As shown in the SPECTRE paper, autoregressive models such as GRAN can overfit the training set to a point, where effectively no novel samples are produced, while at the same time producing amazing MMD metrics. Since this work is essentially turbocharging the autoregressive generation, especially with the relative node ID representation, one could imagine that such overfitting would be a problem. After all this overfitting is one of the main motivations for using one-shot generative models without a given node ordering. Uniqueness and novelty is also commonly reported for the molecule generation as well.\n\nIt would also be interesting to see how some of the one-shot methods (e.g. DiGress) would perform with the C-M ordering and node IDs. As they tend to make GNNs more powerful. Actually a recent paper (https://arxiv.org/pdf/2307.01646.pdf) showed quite some improvements in the one-shot graph generators by using a known ordering. It would make sense to include this in the baselines.", "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": "JlkgoGukwO", "reviewer": "Reviewer_kVSU", "summary": "This paper proposes GEEL, a novel method to generate graphs starting from their sorted edge list. In particular, the edge list is encoded through gaps: each pair of nodes representing an edge becomes a pair where the first element is the gap from the previous pair's first element, while the second element encodes the gap from the current pair's first element. This has the advantage of reducing the vocabulary size from $N^2$ (where $N$ is the number of graph nodes) to $B^2$ (where $B$ is the graph bandwidth), while maintaining the cost of training and inference to be $O(M)$ (where $M$ is the number of edges). The method is extended to deal with attributed graphs by proposing a simple grammar whose elements are triplets of the form (node type token, gap-encoded edge, edge type token), plus rules to compose them meaningfully. \n\nThe generative model is an auto-regressive LSTM that is trained to maximize the likelihood of the training graphs (represented as sequences of gap-encoded edge pairs). The model is evaluated extensively in task of generating a) standard non-attributed graphs such as lobster, ego, community and b) molecules. The experiments show that a) the proposed approach achieves good generative performance with respect to a wide pool of competitors, b) it uses a parsimonious representation which allows reduced vocabulary size and competitive training/inference cost. Lastly, ablation studies are presented to justify the architectural choices.", "questions": "I have some:\n\n- What do the asterisks placed after Graphgen and Graphgen-redux in Table 1 mean?\n- What is meant by \"comparable\" MMD? Which criteria is used to define two MMDs comparable?\n- In Figure 4, what is the value of the $c_1$ and $c_2$ constants? Have they been explicitly calculated?\n- What are the novelty and uniqueness rates achieved by GEEL in the molecular generation experiments? How do they compare to the competitors? For example, I recall CharRNN has a novelty rate of about 84% on the MOSES benchmark, while STGG has a novelty rate of 67% on the same benchmark.\n- Speaking of which, I think it would be better to add the performances of the method in the MOSES benchmark. It should be fairly doable in a short time since the method is fast both in training and inference.\n- What are the vocabulary sizes for the molecular generation experiments (on QM9 and ZINC250k)?\n- Which order is used to encode the edge list of molecules? Is it the SMILES canonical order?\n- If the answer to the question above is yes: as you might know, SMILES works by generating a spanning tree, and then adding the edges that close the rings at the end. Don't you think this kind of process is not ideal to gap-encode the edge list of molecules (since the second element of the closing ring edges would have an abnormally wider gap with respect to the other edges)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I am very pleased with this paper: it is written clearly and easy to follow. On the technical side, it presents a simple but empirically effective contribution, which addresses most of the challenges of edge-list based graph generative methods, namely the large vocabulary sizes and the burden of having to learn long-term dependencies as a consequence. Following, a list of things I identify as strengths:\n\n- The main contribution (the gap-encoded edge list) is novel.\n- The proposed approach is extremely simple yet very effective.\n- The literature review is satisfactory (although it is missing [1] as another edge-list based generative method, but that is a minor omission).\n- The experiments are thorough, spanning across different graph types and a not common wide range of baselines.\n- I appreciated the ablation study which help understanding why certain modelling choices were taken.\n\n\n\n[1] Bacciu et al., Edge-based sequential graph generation with recurrent neural networks. Neurocomputing 2020.", "weaknesses": "The weaknesses I have found are by no means fatal, and I believe they could be addressed through proper rebuttal. In particular:\n\n- perhaps this article is not well-suited for ICLR, since the focus should be on learning representations, but this paper does not revolve around representation learning. Again, I don't think this is fatal, and I would like to hear how this work places itself in the context of this conference by the authors.\n\n- while very effective, this method has also limitations which are not mentioned by the authors. The main one being the fact that it is still a vocabulary-based approach that cannot generalize to graphs with gap-encoded edges not present in the vocabulary. Another one is the dependency on the bandwidth $B$, which can sometimes be $\\approx N$ due to outliers. I understand that this can be bypassed by removing the outliers, but then again it restricts the applicability of the method to a certain class of graphs (those with low bandwidth) to exploit the concise gap-encoding.", "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": "3vLCUCmjdb", "reviewer": "Reviewer_RDfu", "summary": "Good paper, extensive evaluations.\n\nThe paper proposes a simple and scalable graph representation i.e  gap encoded edge list (GEEL) for graph generative modeling.\nThe  representation size  aligns with the number of edges instead of nodes, consequently low size and more applicable for sparse graphs.\n\nThere do exists works which use O(#edges) for representation, however, the proposed work GEEL further reduces the edge list representation by reducing vocabulary size from N^2 to B^2, where B is graph bandwidth.\n\nThe authors extend their approach to attributed graphs(having labels).\n\nEmpirical evaluation is performed on a large number of attributed and non-attributed datasets on a diverse set of graph similarly metrics.\nThe approach also scales better in terms of inference speed when compared to existing works.\n\nOverall the approach shows significant improvements over existing methods for graph generative modeling tasks.", "questions": "1. It is not clear or I could not find out how many graphs were generated by the proposed method/ baselines for each dataset? I agree MMD is computed but how many graphs were generated? Request the authors to add this.\n\n2. Results on Uniqueness and Novelty seem to be missing. It is not clear whether the generated graphs have duplicacy etc.\nRefer metrics section of [A] for details.\nAdding these metrics(atleast for few datasets) could further improve the quality of the manuscript.\n\n3. Could the authors clarify how scalaibiltiy results are computed? I mean is batch size etc. set to 1? \nAlso since GraphGen[A] also works at edge list level O(#Edges), I would expect the authors to compare with GraphGen for scalability comparison.\nCan the authors justify why generation time is shown for one graph? Could it be an outlier?  I see only one number without any standard deviation etc.\nWould it make sense to generate a batch of graphs and report mean+std dev.\n\n\n\n\n\n[A]Goyal et al. GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation, WWW 2020", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Novel approach for graph generative modeling-> compact representation of data.\n\n2. Paper is easy to read. The authors clarify the need of each component. Diagrams are provided for better understanding of the method.\n\n3. Ablation studies are conducted to understand  impact of different sequence encoding(DFS, BFS etc.), diff architectures for sequence modeling such as LSTM, Transformers etc.\n\n4.High reproducibility: The experimental section is very detailed  with respect to the current work as well as baselines. Code is also provided.\n\n5. The authors also visualize generated graphs.\n\nSignificance:\nThe proposed method could pave way for advancing research in context of graph generative modeling especially w.r.t to larger graphs( which are also attributed).", "weaknesses": "I would point to the questions section for details\n\n1. Not clear how many graphs are generated for comparison.\n\n2. Results on uniqueness and novelty metric seem to be missing.\n\n3. Scalability analysis doesn't seem to be complete.\n\nI request the authors to look into the questions section for details on each of the above point.", "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": "JN5XIzCplP", "reviewer": "Reviewer_aPij", "summary": "This paper proposes a molecule graph generation model GEEL, whose backbone can be LSTM or Transformer. GEEL is scalable to relatively large graphs in molecule generation. GEEL reduces the vocabulary size of the edge list representation by using intra- and inter-edge gap encodings. This proposed edge encoding method is novel.", "questions": "If this paper includes some ablation study of replacing the intra- and inter-edge gap encoding with traditional encodings, it will be better. Table 6 could include more experiment results. The parameter size can be adjusted to avoid Out-Of-Memory.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. It is good to have a table like Table 9 to show reproduced datasets.\n2. The intra- and inter-edge gap encoding is delicate and useful.\n3. The use of LSTM reduces the time complexity.", "weaknesses": "1. There is a problem in Appendix C.1 Table 11 (b) Large graphs (|V|max ≤ 187).\n\n2. For the molecule generation task, it is important to generate some novel molecules for further filtering in drag design and other real-world scenarios. This paper does not evaluate the portion of the novel-generated molecules in Table 4. In the extreme case, the model may only be able to generate molecules in the training set.\n\n3. It is hard to claim that GEEL outperforms BiGG. In Table 1, the performance is close. In terms of speed, BiGG runs on GeForce GTX 1080 Ti while GEEL runs on GeForce RTX 3090, which makes Table 2’s result unfair.", "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)