HiGen: Hierarchical Graph Generative Networks
Authors: Mahdi Karami
Venue: ICLR 2024 poster (2024)
Keywords: Generative Models
Graph Generative Network
Graph Neural Network
Probabilistic Model
Primary area: generative models
TL;DR: We propose a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures in a coarse-to-fine fashion.

Abstract: Most real-world graphs exhibit a hierarchical structure, which is often overlooked by existing graph generation methods. To address this limitation, we propose a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures in a coarse-to-fine fashion. At each level of hierarchy, this model generates communities in parallel, followed by the prediction of cross-edges between communities using separate neural networks. This modular approach enables scalable graph generation for large and complex graphs.  Moreover, we model the output distribution of edges in the hierarchical graph with a multinomial distribution and derive a recursive factorization for this distribution. This enables us to generate  community graphs with integer-valued edge weights in an autoregressive manner. Empirical studies demonstrate the effectiveness and scalability of our proposed generative model, achieving state-of-the-art performance in terms of graph quality across various benchmark datasets. 
Code available at https://github.com/Karami-m/HiGen_main.

Published as a conference paper at ICLR 2024
HIGEN: HIERARCHICAL GRAPH GENERATIVE NET- WORKS
Mahdi Karami
mahdi Bondi.karana
ABSTRACT
Most real-world graphs exhibit hierarchical structure, which is often overlooked by existing graph generation methods. To address this limitation, we propose a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures level of hierarchy, this model generates communities in parallel, followed by the prediction of cross-edges between communities using separate neural networks. This modular approach enables scalable graph generation for large and complex graphs. Moreover, we model the output distribution of edges in the hierarchical graph with multinomial distribution and derive recursive factorization for this distribution. This enables us to generate community graphs with integer-valued edge weights in an autoregressive manner. Empirical studies demonstrate the effectiveness and scalability of our proposed generative model, achieving state-of- the-art performance in terms of graph quality across various benchmark datasets. Code available at https: /ttt:::/github. com/ Karami m/ HiGen. main
coarse-to-fin fashion. each
INTRODUCTION
Graphs play a funddaenntll role in representing relationships and are widely applicable in various domains. The task of generating graphs from data holds immense value for diverse applications but also poses significant challenges (Dai et al. (2220). Some of the applications include: the exploration of novel molecular and chemical structures (Jin al. 2020), document generation (Blei et al.) 22003).
circuit design (Mirhoseini et al. 2021), the analysis and synthesis of realistic data networks, as well
as the synthesis of scene graphs computer (Manolis Savva et al. 2019 Ramakrishnan et 2021)
In all the aforementioned domains, a common observation is the presence of locally heterogeneous edge distributions in the graph representing the system, leading to the formation of clusters or communities and hierarchical structures. These clusters represent groups of nodes characterized by a high density edges within the group and a comparatively lower density of edges connecting the group with the rest of the graph. In hierarchical structure that arise from graph clustering, the communities in the lower levels capture the local structures and relationships within the graph. These communities provide insights into the fine-grained interactions among nodes. On the other hand, the higher levels of the hierarchy reflect the broader interactions between communities and characterize global properties of the graph. Therefore, in order generate realistic graphs, is essential for graph generation models to learn this multi-scale structure, and be able to capture the cross-level relations. While hierarchical multi-resolution generative models were developed for specific data types such as voice (Oord et al.) 2016), image (Reed et al. 2017: Karami et al. 2019) and molecular motifs (Jin al. 2020p. these methods rely on domain speciffi priors that are not applicable to general graphs with unordered nature. To the best of our knowledge, there exists no data-driven generative models specifically designed for generic graphs that can effectively incorporate hierarchical structure.
Graph generative models have been extensively studied in the literature. Classical methods based on random graph theory, such as those proposed in [rdos & Rényi (1960) and Barabási & Albert (1999). can only capture limited set of hand-engineered graph statisties. Leskovec al. (2010) leveraged the Kronecker product matrices but the resulting generative model is very limited in modeling the underlying graph distributions. With recent advances in graph neural networks, variety of
deep neural network models have been introduced that are based on variational autoencoders (VAE)
(Kingma & Welling 2013) generative adversarial networks (GAN) (Goodfellow al. 2020).

---

Published as a conference paper at ICLR 2024
Some examples of such models include (De Cao & Kipf 2018: Simonovsky & Komodakis 2018
Kipf & Welling 2016; Ma et al. 2018 Liu et al. 2019; Bojchevski et al. 2018 Yang et al. 2019
The major challenge in VAE based models is that they rely on heuristics to solve graph matching problem for aligning the VAE'S input and sampled output, limiting them to small graphs. On the other hand, GAN-based methods circumvent the need for graph matching by using permutation invariant discriminator. However, they can still suffer from convergence issues and have difficulty capturing complex dependencies in graph structures for moderate to large graphs (Li et al. 2018 Martinkus et al. 2022). To address these limitations, (Martinkus et al. 2022) recently proposed using spectral conditioning to enhance the expressivity of GAN models in capturing global graph properties.
On the other hand, autoregressive models approach graph generation as sequential decision Decision-making process. Following this paradigm. [Li et al. (2018) proposed a generative model based on GNN but it has high complexity of ((m²)) ). In a distinct approach, GraphRNN (You et al. 2018) modeled graph generation with a two-stage RNN architecture for generating new nodes and their links, respectively.
However, traversing all elements of the adjacency matrix in predefined order results in O (n²) time complexity making it non-scalable to large graphs. In contrast, GRAN (Liao et al. 2019)
employs graph attention network and generates the adjacency matrix row by row, resulting in (n) complexity sequential generation process. To improve the scalability of generative models, Dai al. (2220) proposed an algorithm for sparse graphs that decreases the training complexity to O(log n,, but at the expense of increasing the generation time complexity to O((n + m) log n). Despite their improvement in capturing complex statistics of the graphs, autoregressive models highly rely on an appropriate node ordering and do not take into account the community structures of the graphs. Additionally, due to their recursive nature, they are not fully parallelizable.
A new family of diffusion model for graphs has emerged recently. Continuous denoising diffusion was developed by Jo et al. (2022), which adds Gaussian noise to the graph adjacency matrix and node features during the diffusion process. However, since continuous noise destroys the sparsity and structural properties of the graph, discrete denoising diffusion models have been developed as a solution in (Haefeli et al.] [022 Vignac et al. 2022, Kong et al. 2023). These models progressively edit graphs by adding or removing edges in the diffusion process, and then denoising graph neural networks are trained to reverse the diffuusin process. While the denoising diffusion models can offer promising results, their main drawback is the requirement of a long chain of reverse diffusion, which can result in relatively slow sampling. To address this limitation, Chen et al. (2023) introduced diffusion- based graph generative model. In this model, a discrete diftusion process randomly removes edges while a denoising model is trained to inverse this process, therefore it only focuses on a portion of nodes in the graph at each denoising step.
In this work, we introduce HiGen, Hierarchical Graph Generative Network address the limitations of existing generative models by incorporating community structures and cross-level interactions. This approach involves generating graphs in a coarse-to-fine manner, where graph generation at each level is conditioned on a higher level (lower resolution) graph. The generation of communities at lower levels performed in parallel, followed by the prediction of cross-edges between communities using separate graph neural network. This parallelized approach enables high scalability. To capture hierarchical relations, our model allows each node at given level to depend not only on its neighbouring nodes but also on its corresponding super-node at the higher level. We address the generation of integer-valuee valued edge weights of the hicrarchical structure by modeling the output distribution of edges using multinomial distribution. We show that multinomial distribution can be factorized successively, enabling the autoregressive generation of each community. This property makes the proposed architecture well-suited for generating graphs with integer-valued edge weights. Furthermore, by breaking down the graph generation process into the generation of multiple small partitions that are conditionally independent of each other, HiGen reduces its sensitivity to predefined initial ordering of nodes.
2 BACKGROUND
A graph g = (V, E) is a collection of nodes (vertices) V and edges E with corresponding sizes = | and m = [l and an adjacency matrix A for the node ordering म. The node set can be partitioned into e communities (a.k.a. cluster or modules) using a graph partitioning function F: V {1, ... c). where each cluster of nodes forms sub-graph denoted by C, = (V(C2), E(C.))
2

---

Published as a conference paper at ICLR 2024
0
29
=
(a)
(b)
(c)
(d)
(c)
Figure 1: (a) A sample hicrarchical graph, HG with levels shown. Communitics are shown in different colors and weight of node and weight an edge in higher level, represent the sum corresponding community and bipartite, respectively. Node size and edge width indicate their weights. (b) The matrix shows corresponding adjacency matrix of the graph the leaf level, G², where each of its sub-graphs corresponds block in the adjacency matrix, communities correspond diagonal blocks and shown in different colors while bipartites are colored gray. (c) Decomposition of multinomial distribution as a recursive stick-breaking process where at each iteration, first a fraction of the remaining weights r, is allocated to the t-th row (corresponding to the f-th node in the sub-graph) and then this fraction, Ve, is distributed among that row of lower triangular adjacency matrix, Á. (d), (e) Parallel generation of communities and bipartites, respectively. Shadowed lines are the augmented edges representing candidate edges at each step.
edges in
with adjacency matrix A, The cross-links between neighboring communities form a bipartite graph, denoted by B, = (V(C,,, V(C,), E(B,))) with adjacency matrix Aij. Each community super-edge linking neighboring
aggregated to a super-node and each bipartite corresponds communities, which induces coarser graph at the higher (a.k.a. parent) level. Herein, the levels are indexed by superscripts. Formally, each community at level I, C/, is mapped to node at the higher level graph, also called its parent node, v/-1 == Pa(C)) and each bipartite level is represented by an edge in the higher level, also called its parent edge, e Pa(B',) = (ef -1 .u. 11 The weights of the self edges and the weights of the cross-edges in the parent level determined by the sum of the weights of the edges within their corresponding community and bipartite, respectively. Therefore, the edges in the induced graphs at the higher levels have integer-valued weights: w/, Eeesce))
and w = EEEE(B We, moreover sum of all edge weights remains constant in all levels so wo = E.ee(gr) w. (8, v [0.....].
This clustering process continues recursively in a bottom-up approach until single node graph go is obtained, producing a hierarchical graph, defined by the set of graphs in all levels of abstractions, HG : ( ..... -0-1.-- This forms dendrogram tree with GD being the root and g being the final graph that is generated at the leaf level. An HG is visualized in Figure Ta The hierarchical tree structure enables modeling of both local and long- range interactions among nodes, well as control over the flow of information between them, across multiple levels of abstraction. This is a key aspect of our proposed generative model. Please refer to appendix Aoror list of notation definitions.
3

---

Published as a conference paper at ICLR 2024
3 HIERARCHICAL GRAPH GENERATION
In graph generative networks, the objective to learn a generative model, p(g) given set of training graphs. This work aims to establish a hierarchical multi-resolution framework for generating graphs in a coarse-to-fine fashion. In this framework, we assume that the graphs do not have node attributes, so the generative model only needs characterize the graph topology. Given a particular node ordering т, and a hierarchical graph HG := {[g", ..... g 1 g produced by recursively applying graph partitioning function, F, we can factorize the generative model using the chain rule of probability as:
p(g gh, x²) = pllgp p ,.., , σ) = p(g
(....))., p(g", a 9o) p(g")
I p(g t (1 x x p(9)) 1=0
(1)
In other words, the generative process involves specifying the probability of the graph at each level conditioned its parent level graph in the hierarchy. This process is iterated recursively until the leaf level is reached. Here, the distribution the root p(g") = p( w = wo) can be simply estimated using the empirical distribution of the number of edges, Wn [E], of graphs in the training set.
Based on the partitioned structure within each level HG, the conditional generative probability p(G' g can be decomposed into the probability of its communities and bipartite graphs as:
p(g' 1 p((c) Vi V(G U (B V(i.j) E(G'-1)3 g'-1)
II PCC 19
II
p(Bl gg (Cheete)))
6 V(gi-1)
(1.f)E E(gi-1)
This decomposition is based on the assumption that, given the parent graph G' generative proba- bilities of communities, C₁2 are mutually independent. Subsequent to the generation of community graphs, it further assumes that the generation probability of each bipartite can be modeled independent of the other bipartites. [ The following theorem leverages the properties of multinomial distribution to prove the conditional independence of the components for the integer-value weighted hierarchical graph (r.t. appendix B.I for the proof).
Theorem 3.1. Let the random vector : [wel E E(g') denote the set of weights of all edges of G' such that their sum is we 1 The joint probability of can be described by multinomial distribution: w ~ Mu(w Wo, 0¹). By observing that the sum of edge weights within each community C² and bipartite graph Bi, are determined by the weights of their parent edges in the higher level, waa and w--1 respectively, we can establish that these components are conditionally independent and each of them follow a multinomial distribution:
p(g )'
II
Mu([wele e ot
w// 1.'))''))
II
Mu([wele e Bi, | 0,1)) (3)
V(G'--)))
((J) E(Si-1)
where (0 E [0, s.t. 1 (I.5) E E(g--1)) are the multinomial model's parameters.
Therefore, given the parent graph at a higher level, the generation of graph at its subsequent level can be reduced to generation of its partition and bipartite sub-graphs. As illustrated in figure I this decomposition enables parallel generation of the communities in each level which is followed by predicting bipartite sub-graphs in that level. Each of these sub-graphs corresponds to block in the adjacency matrix, as visualized in figure 2a so the proposed hierarchical model generates adjacency matrix in blocks-wise fashion and constructs the final graph topology.
3.1 COMMUNITY GENERATION
Based on the equation 3 the edge weights within each community can be jointly modeled using a multinomial distribution. In this work, our objective is to specify the generative probability of
Indeed, this assumption implies that the cross dependency between communities are primarily encoded by their parent abstract graph which is reasonable where the nodes' dependencies are mostly local and are within community rather than being global.
4

---

Published as a conference paper at ICLR 2024
communities in level 1, p(C g( an autoregressive process, hence, we need to factorize the joint multinomial distribution of edges as a sequence of conditional distributions. Toward this goal, show in appendix: [B.2 that this multinomial distribution can be decomposed into sequence of binomial distribution of each edge using a stick-breaking process. This result enables us to model the community generation as an edge-by-edse autoregressive process with ((Ve ()) generation steps, similar to existing algorithms such as GraphRNN (You et al. 2018 or DeepGMG (Li et al. 2018).
However, inspired by GRAN (Liao al. 2019). community can be generated more efficiently by generating one node at time, reducing the sampling process to ((Vcl) steps. This requires decomposing the generative probability between the f-th node, the new node at the t-th step, and the already generated graph are grouped together. In other words, this model completes the lower triangle adjacency matrix one row a time conditioned on the already generated sub- and the parent-level graph. The following theorem formally derives this decomposition for multinomial distributions.
edges in a group-wise form, where the candidate edges
Theorem 3.2. For random counting vecfor E Z with multinomial distribution Mu(w w. O).
let's 's split it into T disjoint groups w = [I. ..., ur) where u, E ZZ >i= E, E, and also split the probability vector accordingly as 0 = (0,, .... Orl. Additionally, let's define sum all variables in the t-th group (t-th step) by a random count variable V; := Eei, Ut.e- Then, the multinomial distribution can be factorized chain of binomial and multinomial distributions:
T
Mu(w = [u1, ur w. 0 = =101..., 0rl) = II
Bi(ve IT, m.) Mu(u, Ve, Ad)
(4)
(=1
1 O, Ve, Tre 1- Eier 1 0,' ict
X 0.
where: I1
1
Here, It denotes the remaining weight at t-th step, and the probability of binomial, The is the fraction of the remaining probability mass that is allocated to Vt, i.c. the sum of all weights the t-th group. The vector parameter X is the normalized multinomial probabilities of all count variables in the t-th group. Intuitively, this decomposition of multinomial distribution can be viewed as a recursive stick-breet sick-breaking process where at each step t: first binomial distribution is used to determine how much probability mass to allocate to the current group, and a multinomial distribution is used to distribute that probability mass among the variables in the group. The resulting distribution is equivalent to the original multinomial distribution. Proof: Refer to appendix B.3
Let Ch,, denote an already generated sub-graph at the 1-th step, augmented with the set of candidate edges from the new node, v,()), to its preceding nodes, denoted by (((C),)) = {t.,t) i < f}. We collect the weights of the candidate edges in the random vector u, = [wele E (,(d),) (that
corresponds to the (-th row of the lower triangle of adjacency matrix A!) where the sum of the candidate edge weights is V, remaining edges' weight is r, = -// Eist and total edges' weight of community C is w/y-" Based on theorem 3.2 the probability of u, can be characterized by the product of binomial and a multinomial distribution. So. we need to model the parameters of the these distributions. This process is illustrated figure [b] and figure appendix. We further increase the expressiveness of the generative network by extending this probability to mixture model with K mixtures:
K p(u))
Σ
B Bi(ve re, n.. Mu(u: I Ves XLxe
(5)
1=
1 softmax
(MLP'
Aheadd pool(hegg) 11 hpppcpts))))))))()) []
(6)
TAA sigmoid (MLP', [pool(ha) 11 ((braact)) 1)) [k]
B softmax (MLP's [pool(he ((pp(p)))))))))))))))))
Where Ahg.de. a (8,(Ct,)) de dimensional matrix, consisting of the set of candidate edge embeddings (Aheee) == h ha IV (I, E &((CC()) heg is a l x da matrix of node embeddings
5

---

Published as a conference paper at ICLR 2024
of Ci learned by GNN model: heg. GNN com (Ci,)) Here, the graph level representation is obtained by the addpool() aggregation function and the mixture weights are denoted by B'. In order to produce K x [E]( dimensional matrix of multinomial probabilities, the 0LP network acts the edge level, while MLP (.P () and MLP O act the graph level to produce the binomial probabilities and K dimensional arrays for K mixture models, respectively. All of these MLP networks are built by two hidden layers with ReL.()) activation functions.
In the generative model of each community C₁ the embedding of its parent node, ppc(C)) is used as the context, and is concatenated to the node and edge embeddings at level 1. The operation [a v] concatenates vector y to each row of matrix æ. Since parent level reflects global structure of the graph, concatenating its features enriches the node and edge embeddings by capturing long-range interactions and global structure of the graph, which is important for generating local components.
3.2 BIPARTITE GENERATION
Once all the communities in level are generated, the edges of all bipartite graphs at that level can be predicted simultancously. An augmented graph G' composed of all the communities, {C} Vi e V(G'-1)}, and the candidate edges of all bipartites, {Bi V(i,j) E E(G'-1)). Node and edge embeddings are encoded by G, (g'). We similarly extend the multinomial distribution of bipartite, in using mixture model to express its generative probability:
p(w == E(B(,)) = Ml w 0'p.))
0 i.A: = softmax (MLP'(( (AnS(et)))) |l AhpacBt))) [t
(7)
B = softmax (MLP's 3 (pooll (pool(Ahe(st)) Al Alha((s)))
where the random vector [we]. E(B²,) is the set of weights of all candidate edges in bipartite Byy and Ahpa(B)) are the parent edge embeddings of the bipartite graph. By parametrizing the distribution of bipartite graphs based on both the generated communities and the parent graph, HiGen can effectively capture the interdependence between bipartites and communities.
Node Feature Encoding: To encode node embeddings, we extend GraphGPS proposed by Ram pášek et al. (2022). GraphGPS combines local message-passing with global attention mechanism and uses positional and structural encoding for nodes and edges to construct a more expressive and a scalable graph transformer (GT) (Dwivedi & Bresson 2020). We employ GraphGPS as the GNN of the parent graph, G (g'-1). However, apply GraphGPS on augmented graphs of bipartites, GNN! by (. we use distinct initial edge features to distinguish augmented (candidate) edges from real edges. Furthermore, for bipartite generation, the attention scores in the Transformers of the augmented graph J¹ are masked to restrict attention only to connected communities. Moreover, for the community generation, we employ the GNN with attentive messages model, proposed in (Liao ct al. 2019), as GNN The details of model architecture are provided in appendix C.I
RELATED WORK
In order to deal with hierarchical structures in molecular graphs, a generative process was proposed by Jin et al.] (2020) which recursively selects motifs, the basic building blocks, from a set and predicts their attachment to the emerging molecule. However, this method requires prior domain- specific knowledge and relies on molecule-specific graph motifs. Additionally, the graphs are only abstracted into two levels, and component generation cannot be performed in parallel. In (Kuznetsov) & Polykovskiy 2021). hierarchical normalizing flow model for molecular graphs was introduced, where new molecules are generated from a single node by recursively dividing each node into two. However, the merging and splitting of pairs of nodes in this model is based on the node's 's neighborhood without accounting for the diverse community structure of graphs, hence the graph generation of this model is inherently limited, SShizad et al. (2022) proposed graph generation framework based

---

Published as a conference paper at ICLR 2024
on tree decomposition that reduces upper bound on the maximum number of sampling decisions. However, this model is limited to a single level of abstraction with tree structure and requires (nk) generation steps where & represents the width of the tree decomposition, hence its scalability is limited to medium-sized graphs. In contrast, HiGen's ability to employ different generation models for community and inter-community subgraphs at multiple levels of abstraction key advantage that enhances its expressiveness.
5 EXPERIMENTS
In our empirical studies, compare the proposed hierarchical graph generative network against state-of-the ahrt autoregressive models: GRAN and GraphRNN models, diffusion models: DiGress (Vignac et al., 2022), GDSS CJ al. 2022). GraphARM (Kong et al. 2023) and EDGE (Chen et al.
2023). and a GAN-based model: SPECTRE (Martinkus et al. 2022, on range of synthetics and real datasets of various sizes.
Datasets: We used 5 different benchmark graph datasets: (1) the synthetic Stochastic Block Model (SBM) dataset consisting of 200 graphs with 2-5 communities each with 20-40 nodes (Martinkus et al. 2022); (2) the Protein including 918 protein graphs, each has 100 to 500 nodes representing amino acids that are linked if they are closer than Angstroms (Dobson & Doig, 2003), (3) the Enzyme that has 587 protein graphs of 10-125 nodes, representing protein tertiary structures of the enzymes from the BRENDA database (Schomburg et al., (2004) and (4) the Ego dataset containing 757 3-hop ego networks with 50-300 nodes extracted from the CiteSeer dataset (Sen et al. 2008). (5)
Point Cloud dataset, which consists of 41 3D point clouds of household objects. The dataset consists of large graphs with up to 5k nodes and approximately 1. 1.4k nodes on average (Neumann et al. 2013).
Graph Partitioning Different algorithms approach the problem of graph partitioning (clustering) using various clustering quality functions. Two commonly used families of such metrics are modu- larity and cut- out-based metrics (Tsissulin et al., 2020). Although optimizing modularity metric is an NP-hard problem, it is well-studies in the literature and several graph partitioning algorithm based on this metric have been proposed. For example, the Louvain algorithm (Blondel et al., 2008) starts with each node its community and then repeatedly merges communities based the highest increase in modularity until no further improvement can be made. This heuristic algorithm is computationally efficient and scalable to large graphs for community detection. Moreover, a spectral relaxation of modularity metrics has been proposed in Newman (2006a b) which results in an analytical solution for graph partitioning. Additionally, an unsupervised GNN-based pooling method inspired by this spectral relaxation was proposed for partitioning graphs with node attributes (T (itsuuln et al. (020)) As the modularity metric is based on the graph structure, it is well-suited for our problem. Therefore, we employed the Louvain algorithm to get hierarchical clustering of the graph nodes in the datasets and then spliced out the intermediate levels to achieve HGs with uniform depth of L = 2.
Model Architecture In our experiments, the GNN models consist of 8 layers of GraphGPS layers. and the input node features are augmented with positional and structural encoding. This encoding includes the first 8 eigenvectors related to the smallest non-zero eigenvalues of the Laplacian and the diagonal of the random- walk matrix up to 8 steps. Each hierarchical level employs its own GNN and output models. For more architectural details, please refer to Appendix C.I and D
We conducted experiments using the proposed hicrarchical graph generative network (HiGen) model with two variants for the output distribution of the leaf edges: 1) HiGen: the probability of the community edges' weights at the leaf level are modeled by mixture of Bernoulli, using sigmoid() activation in (6), since the leaf levels in experiments have binary edges weights. 2)-iGen-m: the model uses a mixture of multinomial distributions (5) to describe the output distribution for all levels. In this case, we observed that modeling the probability parameters of edge weights at the leaf level, denoted by A in 6 by a multi-hot activation function, defined as a()); :=
sigmoid(s.)/ sigmaid(2z)) where R - (K 11)-implex, provided slightly better performance than the standard softmax() function. However, for both HiGen and HiGen-m, the probabilities of the integer-valuee edges at the higher levels are still modeled by the standard softmaxx) function ?
2 As the leaf levels have binary edge weights while the sum of their weights is determined by their parent edge, possible extension this work could he using the cardinality potential model (Hajimirsaeeghi al.
7

---

Published as a conference paper at ICLR 2024
Table I: Comparison of generation metrics on benchmark datasets. The baseline results for SBM and Protein graphs are obtained from (Martinkus et al. 2022 Vignac al. 2022). the results for enzyme graphs are ohtained from (Kong et al. 2023). and the scores for Ego from (Chen al. 2023). For Ego report GNN- performance metries: GNN RBF and Frechet Distance (FD) besides tructure-based statisties. For the smaller the better. Best results are indicated in bold and the second best methods are underlined. "-" not applicable due to resource issuc or not reported in the reference papers. On the right side, the samples from HiGen are depicted where the communities are distinguished with different colors at 2 levels.
scores,
Stochastic block model
Protein
Model
Deg.
Clus.
Orbit
Spec.
Deg.
Clus.
Orbit
Spec.
GraphRNN
0.0055
0,0584
0.0785
0.0065
0.0040
0.1475
0.5851
0.0152
GRAN
0.0113
0,0553
0.0540
0,0054
0,0479
0.1234
0.3458
0,0125
SPECTRE
0.0015
0.0521
0.0412
0,0056
0.0056
0.0843
0.0267
0.0052
DiGress
0.0013
0.0498
0.0433
HiGen-m
0.0017
0.0503
0.0604
0.0068
0.0041
0.109
0.0472
0.0061
HiGen
0.0019
0.0498
0.0352
0.0046
0.0012
0.0435
0.0234
0.0025
SBM
Protein
Engyme
Ego
Model
Deg.
Clus.
Orbit
Model
Deg.
Clus.
Orbit
GNN RBF
FD
GraphRNN
0.017
0.062
0.046
GraphRNN
0.0768
1,1456
0.1087
0.6827
90.57
GRAN
0,054
0,987
0.033
GRAN
0.5778
0.3360
0.0406
0.2633
489.96
GDSS
0.026
0.061
0.009
GDSS
0.8199
0.6012
0.3315
SPECTRE
0.136
0.125
DiscDDPM
0,4613
0.1681
0.0633
DiGress
0.004
0.083
0.002
DiGress
0.0708
0.0092
0.1205
0.0489
18.68
GraphARM
0.029
0.054
0.015
EDGE
0.0579
0.1773
0.0519
0.0658
15:76
HiGen-m
0.027
0.157
1,2e.3
HiGen-m
0.114
0.0378
0.0535
0,0420
12.2
Enzyme
Ego
HiGen
0.012
0.038
7.2c-4
HiGon
0.0472
0.0031
1,0137
0.0454
5.24
Metrics To evaluate the graph generative models, we compare the distributions of four different
graph structure- statistics between the ground truth and generated graphs: (1) degree distri- butions, (2) clustering coefficient distributions, (3) the number of occurrences of all orbits with four nodes, and (4) the spectra of the graphs by computing the eigenvalues of the normalized graph Laplacian. The first three metrics capture local graph statistics, while the spectra represents global structure. The maximum mean discrepancy (MMD) score over these statistics are used as the metrics. While Liu et al. (2019) computed MMD scores using the computationally expensive Gaussian earth mover's 's distance (EMD) kernel, [iao et al. (2019) proposed using the total variation (TV) distance as an alternative measure. TV distance is much faster and still consistent with the Gaussian EMD kernel. Recently, O'Bray et al. 2022 suggested using other efficient kernels such as an RBF kernel, or Laplacian kernel, or a linear kernel. Moreover, Thompson et al. (022) proposed new evaluation metrics for comparing graph sets using random GNN approach where GNNs are employed to extract meaningful graph features. However, in this work, we follow the experimental setup and evaluation metrics of (Liao et al., 2019), except for the enzyme dataset where we use Gaussian EMD kernel to be consistent with the results reported in [Jo et al. 2022). GNN-based performance metrics of HiGen model are also reported in appendix
The performance metrics of the proposed HiGen models are reported in Table together with gener- ated graph samples of HiGen. The results demonstrate that HiGen effectively captures graph statisties and achieves state-of-te offte-of-thh-arr ahtt on all the benchmarks graphs across various generation metrics. This improvement in both local and global properties of the generated graphs highlights the effectiveness of the hierarchical graph generation approach, which models communities and cross-community interactions separately. A comparison of sampling times for the model can be found in Appendix (D2 Additionally, Appendix (F visual comparisons of generated graphs by the HiGen models and an experimental evaluation of various node ordering and partitioning functions.
For point cloud dataset, the augmented graph of bipartites, 3', contains very large number of candidate edges, leading to out-of-memory during training. To overcome this challenge, we adopted a sub-graph sampling strategy, allowing us to generate one or subset of bipar- tites at a time to ensure memory constraints were met. In our experiments, we sequenced the generation of bipartites based on the index of their parent edges in the parent graph.
2015). which is derived to model the distribution over the set of binary random variables, to model the edge weight at the leaf level.
8

---

Published as a conference paper at ICLR 2024
In this context, when generating the edges of Bly, the aug- mented graph encompassed all preceding communities (C2, Vk S max(i, bipartites (B'ry V(z, y) S (i.j) and the candidate edges of B We trained different mod- els for hierarchical depth of L 2 and L 3. The results of this approach, referred to as HiGen-s, in Table highh lights that HiGen-s outperforms the baselines while other baseline models are not applicable due to out-of out-of-memory and computational complexity.
Table 2: Comparison of generation metrics on benchmark 3D point cloud. The baseline results are from (Liao et al. 2019)
3D Point Cloud
Model
Dep. J
Clus. 4
Orbill
Spec.
Exdoe-Renyl
3.1e-01
1.22
1.27
4.26e-02
GRAN
1.75e-02
5.1e.01
2.1e01
7.45e-03
HiGen-s (L=2)
3.48e-02
282c-01
3.4e-022
5.46e-03
HiGen- (1.=3)
4.970412
3.196001
1.97-022
5.2.-03
This modification can also address a potential limitation related to edge independence when generating all the communiimssss simultaneously. However, it's important to note that the significance of edge independence is more prominent in high-density graphs like community generations, (Chanpuriya al. (02T), whereas its impact is less significant in sparser inter-communities of hierarchical approach. This is evident by the performance improvement observed in our experiments.
6 DISCUSSION AND CONCLUSION
Node ordering sensitivity: The predefined ordering of dimensions can be crucial for training autoregressive (AR) models (Vinyals et al. 2015), and this sensitivity node orderings is particularly pronounced in autoregressive graph generative models (Liao et al. [2019] Chen et al. [202I]. However, in the proposed approach, the graph generation process divided into the generation of multiple small partitions, performed sequentially across the levels, rather than generating the entire graph by single AR model. Therefore, given an ordering for the parent level, the graph generation depends only the permutation of the nodes within the graph communities rather than the node ordering of the entire graph. other words, the proposed method is invariant to large portion of possible node permutations, and therefore the set of distinctive adjacency matrices is much smaller in HiGen. For example, the node ordering 11 = [U1, 02 V3, 2n] with clusters Vg, = {ui, {2) and Vg2 {V3, ) has similar hicrarchical graph T22 [U1, V/s U2 Ua]. since the node ordering within the communities is preserved at all levels. Formally, let {C, Vi E Vęr=1 } be the set of communities at level / produced by a deterministic partitioning function, where n = [V(C)) denotes the size of each partition. The upper bound on the number of distinct node orderings in an HG generated by the proposed process then reduced to II II, mf
The proposed hierarchical model allows for highly parallelizable training and generation. Specifically, let n. := max; (C,,) denote the size of the largest community, then, it only requires On, log n) sequential steps to generate graph of size n.
Block-wise generation: GRAN generates graphs one block of nodes at a time using an autoregres- sive approach, but its performance declines with larger block sizes. This happens because adjacent nodes in an ordering might not be related and could belong to different structural clusters. In con- trast, our method generates node blocks within communities with strong connections and predicts cross-links between communities using a separate model. This allows our approach to capture both local relationships within community and global relationships across communities, enhancing the expressiveness of the graph generative model.
Conclusion This work introduces a novel graph generative model, HiGen, which effectively captures the multi-scale and community structures inherent in complex graphs. By leveraging hier- archical approach that focuses on community-levy HiGen demonstrates significant improvements in performance and scalability compared to existing models, bridging the gap between one-shot and autoregressive graph generative models. Experimental results on benchmark datasets demonstrate that HiGen achieves state-of-the-art performance in terms of graph generation across various metrics. The hierarchical and block-wise generation strategy of HiGen enables scaling up graph generative models to large and complex graphs, making it adaptable to emerging generative paradigms.
generation and cross-community link prediction,
'It is worth noting that all node permutations do not result in distinctive adjacency matrices due to the automorphism property of graphs (Liao et al.] 2019 Chen et al., 2021). Therefore, the number of node permutations provides an upper bound rather than an exact count.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY
To ensure reproducibility, we provide comprchensive documentation key elements in this work. The complete proofs of the theorems, community generative model, bipartite distribution, GNN architectures, and the loss function can be found in Appendices A, B, and C. Furthermore, Section and Appendix D include experimental details, model architectures, benchmark graph datasets, their statistics, the computational resource and the graph partitioning function. These resources collectively facilitate the reproducibility of our research findings.
ACKNOWLEDGMENTS
We would like to thank Fatemeh Fani Sani for preparing the schematic figures.
REFERENCES
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with bregman divergences. Journal of machine learning research, 6(10), 2005.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439): 509-512, 1999.
David Blei, Andrew Y Ng. and Michael Jordan, Latent dirichlet allocation. Journal of machine Learning research, 3(aan):93311022, 2003.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities large networks. Journal of statistical mechanicx: theory and experiment, 2008(10): (188(100)10000, 2008.
Aleksandar Bojchevski, Oleksandr Shehur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. arXiv preprint 1833v:1803.00810 2018.
Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. On the power of edge independent graph models. Advances Neural Information Processing Systems, 34: 24418-24429, 2021.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco JR Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph generation. arXiv preprint arXiv:2106.0660 06189, 2021.
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint arXhv:2305.04111, 2023.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International Conference Machine Learning, pp. 2302-2312, PMLR, 2020.
Nicola De Cao and Thomas Kipf. Molgan; An implicit generative model for small molccular graphs. arXiv
preprint arXiv: 1805. 1973, 2018.
Paul Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology. 330(4):771-788 2003.
Keyu Duan, Zirui Liu, Peihao Wang, Wenqing Zheng, Kaixiong Zhou, Tianlong Chen, Xia Hu, and Zhangyang Wang. comprehensive study on large-scale graph training: Benchmarking and rethinking. Advances Neural Information Processing Systems, 35:5376-552 2022.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012. 2020.
Paul Erdos and Alfréd Rényi. On the evolution of random graphs. Publ. Moth. Inst. Hung. Acad. Sci, 5(1):17-60. 1960.
Ian Goodfellow, Jean Pouget-Abadie Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair. Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11): 139-144, 2020.
10

---

Published as a conference paper at ICLR 2024
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. arXiv preprint arXiv:2210001549, 2022.
Hossein Hajimirsadeghi, Wang Yan, Arash Vahdat, and Greg Mori. Visual recognition by counting instances: A multi-instance cardinality potential kernel. In Proceedings of the IEEE conference computer vision and puttern recognition, pp. 2596-2605, 2015.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International conference on machine learning, pp. 4839-4848. PMIR, 2020.
Jaehyeong 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.
Mahdi Karami, Dale Schuurmans, Jascha Sohl-Dickstein, Laurent Dinh, and Daniel Duckworth. Invertible convolutional flow. Advances in Neural Information Processing Systems, 32, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv: (312.61 14, 2013.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 16096029077 2016.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation, 2023.
Maksim Kuznetsov and Daniil Polykovskiy. Molgrow: graph normalizing flow for hierarchical molecular generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8226-8234, 2021.
Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11(Fcb):985 1042, 2010.
Yujia Li, Oriol Vinyals. Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.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.
Scott Linderman, Matthew Johnson, and Ryan P Adams. Dependent multinomial models made easy: Stick- breaking with the polya-gam gamma augmentation. Advances in Neural Information Processing Systems, 28, 2015.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows, 2019.
Tengfei Ma. Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autocncoders. arXiv preprint arXiv: / 010. 02630, 2018
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A Platform for Embodied AT Research. In Proceedings the IEEE/CVF International Conference on Computer Vision (ICCV), 2019.
Karolis Martinkus, Andreas Loukas, Nathanadl Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning, pp. 15159-151779 PMLR, 2022.
Azalia Mirhoseini, Anna Goldie. Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori. Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862):207- -12, 2021.
Marion Neumann, Plinio Moreno, Laura Antanas. Roman Garnett, and Kristian Kersting, Graph kernels for object category prediction in task-dependent robot grasping. In International Workshop on Mining and Learning with Graphs at KDD, 2013.
Mark RJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review F, 74(3):036104, 2006a.
11

---

Published as a conference paper at ICLR 2024
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):8577 8582, 2006b.
Leslie Braay. Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metries for graph generative models: Problems, pitfalls, and practical solutions. arXiv preprint arXiv:2106.01098 2021.
Aaron den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalch- brenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint MrXiv:160.00349% 2016.
Santhosh Kumar Ramakrishnan, Aaron Gokaslan, Erik Wijmans, Oleksandr Maksymets, Alexander Clegg. John M Turner, Eric Undersander, Wojeiech Galuba, Andrew Westbury, Angel X Chang, Manolis Savva, Yili Zhao, and Dhruv Batra. cabitat-matterpor 3d dataset (HM3d); 1000 large-scale 3d environments for embodied AI. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Truck (Round 2), 2021.
Ladislav Rampášck, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances Neural Information Processing Systems, 35:14501-14515, 2022.
Scott Reed, Aäron Oord, Nal Kalchbrenner, Sergio Gómez Colmenarejo, Ziyu Wang, Yutian Chen, Dan Belov, and Nando Freitas. Parallel multiscale autoregressive density estimation. International Conference on Machine Learning, pp. 2912-2921. PMLR, 2017.
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 (suppl_ (uupP_)):D431-D433 2004.
Prithviraj Sen, Galilco Namata, Mustafa Bilgie, Lise Getoor, Brian Galligher, and Tina Rliassi-Rad. Collective classification in network data, Al magazine, 29(3):93-93, 93,99999222 2008.
Jianho Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-905, 2000.
Hamed Shirzad, Hossein Hajimirsadeghi, Amir H Abdi, and Greg Mori. Td-gen: Graph generation using tree decomposition. In International Conference on Artificial Intelligence and Statistics, pp. 5518-5537. PMLR, 2022.
Hamed Shizzd,, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. arXiv preprint arXiv:2303.06117 2023.
Kyle Siegrist. Probability, Mathematical Statistics, Stochastic Processes.
LibreTexts, 2017. Theory/
URL
https::/sttat..1irree http:///sss....ooooooooaaaaeaaaa
Probabiiiity_Mttheeettaaaaa httpe/amttaaaaatttittttttteeeeee and Stochastic
Stt.aaiissiiiiseeoooottttttaaaat Proceeseesoeeeseeeeeeeee (Siegrist)
Martin Simonovsky and Nikos Komodakis. GraphVAE: Towards generation of small graphs using variational autoencoders. arXiv preprint arXiv:1802.03444 2018
Rylce Thompson, Boris Knyazev, Flahe Ghalehi, Jungtack Kim, and Graham W Taylor. On evaluation metries for graph generative models. arXiv preprint arXiv:2201.0987), 2022.
Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. arXiv preprint arXiv:2006. 16904 2020.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress:
Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. arXiv preprint 1rXiv:1511.0633) 2015.
Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. Advances in neural information processing systems, 32, 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In ICMI, pp. 5694-5703, 2018.
12

---

Published as a conference paper at ICLR 2024
A
NOTATION DEFINITION
Notations
Brief definition and interpretation
-V, E)
A graph with nodes (vertices) V and edges
F: V (
graph partitioning function that partitions a graph communitics (a.k.a. cluster modules)
C (V(C), E(C))
i-th community graph cluster of nodes) at level
A A A
adjacency matrix a graph, community bipartite
B = (MC)), V(C)), E(B)))
bipartite (ur cruss-community) graph composed of cross-links between neighboring communities
of = Pa(C))
parent node of C₁ at the higher level
4 = Pa(Bi,) = (v! of
parent edge of Bly at the higher level
" EnERiCH we
weight of edge (of ../ b/["):: ): sum of the weights of the edges within their child community
5/51 EnERcOE we
weight of edge (of-1 1, .1 1 ): sum of the weights of the edges within their child bipartite
Wo Eeceigrs We = |8l
sum all edge weights remains constant all levels
HG = ( g.....--3 -h-1 g00h
the set graphs in all levels, where g is a single node root graph and g is the final graph the leaf level.
Mu(u/ v, A)
Multinomial distribution of random vector u, with parameters (v, A)
Bi(y |r, m))
Binomial distribution of random variable v, with parameters (r, 1))
&(CL,)) ((t,)) <)
set of candidate (augmented) edges from the new node, vx(C)) to its preceding nodes of community
Cie (vicl,-,) u -)
already generated community the t-th step. augmented with the of candidate odges. Its size is
u. = = and)))
Random vector weights the candidate edges di, (the 1-th row the lower triangle A
v. -1uu.
of candidate edge weights step
n. = wh/ Exer Va
remaining edges' weight at step
hel,
x d, matrix node embeddings of é!,
E [C(,), r) dy dimensional matrix of candidate edge embeddings
g'
augmented graph composed of all the communitics, {C} V(g" and the candidate edges of all bipartites, (B) V(i.j) c ((g used for bipartite generation.
B PROBABILITY DISTRIBUTION OF COMMUNITIES AND BIPARTITES
Theorem B.1. Given a graph G and an ordering n. assuming there is deterministic function that provides the corresponding high-level graphs in hierarchical order as 1L-LL ..., Go), then:
B( = x) = p((g", g''- ,..., (...))))TT = p(G . (9 (.,,,)))))))))))))) p(g - | ( p(g))
II p(g _ g'- p()0)
(8)
13

---

Published as a conference paper at ICLR 2024
Proof. The factorization is derived by applying the chain rule of probability and last equality holds as the graphs at the coarser levels are produced by a partitioning function acting on the finer level graphs. Overall. this hierarchical generative model exhibits a Markovian structure.
B. PROOF OF THEORRM 3.1
Lemma B.2. Given the sum of counting variables in the groups, the groups are independent and each of them has multinomial distribution:
M
p(w w
[u1, -.. UM vast) II Mu(vm Am)
m=1
0m
where: Am
1 0
Here, probability vector (parameter) Am the normalized multinomial probabilities of the counting variables in the m-th group.
Proof.
P(W)
p(w((v1,...g vast)
I(v1
1 u1 ... VM = 1 uM)
p(
[1v (V1,
VM
0 Wi
17
T(v1 = u1
VM = 1s uM)
uc!
Li=1 03
00 E
II w.
201
(1 01) m1
(1 0M)
12
V1!
x Vad
A1.
AMa
B. un s=1
uM 1=1
Mu(Vi, A1) x... X Mu(var, AM)
In hierarchical graph, the edges has non-negative integer valued weights while the of all the edges in community C² and bipartite graph By are determined by their corresponding edges in the parent graph, i.e. w and w respectively. Let the random vector [we]e E(G*) denote the set of weights of all edges of g' such that wh = T w, its joint probability can be described as multinomial distribution: Mu(w Wo, 0')
((G") II
wo!
(e'(c)
wle]
8(G) II
w(e]
where {0' [e] E [0, 1]
s.t. 1 = 1} are the parameters the multinomial distribution Therefore, based lemma B.2 these components are conditionally independent and each of them has multinomial distribution:
p(g' (g
II
Mu([wele c (.00)
II
Mu([wele Byy w O,y))
e v(gi 1)
(d.)) E(G) 1)
where (0 E [0, s.t. 1 17 = (1. E(g are the parameters the model.
Therefore, the log- log-likelihood of g can be decomposed as the log-likelihood of its sub-structures:
log ( Σ
log Per (C) g'
Σ
log (B,, g
(10)
REV
(6.5)
'It is analogous to the random trial of putting halls into & boxes, where the joint probability of the number of balls in all the boxes follows the multinomial distribution.
14

---

Published as a conference paper at ICLR 2024
Bipartite distribution: Let's denote the set of weights of all candidate edges of the bipartite Biy by random vector := [wele E(B),) its probability can be described
[8( II ==1
w ~ Mu(w w/j 0,yy)
(e(
w/e]
(11)
1 )
Ie
w(e)
where [0% 0yyle] 2 0,
E = 1} are the parameter of the distribution, and the multinomial
coefficient T is the number of ways to distribute the total weight w/ Σ all candidate edges of By
- |((B)))
w[e] into
Similarly, the probability distribution the set of candidate edges for each community can be modeled jointly by multinomial distribution but as our objective is model the generative probability of communities in each level as an autoregressive process we are interested to decomposed this probability distribution accordingly.
Community distribution:
B.2 GENERATING A COMMUNITY AS EDGE- BY- EDEEDGE AUTOREGRESSINE PROCESS
Lemma B.3. random counting vector w E & with multinomial distribution can be recursively decomposed into a sequence of binomial distributions as follows:
E Bi(we We www Eice Wi, Oc)
Mu(w (1, WE w. [01, Bgl) II
(12)
O0 Σice O₃
where: 0 =
This decomposition is known stick-breaking process, where Oe is the fraction of the remaining probabilities we take away every time and allocate to the e-th component (Linderman et al. 2013).
B.3 PROOF OF THEBREM
For random counting vector w E Z with multinomial distribution Mu(w, 0), let's split into
M disjoint groups w [11: .... uM where Umn E E Σm Fm E, and also split the
probability vector as 0 [0, .... as) Additionally, let's define sum of all weights in m-th group by a random variable Vm = Eem Um,e.
Lemma B.4. Sum of the weights in the groups, um ZEm distribution:
EM
Em
E has multinomial
(.Vi,,.,VMl) Mu(w,, (ai, awr))
where: Oem = Σ 0m m.)
(13)
In the other words, the multinomial distribution is preserved when its counting variables are combined Siegrist (2077).
Theorem B.5. Given the aforementioned grouping of counts variables, the multinomial distribution can be modeled as a chain of binomials and multinomials:
M
Mu(w, 0 = 1i...... 0ml) = II 00
Bi(w
Σ
Vi, Mem) Mu(Vms Am),
(14)
icm
1 0
Qm
where:
TJem
Eiem 1 0,
Am
o.
Proof. Since sum of the weights of the groups, Y.n. are functions of the weights in the group:
p(w)= p(w, (V1,..., vMr) p(wl(v1,..., Va (p(((1,........).. var))
15

---

Published as a conference paper at ICLR 2024
binomial
1=1
multinomial
1= / 14
Bi(14, n12) 1/3 7 Wy Mu(7, 2q) [0, 2, 5]
1= ==7
1/4 ~ Bi(7, 91) 144 =
Wi Mu(7 Ag) W3 12,
(b)
Figure 2:
An illustration of the generation process of the single community level 1 of HG in Figure la
according to Theorem [.2] and equation (5) The total weight of this community graph is 29, determined by the parent node of this community. Consequently, the edge prohabilities of this community follow Multinomial distribution. This Multinomial is formed Binomials and Multinomials, as outlined 3.2 each iteration of this stikkbreekinng process, first a fraction of the remaining weights r: is allocated to the t-th row (corresponding to the t-th node in the sub-graph) and then this fraction, V., distributed among that row lower triangular adjacency matrix, A.
autoregressive (AR) process and decomposed
sequence of
According lemma B.4 sum of the weights of the groups is a multinomial and by lemma B.3 can be decomposed to sequence of binomials:
p([v1...., vM3) Mu(w, [a1: am)) II Bi(w
Σiem Vis fmm)
where: Om 1T O mm: ie
Ore
Eice Omm
Also based on lemma B.2 given the sum of the wights of all groups, the groups are independent and has multinomial distribution:
p(wlfvi, vast) II
Mu(ym: Am)
m=1
0m
where: Am
17 0...
B.4 TRAINING LOss
According to equations
and (2). the log-likelihood for graph sample can be written
L
log (gg)
Σ Σ 1=1 iE V(Gi-1)
logp(C) 1 +
Σ
log DOg,(B,
1 (Ch (15)
(KJ)E E(G
Therefore, one need to compute the log- likelihoooo of the communities and cross-conee cross-community compo- nents. The log-likelihood of the cross-communities are straightforward using equation 7 For the
16

---

Published as a conference paper at ICLR 2024
log-likelingg likelihhod of the communities, we break it into subsets of edges for each node in autoregres- sive manner, with probability of each subset modeled in equation (5), therefore, the log- log-likelihood is reduced to
ce log pl u, (Ct,))
log p(c |
where p(u,(C),)) is defined in equation as mixture of product of binomial and multinomial. Since the binomial and multinomial are from the exponential family distribution, their log- likelihhodd reduces to Bregman divergence [Banerjee et al. (2005). The binomial log likelihood is general form of Bernoulli log likelihood, binary cross entropy, and multinomial log likelihood is a general form of Multinoulli (categorical) log likelihood, categorical cross entropy.
For training of generative model for the communities at level I we randomly sample total of augmented communities, so given s; of these sub-graphs are from community C; then, we estimate the conditional generative probability for this community by averaging the loss function over all the subgraphs in that community multiplied by the size of the community:
log gi-l) = |C|| p( p( Vt V:))::)
(16)
C MODEL ARCHITECTURE
C.1 GRAPH NEURAL NETWORK (GNN) ARCHITECTURES
To overcome limitations in the sparse message passing mechanism, Graph Transformers (GTs) (Dwivedi & Bresson 2020) have emerged as recent solution. One key advantage of GT's is the ability for nodes to attend to all other nodes in graph, known as global attention, which addresses issues such as over-smoothing, over-squashing, and expressiveness bounds Rampášek et al. (2022). GraphGPS provide a recipe for creating more expressive and scalable graph transformer by making a hybrid message-passing graph neural networks (MPNN)+Transforee recent GNN models propose address the limitation of standard MPNNSs in detecting simple substructures by adding features that they cannot capture on their own, such as the number of cycles. framework for selecting and categorizing different types of positional and structural encodings, including local, global, and relative is provided in Rampášek et al. (2022). Positional encodings, such as eigenvectors of the adjacency or Laplacian matrices, aim to indicate the spatial position of a node within a graph, so nodes that are close to each other within graph subgraph should have similar positional encodings. On the other hand, structural encodings, such as degree of a node, number of k-cycles node belong or the diagonal of the m-steps random-wall matrix, aim represent the structure of graphs or subgraphs, so nodes that share similar subgraphs or similar graphs should have similar structural encodings.
architecture. Additionally,
(9')), In order encode the node features of the augmented graphs of bipartites, GNN!, (G'), cus- tomized GraphGPS in various ways. We incorporated distinct initial edge features to distinguish augmented (candidate) edges from real edges. Furthermore, for bipartite generation, we apply mask on the attention scores of the transformers of the augmented graph O' restrict attention only to connected communities. Specifically, the i-th row of the attention mask matrix is equal to 1 only for the index of the nodes that belong to the same community or the nodes of the neighboring communities that are linked by a bipartite, and 0 (i.e., no attention to those positions) otherwise.
The time and memory complexity of GraphGPS can be reduced to O(n + m) per layer by using linear Transformers such as Performer (Choromanski et al., 2020) or Exphormer, a sparse attention mechanism for graph, [Shirzad et al. (2023) for global graph attention, while they can be as high quadratic in the number of nodes if the original Transformer architecture is employed. We leverage the original Transformer architecture for the experiments on all graphs datasets that are smaller than 1000 nodes except for point cloud dataset where Performer is used.
We also employed GraphGPS the GNN of the parent graph, LNN'''(('-1) On the other hand, for the community generation, we employed the GNN with attentive messages model, proposed in (Liao et al. 2019). as GNN com- Additionally, we conducted experiments for the Enzyme dataset, using GraphGPS with the initial features as used in Liao et al. 2019) for GNN! com. which resulted in comparable performance in the final graph generation.
17

---

Published as a conference paper at ICLR 2024
C.2 COMPLEXITY ANALYSIS
Given the linear complexity of (n + m) for the Graph Neural Network (GNN) building blocks (GraphGPS and GAT), we can analyse the complexity of the proposed hierarchical graph generation. Let's denote the size of the largest community at level as n == max, (1C:) | and ni = ( As explained in section and illustrated Figure Taareeaani and algorithms 2 each level I of hierarchical generation is composed of:
0) Parent node embedding, (g'-), with O(n'-1 +mm--++mm])) m²-1).
1) Parallel community generation for (C; Vi E v(g'-1)), which require n' generation steps. For each community Cj node embedding computation, GNN com (C)), requires O + m))) operations, resulting in ni Σ. On + m n'.(n'' + +m²). In training all of these can be performed parallel on the sampled batch.
2) Bipartite generation require On' + m²) for node embedding computation, GNN hp (9'), where m' |E(ğ))| = (m'' ( On'''')
So, each level of graph generation requires On (n' m²)) computations, and consequently, the overall complexity of HiGen is D Ond + md') = Onn.(n + m) L). Moreover, since most of the computations are parallelizable, graph sampling requires O( L) = One log,, 1)) sequential steps to generate a graph of size n.
The complexity analysis for training follows similar approach, but with the advantage that all steps can be executed in parallel. For batch training, we can adopt either subgraph wise sampling node-wise sampling. ensuring that each batch meets GPU memory constraints (Duan al. 2022). As detailed in Section [B.4] the proposed model enables the random sampling of a total of augmented communities, eliminating the need load the entire graph into memory, distinction from diffusion models like DiGress.
Complexity of partitioning algorithm: Although optimizing modularity metric is an NP-hard problem in general, we used the Louvain algorithm, which is greedy optimization method with On log n) complexity. However, the graph partitioning is only applied once on the training data as pre-processing step and its results are cached to be used throughout the entire training.
The pseudocodes for training and graph sampling using HiGen are presented in algorithms I 2p
Table 3: Complexity of different graph generative models. Here, n is the number nodes, m is number of edges nee the size of the largest cluster graph and is the number of hierarchical levels. In the haseline models, T' is the number of diffusion steps, K is the maximum number of active nodes during the diffusion process of EDGE (Chen al. 2023
Model
Runtime
Sampling steps
GraphRNN
O(n))
(n
GRAN
O(n2)
(
SPECTRE
O(n3)
0(1)
GDSS
O(T n²)
O(T)
DiGress
O(T n²)
O(T)
EDGE
O(T max(m, K))
O(T)
HiGen
(n m) L)
O L)
C.3 CONNECTED GRAPH GENERATION
An advantage of the proposed model its ability to enforce connected graph generation by con- straining the total sum of the candidate edge weights to v, > 0 in the recursive stick-breaking
5(t) We make assumption that the graph is not very dense such that the number of edges is at the order of number of nodes, iee. m O()).
18

---

Published as a conference paper at ICLR 2024
Algorithm 1 Training step of HiGen
1: Input: A hierarchical graph HG ....,,t---1 g4h
for all /
do
D Can be done in parallel
3: C² sample augmented communitics C² from (cl,, mer is c|I
C ith community level
4: C² batch(C')
5:
ğ' < join([C) vi V( u (8) (i,5) EE(g")))) Bl the candidate edges By
6: end for
for all I to L do
D Can be done in parallel
hig-1 + (g'-1)
> get parent node embeddings
het - GNN (C))
b skipped for / since it BP loss' + v(gr-1) logp(C! 9' log (g'
high (0")
using eqn.
12: end for optimizer. step step( loss')
13:
Algorithm 2 Sampling from HiGen
1: Wo (wo)
& Pwo is the empirical distribution of the number of edge in training data
2:
3: for / 1 to L do
high1 < GNN CONNi-1(0)) (g'-11
O) Get parent node embeddings
C- 0
v 1) Generation of communities in parallel for all communitics
for i= to n = -V(g'-1) do
Ci +- (0. ri -1 & Initialize with an empty graph and remaining edges' weight = weight of the parent node
8:
C C U
C
9:
end for
10:
while + do
> grow all communities autoregressively
C² batch(()
12:
hag GNN com (C))
13:
(8', w/. 21) < f(her, h1)-1)
using eqn.
14:
for all i -1to Vig do
D in parallel for all communities sample index categorical
15:
Cat((3)
16:
v Bi(r., [i])
D sample sum of candidate edges for node (step) t
17:
~ Mu(u, (i))
> sample weights of the candidate edges for node (step)
18:
update remaining edges' weight di generation C
19:
if 0 then
20:
C. < update(C (a) u)
21:
Č + C E!
22:
else
23:
C update(( (Ct, r:)
update ét new sampled edges
end if
25:
for end while
26:
27:
2) Bipartite generation (for >
2)
28:
G' - join( (C) Vi V(G"-1)) u (8), (i.)) E((g-))) & B all the candidate edges of B sec. 3.2
29:
hag + (G))
30:
(3', 0') + (ight,
D using
31:
k Cat(B
sample mixture index from categorical dist. P in parallel for all BPs P sample weights of B
32:
for all (i E E(gi-1) do
33:
wiy ~ Mu(w 11 ((
34: end for
35: G' + D'+jjon(((C) vi V(G u (8), V(.)) ((
Join all components
36: end for
37: return G = =
19

---

Published as a conference paper at ICLR 2024
process. This is accomplished by modeling and sampling an auxiliary variable v, 2 0 from the binomial distribution in theorem 3.2 as Bi(Ve -- 1, k Subsequently, its effective value is set as V, = V + I. guarantecing the existence of at least one edge among the candidate edges connecting the new node and the previously generated community in the autoregressive community generation process. This technique was particularly employed in our experiments with connected graphs.
It's noteworthy that the proposed method is not restricted connected graphs and has the capability to model and generate graphs with disconnected components as well. HiGen, in essence, learns to reverse graph coarsening algorithm, such as Louvain. In cases where graph is disconnected, the coarsening algorithm produces an HG with a disconnected graph at the top level (1 = 1 in Figure [Ta]. To illustrate, consider the example graph in Figure Ialis split into two left and right components (by removing the edge between the yellow and blue communities and the edge between the cyan and orange communities, and subsequently removing their corresponding edge at the top level (1 = 1)), therefore the coarsened graph at the top level becomes a disconnected community composed of two components. Consequently, to potentially generate disconnected graphs, we would need to relax the community generation at level / = to include disconnected communities. Meanwhile, we can maintain the constraint of connected community generation for the subsequent levels (1 ( 1).
C.4 GENERATING GRAPH WITH NODE AND EDGE ATTRIBUTES
Adapting HiGen to handle attributed graphs involves reversing the partitioning (coarsening) algo- rithms tailored for clustering attributed graphs like molecular structures. For example GNN-based clustering method inspired by the spectral relaxation of modularity metric for graphs with node attributes proposed by Tsitsulin al. (2020). Toward that goal, we need to modify the proposed community generation and cross- communcy predictor to learn attributed edges or use the graph generation models with such capability.
Extending HiGen for graphs with edge types involves assigning a weight vector w E Zd to each edge c (i, where d is the number of edge types and each feature indicates the number of one specific edge type that the edge ety at level is representing. The autoregressive multinomial and binomial generative models offered in this work then be applied to each dimension so that the attributed graph at level + 1 is generated based on its parent attributed graph G'. Note that, in this approach, the attribute of node 2 can be added self loop edge Ca,: (i, i) with weight w,,; = z;- Consequently, the model only needs to predict the edge attributes (or edge types), aligning with HiGen's is edge weight generation capabilities.
Another approach is training an additional predictor, such as a GNN model for edge/node classifi- cation, dedicated to predicting edge and node types based on the graph structure. This model does not have the difficulties associated with graph topology generation such as graph isomorphism and edge independence focusing solely on predicting edge/node attributes. This additional model can be tailored to specific application requirements and characteristics. Addressing attributed graphs is leknowledged as a potential future avenue for research.
D EXPERIMENTAL DETAILS
Datasets: For the benchmark datasetst, graph sizes, denoted as Ddataset (DVmaz |Maeg EE| maaa: (8)oog), are: D Dprotein
(500, 258, 1575, 646), DEgo (399, 144, 1062, 332), Droint- -Coud = (5.03k, 1.4k, 10.9k, 3k).
Before training the models, we applied Louvain algorithm to obtain hierarchical graph structures for all of datasets and then trimmed out the intermediate levels to achieve uniform depth of L = 2. In case of HG s with varying heights, empty graphs can be added at the root levels of those HGs with lower heights to avoid sampling them during training. Table 4 summarizes some statistics of the hierachical graph datasets. An 80%- split was randomly created for training and testing and 20% of the training data was used for validation purposes.
Model Architecture: In our experiments, the GraphGPS models consisted of 8 layers, while each level of hierarchical model has its own GNN parameters. The input node features were augmented with positional and structural encodings, which included the first 8 eigenvectors corresponding to
20

---

Published as a conference paper at ICLR 2024
Table 4: Summary of statisties of the benchmark graph datasets, Where n. max((C)) denotes the size of largest cluster the leaf level, num,, is number of clusters in each graph and avg teat) and avg(mod gen) are the modularity score of the test set and the generated samples by HiGen.
datasel
mar(n)
avg(n)
avg(ne)
aeg(numme)
ang(mod test)
avg(mod gen)
Enzyme
125
33
9.8
4.62
0.59
0.62
Ego
399
144
37.52
8.88
0.56
0.66
Protein
500
258
26.05
13.62
0.77
0.8
SBM
180
105
31.65
3.4
0.6
0.59
3D point Cloud
5K
1.4K
97.67
18.67
0.85
0.88
the smallest non-zero eigenvalues of the Laplacian matrices and the diagonal of the random-wall matrix up to 8 steps. We leverage the original Transformer architecture for all detests except Point Cloud dataset which use Performer. The hidden dimensions were set to 64 for the Protein, Ego, and Point Cloud datasets, and 128 for the Stochastic Block Model and Enzyme datasets. The number of mixtures was set to K=20.
In comparison, the GRAN models utilized layers of GNNs with hidden dimensions of 128 for the Stochastic Block Model, Ego, and Enzyme datasets, 256 for the Point Cloud dataset, and 512 for the Protein dataset. Despite having smaller model sizes, HiGen achieved better performance than GRAN.
For training, the HiGen models used the Adam optimizer Kingma Ba (2014) with a learning rate of 5e-4 and default settings for 31 (0.9), B2 (0.999), and e (Ie-8).
The experiments for the Enzyme and Stochastic Block Model datasets were conducted on MacBook Air with an M2 processor and 16GB RAM, while the rest of the datasets were trained using an NVIDIA L4 Tensor Core GPU with 24GB RAM as an accelerator.
D.1 MODEL SIZE COMPARISON
Here, we compare the model size, number of trainable parameters, against GRAN, the main baseline of our study. To ensure the HiGen model of the same size or smaller size than GRAN, conducted the experiments for SBM and Enzyme datasets with reduced sizes. For the SBM dataset, we set the hidden dimension 64, and for the Enzyme dataset, it was set to 32. The resulting model sizes and performance metrics are presented in Tables 5 6
Table 5: Comparison of model sizes (number of trainable parameters) of HiGen vs GRAN.
Protein
3D Point Cloud
Ego
Enzyme
SBM
GRAN
1.75e+7
5.7e+6 6.26c+6
1.5e+7
1.54e+6
3. 3.16e+6
HiGen
4.00c+6
3.96c+6
1.48c+6
3. 3.19c+6
Table 6: Comparison of generation metries for Enzyme and Stochastic Block Model (SBM). Here, the hidden dimension of HiGen is set 32 and 62 for Enzyme and SBM, respectively.
Enzyme Clus.
Stochastic block model
Model
Deg.
Orbit
Model
Deg. |
Clus.
Orbit,
Spec. J
Training set
0.0011
0.0025
3.7c-4
Training set GraphRNN
0.0008
0.0332
0.0255
0.0063
GraphRNN
0.017
0.062
0.046
0.0055
0.0584
0.0785
0.0065
GRAN
0.054
0.087
0.033
GRAN
0.0113
0.0553
0.0540
0.0054
GDSS
0.026
0.061
0.009
SPECTRE
0.0015
0.0521
0.0412
0.0056
HiGen
6.8c-3
0.067
1.3c-3
DiGress
0.0013
0.0498
0.0433
HiGen
0.0015
0.0520
0.0370
0.0049
These results highlight that despite smaller or equal model sizes, HiGen outperforms GRAN's performance. This emphasizes the efficacy hicrarchically modeling communities and cross- community interactions distinct entities. This results can be explained by the fact that the proposed
21

---

Published as a conference paper at ICLR 2024
model needs to learn smaller community sizes compared to GRAN, allowing for the utilization of more compact models.
D.2 SAMPLING SPEED COMPARISON
In table 8 we present a comparison of the sampling times between the proposed method and its primary counterpart, GRAN, measured in seconds. The sampling processes were carried out server machine equipped with 32-core AMD Rome 7532 CPU and 128 GB RAM.
Table 7: Sampling times in seconds.
Protein
Ego
SBM
Enzyme
GRAN
46.04
2.145
1.5873
0.2475
HiGen
1.33
0.528
0.4653
0.1452
Table Sampling speedup factor of generative model GRAN: (GRAN(8)) (8). The speedup factor of baseline models obtained from Martinkus al. (2022).
Protein
SBM
GRAN
1
GraphRNN
0.32
0.37
SPECTRE
23.04
25.54
HiGen
34.62
3.41
As expected by the model architecture and is evident from the table HiGen demonstrates significantly faster sampling, particularly for larger graph samples.
E ADDITIONAL RESULTS
Table 9 presents the results of various metries for HiGen models all benchmark datasets. The structural statistics are evaluated using the Total Variation kernel as the Maximum Mean Discrepancy (MMD) metric.
In addition, the table includes the average of Beedom-GNN-bbee metrics Thompson et al. 2022) over 10 random Graph Isomorphism Network (GIN) initializations. The reported metrics MMD with RBF kemel (GNN RBF), the harmonic mean improved precision+recall (GNN FI PR) and harmonic mean of density+coverage (GNN F1 PR).
22

---

Published as a conference paper at ICLR 2024
Table 9: Various graph generative performance metrics for HiGen models all benchmark datasets.
Model
Deg.
Clus. 4
Orbiti
Spec.
RBF
GNN FI PR 1
DC
Enzyme
GRAN
8.45c-03
2.62c-02
2.11e-02
3.46e-02
0.0663
0.950
0,832
HiGen-m
6.61e-03
2.65c-02
2.15e-03
8.75e-03
0.0215
0,970
0.897
HiGen
2.31e-03
2.08c-02
1.51e-03
9.56e-03
0.0180
0.978
0,983
Protein
HiGen-m
0.0041
0.109
0.0472
0.0061
0.167
0.912
0.826
HiGen
0.0012
0.0435
0.0234
0.0025
0.0671
0.979
0.985
Stochastic block model
GRAN
0.0159
0,0518
0.0462
0,0104
0.0653
0.977
0.86
HiGen-m
0.0017
0.0503
0.0604
0.0068
0.154
0.912
0.83
HiGen
0.0019
0.0498
0.0352
0.0046
0.0432
0.986
Ego
GraphRNN
9.55e
0.094
0.048
0.025
0.0972
0.86
GRAN
7.65c-3
0.066
0.043
0.026
0.0700
0.76
0.50
HIGen-m 0.011
0.063
0.021
0.013
0.0420
0.87
0.68
HiGGn
1.9c-3
0.049
0.029
0.004
0.0520
0.88
0.69
Table 10: Performance comparison of HiGen model Ego datasets against the baselines reported in (Chen al. Gaussian EMD kernel was used structure- based statistics together with GNN-based performance metrics: GNN RBF and Frechet Distance (FD)
)023).
Ego
Model
Deg.
Clus.
Orbit
GNN RBF
FD
GraphRNN
0.0768
1.1456
0.1087
0.6827
90.57
GRAN
0.5778
0.3360
0,0406
0.2633
489.96
GDSS
0.8189
0.6032
0.3315
0.4331
60.61
DiscDDPM
0.4613
0.1681
0.0633
0.1561
42.80
DiGress
0.0708
0.0092
0.1205
0.0489
18.68
EDGE
0.0579
0.1773
0.0519
0.0658
15.76
HiGen-m
0.114
0.0378
0.0535
0.0420
12.2
HiGen
0.0472
0.0031
0.0387
0.0454
5.24
As the results show, HiGen outperforms other baseline, particularly improving in terms of degree statistic compared to EDGE which is explicitly degree-guided graph generative model by design.
E. POINT CLOUD
We also evaluated HiGen the Point Cloud dataset, which consists of 41 simulated 3D point clouds of household objects. This dataset consists of large graphs of approximately 1.4k nodes on average with maximum of over 5k nodes. In this dataset, each point is mapped
node in graph, and edges are connecting the k-nearest neighbors based on Euclidean distance in 3D space (Neumann al. 2013 We conducted the experiments for hierarchical depth of T. 2 and L = 3. In the case of = 2, we spliced out the intermediate levels of Louvain algorithm's 's output. For the L = 3 experiments, we splice out all the intermediate levels except for the one that is two level above the leaf level when partitioning function's 's output had more than 3 levels to achieve final HGs with uniform depth of L. For all graphs, Louvain's output had least 3 levels.
However, the quadratic growth of the number of candidate edges in the augmented graph of bipartites G the graph composed of all the communities and the candidate edges of all bipartites used in section 3.2 for bipartite generation can cause out of memory issue when training large graphs in the point cloud dataset. To address this issue, subset of) bipartites at a time to fit the available memory. In our experimental study, we generated bipartites sequentially, sorting them based on the index of their parent edges in the parent level. In this case, the augmented graph ý' used for generating the edges of Bl, consists of all the communities
sample sub-graphs and generate one (or
23

---

Published as a conference paper at ICLR 2024
{Ck vk I max(i, and all the bipartites (Bmm. V(m, n) < (1,5)). augmented with the candidate edges of B This model is denoted by HiGen-s in table 11
This modification can also address a potential limitation related to edge independence when generating all the inter-communities simultaneously. However, it's important to note that the significance of edge independence is more prominent in high-density graphs like community generations, (Chanpuriyal et al. 202T), whereas its impact is less significant in sparser inter-communities of hierarchical approach. This is evident by the performance improvement observed in our experiments.
The GraphGPS models that used for this experiment have employed Performer (Choromanski et al. 2020) which offers linear time and memory complexity. The results in Table TTighlightt the performance improvement of HiGen-s in both local and global properties of the generated graphs.
Table 11: Comparison of generation metrics on benchmark 3D point cloud for L = and deeper hierarchical model of I. = 3. The baseline results are obtained from (Liao et al. 2019).
3D Point Cloud
Model
Deg.
Clus.
Orbit
Spec.
Frdos-Renyl
3.1e-01
1.22
1.27
4.26e-02
GRAN
1.75e-02
5.1e-01
2.1e-01
7.45e-03
HiGen-s (L=2)
3.48e-02
2.82e-01
3.45e-02
5.46e-03
HiGen-s (I=3)
4.97e-02
3.19e-01
1.97e-02
5.2e-03
An alternative approach is to sub-sample a large graph such that each augmented sub-graph consists
of bipartite B and its corresponding pair of communities C,, Cj. This approach allows for parallel generation of bipartite sub-graphs on multiple workers but does not consider the edge dependece between neighboring bipartites.
E.2 ABLATION STUDIES
In this section, two ablation studies were conducted to evaluate the sensitivity of HiGen with different node orderings and graph partitioning functions.
Node Ordering In our experimental study, the nodes in the communities of all levels are ordered using breadth first search (BFS) node ordering while the BFS queue are sorted by the total weight of edges between node in the queue and predecessor nodes plus its self-edge. To compare the sensitivity of the HiGen model against GRAN versus different node orderings, we trained the models with default node ordering and random node ordering. The performance results, presented in Table 12 confirm that the proposed model is significantly less sensitive to the node ordering whereas the performance of GRAN drops considerably with non-optimal orderings.
Table 12: Ablation study on node ordering. Baseline HiGen used BFS ordering and baseline GRAN used DFS ordering. TT, and vy are default, random and Fa node ordering, respectively. Total variation kernel is used as MMD metrics of structural statisties. Also, the average of aundom-GNN-bant random GIN initialization reported for MMD with RBF kernel (GNN RBF). the harmonic mean of improved precision+recall (GNN Fl PR) and harmonic mean of tcovery (GNN Fl PR).
metries aver 10
Enzyme
Model
Deg.
Clus.
Orbit
Spec.
GNN RBF
GNN Fl PR
GNN FI DC 1
GRAN
8.45e-03
2.62e-02
3.46e-02
2.11e-02
6.63e-02
9.50e-01
8.32c-01
GRAN (m))
1.75e-02
2. 29c-00
3.78e-02
2.03e-02
6.51c-02
8.24c-01
6.69c-01
GRAN (mz)
3.90e-02
3.24e
3.81e
2.38e
8.31e
6.72e-01
HiGen
2.31e-03
2.08e-02
1.5le-03
9.56e-03
1.80--02
9.78e-01
9.83e-01
HiGen (Tt)
1.83e-03
2.2ee022
6.75e-04
7.08c-03
1.78e-02
9.84-01
9.77c-01
HiGen (19)
3.31e-03
2.34c-02
2.06e-03
9.10c-03
2.04e-02
9.47-01
8.81e-01
HiGen (mz)
1.34e-03
2.13e-02
6.94e-04
6.56e-05 03
1.90e 02
9.61e-01
9.74e-01
24

---

Published as a conference paper at ICLR 2024
Different Graph Partitioning In this experimental study, evaluated the performance of HiGen using different graph partitioning functions. Firstly, to assess the sensitivity of the hierarchical gener- ative model random initialization in the Louvain algorithm, we conducted the HiGen experiment three times with different random seeds on the Enzyme dataset. The average and standard deviation of performance metrics reported in Table 13 which demonstrate that HiGen consistently achieves almost similar performance across different random initializations.
Additionally, explored spectral clustering (SC), which is relaxed formulation of k-min-cut partitioning (Shi & Malik 2000), as an alternative partitioning method. To determine the number of clusters, we applied SC partition the graphs over range of 0.7y/ s S 1.3vn. where represents the number of nodes in the graph. We computed the modularity score of each partition and selected the value of that yielded the maximum score.
The results presented in Table 13 demonstrate the robustness of HiGen against different graph partitioning functions.
Table 13: Multiple initialization of Louvain partitioning algorithm and also min-cut partitioning
Engyme
Model
Deg.
Clus.
Orbit.]
Spec.
GNN RBF L
GNN FI PR
GNN FI
DC
HiGen
2.64e 03-1mmm4
2.09 02:44
7.46e 0441-44e44
1.74g 02.11
2.00e 02-3
.98 38-14---3
96.1.1
HiGen (SC)
2.24e-03
2.10--02
5.59c-04
8.30c-03
2.00e-02
94.
E.3 GRAPH SAMPLES
Generated hierarchical graphs sampled from HiGen models are presented in this section.
25

---

Published as a conference paper at ICLR 2024
Protein
Stochastic Block Model
Train
GRAN
SPECTRE
HiGen
Figure 3: Samples from HiGen trained on Protein and SBM. Communities are distinguished with different colors
and both levels are depicted. The samples for GRAN and SPECRE are obtained from (Martinkus et al. 2022).
26

---

Published as a conference paper at ICLR 2024
Ego
Enzyme
Train
GDSS
GRAN
HiGen
Figure 4: Samples from HiGen trained on Protein and SBM. Communities are distinguished with different colors and both levels are depicted. The samples for GDSS obtained from (Jo al. 2022).
27

---

Published as a conference paper at ICLR 2024
3D Point Cloud
Train
GRAN
HiGen-s
Figure 5: Samples from HiGen trained on 3D Point Cloud. Communities distinguished with different colors and both levels are depicted. samples for GRAN are obtained from (iao el al. 2019).
28


Reviews:
[{"review_id": "XZIADNwFW3", "reviewer": "Reviewer_fvzA", "summary": "The authors mainly aim to propose a graph generative model that can capture hierarchical structures. To this end, the authors propose a coarse-to-fine manner method that generate the graph structures by modeling the distribution of connectivity as a recursive multinomial distribution and decomposing the graph generation process into the generation of communities and bipartites at each level. The proposed method is evaluated on the general graph generation task and 3D point cloud generation tasks.", "questions": "* How does the performance change depending on the partitioning algorithm?\n* Could you elaborate why HiGen outperforms HiGen-m?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "* The proposed coarse-to-fine manner is an effective method to generate larger graphs as it can gradually recover the structure with the knowledge of the hierarchical clusters of the graphs.\n* The performances of the proposed method are superior to the existing autoregressive and diffusion models.\n* The authors provide an informative ablation study on the effect of the node ordering and the graph partitioning method.", "weaknesses": "* The proposed method is effective in generating the graph structures. However, I am concerned that it requires an additional generator to generate the graph attributes for the realistic graph generation and it could be a harder problem to generate the graph attributes correctly only given the structures.\n* To strengthen the contribution of the proposed method, it would be better to evaluate it on the molecular graphs.", "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": "3Z7DJBa2LK", "reviewer": "Reviewer_D2iQ", "summary": "In this paper, the authors introduce Hierarchical Graph Generative Networks (HIGEN), a model designed to encapsulate the hierarchical characteristics of graphs through a progressive generation of graph sub-structures, transitioning from broader to more detailed aspects. At every hierarchical level, the model concurrently produces communities, subsequently generating bipartite graphs to represent cross-edges between these communities, utilizing distinct neural networks for each task. This compartmentalized strategy ensures that the graph generation process is both scalable and efficient, even when applied to large and intricate graphs. The method presented surpasses the performance of current leading techniques across a range of benchmark datasets.", "questions": "Please refer to weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. HIGEN adeptly grasps the hierarchical nature of real-world graphs, facilitating the generation of sub-structures in a manner that is both scalable and efficient.\n\n2. The authors conduct a comprehensive evaluation of the proposed method, utilizing a variety of benchmark datasets to showcase the method's capability in accurately generating graphs that reflect the statistical characteristics inherent to real-world graphs.\n\n3. The manuscript offers an in-depth examination of the graphs produced by the HIGEN models, including a visual comparison of these generated graphs and a rigorous experimental assessment of diverse node ordering and partitioning functions.\n\n4. The authors also present an analysis of computational complexity, alongside a comparison of sampling speeds, providing a holistic understanding of the method's performance and efficiency.", "weaknesses": "1. The proposed method assumes that the input graph is connected, which may not be the case for some real-world graphs.\n2. Due to its hierarchical generation approach, particularly during the community generation phase, the proposed method might face challenges in maintaining control over the global distribution of the graph.\n\nMinor Problem:\nTypo: \"Model Architecture n our experiments\"", "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": "YPgTePxq1o", "reviewer": "Reviewer_tztH", "summary": "This paper proposes HiGen, a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures in a coarse-to-fine fashion. This method enables scalable graph generation for large and complex graphs, while generating community graphs with integer-valued edge weights in an autoregressive manner. Empirical studies demonstrate the effectiveness and scalability of the proposed method, achieving state-of- the-art performance in terms of graph quality across various benchmark datasets.", "questions": "- See weakness above.\n- Typo: Section 5, paragraph “Model Architecture”", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of generating real-world graphs hierarchically is novel and interesting.\n\n- The resulting HiGen model can generate high-quality real-world graphs, with theoretical support on community generation.\n\n- The experiments are convincing, showing that HiGen can outperform many graph generation models on a wide range of datasets.", "weaknesses": "- The authors should include a complete analysis of complexity against previous methods, including the complexity of graph partitioning.", "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": "Xz2FRlkW48", "reviewer": "Reviewer_oTgM", "summary": "The paper proposes a general hierarchical graph generation method, aiming to generate graph in a coarser-to-fine way. The proposed idea is quite reasonable for graph data. The proposed method learns the probability of connectivity of communities and the edges in each community conditioned on the graph of privious layer. Extensive results on several kinds of datasets well demonstrate the effectiveness of the proposed method that could generate graphs with desired properties.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is novel, where the idea of generating graphs without prior knowledge has not been studied yet. And the idea is also reasonable for generating various kinds of real-world graphs.\n2. The proposed method is sound.\n3. The experiments validate the proposed method could generate a hierarchical graph structure.", "weaknesses": "1. The computation complexity of the proposed model is not clear.\n2. Could the proposed method be applied to molecule generation and compared with HierVAE? (Jin et al. 2020)\n3. How to identify the number of layers and the number of communities in each layer?\n4. The metric of novelty is also important for graph generation method. How about the novelty of the generated graphs by the proposed method?", "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": "ciADxYValK", "reviewer": "Reviewer_WR6B", "summary": "The authors propose a new deep graph generative model, HiGen. HiGen generates a graph in a coarse-to-fine manner, wherein a small, \"low-resolution\" graph is generated, and at the next, higher-resolution level, each node at the prior level corresponds to the graph of a community of nodes, whereas each edge corresponds to a bipartite graph between two communities. The concept of this method promises greater scalability, parallelization, and graph quality than prior methods. Experiments on generating several classes of graphs, such as SBMs, proteins, enzymes, ego networks, and point clouds, indicate overall superiority of the quality of graphs produced by HiGen relative to some prior methods.", "questions": "1) As stated above, I suggest breaking out the training/sampling into algorithms to improve readability.\n\n2) There is an abundance of papers proposing new deep graph generative models in recent years, as outlined in this paper's introduction, and these papers generally claim superior graph quality to prior methods. However, there are many degrees of freedom in measuring the quality of graph generation, so it is hard to tell whether there is real progress. With this in mind, how would the authors argue that there is a real advancement in the graph quality of HiGen? As I mentioned above, a theoretical framework is one possibility, but this paper goes in a more empirical direction.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The introduction features an informative summary of recent work in graph generative deep networks. It positions the author's method well in the context of this prior work.\n2) The topic of the paper, deep graph generation, is very popular in recent years.\n3) The concept of the method is logical and promises better runtime than some prior methods. Experiments indicate better graph quality than prior methods as well.", "weaknesses": "1) There is limited theoretical advancement. The theorems in this work regard the correctness of an aspect of the graph generation (specifically, the correctness of a certain factorization of the multinomial distribution). The introduction alludes to challenges in graph generation like \"difficulty capturing complex dependencies in graph structures,\" learning multi-scale structure, etc., but there is no theory addressing how well the proposed algorithm performs at this task relative to others.\n2) Training / sampling from HiGen could be broken out into algorithms in the text for clearer presentation. At present, reviewing what the algorithms are requires going through several pages of text.\n\nTypos:\n- page 1: Jin et al. unparenthesized\n- page 2: proposed *a* generative model\n- page 7: Kong et al. unparenthesized\n- page 7: \"an analytically solution\"\n- page 7: \"n our experiments,\"\n- page 8: \"However, It’s important\"", "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)