CS Paper Radar

WL-SeqVAE: Sequence-Based Graph Generation Using Variational Autoencoders and Weisfeiler-Leman Colors

Iakovos Evdaimon, Giannis Nikolentzos, Achilleas Tsimichodimos, Christos Xypolopoulos, Michalis Vazirgiannis

cs.LG ·submitted 2026-10-23 13:58 UTC · v1
code/datahot direction

Abstract

In this paper, we introduce WL-SeqVAE, a sequence-based variational autoencoder for generating graphs. The key observation behind WL-SeqVAE is that node colors induced by the Weisfeiler-Leman (WL) algorithm provide compact discrete summaries of local graph structure and can therefore serve as structural tokens for generation. Rather than learning a distribution over adjacency matrices directly, our method maps each graph to a sequence of WL colors and employs a variational autoencoder that encodes this sequence into a Gaussian latent distribution, from which an autoregressive decoder reconstructs the graph. During generation, compatibility constraints derived from the WL colors guide node and edge predictions, combining global information from the latent representation with local structural consistency. This formulation turns graph generation into a sequence generation problem and avoids directly parameterizing a quadratic adjacency matrix. We evaluate WL-SeqVAE on molecular and general graph generation tasks. Across the evaluated datasets, WL-SeqVAE is competitive with established baselines on several local structural and molecular quality metrics. Code is available at https://github.com/iakovosevdaimon/WL-SeqVAE

Closest papers

Nearest neighbours by meaning across the whole index.

Latent Flow Matching for Molecular Graph Generation

cs.LG cs.AI ·2026-10-05 ·Mathis Goupillon, Roman Bresson, Konstantinos Divriotis, Michalis Vazirgiannis
similarity 0.76
Abstract

Modern graph generative models typically operate directly in the discrete graph space, explicitly generating node and edge variables, which can become costly as graphs grow. In this paper, we perform generation explicitly on latent representations of entire graphs obtained from a pretrained Variational Autoencoder with high reconstruction fidelity. The generated representations, obtained through flow matching, are then decoded only at the final step. Across molecular benchmarks of increasing size, our approach achieves strong validity and FCD while offering a favorable quality-efficiency trade-off compared with state-of-the-art explicit graph generative models. One of the main advantages of this formulation is that the graph representation only needs to be learned once, after which the same one can be reused across multiple generative objectives without retraining. We demonstrate generation guided by molecular properties and further introduce validity-aware generation though a classifier learned directly in latent space. All code will be made available upon acceptance.

0.21

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

cs.LG stat.ML ·2026-10-22 ·Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth
theory similarity 0.70
Abstract

Graphs play a crucial role in many applications, ranging from drug discovery to social network modeling and astronomy. Generative models for graphs have substantially advanced in recent years, but we identify relatively simple scenarios where state-of-the-art models struggle to converge within a standard compute budget, or exhibit prohibitively slow generation times. We propose a generative architecture that achieves quality competitive with state-of-the-art models and is orders of magnitude faster at generation. Our approach is inspired by the Aldous-Hoover theorem, a classic representation theorem that characterizes any probability distribution of graphs that is invariant to permutations of node indices or exchangeable. This theorem establishes that three ingredients suffice: a graph-level latent variable, a set of exchangeable node-specific latent variables, and a so-called graphon function that maps graph- and node-level variables to the probability of an edge between any node pair. Given a training set of graphs, our exchangeable Variational Graph AutoEncoder (xVGAE) learns an approximation to their underlying graphons, as well as graph- and node-level latent variables. We show that our xVGAE encodes latent representations that correlate with graph- and node-level properties, and can (quickly, in one shot) generate new graphs that closely match key training set statistics.

0.20

SNACK: A Sequential Notation Framework for Probabilistic Graph Generation

cs.LG stat.ML ·2026-10-14 ·Hohyun Kim, Hyesung Kim, Min-hwan Oh, Seunggeun Lee
top venue similarity 0.69
Abstract · 30 pages; Accepted at NeurIPS 2026

We introduce SNACK, a string representation for probabilistic graph generation that enables language models to generate graphs with discrete node and edge features. SNACK linearizes graphs by encoding the nonzero entries of the lower-triangular adjacency matrix, establishing a bijective correspondence between valid sequences and ordered adjacency matrices. This design enables invalid logit masking to enforce structural constraints, such as chemical valence and ordering rules, thereby guaranteeing 100% valid generated sequences while sticking to standard language modeling for effective training. SNACK also enables principled string-based GFlowNet training by explicitly accounting for node-ordering symmetries. Across standard graph-generation tasks and molecular distribution-learning benchmarks, SNACK achieves competitive sample quality, while substantially improving the throughput of GFlowNet training relative to graph-based generation. Probing analyses further show that models trained on SNACK encode meaningful local and global graph structure despite receiving only sequential supervision. These results position SNACK as a practical framework for probabilistic graph generation with deep sequence models.

0.28

GraphK: Variable-Size Graph Generation with Efficient Edge Construction

