Graph Generation with  $K^2$-trees
Authors: Yunhui Jang
Dongwoo Kim
Sungsoo Ahn
Venue: ICLR 2024 poster (2024)
Keywords: Graph generative models
graph neural networks
Primary area: generative models
TL;DR: We propose a new graph generative model based on the  $K^2$-tree, which is a compact and hierarchical representation for graphs.

Abstract: Generating graphs from a target distribution is a significant challenge across many domains, including drug discovery and social network analysis. In this work, we introduce a novel graph generation method leveraging $K^2$ representation, originally designed for lossless graph compression. The $K^2$ representation enables compact generation while concurrently capturing an inherent hierarchical structure of a graph. In addition, we make contributions by (1) presenting a sequential $K^2$ representation that incorporates pruning, flattening, and tokenization processes and (2) introducing a Transformer-based architecture designed to generate the sequence by incorporating a specialized tree positional encoding scheme. Finally, we extensively evaluate our algorithm on four general and two molecular graph datasets to confirm its superiority for graph generation.

Published as a conference paper at ICLR 2024
GRAPH GENERATION WITH -TEES
Yunhui Jang, Dongwoo Kim, Sungsoo Ahn Pohang University of Science and Technology (uni5510, dongwookim, sungsoo. ahn ) @postech. kr
ABSTRACT
Generating graphs from a target distribution is significant challenge across many domains, including drug discovery and social network analysis. In this work, we introduce novel graph generation method leveraging K²-tree representation, originally designed for lossless graph compression. The K representation encompasses inherent hierarchy while enabling compact graph generation. In addi- tion, we make contributions by (1) presenting a sequential K K representation that incorporates pruning. flattening, and tokenization processes and (2) introducing a Transformer-base architecture designed to generate the sequence by incorporat- ing specialized tree positional encoding scheme. Finally, we extensively evaluate our algorithm on four general and two molecular graph datasets to confirm its superiority for graph generation.
INTRODUCTION
Generating graph-stie graph-structured data is a challenging problem in numerous fields, such as molecular design (Li et al.. 2018: Maziarka et al., 2020), social network analysis (Grover et al., 2019), and public health (Yu et al., 2020). Recently, deep generative models have demonstrated significant potential in addressing this challenge (Simonovsky Komodakis, 2018: et al., 2022: Vignac et al., 2022). In contrast to the classic random graph models (Albert & Barabási, 2002; Erdós et al., 1960), these methods leverage powerful deep generative paradigms, e.g., variational autoencoders (Simonovsky Komodakis, 201 8), normalizing flows (Madhawa et al., 2019), and diffusion models (Jo et al., 2022).
The graph generative models can be categorized into three types by the graph representation the models generate. First, adjacency matrix is the most common representation (Simonovsky & Komodakis, 2018; Madhawa et al., 2019; Liu et al., 2021). Secondly, a string-base based representation graph can represent the graph
extracted from depth- first tree traversal et al., 2022; Goyal et al., 2020; Krenn et al., 2019). Finally, representing a graph as a composition of connected motifs, i.e., frequently appearing subgraphs, can preserve the high-level structural properties (Jin et al., 2018; 2020). We describe the representations on the left of Figure 1.
sequence (Ahn
Although there is consensus the best graph representation, two factors drive their development. First is the need for compactness to reduce the complexity of graph generation and simplify the search space over graphs. For example, to generate a graph with N vertices and M edges, the adjacency matrix requires specifying N elements. In contrast, the string representation typically requires specifying O(N + .M) elements, leveraging the graph sparsity (Ahn et al., 2022; Goyal al., 2020; Segler et al., 2018). Motif representations also save space by representing frequently appearing subgraphs by basic building blocks (Jin et al., 2018; 2020).
The second factor driving the development of new graph representations is the presence of a hierarchy in graphs. For instance, community graphs possess underlying clusters, molecular graphs consist of distinct chemical fragments, and grid graphs exhibit repetitive coarse- -ranniigganingggggg structure. In this context, motif representations (Jin et al., 2018; 2020) address the presence a hierarchy in graphs; however, they limited fixed vocabulary of motifs observed in the dataset or specific domain.
Contribution, In this paper, we propose a novel graph generation framework, coined Hierarchical Graph Generation with 2 (HGGT), which can represent not only non-attributed graphs but also attributed graphs in a compact and hierarchical way without domain -omain--pecific rules. The right-side table of Figure emphasizes the benefits of HGGT. Since the K?_ recursively redefines

---

Published as a conference paper at ICLR 2024
Adjacenry
String-bosed
Method
Repr.
H
A
DA
Graph
CN(C)C
GraphRNNN
Adj.
X
X
GraphGen
String
X
V
/
Motit based
K"
JT-VAE
Motif
/
J
x
GDSS
Adj.
X
J
HGGT (ours)
K2-tree
V
J
Figure I: (Left) Various representations used for graph generation. (Right) Comparing graph generative methods in terms of used graph representation. The comparison is made with respect to method being hierarchical (H), able to handle attributed graphs (A), and domain-agnose (DA).
a graph into K2 substructures, our representation becomes more compact and enables consideration of hierarchical structure in adjacency matrices.'
Specifically, we model the process of graph generation as an autoregressive construction of the K2-tree. To this end, design sequential K2-tree representation that recovers the original K2-tree when combined sequentially. In particular, we propose a two-stage procedure where (1) we prune the K²-tree remove redundancy arising from the symmetric adjacency matrix for undirected graphs and (2) subsequently flatten and tokenize the - into sequence to minimize the number of decisions required for the graph generation.
We employ the Transformer architecture (Vaswani et al., 2017) to generate the sequential K representation of graph. To better incorporate the positional information of each node in tree, we design a new positional encoding scheme specialized to the - structure. Specifically, we represent the positional information of a node by its pathway from the root node; the proposed encoding enables the reconstruction of the full Keetree given just the positional information.
To validate the effectiveness of our algorithm, we test our method on popular graph generation benchmarks across six graph datasets: Community, Enzymes (Schomburg et al., 2004), Grid, Planar, ZINC (Irwin et al., 2012), and QM9 (Ramakrishnan et al., 2014). Our empirical results confirm that HGGT significantly outperformed existing graph generation methods on five out of six benchmarks, verifying the capability of our approach for high-quality graph generation across diverse applications.
To summarize, our key contributions follows:
We propose
graph generative model based on adopting the R compact, hierarchical, and domain-agnostic representation of graphs.
We introduce novel, compact sequential K2-tree representation obtained from pruning, flattening, and tokenizing the 2
We propose an autoregressive model generate the sequential K2-tree representation using Transformer architecture with specialized positional encoding scheme.
We validate the efficacy of our framework by demonstrating saute-of-th-aas graph generation performance on five out of six graph generation benchmarks.
2 RELATED WORK
Graph representations for graph generation. The choice of graph representation is crucial aspect of graph generation, as it significantly impacts the efficiency and allows faithful learning of the generative model. The most widely used one the adjacency matrix, which simply encodes the pairwise relationship between nodes (Jo et al., 2022; Vignac et al., 2022; You et al., 2018; Liao et al., 2019; Shi al., 2020; Luo al., 2021: Kong al., 2023: Chen al., 2023). However, several methods (Vignac et al., 2022; You et al., 2018 8; Jo et al., 2022) suffer from the high complexity in generating the adjacency matrix, especially for large graphs.
'This differs from the conventional hierarchical community structure. We provide the discussion in Ap- pendix H.
2

---

Published as a conference paper at ICLR 2024
Adjacency matrix and its submatrices
Q
Q
8
0
U
O
O
O
O
0
O
0
Level (roof)
Level I
Level
Level 3
Root
Level 0
Level
Level
Level
Input graph G
K² tree T
Figure 2: Kretree with K = 2. The K describes the hierarchy of the adjacency matrix iteratively being partitioned K K submatrices. It is compact due to summarizing any zero-filled submatrix with size larger than 1 x (shaded in grey) by leaf node with label 2u. = 0.
To address this issue, researchers have developed graph generative models that employ alternative graph representations such motif-bases representations and ttring-based representations. For instance, Ahn et al. (2022); Segler et al. (2018) proposed to generate molecule-specine string representations, and Jin et al. (2018; 2020); Yang al. (2021) suggested generative models that extract reasonable fragments from data and generate the set of motifs. However, these methods rely on domain-specific knowledge and are restricted to molecular data.
Lossless graph compression. Lossless graph compression (Besta & Hoefler, 2018) aims to reduce the size and complexity of graphs while preserving their underlying structures. Specifically, several works (Brisaboa et al., 2009; Raghavan & Garcia-Moling 2003) introduced hierarchical graph compression methods that compress graphs leveraging their hierarchical structure. addition, Bouritsas et al. (2021) derived the compressed representation using learning barning-based objective.
K2ーTREE REPRESENTATION OF A GRAPH
In this section, introduce the 22-tree hierarchical and compact representation of graphs, as originally proposed for graph compression (Brisaboa al., 2009). In essence, the K is a K2-arry ordered tree that recursively partitions the adjacency matrix into K x K submatrices." 2 Its key idea is to summarize the submatrices filled only with zeros with single tree-node, exploiting the sparsity of the adjacency matrix. From now on, indicate the tree-node as node. The representation is hierarchical, as it associates each parent and child node pair with matrix and its corresponding submatrix, respectively, as described Figure 2.
To be specific, we consider the 22ettre representation (T, )') of an adjacency matrix A as K2-ary tree T= -V, E) associated with binary node attributes X' {xra u E V}. Every non-root node is uniquely indexed as (i. -tth child of its parent node for some i, E (1...., K). The tree T is ordered so that every (i, j)tth child node is ranked K (ii-1) 1) + among its siblings. Then the 2 satisfies the following conditions:
Each node is associated with submatrix (a) of the adjacency matrix A.
If the submatrix (a) for node u is filled only with zeros, Ta Otherwise, F..
A node u is leaf node if and only if x., = 0 or the matrix A1") is x matrix.
By default, we assume the number of nodes in the original graph be the power of K?
3

---

Published as a conference paper at ICLR 2024
Adj.
K² tree T
Kree
Prumed tret T
2
3
4
Rozt
Reck
1
0
0
0
4
0
0
Sequence
1 1
0
1 0
0
010
Figure 3: Illustration of the sequential representation for K2-tree. The shaded parts of the adjacency matrix A and the K2 'I denote redundant parts, which are further pruned, while the purple-colored parts of A and T denote non-redundant parts. Also, same-colored tree-nodes of pruned Keet are grouped and tokenized into the same colored parts of the sequence y.
Let B1, BR, K denote the K K partitioning of the matrix A(1) with i, correspond- ing to row- and column-wise order, respectively. The child nodes v1,1,..., UK,K of the tree-node u are associated with the submatrices .,, BK.K. respectively.
The generated K2-tree is a compact description of graph G as any node u with 2, and d, <, max, du where du is the distance from the root. summarizes large submatrix filled only with zeros. In the worst-case scenario, the size of the K2_tree is M M (N²/M) + O(1) (Brisaboa et al., 2009), where N and M denote the number of nodes and edges in the original graph, respectively. This constitutes a significant improvement over the N2 size of the full adjacency matrix.
Additionally, the K is hierarchical ensuring that (1) each tree node represents the connectivity between a specific set of nodes, and (2) nodes closer to the root correspond to a larger set of nodes. We emphasize that the nodes associated with submatrices overlapping with the diagonal of the original adjacency matrix indicate intra-connectivity within a group of nodes. In contrast, the remaining nodes describe the interconnectivity between two distinct sets of nodes.
We also describe the detailed algorithms for constructing a K2-ttre from a given graph G and recovering graph from the 32-tree in Appendices and B, respectively. It crucial to note that the ordering of the nodes in the adjacency matrix influences the K structure. Inspired by Diamant al. (2023), we adopt Cuckill-Mckee (C-M) ordering our ordering scheme. We empirically discover that C-M ordering (Cuthill & McKee, 1969) provides the most compact 2 Our explanation is that the C-M ordering is specifically designed to align the non-zero elements of matrix near its diagonal so that there is higher chance of encountering large submatrices filled only with zeros, which can be efficiently summarized the 122ttree representation.
HIERARCHICAL GRAPH GENERATION WITH K²-TREES
In this section, we present our novel method, hierarchical graph generation with 8² 2tress (HGGT), exploiting the hierarchical and compact structure of the 3-ttree representation of a graph. In detail, we transform the K2ettee into a highly compressed sequence through a process involving pruning and tokenization. Subsequently, we employ Transformer enhanced with tree-based positional encodings, for the autoregressive generation of this compressed sequence.
4.1 SEQUENTIAL K2-TREE REPRESENTATION
Here, we propose an algorithm to flatten the - into sequence, which is essential for the autoregressive generation of the tree. In particular, we aim to design a sequential representation that is even more compact than the K2 to minimize the number of decisions required for the generation of the Keer To this end, we propose (1) pruning K2_tree by removing redundant nodes, (2) flattening the pruned 2 into a sequence, and (3) applying tokenization based on the 2 structure. We provide an illustration of the overall process in Figure 3.
We provide the results in Section 5.3.
4

---

Published as a conference paper at ICLR 2024
Adj. A
-ree
Position
pos(u) = ((1,1), (1, 1))
(1,1)
Roet
(2,2)
(Pu, Iu) = 12
0
1
(1.1)
(1.1)
pos(c) ((2, (1,1),
(2 (1,2)
(po, 9.) = (5,
Figure 4: Illustration of the tree-node positions of -t-teee. The shaded parts of the adjacency matrix denote redundant parts, e.g., Pu < qu- Additionally, colored elements correspond to tree- nodes of the same color and the same-colored tree-edges signify the root-to-target downward path. Blue and red tuples denote the order in the first and second levels, respectively. The tree node is non-redundant as Pu > qu while v is redundant as p. < qu.
Pruning the -t-t To obtain the pruned K we identify and eliminate redundant nodes due the symmetry of the adjacency matrix for undirected graphs. In particular, without loss of generality, such nodes are associated with submatrices positioned above the diagonal since they mirror the counterparts located below the diagonal.
To this end, we now describe a formula to identify redundant nodes based on the position of submatrix A tied to specific node u at depth L, within the adjacency matrix A. Let vp, , UT. be a sequence of nodes representing a downward path from the root node r ey to the node vz. With Je,) denoting the order of ty among its K x K siblings, the node position can be represented )). Note that node
as pos(u) ((io) Jo, ..... . (vz.
depth L corresponds an element of kL KL partitions of the adjacency matrix A. The row and column indexes of the submatrix (
are derived as the (Pu: qu) = (E/=1 (i, - 1) + E K K'-'((jv - 1) + 1) as illustrated in Figure 4. As result, we eliminate any node associated with a submatrix above the diagonal. i.e., we remove node u when Pu. < 9n.
Consequently, the pruned K maintains only the nodes associated with submatrices devoid of redundant nodes, i..,, those containing elements of the adjacency matrix positioned at the diagonal or below the diagonal. Notably, following this pruning process, the -2-tree no longer adheres to the structure of a K x K-ary tree. Additionally, consider a non-leaf node u is associated with a submatrix (1)) that includes any diagonal elements of the adjacency matrix A. Then the node possess K(K 1)/2 child nodes after pruning K K(K 1)/2 child nodes associated with the redundant submatrices. Otherwise, the non-leaf node u remains associated with x K child nodes. Note that our framework can be extended to directed graphs by omitting the pruning process.
Flattening and tokenization of the pruned -teee Next, we explain how to obtain a sequential representation of the pruned K²-tree based on flattening and tokenization. Our idea is to flatten a - as a sequence of node attributes {x. u E V} using breadth-first traversal and then to tokenize the sequence by grouping the nodes that share the same parent node, i.c. sibling nodes.
For this purpose, we denote the sequence of nodes obtained from breadth-first traversal of non- root nodes in the 22-tree as .1...., -p and the corresponding sequence of node attributes as (II,,..,, ................................ - -1). It is important to note that sibling nodes sharing the same parent appear sequentially in the breadth-first traversal.
Next, by grouping the sibling nodes, we tokenize the sequence a. As result, we obtain a sequence (yI...., Wr) where each element is token representing a group of attributes associated with sibling nodes. For example, the t-th token corresponding a group of K2 sibling nodes is represented by y (.......... Fvx,x) where t........ UK.K share the same parent node u. Such tokenization allows representing the whole 2 using M (log (N /M) + O(1)) space, where N and M denote the number of nodes and edges in the original graph, respectively.
We highlight that the number of elements in each token y/: may vary due to the pruned K2_tree no longer being a K x K-ary tree, as mentioned above. With this in consideration, we generate a vocabulary of k² + +2/) potential configurations for each token yt. This vocabulary size is small in practice since we set the value K to be small, e.g., setting K induces the size of 24.
5

---

Published as a conference paper at ICLR 2024
CaHNN
Graph G
Featured A
Featured A tret T
2
Root
C
0
0
C
Sequence
111 COC 00 N
Figure 5: An example of featured K2-tree representation. The shaded parts of the adjacency matrix and K denote the redundant parts. The black-colored tree-nodes denote the normal tree-nodes with binary attributes while other-colored feature elements in the adjacency matrix A denote the same-colored featured tree-nodes and sequence elements. The node features (i.e., C and N) and edge feature (i.e., single bond -) of the molecule represented within the leaf nodes.
In particular, we remark that token with (KK + 1)/2 elements carries different semantics from another token with K2 elements. The former corresponds matrix's 's diagonal, thus indicating connectivity within set of nodes. In contrast, the latter relates to submatrix illustrating connectivity between pairs of node sets. This supports our decision to assign distinct values to token with K(K + 1)/2 elements and another with K elements, even when the tokens might represent the same combination of node features the unprumed tree.
submatrix situated on the adjacency
Generating featured graphs. We also extend our HGGT to graphs with node and edge- features, e.g., molecular graphs. At a high level, we apply our algorithm to the featured adjacency matrix, where each diagonal element corresponds corresponds to an edge feature. node attributes leaf nodes - correspond to node and edge features, while attributes of non-leaf nodes are the same with the non-attributed -2etrees (i.e., ones and zeros), See Figure 5 for an illustration and Appendix C for a complete description.
node feature and each non-diagonal element
4.2 GENERATING K²-TREE WITH TRANSFORMER K²-TREE POSITIONAL ENCODING
We describe our algorithm to generate the sequence of K representation y (y). yr). We utilize the masked Transformer (Vaswani et al., 2017) to make predictions on pe (3/ 91-1.... V1). To improve the model's understanding of the tree structure, we devise positional encoding. We also offer an algorithm to construct the 22et from the sequence generated by the Transformer.
Transformer with K2-tree positional encoding. We first introduce the Transformer architecture to parameterize the distribution Po (ys It-1...., 5/1 for autorgressive generation. Briefly, the model is trained with self-attention, and during inference, it generates the sequence one token time, relying on the previously generated sequence. To account for tree structural information, we incorporate tree-positional encodings for each time-step
During training, we mask the attention layer to ensure that predictions at each step are not influ- enced by future tokens of the sequence. The objective function maximum likelihood, denoted by max log p(y), y), where p = p (1 probability of predicting the next token correctly based on the preceding tokens.
This objective aims to maximize the
For inference, we begin the process with begin-of-sequene offseueence (BOS) token as the input to our trained Transformer decoder. The model then computes the distribution potential tokens for the next step, denoted by P(y (()))))=1-)) and the next token is sampled from this distribution. This token is appended to the input sequence, and the extended sequence is fed back into the model to generate the subsequent token. This iterative procedure is terminated when predefined maximum length is reached or an end-of-sequence (EOS) token emerges.
To enhance the input yr, we incorporate the positional encoding for As outlined in Section 4.1, the node attributes in 3/2 are associated with child nodes a particular node u. Therefore, the encoding is based the downward path from the root node do to the node UL, represented as (Vp.... ).) In this context, the order of e amongst its siblings in the non-pruned K -tee is denoted as tuple (Fe Jo.). Subsequently, further update the input feature y/ with positional

