GraphK: Variable-Size Graph Generation with Efficient Edge Construction

• URL: http://arxiv.org/abs/2608.18777v1
• Date: Wed, 19 Aug 2026 10:34:17 GMT
• Title: GraphK: Variable-Size Graph Generation with Efficient Edge Construction
• Abstract summary: We present GraphK, a novel encoder-sampler-decoder framework for graph generation.<n>By learning permutation-invariant latent representations, GraphK generalizes across graph sizes and structures.<n>Experiments on synthetic and real-world datasets show that GraphK outperforms existing methods.
• Score: 0.27998963147546135
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph generation models have advanced significantly with deep learning, yet they remain limited in scalability, flexibility, and ability to model underlying structures. We present GraphK, a novel encoder-sampler-decoder framework for graph generation that overcomes these challenges through structural flexibility and computational efficiency. Unlike autoregressive approaches constrained by vocabulary size (i.e. number of nodes in graph generation), GraphK allows for both upscaling (generating graphs with more nodes than the input) and downscaling, providing a flexible control over output graph size. By learning permutation-invariant latent representations and sampling new node embeddings via maximum likelihood estimation, GraphK generalizes across graph sizes and structures. For edge generation, we employ edge prediction with a KDTree-based top-k neighbor search in the latent space, reducing computational cost. Based on the manifold smoothness assumption, our method effectively captures graph properties. Experiments on synthetic and real-world datasets show that GraphK outperforms existing methods, accurately learns graph structures, and generates synthetic graphs without explicit definitions.

Related papers

• Generating Large Semi-Synthetic Graphs of Any Size [0.4419843514606336]
  Graph generation is an important area in network science.<n>Recent advancements in deep learning have enabled data-driven methods to learn and generate graphs.<n>We propose Latent Graph Sampling Generation (LGSG) to generate graphs of varying sizes without retraining.
  arXiv  Detail & Related papers  (2025-07-02T21:46:28Z)
• Scale-Free Graph-Language Models [44.283149785253286]
  Graph-language models (GLMs) have demonstrated great potential in graph-based semi-supervised learning.<n>This paper introduces a novel GLM that integrates graph generation and text embedding within a unified framework.
  arXiv  Detail & Related papers  (2025-02-21T03:41:43Z)
• GraphEdit: Large Language Models for Graph Structure Learning [14.16155596597421]
  Graph Structure Learning (GSL) focuses on capturing intrinsic dependencies and interactions among nodes in graph-structured data.<n>Existing GSL methods heavily depend on explicit graph structural information as supervision signals.<n>We propose GraphEdit, an approach that leverages large language models (LLMs) to learn complex node relationships in graph-structured data.
  arXiv  Detail & Related papers  (2024-02-23T08:29:42Z)
• GraphMaker: Can Diffusion Models Generate Large Attributed Graphs? [7.330479039715941]
  Large-scale graphs with node attributes are increasingly common in various real-world applications. Traditional graph generation methods are limited in their capacity to handle these complex structures. This paper introduces a novel diffusion model, GraphMaker, specifically designed for generating large attributed graphs.
  arXiv  Detail & Related papers  (2023-10-20T22:12:46Z)
• An Accurate Graph Generative Model with Tunable Features [0.8192907805418583]
  We propose a method to improve the accuracy of GraphTune by adding a new mechanism to feed back errors of graph features. Experiments on a real-world graph dataset showed that the features in the generated graphs are accurately tuned compared with conventional models.
  arXiv  Detail & Related papers  (2023-09-03T12:34:15Z)
• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
  arXiv  Detail & Related papers  (2023-06-05T07:53:52Z)
• Explanation Graph Generation via Pre-trained Language Models: An Empirical Study with Contrastive Learning [84.35102534158621]
  We study pre-trained language models that generate explanation graphs in an end-to-end manner. We propose simple yet effective ways of graph perturbations via node and edge edit operations. Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs.
  arXiv  Detail & Related papers  (2022-04-11T00:58:27Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. We propose a novel framework called textitgraphon autoencoder to build an interpretable and scalable graph generative model. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons.
  arXiv  Detail & Related papers  (2021-05-29T08:11:40Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. In this paper, two novel unsupervised graph embedding methods, unsupervised graph embedding via adaptive graph learning (BAGE) and unsupervised graph embedding via variational adaptive graph learning (VBAGE) are proposed. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, and graph visualization tasks.
  arXiv  Detail & Related papers  (2020-03-10T02:33:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.