cs.LG ·2026-08-19 ·Resul Tugay, Eren Oluğ, Elif Ak, Sule Gunduz Oguducu
similarity 0.68
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.

0.22

WorldGraph: Graph-Native World Modeling

cs.LG cs.AIcs.CV ·2026-09-28 ·Zezhong Ding, Yipeng Li, Xike Xie
benchmark similarity 0.64
Abstract

World models infer latent states of an environment to capture its underlying dynamics and predict future evolution. Many real-world environments, however, are inherently relational and observed as evolving graphs, where entities, relations, and their properties change over time. Prior graph-related world models use graph structures to organize internal states or support task-specific reasoning, rather than treating an evolving graph itself as the modeled world. We instead study graph world modeling (GWM), where graph evolution itself constitutes the world dynamics. We formulate graph world modeling over observed graph evolution, latent graph states, and heterogeneous graph-transition predictions. Based on this formulation, we construct GWM-Zero, a benchmark covering node-, edge-, and graph-level transitions over eight temporal graph datasets. We propose WorldGraph, which combines a state-aware graph transformer for multi-granularity structural and transition-conditioned evolution modeling with transition-aware GRPO using dynamic grouping and structure-aware verifiable rewards. Extensive experiments on GWM-Zero show that WorldGraph consistently outperforms representative graph representation, temporal graph learning, graph pretraining, and graph world-model baselines across all three transition granularities.

0.15

Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learning

cs.LG ·2026-10-05 ·Nicolas Hochuli, Lorenzo Miele, Kristina Shea, Tino Stankovic
benchmark similarity 0.62
Abstract

Planar graphs are central to applications across science and engineering, yet existing generators provide limited support for goal-directed generation under hard structural and geometric feasibility constraints. We propose a dataset-free method for generating planar graph embeddings by combining parametric graph grammars with safe reinforcement learning to optimize generic task-specific objectives while satisfying constraints during construction. We formulate the generation process as a constrained Markov decision process, where the graph grammar defines the state and action spaces. We further introduce an action projection that maps sampled actions toward state-dependent safe sets, improving constraint satisfaction during training. In contrast to classical graph generators and deep generative models, which typically offer limited goal-directed control or rely on weak constraint satisfaction, our method constructs feasible planar graph embeddings directly during generation. We also introduce a benchmark suite for constrained and goal-directed planar graph generation, together with classical and deep generative baselines. Across all benchmark tasks, our method consistently outperforms baselines while satisfying the formulated constraints.

0.20

Implicit Feature Reweighting for Label-Free Graph Generalization

cs.LG ·2026-10-21 ·Tianjun Yao, Chen Xi, Xinyang Li, Lixian Zhang
code/data similarity 0.61
Abstract · We propose an implicit feature reweighting method to enhance graph-level OOD generalization without class labels

Graph-level out-of-distribution (OOD) generalization is critical for deploying graph neural networks in real-world applications where distribution shifts are inevitable. Existing approaches typically require class labels during representation learning to decide which substructures are predictive, limiting their applicability. We propose SCARCE, a label-free representation-learning framework that yields distribution-shift-robust graph representations from an environment partition of the training graphs alone, whether that partition comes from dataset metadata or, when none is available, from clustering a self-supervised embedding. Our method operates in two stages: (1) a variational graph autoencoder is warm-started for graph reconstruction; and (2) an adversarial confusion mechanism forces the encoder to produce representations from which a discriminator cannot distinguish environments, while preserving graph-reconstruction fidelity. We provide theoretical analysis showing that environment confusion contracts environment-discriminative directions in the representation space, which, under regularized downstream classifiers, is equivalent to imposing a stronger directional penalty on environment-associated features. This feature-reweighting mechanism reduces reliance on spurious correlations without erasing information, offering a label-free, continuous relaxation of last-layer reweighting methods. Experiments on a controlled synthetic datasets and the DrugOOD datasets show that SCARCE achieves state-of-the-art OOD generalization among label-free methods, using no class labels during representation learning.

0.22

Interpretable and Steerable Molecular Graph Generation using Concept Bottlenecks

cs.LG ·2026-10-25 ·Sarabeshwar Balaji, Ritesh Kumar, Lav R. Varshney
published similarity 0.61
Abstract · Accepted at AI for Drug Discovery Workshop @ NeurIPS 2026. Additional experiments added

Deep graph generators (DGGs) largely lack interpretability, which is a significant limitation for one of their most crucial applications, drug discovery, where interpretable and transparent generation could provide greater control over the desirability of generated molecules, thereby reducing trial-and-error in candidate selection. Common approaches to interpretability, such as disentanglement, cannot guarantee that the learned representations are human-interpretable. To address this, we propose incorporating concept bottlenecks into DGGs, allowing users to interpret, debug, and steer the generation process. We show that this consistently improves distributional fidelity (lower FCD), with only modest, non-systematic effects on validity and uniqueness. We further explore Concept Controller, an optimization-based steering approach that has proven to be effective for steerable image generation. We evaluate our approach on a one-shot molecular graph generation framework, though the underlying ideas can be transferred to sequential graph generation as well.

0.20