HiGeN: Hierarchical Multi-Resolution Graph Generative Networks

Mahdi Karami, Jun LuoarXiv 2023 · DOI · arXiv

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.

The hierarchical decomposition process. A single "super-node" at a higher level ($l_0, l_1$) represents an entire community at the level below ($l_2, l_3$).

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.

The recursive stick-breaking process using multinomial factorization. This allows the model to handle integer-valued edge weights and enables parallel generation of community 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

Abstract

In real world domains, most graphs naturally exhibit a hierarchical structure. However, data-driven graph generation is yet to effectively capture such structures. To address this, we propose a novel approach that recursively generates community structures at multiple resolutions, with the generated structures conforming to training data distribution at each level of the hierarchy. The graphs generation is designed as a sequence of coarse-to-fine generative models allowing for parallel generation of all sub-structures, resulting in a high degree of scalability. Our method demonstrates generative performance improvement on multiple graph datasets.
BibTeX
@misc{karami2023higen,
  author = {Mahdi Karami and Jun Luo},
  title = {{HiGeN: Hierarchical Multi-Resolution Graph Generative Networks}},
  year = {2023},
  eprint = {2303.03293},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.03293},
}
Figure