HiGen: Hierarchical Graph Generative Networks

Most real-world graphs exhibit a hierarchical structure, which is often overlooked by existing graph generation methods. In his work, we introduce HiGen, a Hierarchical Graph Generative Networkto 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 is performed in parallel, followed by the prediction of cross-edges between communities using a separate model. This parallelized approach enables high scalability.To capture hierarchical relations, our model allows each node at a given level to depend not only on its neighbouring nodes but also on its corresponding super-node at the higher level. Furthermore, we address the generation of integer-valued edge weights of the hierarchical structure by modeling the output distribution of edges using a 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 a predefined initial ordering of nodes. Empirical studies demonstrate that the proposed generative model captures both local and global properties of graphs and achieves state-of-the-art performance in terms of graph quality on various benchmark graph datasets.