Size Matters: Large Graph Generation with HiGGs

Large graphs are present in a variety of domains, including social networks, civilinfrastructure, and the physical sciences to name a few. Graph generation issimilarly widespread, with applications in drug discovery, network analysis andsynthetic datasets among others. While GNN (Graph Neural Network) modelshave been applied in these domains their high in-memory costs restrict them tosmall graphs. Conversely less costly rule-based methods struggle to reproducecomplex structures. We propose HIGGS (Hierarchical Generation of Graphs)as a model-agnostic framework of producing large graphs with realistic localstructures. HIGGS uses GNN models with conditional generation capabilities tosample graphs in hierarchies of resolution. As a result HIGGS has the capacityto extend the scale of generated graphs from a given GNN model by quadraticorder. As a demonstration we implement HIGGS using DiGress, a recent graph-diffusion model, including a novel edge-predictive-diffusion variant edge-DiGress.We use this implementation to generate categorically attributed graphs with tensof thousands of nodes. These HIGGS generated graphs are far larger than anypreviously produced using GNNs. Despite this jump in scale we demonstrate thatthe graphs produced by HIGGS are, on the local scale, more realistic than thosefrom the rule-based model BTER.