PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.32650v1cs.LG

TL;DR

Graph generation remains difficult because graph structures are combinatorial, variable-sized, and costly to model directly. WL-SeqVAE encodes WL-color sequences into a Gaussian latent space and decodes graphs autoregressively under compatibility constraints; it is reported as competitive across molecular and general graph generation tasks.

  • Problem

    Graph generation must contend with combinatorial structures, permutation invariance, varying graph sizes, complex dependencies, and a quality–scalability trade-off.

    Source: §1 · p. 2

  • Method

    WL-SeqVAE encodes sequences of WL-derived node colors into a continuous latent representation and autoregressively decodes graphs under WL-derived compatibility constraints.

    Source: §4.1 · p. 4, §4.3 · p. 6, §6 · p. 12

  • Results

    WL-SeqVAE is competitive with current state-of-the-art models on molecular and general graph generation tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The sequence-generation formulation avoids directly generating a quadratic adjacency matrix while retaining competitive results across several graph-quality metrics.

    Source: §6 · p. 12

    WL constraints are local and do not guarantee global properties such as planarity, exact grid structure, or community structure.

    Source: §C.1 · p. 22

Abstract

from arXiv · show

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

1 Introduction

Graph generation is in demand for producing realistic samples, but remains challenging because graphs vary in size, are permutation-invariant, and have complex dependencies. WL-SeqVAE models WL-derived node colors as sequences and reports competitive results on molecular and general graph generation.

1 Introduction

  • Generative graph models are needed to produce realistic graphs preserving observed structural characteristics across application domains.Source: §1 · pp. 1–2
  • Graph generation remains challenging because of combinatorial structure, permutation invariance, varying graph sizes, complex dependencies, and the trade-off between quality and scalability.Source: §1 · p. 2
  • The paper proposes WL-SeqVAE, which uses Weisfeiler–Leman node colors as structural tokens for graph generation.Source: §1 · p. 2
  • Its VAE encoder maps node sequences to a Gaussian latent distribution, while an autoregressive decoder reconstructs graphs under WL-derived compatibility constraints.The design combines global latent information with local structural consistency.Source: §1 · p. 2
  • WL-SeqVAE is competitive with current state-of-the-art graph generators on molecular and general graph generation tasks.The sequence-generation formulation is presented as mitigating challenges from quadratic graph complexity.Source: §1 · p. 2

2 Related Work

Graph-generation research spans autoregressive, VAE, GAN, flow, diffusion, and flow-matching approaches. WL-SeqVAE is positioned near motif-based generation, while the authors state that prior work had not explored WL for graph generation.

2 Related Work

  • Graph-generation approaches include autoregressive models, VAEs, GANs, normalizing flows, diffusion models, and flow matching.Source: §2 · p. 2
  • Autoregressive methods model conditional node and edge distributions, while VAEs reconstruct graphs from continuous latent representations.The section also surveys GAN and normalizing-flow models and representative examples.Source: §2 · p. 2
  • Diffusion methods expanded from score-based models to discrete, autoregressive, and latent variants; CatFlow and Defog represent discrete flow matching.Source: §2 · p. 3
  • Motif-based graph generation is identified as the closest related approach, and the authors state that prior work had not used WL for graph generation.The cited example is a hierarchical VAE that generates molecular graphs from structural motifs [15].Source: §2 · p. 3

3 Preliminaries

The preliminaries establish graph notation and explain how 1-WL iteratively refines vertex colors. Each refinement incorporates a node’s previous color and its neighbors’ previous colors, producing increasingly fine color classes.

3.1 Notation

  • A graph is denoted G = (V, E), with n vertices and m edges; the notation also defines neighborhoods, degree, eccentricity, rings, shortest-path distance, and stubs.Source: §3.1 · p. 3
  • The paper treats graphs as colored graphs, where a coloring assigns each vertex a color, and assumes a monochromatic coloring when none is specified.Source: §3.1 · p. 3

3.2 Weisfeiler-Leman Algorithm

  • The 1-dimensional WL algorithm repeatedly refines vertex colors by incorporating each vertex’s previous color and the multiset of its neighbors’ previous colors.The resulting color classes are at least as fine as those from the preceding iteration.Source: §3.2 · pp. 3–4
  • Across a collection of graphs, WL iteration ℓ assigns each vertex a color c(ℓ) from the iteration’s color set.Source: §3.2 · p. 3
  • Figure 1 outlines the model pipeline: a BFS ring-ordered sequence of 1-WL colors is encoded as a Gaussian latent representation, then decoded autoregressively under WL-compatibility constraints.Source: Figure 1 · p. 4

4 The WL-SeqVAE Graph Generator

WL-SeqVAE represents graphs as ordered sequences of Weisfeiler–Leman node colors and uses a VAE to encode and reconstruct those sequences. Its encoder and decoder use color-derived structure to guide graph generation.

4.1 Node colors

  • Final WL colors encode information from each node’s L-hop neighborhood and serve as the model’s node representations.Separate embedding layers are used for colors from each WL iteration.Source: §4.1 · p. 4

