Introduction
Generating realistic graphs—ranging from social networks and protein structures to 3D point clouds—is a fundamental challenge in machine learning. Most existing graph generative models, such as GraphRNN or GRAN, treat graphs as "flat" entities, generating them node-by-node or edge-by-edge. This approach suffers from two primary drawbacks. First, the computational complexity is often $O(n^2)$ or $O(n)$ in a sequential manner, creating significant bottlenecks for large-scale graphs. Second, these models often exhibit "structural blindness," failing to capture the hierarchical community structures (e.g., neighborhoods within districts within cities) that characterize real-world networks.
HiGeN (Hierarchical Multi-Resolution Graph Generative Networks) addresses these issues by adopting a "coarse-to-fine" approach. By recursively generating community structures and utilizing a novel parallelizable multinomial factorization, HiGeN captures both global topology and local details more effectively than previous state-of-the-art models.
Hierarchical Graph Modeling
The core innovation of HiGeN is the hierarchical decomposition of the target graph. The process begins with a pre-processing step using the Louvain algorithm to detect communities and "coarsen" the graph into multiple levels of abstraction.
In this framework, generation starts at the top (the most abstract level) and works downward. Once the high-level structure is determined, the sub-communities within it are generated in parallel. This "top-down" context is crucial; the representation of a node depends not just on its immediate neighbors but also on its "parent" in the hierarchy, preventing the model from losing global coherence during the generation of large structures.
Recursive Stick-Breaking and Factorization
To handle edge weights and community sizes efficiently, the authors introduce a mathematical technique based on multinomial distribution factorization. This is conceptualized as a "stick-breaking" process: the model first decides the total number of edges or nodes for a group and then "breaks" that total into smaller pieces for individual sub-components.
By partitioning the graph into independent communities, HiGeN achieves a complexity of $O(c \log n)$, where $c$ is the size of the largest community. This parallel architecture allows the model to scale to massive graphs that would be computationally prohibitive for sequential models.
Experimental Evaluation
The model was rigorously tested on five diverse datasets, including synthetic Relaxed Caveman and Planted Partition graphs, as well as real-world Protein structures, Ego citation networks, and complex 3D Point Clouds (containing up to 5,000+ nodes).
HiGeN consistently outperformed or matched state-of-the-art baselines across several key metrics:
- Structural Accuracy: On Maximum Mean Discrepancy (MMD) for degree and clustering distributions, HiGeN showed up to an order-of-magnitude improvement over GRAN, particularly on the Protein and Planted Partition datasets.
- Global Topology: The model significantly improved the capture of graph Laplacian spectra, indicating a superior understanding of global connectivity compared to "flat" models.
- Efficiency: The use of specialized models for each hierarchical level proved more effective than a single shared model, as different levels of abstraction possess distinct statistical properties, such as varying sparsity.
Conclusion and Future Work
HiGeN demonstrates that hierarchical priors are essential for modeling the complex organizational structures of real-world graphs. While the current model relies on external community detection (Louvain) for pre-processing, it sets the stage for future "end-to-end" learning where community structures are learned jointly with the generation process. Scaling these parallel architectures to even larger datasets remains a key objective for future research in graph representation learning.
Summary updated