GraphK Generates Variable-Size Graphs with High Efficiency

Deep learning models for graph generation have advanced significantly but often face limitations in scalability, flexibility, and their ability to capture underlying structural properties. Traditional autoregressive approaches are typically constrained by a fixed vocabulary size, meaning they can only generate graphs with a predetermined number of nodes. This research introduces GraphK, a novel encoder-sampler-decoder framework designed to address these issues. GraphK offers structural flexibility by allowing both upscaling (generating graphs larger than the input) and downscaling, providing fine-grained control over the output graph size. It achieves this by learning permutation-invariant latent representations and sampling new node embeddings through maximum likelihood estimation, enabling generalization across diverse graph sizes and structures. For efficient edge generation, GraphK employs a KDTree-based top-k neighbor search within the latent space, significantly reducing computational costs. This approach, based on the manifold smoothness assumption, effectively captures complex graph properties. Experiments on both synthetic and real-world datasets demonstrate that GraphK surpasses existing methods in performance, accurately learning graph structures and generating high-quality synthetic graphs without requiring explicit structural definitions.