4.2 Encoder

  • A Transformer encoder processes a sequence ordered from a minimum-eccentricity central node, with remaining nodes sorted lexicographically by their signatures.A [CLS] token is prepended, and the normalized [CLS] representation is projected to Gaussian parameters.Source: §4.2 · pp. 4–5

4.3 Decoder

  • The decoder generates ring by ring, predicting the central node’s final WL color before predicting compatible neighbor colors and candidate edges.Edge predictions require reciprocal compatible unresolved stubs; decoder inputs also include a representation of the graph constructed so far.Source: §4.3 · p. 6

4.4 Training Objective

  • Training combines reconstruction and regularization losses, with reconstruction covering node-color prediction and two types of edge prediction.The edge components cover links between adjacent rings and within the same ring; node-color prediction uses teacher forcing and restricts non-central predictions to compatible colors.Source: §4.4 · p. 7

4.5 Sampling

  • Sampling starts from a central node and resolves compatible stubs ring by ring, stopping when stubs are resolved or the node limit is reached.The node limit is set from a sampled target size and a hyperparameter; termination with no unresolved stubs yields a WL-complete graph.Source: §4.5 · p. 8

5 Experimental Evaluation

The evaluation covers general graph generation and molecular generation on QM9 and ZINC250K. WL-SeqVAE shows dataset- and metric-dependent results, with local structural statistics captured more effectively than stronger global structure and molecular distribution matching remaining challenging.

5 Experimental Evaluation

  • The evaluation tests structural properties on four general graph datasets and chemical validity and diversity on QM9 and ZINC250K.General-graph comparisons use degree, clustering, and orbit MMD2, where lower values indicate closer agreement with the test distribution.Source: §5 · p. 8, §5.1 · p. 9

5.1 General Graph Generation

  • For general graphs, the study compares WL-SeqVAE with five baselines, using the full set on Ego-small and Community-small but only CatFlow on Enzymes and Grid.The reported protocol follows CatFlow and uses ordered GDSS splits.Source: §5.1 · p. 9
  • On general graphs, WL-SeqVAE performs well on some local statistics but varies by dataset: it matches CatFlow's Ego-small orbit score at 0.008 and reaches 0.019 degree MMD2 on Community-small.It trails CatFlow on all three Enzymes statistics; on Grid, its orbit MMD2 is 0.0442 versus CatFlow's 0.075, while degree and especially clustering are less favorable.Source: §5.1 · pp. 9–10, Table 2 · p. 10

5.2 Molecular Graph Generation

  • For molecular evaluation, each seed uses 10,000 generation attempts; validity is measured over all attempts without valency correction or edge resampling, and uniqueness over RDKit-valid molecules.FCD compares valid generated molecules with the test reference distribution; novelty is omitted under the stated CatFlow protocol.Source: §5.2 · p. 10
  • On QM9, WL-SeqVAE reaches 99.74% validity, 94.74% uniqueness, and 1.4071 FCD; on ZINC250K, it reaches 93.16% validity, 100.00% uniqueness, and 18.1730 FCD.QM9 uniqueness is lower and FCD higher than CatFlow's; ZINC250K FCD is higher than GDSS, Dirichlet FM, CatFlow, and DeFoG. Distribution matching remains challenging.Source: §5.2 · p. 11, Table 3 · p. 11
  • High molecular validity does not guarantee strict WL completion: a molecule can be chemically valid while leaving sampled local WL constraints or stubs unresolved.WL-completeness measures the fraction of generated samples satisfying all local WL constraints with no unresolved stubs.Source: §5 · p. 9, §5.2 · p. 11
  • Generated examples show small QM9 molecules with common oxygen- and nitrogen-containing groups and larger ZINC structures with aromatic systems, heterocycles, amides, and halogen substituents.The examples are described as structurally diverse and visually consistent with their respective dataset distributions.Source: §5.2 · pp. 11–12, Figure 2 · p. 11

6 Conclusion

WL-SeqVAE recasts graph generation as sequence generation using WL colors as structural tokens, combining a continuous latent representation with WL-derived compatibility constraints. Experiments on molecular and abstract graphs find it competitive with established baselines across several quality metrics.

6 Conclusion

  • WL-SeqVAE encodes sequences of WL colors into a continuous latent representation and decodes autoregressively under WL-derived compatibility constraints.This combines global latent information with local structural consistency while avoiding direct generation of a quadratic adjacency matrix.Source: §6 · p. 12

A.1 Experimental Setup and Configuration

  • Training uses four Transformer layers, four attention heads, hidden dimension 192, latent dimension 64, and dropout 0.1 unless noted otherwise.Batch size and maximum sequence length vary by dataset and WL depth.Source: §A.1 · p. 15

A.2 Baseline Models

  • The comparison spans autoregressive, VAE, adversarial, flow, diffusion, and flow-matching graph generators.Baselines include GraphVAE, GNF, EDP-GNN, GDSS, and CatFlow for general graphs, with additional molecular and PROTEINS-specific comparisons.Source: §A.2 · p. 17