---

Published as a conference paper at ICLR 2024
Table I: Generic graph generation performance. The baseline results are from prior works (Jo et al., 2022; Liao et al., 2019; Martinkus et al., 2022; Luo et al., 2022) public codes (marked by *). For each metric, the best number highlighted in bold and the second-best number is underlined.
Community-smme -mall
Planar
Enzymes
Grid
12 S VV
s 20
[V]
64
10 &
[V] s
125
100 & [V] S 400
Method
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Deg.
Clus.
Orb.
Dog.
Clus.
Orb.
VAa
0.350
0,980
0.540
1.369
0.629
0.191
1.619
0,000
0.919
GraphRNN
0,080
0.120
0,040
0.005
0.278
1,254
0.017
0.062
0.046
0.064
0.043
0.021
GNF
0.200
0,200
0.110
GRAN
0.005
0.142
0.090
0.001
0.043
0.001
0.023
0.031
0.169
0.001
0.004
0.002
EDP-GNN
0.053
0.144
0.026
0,023
0,268
0.082
0.455
0.238
0.328
GraphGen
0.075
0.065
0.014
1.762
1.423
1.640
0.146
0.079
0.054
1,550
0.017
0.860
GraphAF
0.180
0.200
0.020
1.669
1.283
0.266
GraphDF
0.060
0.120
0.030
1.503
1,283
0.266
SPECTRE
0.010
0.067
0.010
GDSS
0.045
0.086
0.007
0.250
0.393
0.587
0.026
0.061
0.009
0.111
0.005
0.070
DiGress
0.012
0.025
0.002
0.000
0.002
0.008
0.011
0.039
0.010
0.016
0.000
0.004
GDSM
0.011
0.015
0.001
0.013
0.088
0.010
0.002
0.000
HGGT (ours)
0.001
0.006
0.003
0.000
0.001
0.000
0.005
0.017
0.000
0.000
0.000
0.000
(a) Train
(b) GraphGen
(c) GDSS
(d) DiGress
(e) HGGT (ours)
Figure Generated samples for Community-small (top), and Grid (bottom) datasets.
encoding, which represented as PE(u) = Σt= dee where e denotes the embedding function that converts the order tuple into vector representations and ((tu).ee)).... (ee.: is the sequence of orders downward path from 7" to u.
Constructing -trreee from the sequential representation. We next explain the algorithm to recover a K from its sequential representation y. In particular, we generate the K2 K2_tree simul- taneously with the sequence incorporate the tree information for each step of the autoregressive generation. The algorithm begins with an empty tree containing only a root node and iteratively expands each "frontier" node based the sequence of the decisions made by the generative model. To facilitate a breadth-first expansion approach, the algorithm utilizes a first-in-frrtt-out (FIFO) queue, which contains node candidates be expanded.
To be specific, our algorithm initializes K2-tree T = ((r}, 0) with the root node r associated with the node attribute x, algorithm expands the node u popped from the queue Q using the token ye. To be specific, for each node attribute æ in yt, our algorithm adds a child node v with I, æ. v = 1 and the size of A(e) is larger than x the child node v is inserted into the queue Q. This algorithm is designed to retrieve the pruned tree, which allows the computation of positional data derived from the information.
It also initializes the FIFO queue Q with r. Then each t-th step, our
EXPERIMENT
5.1 GENERIC GRAPH GENERATION
Experimental setup. We first validate the general graph generation performance of our HGGT on four popular graph benchmarks: (1) Community-small, 100 community graphs, (2) Planar, 200
7

---

Published as a conference paper at ICLR 2024
Table Molecular graph generation performance. The baseline results are from prior works (Jo et al., 2022; Luo et al., 2022) or obtained by running the open-source codes (denoted by *). The best results are highlighted in bold and the second best results are underlined.
QM9
ZINC250K
Method
Val. 1
NSPDK
FCD
Uniq.
Nov.
Val.
NSPDK 4
FCD 1
Uniq. 7
Nov. 1
EDP-GNN
47.52
0.005
2.68
99.25
86.58
82.97
0.049
16.74
99.79
100
MoFlow
91.36
0.017
4.47
98.65
94.72
63,11
0.046
20.93
99.99
100
GraphAF
74.43
0.020
5.27
88.64
86
68.47
0.044
16.02
98.64 64
100
GraphDF
93.88
0.064
10.93
98.58
98.54
90.61
0.177
33.55
99.63
100
GraphEBM
0.030
6.14
97.90
97.01
5.29
0.212
35.47
98.79 08.79
100
GDSS
95.72
0.003
2.9
98.46
86.27
97.01
0.019
14.66
99.64
100
DiGress*
99.01
0.001
0.25
96.34
35.46
100
0.042
16.54
99.97
100
GDSM
99,90
0.003
2.65
92.70
0.017
12.96
HGGT (ours)
99.22
0.000
0.40
95.65
24.01
92.87
0.001
1,93
99.97
99.83
planar graphs, (3) Enzymes (Schomburg et al., 2004), 587 protein tertiary structure graphs, and (4) Grid, 100 2D grid graphs. Following baselines, we adopt maximum mean discrepancy (MMD) to compare three graph property distributions between generated graphs and test graphs: degree (Deg.), clustering coefficient (Clus.), and 4-node-orbit counts (Orb.). We conduct all the experiments using single RTX 3090 GPU. The detailed descriptions of our experimental setup are in Appendix D.
Baselines. We compare our HGGT with twelve graph generative models: Graph VAE (Simonovsky & Komodakis, 2018) 30, GraphRNN (You al., 2018), GNF Liu et al. (2019), GRAN (Liao et al., 2019), EDP-GNN (Niu et al., 2020), GraphGen (Goyal et al., 2020), GraphAF (Shi et al., 2020), GraphDF (Luo al., 2021), SPECTRE (Martinkus al., 2022), GDSS (Jo al., 2022), DiGress (Vignac et al., 2022), and GDSM (Luo et al., 2022). A detailed implementation description is in Appendix E.
Results. Table shows the experimental results. We observe that HGGT outperforms all baselines on all datasets. Note that our model consistently outperforms all baselines regardless of the graph sizes, indicating better generalization performance across various environments. In particular, we observe how the performance of HGGT is extraordinary for Grid, We hypothesize that HGGT better captures the hierarchical structure and repetitive local connectivity of the grid graphs than the other baselines. We also provide visualizations of the generated graphs in Figure
5.2 MOLECULAR GRAPH GENERATION
Experimental setup. To test the ability of HGGT on featured graphs, we further conduct an evaluation of molecule generation tasks. We use two molecular datasets: QM9 (Ramakrishnan et al., 2014) and ZINC250k (Irwin et al., 2012). Following the previous work (Jo et al., 2022), we evaluate 10,000 generated molecules using five metrics: (a) validity (Val.), (b) neighborhood subgraph pairwise distance kernel (NSPDK), (c) Frechet ChemNet Distance (FCD). (d) uniqueness (Uniq.), and (c) novelty (Nov.). Note that NSPDK and FCD measured between the generated samples and the test set. The validity, uniqueness, and novelty metrics are measured within the generated samples.
Baselines. We compare HGGT with eight deep graph generative models: EDP-GNN (Niu et al., 2020), MoFlow (Zang & Wang, 2020), GraphAF (Shi et al., 2020), GraphDF (Luo et al., 2021). GraphEBM (Liu al., 2021), GDSS (Jo al., 2022), DiGress (Vignac et al., 2022), and GDSM(Luo et al., 2022). We provide a detailed implementation description in Appendix E.
Results. The experimental results are reported Table 2. We observe that HGGT showed competitive results on all the baselines on most of the metrics. The results suggest that the model can generate chemically valid features, i.e., atom types, accordingly, along with the structure of the graphs. In particular, for the ZINC250K dataset, we observe a large gap between our method and the baselines NSPDK and FCD scores while showing competitive performance in the other metrics. Since FCD and NSPDK measure the similarity between molecular features and subgraph structures, respectively, HGGT can generate similar features and subgraphs observed in the real molecules.
5.3 ABLATION STUDIES
Time complexity. We conduct experiments to measure the inference time the proposed algorithm. The results are presented in the upper left table of Figure 7, where we report the time to generate
8

---

Published as a conference paper at ICLR 2024
Time (sec)
Comm.
Planar
Enzymes
Grid
Tree PE
GRAN
3.51
5.40
3.99
14.68
Absolute PE Relalive PE
GDSS
0.54
8.85
1.09
25.90
DiGress
0.34
3.29
1.29
45,41
HGGT (ours)
0.03
0.58
0.09
8.16
Training
Method
Comm.
Planar
Enzymes
Grid
BFS 0.534
0.201
0,432
0,048
DFS 0.619
0.204
0.523
0.064
C-M
0.508
0.195
0.404
0.045
Epochs
Figure 7: (Upper left) Inference time to generate a single graph. (Lower left) Average compres- sion ratio on various node orderings. (Right) Training loss on different positional encodings.
Table 3: Ablation study for algorithmic components of HGGT.
Community-smal
Planar
Enzymes
Group
TPE
Prune
Degree
Cluster.
Orbit
Degree
Cluster.
Orbit
Degree
Cluster.
Orbit
x
0.072
0.199
0.080
0.346
1.824
1,403
0.050
0.060
0.021
x
0.009
0.105
0.001
0.003
0.001
0.002
0.005
0,022
0.007
0.002
0.028
0.001
0.003
0.001
0.002
0.002
0.020
0.002
0.001
0.006
0.003
0.000
0.001
0.000
0.005
0.017
0.000
a single sample. We can observe that HGGT generates a graph faster than the others due to the simplified representation.
Adjacency matrix orderings. is clear that the choice of node ordering influences the size of K2-tree. We validate choice of Cuthill-McKee (C-M) ordering (Cuthill & McKee, 1969) by comparing its compression ratio to other node orderings: breadth-first search (BFS) and depth-first search (DFS). The compression ratio is defined as the number of elements in K2 divided by N In the left below table of Figure 7, we present the compression ratios for each node ordering. One can observe that C-M ordering shows the best ratio in all the datasets compared others.
Positional encoding. In this experiment, we assess the impact of various positional encodings in our method. We compare our tree positional encoding (TPE) absolute positional encoding (APE) (Vaswani et al., 2017) and relative positional encoding (RPE) (Shaw et al., 2018 8) on the Planar dataset. Our findings, as presented the right figure of Figure 7, demonstrate that TPE outperforms other positional encodings with faster convergence of training loss. These observations highlight the importance of appropriate positional encoding for generating high-quality graphs.
Ablation of algorithmic components. We introduce three components to enhance the performance of HGGT: grouping into tokens (Group), incorporating tree positional encoding (TPE), and pruning the K (Prune). To verify the effectiveness of each component, present the experimental results for our method with incremental inclusion of these components. The experimental results are reported in Table 3. The results demonstrate the importance of each component in improving graph generation performance, with grouping being particularly crucial, thereby validating the significance of our additional components the sequential K22ttre representation.
CONCLUSION
In this paper, we presented novel 22- -tree-based graph generative model (HGGT) which enables compact, hierarchical, and domain-agnostic generation. Our experimental evaluation demonstrated state-of-the-art performance across various graph datasets. An interesting avenue for future work is the broader examination of other graph representations to graph generation, e.g., plethora of representations (Boldi et al., 2009; Larsson & Moffat, 2000).

---

Published as a conference paper at ICLR 2024
Reproducibility All experimental code related to this paper is available at https:: / thub. yun.ujunuujjnn///aa /GGT. Detailed insights regarding the experiments, encompassing dataset and model specifies, are available in Section 5. For intricate details like hyperparameter search, consult Appendix D. In addition, the reproduced dataset for each baseline is in Appendix E.
Acknowledgements This work partly tions Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) Artificial Intelligence Graduate School Program (POSTECH)), the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2022R AARRIAGAIAN A6AIA0305295413 202IRICIC101 1375), and the Technology Innovation Program (No. 20014926, Development of BIT Convergent AI Architecture, Its Validation and Candidate Selection for COVID19 Antibody, Repositioning and Novel Synthetic Chemical Therapeutics) funded by the Ministry of Trans, Industry & Energy (MOTIE, Korea).
supported by Institute of Information & communica-
(No. -ITP-2019-0-013
(No. 0022ICIIC101322
REFERENCES
Sungsoo Ahn, Binghong Chen, Tianzhe Wang, and Le Song. Spanning tree-based graph generation for molecules. In International Conference Learning Representations, 2022. URL https:
//appneeeiiew... wtwe:///ooommiidommeeee 8T2m. 1.3
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47 2002.
Reet Barik, Marco Minutoli, Mahantesh Halappanavar, Nathan R Tallent, and Ananth Kalyanaraman. Vertex reordering for real-world graphs and applications: An empirical evaluation. In 2020 IEEE International Symposium on Workload Characterization (I/SWC), pp. 240-251. IEEE, 2020. 23
Maciej Besta and Torsten Hoefler. Survey and taxonomy of lossless graph compression and space- efficient graph representations. arXiv preprint /rXiv:/806.0179) 2018. 3
Paolo Boldi, Massimo Santini, and Sebastiano Vigna. Permuting web and social graphs. Internet
Mathematics, 6(3):257-283, 2009. 9
Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, and Michael Bronstein. Partition and code: learning how to compress graphs. Advances in Neural Information Processing Systems, 34: 18603-18619, 2021.
Nieves R Brisaboa, Susana Ladra, and Gonzalo Navarro. k2-trees for compact web graph representa- tion. In SPIRE, volume 9, pp. 18-30. Springer, 2009. 4,
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and begree-guides graph generation via discrete diffusion modeling. arXiv preprint (xXiv:2305.04111, 2023. 2
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, 9
Nathaniel Lee Diamant, Alex M 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. 4, 18
Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sei, 5(1):17-60, 1960.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: a scalable approach to domain- agnostic labeled graph generation. Proceedings of The Web Conference 2020, pp. 1253-1263, 2020. 1, 8, 18
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference machine learning, pp. 2444. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2024
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012. 2,
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-2332.
PMLR, 2018. 1,3
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International conference on machine learning, pp. 4839-4844 4848. PMLR, 2020. 1,
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference Machine Learning, pp. 10362-10383. PMLR, 2022. 2, 7, 8, 17,
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang. B. Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation, 2023. URL attpps//openreeieew
net/forum? i (-e--9884888------ 8HZXxd5. 2
Mario Krenn, Florian Häse, A Nigam, Pascal Friederich, and Alán Aspuru-Guzik, SELFIES: a robust representation of semantically constrained graphs with an example application in chemistry. arXiv preprint arXiv:/905.0 13744, 2019.
N Jesper Larsson and Alistair Moffat. Off-line dictionary-bast based compression. Proceedings of the IEEE, 88( 18(11):1722-1732, 2000. 9
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:/803.0333 03324, 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019. 8, 18. 23
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. Advances in Neural Information Processing Systems, 32, 2019. 8, 18
Meng Liu, Keqiang Yan, Bora Oztekin, and Shuiwang Ji. Graphebm: Molecular graph generation with mesgy-bassed models. arXiv preprint arXiv:2102.005:2 2021. 1, 8, 18
Tianze Luo, Zhanfeng Mo, and Sinno Jialin Pan. Fast graph generative model via spectral diffusion.
arXiv preprint arXiv:221.008822 2022. 8, 17, 18
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. 2, 8, 18
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe, Graphnvp: An invertible flow model for generating molecular graphs. arXiv preprint 190. 2019.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spec- tral conditioning helps to overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning, pp. 15159-15179. PMLR, 2022. 7, 18
Lukasz Maziarka, Agnieszka Pocha, Jan Kaczmarezyk, Krzysztof Rataj, Tomasz Danel, and Michal Warchol. Mol-cyclegan: a generative model for molecular optimization. Journal of Cheminformat- ics, 18,1):1-18, 2020. 1
Chris Mueller. Sparse matrix reordering algorithms for cluster identification. Machune Learning in Bioinformatics, 2004. 23
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permu- tation invariant graph generation via score- score-based generative modeling. International Conference Artificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020. 8, 18
11

---

Published as a conference paper at ICLR 2024
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-peeffomancc deep learning library. Advances in neural information processing systems, 32, 2019. 18
Sriram Raghavan and Hector Garcia-Molina. Representing web graphs. In Proceedings 19th International Conference on Data Engineering (Cat. No. 03CH37405), pp. 405-416. IEEE, 2003.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014. 2, 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. 2, 8
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): 220-131, 2018. 3
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. arXiv preprint arXiv: 1803 00055, 2018. 9
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: a flow-hased autoregressive model for molecular graph generation. arXiv preprint a79:922001.09382, 2020. 2, 8, 18
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning-CCANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pp. 412-422. Springer, 2018. 1, 8, 18
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. 2, 6, 9, 18
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 147344 2022. 1, 2, 8, 18
Soojung Yang, Doyeong Hwang, Seul Lee, Seongok Ryu, and Sung Ju Hwang. Hit and lead discovery with explorative rl and fragment-base based molecule generation. Advances in Neural Information Processing Systems, 34:7924-7953 2021. 3
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018. 23
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. 2, 8, 18, 23
Hao Yu, Xu Sun, Wei Deng Solvang, and Xu Zhao. Reverse logistics network design for effective management of medical waste in epidemic outbreaks: Insights from the coronavirus disease 2019 (covid-19 19) outbreak in wuhan (china). International journal of environmental research and public health, 1775) 2020.
Chengxi Zang and Fei Wang. Mollow: 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, 18
12

---

Published as a conference paper at ICLR 2024
A CONSTRUCTION OF A K²-TREE FROM THE GRAPH
Algorithm 2 -tee construction
Input:Ajjacency matrix and partitioning factor K.
1: Initialize the tree T (V,E) with V = 0, E V.
K tree.
2: Initialize an empty queue Q.
Candidates to be expanded into child nodes. 3: Set V +- V (r). Iy t and let A < A. Insert r into the queue Q. Add root node r.
4: while Q # do
5: Pop u from Q.
6: if Tr 0 then
Condition for expanding the node
7: Go to line 4.
8:
end if
9:
Update +- dimn A (/)
for i 1.... K do
Row-wise indices.
11:
for j = 1........ K do
> Column-wise indices.
1)8 is, (j 1)s jjs Set Bi, < ((w) ((i
Operation to obtain s submatrix Big of A(w),
13:
If BiG is filled with zeros, set Z. f 1. Otherwise, set x, f- 0.
b Update tree-node attribute.
14:
If dim((e.)) > 1, update Q f- Usg-
15:
end for end for
16:
17:
Set V + VU "UU UKKK.. UK.K) Set & E {uu, (I. UK,))
b Update tree nodes.
Update tree edges.
19:
end while
Output: K2_ (T,X) where fr u V}.
In this section, we explain our algorithm to construct ? (T,X) X)) from given graph G = A where a symmetric non-featured graph and A is an adjacency matrix. Note that he K²-ary tree VJ. In addition, let dim (A) to
T (V, E) is associated with binary node attributes X' = {a,, denote the number rows(or columns) n of the square matrix E {0, 1) We describe the full procedure in Algorithm 1. Note that the time complexity of the procedure is O(N2) (Brisaboa et al., 2009), where denotes the number nodes in the graph G.
13