A.3 Evaluation Details

  • General-graph evaluation uses ordered splits and degree, clustering, and orbit MMD2, while molecular evaluation reports validity, uniqueness, and FCD.Molecular FCD is computed over valid generated molecules with duplicates retained.Source: §A.3 · p. 17

A.4 Three-Seed Results

  • Results are reported as mean and population standard deviation over three seeds, with sensitivity tables covering WL depths and checkpoint roles.The last completed epoch appears only as a diagnostic in those tables.Source: §A.4 · p. 18, Table 6 · p. 18, Table 7 · p. 18

A.5 Additional Results

Additional evaluations show that WL-SeqVAE can produce unique, novel, and dataset-valid graphs, but its agreement with reference structural statistics varies by dataset. PROTEINS and Planar results highlight that validity or diversity alone does not ensure close distribution matching.

Proteins Dataset

  • PROTEINS graphs were fully unique and novel, but WL-SeqVAE had higher orbit MMD2 than every reported baseline and did not match SPECTRE on higher-order statistics.Its degree MMD2 was lower than GRAN and both GG-GAN variants, while its clustering MMD2 was comparable to GraphRNN and lower than both GG-GAN variants.Source: §A.5 · pp. 18–19, Table 11 · p. 20

Synthetic Graph Generation

  • Planar generation achieved 100% V.U.N. versus CatFlow’s 80%, yet degree, clustering, and orbit ratios were substantially higher than the baselines.The 0% strict WL-completion rate can coexist with dataset validity because graphs may satisfy dataset criteria while leaving local WL requirements unresolved.Source: §A.5 · p. 19, Table 12 · p. 20
  • No SBM run produced all 40 requested graphs; the reported results suggest local WL compatibility alone is insufficient to reproduce global community structure.The authors identify community-level or spectral conditioning as a direction to address this gap.Source: §A.5 · pp. 19–20, Table 12 · p. 20

A.6 Vocabulary Growth and Dataset-Dependent Training Time

Increasing WL refinement depth substantially expands the color vocabulary, especially on larger datasets, without a proportional increase in training time. The reported timing patterns vary with dataset size.

Dataset-Dependent Training Time

  • Training and validation times remain relatively stable or even decrease on smaller datasets, whereas larger datasets show more moderate increases, suggesting deeper WL refinement need not add substantial computational overhead.Source: §A.6 · p. 21

Vocabulary Growth

  • WL vocabulary size increases substantially with refinement depth, particularly for QM9, ZINC250K, and PROTEINS.Figure 3 plots training-set vocabulary growth from one to three iterations using dataset-specific logarithmic scales.Source: §A.6 · p. 20, Figure 3 · p. 21

B Samples from WL-SeqVAE

The appendix describes how representative graph and molecular samples are selected for display. The limitations section restricts the model’s feature scope to discrete labels and excludes continuous, mixed, and conditional graph attributes.

B Samples from WL-SeqVAE

  • For Enzymes, PROTEINS, SBM, and Planar, 20 evenly spaced generated graphs are selected after sorting by graph size, edge-list signature, and generation order.The selection is described as representing the output range without manual curation.Source: B Samples from WL-SeqVAE · p. 21
  • Molecular examples are selected from valid, unique canonical SMILES in first-occurrence order, using the validation-selected two-iteration configuration.Twenty evenly spaced examples are retained for each dataset.Source: B Samples from WL-SeqVAE · p. 21

C Limitations

  • WL-SeqVAE uses finite atom and bond categories as discrete labels and does not handle continuous attributes, mixed feature vectors, or conditional graph-level targets.Source: C Limitations · p. 22

C.1 Methodological Limitations

WL-compatible actions do not guarantee strict completion, and local WL constraints do not ensure global graph or molecular properties.

C.1 Methodological Limitations

  • Completion ranges from 11.67% for Grid at 3 WL iterations to 89.17% for Ego-small at 1 WL iteration.Each accepted action is WL-compatible, but one or more sampled WL requirements may remain unresolved when generation stops.Source: §C.1 · p. 22
  • Local WL constraints ensure reciprocal compatibility between edge endpoints but do not guarantee planarity, exact grid structure, community structure, synthesizability, or other molecular properties.Graphs can be connected and molecules chemically valid while performing poorly on datasets with strong global constraints.Source: §C.1 · p. 22

C.2 Practical Limitations

The sequential decoder's trace vocabulary grows with WL depth and graph diversity, while larger graphs may require longer sequences and larger trace caches for high completion.

C.2 Practical Limitations

  • The sequential decoder's trace vocabulary grows with WL depth and graph diversity.Higher WL depths can improve structural specificity but also enlarge the color vocabulary and increase sparsity.Source: §C.2 · p. 22
  • Higher WL depths can improve structural specificity but enlarge the color vocabulary and increase sparsity.Source: §C.2 · p. 22
  • Larger molecules or graphs may require longer maximum sequences and larger trace caches to achieve high completion.Source: §C.2 · p. 23

Related papers

Loading 2610.32650v1…