---

Published as a conference paper at ICLR 2024
B CONSTRUCTING A GRAPH FROM THE K²-TREE
Algorithm 2 Graph G construction
Input: K2_ -tttree (T,2) and partitioning factor K.
Set + KPr
Full adjacency matrix size.
Initialize A E {0, m with zeros.
for u do
For each leaf node with Ja 1. > Position of node
pos(u) =
( Jec)).
(Pur (u) = (E KL (i- + +,,1, Kh
- +1)+1)
Location of node
Set Ap..qu. f- end for Output: Adjacency matrix A.
We next describe the algorithm generate graph G A given the K²-tree (T, with tree depth Dr. Let L C V be the set of leaf nodes in K with node at- tributes Note that represent the tree-node position of (e.,.Je)) )...., Jer)) based on a downward path Vi...., UL from the root node r = % to the tree-node u = VL. In addition, the location of corresponding submatrix A(") is denoted as gn) (Et Ki- 1, Et_ KL-((jn, 1) 1) in described in Section 4.1. describe the full procedure as Algorithm 2. Note that the time complexity of the procedure O(N3), where N denotes the number of nodes in the graph G, since it requires querying for each element the adjacency matrix.
as pos(u)
14

---

Published as a conference paper at ICLR 2024
C GENERALIZING -²-TREE TO ATTRIBUTED GRAPHS
Algorithm 3 Featured R construction
Input: Modified adjacency matrix A and partitioning factor K.
Featured tret Candidates to be expanded into child nodes. 3: Set V <- VU (r). < and let A <- A. Insert into the queue Q. Add root node r.
1: Initialize the tree T (V, with V = 0, 0.
2: Initialize an empty queue Q
4: while Q + 0 do
5: Pop from Q
6: if T.. 0 then
Condition for expanding the node
7:
Go to line 4.
8:
end if
9:
Update +- dim A(4)/K
for 1, ..... K do
Row-wise indices. > Column-wise indices.
11:
for j = 1, K do
12:
Set Big + A [(i - 1)s is, (j - 1)s js].
Operation to obtain s X s submatrix B.,, of A((), Update tree-node attribute.
13:
if Big is filled with zeros then
14:
Set Tip <- O.
15:
else if B > then
Non-leaf tree-nodes with attribute 1.
16:
Set Fv t 1.
else
Leaf tree-nodes with node features and edge features. b We treat x 1 matrix Bt,j as scalar.
18:
Set t Bı.--
end if
20:
if dim BBj) then Q < Vig-
end if
22:
end for end for
23:
24:
Set V + VU (11.1..... J. UK.K)
Update tree nodes. Update tree edges.
25:
Set + EU 01.1). (u, kK
26:
end while
Output: Featured Keet (T,X) where X' = (Ix E VJ.
Algorithm 4 Featured graph G construction
1: Input: Featured K (T, X') and partitioning factor K.
2: m < KP
Full adjacency matrix size.
3: Initialize A {0, 1m with zeros.
4: for u L do
> For each Ieaf node with x. & 0. Position of node
5: pos(u)=
Juy); (vez:Jre))
6: (Pu. = (Et= KL-L (ive - 1) + +1, +1 KL-e(jo, 1) 1 Location of node u.
7: Set Aprigo <-
8: end for
9: Output: Modified adjacency matrix A.
In this section, we describe a detailed process to construct a -ree for featured graphs with node features and edge features (e.g., molecular graphs), which is described briefly in Section 4. We modify the original adjacency matrix by incorporating categorical features into each element, thereby enabling the derivation of the featured K 2tee from the modified adjacency matrix.
Edge features. Integrating edge features into the adjacency matrix is straightforward. It can be accomplished by simply replacing the ones with the appropriate categorical edge features.
Node features. Integrating node features into the adjacency matrix is more complex than that of edge features since the adjacency matrix only describes the connectivity between node pairs. To address this issue, assume that all graph nodes possess self-loops, which leads to filling ones to the diagonal elements. Then we replace ones on the diagonal with categorical node features that correspond to the respective node positions.
15

---

Published as a conference paper at ICLR 2024
Let Du E A' be the non-binary tree-node attributes that include node features and edge features and C be the set of leaf nodes in -rettee with non-zero node attributes. Then we can construct a featured K2-tree with modified adjacency matrix and construct graph G from the featured -tee as described in Algorithm 3 and Algorithm 4, respectively.
16

---

Published as a conference paper at ICLR 2024
D EXPERIMENTAL DETAILS
In this section, we provide the details of the experiments. Note that we chose in all experiments and provide additional experimental results for in Appendix G.
D.1 GENERIC GRAPH GENERATION
Table 4: Hyperparameters of HGGT generic graph generation.
Hyperparameler
Community-small
Planar
Enzymes
Grid
Dim. of feed-forward network
512
512
512
512
Transformer dropout rate
0.1
0
0.1
0.1
Transformer
# of attention hcads
8
8
# layers
3
Batch size
128
32
32
8
# epochs
500
500
Dim. token embedding
512
Train
Gradient clipping norm Input dropout rate
0
Learning rate
1 x 10-3
10-3
2 10 5 10
We used the same split with GDSS (Jo et al., 2022) for Community-small, Enzymes, and Grid datasets. Otherwise, we used the same split with SPECTRE (Luo et al., 2022) for the Planar dataset. We fix k = 2 and perform the hyperparameter search to choose the best learning rate in {0.0001, 0.0002, 0.0005, 0.001} and the best dropout rate in {0, 0.13. We select the model with the best MMD with the lowest average of three graph statistics: degree, clustering coefficient, and orbit count. Finally, we provide the hyperparameters used in the experiment in Table
D.2 MOLECULAR GRAPH GENERATION
Table 5: Statstics of molecular datasets: QM9 and ZINC250k.
Dataset
#l of graphs
of nodes
# of node types
# of edge types
QM9
133,885
V
3
ZINC250K
249,455
S
V
38
9
3
Table 6: Hyperparameters of HGGT in molecular graph generation.
Hyperparameter
QM9
ZINC250k
Dim. of feedforward network
512
512
Transformer dropout rate
0.1
0.1
Transformer
of attention heads layers
8
2
Batch size
1024
256
epochs
500
Dim. of token emhedding
$12
Train
Gradient clipping nurm
1
Input dropout rate
0.5
Leurning rate
5 x 10
5 10
The statistics of training molecular graphs (i.e., QM9 and ZINC250K datasets) are summarized in Table 5 and used the same split with GDSS (Jo al., 2022) for fair evaluation. We fix k: 2 and perform the hyperparameter search to choose the best number of layers in (2. 3} and select the model with the best validity. In addition, we provide the hyperparameters used in the experiment in Table
17

---

Published as a conference paper at ICLR 2024
E IMPLEMENTATION DETAILS
E COMPUTING RESOURCES
We used PyTorch (Paszke et al., 2019) implement HGGT and train the Transformer (Vaswani et al., 2017) models on single GeForce RTX 3090 GPU.
E.2 MODEL ARCHITECTURE
We describe the architecture the proposed trans- former generator of HGGT in Figure 8. The generator takes sequential representation of K2-ttee as input and generates the output probability of each token as described in Section 4.2. The model consists of a token embedding layer, transformer encoder(s), and multilayer perceptron layer with tree positional en- coding.
Outpul profsshilitiiss 0.01 0.34 0.05 0.08
Muhilayer perceptron
Transformer decoder
pusitional encuding
Token embolding
E.3 DETAILS FOR BASELINE IMPLEMENTATION
Generic graph generation. The baseline results from prior works are as follows. Results for Graph- VAE (Simonovsky & Komodakis, 2018), GraphRNN (You et al., 2018), GNF (Liu et al., 2019), EDP- GNN (Niu al., 2020), GraphAF (Shi et al., 2020). GraphDF (Luo et al., 2021), and GDSS (Jo et al., 2022) are obtained from GDSS, while the results for GRAN (Liao et al., 2019), SPECTRE (Martinkus et al., 2022), and GDSM (Luo al., 2022) derived from their respective paper. Additionally, we reproduced DiGress (Vignac et al., 2022) and GraphGen (Goyal et al., 2020) using their open-source codes. We used original hyperparameters when the original work provided them. DiGress takes more than three days for the Planar, Enzymes, and Grid datasets, so we report the results from fewer epochs after convergence.
Sequence y
010 1001 1
Figure 8: The architecture of HGGT.
Molecular graph generation. The baseline results from prior works are as follows. The results for EDP-GNN (Niu et al., 2020), MoFlow (Zang & Wang, 2020), GraphAF (Shi al., 2020), GraphDF (Luo al., 2021), GraphEBM (Liu et al., 2021), and GDSS (Jo et al., 2022) are from GDSS, and the GDSM (Luo et al., 2022) result is extracted from the corresponding paper. Moreover, we reproduced DiGress (Vignac et al., 2022) using their open-source codes.
E.4 DETAILS FOR THE IMPLEMENTATION
We adapted node ordering code from (Diamant et al., 2023), evaluation scheme from (Jo et al., 2022; Martinkus al., 2022), and NSPDK computation from (Goyal et al., 2020).
18

---

Published as a conference paper at ICLR 2024
F GENERATED SAMPLES
In this section, we provide the visualizations of the generated graphs for generic and molecular graph generation.
F.1 GENERIC GRAPH GENERATION
Community-small
(a) Train
(b) GraphGen
(c) GDSS
(d) DiGress
(e) Ours (HGGT)
Figure 9: Visualization of the graphs from the Community dataset and the generated graphs.
Planar
(a) Train
(b) GraphGinn
EHITE sodd
exilt
EASTE codE
mell
(d) DiGress
(c) Ours (HGGT)
Figure 10: Visualization the graphs from the Planar dataset and the generated graphs.
We present visualizations of graphs from the training dataset and generated samples from GraphGen, DiGress, GDSS, and HGGT in Figure 9, Figure 10, Figure 11, and Figure 12. Note that reproduced GraphGen and DiGress using open-source codes while utilizing the provided checkpoints for GDSS. However, given that the checkpoints provided for GDSS do not include the Planar dataset, have omitted GDSS samples for this dataset. We additionally give the number of nodes and edges each graph.
19

---

Published as a conference paper at ICLR 2024
Enzymes
B-SA 9-27
(-36-1
Eara
(a) Train
(b) GraphGen
(c) GDSS
(d) DiGress
(c) Ours (HGGT)
Figure 11: Visualization of the graphs from the enzymes dataset and the generated graphs.
Grid
BUSUL BO20
SHALL FIZIS
FOR FOX
BISE BOSE
CHRIL 9425
GHEDE FIZS
(a) Train
(b) GraphGen
(c) GDSS
Fill
(d) DiGress
(e) Ours (HGGT)
Figure 12: Visualization of the graphs from the Grid dataset and the generated graphs.
20

---

Published as a conference paper at ICLR 2024
F.2 MOLECULAR GRAPH GENERATION
Figure 13: Visualization of the molecules generated from the QM9 dataset.
tyo wo ous quob dseor Xeyd
XRo whr0 moowO rand plob wDe agpinoo .omp
suato
Figure 14: Visualization of the molecules generated from the ZINC250k dataset.
We present visualizations of generated molecules from HGGT in Figure 13 and Figure 14. Note that the 24 molecules are non-cherry-pice and randomly sampled.
21

---

Published as a conference paper at ICLR 2024
G ADDITIONAL EXPERIMENTAL RESULTS
In this section, we report additional experimental results.
Figure 15: Generation results of HGGT with &: = 3.
Community-small
Planar
Degree
Cluster.
Orbit
Degree
Cluster:
Orbit
0.001
0.006
0.003
0.000
0.001
0.000
0.007
0.050
0.001
0.001
0.003
0.000
G.1 GENERIC GRAPH GENERATION
We provide generic graph generation results for = 3. Increasing decreases the sequence length, while vocabulary size increases to 20² + 26 578.
We used Community-small and Planar datasets and measured MMD between the test graphs and generated graphs. We perform the same hyperparameter search for a fair evaluation as k = 2. The results are in Figure 15. We can observe that HGGT still outperforms the baselines even with different k.
G.2 MOLECULAR GRAPH GENERATION
Table Additional molecular graph generation performance.
QM9
Method
Frag. f
Intdiv. f
QED
SA +
SNN
Scaf. f
Weight |
DiGress
0.9737
0.9189
0.0015
0.0189
0.5216
0.9063
0.1746
HGGT (Ours)
0.9874
0.9150
0.0012
0.0304
0.5156
0.9368
0.2430
ZINC250K
Method
Frag. f
Intdiv.
QED
SA 4
SNN 1
Scaf.
Weight
DiGress
0.7702
0.9061
0.1284
1.9290
0.2491
0.0001
62.9923
HGGT (Ours)
0.9877
0.8644
0.0164
0.2407
0.4383
0.5298
1.8592
additionally report seven metrics of the generated molecules: (a) fragment similarity (Frag.), which measures the BRICS fragment frequency similarity between generated molecules and test molecules, (b) internal diversity (Intdiv.), which measures the chemical diversity in generated molecules, (c) quantitative estimation of drug-likeness (QED), which measures the drug-likeness similarity between generated molecules and test molecules, (d) synthetic accessibility score (SA), which compares the synthetic accessibility between generated molecules and test molecules, (e) similarity the nearest neighbor (SNN), an average of Tanimoto similarity between the fingerprint of generated molecule and molecule, (f) scaffold similarity (Scaf.), the Bemis-Murcko scaffold frequency similarity between generated molecules and test molecules, and (g) weight, the atom weight similarity between generated molecules and test molecules. The results are in Table 7.
22

---

Published as a conference paper at ICLR 2024
H DISCUSSION
H.1 HIERARCHY OF -2-TREE REPRESENTATION
K²-tree representation is hierarchical as it forms parent-child hierarchy between nodes. In detail, each node in - corresponds a block (i.e.. submatrix) in the adjacency matrix. Given child and its parent node, the child node block is submatrix of the parent block node, which enables K²-tree represent hierarchical structure between the blocks. While this hierarchy may differ from the exact hierarchical community structure, the K²-tree representation still represents valid hierarchy present in the adjacency matrix. We also note that our K²2tree representation should not be confused with the hierarchical representation learned by graph neural networks with pooling functions (Ying al., 2018).
Nevertheless, bandwidth minimization algorithms (including C-M node ordering) often induce node orderings that align with underlying clusters. Prior works (Barik et al., 2020; Mueller, 2004) have empirically figured out that bandwidth minimization tends to cluster the points along the diagonal, which leads to a partial capture of the underlying community structure. This also supports our statement that K22 -2ettre tree representation is hierarchical.
H.2 COMPARISON WITH PRIOR WORKS AUTOREGRESSIVE GRAPH GENERATIVE MODEL
In this section, we compare HGGT to two prior works autoregressive graph generative models: GraphRNN You al., 2018) and GRAN (Liao al., 2019). The main difference comes from the key idea of HGGT: the ability to capture recurring patterns and the hierarchy of the adjacency matrix. In detail, HGGT maps the recurring patterns the dataset (large zero-filled block matrices) into simple object (a vero-valued node in the R that the model can easily generate. This mapping allows the generative model to focus on learning instance-specific details rather than the generation of the whole pattern that is common across the dataset. In addition, -tee representation can represent a valid hierarchy present in the adjacency matrix, as described in Appendix H.1
BFS ordering (GraphRNN)
Without BFS ordering
Figure 16: Reduced representation size of GraphRNN.
Comparison to GraphRNN. Both HGGT and GraphRNN reduce the representation size, which removes the burden of the graph generative models learning long-range dependencies. In detail, HGGT reduces the representation size by leveraging K 2 pruning, and tokenization. Otherwise, GraphRNN employs BFS node ordering constraining the upper-corner elements of the adjacency matrix to be consecutively zero as described in Figure 16.
Comm.
Planar
Enzymes
Grid
Full matrix
241.3
4096.0
1301.6
50356.
GraphRNN
75.2
2007.3
234.7
4106.3
HGGT (ours)
30.3
211.7
67.3
419.1
Table 8: Representation size of GraphRNN and HGGT
23

---

Published as a conference paper at ICLR 2024
Dataset
Rep. size
N2
Comm. 48
400
Enzymes
238
15625
Planar
230
4696
Grid
706
130321
The reduction of HGGT is higher as shown in Table 8 that reports the average size of the representation empirically. Note that the representation size of HGGT and GraphRNN indicates the number of tokens and the number of elements limited by the maximum size of the BFS queue, respectively. While the comparison is not fair due to different vocabulary sizes, one could expect HGGT to suffer less from the long-range dependency problem due to the shorter representation.
Comparison to GRAN. The main difference between HGGT and GRAN comes from the different generated representations. HGGT generates K representation with large zero-filled blocks, which is further summarized into a single node in the R while GRAN generates the conventional adjacency matrix. Notably, the block of nodes of GRAN is solely used for parallel decoding, which is conceptually irrelevant to the graph representation.
In addition, the concept of block and the decoding process of the blocks differ in both methods. On one hand, the square-shaped HGGT block defines connectivity between a pair of equally-sized node sets. HGGT sequentially specifies these block matrix elements in hierarchical way. i.e., first specifying whether the whole block matrix is filled with zeros and then specifying its smaller submatrices. On the other hand, the rectangular-shaped GRAN block defines connectivity between set of newly added nodes and the existing nodes. GRAN can optionally decode the block matrix elements in parallel, speeding up the decoding process at the cost lower performance.
24


Reviews:
[{"review_id": "CJ5QXoo1aR", "reviewer": "Reviewer_Nzff", "summary": "The paper proposes a novel algorithm to generate graphs based upon $K^2$-tree representation. One of the positive sides of $K^2$-tree representation lays in the fact that it ensures the compactness of the obtained representation without losing the hierarchical information from the nodes and edges in the original graph. After having described how $K^2$-tree representation works, the authors outline the generation algorithm built upon it. Specifically, the algorithm prunes redundant nodes from the representation (e.g., given its symmetrical nature); the, it flattens and tokenizes the pruned $K^2$-tree; finally, it exploits a Transformer architecture to generate the new graph through positional encoding. Results on various graph learning tasks and domains against other state-of-the-art graph generation solutions outline the efficacy of the proposed approach. The evaluation is complemented through an extensive ablation study which further validates the goodness of the algorithm.", "questions": "* Could it be possible to adopt the proposed graph generation algorithm to create graphs with specific topological properties (e.g., node degree or clustering coefficient)?\n\n**After the rebuttal.** The rebuttal answered all questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ The paper is well-written and easy-to-follow.\n+ The proposed algorithm is simple but effective.\n+ The proposed algorithm is also able to generate featured graphs (e.g., molecular structures which come with features on graph edges).\n+ The experimental analysis is extensive and supports the efficacy of the proposed solution.\n+ The code is released at review time.", "weaknesses": "- To the best of my knowledge, I cannot see any specific weakness.", "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": "u4TTrh9jWw", "reviewer": "Reviewer_JeGt", "summary": "In this paper, the authors propose a new graph generative model Hierarchical Graph Generation with $K^2$–Tree (HGGT). $K^2$-tree is a lossless graph representation and the authors compress it by pruning, flattening and tokenizing operations such that it fits to Transformer with $K^2$-tree positional encoding for graph generation. The effectiveness and efficiency of HGGT are evaluated on six datasets.", "questions": "(1) Why is the performance of HGGT on molecular datasets not so good as that on the generic graph datasets? It seems that HGGT achieves the worst score on three metrics of the two molecular benchmarks (Uniqueness on QM9 and Novelty on both).\n\n(1) What are the time complexities of Algorithms 1-4 and HGGT?\n\n(2) Is the $K^2$-representation still lossless after pruning, flattening and tokenization? I guess yes, but is there a simple proof for this?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The approach of combining $K^2$-tree compressed representation with Transformer is new.\n\n(2) The performance of HGGT is superior to the SOTA baselines on most datasets.", "weaknesses": "(1) The performance of HGGT (Table 2) is not so satisfactory for molecular graph generation which is probably the most important application of this graph generative model.\n\n(2) It lacks the worst case time complexity analysis for the algorithms.", "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": "JldT93F1Sm", "reviewer": "Reviewer_K9N3", "summary": "This paper presents a new graph generative model which capitalizes on the $K^2-$tree representation, a  representation of graphs that is more compact than the adjacency matrix. The $K^2-$tree representation is transformed into a sequence and then a Transformer-based architecture is employed which predicts one token at a time based on the previously generated sequence. The Transformer is also equipped with positional encodings that take into account the structure of the tree. The proposed model is trained on synthetic and real-world datasets. The results indicate that in most cases, the generated graphs better preserve graph properties than the baselines.", "questions": "In p.5, why $K^2$ elements are not enough and $K(K + 1)/2$ more elements are added, thus increasing the vocabulary size for each token?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The proposed model shows strong empirical performance over previous baselines on both synthetic and real-world datasets. Thus, HGGT could be a useful addition to the list of graph generative models.\n\n- The $K^2-$tree representation seems interesting and the proposed model has some novelty. Even though there are previous works that have proposed autoregressive models for graph generation, in my view the main components of HGGT are different from those of previous works.\n\n- The model supports node and edge features, while the results reported in Figure 7 suggest that HGGT is much more efficient than competing models.", "weaknesses": "- The paper claims that the employed representation is hierarchical, however, I do not fully agree with this claim. In case a hierarchical community structure is present in the graph, a hierarchical representation is supposed to capture this community structure. However, the proposed $K^2-$tree representation would not necessarily capture this (since it depends on the node ordering). On the other hand, the hierarchical clustering algorithm would produce a proper hierarchical representation. I thus think that this claim needs rephrasing to avoid misunderstanding.\n\n- The proposed model is conceptually similar to GRAN [1] which sequentially generates blocks of nodes and associated edges. A detailed discussion of how HGGT differs from GRAN is missing from the paper.\n\n- One of my main concerns with this work is that it is not clearly explained in the paper why the proposed model significantly outperforms the baselines. This is not the first autoregressive model for graph generation, and previous models also came up with different schemes to reduce the time and space complexity (such as BFS ordering and generation of blocks of the adjacency matrix in [2] and [1], respectively). Thus, I would not expect such a significant difference in performance between HGGT and those previous models. I would like the authors to comment on this.\n\n- In Table 2, we can observe that the novelty of the generated molecules is low compared to those of the baselines (mainly on QM9). I would expect the authors to provide some explanation or intuitions about why the proposed model fails to produce novel graphs.\n\n- In section 5.2, it is mentioned that \"Each metric is measured between the 10,000 generated samples and the test set\". I do not think that this is actually true. If I am not wrong the validity and the uniqueness have nothing to do with the samples of the test set. Furthermore, the Frechet ChemNet Distance and the novelty are commonly computed by comparing the generated samples against those of the training set and not those of the test set.\n\n[1] Liao, R., Li, Y., Song, Y., Wang, S., Hamilton, W. L., Duvenaud, D., Urtasun, R., & Zemel, R. \"Efficient graph generation with graph recurrent attention networks\". In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 4255-4265, 2019.\\\n[2] You, J., Ying, R., Ren, X., Hamilton, W., & Leskovec, J. \"Graphrnn: Generating realistic graphs with deep auto-regressive models\". Proceedings of the 35th International Conference on Machine Learning, pp. 5708-5717, 2018.", "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": "zEGhSuvsp0", "reviewer": "Reviewer_XLS2", "summary": "The paper focuses on generating graphs from a target distribution, which is a vital task in several areas like drug discovery and social network analysis. The paper introduces a new framework termed as \"Hierarchical Graph Generation with K^2−Tree\" (HGGT). This model (1) uses a K^2−Tree representation, which was originally designed for lossless graph compression, enabling a compact graph representation while also capturing the hierarchical structure of the graph. (2) Incorporates pruning, flattening, and tokenization processes in the K^2−Tree representation. (3) Introduces a Transformer-based architecture, optimized for generating sequences by using a specialized tree positional encoding scheme.", "questions": "See weakness, I'd like to raise my score if concern is addressed", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper's emphasis on hierarchically capturing graph structures using K^2−Tree is technically sound. Hierarchies are crucial for many real-world graphs, and K^2−Tree, with its inherent structure, naturally offers this advantage.\n\n2. The introduction of pruning, flattening, and tokenization processes aims to achieve a compact representation. This can lead to both storage and computational efficiencies, which are pivotal when dealing with large-scale graph data.", "weaknesses": "1. I have doubts about the motivation, which is not strong enough to drive the development of such work. \n\n2. Related work missing, such as [1, 2]\n\n3. The paper doesn't detail the computational resources required, which raises concerns about its practicality for very large graphs.\n\n4. Tokenization can sometimes lead to loss of information, and without details, it's uncertain how this impacts the overall graph representation.\n\n[1] Kong, Lingkai, et al. \"Autoregressive Diffusion Model for Graph Generation.\" (2023).\n\n[2] Chen, Xiaohui, et al. \"Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling.\" (2023)", "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)